系统性学习数据结构-第二讲-顺序表与链表

1.线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。

线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。

但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。

那么顺序表和数组的区别究竟在哪里？

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口，所以我们只需要调用对应的函数对顺序表进行操作即可，

不再需要我们自己去撰写代码去对数组进行操作，这有效的简化了我们的操作。

2.2 分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

typedef int SLDatatype;
#define N 7
typedef strucut{SLDataType a[N]; //定长数组int size; //有效数据个数
}SL；

对于静态的顺序表，有一个缺陷，我们已经人为固定了数组的长度，所以空间少了我们不够用，多了我们就造成了空间浪费。

所以为了解决这个缺陷，我们引出了动态顺序表。

2.2.2 动态顺序表

typedef struct SeqList
{SLDataType* a;int size;     //有效数据个数int capacity; //空间容量
}SL；

在动态顺序表中，我们将静态顺序表中的定长数组更换成了指针，所以我们能对空间进行操作，不会再出现像静态顺序表中的情况。

2.3 动态顺序表的实现

我们先从头文件的实现进行分析：

SeqList.h

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDataType* a;int size; // 有效数据个数int capacity; // 空间容量
}SL;
//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//尾部插入
void SLPushBack(SL* ps, SLDataType x);
//尾部删除
void SLPopBack(SL* ps);
//头部插入
void SLPushFront(SL* ps, SLDataType x);
//头部删除
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找数据
int SLFind(SL* ps, SLDataType x);

下面我们再对源文件的实现进行分析：

SeqLlish.c

#include "SeqList.h"//初始化顺序表
void SLInit(SL* ps)
{ps->arr = NULL;ps->capacity = 0;ps->size = 0;
}//销毁顺序表
void SLDesTroy(SL* ps)
{if(ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->size = 0;
}//顺序表容量扩容检查机制
void SLCheckCapacity(SL* ps)
{if(ps->size == ps->capacity){ int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;/*SL* tmp = realloc(ps->arr, NewCapacity * sizeof(SLDataType)); 错误点1：指针类型不对，以及没有强转指针类型*/SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail!:");exit(1);}ps->arr = tmp;ps->capacity = NewCapacity;}}//尾部插入
void SLPushBack(SL* ps, SLDataType data)
{assert(ps);/*assert(ps->arr); 错误点2：去判断数组是否为空*/SLCheckCapacity(ps);/*SLCheckCapacity(&ps); 错误点3：传入的为结构体地址的地址*/ps->arr[ps->size++] = data;
}//头部插入
void SLPushFront(SL* ps, SLDataType data)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = data;ps->size++;
}//尾部删除
void SLPopBack(SL* ps)
{assert(ps && ps->size);//错误点4：assert(ps); 也需判断size变量是否为0，这点与插入数据是不同的ps->size--;
}//头部删除
void SLPopFront(SL* ps)
{//顺序表不能为空assert(ps && ps->size);//注意变量的限制for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//查找指定数据
int SLFind(SL* ps, SLDataType data)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == data)return i;}return -1;
}//指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType data)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//错误点5：不去判断插入坐标的大小是否合法SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = data;ps->size++;//错误点6：最后没有对size进行更改
}//指定位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps && ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos; i < ps->size - 1; i--){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

编写代码过程中要勤测试，避免学出大量代码再测试而导致出现问题，问题定位无从下手。

2.4 顺序表算法题

2.4.1 移除元素

int removeElement(int* nums, int numsSize, int val) {int* New = nums;int num = 0;for(int i = 0; i < numsSize; i++){if(nums[i] != val){New[num] = nums[i];num++;}}  return num;
}

2.4.2 删除有序数组中的重复项

int removeDuplicates(int* nums, int numsSize) {int* New = nums;int num = 0;for(int i = 1; i < numsSize; i++){if(nums[i] != New[num]){New[++num] = nums[i];}}return num + 1;
}

