💟作者简介：大家好，我是锡兰Ceylan_，可以叫我CC ❣️    
📝个人主页：锡兰Ceylan_的博客
🏆博主信息：平凡的大一学生，有着不平凡的梦

        专栏

• 【备战蓝桥，冲击省一】
• 【开卷数据结构】

⚡希望大家多多支持😘一起进步~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努努力💪​

🌺线性表的定义

线性表：线性表是由n ( n≥0 ) 个数据特性相同的元素构成的有限序列。n是线性表的表长，当 n=0时线性表是一个空表。若用 L 来命名线性表，则其一般表达式为

L  =  (a1，a2，...... ，an)

图像：

a1是唯一的【第一个】数据元素，又称表头元素。an是唯一的【最后一个】数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后续。

以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

🌺线性表的特点

从线性表的图像和表达式中可以很明显的看出线性表的特点，那就是

1. 存在唯一的“第一元素”，没有前驱；
2. 除第一元素外，其它元素均有唯一的＂前驱＂。
3. 存在唯一的“最后元素”，没有后继；
4. 除最后元素外，其它元素均有唯一的＂后继＂；

🌺 顺序表

        线性表的顺序存储又称为顺序表，它用一组地址连续的存储单元依次存放线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。

第1个元素存储在线性表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素。当我们知道顺序表的第一位元素的地址时，就很容易就可以推理出剩余元素的地址，因此顺序表是一种随机存取的存储结构。

顺序表的特点：表中元素的逻辑顺序与其物理顺序相同

 假设线性表L存储的起始位置是 LOC（A），sizeof（ElemType）是每个数组元素所占用的存储空间的大小，那么线性表L的顺序存储如下图所示。

        每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数。因此，线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

看到这里不知道大家有没有感觉很熟悉，似曾相识。没错，我们的老朋友——数组也是一种随机存取的存储结构。因此，通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

注意：线性表中元素的位序是从【1】开始的，而数组中元素的下标是从【0】开始的.

🌷实现原理

首先我们需要定义一下顺序表的长度，也就是最大有多少个元素。我们采用【define】来确定长度，因为使用【define】可以更方便的进行对长度的修改。

#difine        MAXSIZE        ****        //最大长度

下面，我们用结构体，定义一个新的数据类型。

