Алгоритмы - Структуры данных

 
 List.createList().getLength() = 0
 List.insert(i,x).getLength() = List.getLength() + 1
 List.remove(i).getLength() = List.getLength() - 1
 List.createList().isEmpty() = true
 List.insert(i,item).isEmpty() = false
 List.createList().remove(i) = error
 List.insert(i,x).remove(i) = List
 List.createList().retrieve(i) = error
 List.insert(i,x).retrieve(i) = x
 List.retrieve(i) = List.insert(i, x).retrieve(i+1)
 List.retrieve(i+1) = aList.remove(i).retrieve(i)
 
 

 
 #define N 1000
 
 int main() {
   int i, j, a[N];
 
   for (i = 2; i < N; ++i)
     a[i] = 1;
   for (i = 2; i < N; ++i)
     if (a[i])
       for (j = i; i*j < N; ++j)
 	a[i*j] = 0;
   for (i = 2; i < N; ++i)
     if (a[i])
       printf("%4d ", i);
   printf("\n");
 }
 
 

 
 func main() {
     primes := make([]int, 0)
     n := 1000
 	checked := make([]bool, n)
 	sqrt_n := int(math.Sqrt(float64(n)))
 
 	for i := 2; i <= sqrt_n; i++ {
 		if !checked[i] {
 			for j := i * i; j < n; j += i {
 				checked[j] = true
 			}
 		}
 	}
 
 	for i := 1; i < n; i++ {
 		if !checked[i] {
 			primes = append(primes, i)
 		}
 	}
 
 	fmt.Printf("%v \n", primes)
 	return
 }
 
 

 
 n = 1000
 a = []
 for i in range(n + 1):
     a.append(i)
 i = 2
 while i <= n:
     if a[i] != 0:
         j = i + i
         while j <= n:
             a[j] = 0
             j = j + i
     i += 1
 i = 0
 while i < len(a):
     if a[i] != 0:
         print i
     i += 1
 
 
 

Связные списки

 
 struct node{
     int info;
     struct node *link;
 };
 struct node *start=NULL;
 struct node * createnode(){
   struct node *t;
   t=(struct node*)malloc(sizeof(struct node));
   return(t);
 }
 
 

 
 type List struct {
     Length int
     Head   *Node
     Tail   *Node
 }
 func NewList() *List {
     l := new(List)
     l.Length = 0
     return l
 }
 type Node struct {
     Value interface{}
     Prev  *Node
     Next  *Node
 }
 
 

 
 class Node:
     def __init__(self, data):
         self.data = data 
         self.next = None 
     def __repr__(self):  
         return f"Node({self.data})"
 
 class LinkedList:
     def __init__(self):
         self.head = None 
 
     def insert_tail(self, data) -> None:
         pass
 
     def insert_head(self, data) -> None:
         pass
 
     def delete_head(self):  # delete from head
         pass
 
     def delete_tail(self):  # delete from tail
         pass
 
     def __getitem__(self, index):
         current = self.head
         ...
         return current
 
     def __setitem__(self, index, data):
         current = self.head
         ...
 
 

Поиск в связном списке

 
 list *search_list(list *l, item_type x)
 {
     if (l == NULL) return(NULL);
     if (l->item == x)
         return(l); 
     else
         return( search_list(l->next, x) );
 }
 
 

 
 func (l *List) Get(index int) (*Node, error) {
 	if index > l.Len() {
 		return nil, errors.New("Index out of range")
 	}
 	node := l.Head
 	for i := 0; i < index; i++ {
 		node = node.Next
 	}
 	return node, nil
 }
 
 

 
    def get_item(self, data):
         current = self.head
         while current:
             if data == current.data:
                 return current
             current = current.next
         return None
 
 

Вставка в связном списке

 
 void insert_list(list **l, item_type х)
 {
     list *р;
     /* Временный указатель */
     р = malloc(sizeof(list) );
     p->item = х;
     p->next = *l;
     *l = р;
 }
 
 

 
 func NewNode(value interface{}) *Node {
 	return &Node{Value: value}
 }
 
 func (l *List) Add(value interface{}, index int) error {
 	if index > l.Len() {
 		return errors.New("Index out of range")
 	}
 
 	node := NewNode(value)
 
 	if l.Len() == 0 || index == 0 {
 		l.Prepend(value)
 		return nil
 	}
 
 	if l.Len()-1 == index {
 		l.Append(value)
 		return nil
 	}
 
 	nextNode, _ := l.Get(index)
 	prevNode := nextNode.Prev
 
 	prevNode.Next = node
 	node.Prev = prevNode
 
 	nextNode.Prev = node
 	node.Next = nextNode
 
 	l.Length++
 
 	return nil
 }
 
 
 

 
     def append(self, data):
         n = Node(data)
         if not self.head:
             self.head = n
             self.tail = n
         else:
             self.tail.next = n
             self.tail = self.tail.next
 
 

