【线性表，线性表中的顺序表和链表】
目录
- 1、线性表的定义和基本操作
- 1.1、线性表的定义
- 1.2、线性表的基本操作
- 2、顺序表和链表的比较
- 2.1、顺序表
- 2.1.1、顺序表的定义和特点
- 2.1.2、顺序表的实现
- （1）顺序表的静态分配：
- （2）顺序表的动态分配
- 2.1.3、顺序表的基本操作：
- （1）插入操作
- （2）删除操作
- （3）按位查找
- （4）按值查找
- 2.2、链表
- 2.2.1、链表的定义及特点
- 2.2.2、链表的实现方式
- （1）带头结点
- （2）不带头结点：
- 2.2.3、单链表的基本操作
- （1）单链表的插入
- （2）指定结点的后插操作
- （3）指定结点的前插操作
- （4）单链表的删除
- 1）按位序删除结点
- 2）指定结点的删除
- （5）单链表的查找
- 1）按位查找
- 2）按值查找
- （6）求单链表的长度
- （7）单链表的建立
- 1）尾插法建立单链表
- 2）头插法建立单链表
- 3）链表的逆置
- 2.2.4、双链表
- 2.2.4.1、双链表的初始化（带头结点）
- 2.2.4.2、双链表的插入（后插）
- 2.2.4.3、双链表的删除（后删）和销毁
- 2.2.4.4、双链表的遍历
- 1）前向遍历
- 2）后向遍历
- 2.2.5、循环链表
- 2.2.5.1、循环单链表
- 2.2.5.2、循环双链表
- 2.2.5.3、循环链表的插入
- 2.2.5.4、循环链表的删除
- 2.2.6、静态链表
- 2.2.6.1、静态链表的定义
- 2.3、顺序表和链表的比较
1、线性表的定义和基本操作
1.1、线性表的定义
线性表是具有相同数据类型的n（n>0）个数据元素的有限序列。
其中n为表长，当n=0时，线性表是一个空表，若用L命名线性表，则其一般表示为：
特点：
- 存在唯一的第一个元素；
- 存在唯一的最后一个元素；
- 除第一个元素外，每个元素均只有一个直接前驱；
- 除最后一个元素外，每个元素均只有一个直接后继；
【直接前驱】：指在该序列中位于其前面且紧邻的元素；
【直接后继】：指在该序列中位于其后面且紧邻的元素。
例如：在一个整数数组[1，5，8，10，49]中，元素8的直接前驱为5，直接后继为10。
1.2、线性表的基本操作
- InitList(&L)：初始化表，构造一个空的线性表L，分配内存空间；
- DestroyList(&L)：销毁操作，销毁线性表，并释放线性表L所占用的空间；
- ListInsert(&L;i,e)：插入操作，在线性表L中的第i个位置上插入指定元素e；
- ListDelete(&L;i,&e)：删除操作，删除线性表L中第i个位置处的元素，并用e返回删除的元素；
- LocateElem(L,e)：按值查找操作，在表L中查找具有给定关键字值的元素；
- GetElem(L,i)：按位查找操作，获取表L中第i个位置上的元素的值；
- Length(L)：求表长，返回线性表L的长度，即L中数据元素的个数；
- PrintList(L)：输出操作，按照前后顺序输出线性表L中的所有元素值；
- Empty(L)：判空操作，若L为空表，则返回为true，否则返回false。
发现在上述操作中，创销增删时传入的是参数的引用，其余操作传入的是参数，涉及到了传值调用和传址调用，如下：
1.传值调用
#include void test(int x) { x = 1024; printf("test函数内部 x = %d\n",x); } int main() { int x = 1; printf("调用test前 x = %d\n", x); test(x); printf("调用test后 x = %d\n", x); return 0; }程序输出结果为：
2.传址调用
#include void test(int &x) { x = 1024; printf("test函数内部 x = %d\n",x); } int main() { int x = 1; printf("调用test前 x = %d\n", x); test(x); printf("调用test后 x = %d\n", x); return 0; }程序输出结果为：
2、顺序表和链表的比较
2.1、顺序表
2.1.1、顺序表的定义和特点
顺序表： 用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表的特点：
- 随机访问，即可以在O(1)时间内找到第i个元素；
- 存储密度高，每个节点只存储数据元素；
- 拓展容量不方便，即使使用动态分配的方式实现，拓展长的的时间复杂度也比较高，因为需要把数据复制到新的区域；
- 插入删除操作不方便，需要移动大量的元素，时间复杂度为：O(n)。
2.1.2、顺序表的实现
顺序表的实现：顺序表的实现有静态分配和动态分配。
（1）顺序表的静态分配：
- 使用静态数组实现；
- 顺序表的表长刚开始确定后就无法再更改（存储空间是静态的）。
#include #define MaxSize 10 //定义表长最大值为10 using namespace std; typedef struct { int data[MaxSize];//用静态数组存放数据元素 int length;//顺序表的当前长度 }ArrayList;//顺序表的定义类型（静态分配方式） void initList(ArrayList &L) { for (int i = 0; i（2）顺序表的动态分配
#include #include//malloc,free的头文件 #define initsize 10 //默认是初始值 typedef struct{ int* data; int MaxSize;//顺序表的最大容量 int length;//顺序表的当前长度 }Seqlist; void initlist(Seqlist& L) { //用malloc函数申请一片连续的存储的空间 L.data = (int*)malloc(initsize * sizeof(int)); L.length = 0; L.MaxSize = initsize; } void increaseSize(Seqlist &L,int len) { int* p = L.data; L.data = (int*)malloc((L.MaxSize + len) * sizeof(int)); for (int i = 0; i2.1.3、顺序表的基本操作：
（1）插入操作
ListInsert(&L,i,e)：在第i个位置处插入指定元素e，平均时间复杂度为：O(n)
#define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; //用静态的数组存放数据 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 bool ListInsert(SqList &L, int i, int e){ if(iL.length+1) //判断i的范围是否有效 return false; if(L.length>=MaxSize) //当前存储空间已满，不能插入 return false; for(int j=L.length; j>=i; j--){ //将第i个元素及其之后的元素后移 L.data[j]=L.data[j-1]; } L.data[i-1]=e; //在位置i处放入e L.length++; //长度加1 return true; } int main(){ SqList L; //声明一个顺序表 InitList(L);//初始化顺序表 //...此处省略一些代码；插入几个元素 ListInsert(L,3,3); //再顺序表L的第三行插入3 return 0; }（2）删除操作
ListDelete(&L,i,&e)：删除表L中第i个位置处的元素，并用e返回删除元素的值，平均时间复杂度为：O(n)
#define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; // 删除顺序表i位置的数据并存入e bool ListDelete(SqList &L, int i, int &e) { if (i L.length) // 判断i的范围是否有效 return false; e = L.data[i-1]; // 将被删除的元素赋值给e for (int j = i; j（3）按位查找
GetElem(L，i)：获取顺序表L中第i个位置上的元素，平均时间复杂度为：O(1)
// 静态分配的按位查找 #define MaxSize 10 typedef struct { ElemType data[MaxSize]; int length; }SqList; ElemType GetElem(SqList L, int i) { return L.data[i-1]; }// 动态分配的按位查找 #define InitSize 10 typedef struct { ElemType *data; int MaxSize; int length; }SeqList; ElemType GetElem(SeqList L, int i) { return L.data[i-1]; }（4）按值查找
LocateElem（L，e）：在表L中查找具有给的那个关键字值的元素，平均时间复杂度为：O(n)
#define InitSize 10 //定义最大长度 typedef struct{ ElemTyp *data; //用静态的“数组”存放数据元素 int Length; //顺序表的当前长度 }SqList; //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SqList L, ElemType e){ for(int i=0; i ElemType data;//数据域 struct LNode *next;//指针域 }LNode, *LinkList; ElemType data; struct LNode* next; }LNode, * LinkList; //初始化一个单链表（带头结点） bool initList(LinkList& L) { L = (LNode*)malloc(sizeof(LNode));//头指针指向的结点，分配一个头结点（不存储数据） if (L == NULL) return false;//内存不足，分配失败 L-next = NULL;//头结点之后暂时还没有结点 return true; } void test() { LinkList L; initList(L); //... } //判断单链表是否为空（带头结点） bool Empty(LinkList L) { if (L->next == NULL) return true; else return false; }（2）不带头结点：
麻烦，对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用到不同的代码逻辑。
typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; //初始化一个空的单链表 bool InitList(LinkList &L){ L = NULL; //空表，暂时还没有任何结点 return true; } void test(){ LinkList L; //声明一个指向单链表的头指针 //初始化一个空表 InitList(L); ... } //判断单链表是否为空 bool Empty(LinkList L){ return (L==NULL) }2.2.3、单链表的基本操作
（1）单链表的插入
ListInsert(&L,i,e)： 在表L中第i个位置处插入一个元素e。找到第i-1个结点（前驱结点），将新结点插入其后，其中头结点可以看做第0个结点，故i=1时也适用。
平均时间复杂度为：O(n)
//带头结点的插入 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; //在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L, int i, ElemType e) { //判断i的合法性, i是位序号(从1开始) if(i //如果ilengh, p最后会等于NULL p = p-next; //p指向下一个结点 j++; } if (p==NULL) //如果p指针知道最后再往后就是NULL return false; //在第i-1个结点后插入新结点 LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点 s->data = e; s->next = p->next; p->next = s; //将结点s连到p后,后两步千万不能颠倒 return true; }不带头结点插入时，不存在第0个结点，因此！i = 1时，需要特殊处理：（插入删除）第1个元素时，需要更改头指针L；
typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; bool ListInsert(LinkList &L, int i, ElemType e) { if(i LNode *s = (LNode *)malloc(size of(LNode)); s-data =e; s->next =L; L=s; //头指针指向新结点 return true; } //i>1的情况与带头结点一样！唯一区别是j的初始值为1 LNode *p; //指针p指向当前扫描到的结点 int j=1; //当前p指向的是第几个结点 p = L; //L指向头结点，头结点是第0个结点（不存数据） //循环找到第i-1个结点 while(p!=NULL && j //如果ilengh, p最后会等于NULL p = p->next; //p指向下一个结点 j++; } if (p==NULL) //i值不合法 return false; //在第i-1个结点后插入新结点 LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点 s->data = e; s->next = p->next; p->next = s; return true; }（2）指定结点的后插操作
InsertNextNode(LNode *p, ElemType e);
给定一个结点p，在其后插入元素e，根据单链表的链表指针只能往后查找的逻辑关系，故给定一个结点p，p之后的结点我们可以知道，之前的就无法得知了。
typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; bool InsertNextNode(LNode *p, ElemType 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; } //平均时间复杂度 = O(1) //有了后插操作，那么在第i个位置上插入指定元素e的代码可以改成： bool ListInsert(LinkList &L, int i, ElemType e) { if(i //如果ilengh, p最后4鸟会等于NULL p = p-next; //p指向下一个结点 j++; } return InsertNextNode(p, e) }（3）指定结点的前插操作
设待插入结点为s，将s插入到结点p的前面，我们仍然可以将结点s插入到结点p之后，然后将p->data和s->data进行交换，这样既满足了逻辑关系，又能使得时间复杂度为O(n)。
//前插操作：在p结点之前插入元素e bool InsertPriorNode(LNode *p, ElenType e){ if(p==NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) //内存分配失败 return false; //重点来了！ s->next = p->next; p->next = s; //新结点s连到p之后 s->data = p->data; //将p中元素复制到s p->data = e; //p中元素覆盖为e return true; }（4）单链表的删除
1）按位序删除结点
ListDelete(&L,i,&e)：删除表L中第i个位置上的元素，并用e来返回删除元素的值；头结点视为第0个结点；
思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点
typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; bool ListDelete(LinkList &L, int i, ElenType &e){ if(i //如果ilengh, p最后会等于NULL p = p-next; //p指向下一个结点 j++; } if(p==NULL) return false; if(p->next == NULL) //第i-1个结点之后已无其他结点 return false; LNode *q = p->next; //令q指向被删除的结点 e = q->data; //用e返回被删除元素的值 p->next = q->next; //将*q结点从链中“断开” free(q) //释放结点的存储空间 return true; }2）指定结点的删除
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; //将*q结点从链中“断开” free(q); return true; } //时间复杂度 = O(1)（5）单链表的查找
1）按位查找
GetElem(L,i)：按位查找操作，获取表L中第i个位置上的元素
平均时间复杂度：O(n)
LNode * GetElem(LinkList L, int i){ if(i //循环找到第i个结点 p = p-next; j++; } return p; //返回p指针指向的值 } LNode *P = L-next; //p指向第一个结点 //从第一个结点开始查找数据域为e的结点 while(p!=NULL && p->data != e){ p = p->next; } return p; //找到后返回该结点指针，否则返回NULL }（6）求单链表的长度
Length(LinkList L)：计算单链表中数据结点的个数（不含头结点），需要从第一个结点开始顺序依次访问表中的每个结点；
平均时间复杂度：O(n)
int Length(LinkList L){ int len=0; //统计表长 LNode *p = L; while(p->next != NULL){ p = p->next; len++; } return len; }（7）单链表的建立
- 初始化一个单链表
- 每次去一个数据元素，插入到表尾或表头
1）尾插法建立单链表
平均时间复杂度：O(n)
思路：每次都将新结点插入到当前链表的末尾，所以必须增加一个尾指针r,使其始终指向当前链表的为结点
优点：生成的链表中结点的次序和输入数据的顺序会一致
// 使用尾插法建立单链表L LinkList List_TailInsert(LinkList &L){ int x; //设ElemType为整型int L = (LinkList)malloc(sizeof(LNode)); //建立头结点(初始化空表) LNode *s, *r = L; //r为表尾指针 scanf("%d", &x); //输入要插入的结点的值 while(x!=9999){ //输入9999表示结束 s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; //r指针指向新的表尾结点 scanf("%d", &x); } r->next = NULL; //尾结点指针置空 return L; }2）头插法建立单链表
平均时间复杂度：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){ //输入9999表结束 s = (LNode *)malloc(sizeof(LNode)); //创建新结点 s->data = x; s->next = L->next; L->next = s; //将新结点插入表中，L为头指针 scanf("%d", &x); } return L; }3）链表的逆置
算法思想：逆置链表初始为空，原表结点从原链表中依次删除，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的新的第一个结点，如此循环，直至原链表为空；
LNode *Inverse(LNode *L) { LNode *p, *q; p = L->next; //p指针指向第一个结点 L->next = NULL; //头结点指向NULL while (p != NULL){ q = p; p = p->next; q->next = L->next; L->next = q; } return L;2.2.4、双链表
对双链表中结点的描述：
//定义双链表结点类型 typedef struct DNode{ ElemType data;//定义数据域 struct DNode *prior, *next;//前驱指针和后继指针 }DNode,*DLinkList;2.2.4.1、双链表的初始化（带头结点）
#include typedef struct DNode { ElemType data; struct DNode* prior, * next; }DNode, *DLinkList; bool initlist(DLinkList &DL) { DL = (DNode*)malloc(sizeof(DNode));//分配一个结点 if (DL == NULL)//内存不足，分配失败 return false; DL->prior = NULL;//头结点的prior永远指向NULL DL->next = NULL;//头结点之后还没有结点 return true; } void testDLinkList() { //初始化双链表 DLinkList DL; initlist(DL); } //判断双链表是否为空 bool Empty(DLinkList DL) { if (DL->next == NULL)//判断头结点的next指针是否为空 return false; else return true; }2.2.4.2、双链表的插入（后插）
//将结点p插到结点s之后 bool InsertNextDNode(DNode *s, DNode *p){ if(p == NULL || s == NULL) return false; p->next = s->next; if(s->next != NULL)//s不是最后一个结点（s有后继结点） s->next->prior = p; p->prior = s; s->next = p; }2.2.4.3、双链表的删除（后删）和销毁
bool DeleteNextDNode(DNode *p){ if(p == NULL) return false; DNode *q = p->next; if(q == NULL) return false; p->next = q->next; if(q->next != NULL) q->next->prior = p; free(q); return true; } //销毁一个双链表 bool DestroyDLinkLIst(DLinkList &DL){ //循环释放每一个结点 while(DL->next !=NULL){ DeleteNextDNode(DL);//删除头结点的后继节点 free(DL);//释放头结点 DL = NULL;//头结点指向空 } }2.2.4.4、双链表的遍历
1）前向遍历
while(P != NULL){ //对结点p做相应处理，eg.打印 p = p->prior; }2）后向遍历
while(P != NULL){ //对结点p做相应处理，eg.打印 p = p->next; }注意：双链表不可以随机存取，按位查找和按值查找都只能用遍历的方式实现，时间复杂度为O(n)。
2.2.5、循环链表
2.2.5.1、循环单链表
最后一个结点的指针不是指向NULL而是指向头结点
typedef struct LNode{ ElemType data; struct LNode *next; }DNode, *Linklist; /初始化一个循环单链表 bool InitList(LinkList &L){ L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点 if(L==NULL) //内存不足，分配失败 return false; L->next = L; //头结点next指针指向头结点 return true; } //判断循环单链表是否为空（终止条件为p或p->next是否等于头指针） bool Empty(LinkList L){ if(L->next == L) return true; //为空 else return false; } //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L, LNode *p){ if(p->next == L) return true; else return false; }单链表和循环单链表的比较：
1. 单链表： 从一个结点出发，只能找到该结点后面的各个结点；对链表的操作大多都在头部或尾部；设立头指针，从头结点找到尾部得到时间复杂度为O(n)，即对表尾操作需要O(n)的时间复杂度。
2. 循环单链表： 从表中任一个结点出发，可以找到该表中所有其他结点；设立尾指针，从尾部找到头部的时间复杂度为O(1)，即对表头和表尾操作的时间复杂度都只需要O(1)的时间复杂度。
3. 循环单链表的优点： 从表中任一个结点出发，可以找到该表中所有其他结点；
2.2.5.2、循环双链表
表头结点的前驱结点prior指向表尾结点，表尾结点的后继结点next指向表头结点。
typedef struct DNode{ ElemType data; struct DNode *prior, *next; }DNode, *DLinklist; //初始化空的循环双链表 bool InitDLinkList(DLinklist &L){ L = (DNode *) malloc(sizeof(DNode)); //分配一个头结点 if(L==NULL) //内存不足，分配失败 return false; L->prior = L; //头结点的prior指向头结点 L->next = L; //头结点的next指向头结点 } void testDLinkList(){ //初始化循环单链表 DLinklist L; InitDLinkList(L); //... } //判断循环双链表是否为空 bool Empty(DLinklist L){ if(L->next == L) return true; else return false; } //判断结点p是否为循环双链表的表尾结点 bool isTail(DLinklist L, DNode *p){ if(p->next == L) return true; else return false; }2.2.5.3、循环链表的插入
bool InsertNextDNode(DNode *p, DNode *s){ s->next = p->next; p->next->prior = s; s->prior = p; p->next = s;2.2.5.4、循环链表的删除
//删除p的后继结点q p->next = q->next; q->next->prior = p; free(q);
2.2.6、静态链表
2.2.6.1、静态链表的定义
用数组的方式来描述线性表的链式存储结构：分配一整片连续的内存空间，各个结点集中安置，包括了数据元素和下一个结点的数组下标（游标）。
#define MaxSize 10 //静态链表的最大长度 struct Node{ //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标(游标) }; //用数组定义多个连续存放的结点 //相当于typedef struct Node SLinkList[MaxSize]; 重命名struct Node，用SLinkList定义“一个长度为MaxSize的Node型数组; void testSLinkList(){ struct Node a[MaxSize]; //数组a作为静态链表, 每一个数组元素的类型都是struct Node //... }或者是
#define MaxSize 10 //静态链表的最大长度 typedef struct{ //静态链表结构类型的定义 ELemType data; //存储数据元素 int next; //下一个元素的数组下标 }SLinkList[MaxSize]; void testSLinkList(){ SLinkList a; }2.3、顺序表和链表的比较
逻辑结构 存储结构 创建 销毁 增/删 查 顺序表 线性表 顺序存储 优点：支持随机存取，存储密度高 缺点：大片连续空间分配不方便，改变容量不方便 静态分配：需要预分配大片连续空间，若空间太小，拓展容量不方便，若太大又浪费内存资源；动态分配：可以改变容量，但是需要移动大量元素，时间代价高 对于静态数组，系统会自动回收；对于动态分配，需要手动进行free() 插入/删除元素需要将后续元素进行后移/前移，时间复杂度为O(n)，时间开销主要来自移动元素 按位查找：O(1)；按值查找：O(n)，若表内元素有序，则可以在O(log2n)时间内找到 链表 线性表 链式存储 优点：离散的小空间分配方便，改变容量方便 缺点：不可随机存取，存储密度低 只需要分配一个头结点或者声明一个头指针 利用后删从头结点依次删除后续结点，最后释放头结点 插入/删除元素只需要修改指针，时间复杂度为O(n)，时间开销主要来自查找目标元素 按位查找：O(n)；按值查找：O(n) 顺序表 链表 弹性（可扩容） 不嘻嘻 嘻嘻 增/删 不嘻嘻 嘻嘻 查 嘻嘻 不嘻嘻
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