2.4.3 合并两个有序数组

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int New[m + n];int sign = 0;int sign1 = 0, sign2 = 0;while(sign1 < m && sign2 < n){if(nums1[sign1] < nums2[sign2]){New[sign++] = nums1[sign1++];}else{New[sign++] = nums2[sign2++];}}if(sign1 < m){while(sign1 < m){New[sign] = nums1[sign1];sign++;sign1++;}}else{while(sign2 < n){New[sign] = nums2[sign2];sign++;sign2++;}}for(int i = 0; i < m + n; i++){nums1[i] = New[i];}
}

2.5 顺序表问题与思考

• 中间/头部的插入删除，时间复杂度为O(N)

• 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

• 增容⼀般是呈 2 倍的增长，势必会有⼀定的空间浪费。例如当前容量为 100 ，满了以后增容到 200

在这种情况下再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

那为了解决这种空间的浪费，引出我们的单链表。

3. 单链表

3.1 概念与结构

概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的，指针链接次序实现的。

淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉加上，不会影响其他车厢，

每节车厢都是独立存在的。

在链表里，每节“车厢”是什么样的呢？

3.1.1 结点

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/结点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

图中指针变量 plist 保存的是第⼀个结点的地址，我们称 plist 此时“指向”第⼀个结点，如果我们希望 plist “指向”第⼆个结点时，

只需要修改 plist 保存的内容为0x0012FFA0，链表中每个结点都是独立申请的。

（即需要插入数据时才去申请一块结点的空间）

需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

3.1.2 链表的性质

1. 链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2. 结点⼀般是从堆上申请的

3. 从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：

假设当前保存的结点为整型

struct SListNode
{int data; //结点数据struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，

也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。

当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。

3.1.3 链表的打印

给定的链表结构中，如何实现结点从头到尾的打印？

思考：当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时，该如何修改？

3.2 实现单链表

我们先从头文件对实现单链表进行分析：

SList.h

//定义链表的结构
//定义结点的结构typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next; //指向下一个节点的指针
}SLTNode;//向操作系统申请一个新节点
SLTNode* SLTBuyNode(SLTDataType data);//打印链表，phead：头（首）结点
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType data);//头插
void SLTPushFront(SLTNode** pphead, SLTDataType data);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType data);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data);//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType data);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDestroy(SLTNode** pphead);

下面再从源文件对实现单链表进行分析：

SList.c

#include "SList.h"//向操作系统申请一个新节点
SLTNode* SLTBuyNode(SLTDataType data)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//SLTNode* newnode = malloc(sizeof(SLTNode)); 错误点1：没有强转指针类型if (newnode == NULL){perror("malloc fail:");exit(1);}newnode->data = data;newnode->next = NULL;return newnode;
}//打印链表数据
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ",pcur->data);pcur = pcur->next;}printf("NULL");
}void SLTPushBack(SLTNode** pphead, SLTDataType data)
{assert(pphead);SLTNode* newnode = SLTBuyNode(data);//链表为空，phead直接指向newnode结点if (*pphead == NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;//不能讲头节点的位置进行改变，所以创建一个变量进行接下来的操作//链表不为空，找尾结点，将尾结点和新节点连接起来while (ptail->next != NULL){ptail = ptail->next;}ptail->next = newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType data)
{assert(pphead);SLTNode* newnode = SLTBuyNode(data);newnode->next = *pphead;*pphead = newnode;//最后要将头节点的位置改变
}void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个节点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead == NULL;}else{SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType data)
{SLTNode* pcur = phead;while (pcur != NULL){if (pcur->data == data)return pcur;pcur = pcur->next;}return NULL;
}//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType data)
{assert(pphead && pos);if (pos == *pphead){SLTPushFront(pphead, data);}else {SLTNode* newnode = SLTBuyNode(data);SLTNode* prev = NULL;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}void SLTInsertAfter(SLTNode* pos, SLTDataType data)
{assert(pos);SLTNode* newnode = SLTBuyNode(data);newnode->next = pos->next;pos->next = newnode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead && pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}void SListDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3.3 链表的分类

链表的结构非常多样，以下情况组合起来就有 8 种（2 * 2 * 2）链表结构：

链表说明：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表

1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.4 单链表算法题

3.4.1 移除链表元素

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {if(head == NULL)return NULL;struct ListNode* NewElement = (struct ListNode*)malloc(sizeof(struct ListNode));NewElement->next = head;struct ListNode* pcur = NewElement;while(pcur->next != NULL){if(pcur->next->val == val){pcur->next = pcur->next->next;}else{pcur = pcur->next;}}return NewElement->next;
}

3.4.2 反转链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL, *pcur = head;while(pcur != NULL){struct ListNode* next = pcur->next;pcur->next = prev;prev = pcur;pcur = next;}return prev;
}