Удаление в связном списке

 
 list *remove_list(list *1, item_type x)
 {
     if ((l == NULL) M (l->next == NULL)) {
         printf("Error: null list.\n"); return(NULL);
     }
     if ((l->next)->item == х)
         return(l);
     else
         return( remove_list(l->next, x));
 }
 
 delete_list(list **1, item_type х)
 {
     list *р;       /* Указатель на узел*/
     list *pred;    /* Указатель на предшествующий узел  */
     list *search_list(), *remove_list();
     р = search_list(*l,х);
     if (р ! = NULL) {
         pred = remove_list(*l,x);
         if (pred == NULL)    /* Соединяем список */
             *l = p->next;
         else
             pred->next = p->next;
             free(p);    /* Освобождение памяти узла */
     }
 }
 
 
 

 
 func (l *List) Remove(value interface{}) error {
 	if l.Len() == 0 {
 		return errors.New("Empty list")
 	}
 
 	if l.Head.Value == value {
 		l.Head = l.Head.Next
 		l.Length--
 		return nil
 	}
 
 	found := 0
 	for n := l.Head; n != nil; n = n.Next {
 
 		if *n.Value.(*Node) == value && found == 0 {
 			n.Next.Prev, n.Prev.Next = n.Prev, n.Next
 			l.Length--
 			found++
 		}
 	}
 
 	if found == 0 {
 		return errors.New("Node not found")
 	}
 
 	return nil
 }
 
 

 
     def delete(self, data):
         pre = None
         cur = self.head
         while(cur):
             if cur.data == data:
                 if pre:
                     pre.next = cur.next
                 else:
                     self.head = self.head.next
                 cur = None
                 break
             pre = cur
             cur = cur.next	
         self.curr = None
 

Стеки и очереди

Словари

Двоичные деревья поиска (BST)

 
 typedef struct tree {
     item_type item;
     struct tree *parent;
     struct tree *left;
     struct tree *right;
 } tree;
 
 

 
 type Node struct {
     Value  int
     Parent *Node
     Left   *Node
     Right  *Node
 }
 type Tree struct {
     Head *Node
     Size int
 }
 
 

 
 class BSTnode(object):
     def __init__(self, parent, t):
         self.key = t
         self.parent = parent
         self.left = None
         self.right = None
         self.size = 1
 

Поиск в двоичных поисковых деревьях

 
 tree *search_tг е е (tree *l, item_type х)
 {
     if (l == NULL) return (NULL);
     if (l->item == x) return(l);
     if (x < l->item)
         return( search_tree(l->left, x));
     else
         return(search_tree(l->right, x) );
 }
 
 

 
 
 func (n *Node) Compare(m *Node) int {
 	if n.Value < m.Value {
 		return -1
 	} else if n.Value > m.Value {
 		return 1
 	} else {
 		return 0
 	}
 }
 
 func (t *Tree) Search(i int) *Node {
 	h := t.Head
 	n := &Node{Value: i}
 
 	for h != nil {
 		switch h.Compare(n) {
 		case -1:
 			h = h.Right
 		case 1:
 			h = h.Left
 		case 0:
 			return h
 		default:
 			panic("Node not found")
 		}
 	}
 	panic("Node not found")
 }
 
 

 
     def find(self, t):
         if t == self.key:
             return self
         elif t < self.key:
             if self.left is None:
                 return None
             else:
                 return self.left.find(t)
         else:
             if self.right is None:
                 return None
             else:
                 return self.right.find(t)
 
 
 

Поиск минимума в двоичных поисковых деревьях

 
 tree *find_minimum(tree *t)
 {
     tree *min; /* Указатель на наименьший элемент    */
     if (t == NULL) return(NULL);
     min = t;
     while (min->left != NULL)
         min = min->left;
     return(min);
 }
 
 

 
 func (tree *BinaryTree) Min() interface{} {
 	if tree.node == nil || tree.left.node == nil {
 		return tree.node
 	}
 	return tree.left.Min()
 }
 
 

 
    def minimum(self):
          current = self
          while current.left is not None:
              current = current.left
          return current
 
 

 
 void traverse_tree(tree *l)
 {
     if (l != NULL) {
         traverse_tree(l->left);
         proCess_item(l->item);
         traverse_tree(l->right) ;
     }
 }
 
 

Вставка в двоичных поисковых деревьях

