栈 本文部分截图来自王道考研 书籍参考：[1]王晓东.数据结构（语言描述）[M].北京：电子工业出版社.2019前言 前言 栈是一种特殊的表，这种表只能在表首进行插入和删除。所以表首对于栈有特殊意义，称为栈顶，表尾称为栈底，不含任何元素的栈称为空栈。可以简单的来说，栈的修改是按后进先出的原则进行，又称为后进先出（Last In First Out）表，简称LIFO表。 假社一个栈SSS中的元素为a(n),a(n−1),...,a(1)a(n),a(n-1),...,a(1)a(n),a(n−1),...,a(1)，则称a(1)a(1)a(1)为栈底元素，a(n)a(n)a(n)为栈顶元素。栈中元素按照a(1),a(2)...,a(n)a(1),a(2)...,a(n)a(1),a(2)...,a(n)的顺序进栈，第一个进栈的是a(1)a(1)a(1)，接着依次往后，任何时候，出栈的都是栈顶元素a(n)a(n)a(n)。当nnn个不同的元素进栈，出栈元素不同排列的个数则为 1n+1C2nn\frac{1}{n+1}C_{2n}^n n+11​C2nn​ 这个公式称为卡特兰（Catalan）数 InitStack(&S)：初始化栈，构造一个空栈SSS，分配内存空间。 StackFree(&S)`：销毁栈，销毁并释放栈SSS所占用的内存空间 Push(&S,x)：进栈，若栈SSS未满，则将xxx加入使之成为新栈顶。 Pop(&S,&x)：出栈，若栈SSS非空，则弹出栈顶元素，并用xxx返回。 StackTop(&S,&x)：读入栈顶元素，若栈SSS非空，则用xxx返回栈顶元素 StackEmpty(&S)：判断一个栈SSS是否为空，若SSS为空，则返回True，否则False 栈的顺序存储 栈是一个特殊的表，所以可以使用数组来实现栈，用一个数组data存储栈元素，栈底固定在数组的底部，即data[0]为最早的入栈元素 代码实现 栈的顺序存储实现 // 栈-顺序存储 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct astack{ int top, //栈顶 maxtop; // 栈空间上界 int *data; // 存储栈元素的数组 }Astack; typedef struct astack *Stack; //栈指针类型 Stack StackInit(int size){ Stack S = (Stack)malloc(sizeof(*S)); // 创建一个空栈 S->data = (int *)malloc(size*sizeof(int)); //为存储栈元素的数组分配内存空间 S->maxtop = size; // 栈空间上限为size S->top = -1; // 初始化栈顶指针 return S; } void testStack(){ Stack S; S = StackInit(10); } int main(){ testStack(); return 0; } 创建一个size大小的栈，因为刚开始的时候，data[0]还没存放数据，所以S->top初始化不能等于000，令它等于−1-1−1 栈顺序存储的基本操作 判断非空 int StackEmpty(Stack S){ /* 是否为空栈 */ return S->top < 0; // 如果栈顶小于0，证明还没存储元素 } 进栈操作 void Push(Stack S, int x){ /* 进栈操作 */ if (StackFull(S)){ // 判断是否栈满 exit(1); } S->top = S->top+1; // 栈顶加1 S->data[S->top] = x; // 添加一个元素 } 先判断栈顶指针是否已经达到了栈的最大容量，如果是返回False。因为入栈了一个元素，所以栈顶指针加1，再令当前栈顶指针的位置等于插入元素xxx。 出栈操作 int Pop(Stack S){ /* 出栈操作 */ if(StackEmpty(S)){ exit(1); } int x = S->data[S->top]; //返回出栈的元素 S->top = S->top-1; // 栈顶减一 return x; } 令栈顶指针top减去一位，使得逻辑上进行一个出栈操作，但实际数据还是遗留在内存中。 读栈顶元素 int StackTop(Stack S){ /* 读取栈顶 */ if (StackEmpty(S)){ exit(1); } return S->data[S->top]; } 因为数组是动态分配的，所以需要写一个释放内存的函数 void StackFree(Stack S){ free(S->data); free(S); } 打印栈 void StackPrint(Stack S){ /* 打印栈 */ for (int i=S->top; i>=0; i--){ // 因为栈后进先出，所以要从栈顶开始打印，一直到栈底 printf("%d\n",S->data[i]); } } 在同时使用过多个栈的情况，为了不会栈溢出，通常要给栈分配一个较大的栈空间，但是各个栈在算法运行中，所使用的最大空间很难估计。所以可以使用共享栈来提高栈空间的利用率。 例如两个栈使用同一个数组data[0:n]，那么利用栈底不变的特性，一个栈底设为0，另一个栈底设为n，分别各自往数组中间延申。这样每一个栈最大的可用空间为n2\frac{n}{2}2n​。 栈的链式存储 如果要用到多个栈的时候，可以使用链表作为栈的存储结构，也就是栈的链式存储，就是用指针来实现栈。这样方式使栈有着动态大小，这种实现方式也被称为链栈 代码实现 栈的链式存储实现 // 栈-链式存储 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct snode{ // 栈结构 int data; // 栈元素 struct snode *next; // 下一结点指针 }StackNode; typedef StackNode *SLink; // 栈结点指针类型 typedef struct lstack{ // 栈结构 SLink top; // 栈顶指针 }Lstack; typedef Lstack *Stack; SLink NewStackNode(){ /* 创建新结点 */ return (SLink)malloc(sizeof(StackNode)); } Stack StackInit(){ /* 初始化栈 */ Stack S = (Stack)malloc(sizeof(*S)); S->top = NULL; // top置为空指针 return S; } void testStack(){ Stack S; S = StackInit(); } int main(){ testStack(); return 0; } 首先创建一个栈结点的类型，data存储栈元素，next指向下一个结点的指针。使用typedef创建一个snode类型的栈结点指针类型SLink。 再创建一个链栈Stack，其中结构只有一个栈顶指针，其指针的类型是栈结点指针类型SLink。 栈链式存储的基本操作 判断非空 int StackEmpty(Stack S){ /* 判断释放为空栈 */ return S->top == NULL; } 进栈操作 void Push(Stack S, int x){ SLink p = NewStackNode(); // 申请一个结点的内存空间 p->data = x; // 将栈元素存入 p->next = S->top; // 将新结点的下一个结点指针置空 S->top = p; // 栈顶结点下一个为p，使p为新的栈顶 } 为新结点申请一块内存空间，同时类型设置为栈结点指针类型，将元素x存入data中，将新结点的下一个结点置为top的下一个结点。因为top的下一个结点是NULL，所以此时结点p的下一个结点也为NULL。这时结点p为栈的栈顶。 出栈操作 int Pop(Stack S){ /* 出栈操作 */ if (StackEmpty(S)){ // 判断栈是否为空栈 exit(1); } int x = S->top->data; // 返回出栈元素 SLink p = S->top; // 另p等于栈顶指针 S->top = p->next; // 将栈顶指针top，指向p的下一个结点。 free(p); // 释放p return x; } 假设栈内结点为k−>q−>s−>Nullk->q->s->Nullk−>q−>s−>Null，这时执行出栈操作，这时候的栈顶为sss，定义一个变量xxx，另它等于栈顶的data，将出栈元素赋值给x，再函数的结尾处返回。定义一个栈指针类型的结点ppp，另它等于栈顶，所以这个时候栈内就变成这样k−>q−>p−>Nullk->q->p->Nullk−>q−>p−>Null。将栈顶指向ppp的下一个结点，也就是NullNullNull,k−>q−>NULLk->q->NULLk−>q−>NULL，最后将ppp占用的结点内存释放。 读栈顶元素 int StackTop(Stack S){ /* 读取栈顶元素 */ if (StackEmpty(S)){ exit(1); } return S->top->data; } 打印栈 int StackPrint(Stack S){ /* 打印栈 */ if (StackEmpty(S)){ // 判断非空 exit(1); } SLink p = NewStackNode(); // 创建一个结点 p = S->top; // 令p等于栈顶结点 while (p!=NULL){ printf("%d\n",p->data); // p = p->next; } }

线性表 本文部分截图来自王道考研 书籍参考：[1]王晓东.数据结构（语言描述）[M].北京：电子工业出版社.2019前言 前言 线性表是一种非常灵便的结构，可以根据需要改变的表的长度，也可以在表中任何位置对元素进行访问、插入、删除等操作。还可以将多个表连接成为一个表，也可以对一个表进行拆分成多个表。 线性表的定义，是具有相同数据类型的n(n≥0)n(n \geq 0)n(n≥0)个数据元素组成的***有限序列***，其中元素nnn的个数定义为表的长度。当n=0n=0n=0时，线性表是一个空表，当n≥1n \geq 1n≥1时，称元素a(k)a(k)a(k)位于该表的第kkk个位置。若用L命名线性表，则其一般表示为 L=(a1,a2,.....,ai,ai+1,.....,an)L=(a_1,a_2,.....,a_i,a_{i+1},.....,a_n) L=(a1​,a2​,.....,ai​,ai+1​,.....,an​) 除此之外，还要定义一些关于线性表的运算，将这一个数学模型成为一个抽象数据***List***。用xxx表示表中的一个元素，kkk表示元素在表中的位置。 InitList(&L)：初始化表，创建一个新的线性表LLL，分配内存空间 Destroy(&L)：销毁线性表，释放LLL所占的内存空间 ListEmpty(&L) ：测试表LLL是否为空 ListLength：表LLL的长度 ListLocate(&x,&L)：元素xxx在表中LLL的位置，如果xxx在表中重复出现，返回最前面的 ListRetrieve(&k,&L)：返回LLL中的kkk处位置的元素 ListInsert(&k,&x,&L)：在表LLL的k处位置插入元素xxx，将原来占据该位置的元素及其后面都向后推一个位置 ListDelete(&k,&L)：将表LLL的kkk处位置的元素删除，并返回删除的元素。 PrintList(&L)：将表LLL中的所有元素按照位置顺序打印输出 顺序表（数组实现） 定义 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来实现 这种方法，容易实现对表的遍历，在表的尾部插入一个元素很容易。但是如果要在表的头和中间的位置插入一个新元素。那么这个新元素插入位置的后面所有元素都要后移一位，为空出位置，存放新元素。删除以是如此，如果删除的元素不是表的最后一位，那么被删除元素后面的所有元素，都要往前移动一位，填补空缺。 代码实现 顺序表的实现-静态分配 // 定义一个表的结构，ElemType在数据结构表示，任何一种数据类型，并无实际的此类型 // 如果是int类型，将ElemType改为int即可 #define MaxSize 10 // 定义最大长度 typedef struct{ ElemType data[MaxSize]; // 用静态的数组存放数据元素 int length; //顺序表当前长度 }SqList; //顺序表的类型定义（静态分配方式） // 实现代码 // 顺序表-静态分配 #include <stdio.h> #define MaxSize 10 // 定义最大长度 // 表的类型定义 typedef struct{ int data[MaxSize]; // 用静态的数组存放数据元素 int length; // 表的当前长度 }SqList; typedef SqList *List; void InitList(List L){ /* 初始化一个数组 */ for (int i=0; i<MaxSize; i++){ L->data[i]=0; // 将所有数据元素设置为默认初始值 } L->length=0; } int main(){ List L; InitList(L); return 0; } 在IinitList初始化表的函数中，用了一个for函数对每一个元素进行了初始化，如果不怎么会给内存遗留的脏数据污染（如下图）。 静态分配的精髓就是再data[MaxSize]，直接设置一个固定的长度的数组。但是有非常大的缺陷，如果存满的只能放弃这个数组，因为静态数组的表长确定后创建是不能更改的。 顺序表的实现-动态分配 #define InitSize 10 // 顺序表的初始长度 typedef struct{ ElemType *data; //动态分配数组的指针 int maxsize; // 顺序表的最大容量 int length; // 顺序表的当前长度 }SeqList; c语言实现顺便表的动态分配，主要依靠malloc free两个函数，一个进行动态申请内存空间，一个进行释放内存空间，包含在头文件<stdlib.h>头文件中 #include <stdlib.h> L->data = (ElemType *)malloc(sizeof(ElemType)*InitSize); // 申请空间 free(L); //释放空间 #include <stdio.h> #include <stdlib.h> #define InitSize 10 typedef struct{ int *data; int maxsize; int length; }SeqList; typedef SeqList *SList; void InitList(SList L){ /* 初始化一个动态分配数组 */ L->data=(int *)malloc(InitSize*sizeof(int)); // 申请InitSize值的内存空间 L->length = 0; L->maxsize = InitSize; } void IncreaseSize(SList L,int len){ /* 增加动态数组的长度 */ int *p = L->data; //先将原先的数组保存 L->data = (int *)malloc((L->maxsize+len)*sizeof(int)); // 申请加上len之后的内存空间大小 for (int i=0; i<L->length; i++){ L->data[i] = p[i]; //将数据复制到新区域 } L->maxsize = L->maxsize+len; // 顺序表最大长度添加len free(p); // 释放原来的内存空间 } void ListFree(SList L){ /* 释放表 */ free(L->data); free(L); } int main(){ //动态分配 SList L; InitList(L); IncreaseSize(L,5); return 0; } 不管是动态分配还是静态分配，都具有一些相同的特性 随机访问，可以在O(1)O(1)O(1)时间内找到第i个元素 存储密度高，每一个节点只存储数据元素本身 关于顺序表的基本操作 代码实现 表的类型定义 typedef struct alist{ int n; // 表长 int MaxSize; // 定义数组长度 int curr; //当前位置 int *table; //存放数据元素的数组 }Alist; typedef Alist *List; 初始化size大小的表 List ListInit(int size){ /* 初始化表 */ List L = (List)malloc(sizeof(*L)); //为表L申请一块内存空间 L->table = (int *)malloc(size*sizeof(int)); // 为表L中存放数据的数组申请一块内存空间 L->MaxSize = size; L->n = 0; // 因为是动态数组，所以先另表长为0 return L; //返回表L } 测试表L是否为空 int ListEmpty(List L){ /* 测试是否为空 */ return L->n == 0; //如果表L的n等于0，代表表当前长度为0 } 释放表L的所申请的内存空间 void ListFree(List L){ free(L->table); free(L); } 在表L的k位置处插入元素x void ListInsert(int k, int x, List L){ /* 表中插入元素 */ if (k<1 || k>L->n+1){ // 如果插入的位置小于1或者大于表当前长度,返回false ListFree(L); exit(1); } if (L->n >= L->MaxSize){ // 如果插入的位置大于表的最大长度,返回false ListFree(L); exit(1); } for (int j=L->n; j>=k; j--){ // 如果j大于k，那么将k以及后面的元素后移 L->table[j] = L->table[j-1]; } L->table[k-1] = x; // 在k位置存入x L->n++; // 表的当前长度+1 } 删除表中k处的元素 int ListDelete(int k, List L){ /* 删除k处的元素 */ if (k<1 || k>L->n) // 如果删除的位置小于1或者大于表当前长度,返回false ListFree(L); exit(1); } int x = L->table[k-1]; for (int i=k; i<L->n; i++){ // 将所有的值往前移一位 L->table[i-1] = L->table[i]; } L->n--; // 表长减一 return x; } 元素x在表中的位置（按值查找） int ListLocate(int x, List L){ /* 元素x在表中的位置 */ for (int i=0; i<L->n; i++){ //循环表 if (L->table[i] == x){ // 如果第i位的元素，等于x，证明x在i位 return i+1; // 因为表是从0开始，所以返回位置的时候，要加一位 } } return 0; } 表中k处的元素（按位查找） int ListRetrieve(int k, List L){ /* 返回表中k处位置的元素 */ if (k<1 || k>L->n){ // 如果调用的函数时，k的参数是小于1，或者大于表长的，则退出程序 exit(1); } return L->table[k-1]; } 部分表操作的时空复杂度 插入的时空复杂度 如果插入的地方，为表尾，那么这是最好的情况，时间复杂度为O(1)O(1)O(1)。最坏情况下需要O(n)O(n)O(n)的时间。因为插入的位置可以是表的任意位置，所以需要分析一下平均时间复杂度。设在长度为nnn的表中进行插入，那么所需元素移动次数的平均值为EIN(n)E_{IN}(n)EIN​(n)。在表中第kkk个位置插入元素x需要移动数组元素n−kn-kn−k次。所以 EIN(n)=∑k=0nPk(n−k)E_{IN}(n)=\sum_{k=0}^nP_k(n-k) EIN​(n)=k=0∑n​Pk​(n−k) PkP_kPk​表示在表中第kkk个位置插入元素的概率，假设在表中任何合法位置插入元素的机会是均等的，则 P0=P1=...=Pn=1n+1P_0=P_1=...=P_n=\frac{1}{n+1} P0​=P1​=...=Pn​=n+11​ 那么在同等概率下 EIN(n)=∑k=0nPk(n−k)=∑k=0nn−kn+1=n2E_{IN}(n)=\sum_{k=0}^nP_k(n-k)=\sum_{k=0}^n\frac{n-k}{n+1}=\frac{n}{2} EIN​(n)=k=0∑n​Pk​(n−k)=k=0∑n​n+1n−k​=2n​ 因为使用大n表示法，系数可以忽略，所以平均时间复杂度为 O(n)O(n) O(n) 删除的时空复杂度 与插入一样，设在长度为nnn的表中删除一个元素，所需要元素移动次数的平均值为EDE(n)E_{DE}(n)EDE​(n)。删除表中第kkk个位置上的元素移动次数为n−kn-kn−k次。所以 EDE(n)=∑k=0nQk(n−k)E_{DE}(n)=\sum_{k=0}^nQ_k(n-k) EDE​(n)=k=0∑n​Qk​(n−k) QkQ_kQk​表示在第kkk个位置删除元素的概率，在等概率删除的情况下 Q1=Q2=...=Qn=1nQ_1=Q_2=...=Q_n=\frac{1}{n} Q1​=Q2​=...=Qn​=n1​ 所以可知 EDE(n)=∑k=0nQk(n−k)=∑k=0nn−kn=n−12E_{DE}(n)=\sum_{k=0}^nQ_k(n-k)=\sum_{k=0}^n\frac{n-k}{n}=\frac{n-1}{2} EDE​(n)=k=0∑n​Qk​(n−k)=k=0∑n​nn−k​=2n−1​ 同样因为是大n表示法，所以平均时间复杂度为 O(n)O(n) O(n) 链表-单链表 定义 单链表是一种链式存储，由一个个节点构成。每一个节点除了存放数据元素外，还要存放指向下一个节点的指针，用指针依次串联起来。 这种方法不需要大片连续的存储空间，改变容量方便。插入和删除运算时，不在需要移动元素来移动或者填补空缺。但缺点就是因为每一个节点中设置了指针来表示元素之间的逻辑关系，所以增加了一定的空间开销，同时不可以在随机存取。如果表是$ a(1),a(2),(3)....a(n) ，那么元素，那么元素，那么元素a(k)的指针应指含有元素的指针应指含有元素的指针应指含有元素a(k+1)$的单元。 代码实现 单链表的实现 // 单链表节点类型 typedef struct LNode{ ElemType data; // 每一个节点存放一个数据类型 称为数据域 struct LNode *next; // 指针指向下一个节点 称为指针域 }LNode; 增加一个新的节点，在内存中申请一个节点所需空间，并用指针p指向这个节点 typedef struct LNode LNode; LNode *p = (LNode *)malloc(sizeof(struct LNode)); 表示一个单链表时，只需要声明一个头指针L，指向单链表的下一个指针 // 两种写法 typedef struct LNode *LinkList; LNode * L; LinkList L; // 两种定义方法效果是一样的，用LinkList可读性好一些 不带头节点的单链表 // 单链表-代码 #include <stdio.h> #include <stdbool.h> typedef struct LNode{ // 定义单链表节点类型 int data; //每一个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode, *LinkList; // 初始化一个空的单链表 bool InitList(LinkList L){ /* 初始化单链表 */ L = NULL; // 空表暂时没有节点 return true; } void testLink(){ /* 测试不带头节点的单链表 */ LinkList L; //声明一个指向单链表的指针 InitList(L); //初始化一个空表 } int main(){ testLink(); return 0; } 另L=NULL，和之前顺序表的初始化一样，也是为了除去内存遗留的脏数据 带头节点的单链表 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct LNode{ // 定义单链表节点类型 int data; //每一个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode; typedef LNode *LinkList; bool InitHeadList(LinkList L){ /* 初始化带头节点的单链表 */ L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点 if (L==NULL){ // 如果L分配之后，还是为NULL，代表内存不足分配失败 return false; } L->next = NULL; // 头节点之后暂时还没有节点 return true; } void testHeadLink(){ /* 测试带头节点的单链表 */ LinkList L; InitHeadList(L); } int main(){ // testLink(); testHeadLink(); return 0; } 其中不带头节点的话，头指针指向的下一个元素存储数据，而带头节点则是头节点是不存储数据的，头节点的下一节点才存储。不带头节点写代码更加麻烦，对第一个数据节点和后续的节点都需要不同的代码逻辑，对空表和非空表的处理也不相同，所以大多数情况，还是使用带头节点的单链表。 关于单链表的基本操作 （除了特别声明，默认操作的都是带头节点的单链表） 代码实现 表的类型定义 typedef struct LNode{ // 定义单链表节点类型 int data; //每一个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode; 单链表的初始化 bool InitHeadList(LinkList L){ /* 初始化带头节点的单链表 */ L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点 if (L==NULL){ // 如果L分配之后，还是为NULL，代表内存不足分配失败 return false; } L->next = NULL; // 头节点之后暂时还没有节点 return true; } 按位序插入（在第i位插入元素e） bool LinkInsert(LinkList L, int i, int e){ if ( i<1 ){ return false; } LNode *p; // 指针p指向当前扫描到的节点 int j=0; // 当前p指向的是第几个节点 p = L; // L指向头节点，头节点是第0个节点 while (p!=NULL && j<i-1){ // 循环找到第i-1个节点 p = p->next; j++; } if (p==NULL){ // i的值不合法 return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; //s的next指向原先第i-1节点的下一个节点 p->next = s; // 将节点s连接到p return true; } 首先定义一个指针p，用于指向当前的节点，定义一个变量j用于表示p是第几个节点。然后在初始化中的头节点L等于p。开始进行循环，将p扫描节点依次后移，直至不满足循环条件，这时指针p就为第i-1个节点，然后定义一个新的节点s，然后s的next指向原先第i-1节点的下一个节点（如果是一条从头节点开始的全新单链表，那么p的next是NULL，为了考虑到插入的情况，可能是已经前后都含有数据的单链表，所以s的next不能直接设置为NULL，必须设置为p节点的next），使第i-1个节点的next指向s。 指定节点的后插操作 bool InsertNextNode(LNode *p, int e){ /*后插操作：在p节点之后插入元素e */ if (p==NULL){ return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); if (s==NULL){ // 分配内存失败 return false; } s->data = e; // 用节点s保存数据e s->next = p->next; p->next = s; //将节点s连接到p之后 return true; } 这里没有什么可以说的，就是把s的下一个指向等于p的下一个指向，再让p的下一个指向等于节点s。可以扩展一下的就是，可以将后插操作的函数应用到位序插入中 bool LinkInsert(LinkList L, int i, int e){ if ( i<1 ){ return false; } LNode *p; // 指针p指向当前扫描到的节点 int j=0; // 当前p指向的是第几个节点 p = L; // L指向头节点，头节点是第0个节点 while (p!=NULL && j<i-1){ // 循环找到第i-1个节点 p = p->next; j++; } InsertNextNode(p, e); } 指定节点的前插操作 bool InsertPriorNode(LNode *p, int e){ /* 在节点p之前插入元素e */ if (p==NULL){ return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); if (s==NULL){ return false; } s->next = p->next; //新节点s连接到p之后 p->next = s; s->data = p->data; // 对p节点和s节点的数据元素进行替换 p->data = e; return true; } 实现方式可以有两种，一种是传入一个单链表L，然后进行遍历，时间复杂度为O(n)O(n)O(n)。一种将新节点放在指定节点之后，然后对新节点和指定节点的数据元素进行替换，使得逻辑上达到了前插操作，同时将时间复杂度变成了O(1)O(1)O(1)。 按位序删除 int ListHeadDelete(LinkList L, int i){ if (i<1){ return false; } LNode *p; // 指针p指向当前扫到的节点 int j=0; // 当前p指向的是第几个节点 p = L; // L指向头节点 while (p!=NULL && j<i-1){ // 另p等于i-1个节点 p = p->next; j++; } if (p==NULL){ // i值不合法 return false; } if (p->next==NULL){ // i-1个节点后没有节点 return false; } LNode *q = p->next; // 另q指向被删除节点 int e = q->data; //e为返回元素的值 p->next=q->next; // 将*q从链中剔除 free(q); // 释放节点存储空间 return e; } 指定节点的删除 bool DeleteNode(LNode *p){ /* 删除指定的节点 */ if (p==NULL){ return false; } LNode *q = p->next; // 令q指向*p的后继节点 p->data = p->next->data; //和后继节点交换数据域，此时p就相当于变成了逻辑意义上的下一个节点 p->next = q->next; // 再将p的下一个链接到q的下一个 free(q); //释放q return true; } 这于指定节点的插入，是同样的道理，依旧是运用了数据域内容的交换，实现了逻辑意义上的删除，同时时间复杂度为O(1)O(1)O(1) 按位查找 LNode *GetElem(LinkList L,int i){ if(i<0){ return NULL; } LNode *p; int j=0; p=L; while (p!=NULL && j<i){ // 循环找到第i个节点，上面的操作和插入一样 p=p->next; j++; } return p; } 基本与按位插入是一样的原理，只不过按位插入是循环到底i-1个节点，查找是循环到第i个节点。如果查找的节点刚为第一个的话，那么时间复杂度为O(1)O(1)O(1)，平均时间复杂度为O(n)O(n)O(n)。 按值查找 LNode *LocateElem(LinkList L,int e){ /* 按值查找 */ LNode *p = L->next; //令p等于头指针的下一个节点 while (p!=NULL && p->data !=e){ // 如果p的数据元素不等于查找值，继续下一个节点，直到满足 p=p->next; } return p; } 因为它是依次往后扫描寻找，当e再第n个位置的时候，那么就循环了n次，所以它的平均时间复杂度为O(1)O(1)O(1)。 单链表的长度 int Length(LinkList L){ int len=0; LNode *p = L; while (p->next!=NULL){ p=p->next; len++; } return len; } 因为单链表不具备随机访问的特性，是依次查询，所以它的平均时间复杂度为O(1)O(1)O(1)。 单链表的建立 如果有很多个数据元素，要把它们存入到一个单链表中。有两种方法可以实现，一种是尾插法，一种是头插法。 初始化一个单链表，每次取一个元素，插入到表尾/表头 尾插法 LinkList List_Tailnsert(LinkList L){ /* 尾插法 */ int x; // 设置要插入的数据 L = (LinkList)malloc(sizeof(LNode)); // 初始化空表 LNode *s,*r=L; // r为表为指针 scanf("%d",&x); // 输入节点的值 while (x!=9999) { s=(LNode *)malloc(sizeof(LNode)); //在r节点之后插入元素s s->data = x; r->next = s; r = s; // 保持r永远是最后一个指针 scanf("%d",&x); } r->next = NULL; // 表尾指针指向NULL return L; } 平均时间复杂度为O(n)O(n)O(n) 头插法 LinkList List_HeadInsert(LinkList L){ LNode *s; int x; L = (LinkList)malloc(sizeof(LNode)); //创建头节点 L->next = NULL; //初始化为空链表 scanf("%d",&x); //节点值 while (x!=9999){ s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; //将新节点的指针为头节点的下一个 L->next = s; // 令头节点的下一个变成新插入的节点 scanf("%d",&x); } } 链表-双链表 定义 单链表中，从表的任一节点出发，都可以找到其前驱结点，但需要O(n)O(n)O(n)的时间。那么可以在链表的每一个结点中设置两个指针，一个指向后继结点，另一个指向前驱结点，称为双链表 代码实现 双链表的实现 typedef struct DNode{ // 定义双链表结点类型 ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist; 带头节点的双链表 // 双链表 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct DNode{ int data; struct DNode *prior, *next; }DNode, *DLinklist; bool InitDLinklist(DLinklist L){ L=(DNode *)malloc(sizeof(DNode)); // 分配一个头结点 if (L==NULL){ // 内存不足，分配失败 return false; } L->prior = NULL; // 头节点的prior永远指向NULL L->next = NULL; //头节点之后的结点暂时指向空 return true; } void testDLinklist(){ DLinklist L; InitDLinklist(L); } int main(){ testDLinklist(); return 0; } 只是在单链表的基础上，多了一个前驱指针。用来指向上一个结点，剩下基本一样。要注意的是，头结点因为是第一个结点，所它的前驱指针永远是指向NULL的。 关于双链表的基本操作 代码实现 后插操作 bool InsertNextDNode(DNode *p, DNode *s){ if (p==NULL || s==NULL){ // 非法参数 return false; } s->next=p->next; // 令p的后继结点等于s的后继结点 if (p->next!=NULL){ // 判断是否为表尾，如果是表尾，那么p的下一结点是NULL p->next->prior = s; // 令p后继结点的前驱结点等s } s->prior = p; // s的前驱结点为p p->next = s; // p的后继结点为s return true; } 例如p结点的下一结点为k，这时要在p后面插入结点s。首先将p的下一个结点，也就是k，变成s的下一结点。在令k的前驱结点指向s，s的前驱结点指向p，p的下一个结点指向s。这就完成了在原先的p和k中间位置插入了结点s。 删除操作 bool DeleteNextDNode(DNode *p){ /* 删除p结点的后继结点 */ if (p==NULL){ // 验证非法参数 return false; } DNode *q = p->next; // 找到p的后继结点q if (q=NULL){ // p没有后继结点 return false; } p->next = q->next; // 令p的后继结点等于q的后继结点 if (q->next!=NULL){ // 判断q是不是最后一个结点 q->next->prior = p; // q的后继结点的前驱结点等于p } free(q); return true; } 销毁一个双链表 void DeleteDLinklist(DLinklist L){ /* 销毁一个双链表 */ while (L->next != NUll){ DeleteDLinklist(L); } free(L); L = NULL; } 遍历操作 void PrintDLinklist(DNode *p){ /* 遍历一个双链表 */ while (p!=NULL){ printf("%d",p->data); p = p->next; } } 没啥逻辑可说的，就是给定一个结点，然后对结点进行判断是否为NULL，满足循环条件进入循环，打印结点数据，然后将p指向给定结点的下一个结点，时间复杂度为O(n)O(n)O(n) 链表-循环链表 定义 单链表最后一个结点的指针为空指针，循环链表就是将这个空指针指向了头结点。使整个链表形成了一个环，首尾相接。 代码实现 循环单链表的实现 // 循环链表 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct LNode{ // 定义一个单链表结点类型 int data; struct LNode *next; }LNode, *LinkList; bool InitList(LinkList L){ /* 初始化一个循环单链表 */ L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点 if (L==NULL){ return false; } L->next = L; // 将头节点的后继结点指向头结点 return true; } int main(){ LinkList L; InitList(L); return 0; } 循环双链表的实现 typedef struct DNode{ int data; struct DNode *prior, *next; }DNode, *DLinkList; bool InitDLinkList(DLinkList L){ /* 初始化循环链表 */ L = (DNode *)malloc(sizeof(DNode)); if (L==NULL){ return false; } L->prior = L; // 头结点的前驱结点指向头结点 L->next = L; // 头结点的后继结点指向头结点 } int main(){ DLinkList L; InitDLinkList(L); return 0; } 链表-静态链表 定义 设置一个游标，游标是数组中指示数组单元地址的下标值。它指示表中下一个元素在数组中的存储地址（数组下标）。虽然是用数组的方式存储表中的元素，但是插入和删除操作，并不需要移动表中元素，只需要修改游标。 代码实现 静态链表的实现 // 静态链表 #include <stdio.h> #include <stdlib.h> #define MaxSize 10 // 静态链表的最大长度 typedef struct SNode{ int data; // 存储的数据元素 int next; // 下一个元素的数组下标 }SNode, SLinkList[MaxSize]; void InitSLinkList(SLinkList L){ L = (SNode *)malloc(MaxSize*sizeof(SNode)); // 申请一片地址 for (int i=0; i<MaxSize; i++){ L[i].data = 0; // 初始化每一个数组元素 L[i].next = i+1; //初始化每一个游标 } L[MaxSize-1].next = -1; // 设置最后一个游标为-1代表表尾 } void testSLinkList(){ SLinkList L; InitSLinkList(L); } int main(){ testSLinkList(); return 0; }