数据结构笔记-2、线性表

2.1、线性表的定义和基本操作

如有侵权请联系删除。

2.1.1、线性表的定义：

​ 线性表是具有相同数据类型的 n (n>=0) 个数据元素的有限序列，其中 n 为表长，当 n = 0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为：
L = ( a 1 , a 2 , a 3 , . . . , a i , x i + 1 , . . . , a n ) L=(a_1,a_2,a_3,...,a_i,x_{i+1},...,a_n) L=(a1​,a2​,a3​,...,ai​,xi+1​,...,an​)
式中， a 1 a_1 a1​ 是唯一的“第一个元素”，又称表头元素； a n a_n an​ 是唯一的“最后一个元素”，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后驱。

​ 由此，线性表的特点是：

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中数据有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个数据。
  • 表中元素的数据类型都相同，这意味着每个元素都占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

2.1.2、线性表的操作：

​ 线性表的主要操作如下：

InitList(&L) ：初始化表。构造一个空的线性表。

Length(L) ：求表长。返回线性表 L 的长度，即 L 中数据元素的个数。

LocateElem(L,e) ：按值查找操作。在表 L 中查找具有给定关键字值的元素。

GetElem(L,i) ：按位查找操作。获取表 L 中第 i 个位置的元素的值。

ListInsert(&L,i,e) ：插入操作。在表 L 中的第 i 个位置上插入指定元素 e 。

ListDelete(&L,i,&e) ：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。

PrintList(L) ：输出操作。按前后顺序输出线性表 L 的所有元素值。

Empty(L) ：判空操作。若 L 为空表，则返回 true，否则返回 false。

DestroyList(&L) ：销毁操作。销毁线性表，并释放线性表 L 所占用的内存。

2.2、线性表的顺序表示：

2.2.1、顺序表的定义：

​ 线性表的顺序储存又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧跟着存储位置的是第 i + 1 个元素，称 i 为元素 a i a_i ai​ 在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与物理顺序相同。

​ 假设线性表 L 存储的起始地址为 LOC(A)，sizeof(ElemType) 是每个数据元素所占用内存空间的大小，则表 L 所对应的顺序存储如下图所示。

在这里插入图片描述

​ 通常用高级语言中的数组来描述线性表的顺序存储结构。

​ 假定线性表的元素类型为 ElemType ，则线性表的顺序存储类型描述为：

#define MaxSize 50					//定义线性表的最大长度
typedef struct {ElemType data[MaxSize];			//顺序表的元素int length;						//顺序表的当前长度
} SqList;							//顺序表的类型定义

​ 一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

​ 而在动态分配时，存储数组的空间实在程序执行过程中通过动态存储分配语句分配到，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表依次性地划分所有空间。

#define InitSize 100				//表长度的初始定义
typedef struct {ElemType *data;					//指示动态分配数组的指针int MaxSize,length;				//数组的最大容量和当前个数
} SeqList;							//动态分配数组顺序表定义

​ C语言初始动态分配语句为：

L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

​ 顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间 O(1) 内找到指定的元素。

​ 顺序表的存储密度高，每个结点只存储数据元素。

​ 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.2.2、顺序表上基本操作的实现：

（1）、插入操作：

​ 在顺序表 L 的第 i (1<= i <= L.Length+1) 个位置插入新元素 e 。若 i 的输入不合法，则返回 false ，表示插入失败；否则，将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 e ，顺序表长度增加 1，插入成功，返回 true。

#include "stdio.h"
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;int ListInsert(SqList *L,int i , int e);int main(){SqList L;L.length = 0;for (int i = 0; i < 9; i++){L.data[i] = i + 1;L.length += 1;}ListInsert(&L,4,10);for (int i = 0; i < L.length; i++){printf("%d,",L.data[i]);}printf("\n%d",L.length);return 0;
}//实现插入算法的主体函数
int ListInsert(SqList *L,int i , int e){if (i < 1 || i > L->length + 1)return 0;if (L->length >= MaxSize)return 0;for (int j = L->length;j >= i;j--)L->data[j] = L->data[j-1];L->data[i - 1] = e;L->length ++;return 1;
}

​ 注意：区别顺序表的为序和数组下标。

​ 最好情况：在表尾插入（i = n + 1），元素后移语句将不执行，时间复杂度为 O(1)。

​ 最坏情况：在表头插入（i = 1），元素后移语句将执行 n 次，时间复杂度为 O(n)。

