github仓库
链表 单向链表
单向链表每次查找只能从前向后查找，单向的，只会有一个指针并且指向下一个节点。所以每个节点只能找到自己后面的节点，但是无法找到之前的链表。
对于循环 链表，最末端的节点会指向头节点，形成首尾相接的循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 #include <stdio.h> #include <stdlib.h> #define ListNode(T) typedef struct listnode_##T{\ struct listnode_##T* next;\ T val;\ }listnode_##T; #define listnode(T) listnode_##T #define NewListNode(T) listnode_##T* newListNode_##T(T val){\ listnode_##T *node = (listnode_##T *) malloc(sizeof(listnode_##T));\ node->next = NULL;\ node->val = val;\ return node;\ } #define newListNode(T) newListNode_##T #define DeleteListNode(T) void deleteListNode_##T(listnode_##T *node){\ free(node);\ } #define deleteListNode(T) deleteListNode_##T #define LinkedList(T) typedef struct linkedlist_##T{\ struct listnode_##T *head;\ struct listnode_##T *tail;\ int length;\ T val;\ void (*insert)(struct linkedlist_##T *list, int index, listnode_##T* node);\ void (*remove)(struct linkedlist_##T *list, int index);\ void (*merge)(struct linkedlist_##T *dst, struct linkedlist_##T *src, int dstbegin, int srcbegin, int srcend);\ void (*clear)(struct linkedlist_##T *list);\ int (*isempty)(struct linkedlist_##T *list);\ }linkedlist_##T; #define linkedlist(T) linkedlist_##T #define Insert(T) void insert_##T(linkedlist_##T* list, int index, listnode_##T* node){\ listnode_##T *iterator = list->head;\ while(iterator->next != list->tail && index--){\ iterator = iterator->next;\ }\ if (index > 0)printf("index has out of range, but will insert tail\n" );\ node->next = iterator->next;\ list->length++;\ iterator->next = node;\ } #define Remove(T) void remove_##T(linkedlist_##T* list, int index){\ listnode_##T *iterator = list->head;\ if (!list->length){\ printf("this list is empty, can't remove node\n" );\ return;\ }\ index--;\ while(iterator->next != list->tail && index-- > 0){\ iterator = iterator->next;\ }\ if (index != 0){\ printf("index has out of range, can't remove node\n" );\ return;\ }\ listnode_##T *node = iterator->next;\ iterator->next = iterator->next->next;\ free(node);\ list->length--;\ } #define Merge(T) void merge_##T(linkedlist_##T *dst, struct linkedlist_##T *src, int dstbegin, int srcbegin, int srcend){\ listnode_##T *dstit = dst->head;\ listnode_##T *srcit = src->head;\ while(dstit->next != dst->tail && dstbegin-- > 0) dstit = dstit->next;\ if (dstbegin > 0) printf("dstbegin has out of range, so merge begin at the tail\n" );\ listnode_##T *copybegin;\ listnode_##T *copyend;\ int copylength = 0;\ while(srcit->next != src->tail){\ srcit = srcit->next;\ srcbegin--;\ srcend--;\ if (srcend <= 0)break;\ if (srcbegin == 0){\ copybegin = newListNode(T)(srcit->val);\ copyend = copybegin;\ copylength++;\ }\ else if (srcbegin < 0){\ listnode_##T *node = newListNode(T)(srcit->val);\ copyend->next = node;\ copyend = copyend->next;\ copylength++;\ }\ }\ if (srcbegin > 0 ){\ printf ("srcbegin has out of range, so stop merge\n" );\ return ;\ }\ copyend->next = dstit->next;\ dstit->next = copybegin;\ dst->length += copylength;\ } #define Clear(T) void clear_##T(linkedlist_##T *list){\ listnode_##T *it = list->head;\ while(it->next != list->tail){\ listnode_##T *deletenode = it->next;\ it->next = it->next->next;\ free(deletenode);\ }\ list->length = 0;\ } #define Isempty(T) int isempty_##T(linkedlist_##T *list){\ return list->head->next == list->tail;\ } #define NewLinkedList(T) linkedlist_##T *newLinkedList_##T(){\ linkedlist_##T *list = (linkedlist_##T *)malloc(sizeof(linkedlist_##T));\ list->head = (listnode_##T *)malloc(sizeof(listnode_##T));\ list->head->val = 0;\ list->tail = (listnode_##T *)malloc(sizeof(listnode_##T));\ list->tail->val = 0;\ list->length = 0;\ list->head->next = list->tail;\ list->tail->next = NULL;\ list->insert = insert_##T;\ list->remove = remove_##T;\ list->merge = merge_##T;\ list->clear = clear_##T;\ list->isempty = isempty_##T;\ return list;\ } #define newLinkedList(T) newLinkedList_##T() #define DeleteLinkedList(T) void deleteLinkList_##T(linkedlist_##T *list){\ listnode_##T *iterator = list->head;\ while(iterator){\ listnode_##T *deletenode = iterator;\ iterator = iterator->next;\ free(deletenode);\ }\ free(list);\ } #define deleteLinkedList(T) deleteLinkList_##T #define DEFINELIST(T) ListNode(T)\ NewListNode(T)\ DeleteListNode(T)\ LinkedList(T)\ Insert(T)\ Remove(T)\ Merge(T)\ Clear(T)\ Isempty(T)\ NewLinkedList(T)\ DeleteLinkedList(T) DEFINELIST(int ) DEFINELIST(char ) DEFINELIST(float ) DEFINELIST(double ) int main () { linkedlist(int ) *list = newLinkedList(int ); linkedlist(int ) *list1 = newLinkedList(int ); listnode(int ) *node = newListNode(int )(1 ); listnode(int ) *node1 = newListNode(int )(2 ); list ->insert(list , 0 , node); list ->insert(list , 1 , node1); listnode(int ) *node2 = newListNode(int )(3 ); listnode(int ) *node3 = newListNode(int )(4 ); list1->insert(list1, 0 , node2); list1->insert(list1, 1 , node3); list ->merge(list , list1, 1 , 1 , 3 ); listnode(int ) *iterator = list ->head->next; while (iterator != list ->tail){ printf ("%d\n" , iterator->val); iterator = iterator->next; } list ->remove(list , 0 ); iterator = list ->head->next; while (iterator != list ->tail){ printf ("%d\n" , iterator->val); iterator = iterator->next; } deleteLinkedList(int )(list ); }
双向循环链表
链表中有两个指针(pre, next)，并且指向前一个节点和后一个节点。头节点的前指针(pre)指向尾节点，并且尾节点的后指针(next)指向头节点，形成循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 #include <stdio.h> #include <stdlib.h> #define ListNode(T) typedef struct ListNode_##T{\ struct ListNode_##T *pre;\ struct ListNode_##T *next;\ T val;\ }ListNode_##T; #define listnode(T) ListNode_##T #define NewListNode(T) ListNode_##T *newListNode_##T(T val){\ ListNode_##T *node = (ListNode_##T *) malloc(sizeof(ListNode_##T));\ node->next = NULL;\ node->pre = NULL;\ node->val = val;\ return node;\ } #define DeleteListNode(T) void deleteListNode_##T(ListNode_##T *node){\ free(node);\ } #define newListNode(T) newListNode_##T #define deleteListNode(T) deleteListNode_##T #define DoubleList(T) typedef struct doublelist_##T{\ ListNode_##T *head;\ ListNode_##T *tail;\ int length;\ void (*insert)(struct doublelist_##T *doublelist, int index, ListNode_##T *node);\ void (*remove)(struct doublelist_##T *doublelist, int index);\ void (*merge)(struct doublelist_##T *dst, struct doublelist_##T *src, int dstbegin, int srcbegin, int srcend);\ void (*clear)(struct doublelist_##T *list);\ void (*isempty)(struct doublelist_##T *list);\ }doublelist_##T; #define doublelist(T) doublelist_##T #define Insert(T) void insert_##T(doublelist_##T *doublelist, int index, ListNode_##T *node){\ ListNode_##T *iterator = doublelist->head;\ while(iterator != doublelist->tail && index--){\ iterator = iterator->next;\ }\ if (!index)\ printf("index has out of range and will insert front of tail\n" );\ node->next = iterator->next;\ node->pre = iterator;\ iterator->next->pre = node;\ iterator->next = node;\ doublelist->length++;\ } #define Remove(T) void remove_##T(doublelist_##T *doublelist, int index){\ ListNode_##T *iterator = doublelist->head;\ while(iterator != doublelist->tail && index--){\ iterator = iterator->next;\ }\ if (index >= 0){\ printf("index has out of range, can't remove any node\n" );\ return;\ }\ iterator->pre->next = iterator->next;\ iterator->next->pre = iterator->pre;\ iterator->pre = NULL;\ iterator->next = NULL;\ free(iterator);\ } #define Merge(T) void merge_##T(struct doublelist_##T *dst, struct doublelist_##T *src, int dstbegin, int srcbegin, int srcend){\ ListNode_##T *dstit = dst->head;\ ListNode_##T *srcit = src->head;\ while(dstit->next != dst->tail && dstbegin-- > 0) dstit = dstit->next;\ if (dstbegin > 0) printf("dstbegin has out of range, so merge begin at the tail\n" );\ ListNode_##T *copybegin;\ ListNode_##T *copyend;\ int copylength = 0;\ while(srcit->next != src->tail){\ srcit = srcit->next;\ srcbegin--;\ srcend--;\ if (srcend <= 0)break;\ if (srcbegin == 0){\ copybegin = newListNode(T)(srcit->val);\ copyend = copybegin;\ copylength++;\ }\ else if (srcbegin < 0){\ ListNode_##T *node = newListNode(T)(srcit->val);\ copyend->next = node;\ node->pre = copyend;\ copyend = copyend->next;\ copylength++;\ }\ }\ if (srcbegin > 0){\ printf("srcbegin has out of range, so stop merge\n" );\ return;\ }\ dstit->next->pre = copyend;\ copyend->next = dstit->next;\ copybegin->pre = dstit;\ dstit->next = copybegin;\ dst->length += copylength;\ } #define Clear(T) void clear_##T(doublelist_##T *list){\ while(list->head->next != list->tail){\ ListNode_##T *deletenode = list->head->next;\ list->head->next = list->head->next->next;\ free(deletenode);\ }\ list->tail->pre = list->head;\ } #define NewDoubleList(T) doublelist_##T *newDoubleList_##T(){\ doublelist_##T *doublelist = (doublelist_##T *) malloc(sizeof(doublelist_##T));\ doublelist->head = (ListNode_##T *) malloc(sizeof(ListNode_##T));\ doublelist->tail = (ListNode_##T *) malloc(sizeof(ListNode_##T));\ doublelist->head->next = doublelist->tail;\ doublelist->head->pre = doublelist->tail;\ doublelist->tail->next = doublelist->head;\ doublelist->tail->pre = doublelist->head;\ doublelist->length = 0;\ doublelist->insert = insert_##T;\ doublelist->remove = remove_##T;\ doublelist->clear = clear_##T;\ doublelist->merge = merge_##T;\ return doublelist;\ } #define DeleteDoubleList(T) void deleteDoubleList_##T(doublelist_##T *doublelist){\ ListNode_##T *iterator = doublelist->head;\ while(iterator){\ ListNode_##T *deleteNode = iterator;\ iterator = iterator->next;\ free(deleteNode);\ }\ free(doublelist);\ } #define newDoubleList(T) newDoubleList_##T #define deleteDoubleList(T) deleteDoubleList_##T #define DEFINEDOUBLELIST(T) ListNode(T)\ NewListNode(T)\ DeleteListNode(T)\ DoubleList(T)\ Insert(T)\ Remove(T)\ Clear(T)\ Merge(T)\ NewDoubleList(T)\ DeleteDoubleList(T) DEFINEDOUBLELIST(int ) DEFINEDOUBLELIST(char ) DEFINEDOUBLELIST(float ) DEFINEDOUBLELIST(double ) int main () { doublelist(int ) *list = newDoubleList(int )(); doublelist(int ) *list1 = newDoubleList(int )(); listnode(int ) *node = newListNode(int )(10 ); listnode(int ) *node1 = newListNode(int )(1 ); list ->insert(list , 0 , node); list ->insert(list , 1 , node1); listnode(int ) *node2 = newListNode(int )(3 ); listnode(int ) *node3 = newListNode(int )(4 ); list1->insert(list1, 0 , node2); list1->insert(list1, 1 , node3); list ->merge(list , list1, 1 , 1 , 3 ); listnode(int ) *iterator = list ->head; while (iterator->next != list ->tail){ iterator = iterator->next; printf ("%d\n" , iterator->val); } list ->remove(list , 1 ); iterator = list ->head; while (iterator->next != list ->tail){ iterator = iterator->next; printf ("%d\n" , iterator->val); } free (list ); }
跳表
是一种随机化的数据结构，实质上就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能
这种随机的数据结构，可以看做是一个二叉树的变种，它在性能上与红黑树、AVL树很相近；但是Skip List(跳跃列表)的实现相比前两者要简单很多
从功能角度来看，跳跃表就像在链表之上架起了查询的“高速公路”，可以在普通链表上快速的查找到所要的元素。在查找元素时，跳表能够提供 O(log n) 的时间复杂度
对于一个链表来说，需要查找某个元素必须从头向后扫描，直到找到该元素或者扫描到完整的链表。
但是对于一个有序链表，可以提取出来其中的某些节点作为索引值，可以更快的找到所需要的元素，如上图
要想实现比较快的查找，可以通过构建索引，使得每一个 K 级节点都有 K + 1 个指针，分别跳过 $2^K-1,2^{K-1}-1,…,2^0-1$ 个节点，这样就可以实现较快查找。
但是这个构建是静态的，并不能保证动态（插入或者删除节点）稳定性。所以可以首先确定一个实数 p，使得 $0<p<1$ 并且要求在跳表中具有 K 级指针的节点所占的比例为 $\frac{100}{2^{K+1}}$ 。这样每当插入新的节点时，那这个节点就有 50% 概率为 0 级节点，有…这就维持了跳跃表的平衡。
上述实现时，可以利用随机数 0~1，如果是 1 就加一个等级，一直到出现 0 为止。然后将节点插入到链表中
数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <stdio.h> #include <stdlib.h> #define Array(T) typedef struct array_##T{\ T *val;\ }array_##T; #define array(T) array_##T #define NewArray(T) array_##T *newArray_##T(int size){\ array(T) *array = (array_##T *)malloc(sizeof(array_##T));\ array->val = (T *)malloc(sizeof(T) * size);\ return array;\ } #define newArray(T) newArray_##T #define DeleteArray(T) void deleteArray_##T(array_##T *array){\ free(array->val);\ free(array);\ } #define deleteArray(T) deleteArray_##T #define DEFINEARRAY(T) Array(T)\ NewArray(T)\ DeleteArray(T) DEFINEARRAY(int ) DEFINEARRAY(char ) DEFINEARRAY(float ) DEFINEARRAY(double ) int main () { array (int ) *a = newArray(int )(10 ); *(a->val) = 1 ; *(a->val + 1 ) = 2 ; *(a->val + 2 ) = 3 ; *(a->val + 3 ) = 4 ; a->val[4 ] = 5 ; printf ("%d\n" , *(a->val)); printf ("%d\n" , *(a->val + 1 )); printf ("%d\n" , *(a->val + 2 )); printf ("%d\n" , *(a->val + 3 )); printf ("%d\n" , a->val[4 ]); deleteArray(int )(a); }
队列 先进先出
循环队列 固定长度的循环队列，在一般项目中比较常用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define Queue(T) typedef struct queue_##T{\ T *val;\ int head;\ int tail;\ int size;\ int (*maxsize)(struct queue_##T* queue);\ int (*getsize)(struct queue_##T* queue);\ int (*isempty)(struct queue_##T* queue);\ int (*isfull)(struct queue_##T* queue);\ void (*push)(struct queue_##T* queue, T val);\ void (*pop)(struct queue_##T* queue);\ T (*top)(struct queue_##T* queue);\ void (*clear)(struct queue_##T *queue);\ }queue_##T; #define queue(T) queue_##T #define Maxsize(T) int maxsize_##T(queue_##T *queue){return queue->size;} #define Getsize(T) int getsize_##T(queue_##T *queue){\ int size = queue->tail - queue->head;\ while(size < 0)size += queue-> size;\ while(size > queue->size)size -= queue->size;\ return size;\ } #define Isempty(T) int isempty_##T(queue_##T *queue){\ return queue->head == queue->tail;\ } #define Isfull(T) int isfull_##T(queue_##T *queue){\ return queue->tail == (queue->head - 1 >= 0? queue->head - 1 : queue->head - 1 + queue->size);\ } #define Push(T) void push_##T(queue_##T *queue, T val){\ if (queue->tail == (queue->head - 1 >= 0? queue->head - 1 : queue->head - 1 + queue->size))return;\ queue->val[queue->tail] = val;\ queue->tail += 1;\ queue->tail %= queue->size;\ } #define Pop(T) void pop_##T(queue_##T *queue){\ if (queue->head == queue->tail){\ printf("this queue is empty" );\ return;\ }\ queue->head++;\ queue->head %= queue->size;\ } #define Top(T) T top_##T(queue_##T *queue){\ if (queue->head == queue->tail){\ printf("this queue is empty" );\ return (T)0;\ }\ return queue->val[queue->head];\ } #define Clear(T) void clear_##T(queue_##T *queue){\ queue->head = 0;\ queue->tail = 0;\ } #define NewQueue(T) queue_##T *newqueue_##T(int size){\ queue_##T *queue = (queue_##T *) malloc(sizeof(queue_##T));\ queue->val = (T *) malloc(sizeof(T) * size);\ queue->size = size;\ queue->head = 0;\ queue->tail = 0;\ queue->maxsize = maxsize_##T;\ queue->getsize = getsize_##T;\ queue->isempty = isempty_##T;\ queue->isfull = isfull_##T;\ queue->push = push_##T;\ queue->pop = pop_##T;\ queue->top = top_##T;\ queue->clear = clear_##T;\ return queue;\ } #define newqueue(T) newqueue_##T #define DeleteQueue(T) void deletequeue_##T(queue_##T* queue){\ free(queue->val);\ free(queue);\ } #define deletequeue(T) deletequeue_##T #define DEFINEQUEUE(T) Queue(T)\ Maxsize(T)\ Getsize(T)\ Isempty(T)\ Isfull(T)\ Push(T)\ Pop(T)\ Top(T)\ Clear(T)\ NewQueue(T)\ DeleteQueue(T) DEFINEQUEUE(int ) DEFINEQUEUE(char ) DEFINEQUEUE(float ) DEFINEQUEUE(double ) int main () { queue (int ) *queue = newqueue(int )(10 ); queue ->push(queue , 1 ); queue ->push(queue , 2 ); queue ->push(queue , 3 ); queue ->push(queue , 4 ); while (!queue ->isempty(queue )){ printf ("%d\n" , queue ->top(queue )); queue ->pop(queue ); } deletequeue(int )(queue ); }
可扩充的双向循环队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 #include <stdio.h> #include <stdlib.h> #include <string.h> #define Queue(T) typedef struct queue_##T{\ void* start;\ void* end;\ T* ptr;\ int size;\ void (*push)(struct queue_##T *queue, T val);\ void (*pop)(struct queue_##T *queue);\ T (*top)(struct queue_##T* queue);\ }queue_##T; #define queue(T) queue_##T #define Push(T) void push_##T(queue_##T *queue, T val){\ if (queue->ptr == queue->end){\ T *newstart = (T *) malloc(2 * queue->size);\ memcpy(newstart, queue->start, queue->size);\ free(queue->start);\ queue->start = newstart;\ queue->end = queue->start + queue->size * 2;\ queue->ptr = queue->start + queue->size;\ queue->size = 2 * queue->size;\ }\ memmove(queue->ptr, &val, sizeof(T));\ queue->ptr += 1;\ } #define Pop(T) void pop_##T(queue_##T *queue){\ if ((void *)queue->ptr == queue->start)return;\ memmove(queue->start, queue->start + sizeof(T), queue->end - queue ->start - sizeof(T));\ queue->ptr -=1;\ } #define Top(T) T top_##T(queue_##T *queue){\ T data;\ if ((void *)queue->ptr - queue->start < sizeof(T))return 0;\ memmove(&data, queue->start, sizeof(T));\ return data;\ } #define NewQueue(T) queue_##T *newqueue_##T(){\ queue_##T *queue = (queue_##T *) malloc(sizeof(queue_##T));\ queue->start = malloc(sizeof(T) * 32);\ queue->size = 32 * sizeof(T);\ queue->end = queue->start + queue->size;\ queue->ptr = queue->start;\ queue->push = push_##T;\ queue->pop = pop_##T;\ queue->top = top_##T;\ return queue;\ } #define newqueue(T) newqueue_##T #define DeleteQueue(T) void deletequeue_##T(queue_##T* queue){\ free(queue->start);\ free(queue);\ } #define deletequeue(T) deletequeue_##T #define DEFINEQUEUE(T) Queue(T)\ Push(T)\ Pop(T)\ Top(T)\ NewQueue(T)\ DeleteQueue(T) DEFINEQUEUE(int ) DEFINEQUEUE(char ) DEFINEQUEUE(float ) DEFINEQUEUE(double ) int main () { queue (int ) *queue = newqueue(int )(); int i = 33 ; while (i--) queue ->push(queue , i); i = 33 ; while (i--){ printf ("%d\n" , queue ->top(queue )); queue ->pop(queue ); } deletequeue(int )(queue ); }
优先可扩充队列 根据特定的算法来实现排序，并且在每次插入元素时进行二分查找，找到合适的位置存入数据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 #include <stdio.h> #include <string.h> #include <stdlib.h> #define DefaultCompare(T) int compare_##T(const T a, const T b){\ if (a < b) return 1;\ if (a == b) return 0;\ return -1;\ } DefaultCompare(int ) DefaultCompare(char ) DefaultCompare(float ) DefaultCompare(double ) #define defaultcompare(T) compare_##T #define PriorityQueue(T) typedef struct priority_queue_##T{\ void *start;\ void *end;\ T *ptr;\ int (*compare)(const T a, const T b);\ void (*push)(struct priority_queue_##T *queue, const T val);\ void (*pop)(struct priority_queue_##T *queue);\ T (*top)(struct priority_queue_##T *queue);\ T (*getval)(struct priority_queue_##T *queue, int index);\ int (*find)(struct priority_queue_##T *queue, const T val);\ int (*size)(struct priority_queue_##T *queue);\ int (*maxsize)(struct priority_queue_##T *queue);\ int (*isempty)(struct priority_queue_##T *queue);\ void (*clear)(struct priority_queue_##T *queue);\ void (*merge)(struct priority_queue_##T *dst, struct priority_queue_##T *src, int srcbegin, int srcend);\ }priority_queue_##T; #define priorityqueue(T) priority_queue_##T #define Push(T) void push_##T(priority_queue_##T *queue, const T val){\ int size = queue->ptr - (T *) queue->start;\ if (queue->ptr == queue->end){\ void *newstart = malloc(sizeof(T) * size * 2);\ memcpy(newstart, queue->start, size * sizeof(T));\ queue->start = newstart;\ queue->end = newstart + size * 2 * sizeof(T);\ queue->ptr = newstart + size * sizeof(T);\ }\ int left = 0, right = size;\ while(right > left){\ int mid = (right + left) >> 1;\ T *it = (T *) queue->start + mid;\ if (queue->compare(*it, val) > 0) right = mid - 1;\ else if (queue->compare(*it, val) < 0) left = mid + 1;\ else {\ left = mid;\ break;\ }\ }\ memmove(queue->start + (left + 1) * sizeof(T), queue->start + (left + 0) * sizeof(T), (size - left) * sizeof(T));\ *((T *) queue->start + left + 0) = val;\ queue->ptr += 1;\ } #define Pop(T) void pop_##T(priority_queue_##T *queue){\ if (queue->start == (void *) queue->ptr){\ printf("this queue has been empty\n" );\ return;\ }\ memcpy(queue->start, queue->start + sizeof(T), (queue->end - queue->start - 1));\ queue->ptr -= 1;\ } #define Top(T) T top_##T(priority_queue_##T *queue){\ if (queue->start == (void *) queue->ptr){\ printf("this queue has been empty\n" );\ return (T) 0;\ }\ T val = *((T *) queue->start);\ return val;\ } #define Size(T) int size_##T(priority_queue_##T *queue){\ return queue->ptr - (T *) queue->start;\ } #define Maxsize(T) int maxsize_##T(priority_queue_##T *queue){\ return (T *) queue->end - (T *) queue->start;\ } #define Isempty(T) int isempty_##T(priority_queue_##T *queue){\ return queue->start == (void *) queue->ptr;\ } #define Clear(T) void clear_##T(priority_queue_##T *queue){\ queue->ptr = queue->start;\ } #define Find(T) int find_##T(priority_queue_##T *queue, const T val){\ int size = queue->ptr - (T *) queue->start;\ int left = 0, right = size - 1;\ while(right > left){\ int mid = (left + right) >> 1;\ T *it = (T *) queue->start + mid;\ if (queue->compare(*it, val) > 0) right = mid - 1;\ else if (queue->compare(*it, val) < 0) left = mid + 1;\ else return mid;\ }\ return -1;\ } #define GetVal(T) T getval_##T(priority_queue_##T *queue, int index){\ if (index * sizeof(T) + queue->start > (void *) queue->ptr){\ printf("index has out of range\n" );\ return (T) 0;\ }\ return *((T *) queue->start + index);\ } #define Merge(T) void merge_##T(priority_queue_##T *dst, priority_queue_##T *src, int srcbegin, int srcend){\ int srcsize = src->ptr - (T *) src->start;\ if (srcsize < srcbegin){\ printf("srcbegin has out of index, stop merge\n" );\ return;\ }\ for(int i = srcbegin; i < srcend && i < srcsize; i++){\ dst->push(dst, *((T *) src->start + i));\ }\ } #define NewPriorityQueue(T) priority_queue_##T *newpriorityqueue_##T(int (*compare)(const T a, const T b)){\ priority_queue_##T *queue = (priority_queue_##T *) malloc(sizeof(priority_queue_##T));\ queue->start = malloc(32 * sizeof(T));\ queue->end = queue->start + 32 * sizeof(T);\ queue->ptr = queue->start;\ queue->compare = compare;\ queue->push = push_##T;\ queue->pop = pop_##T;\ queue->top = top_##T;\ queue->size = size_##T;\ queue->maxsize = maxsize_##T;\ queue->isempty = isempty_##T;\ queue->clear = clear_##T;\ queue->find = find_##T;\ queue->getval = getval_##T;\ queue->merge = merge_##T;\ } #define DeletePriorityQueue(T) void deletepriorityqueue_##T(priority_queue_##T *queue){\ free(queue->start);\ free(queue);\ } #define newpriorityqueue(T) newpriorityqueue_##T #define deletepriorityqueue(T) deletepriorityqueue_##T #define DEFINEPRIORITYQUEUE(T) PriorityQueue(T)\ Push(T)\ Pop(T)\ Top(T)\ Size(T)\ Maxsize(T)\ Isempty(T)\ Clear(T)\ Find(T)\ GetVal(T)\ Merge(T)\ NewPriorityQueue(T)\ DeletePriorityQueue(T) DEFINEPRIORITYQUEUE(int ) DEFINEPRIORITYQUEUE(char ) DEFINEPRIORITYQUEUE(float ) DEFINEPRIORITYQUEUE(double ) int main () { priorityqueue(int ) *queue = newpriorityqueue(int ) (defaultcompare(int )); queue ->push(queue , 10 ); queue ->push(queue , 11 ); queue ->push(queue , 15 ); queue ->push(queue , 9 ); printf ("%d\n" , queue ->find(queue , 2 )); printf ("%d\n" , queue ->find(queue , 10 )); printf ("%d\n" , queue ->size(queue )); printf ("%d\n" , queue ->getval(queue , 1 )); for (int i = 0 ; i < 4 ; i++){ printf ("%d\n" , queue ->top(queue )); queue ->pop(queue ); } deletepriorityqueue(int ) (queue ); }
向量 有点类似于队列，但是在 C++ 中 vector 有个特点就是每次内存不足时会申请原来的内存的两倍的内存，然后将数据存入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 #include <stdio.h> #include <stdlib.h> #include <string.h> #define Vector(T) typedef struct vector_##T{\ void *start;\ void *end;\ T *ptr;\ int (*size)(struct vector_##T *vector);\ int (*max_size)(struct vector_##T *vector);\ int (*isempty)(struct vector_##T *vector);\ void (*push_back)(struct vector_##T *vector, T val);\ void (*pop_back)(struct vector_##T *vector);\ void (*remove)(struct vector_##T *vec, int begin, int end);\ int (*find)(struct vector_##T *vec, T val);\ T (*back)(struct vector_##T *vector);\ T (*front)(struct vector_##T *vector);\ void (*copyfrom)(struct vector_##T *dst, struct vector_##T *src, int srcbegin, int srcend);\ void (*merge)(struct vector_##T *dst, struct vector_##T *src, int dstbegin, int srcbegin, int srcend);\ void (*clear)(struct vector_##T *vec);\ }vector_##T; #define vector(T) vector_##T #define Size(T) int size_##T(vector_##T *vector){\ return vector->ptr - (T *)vector->start;\ } #define Max_size(T) int max_size_##T(vector_##T *vector){\ return (T *) vector->end - (T *) vector->start;\ } #define Isempty(T) int isempty_##T(vector_##T *vector){\ return (void *) vector->ptr == vector->start;\ } #define Push_back(T) void push_back_##T(vector_##T *vector, T val){\ if (vector->end - (void *)vector->ptr < sizeof(T)){\ int size = vector->end - vector->start;\ void *newstart = malloc(size * 2);\ memcpy(newstart, vector->start, size);\ free(vector->start);\ vector->start = newstart;\ vector->end = vector->start + size * 2;\ vector->ptr = vector->start + size;\ }\ memcpy(vector->ptr, &val, sizeof(T));\ vector->ptr += 1;\ } #define Pop_back(T) void pop_back_##T(vector_##T *vector){\ if (vector->ptr != vector->start)\ vector->ptr -= 1;\ else \ printf("this vector has been empty\n" );\ } #define Back(T) T back_##T(vector_##T *vector){\ if (vector->ptr == vector->start){\ printf("this vector is empty\n" );\ return (T)0;\ }\ T val;\ memcpy(&val, vector->ptr - 1, sizeof(T));\ return val;\ } #define Front(T) T front_##T(vector_##T *vector){\ if (vector->ptr == vector->start){\ printf("this vector is empty\n" );\ return (T)0;\ }\ T val;\ memcpy(&val, vector->start, sizeof(T));\ return val;\ } #define Remove(T) void remove_##T(vector_##T *vec, int begin, int end){\ T *pbegin = vec->start + begin;\ T *pend = vec->start + end;\ memcpy((void *)pbegin, (void *)pend, ((void *) vec->ptr - (void *) pend));\ vec->ptr = pbegin + (vec->ptr - pend);\ } #define Find(T) int find_##T(vector_##T *vec, T val){\ T *iterator = vec->start;\ int index = 0;\ while(iterator != vec->ptr){\ if (*iterator == val)return index;\ iterator++;\ index++;\ }\ return -1;\ } #define Copyfrom(T) void copyfrom_##T(vector_##T *dst, vector_##T *src, int srcbegin, int srcend){\ int srcsize = (void *) src->ptr - src->start;\ if (srcbegin * sizeof(T) > srcsize){\ printf("begin index has out of range" );\ return;\ }\ if (srcend * sizeof(T) > srcsize){\ printf("end index has out of range" );\ return;\ }\ int dstmaxsize = dst->end - dst->start;\ int copysize = sizeof(T) * (srcend - srcbegin);\ if (dstmaxsize < copysize){\ while(dstmaxsize < copysize)\ dstmaxsize << 2;\ void *newstart = malloc(dstmaxsize);\ dst->start = newstart;\ }\ memcpy(dst->start, src->start + sizeof(T) * srcbegin, copysize);\ dst->ptr = (T *) dst->start + srcend - srcbegin;\ } #define Merge(T) void merge_##T(struct vector_##T *dst, struct vector_##T *src, int dstbegin, int srcbegin, int srcend){\ int srcsize = (void *) src->ptr - src->start;\ if (srcbegin * sizeof(T) > srcsize){\ printf("begin index has out of range" );\ return;\ }\ if (srcend * sizeof(T) > srcsize){\ printf("end index has out of range" );\ return;\ }\ int dstmaxsize = dst->end - dst->start;\ int dstsize = (void *) dst->ptr - dst->start;\ while(dstmaxsize < dstsize + (srcend - srcbegin) * sizeof(T))\ dstmaxsize << 2;\ void *newstart = malloc(dstmaxsize);\ memcpy(newstart, dst->start, dstbegin * sizeof(T));\ memcpy(newstart + dstbegin * sizeof(T), src->start + srcbegin * sizeof(T), (srcend - srcbegin) * sizeof(T));\ memcpy(newstart + dstbegin * sizeof(T) + srcsize, dst->start + dstbegin * sizeof(T), (void *) dst->ptr - dst->start - dstbegin * sizeof(T));\ free(dst->start);\ dst->start = newstart;\ dst->end = newstart + dstmaxsize;\ dst->ptr = newstart + dstsize + (srcend - srcbegin) * sizeof(T);\ } #define Clear(T) void clear_##T(vector_##T *vec){\ vec->ptr = vec->start;\ } #define NewVector(T) vector_##T *newvector_##T(){\ vector_##T *vector = malloc(sizeof(vector_##T));\ vector->start = malloc(sizeof(T) * 32);\ vector->end = vector->start + sizeof(T) * 32;\ vector->ptr = vector->start;\ vector->size = size_##T;\ vector->max_size = max_size_##T;\ vector->push_back = push_back_##T;\ vector->pop_back = pop_back_##T;\ vector->front = front_##T;\ vector->back = back_##T;\ vector->find = find_##T;\ vector->remove = remove_##T;\ vector->copyfrom = copyfrom_##T;\ vector->merge = merge_##T;\ vector->clear = clear_##T;\ return vector;\ } #define DeleteVector(T) void deletevector_##T(vector_##T *vector){\ free(vector->start);\ free(vector);\ } #define newvector(T) newvector_##T #define deletevector(T) deletevector_##T #define DEFINEVECTOR(T) Vector(T)\ Size(T)\ Max_size(T)\ Push_back(T)\ Pop_back(T)\ Back(T)\ Front(T)\ Remove(T)\ Find(T)\ Copyfrom(T)\ Merge(T)\ Clear(T)\ NewVector(T)\ DeleteVector(T) DEFINEVECTOR(int ) DEFINEVECTOR(char ) DEFINEVECTOR(float ) DEFINEVECTOR(double ) int main () { vector (int ) *v = newvector(int )(); vector (int ) *v2 =newvector(int )(); int i = 33 ; while (i--){ v->push_back(v, i); } i = 33 ; v2->copyfrom(v2, v, 0 , 10 ); v2->merge(v2, v, 5 , 1 , 10 ); while (i--){ printf ("%d\n" , v->back(v)); printf ("%d\n" , v2->back(v2)); v->pop_back(v); v2->pop_back(v2); } v->pop_back(v); deletevector(int )(v); deletevector(int )(v2); }
栈
栈和堆是计算机中比较常用的数据结构，在计算机中，会有栈内存和堆内存，堆是向高地址扩展 也就是常说的向上生长。是不连续的内存区域。栈是向低地址扩展 也就是常说的向下生长。 是连续的内存区域。而且栈是系统分配的内存，速度较快，会自动回收，但是堆是程序员分配的内存，不会自动回收，但是程序结束之后会被回收。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 #include <stdio.h> #include <stdlib.h> #include <string.h> #define Stack(T) typedef struct stack_##T{\ void *start;\ void *end;\ T *ptr;\ void (*push)(struct stack_##T *stack, T val);\ void (*pop)(struct stack_##T *stack);\ T (*top)(struct stack_##T *stack);\ int (*isfull)(struct stack_##T *stack);\ int (*isempty)(struct stack_##T *stack);\ int (*size)(struct stack_##T *stack);\ int (*maxsize)(struct stack_##T *stack);\ }stack_##T; #define stack(T) stack_##T #define Push(T) void push_##T(stack_##T *stack, T val){\ if (stack->end - (void *)stack->ptr < sizeof(T)){\ printf("this stack has been full\n" );\ return;\ }\ memcpy((void *)(stack->ptr), &val, sizeof(T));\ stack->ptr += 1;\ } #define Pop(T) void pop_##T(stack_##T *stack){\ if ((void *)stack->ptr - stack->start < sizeof(T)){\ printf("this stack has been empty\n" );\ return;\ }\ stack->ptr -= 1;\ } #define Top(T) T top_##T(stack_##T *stack){\ if (stack->start == (void *)stack->ptr)return (T)0;\ T data;\ memcpy(&data, stack->ptr - 1, sizeof(T));\ return data;\ } #define Isfull(T) int isfull_##T(stack_##T *stack){\ return (void *)stack->ptr == stack->end;\ } #define Isempty(T) int isempty_##T(stack_##T *stack){\ return (void *)stack->ptr == stack->start;\ } #define Size(T) int size_##T(stack_##T *stack){\ return stack->ptr - (T *) stack->start;\ } #define Maxsize(T) int maxsize_##T(stack_##T *stack){\ return (T *) stack->end - (T *) stack->start;\ } #define NewStack(T) stack_##T *newStack_##T(int size){\ stack_##T *stack = (stack_##T *) malloc(sizeof(stack_##T));\ stack->start = malloc(sizeof(T) * size);\ stack->end = stack->start + sizeof(T) * size;\ stack->ptr = stack->start;\ stack->push = push_##T;\ stack->pop = pop_##T;\ stack->top = top_##T;\ stack->isfull = isfull_##T;\ stack->isempty = isempty_##T;\ stack->size = size_##T;\ stack->maxsize = maxsize_##T;\ return stack;\ } #define newStack(T) newStack_##T #define DeleteStack(T) void deleteStack_##T(stack_##T *stack){\ stack->ptr = NULL;\ stack->end = NULL;\ free(stack->start);\ free(stack);\ } #define deleteStack(T) deleteStack_##T #define DEFINESTACK(T) Stack(T)\ Push(T)\ Pop(T)\ Top(T)\ Isfull(T)\ Isempty(T)\ Size(T);\ Maxsize(T)\ NewStack(T)\ DeleteStack(T) DEFINESTACK(int ) DEFINESTACK(char ) DEFINESTACK(float ) DEFINESTACK(double ) int main () { stack (int ) *stack = newStack(int )(10 ); int i = 13 ; while (i--){ stack ->push(stack , i); } i = 13 ; while (i--){ int a = (stack ->top(stack )); printf ("%d\n" , a); stack ->pop(stack ); } }
树 二叉树 每个树的节点有两个子结点 right_leaf, left_leaf ，从而树的结构表现为两个叉
平衡二叉树 是一种特殊的二叉树，但是左右两侧的树的高度之差不超过1，而且在二叉树中的查找速度相当于是 。但是需要特定的算法来保持树的平衡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #define max(x, y) (x) > (y)? (x) : (y) #define treenode(T) struct treenode_##T #define Queue(T) typedef struct queuetreenode_##T{\ void *start;\ void *end;\ struct treenode_##T **ptr;\ int size;\ void (*push)(struct queuetreenode_##T *queue, treenode_##T *val);\ void (*pop)(struct queuetreenode_##T *queue);\ treenode_##T *(*top)(struct queuetreenode_##T *queue);\ }queuetreenode_##T; #define queue(T) queuetreenode_##T #define Push(T) void pushtreenode_##T(queuetreenode_##T *queue, struct treenode_##T *val){\ if ((void *) queue->ptr == queue->end){\ int size = queue->end - queue->start;\ void *newstart = malloc(2 * size);\ memcpy(newstart, queue->start, size);\ free(queue->start);\ queue->start = newstart;\ queue->end = queue->start + 2 * size;\ queue->ptr = queue->start + size;\ }\ memcpy(queue->ptr, &val, sizeof(struct treenode_##T *));\ queue->ptr += 1;\ queue->size++;\ } #define Pop(T) void poptreenode_##T(queuetreenode_##T *queue){\ if ((void *) queue->ptr == queue->start) return;\ memmove(queue->start, queue->start + sizeof(treenode_##T *), queue->end - queue->start - sizeof(treenode_##T *));\ queue->ptr -= 1;\ queue->size--;\ } #define Top(T) treenode_##T *toptreenode_##T(queuetreenode_##T *queue){\ treenode_##T *treenode = *((treenode_##T **) queue->start);\ return treenode;\ } #define NewQueue(T) queuetreenode_##T *newqueuetreenode_##T(int size){\ queuetreenode_##T *queue = (queuetreenode_##T *) malloc(sizeof(queuetreenode_##T));\ queue->start = malloc(sizeof(treenode_##T *) * size);\ queue->end = queue->start + sizeof(treenode_##T *) * size;\ queue->ptr = queue->start;\ queue->push = pushtreenode_##T;\ queue->pop = poptreenode_##T;\ queue->top = toptreenode_##T;\ } #define newqueue(T) newqueuetreenode_##T #define DeleteQueue(T) void deletequeuetreenode_##T(queuetreenode_##T *queue){\ free(queue->start);\ free(queue);\ } #define deletequeue(T) deletequeuetreenode_##T #define TreeNode(T) typedef struct treenode_##T{\ T val;\ struct treenode_##T *parent;\ struct treenode_##T *left;\ struct treenode_##T *right;\ int height;\ void (*nodeDFS)(treenode_##T *this, void (*func)(T val));\ void (*nodeBFS)(treenode_##T *this, void (*func)(T val));\ void (*insertl)(struct treenode_##T *this, struct treenode_##T *node);\ void (*insertr)(struct treenode_##T *this, struct treenode_##T *node);\ int (*isleaf)(struct treenode_##T *this);\ int (*isroot)(struct treenode_##T *this);\ }treenode_##T; #define NodeDFS(T) void nodeDFS_##T(treenode_##T *this, void (*func)(T val)){\ if (!this)return;\ func(this->val);\ nodeDFS_##T(this->left, func);\ nodeDFS_##T(this->right, func);\ } #define NodeBFS(T) void nodeBFS_##T(treenode_##T *this, void (*func)(T val)){\ queue(T) *nodequeue = newqueue(T)(32);\ nodequeue->push(nodequeue, this);\ while(nodequeue->size){\ treenode_##T *node = nodequeue->top(nodequeue);\ nodequeue->pop(nodequeue);\ if (!node)continue;\ func(node->val);\ nodequeue->push(nodequeue, node->left);\ nodequeue->push(nodequeue, node->right);\ }\ } #define InsertL(T) void insertl_##T(treenode_##T *this, treenode_##T *node){\ this->left = node;\ this->height = (1 + node->height > this->height? 1 + node->height : this->height);\ node->parent = this;\ } #define InsertR(T) void insertr_##T(treenode_##T *this, treenode_##T *node){\ this->right = node;\ this->height = (1 + node->height > this->height? 1 + node->height : this->height);\ node->parent = this;\ } #define Isleaf(T) int isleaf_##T(treenode_##T *this){\ return !this->right && !this->left;\ } #define Isroot(T) int isroot_##T(treenode_##T *this){\ return !this->parent;\ } #define NewTreeNode(T) treenode_##T *newtreenode_##T(T val){\ treenode_##T *node = (treenode_##T *) malloc(sizeof(treenode_##T));\ node->val = val;\ node->left = NULL;\ node->right = NULL;\ node->parent = NULL;\ node->height = 0;\ node->nodeDFS = nodeDFS_##T;\ node->nodeBFS = nodeBFS_##T;\ node->insertl = insertl_##T;\ node->insertr = insertr_##T;\ node->isleaf = isleaf_##T;\ node->isroot = isroot_##T;\ return node;\ } #define DeleteTreeNode(T) void deletetreenode_##T(treenode_##T *node){\ if (!node)return;\ deletetreenode_##T(node->left);\ deletetreenode_##T(node->right);\ free(node);\ } #define newtreenode newtreenode_##T #define deletetreenode(T) deletetreenode_##T #define Tree(T) typedef struct tree_##T{\ treenode_##T *root;\ int size;\ int (*compare)(const T a, const T b);\ int (*isempty)(struct tree_##T *this);\ treenode_##T *(*getroot)(struct tree_##T *tree);\ void (*insert)(struct tree_##T *this, T val);\ int (*heightBFS)(treenode_##T *node);\ void (*updateheight)(struct tree_##T *this);\ void (*balanceBFS)(queue(T) *queue, treenode_##T *node);\ void (*linkBFS)(queue(T) *queue, treenode_##T *node, int left, int right, int mid);\ void (*balance)(struct tree_##T *this);\ }tree_##T; #define tree(T) tree_##T #define Isempty(T) int isempty_##T(tree_##T *this){\ return this->size == 0;\ } #define Getroot(T) treenode_##T *getroot_##T(tree_##T *this){\ return this->root;\ } #define HeightBFS(T) int heightBFS_##T(treenode_##T *node){\ if (node == NULL) return 0;\ int heightleft = heightBFS_##T(node->left);\ int heightright = heightBFS_##T(node->right);\ node->height = max(heightleft, heightright) + 1;\ return node->height;\ } #define Updateheight(T) void updateheight_##T(tree_##T *this){\ this->heightBFS(this->root);\ } #define Insert(T) void insert_##T(tree_##T *this, T val){\ treenode_##T *node = newtreenode_##T(val);\ if (!this->root){\ this->root = node;\ this->size++;\ return;\ }\ treenode_##T *iterator = this->root;\ while(iterator){\ if (iterator->val == val){\ printf("this tree has a same val, so can't insert\n" );\ return;\ }\ if (val < iterator-> val){\ if (!iterator->left){\ iterator->left = node;\ break;\ }\ iterator = iterator->left;\ }\ if (val > iterator->val){\ if (!iterator->right){\ iterator->right = node;\ break;\ }\ iterator = iterator->right;\ }\ }\ this->balance(this);\ this->updateheight(this);\ this->size++;\ } #define BalanceBFS(T) void balanceBFS_##T(queue(T) *queue, treenode_##T *node){\ if (!node)return;\ balanceBFS_##T(queue, node->left);\ queue->push(queue, node);\ balanceBFS_##T(queue, node->right);\ node->parent = NULL;\ node->left = NULL;\ node->right = NULL;\ } #define LinkBFS(T) void linkBFS_##T(queue(T) *queue, treenode_##T *node, int left, int right, int mid){\ if (left >= right) return;\ if (left == mid - 1){\ node->left = *((treenode_##T **) queue->start + left);\ node->left->parent = node;\ }\ else if (left < mid - 1){\ int leftmid = (left + mid) >> 1;\ node->left = *((treenode_##T **) queue->start + leftmid);\ node->left->parent = node;\ linkBFS_##T(queue, node->left, left, mid - 1, leftmid);\ }\ if (right == mid + 1){\ node->right = *((treenode_##T **) queue->start + right);\ node->right->parent = node;\ }\ else if (right > mid + 1){\ int rightmid = (right + mid) >> 1;\ node->right = *((treenode_##T **) queue->start + rightmid);\ node->right->parent = node;\ linkBFS_##T(queue, node->right, mid + 1, right, rightmid);\ }\ } #define Balance(T) void balance_##T(tree_##T *this){\ queue(T) *queue = newqueue(T)(this->root->height * 2);\ this->balanceBFS(queue, this->root);\ int size = queue->size - 1;\ int mid = size >> 1;\ this->root = *((treenode_##T **) queue->start + mid);\ this->linkBFS(queue, this->root, 0, size, mid);\ deletequeue(T) (queue);\ } #define NewTree(T) tree_##T *newtree_##T(){\ tree_##T *tree = (tree_##T *) malloc(sizeof(tree_##T));\ tree->root = NULL;\ tree->size = 0;\ tree->isempty = isempty_##T;\ tree->getroot = getroot_##T;\ tree->insert = insert_##T;\ tree->heightBFS = heightBFS_##T;\ tree->updateheight = updateheight_##T;\ tree->balanceBFS = balanceBFS_##T;\ tree->linkBFS = linkBFS_##T;\ tree->balance = balance_##T;\ return tree;\ } #define DeleteTree(T) void deletetree_##T(tree_##T *tree){\ deletetreenode_##T(tree->root);\ free(tree);\ } #define newtree(T) newtree_##T #define deletetree(T) deletetree_##T #define DEFINETREE(T) TreeNode(T)\ Queue(T)\ Push(T)\ Pop(T)\ Top(T)\ NewQueue(T)\ DeleteQueue(T)\ NodeDFS(T)\ NodeBFS(T)\ InsertL(T)\ InsertR(T)\ Isleaf(T)\ Isroot(T)\ NewTreeNode(T)\ DeleteTreeNode(T)\ Tree(T)\ Isempty(T)\ Getroot(T)\ HeightBFS(T)\ Updateheight(T)\ Insert(T)\ BalanceBFS(T)\ LinkBFS(T)\ Balance(T)\ NewTree(T)\ DeleteTree(T) DEFINETREE(int ) DEFINETREE(char ) DEFINETREE(float ) DEFINETREE(double ) int main () { tree(int ) *tree = newtree(int )(); tree->insert(tree, 1 ); tree->insert(tree, 1 ); tree->insert(tree, 2 ); tree->insert(tree, 3 ); tree->insert(tree, -1 ); tree->insert(tree, -2 ); tree->root->nodeDFS(tree->root); tree->root->nodeBFS(tree->root); deletetree(int )(tree); }
有根树 相当于是一个多节点的树，每个节点都有多个子节点，多叉树，操作系统中的文件结构就类似于一个有根多叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 #include <stdio.h> #define treenode(T) struct treenode_##T #define Queue(T) typedef struct queuetreenode_##T{\ void *start;\ void *end;\ struct treenode_##T **ptr;\ int size;\ void (*push)(struct queuetreenode_##T *queue, treenode_##T *val);\ void (*pop)(struct queuetreenode_##T *queue);\ void (*merge)(struct queuetreenode_##T *dst, struct queuetreenode_##T *src, int dstbegin, int srcbegin, int srcend);\ treenode_##T *(*top)(struct queuetreenode_##T *queue);\ }queuetreenode_##T; #define queue(T) queuetreenode_##T #define Push(T) void pushtreenode_##T(queuetreenode_##T *queue, struct treenode_##T *val){\ if ((void *) queue->ptr == queue->end){\ int size = queue->end - queue->start;\ void *newstart = malloc(2 * size);\ memcpy(newstart, queue->start, size);\ free(queue->start);\ queue->start = newstart;\ queue->end = queue->start + 2 * size;\ queue->ptr = queue->start + size;\ }\ memcpy(queue->ptr, &val, sizeof(struct treenode_##T *));\ queue->ptr += 1;\ queue->size++;\ } #define Pop(T) void poptreenode_##T(queuetreenode_##T *queue){\ if ((void *) queue->ptr == queue->start) return;\ memmove(queue->start, queue->start + sizeof(treenode_##T *), queue->end - queue->start - sizeof(treenode_##T *));\ queue->ptr -= 1;\ queue->size--;\ } #define Top(T) treenode_##T *toptreenode_##T(queuetreenode_##T *queue){\ treenode_##T *node = *((treenode_##T **) queue->start);\ return node;\ } #define Merge(T) void merge_##T(queuetreenode_##T *dst, queuetreenode_##T *src, int dstbegin, int srcbegin, int srcen){\ int srcsize = src->ptr - (treenode_##T * *) src->start;\ if (srcbegin >= srcsize){\ printf("begin index has out of range" );\ return;\ }\ if (srcend * sizeof(treenode_##T *) > srcsize){\ printf("end index has out of range" );\ return;\ }\ int dstmaxsize = dst->end - dst->start;\ int dstsize = (void *) dst->ptr - dst->start;\ while(dstmaxsize < dstsize + (srcend - srcbegin) * sizeof(treenode_##T *))\ dstmaxsize << 2;\ void *newstart = malloc(dstmaxsize);\ memcpy(newstart, dst->start, dstbegin * sizeof(treenode_##T *));\ memcpy(newstart + dstbegin * sizeof(treenode_##T *), src->start + srcbegin * sizeof(treenode_##T *), (srcend - srcbegin) * sizeof(treenode_##T *));\ memcpy(newstart + dstbegin * sizeof(treenode_##T *) + srcsize, dst->start + dstbegin * sizeof(treenode_##T *), (void *) dst->ptr - dst->start - dstbegin * sizeof(treenode_##T *));\ free(dst->start);\ dst->start = newstart;\ dst->end = newstart + dstmaxsize;\ dst->ptr = newstart + dstsize + (srcend - srcbegin) * sizeof(treenode_##T *);\ } #define NewQueue(T) queuetreenode_##T *newqueuetreenode_##T(int size){\ queuetreenode_##T *queue = (queuetreenode_##T *) malloc(sizeof(queuetreenode_##T));\ queue->start = malloc(sizeof(treenode_##T *) * size);\ queue->end = queue->start + sizeof(treenode_##T *) * size;\ queue->ptr = queue->start;\ queue->push = pushtreenode_##T;\ queue->pop = poptreenode_##T;\ queue->top = toptreenode_##T;\ queue->merge = merge_##T;\ } #define newqueue(T) newqueuetreenode_##T #define DeleteQueue(T) void deletequeuetreenode_##T(queuetreenode_##T *queue){\ free(queue->start);\ free(queue);\ } #define deletequeue(T) deletequeuetreenode_##T #define TreeNode(T) typedef struct treenode_##T{\ treenode_##T *parent;\ queuetreenode_##T *children;\ T val;\ void (*insert)(treenode_##T *this, treenode_##T *node);\ void (*dfs)(treenode_##T *this, void (*func)(treenode_##T *node));\ void (*bfs)(treenode_##T *this, void (*func)(treenode_##T *node));\ int (*isleaf)(struct treenode_##T *this);\ int (*isroot)(struct treenode_##T *this);\ }treenode_##T; #define NodeInsert(T) void nodeinsert_##T(treenode_##T *this, void (*func)(treenode_##T *node)){\ children->push(node);\ } #define NodeDFS(T) void nodedfs_##T(treenode_##T *this, void (*func)(treenode_##T *node)){\ if (!this)return;\ func(this);\ nodedfs_##T(this->left, func);\ nodedfs_##T(this->right, func);\ } #define NodeBFS(T) void nodebfs_##T(treenode_##T *this, void (*func)(treenode_##T *node)){\ queue(T) *nodequeue = newqueue(T)(32);\ nodequeue->push(this);\ while(nodequeue->size){\ treenode_##T *node = nodequeue->top(nodequeue);\ nodequeue->pop(nodequeue);\ if (!node)continue;\ func(node);\ nodequeue->merge(nodequeue, this->children, nodequeue->ptr - (treenode_##T **) node->start, 0, this->children->ptr - (treenode_##T **) this->children->start);\ }\ } #define IsLeaf(T) int isleaf_##T(treenode_##T *this){\ return this->children->ptr == this->children->start;\ } #define IsRoot(T) int isroot_##T(treenode_##T *this){\ return !this->parent;\ } #define NewTreeNode(T) treenode_##T *newtreenode_##T(T val){\ treenode_##T *node = (treenode_##T *) malloc(sizeof(treenode_##T));\ node->val = val;\ node->parent = NULL;\ node->children = newqueue();\ node->insert = NodeInsert(T);\ node->bfs = NodeBFS(T);\ node->dfs = NodeDFS(T);\ node->isleaf = IsLeaf(T);\ node->isroot = IsRoot(T);\ return node;\ } #define DeleteTreeNode(T) void deletetreenode_##T(treenode_##T *this){\ this->dfs(this, free);\ } #define newtreenode(T) newtreenode_##T #define deletetreenode(T) deletetreenode_##T #define Tree(T) typedef struct tree_##T{\ treenode_##T *root;\ int size;\ }tree_##T; #define tree(T) tree_##T #define NewTree(T) tree_##T *newtree_##T(){\ tree_##T *tree = (tree_##T *) malloc(sizeof(tree_##T));\ tree->root = NULL;\ tree->size = 0;\ return tree;\ } #define DeleteTree(T) tree_##T *deletetree_##T(tree_##T *this){\ deletetreenode(T)(this->root);\ free(this);\ } #define DEFINETREE(T) TreeNode(T)\ Queue(T)\ Push(T)\ Pop(T)\ Top(T)\ NewQueue(T)\ DeleteQueue(T)\ NodeInsert(T)\ NodeDFS(T)\ NodeBFS(T)\ IsLeaf(T)\ IsRoot(T)\ NewTreeNode(T)\ DeleteTreeNode(T)\ Tree(T)\ NewTree(T)\ DeleteTree(T)
矩阵 矩阵实际上就是一个结构体内部有着一个二维数组，并且对这个二维数组进行维护，进行加减乘等运算，还有转置和逆运算
图 图结构是描述和解决实际应用问题的一种基本而有力的工具，可以定义为 G=(V, E) ，其中 V 中的元素称作顶点，集合 E 中的元素对应着 V 中的某一对顶点的边
对于任何边 e = (u, v) ，称顶点u和v彼此邻接（adjacent），互为邻居；而它们都与边 e 彼此关联（incident），在无向图中，与顶点v关联的边数，称作v的度数（degree），记作 deg(v)
无向图 对于上述中的 E 集合中的边是没有方向的，或者说是双向的。
有向图 对于上述中的 E 集合中的边是有方向的的
混合图 对于上述中的 E 集合中的边是有方向和无方向的混合的
简单图 联接于同一顶点之间的边，称作自环（self-loop）