typedef struct{   ElemType *elem;  //存储空间基地址    int length;     //当前长度}SqList;     //结构类型为SqList

第一数据域：

在结构体中包含了两个数据域，第一个数据域是elem，很明显，elem是一个指针域，它指向了ElemType类型（在真正实现时，是本来的数据类型）

ElemType：它是element type（“元素的类型”）的简化体

【ElemType *elem】代表着连续空间的首地址，也称基地址，elem类似于数组的名字，它也可以当作数组名字使用。

第二数据域：

第二数据域length表示线性表的数据元素的长度

🌷顺序表的初始化

顺序表的初始化就是建立一个新的空的顺序表

🔺实现原理

1️⃣为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。

2️⃣将表的当前长度设为0。

💬 代码演示

Status InitList(SqList &L){//构造一个空的顺序表L L.elem=new ElemType[MAXSIZE];//为顺序表分配一个大小为MAXSIZE的数组空间  if(!L. elem) exit(OVERFLOW);//存储分配失败退出 L.length=0;   //空表长度为0 return OK; }

🌷顺序表的取值

🔺实现原理

1️⃣判断指定位置是否合理，若不合理，则返回 ERROR。

2️⃣若i值合理，则将第i个元素L.elem[i-1]赋值给参数e，通过e返回第i个数据元素的传值。

💬 代码演示

Status GetElem(SqListL, int i,ElemType &e){if(iL. length) //判断是否合理 return ERROR;e=L. elem[i-1];    //elem[i-1]存储第i个数据元素 return OK;}

🌷顺序表的查找

🔺实现原理

1️⃣从第一个元素开始，一个一个与e相比较，若查找成功，返回该元素在表中的位置序号。

2️⃣若查找失败，则返回0。

💬 代码演示

int LocateElem(SqList L,ElemType e){//在顺序表1中查找值为e的数据元素，返回其序号for(i=0;i<L. length;i++){if(L. elem[i]==e) return i+1;}return 0; }

🌷顺序表的插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使得长度为n的线性表变成长度为n+1的线性表。

❓那么问题来了，应该怎么实现呢？

在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，为了在线性表的第i个位置上插入一个数据元素，则需将第i个至最后一个数据元素依次向后移动一个位置。

🔺实现原理

1️⃣判断插入位置i是否合法(i值的合法范围是1≤i≤n+1)，若不合法则返回ERROR。

2️⃣判断顺序表的存储空间是否已满，若满则返回ERROR。

3️⃣将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i=n+1时无需移动）

4️⃣将要插入的新元素e放入第i个位置。

5️⃣表长加一。

🔑空间状态

💬 代码演示

Status ListInsert(SqList &L, int i,ElemType e){//在顺序表L中第i个位置插入新的元素e，i值的合法范围是1≤i≤L. length+1if((iL. length+1)) return ERROR;//i值不合法if(L. length==MAXSIZE) return ERROR;//当前存储空间已满for(j=L. length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=e;++L. length;return OK;}

🌷顺序表的删除

和插入同理，在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，为了在线性表的第i个位置上删除一个数据元素，则需将第i个至最后一个数据元素依次向前移动一个位置。

🔺实现原理

1️⃣判断插入位置i是否合法(i值的合法范围是1≤i≤n+1)，若不合法则返回ERROR。

2️⃣将第i+1个至第n个元素依次向前移动一个位置。

3️⃣表长减一。

🔑空间状态

💬 代码演示

Status ListDelete(SqList &L, int i){//在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.1ength if(iL. length)) return ERROR;//i值不合法for(j=i;j<=L. length-1;j++)L,elem[j-1]=L,elem[j];//被删除元素之后的元素前移--L. length;//表长减1return OK;}

🌷顺序表的优缺点

顺序表的内存连续，支持随机访问,可以高效的按下标进行操作，可以很方便的查找表中任一元素。

然而，通过上文不难发现，在做插入或删除操作时，需移动大量元素。当表中数据元素个数较多且变化较大时，操作过程相对复杂。这些问题，可以通过线性表的另一种表示方法——链式存储结构来解决。

🌺链表

🌷链表的定义

线性表的链式存储又称为单链表，其特点是用一组任意的存储单元来存储线性表的数据元素。

为了表示每个数据元素ai与其后续数据元素ai+1之间的逻辑关系，a1除了存储自身的信息之外，还需要存储一个指向其后续内容的信息（一般为后续内容的地址）。这两部分信息组成数据元素ai的存储映像，称为结点。

​

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

typedef struct LNode//定义单链表结点类型 {ElemType data;//数据元素 struct LNode *next;//指向下一地址 }LNode, *LinkList;

🌷链表的存储方式

整个链表的存取必须从头指针开始进行，头指针指向链表的第一个结点的存储位置。同时由于最后一个元素没有直接后继，则单链表的最后一个结点的指针为空（NULL）

我们来想一想，如果用链表来存储【Ceylan】，它的逻辑状态是什么样的呢？​

首先应该需要一个头指针L，它指向第一个元素 'C'，通过 'C' 所在结点的信息，可以访问下一节点 'e' 所在位置，以此类推，就可以完整找到整个【Ceylan】

​

🌷单链表的初始化

单链表的初始化就是建立一个新的空的单链表。

🔺实现原理

1️⃣生成新结点作为头结点，用头指针L指向头结点

2️⃣头结点指向空

💬 代码演示

Status InilList(LinkList &L){//构建一个空的链表L L=new LNode;//生成新结点作为头结点，用头指针L指向头结点 L->next=NULL;//头结点指向空 return OK; }

🌷头插法建立单链表

🔺实现原理

1️⃣建立一个空表，生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的表头，也就是头结点之后

​

 💬 代码演示

void CreateList_H(LinkList &L,int n){L=new LNode;L->next=NULL; //先建立一个带头结点的空链表 for(int i=0;i>p->data;//输入p结点的数据 p->next=L->next;L->next=p;//将新结点*p插入到头结点之后 }} 

❗️注意：

因为每次插入都是在链表头部，所以应该逆位序输入数据。输入顺序和线性表中的逻辑顺序是相反的。

🌷尾插法建立单链表

🔺实现原理

1️⃣建立一个空表，生成新节点

2️⃣将数据存放到新节点的数据域中

3️⃣将新节点插入到当前链表的尾部

​💬 代码演示

void CreateList_R(LinkList &L,int n){L=new LNode;//先建立一个带头结点的空链表 r=L;//尾指针指向头结点 for(int i=0;i>p->data;//输入p结点的数据 p->next=NULL;r->next=p;//将新结点*p插入尾结点*r之后 r=p }} 

🌷按序号寻找结点值

🔺实现原理

1️⃣从第一个结点开始，顺指针next逐个向下搜索，直到找到第  i  个结点，

2️⃣若没有找到，返回最后一个指针域NULL

💬 代码演示

LNode *GetElem(LinkList L,int i){int j=1;//计数，初始为1 LNode *p=L->next;//头结点指针赋值给p if(i==0)return L;//若i为 0，返回头指针 if(i<1)return NULL;//若i无效，则返回 NULL while(p&&jnext;j++;}return p;//返回第 i 个结点的指针 } 

LNode *LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->data!=e)//从第一个结点开始查找数据域为 e 的结点 {p=p->next;}return p;//找到后返回该结点指针，否则返回NULL } 

p=GetElem(L,i-1)//查找插入位置的前驱结点 s->next=p->next;//新结点*s的指针域指向*p的后续结点p->next=s;//令结点*p的指针域指向新的插入的结点*s

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

s->next=p->next;     //将结点*插入到结点*p之后p->next->prior=s;s->prior=p;p->next=s;

p->next=q->next; //操作一q->next->prior=p;//操作二free(p);  //释放结点空间