Си:

 
 insert_tгее (tree **l, item_type х, tree *parent)
 {
     tree    *p;    /* Временный указатель */
     if (*l == NULL) {
         p = malloc(sizeof(tree)); /* Выделение памяти для нового узла */
         p->item = х;
         p->left = p->right = NULL;
         p->parent = parent;
         *l = p;         /* Указатель на родительский узел */
         return;
     }
     if (x < (*l)->item)
     insert_tree(&((*l)->left), x, *1);
     else
     insert_tree(&((*l)->right), x, *1);
 }
 
 

Go:

 
 func (t *Tree) Insert(i int) {
 	n := &Node{Value: i}
 	if t.Head == nil {
 		t.Head = n
 		t.Size++
 		return
 	}
 
 	h := t.Head
 
 	for {
 		if n.Compare(h) == -1 {
 			if h.Left == nil {
 				h.Left = n
 				n.Parent = h
 				break
 			} else {
 				h = h.Left
 			}
 		} else {
 			if h.Right == nil {
 				h.Right = n
 				n.Parent = h
 				break
 			} else {
 				h = h.Right
 			}
 		}
 	}
 	t.Size++
 }
 
 

Python:

 
     def insert(self, t, NodeType):
          self.size += 1
          if t < self.key:
              if self.left is None:
                  self.left = NodeType(self, t)                
                  return self.left
              else:
                  return self.left.insert(t, NodeType)
          else:
              if self.right is None:
                  self.right = NodeType(self, t)   
                  return self.right
              else:
                  return self.right.insert(t, NodeType)
 
 

Удаление в двоичных поисковых деревьях

Си:

 
 int delete(struct tree * search_tree, int ** item)
  {
  	struct node ** q,*z;
  	
  	q=&search_tree->root;
  	z=search_tree->root;
  	for(;;)
  	{
  		if(z == NULL) return 0;
  		else if(item == (int **)z->data) break;
  		else if(item > (int **)z->data)
  		{
  			q = &z->right;
  			z = z->right;
  		}
  		else
  		{
  			q = &z->left;
  			z = z->left;
  		}
  	}		
  	
  	// нашли - теперь удаляем
  	if(z->right == NULL) *q = z->left;
  	else
  	{
  		struct node * y = z->right;
  		if(y->left == NULL)
  		{
  			y->left = z->left;
  			*q-y;
  		}
  		else
  		{
  			struct node * x=y->left;
  			while(x->left != NULL)
  			{
  				y = x;
  				x = y->left;
  			}
  			y->left = x->right;
  			x->left = z->left;
  			x->right = z->right;
  			*q=x;
  		}
  	}
  
  	search_tree->count --;
  	free(z);
  	return 1;
  }
 
 

Go:

 
 func (t *Tree) Delete(i int) bool {
 	var parent *Node
 
 	h := t.Head
 	n := &Node{Value: i}
 	for h != nil {
 		switch n.Compare(h) {
 		case -1:
 			parent = h
 			h = h.Left
 		case 1:
 			parent = h
 			h = h.Right
 		case 0:
 			if h.Left != nil {
 				right := h.Right
 				h.Value = h.Left.Value
 				h.Left = h.Left.Left
 				h.Right = h.Left.Right
 
 				if right != nil {
 					subTree := &Tree{Head: h}
 					IterOnTree(right, func(n *Node) {
 						subTree.Insert(n.Value)
 					})
 				}
 				t.Size--
 				return true
 			}
 
 			if h.Right != nil {
 				h.Value = h.Right.Value
 				h.Left = h.Right.Left
 				h.Right = h.Right.Right
 
 				t.Size--
 				return true
 			}
 
 			if parent == nil {
 				t.Head = nil
 				t.Size--
 				return true
 			}
 
 			if parent.Left == n {
 				parent.Left = nil
 			} else {
 				parent.Right = nil
 			}
 			t.Size--
 			return true
 		}
 	}
 	return false
 }
 
 

Python:

 
     def delete(self):
             if self.left is None or self.right is None:
                 if self is self.parent.left:
                     self.parent.left = self.left or self.right
                     if self.parent.left is not None:
                         self.parent.left.parent = self.parent
                 else:
                     self.parent.right = self.left or self.right
                     if self.parent.right is not None:
                         self.parent.right.parent = self.parent 
                 current = self.parent
                 while current.key is not None:
                     current.update_stats()
                     current = current.parent
                 return self
             else:
                 s = self.successor()
                 self.key, s.key = s.key, self.key
                 return s.delete()        
 

Оставьте свой комментарий !
Ваше имя: Комментарий: Оба поля являются обязательными  Автор   Комментарий к данной статье