2. 链表
2.1 链表的概念及其结构
基本概念:
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。这里以单链表为例，说明其特征,如图1
- 存储空间不连续，数据元素之间使用指针相连,每个数据元素只能访问周围的一个元素;
- 长度不固定,可以任意增删;
- 要访问指定元素,要从头开始遍历元素,直到找到那个元素位置,时间复杂度为O(N)；
- 在指定的数据元素插入或删除，不需要移动其他元素,时间复杂度为O(1);
链表结构:
链表的结构非常多样,以下情况组合起来一共有8中链表结构:
1. 单向、双向 2. 带头、不带头 3. 循环、非循环
（注释:
单向:只包含指向下一个结点的指针，只能单向遍历;
双向:包含指向下一个结点的指针也包含指向前一个结点的指针,因此可以双向遍历;
带头:1.头结点是为了操作的统一和方便而设立的，放在链表第一个元素之前，其数据域大多无意义，但也可以用来保存链表长度。2.有了头结点，对链表头部的插入和删除操作就统一了。3.头结点不是链表的必要元素。
循环:将尾节点与首节点链接起来，形成了一个环状结构，在某些情况下会非常有用)
虽然有这么多链表的结构,但我们在实际运用中最常见到的还是两种结构:
这里由于篇幅原因,只讲解第一个无头单向非循环链表.
2.2 单链表的插入(头插,尾插,指定位置插入）
1）尾插(无头结点):1.创建新结点2.判断链表是否为空3.为空则让头指针指向新结点4.否则找到最后一个指针,指向新结点;
SLTNode* BuyListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } void SListPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuyListNode(x);//创建新结点 if (*pphead == NULL) {//判断链表是否为空 *pphead = newnode; } else { //找到最后一个结点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //将最后一个结点指向新结点 tail->next = newnode; } }
2)头插(无头结点):1.创建新结点 2.新结点指向原链表 3.头指针指向新结点;(注:2,3顺序不能颠倒,否则新结点将找不到原链表的地址)
SLTNode* BuyListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } void SListPushFront(SLTNode** pphead, SLTDateType x) { SLTNode* newnode = BuyListNode(x); newnode->next = *pphead; *pphead = newnode; }
3)在pos位置之前插入结点:1.创建新结点;2.判断第一个是否是其指定的位置3.如果是再来个头插,否则,找到pos的前一个位置posPrev;4将其新结点插入到pos位置之前，posPrev之后;
SLTNode* BuyListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } // 在pos位置之前去插入一个节点 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); assert(pos); SLTNode* newnode = BuyListNode(x);//创建新结点 //判断第一个是否等于pos if (*pphead == pos) { newnode->next = *pphead; *pphead = newnode; } else { //找到pos的前一个位置 SLTNode* posprev = *pphead; while (posprev->next != pos) { posprev = posprev->next; } posprev->next = newnode; newnode->next = pos; } }
4)在pos位置之后插入结点:1.创建新结点; 2.新结点的next指向pos的next；3.pos的next指向newnode;(注:2,3不能交换位置,否则将丢失pos之后的地址）
SLTNode* BuyListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } void SListInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuyListNode(x); newnode->next = pos->next; pos->next = newnode; }
2.3 单链表的删除(头删,尾删,指定位置删除)
1)尾删:1.判断链表是否为空,为空则则停止删除;2.若只有一个结点,释放其结点,让其链表为空;3.若有两个或两个以上的结点,找到最后一个和其前驱;4.其前驱next为空,释放最后一个结点;
void SListPopBack(SLTNode** pphead) { assert(*pphead != NULL); //1.一个的情况 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //2.两个或者两个以上 else { SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
2)头删: 1.判断链表是否为空;2.头指针指向第一个结点的next;3.释放第一个结点;
void SListPopFront(SLTNode** pphead) { assert(*pphead != NULL);//判断连表是否为空· SLTNode* cur = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = cur; }
3)指定位置删除:1.判断链表是否为空;2.如果pos等于第一个结点,则采用头删;3.找出pos的前一个prev 4.将prev的next指向pos的next;5.释放pos;
void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SListPopFront(pphead);//头删,详见上面代码 } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
2.4 单链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } else { cur = cur->next; } } return NULL; }
2.5 单链表的接口实现(供大家考察是否掌握)
// 1、无头+单向+非循环链表增删查改实现 typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x // 分析思考为什么不在pos位置之前插入？ void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos);
3. 顺序表与链表的优缺点
3.1 存取方式
顺序表:可以顺序存取,也可以随机存取;
单链表:只能从表头顺序进行存取元素;
3.2 逻辑结构与物理结构
顺序表:逻辑上相邻的元素,对应的物理存储位置也相邻；
单链表:逻辑上相邻的元素，物理存储位置不一定相邻，其逻辑关系是通过指针链接来表示的;
3.3 时间性能
顺序表支持随机访问,时间复杂度为O(1);
顺序表插入和删除需要依次移动元素，时间复杂度为O(N);
单链表要访问指定元素,需要从头遍历,时间复杂度为O(N);
单链表的插入和删除不需要移动元素,时间复杂度为O(1)；
3.4 空间性能
顺序表:需要预先分配存储空间，分配过多就会造成存储空间的浪费，而分配过少则会发生上溢。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大的连续存储空间，则会导致分配失败。
单链表:按需分配，且元素个数不受限制
以上是顺序表与链表的相关知识点，有不足的地方或者对代码有更好的见解，欢迎评论区留言共同商讨，共同进步！！