​ 平均情况：假设 p i p_i pi​（ p i = 1 / ( n − 1 ) p_i=1/(n-1) pi​=1/(n−1)）是在第 i 个位置上插入一个结点的概率，则在长度为 n 的线性表中插入一个结点时，所需移动的结点平均次数为：
∑ i = 1 n + 1 p i ( n − i + 1 ) = ∑ i = 1 n + 1 1 n + 1 ( n − i + 1 ) = 1 n + 1 ∑ i = 1 n + 1 ( n − i + 1 ) = 1 n + 1 n ( n + 1 ) 2 = n 2 \sum_{i=1}^{n+1}p_i(n-i+1)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\frac{n}{2} i=1∑n+1​pi​(n−i+1)=i=1∑n+1​n+11​(n−i+1)=n+11​i=1∑n+1​(n−i+1)=n+11​2n(n+1)​=2n​
​ 因此，顺序表插入算法的平均时间复杂度为 O(n)

（2）、删除操作：

​ 删除顺序表 L 中第 i （1 <= i <= L.length）个位置的元素，用引用变量 e 返回。若 i 的输入不合法，则返回 false ；否则，将被删元素赋给引用变量 e ，并将 i + 1 个元素及其后的所有元素依次往前移动一个位置，返回 true。

#include "stdio.h"
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;int ListInsert(SqList *L,int i , int e);
int ListDelete(SqList *L,int i , int *e);int main(){SqList L;int e;L.length = 0;for (int i = 0; i < 9; i++){L.data[i] = i + 1;L.length += 1;}ListInsert(&L,4,10);ListDelete(&L,4,&e);for (int i = 0; i < L.length; i++){printf("%d,",L.data[i]);}printf("\n%d",e);return 0;
}int ListInsert(SqList *L,int i , int e){if (i < 1 || i > L->length + 1)return 0;if (L->length >= MaxSize)return 0;for (int j = L->length;j >= i;j--)L->data[j] = L->data[j-1];L->data[i - 1] = e;L->length ++;return 1;
}//实现删除算法的主体函数
int ListDelete(SqList *L,int i , int *e){if (i < 1 || i > L->length)return 0;*e = L->data[i-1];for (int j = i;j<L->length;j++)L->data[j-1] = L->data[j];L->length--;return 1;
}

​ 最好情况：删除表尾元素（即 i = n），无须移动元素，时间复杂度为 O(1)。

​ 最坏情况：删除表头元素（即 i = 1），需移动除表头元素以外的所有元素，时间复杂度为 O(n)。

​ 平均情况：假设 p i p_i pi​（ p i = 1 / n p_i=1/n pi​=1/n）是删除第 i 个位置上结点的概率，则在长度为 n 的线性表中删除一个结点时，所需移动结点的平均次数为：
∑ i = 1 n + 1 p i ( n − i ) = ∑ i = 1 n + 1 1 n + 1 ( n − i ) = 1 n ∑ i = 1 n + 1 ( n − i ) = 1 n n ( n − 1 ) 2 = n − 1 2 \sum_{i=1}^{n+1}p_i(n-i)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i)=\frac{1}{n}\sum_{i=1}^{n+1}(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2} i=1∑n+1​pi​(n−i)=i=1∑n+1​n+11​(n−i)=n1​i=1∑n+1​(n−i)=n1​2n(n−1)​=2n−1​
​ 因此，顺序表删除算法的平均时间复杂度为 O(n)。

​ 可见，顺序表中插入和删除操作的时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。如下图所示：

在这里插入图片描述

（3）、按值查找（顺序查找）

​ 在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序。

#include "stdio.h"
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;int ListInsert(SqList *L,int i , int e);
int ListDelete(SqList *L,int i , int *e);
int LocateElem(SqList *L,int e);int main(){SqList L;int e,index;L.length = 0;for (int i = 0; i < 9; i++){L.data[i] = i + 1;L.length += 1;}ListInsert(&L,4,10);ListDelete(&L,4,&e);for (int i = 0; i < L.length; i++){printf("%d,",L.data[i]);}printf("\n%d",e);index = LocateElem(&L,4);printf("\n%d",index);return 0;
}int ListInsert(SqList *L,int i , int e){if (i < 1 || i > L->length + 1)return 0;if (L->length >= MaxSize)return 0;for (int j = L->length;j >= i;j--)L->data[j] = L->data[j-1];L->data[i - 1] = e;L->length ++;return 1;
}int ListDelete(SqList *L,int i , int *e){if (i < 1 || i > L->length)return 0;*e = L->data[i-1];for (int j = i;j<L->length;j++)L->data[j-1] = L->data[j];L->length--;return 1;
}//实现按值查找算法的主体函数
int LocateElem(SqList *L,int e){int i;for (i = 0;i < L->length;i++)if (L->data[i] == e)return i + 1;return 0;
}

