数据结构

#C #Cpp
Table of Contents

github仓库

链表

单向链表

Untitled

单向链表每次查找只能从前向后查找，单向的，只会有一个指针并且指向下一个节点。所以每个节点只能找到自己后面的节点，但是无法找到之前的链表。

对于循环链表，最末端的节点会指向头节点，形成首尾相接的循环。

  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

//------------------------------------------------------------------------
// File Name: mylist.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Mon 25 Sep 2023 20:34:40 CST
// Description: 单向链表 insert remove new delete
//------------------------------------------------------------------------

#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
// insert at the front of index node
#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;\
}
// remove the next of iterator
#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--;\
}
// 都是以节点之后开始的
// [srcbegin, srcend) 节点id从1开始
#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);
  // while(iterator != list1->tail){
  //   printf("%d\n", iterator->val);
  //   iterator = iterator->next;
  // }
  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);
}

双向循环链表

doublelist

链表中有两个指针(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

//------------------------------------------------------------------------
// File Name: mydoublelist.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Thu 28 Sep 2023 14:34:59 CST
// Description: 双向链表
//------------------------------------------------------------------------

#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);
}

跳表

Untitled

是一种随机化的数据结构，实质上就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能

这种随机的数据结构，可以看做是一个二叉树的变种，它在性能上与红黑树、AVL树很相近；但是Skip List(跳跃列表)的实现相比前两者要简单很多

从功能角度来看，跳跃表就像在链表之上架起了查询的“高速公路”，可以在普通链表上快速的查找到所要的元素。在查找元素时，跳表能够提供 O(log n) 的时间复杂度

对于一个链表来说，需要查找某个元素必须从头向后扫描，直到找到该元素或者扫描到完整的链表。

但是对于一个有序链表，可以提取出来其中的某些节点作为索引值，可以更快的找到所需要的元素，如上图

要想实现比较快的查找，可以通过构建索引，使得每一个 K 级节点都有 K + 1 个指针，分别跳过 $2^K-1,2^{K-1}-1,...,2^0-1$ 个节点，这样就可以实现较快查找。

但是这个构建是静态的，并不能保证动态（插入或者删除节点）稳定性。所以可以首先确定一个实数 p，使得 $0

上述实现时，可以利用随机数 0~1，如果是 1 就加一个等级，一直到出现 0 为止。然后将节点插入到链表中

数组

Untitled

 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

//------------------------------------------------------------------------
// File Name: myarray.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Wed 27 Sep 2023 08:23:46 CST
// Description:
//------------------------------------------------------------------------

#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

//------------------------------------------------------------------------
// File Name: myqueue.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Wed 27 Sep 2023 09:06:03 CST
// Description:
//------------------------------------------------------------------------

#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

//------------------------------------------------------------------------
// File Name: myqueue.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Wed 27 Sep 2023 09:06:03 CST
// Description:
//------------------------------------------------------------------------

#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

//------------------------------------------------------------------------
// File Name: priorityqueue.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Wed 04 Oct 2023 08:41:25 CST
// Description:  优先级队列
//------------------------------------------------------------------------

#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
// Binary search sort insert
#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

//------------------------------------------------------------------------
// File Name: myvector.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Fri 29 Sep 2023 11:36:37 CST
// Description: 向量
//------------------------------------------------------------------------

#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;\
}
// srcbegin and srcend is index
#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);
}

栈

Untitled

栈和堆是计算机中比较常用的数据结构，在计算机中，会有栈内存和堆内存，堆是向高地址扩展 也就是常说的向上生长。是不连续的内存区域。栈是向低地址扩展 也就是常说的向下生长。 是连续的内存区域。而且栈是系统分配的内存，速度较快，会自动回收，但是堆是程序员分配的内存，不会自动回收，但是程序结束之后会被回收。

  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

//------------------------------------------------------------------------
// File Name: mystack.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Fri 29 Sep 2023 14:05:50 CST
// Description: 栈
//------------------------------------------------------------------------

#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，而且在二叉树中的查找速度相当于是

$$O(\log_2n)$$

。但是需要特定的算法来保持树的平衡

  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

//------------------------------------------------------------------------
// File Name: mybinarytree.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Mon 02 Oct 2023 10:57:36 CST
// Description: （平衡）二叉树
//------------------------------------------------------------------------

#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
// 这里的 size 函数是深度优点算法
// 广度优先算法需要借助其他数据结构了
#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

//------------------------------------------------------------------------
// File Name: k-arytree.c
// Author: Dragon
// mail: [beloved25177@126.com](mailto:beloved25177@126.com)
// Created Time: Thu 05 Oct 2023 11:35:22 CST
// Description: 有根树
//------------------------------------------------------------------------

#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)

矩阵

矩阵实际上就是一个结构体内部有着一个二维数组，并且对这个二维数组进行维护，进行加减乘等运算，还有转置和逆运算

matrix

图

图结构是描述和解决实际应用问题的一种基本而有力的工具，可以定义为 G=(V, E) ，其中 V 中的元素称作顶点，集合 E 中的元素对应着 V 中的某一对顶点的边

对于任何边 e = (u, v) ，称顶点u和v彼此邻接（adjacent），互为邻居；而它们都与边 e 彼此关联（incident），在无向图中，与顶点v关联的边数，称作v的度数（degree），记作 deg(v)

map

无向图

对于上述中的 E 集合中的边是没有方向的，或者说是双向的。

有向图

对于上述中的 E 集合中的边是有方向的的

混合图

对于上述中的 E 集合中的边是有方向和无方向的混合的

简单图

联接于同一顶点之间的边，称作自环（self-loop）

← prev next →