3.4.3 链表的中间结点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* pfast = head, *pslow = head;while(pfast != NULL && pfast->next != NULL){pslow = pslow->next;pfast = pfast->next->next;}return pslow;
}

3.4.4 合并两个有序链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* NewList = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* pcur = NewList;while(list1 && list2){if(list1->val < list2->val){pcur->next = list1;list1 = list1->next;pcur = pcur->next;}else{pcur->next = list2;list2 = list2->next;pcur = pcur->next;}}if(list1){pcur->next = list1;}else{pcur->next = list2;}return NewList->next;
}

3.4.5 相交链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* pcurA = headA, *pcurB = headB;int numA = 0, numB = 0;while(pcurA != NULL){numA++;pcurA = pcurA->next;}while(pcurB != NULL){numB++;pcurB = pcurB->next;}int gap = abs(numA - numB);struct ListNode* shortlist = headA, *longlist = headB;if(numA > numB){shortlist = headB;longlist = headA;}while(gap--){longlist = longlist->next;`在这里插入代码片`}while(shortlist) //此时长链表与短链表长度一直，所以只需要判断一个即可{if(shortlist == longlist){return longlist;}longlist = longlist->next;shortlist = shortlist->next;}return NULL;
}

3.4.8 环形链表

bool hasCycle(struct ListNode *head) {struct ListNode *slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){return true;}}return false;
}

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next;int n=3; //fast每次⾛三步while(n--){if(fast->next)fast = fast->next;elsereturn false;}if(slow == fast){return true;}}return false;
}

3.4.9 环形链表II

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow = head, *fast = head;struct ListNode *same = NULL, *pcur = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){same = slow;break;}   }if(same){while(same != pcur){same = same->next;pcur = pcur->next;}return pcur;}return NULL;
}

4. 双向链表

4.1 概念与结构

💡注意：这里的“带头”跟前面我们说的“头结点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”

4.2 实现双向链表

list.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; struct ListNode* prev;LTDataType data;
}LTNode;void LTPrint(LTNode* phead);//双向链表的初始化
//void LTInit(LTNode** pphead);//传地址：形参的改变影响实参
LTNode* LTInit();
//为了保持接口一致性，建议统一参数，都传一级：手动将实参置为NULL
void LTDesTroy(LTNode* phead);
//传二级：未保持接口一致性
//void LTDesTroy(LTNode** pphead);//尾插
//phead结点不会发生改变，参数传一级
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找指定节点位置
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的结点
void LTErase(LTNode* pos);
//判断链表是否为空
bool LTEmpty(LTNode* phead);

list.c

#include"list.h"LTNode* BuyNode(LTDataType data)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fial:");exit(1);}node->data = data;node->next = node->prev = node;return node;
}//双向链表的初始化（使用二级指针的情况）
//为了接口一致性，不采用此方式进行实现
//void LTInit(LTNode** pphead)
//{
//	*pphead = buyNode(-1);
//}LTNode* LTInit()
{LTNode* phead = BuyNode(-1);return phead;
}//传二级指针的销毁方式
//为了接口一致性同样不进行采用
//void LTDesTroy(LTNode** pphead)
//{
//	LTNode* pcur = (*pphead)->next;
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//}void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL; //不要忘记把指针置空
}void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* plist = phead->prev;newnode->prev = plist;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* plist = phead->prev;newnode->next = phead->next;newnode->prev = phead;phead->next = newnode;phead->next->prev = newnode;
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

5. 顺序表与链表的分析