​ 最好情况：查找到元素在表头，仅需比较一次，时间复杂度为 O(1)。

​ 最坏情况：查找到元素在表尾（或不存在），需要比较 n 次，时间复杂度为 O(n)。

​ 平均情况：假设 p i p_i pi​（ p i = 1 / n p_i=1/n pi​=1/n）是查找到元素在第 i (1 <= i <L.length)个位置上的概率，则长度为 n 的线性表中查找值为 e 的元素所需比较多平均次数为 ：
∑ i = 1 n p i × i = ∑ n = 1 n 1 n × i = 1 n n ( n + 1 ) 2 = n + 1 2 \sum_{i=1}^{n}p_i\times i=\sum_{n=1}^{n}\frac{1}{n}\times i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2} i=1∑n​pi​×i=n=1∑n​n1​×i=n1​2n(n+1)​=2n+1​
​ 因此，顺序表按值查找算法的平均时间复杂度为 O(n)。

2.3、线性表的链式表示：

​ 链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过 “链”建立起元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

2.3.1、单链表的定义：

​ 线性表的链式存储又称单链表，它是指通过一组任意的存储单位来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需存放一个指向其后继的指针。单链表结点一般存放两个域，一个时 data 数据域，用于存放数据；另一个 next 为指针域，用于存放后继结点的地址。

​ 单链表中结点类型的描述如下：

typedef struct LNode {ElemType data;struct LNode *next;
}LNode,*LinkList;

​ 利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的接待你时，需要从头开始遍历，依次查找。

​ 通常用头指针来表示一个单链表，如单链表 L ，头指针为 NULL 时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，成为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点，如下图：
在这里插入图片描述

​ 头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点时带头节点的链表中的第一个结点，结点内通常不存储信息。

​ 引入头结点后，可以带来两个优点。

  1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
  2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

2.3.2、单链表上基本操作和实现：

1、采用头插法建立单链表：

​ 该方法从一个空表开始，生成新节点，并将读取到的数据存放到信结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后，如下图:

在这里插入图片描述

​ 头插法建立单链表的算法如下：

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);int main(){LinkList L,p;L = List_HeadInsert(L);p = L->next;while(p){printf("%d,",p->data);p = p->next;}return 0;
}//实现头插法建立链表的函数，输出结果是输入的逆序，输入1 2 3，输出结果是3，2，1
LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}

​ 采用头插法建立单链表时，读入数据的顺序与生成的链表的元素的顺序时相反的。每个结点插入的时间为 O(1)，设单链表长为 n ，则总时间复杂度为 O(n)。

2、采用尾插法建立单链表：

​ 头插法建立单链表的算法虽然简单，但生成的链表中节点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针 r ，使其始终指向当前链表的尾结点，如下图：

