目录
一、线性表
1.顺序表
2.单链表（不带头结点）
3.单链表（带头结点）
3.双链表（带头结点）
4.循环单链表（L指向表头）
5.循环单链表（L指向表尾)
6.循环双链表
7.静态链表
二、栈和队列
1.顺序栈
2.共享栈
3.链栈（带头）
4.链栈（不带头）
5.顺序队列
6.循环队列
6.1 rear指向队尾指针后一个位置and牺牲一个存储空间来区分队空和队满
6.2 rear指向队尾指针后一个位置and增设size判断
6.3 rear指向队尾指针后一个位置and增设tag判断
6.4 rear指向队尾and牺牲一个存储空间来区分队空和队满
6.2 rear指向队尾and增设size判断
6.3 rear指向队尾and增设tag判断
7.链队列（带头）
8.链队列（不带头）
三、串
1、串的基本操作
2、kmp模式匹配
四、树与二叉树
1、二叉树计算高度
2、二叉树的先序，中序，后序遍历（递归）
3、二叉树的先序，中序，后序遍历（非递归）
4、二叉树的层序遍历
5、中序线索化二叉树
6、先序线索化二叉树
7、后序线索化二叉树
8、先序，中序，后序线索二叉树总结
9、平衡二叉树
五、排序
1、插入排序
（1）直接插入排序
（2）折半插入排序
（3）希尔排序
2、交换排序
（1）冒泡排序
（2）快速排序
3、选择排序
（1）简单选择排序
（2）堆排序
4、归并排序
注：
一、线性表 1.顺序表 #include#include#includeusing namespace std;#define InitSize 10 //定义最大长度静态分配//typedef struct {//int data[InitList];//int length;//}SqlList;//动态分配typedef struct {int *data;int length;//当前长度int MaxSize;//最大长度}SqlList;//初始化顺序表void InitList(SqlList &L) {L.data = (int *)malloc(InitSize * sizeof(int));L.length = 0;L.MaxSize = InitSize;}//增加顺序表的长度void IncreaseSize(SqlList &L, int len) {int* p = L.data;L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));for (int i = 0; i < L.length; i++) {L.data[i] = p[i];}L.MaxSize += len;free(p);}//插入元素，在位序i的位置插入元素ebool ListInsert(SqlList& L, int i, int e) {if (iL.length + 1) return false;//i的范围是否有效if (L.length >= L.MaxSize) return false;//当前存储空间已满，不能插入for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];}L.data[i - 1] = e;L.length++;return true;}//删除操作，删除位序i个位置上的元素,e是删除的元素bool ListDelete(SqlList& L, int i, int& e) {if (iL.length) return false;e = L.data[i - 1];for (int j = i; j < L.length; j++) {L.data[j-1] = L.data[j];}L.length--;return true;}//按位查找 返回位序i的元素int GetElem(SqlList L, int i) {if (iL.length) return -1;return L.data[i - 1];}//查找第一个元素值等于e的元素，并返回其位序int LocateElem(SqlList L, int e) {for (int i = 0; i < L.length; i++) {if (L.data[i] == e) return i + 1;}return -1;}//删除值位于s和t之间的数bool Delete_s_t(SqlList& L, int s, int t) {if (L.length == 0 || s >= t) return false;int k = 0;for (int i = 0; i < L.length; i++) {if (L.data[i]t) {L.data[k++] = L.data[i];}}L.length = k;return true;}int main() {SqlList L;InitList(L);ListInsert(L, 1, 1);ListInsert(L, 2, 6);ListInsert(L, 3, 3);ListInsert(L, 4, 8);ListInsert(L, 5, 2);for (int i = 0; i < L.length; i++) {cout next;p->next = s;return true;}//不带头节点的插入操作，在第i个位置插入元素ebool ListInsert(LinkList& L, int i, int e) {if (i < 1) return false;if (i == 1) {LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = L;L = s;return true;}LNode* p;p = L;int j = 1;//当前p指向的是第几个节点，没有头节点，所以从1开始while (p && j < i - 1) {p = p->next;j++;}if (!p) return false;return InsertNextNode(p, e);}//前插操作，在p节点前插入元素ebool InsertPriorNode(LNode* p, int e) {if (!p) return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (!s) return false;s->next = p->next;p->next = s;s->data = p->data;p->data = e;return true;}//前插操作，在节点p之前插入节点sbool InsertPriorNode(LNode* p, LNode* s) {if (!p || !s) return false;s->next = p->next;p->next = s;swap(s->data, p->data);return true;}//删除位序i的节点，e是i节点的值bool ListDelete(LinkList& L, int i, int& e) {if (L == NULL) {e = -1;return false;}if (i < 1) return false;if (i > 1) {LNode* p = GetElem(L, i - 1);if (!p || !(p->next)) return false;LNode* q = p->next;e = q->data;p->next = q->next;free(q);}else {if (L->next == NULL) {e = L->data;L = NULL;}else {e = L->data;L = L->next;}}return true;}//删除指定节点Pbool DeleteNode(LNode* p) {if (p->next == NULL) return false;//下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作LNode* q = p->next;p->data = q->data;p->next = q->next;free(q);return true;}//尾插法，不带头结点LinkList List_TailInsert(LinkList& L) {InitList(L);LNode* s, * r = L ;//r表示表尾指针int x;bool is_head = true;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));if (is_head) {is_head = false;s->data = x;L = s;r = s;}s->data = x;r->next = s;r = s;}r->next = NULL;return L;}//头插法，不带头结点LinkList List_HeadInsert(LinkList& L) {InitList(L);LNode* s;int x;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L;L = s;}return L;}void print(LinkList L) {LNode* s = L;while (s!= NULL) {cout data next;}cout next = p->next;p->next = s;swap(s->data , p->data);return true;}//删除位序i的节点，e是i节点的值bool ListDelete(LinkList& L, int i, int& e) {if (i < 1) return false;LNode* p = GetElem(L, i - 1);if (!p || !(p->next)) return false;LNode* q = p->next;e = q->data;p->next = q->next;free(q);return true;}//删除指定节点Pbool DeleteNode(LNode* p) {if (p->next == NULL) return false;//下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作LNode* q = p->next;p->data = q->data;p->next = q->next;free(q);return true;}bool InitList(LinkList& L) {L = (LNode* )malloc(sizeof(LNode));//分配一个头节点if (!L) return false;L->next = NULL;return true;}//尾插法，带头结点LinkList List_TailInsert(LinkList& L) {L = (LinkList)malloc(sizeof(LNode));L->next = NULL;LNode* s, * r = L;//r表示表尾指针int x;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;}r->next = NULL;return L;}//头插法，带头结点LinkList List_HeadInsert(LinkList& L) {L = (LinkList)malloc(sizeof(LNode));L->next = NULL;LNode* s;int x;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;}return L;}void print(LinkList L) {LNode* s = L;while (s->next!=NULL) {s = s->next;cout data next = p->next;}p->next = q;return true;}//前插，在p节点前面插入节点sbool InsertPriorDnode(DNode* p, DNode* s) {return InsertNextDNode(p->prior, s);}//按位插入，在第i个位置插入值为e的节点（位序i）bool InsertDLinkList(DLinkList& L, int i, ElemType e) {if (i next;if (q == NULL) return false;p->next = q->next;if (q->next != NULL) q->next->prior = p;free(q);return true;}//销毁双链表bool DestoryList(DLinkList& L) {while (L->next != NULL) {DeleteNextNode(L);}free(L);L = NULL;return true;}//尾插法DLinkList List_TailInsert(DLinkList& L) {InitDLinkList(L);DNode* p = L;ElemType x;while (cin >> x) {InsertNextDNode(p, x);p = p->next;}return L;}//头插法DLinkList List_HeadInsert(DLinkList& L) {InitDLinkList(L);ElemType x;while (cin >> x) {InsertNextDNode(L, x);}return L;}int Length(DLinkList L) {DNode* p = L;int len = 0;while (p->next != NULL) {len++;p = p->next;}return len;}//删除指定节点sbool DeleteNode(DNode* s) {DNode* p;p = s->prior;p->next = s->next;if (s->next != NULL) {s->next->prior = p;}free(s);return true;}//删除位序i的节点，e是i节点的值bool ListDelete(DLinkList& L, int i, ElemType& e) {if (i Length(L)) return false;DNode* s;s = GetElem(L, i);if (s == NULL) return false;e = s->data;return DeleteNode(s);}void print(DLinkList L) {DNode* p = L->next;while (p != NULL) {cout data next;}cout next;e = q->data;p->next = q->next;free(q);return true;}//删除指定节点Pbool DeleteNode(LinkList& L, LNode* p) {LNode* q = p->next;p->data = q->data;p->next = q->next;if (L == q) {L = p;}free(q);return true;}//尾插法，带头结点LinkList List_TailInsert(LinkList& L) {InitList(L);LNode* s, * r = L;//r表示表尾指针int x;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;}r->next = L;return L;}//头插法，带头结点LinkList List_HeadInsert(LinkList& L) {InitList(L);LNode* s, * r = L;int x;bool isFirst = true;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;if (isFirst) {r = s;isFirst = false;}}r->next = L;return L;}bool Empty(LinkList L) {if (L->next == L) {return true;}return false;}//判断是否为表尾节点bool isTail(LinkList L, LNode* p) {if (p->next == L) return true;return false;}void print(LinkList L) {LNode* s = L->next;while (s != L) {cout data next;}cout next;e = q->data;p->next = q->next;free(q);return true;}//删除指定节点Pbool DeleteNode(LinkList& L, LNode* p) {LNode* q = p->next;p->data = q->data;p->next = q->next;if (L == p) {//尾节点q = p;while (q->next != p) {q = q->next;}L = q;}//free(q)；不能这样写，因为指针之间的赋值是指向同一块区域，就比如L和q就是指向相同的区域return true;}//尾插法，带头结点LinkList List_TailInsert(LinkList& L) {InitList(L);LNode* s, * r = L;//r表示表尾指针int x;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;}r->next = L;L = r;return L;}//头插法，带头结点LinkList List_HeadInsert(LinkList& L) {InitList(L);LNode* s, * r = L;int x;bool isFirst = true;while (cin >> x) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;if (isFirst) {r = s;isFirst = false;}}r->next = L;L = r;return r;}bool Empty(LinkList L) {if (L->next == L) {return true;}return false;}//判断是否为表尾节点bool isTail(LinkList L, LNode* p) {if (p == L) return true;return false;}void print(LinkList L) {LNode* s = L->next->next;while (s != L->next) {cout data next;}cout x) {InsertNextDNode(L, x);}return L;}int Length(DLinkList L) {DNode* p = L;int len = 0;while (p->next != L) {len++;p = p->next;}return len;}//删除指定节点sbool DeleteNode(DNode* s) {DNode* p;p = s->prior;p->next = s->next;s->next->prior = p;free(s);return true;}//删除位序i的节点，e是i节点的值bool ListDelete(DLinkList& L, int i, ElemType& e) {if (i Length(L)) return false;DNode* s;s = GetElem(L, i);if (s == NULL) return false;e = s->data;return DeleteNode(s);}void print(DLinkList L) {DNode* p = L->next;while (p != L) {cout data next;}cout