- 线性表是存储数据中具有一对一关系的一种存储结构。
- 注意这里的线性表指的是存储结构（顺序表、链表），而不是存取结构（栈、队列等）。存取结构也可以基于存储结构来实现，比如顺序栈、链栈
- 线性存储结构共同点是将数据按照顺序用一根线串联起来。
- 所存储的数据类型必须相同。
- 对于顺序表而言。每一个结点元素的类型都是相同的，因为需要通过索引来找到元素的位置，则每个结点元素的长度必须相同，符合相同结构体定义的数据才能被线性表的统一规则正确访问。
- 对于链表而言。链表对结点的访问依赖于指针而不依赖于索引，即是不依赖于结点的相同性。但归根结底，链表也是数据存储结构，对结点的访问终究是要访问到具体的数据。两个结点如果属于不同的结构体，那么通过结构体变量访问数据项的时候，不同的数据类型所占的长度也是不一样的，无法通过统一规则访问。所以链表也要求数据类型必须相同。
1 顺序表
- 通过元素的顺序存储来反映数据间的逻辑关系。
- 可以通过索引随机存取顺序表的元素。
- 索引访问的优势。定义顺序存储结构时，结点首地址与结点大小是已知的，借助于地址空间的连续性，拿到索引（偏移量）就可以精确计算出访问元素的位置。因此更适合查询或更新元素多的场景。时间复杂度O(1)
- 索引访问的不足。所有的插入和删除操作需要通过移动元素来实现，因为需要保证存储结构所定义的地址空间连续性，元素通过索引访问的正确性。移动元素是一个非常耗性能的操作。若顺序的长度为n，那么平均时间复杂度O(n/2)。
- 存储结构定义。
// 顺序表的存储结构定义 typedef struct { // 线性表存储空间地址 ElementType* elem;
// 线性表当前存放元素的个数int length;// 当前线性表的容量int listSize;// 约定每次扩容的增量int incrementSize;
}SqList;
- 常用操作注意项。- **初始化** -> 分配内存需要注意失败的情况。```c/* 01_顺序表——创建空表：没有元素，长度为0，默认容量和增量*/Status createList_Sq(SqList& sL, int initSize = LIST_INIT_SIZE, int incrementSize = LIST_INCREMENT){// 开辟顺序表存储空间sL.elem = (ElementType*)malloc(initSize * sizeof(ElementType));// 创建失败，返回错误码if (!sL.elem){return ERROR;}sL.length = 0;sL.listSize = initSize;sL.incrementSize = incrementSize;return OK;}
插入元素
/* 05_顺序表——插入元素：在指定索引 index 之前插入一个元素*/Status insertElem_Sq(SqList& sL, int index, ElementType elem){// 索引不合法if (index < 0){return ERROR;}// 是否进行扩容if (sL.length + 1 >= sL.listSize){sL.elem = (ElementType*)malloc((sL.listSize + (size_t)sL.incrementSize) * sizeof(ElementType));// 扩容失败if (!sL.elem){return ERROR;}sL.listSize += sL.incrementSize;}// 在末尾添加if (index >= sL.length){//sL.elem[sL.length] = elem;*(sL.elem + sL.length) = elem;}else{// 插入前从后往前移动元素，注意索引取值/*for (int i = sL.length - 1; i >= index; i--){sL.elem[i + 1] = sL.elem[i];}*/for (ElementType* p = sL.elem + sL.length + 1; p >= sL.elem + index; p--){*(p + 1) = *p;}//sL.elem[index] = elem;*(sL.elem + index) = elem;}// 不要忘记长度++sL.length;return OK;}
- 插入索引在当前长度范围外的定义。
- 注意判断是否达到扩容条件，以及扩容失败后的操作。
- 插入成功后不要忘记当前元素长度字段。
删除元素 -> 同插入。只是少了扩容条件，多了返回元素的功能性定义。
/* 08_顺序表——删除：删除指定索引的元素*/ElementType deleteElem_Sq(SqList& sL, int index){// 如果不在元素索引范围内if (index < 0 || index >= sL.length){return -1;}ElementType toDelete = *(sL.elem + index);// 数组方式/*for (int i = index; i < sL.length - 1; i++){sL.elem[i] = sL.elem[i + 1];}*/// 指针方式ElementType* p = sL.elem + index;ElementType* q = sL.elem + sL.length - 1;while (p < q){*p = *(p + 1);p++;}// 别忘记长度减一sL.length--;return toDelete;}
清空和销毁。
清空是置为初始化状态，存储结构定义还在。
/* 06_顺序表——清空*/Status clearList_Sq(SqList& sL){// 先清空数组中的值delete[] sL.elem;// 重新分配sL.elem = (ElementType*)malloc(LIST_INIT_SIZE * sizeof(ElementType));if (!sL.elem){return ERROR;}// 其余长度置为初始sL.length = 0;sL.listSize = LIST_INIT_SIZE;sL.incrementSize = LIST_INCREMENT;return OK;}
销毁需要释放空间。
/* 07_顺序表——销毁*/Status destroyList_Sq(SqList& sL){// 回收数组空间delete[] sL.elem;//free(sL.elem);// 其余控制元素置为0sL.length = 0;sL.listSize = 0;sL.incrementSize = 0;return OK;}
2 链表
- 通过链式存储来反映元素之间的一对一关系。
- 通过指针构成的链遍历链表的元素。
- 链式存储的优势。对于插入和删除操作，只需要针对插入/删除元素与其相邻的元素进行操作，不存在大量移动元素的耗性能的情景。
- 链式存储的不足。对于更新和查询操作，需要从表头指针开始向后访问，即是以遍历的方式进行顺序访问，访问不方便。
主要通过单链表来记录链式存储结构的定义和常用操作，再此基础上类比循环链表和双向链表。
2.1 单链表
- 存储结构定义
- 对于数据而言。数据是零散存储的，每个元素结点只需要维护该结点的元素。
- 对于数据间的一对一关系，需要指针进行维护。所以需定义指向当前元素结点类型的指针，完成对链的定义。
- 对于链表结构，初始访问地址需要一个指针，拿到它才能对该链表进行操作。这里将这个指针的存储位置不同，将单链表分为带头结点和不带头结点。
/ 定义单链表结点/ typedef struct SL_Node { // 存储的元素 ElementType data; // 指向下一个结点的指针 struct SL_Node next; }HNode, SL;
> <a name="58d31dee"></a>### 常用操作注意项<a name="465f8828"></a>#### 2.1.1 初始化操作- 带头结点。即是需要构造出一个头节点，并且返回或初始化该头节点的地址作为头指针。有两种方式创建头节点。- 通过指针的创建。由以上定义，SL指向该类型结点的指针。此处head即是**指向头结点类型的指针**。由于指针在定义的时候，我们是不知道该头指针的地址的，当它分配完内存后我们才能得知地址，涉及的操作需要**修改**指向头结点的**head指针的值**，我们必须将头指针作为**引用类型传入**，是得修改能对该变量生效。```c/* 01_单链表——初始化_带头结点*/Status initList_SLh(SL& head){// 指向头节点的指针head = (SL)malloc(sizeof(SL_Node));if (!head){return ERROR;}head->data = NULL;head->next = NULL;return OK;}
通过指向头节点的二级指针创建。通过以上指针方式创建的讲述，应该会更好理解指向结点的二级指针方式创建头结点。
/* 18_单链表——初始化_带头结点2*/Status initList_SLh2(HNode** hNode){*hNode = (HNode*)malloc(sizeof(SL_Node));if (!*hNode){return ERROR;}(*hNode)->data = NULL;(*hNode)->next = NULL;return OK;}
同顺序表，两种方式内存分配都需要考虑分配失败的情况。
- 不带头结点。即是需要初始化一个指向首元的指针，初始化时候没有元素，所以指针给一个NULL值即可。
/* 02_单链表——初始化_无头结点*/Status initList_SL(SL& sL){sL = NULL;return OK;}
- 不带头结点。即是需要初始化一个指向首元的指针，初始化时候没有元素，所以指针给一个NULL值即可。
2.1.2 查询、更新、求长度、遍历操作
需要从第一个元素依次往后查找。区分带头结点和不带头节点，这里举出求长度的操作。
带头结点。头指针指向的是头节点，首元是头节点的next域指向的结点。
/* 03_单链表——长度_带头结点*/int listLength_SLh(SL head){// 初始迭代长度int length = 0;// 指向头结点的变量SL p = head->next;while (p){length++;p = p->next;}return length;}
不带头节点。头指针指向的即是首元结点。
/* 04_单链表——长度_无头结点*/int listLength_SL(SL sL){int length = 0;// 从头指针开始迭代SL p = sL;while (p){length++;p = p->next;}return length;}
2.1.3 插入元素方式
这里采用批量插入方式作为说明，对应的单个元素插入方式即为后插法、前插法。 同样，插入元素需要判断内存分配结果。
1 尾插法
这里是用于批量建立的过程。 整个过程只需要两个指针（待插入元素的指针s；其插入后的前驱位置元素指针p）
- 类比为单个元素的后插法，与前插法比较，后插法不需要额外的指针。两个操作的顺序不可逆，可画图理解。
// 1. 将【待插入元素】指向【前驱元素】的后继s->next = p -> next;// 2. 将【前驱元素】指向【待插入元素】p->next = s;
带头结点
/* 07_单链表——尾插法建立_带头节点*/Status tailInsert_SLh(SL& head, ElementType *datas, int length){// 指针p存放上一个结点SL p = head;// 用于新建的结点SL s = NULL;for (int i = 0; i < length; i++){// 指针p，每次循环在最后一个结点指针域，进行结点创建s = (SL)malloc(sizeof(SL_Node));if (!s){return ERROR;}s->data = *(datas + i);s->next = NULL;// 新结点连接到上一个结点p->next = s;// 迭代p = s;s = s->next;}return OK;}
不带头结点
对于头指针的方法，需要判断是否为第一个元素。
- 因为插入元素需要保存上一个结点，不带头结点的链表，头指针无上一个结点，所以需要单独处理。 ```c / 08单链表——尾插法建立不带头节点/ Status tailInsert_SL(SL& sL, ElementType* datas, int length) { // 指针p，用来保存上一个结点 SL p = sL; // 指针s，用于创建新结点 SL s = NULL;
for (int i = 0; i < length; i++) { // 指针p，每次循环在最后一个结点指针域，进行结点创建 s = (SL)malloc(sizeof(SL_Node)); if (!s) {
return ERROR;
} s->data = *(datas + i); s->next = NULL; // 不为第一个结点时 if (i) {
// 将新节点连到p后面p->next = s;
} // 为第一个结点时s新创建的地址赋值给链表标识sL，以及上一个结点标识p else {
sL = s;
} // 新节点作为上一个结点 p = s; // 指针q，再移动到新结点创建位置 s = s->next; } return OK; } ```
2 头插法
同样，这里是用于批量建立过程。
- 下面两个方法是批量插入的方法，每一个插入的节点都是在头结点之后，即是head -> next，所以不需要额外的只针来保存该节点。如果是单个元素，则插入到指定位置前，需要从头找到前置节点。
- 将该方法类比为单个元素的前插法。
- 除了提供的插入元素指针s和插入位置的指针p，p向前找不能找到前置元素，需要从头找到p结点元素的前置元素。
- 前插操作的两个语句可逆，因为三个结点都有指针进行保存。
// 1. 找到p结点元素的前置结点// 头指针，指向头结点SL head;// 注意这里带头结点，从头结点开始;如果没有头结点，p为第一个元素的时候，需要特殊处理。SL q = head;while(q->next != p){q = q->next;}// 2. 找到q后即开始前插操作。两个语句顺序可逆。s->next = p;q->next = s;
带头结点
/* 09_单链表——头插法建立_带头结点*/Status headInsert_SLh(SL& head, ElementType* datas, int length){// 指针p，用作保存上一个创建的结点，使得头节点指向的新创建结点指向上一个结点。SL p = head;// 指针s，用于创建新的结点SL s = NULL;for (int i = 0; i < length; i++){// 每次通过头结点创建新结点s = (SL)malloc(sizeof(SL_Node));if (!s){return ERROR;}s->data = *(datas + i);// 元素接到头结点后head->next = s;// 第一个结点插入if (!i){// 第一个结点即为表尾结点s->next = NULL;}// 非第一个结点else{// 结点前置为头结点head->next = s;// 结点后继为上一个结点s->next = p;}// 指针p保存当次插入的结点位置p = s;}return OK;}
不带头节点
/* 10_单链表——头插法建立_不带头结点*/Status headInsert_SL(SL& sL, ElementType* datas, int length){// 同上，指针p用来保存上一个创建的结点SL p = sL;// 指针s，用来创建新的节点SL s = NULL;for (int i = 0; i < length; i++){s = (SL)malloc(sizeof(SL_Node));if (!s){return ERROR;}s->data = *(datas + i);// 第一个结点if (!i){// 第一个结点作为表尾结点s->next = NULL;}else{// 连接到上一次插入的结点s->next = p;}// 连接到开始sL = s;// 保存为上一个结点p = s;}return OK;}
2.1.4 删除元素
删除指定值的元素并返回。每次必须通过前驱结点的next判断该结点，上前驱结点才好更改指针指向。
带头节点 -> 带头结点的好处是，不用额外考虑元素个数。
- 多一个头结点就刚好满足了每一个待判断的结点都有前驱，首元结点的前驱即是头结点。
- 若链表没有元素，则不用进入循环体，没有额外的考虑。
/* 14_单链表——删除结点_带头结点*/void deleteElem_SLh(SL& head, ElementType data){// 保存待删除结点的上一个结点SL p = head;// 保存待删除结点SL q = NULL;while (p->next){// 指针p总是在上一个结点的时候判断出下一个结点的条件if (p->next->data == data){q = p->next;// 指针q若无后继结点，不影响p->next = q->next;free(q);return;}// 否则继续查找p = p->next;}}
不带头节点
- 不太方便。
- 第一个元素没有前驱结点，需单独判断。
- 但是否有第一个元素还需要判断。带头结点的删除则可以直接进入循环体中判断。
/* 15_单链表——删除结点_不带头结点*/void deleteElem_SL(SL& sL, ElementType data){// 指针p，保存待删除结点的前一个结点SL p = sL;// 指针q，指向p的后继结点SL q = p->next;// 如果链表没有结点，直接返回if (!p){return;}// 如果第一个结点就是待删除结点else if (p && p->data == data){sL = q;free(p);return;}// 两个以上结点while (p->next){// 指针p总是在上一个结点的时候判断出下一个结点的条件if (p->next->data == data){q = p->next;p->next = q->next;free(q);return;}p = p->next;}}
- 不太方便。
2.1.5 原地逆置单链表
『单链表原地逆置』个人理解。
- 大思路是将所有结点分为两种状态，『已完成逆置』和『待逆置』；
- 刚开始的状态，所有结点都是待逆置状态。
- 除了首元结点外，后续结点在执行逆置过程中都有结点处于已完成逆置状态。
- 为了方便理解，且不将『首元结点的逆置』与『其余结点逆置』过程作为不同子过程单独处理，需在首元结点逆置过程中『虚拟出一个空结点』作为『已完成逆置状态』的结点。
- 此次虚拟空结点作为『已完成逆置状态结点』，更方便将循环体划分出来。
- 难点在于划分出单轮次的循环过程。
带头结点
/* 16_单链表——原地逆置_带头节点*/void invertList_SLh(SL& head){// 指针p保存下一个带改变指向的元素，保证断开后头结点的指针能找到SL p = head->next;// 用指针p保存了，此处一定要置空，作为虚拟出的空结点head->next = NULL;// 指针s是要改变指向的元素SL s = NULL;// 特别注意理解第一轮的过程，虚拟一个NULL结点在头结点和首元结点之间，作为【已完成逆置】的元素。while (p){// 当前【待逆置的元素】完成，设置【下一个待逆置元素】为【当前待逆置】；s = p;// 指针p作为【下一个待逆置】p = p->next;// 当前待逆置元素，指向上一个逆置完成的元素（第一个结点的上一个元素即是虚拟出的空结点，此处在进入循环前置空）s->next = head->next;// 当前元素逆置完成，【头结点指针指向的元素】则是【上一轮逆置完成的元素】head->next = s;}}
不带头结点
- 实现上与带头结点的没有不同，仅仅头指针与头结点next域的替换。
/* 17_单链表——原地逆置_不带头节点*//* 过程同上，原理无不同，只有head->next替换为sL头指针*/void invertList_SL(SL& sL){SL p = sL;sL = NULL;SL s = NULL;while (p){s = p;p = p->next;s->next = sL;sL = s;}}
- 实现上与带头结点的没有不同，仅仅头指针与头结点next域的替换。
2.2 循环链表
- 与单链表唯一的区别是，表尾的结点指向不是NULL。
- 带头结点
- 表为结点指向头结点
- 不带头结点
- 表尾结点指向首元结点
- 带头结点
- 基于这样一种变化，对于查询、遍历等循环结束条件，与链表是否为空的判断条件，由头结点next域或头指针是否为NULL，改成是否为头结点或首元结点。
2.3 双向循环链表
- 相对于单链表
- 优势是，对于头插法的操作，不需要从表头开始进行遍历查找，可以直接找到前驱。
- 劣势是，多维护一个前驱的关系，在某些情况可能比单链表耗性能。
- 存储结构定义
/ 双向链循环表存储结点/ typedef struct DuL_Node { // 指向前驱节点指针 DuL_Node prior; // 存储元素 ElementType data; // 指向后继节点指针 DuL_Node next; }DuNode, *DuL;
> <a name="84881111"></a>### 常用操作<a name="cf9de519"></a>#### 2.3.1 初始化操作- 前驱与后继指针都指向头结点```c/* 01_双向循环链表——初始化_带头结点*/Status initList_DuL(DuL& duL){duL = (DuL)malloc(sizeof(DuL_Node));if (!duL){return ERROR;}duL->data = NULL;// 循环链表，初始前置和后继时候指向自己duL->prior = duL;duL->next = duL;return OK;}
2.3.2 指定索引位置前插入元素
不需要通过前驱结点来判断索引位置结点，找到后就直接对索引位置进行操作。
/* 02_双向循环链表——在指定索引位置前插入元素*/Status insertByIndex_DuL(DuL& duL, int index, ElementType data){// 定义：插入之前的元素结点DuL beforeInsert = duL;// 先找到待插入为值的前置结点for (int i=0;i<index;i++){// 如果索引大于链表元素个数，则直接放最后if (beforeInsert->next != duL){beforeInsert = beforeInsert->next;}}// 插入后的后继节点DuL afterInsert = beforeInsert->next;// 建立插入结点DuL curInsert = (DuL)malloc(sizeof(DuL_Node));if (!curInsert){return ERROR;}curInsert->data = data;// 与前置结点关联beforeInsert->next = curInsert;curInsert->prior = beforeInsert;// 与后继结点关联curInsert->next = afterInsert;afterInsert->prior = curInsert;return OK;}
2.3.3 遍历
访问方法简单定义
/* 05_双向循环链表——访问*/void visit(DuNode duNode){printf("duNode data -> %d\n", duNode.data);}
1. 正向遍历
- 通过next后继指针遍历
/* 03_双向循环链表——正序遍历*/void traverseList_DuL(DuL duL){DuL p = duL->next;while (p != duL){visit(*p);p = p->next;}}
2. 反向遍历
- 通过prior前驱指针遍历
/* 04_双向循环链表——反向遍历*/void backTraverseList_DuL(DuL duL){DuL p = duL->prior;while (p != duL){visit(*p);p = p->prior;}}
2.3.4 批量插入元素到表尾
- 访问正向或反向的表尾元素很简单，直接通过头节点的prior即可。
- 相对于单链表而言，不需要从表头开始遍历到表尾。
/* 06_双向循环链表——批量插入数据到表尾*/Status batchInsertToTail_DuL(DuL& duL, ElementType* datas, int length){// 待插入的位置DuL tail = duL->prior;// 待插入的结点迭代DuL cur = NULL;for (int i = 0; i < length; i++){// 每次创建一个结点cur = (DuL)malloc(sizeof(DuNode));// 插入失败则返回错误if (!cur){return ERROR;}cur->data = *(datas + i);// 连接前置结点tail->next = cur;cur->prior = tail;// 连接后继结点cur->next = duL;duL->prior = cur;// 下一个tail = cur;}return OK;}
2.3.5 删除指定索引的元素
不需要通过前驱结点访问到当前结点，因为双向的优势可以直接找前驱或者后继。
/* 07_双向循环链表——删除指定索引的元素*/ElementType deleteByIndex_DuL(DuL& duL, int index){ElementType data;DuL cur = duL->next;// 直接找到该结点，不用找前置for (int i = 0; i < index; i++){if (cur->next == duL){return NULL;}cur = cur->next;}// 保存返回值data = cur->data;// 将前置节点和后继结点连接起来cur->prior->next = cur->next;cur->next->prior = cur->prior;// 释放空间free(cur);return data;}
暂时先补充到这里，如果有常见的操作会更新加到这里。
若有收获，就点个赞吧
0 人点赞