在这里插入图片描述

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);int main(){LinkList L,p;//头插法建立链表的函数调用
//    L = List_HeadInsert(L);//尾插法建立链表的函数调用L = List_TailInsert(L);p = L->next;while(p){printf("%d,",p->data);p = p->next;}return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}//实现尾插法建立链表的函数
LinkList List_TailInsert(LinkList L){int x;L = (LinkList)malloc(sizeof(LNode));LinkList s,r = L;scanf("%d",&x);while (x != 9999){s = (LinkList) malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}

3、按序号查找结点：

​ 在单链表中从第一个结点出发，顺时针 next 域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点指针域 NULL。

​ 按序号查找结点值的算法如下：

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);int main(){LinkList L,p;//头插法建立链表的函数调用
//    L = List_HeadInsert(L);//尾插法建立链表的函数调用L = List_TailInsert(L);p = L->next;while(p){printf("%d,",p->data);p = p->next;}LinkList target =  GetElem(L,4);printf("\n%d",target->data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L = (LinkList)malloc(sizeof(LNode));LinkList s,r = L;scanf("%d",&x);while (x != 9999){s = (LinkList) malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}//实现按序号查找结点算法的函数
LinkList GetElem(LinkList L,int i){if (i < 1)return NULL;int j = 1;LinkList p = L->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}

​ 按序号查找操作的时间复杂度为 O(n)。

4、按值查找表结点：

​ 从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值 e ，则返回该结点的指针；若整个单链表中没有这样的结点，则返回 NULL。

​ 按值查找表结点的算法如下：

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);int main(){LinkList L,p;//头插法建立链表的函数调用
//    L = List_HeadInsert(L);//尾插法建立链表的函数调用L = List_TailInsert(L);p = L->next;while(p){printf("%d,",p->data);p = p->next;}LinkList target =  GetElem(L,4);printf("\n%d",target->data);target = LocateElem(L,5);printf("\n%d",target->data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L = (LinkList)malloc(sizeof(LNode));LinkList s,r = L;scanf("%d",&x);while (x != 9999){s = (LinkList) malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i < 1)return NULL;int j = 1;LinkList p = L->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}//实现按值查找结点的函数如下
LinkList LocateElem(LinkList L,int e){LinkList p = L->next;while (p!=NULL && p->data != e)p = p->next;return p;
}

5、插入结点操作

通过查找到指定结点的前驱结点进行后插操作

​ 插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第 i - 1个结点，，再在其后插入新结点。

​ 算法先调用按序号查找算法 GetElem(L,i-1)，查找第 i - 1 个结点。假设返回的第 i - 1 个结点为 *p，然后令新结点 *s 的指针域指向 *p 的后继结点，再领结点 *p 的指针域指向新插入的结点 *s。如下图所示：

在这里插入图片描述

​ 实现插入结点的代码如下：

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);int main(){LinkList L,p;//头插法建立链表的函数调用
//    L = List_HeadInsert(L);//尾插法建立链表的函数调用L = List_TailInsert(L);L = PreInsert(L,5,99);p = L->next;while(p){printf("%d,",p->data);p = p->next;}LinkList target =  GetElem(L,4);printf("\n%d",target->data);target = LocateElem(L,5);printf("\n%d",target->data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L = (LinkList)malloc(sizeof(LNode));LinkList s,r = L;scanf("%d",&x);while (x != 9999){s = (LinkList) malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i < 1)return NULL;int j = 1;LinkList p = L->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}LinkList LocateElem(LinkList L,int e){LinkList p = L->next;while (p!=NULL && p->data != e)p = p->next;return p;
}//实现通过第 i 个数据的前驱结点进行插入的函数算法
LinkList PreInsert(LinkList L,int i,int e){                       //实现在第i个结点之后进行插入LinkList p,s;s = (LinkList) malloc(sizeof(LNode));p = GetElem(L,i-1);                                         //获取第i个结点的前驱结点s->data = e;s->next = p->next;p->next = s;return L;
}
扩展：对指定结点进行前插操作

​ 假设，我们想将结点 s 插入到 p 之前。那么则需要将 s 插到 p 的后面，然后交换 p->data 与 s->data 域，这样既可以满足了逻辑关系，又能使得时间复杂度为 O(1)。

​ 代码实现如下：

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);
LinkList backInsert(LinkList L,int i,int e);int main(){LinkList L,p;//头插法建立链表的函数调用
//    L = List_HeadInsert(L);//尾插法建立链表的函数调用L = List_TailInsert(L);L = backInsert(L,5,99);p = L->next;while(p){printf("%d,",p->data);p = p->next;}LinkList target =  GetElem(L,4);printf("\n%d",target->data);target = LocateElem(L,5);printf("\n%d",target->data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L = (LinkList)malloc(sizeof(LNode));LinkList s,r = L;scanf("%d",&x);while (x != 9999){s = (LinkList) malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i < 1)return NULL;int j = 1;LinkList p = L->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}LinkList LocateElem(LinkList L,int e){LinkList p = L->next;while (p!=NULL && p->data != e)p = p->next;return p;
}LinkList PreInsert(LinkList L,int i,int e){                       //实现在第i个结点之后进行插入LinkList p,s;s = (LinkList) malloc(sizeof(LNode));p = GetElem(L,i-1);                                         //获取第i个结点的前驱结点s->data = e;s->next = p->next;p->next = s;return L;
}//实现后插结点的函数主题如下
LinkList backInsert(LinkList L,int i,int e){LinkList p,s;int temp;s = (LinkList) malloc(sizeof(LNode));p = GetElem(L,i);                                         //获取第i个结点的前驱结点s->data = e;s->next = p->next;p->next = s;temp = p->data;p->data = s->data;s->data = temp;return L;
}

6、删除结点操作：

​ 删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性，后查找表中第 i - 1 个结点，即被删结点的前驱结点，再将其删除。如下图：

在这里插入图片描述

​ 代码实现如下：

#include "stdio.h"
#include "stdlib.h"
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);
LinkList backInsert(LinkList L,int i,int e);
LinkList DeleteNode(LinkList L,int i);int main(){LinkList L,p;L = List_TailInsert(L);p = L->next;L = DeleteNode(L,4);while(p){printf("%d,",p->data);p = p->next;}return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while (x!=9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L = (LinkList)malloc(sizeof(LNode));LinkList s,r = L;scanf("%d",&x);while (x != 9999){s = (LinkList) malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i < 1)return NULL;int j = 1;LinkList p = L->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}LinkList LocateElem(LinkList L,int e){LinkList p = L->next;while (p!=NULL && p->data != e)p = p->next;return p;
}LinkList PreInsert(LinkList L,int i,int e){                       //实现在第i个结点之后进行插入LinkList p,s;s = (LinkList) malloc(sizeof(LNode));p = GetElem(L,i-1);                                         //获取第i个结点的前驱结点s->data = e;s->next = p->next;p->next = s;return L;
}LinkList backInsert(LinkList L,int i,int e){LinkList p,s;int temp;s = (LinkList) malloc(sizeof(LNode));p = GetElem(L,i);                                         //获取第i个结点的前驱结点s->data = e;s->next = p->next;p->next = s;temp = p->data;p->data = s->data;s->data = temp;return L;
}//实现删除结点操作的函数的主体如下
LinkList DeleteNode(LinkList L,int i){LinkList p,q;int e;p = GetElem(L,i-1);q = p->next;p->next = q->next;printf("被删除结点的元素的数据为：%d\n",q->data);free(q);return L;
}

​ 和插入算法一样，该算法的主要时间也是耗费在查找操作上，时间复杂度为 O(n)。

7、求表长操作：

​ 求表长操作要求计算单链表数据结点，也就是不含头结点的结点的总个数，需要从第一个结点开始遍历，直到访问完所有的结点，因为比较简单，具体实现就不进行赘述了，不过需要注意：有的链表存在头结点，有的不存在，在计算的时候要做好相关的区分操作。

8、销毁整个表（我自己写的）

​ 不多解释，直接上源码：

void AllFree(LinkList L){LinkList p = L->next,r;while(p){r = p;p = p->next;free(r);}free(p);free(L);
}

2.3.3、双链表：

​ 单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为 O(1)，访问前驱结点的时间复杂度为 O(n)。

​ 为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针 prior 和 next ，分别指向其前驱和后继结点，如下图：

在这里插入图片描述

​ 双链表中结点类型的描述如下：

typedef struct DNode{ElemType data;struct DNode *prior,*next;
} Dnode,*DLinkList;

​ 双链表在单链表的结点中增加了一个指向前驱的 prior 指针，因此双链表中的按值查找和按位查找的操作与单链表相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对 prior 指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为 O(1)。

1、双链表的插入操作：

​ 在双链表中 p 所指的结点之后插入结点 *s ，其指针的变化过程如下图：

在这里插入图片描述

​ 插入操作的代码如下：

#include "stdio.h"
#include "stdlib.h"typedef struct DNode{int data;struct DNode *prior,*next;
} DNode,*DLinkList;DLinkList create(DLinkList DL);
DLinkList GetElem(DLinkList DL,int i);
DLinkList Insert(DLinkList DL,int i,int e);
void AllFree(DLinkList L);int main(){DLinkList DL,p;DL = create(DL);p = DL->next;while(p){printf("%d,",p->data);p = p->next;}puts("");DL = Insert(DL,3,10);p = DL->next;while(p){printf("%d,",p->data);p = p->next;}AllFree(DL);return 0;
}DLinkList create(DLinkList DL){int x;DL = (DLinkList)malloc(sizeof(DNode));DLinkList s,r = DL;scanf("%d",&x);while (x != 9999){s = (DLinkList) malloc(sizeof(DNode));s->data = x;r->next = s;r->next->prior = r;r = s;scanf("%d",&x);}r->next = NULL;return DL;
}DLinkList GetElem(DLinkList DL,int i){if (i < 1)return NULL;int j = 1;DLinkList p = DL->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}//实现插入操作的函数主体如下
DLinkList Insert(DLinkList DL,int i,int e){DLinkList s,p;s = (DLinkList) malloc(sizeof(DNode));p = GetElem(DL,i-1);s->data = e;s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return DL;
}void AllFree(DLinkList DL){DLinkList p = DL->next,r;while(p){r = p;p = p->next;free(r);}free(p);free(DL);
}

2、双链表的删除操作：

​ 删除双链表的结点 *p 的后继结点 *q ，指针变化过程如下图：

在这里插入图片描述

​ 删除操作的代码如下：

#include "stdio.h"
#include "stdlib.h"typedef struct DNode{int data;struct DNode *prior,*next;
} DNode,*DLinkList;DLinkList create(DLinkList DL);
DLinkList GetElem(DLinkList DL,int i);
DLinkList Insert(DLinkList DL,int i,int e);
DLinkList Delete(DLinkList DL,int i);
void AllFree(DLinkList L);int main(){DLinkList DL,p;DL = create(DL);p = DL->next;while(p){printf("%d,",p->data);p = p->next;}puts("");DL = Insert(DL,3,10);p = DL->next;while(p){printf("%d,",p->data);p = p->next;}puts("");DL = Delete(DL,3);p = DL->next;while(p){printf("%d,",p->data);p = p->next;}AllFree(DL);return 0;
}DLinkList create(DLinkList DL){int x;DL = (DLinkList)malloc(sizeof(DNode));DLinkList s,r = DL;scanf("%d",&x);while (x != 9999){s = (DLinkList) malloc(sizeof(DNode));s->data = x;r->next = s;r->next->prior = r;r = s;scanf("%d",&x);}r->next = NULL;return DL;
}DLinkList GetElem(DLinkList DL,int i){if (i < 1)return NULL;int j = 1;DLinkList p = DL->next;while(p != NULL && j < i){p = p->next;j ++;}return p;
}DLinkList Insert(DLinkList DL,int i,int e){DLinkList s,p;s = (DLinkList) malloc(sizeof(DNode));p = GetElem(DL,i-1);s->data = e;s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return DL;
}//实现删除结点的函数的主体
DLinkList Delete(DLinkList DL,int i){DLinkList p,q;q = GetElem(DL,i);p = q->prior;p->next = q->next;q->next->prior = p;free(q);return DL;
}void AllFree(DLinkList DL){DLinkList p = DL->next,r;while(p){r = p;p = p->next;free(r);}free(p);free(DL);
}

2.3.4、循环链表：

1、循环单链表：

​ 循环单链表和单链表的区别在于，表中最后一个结点的指针不是 NULL ，而改为指向头结点，从而整个链表形成一个环，如下图：

在这里插入图片描述

​ 在循环单链表中，表尾结点的 next 域指向 L ，故表中没有指针域为 NULL 的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

​ 循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作在表尾进行，则执行的操作不同，以让单链表继续保持循环的特性。当然，正因为循环单链表是一个环，因此在任何一个位址上的插入和删除操作都是等价的，无需判断是否是表尾。

​ 在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对循环链表不设头指针仅设尾指针，以使得操作效率更高。其原因是，若设的是头指针，对在表尾插入元素需要 O(n) 的时间复杂度，而若设的是尾指针 r ，r->next 即为头指针，对在表头或表尾插入元素都只需要 O(1) 的时间复杂度。

2、循环双链表：

​ 由循环单链表的定义不难退出寻你换双链表。不同的是在循环双链表中，头结点的 prior 指针还要指向表尾结点，如下图：

在这里插入图片描述

​ 在循环双链表 L 中，某节点 *p 为尾结点时，p->next == L ；当循环双链表为空表时，其头结点的prior 域和 next 域都等于 L 。

2.3.5、静态链表：

​ 静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和 指针域 next ，与之前的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一段连续的内存空间。

​ 静态链表和单链表的对应关系如下。

在这里插入图片描述

​ 静态链表结构类型的描述如下：

#define MaxSize 50
typedef struct {ElemType data;int next;
}SLinkList[MaxSize];

​ 静态链表以 next == 1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语言中，这是一种非常巧妙的设计方法。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/351681.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

爬虫初学篇

爬虫初学篇

初次学习爬虫&#xff0c;知识笔记小想 目录&#x1f31f; 一、&#x1f349;基础知识二、&#x1f349;http协议&#xff1a;三、&#x1f349;解析网页(1) xpath的用法&#xff1a;(2) bs4解析器的解释&#xff1a;(3) python字符编码的错误&#xff1a;(4) 正则表达式&#…
阅读更多...
第零篇——数学到底应该怎么学？

第零篇——数学到底应该怎么学？

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华 一、背景介绍 宏观讲解数学定位&#xff0c;数学学习方式方法&#xff0c;再次详细学习…
阅读更多...
Golang | Leetcode Golang题解之第160题相交链表

Golang | Leetcode Golang题解之第160题相交链表

题目&#xff1a; 题解&#xff1a; func getIntersectionNode(headA, headB *ListNode) *ListNode {if headA nil || headB nil {return nil}pa, pb : headA, headBfor pa ! pb {if pa nil {pa headB} else {pa pa.Next}if pb nil {pb headA} else {pb pb.Next}}retu…
阅读更多...
单调栈（续）、由斐波那契数列讲述矩阵快速降幂技巧

单调栈（续）、由斐波那契数列讲述矩阵快速降幂技巧

在这里先接上一篇文章单调栈&#xff0c;这里还有单调栈的一道题 题目一&#xff08;单调栈续&#xff09; 给定一个数组arr&#xff0c; 返回所有子数组最小值的累加和 就是一个数组&#xff0c;有很多的子数组&#xff0c;每个数组肯定有一个最小值&#xff0c;要把所有子…
阅读更多...
【stm32-新建工程】

【stm32-新建工程】

stm32-新建工程 ■ 下载相关STM32Cube官方固件包&#xff08;F1&#xff0c;F4&#xff0c;F7&#xff0c;H7&#xff09;■ 1. ST官方搜索STM32Cube■ 2. 搜索 STM32Cube■ 3. 点击获取软件■ 4. 选择对应的版本下载■ 5. 输入账号信息■ 6. 出现下载弹框&#xff0c;等待下载…
阅读更多...
MySQL 使用 MyFlash 快速恢复误删除、误修改数据

MySQL 使用 MyFlash 快速恢复误删除、误修改数据

一、MyFlash MyFlash 是由美团点评公司技术工程部开发并维护的一个开源工具&#xff0c;主要用于MySQL数据库的DML操作的回滚。这个工具通过解析binlog日志&#xff0c;帮助用户高效、方便地进行数据恢复。MyFlash的优势在于它提供了更多的过滤选项&#xff0c;使得回滚操作变…
阅读更多...
云计算在保险行业的应用：太平财险团财险理赔新核心业务系统案例

云计算在保险行业的应用：太平财险团财险理赔新核心业务系统案例

随着科技的快速发展&#xff0c;云计算技术已经成为推动保险行业数字化转型的重要力量。云计算为保险公司提供了弹性、可扩展的计算资源&#xff0c;使其能够灵活应对业务高峰和低谷&#xff0c;提高业务运营效率和风控水平。太平财险与太平金科联合开发的“团财险理赔新核心业…
阅读更多...
LLVM 中 的 pass 及其管理机制

LLVM 中 的 pass 及其管理机制

概述 LLVM 编译器框架的核心概念是任务调用和执行 编译器开发者将IR分解为不同的处理对象&#xff0c;并将其处理过程实现为单独的pass类型。在编译器初始化&#xff0c;pass被实例化&#xff0c;并被添加到pass管理中 pass 管理器(pass manager) 以流水线的方式将各个独立的…
阅读更多...
HCS-华为云Stack-容器网络

HCS-华为云Stack-容器网络

HCS-华为云Stack-容器网络 容器隧道overlay VPC网络
阅读更多...
vue3轮播图怎么做

vue3轮播图怎么做

先看效果 实现代码 <n-carouseleffect"card"dot-type"line"draggable:autoplay"!isHovered":current-index"currentIndex"prev-slide-style"transform: translateX(-150%) translateZ(-450px);opacity:1"next-slide-st…
阅读更多...
结构设计模式 - 桥接设计模式 - JAVA

结构设计模式 - 桥接设计模式 - JAVA

桥接设计模式 一. 介绍二. 桥接模式示例2.1 定义实现部分和具体实现2.2 定义抽象部分和细化抽象部分2.3 测试2.4 解释 三. 结论 前言 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 一.…
阅读更多...
windows11 x64 23H2 企业纯净版2024.6.16

windows11 x64 23H2 企业纯净版2024.6.16

闲来无事试安装了下da_nao_yan的 【6月12日更新】Windows11 22631.3737企业版 23H2 自用优化版 &#xff08;原版地址&#xff1a;https://bbs.pcbeta.com/viewthread-1985546-1-1.html&#xff09;&#xff0c;感觉比原版流畅多了&#xff0c;重新按照自己习惯封装了下&#x…
阅读更多...
使用 C# 进行面向对象编程：第 9 部分

使用 C# 进行面向对象编程：第 9 部分

使用 OOP 的用户活动日志 应用程序背后的关键概念 在这一部分中&#xff0c;我们将使用之前学到的一些 OOP 概念。我们将创建一个小型应用程序。在继续之前&#xff0c;请阅读我的文章user-activity-log-using-C-Sharp-with-sql-server/。在本课程中&#xff0c;我们将再次使…
阅读更多...
LabVIEW进行负载测试

LabVIEW进行负载测试

本文介绍了如何使用LabVIEW进行负载测试&#xff0c;通过一个具体案例详细讲解了测试系统的组成、工作原理和实现方法。系统采用先进的硬件和软件架构&#xff0c;结合LabVIEW的强大功能&#xff0c;成功实现了对设备的高效负载测试&#xff0c;确保了系统的可靠性和性能。 项…
阅读更多...
拥抱开源，构建未来：王嘉树与 TDengine 的开源之旅

拥抱开源，构建未来：王嘉树与 TDengine 的开源之旅

在当代的技术浪潮中&#xff0c;开源文化不仅催生了无数创新技术&#xff0c;也为广大技术爱好者提供了一个展示才华、相互学习的平台。我们今天采访到的这位北京邮电大学电子工程学院的研究生&#xff0c;就是在这样的背景下&#xff0c;通过开源活动不断探索、学习并实现自我…
阅读更多...
2024年汉字小达人活动还有4个多月开赛：来做18道历年选择题备考吧

2024年汉字小达人活动还有4个多月开赛：来做18道历年选择题备考吧

结合最近几年的活动安排&#xff0c;预计2024年第11届汉字小达人比赛还有4个多月就启动&#xff0c;那么孩子们如何利用这段时间有条不紊地准备汉字小达人比赛呢&#xff1f; 我的建议是充分利用即将到来的暑假&#xff1a;①把小学1-5年级的语文课本上的知识点熟悉&#xff0…
阅读更多...
Docker 安装 MySQL5.7 和 MySQL8

Docker 安装 MySQL5.7 和 MySQL8

文章目录 安装 MySQL5.7拉取镜像前期准备启动容器 安装MySQL8.0拉取镜像查看镜像前期准备启动容器 安装 MySQL5.7 拉取镜像 docker pull mysql:5.7拉下来镜像后 执行 docker images 此时我们已经有这个镜像了。 前期准备 在根目录下创建 app &#xff0c; 在 app 目录下创建…
阅读更多...
蚂蚁SEO的蜘蛛对网页收录有帮助吗 ？

蚂蚁SEO的蜘蛛对网页收录有帮助吗 ？

网页蜘蛛对网站收录有着至关重要的帮助。在深入探讨这一话题之前&#xff0c;我们首先需要了解网页蜘蛛的工作原理及其在互联网生态系统中的角色。 网页蜘蛛&#xff0c;也被称为网络爬虫或网络机器人&#xff0c;是搜索引擎的核心组成部分。它们按照特定的算法和规则&#xff…
阅读更多...
力扣231. 2 的幂（位运算）

力扣231. 2 的幂（位运算）

Problem: 231. 2 的幂 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.若为0和负数则直接返回false&#xff1b; 2.利用一个标志数mask令其为一&#xff0c;不断的算术左移同时和n做与&#xff08;&&#xff09;运算&#xff0c;统计n中二进制位为1的个数&a…
阅读更多...
Java | Leetcode Java题解之第155题最小栈

Java | Leetcode Java题解之第155题最小栈

题目&#xff1a; 题解&#xff1a; class MinStack {Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {xStack new LinkedList<Integer>();minStack new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023