"申请新节点"函数
新节点都是使用malloc函数动态申请的.函数实现很简单,相信聪明的友友们可以理解,牛牛就不过介绍了.
SLTNode* BuyNode(DateType x)//创建新结点 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); assert(newnode);//防止申请结点失败 newnode->Date = x; newnode->next = NULL; return newnode; }
2.3 "删除"元素操作.
因为链表的结点都是动态申请的,所以链表的删除操作需要将目标结点释放,同时为了保护原有的链表结构,需要将受目标结点的其他结点也灵活修改.
单链表的"尾删"
"删除结点"步骤:
- 处理特殊情况,如果头指针指向NULL,空链表不能执行删除操作.
- 找倒数第二个结点,方法:tail->next->next != NULL因为最后一个结点的next=NULL;
数据结构记得多画图哦,有助于我们理解.
- 先释放尾结点(tail->next),再将倒数第二个结点的next置空NULL
- 处理特殊情况:如果链表就只有一个结点,就不存在倒数第二个结点,此时直接释放头结点,并将头结点置空.
图解:
//尾删 void PopBack(SLTNode** pphead) { assert(pphead);//二级指针不可能为空,如果为空就一定是传错了 assert(*pphead);//防止空链表的删除操作 SLTNode* tail = *pphead;//创建一个指针代替头指针遍历 if (tail->next == NULL) { free(tail); tail= NULL; } else { while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
单链表的"头删":
同样,单链表的"头删"也是很简单的操作.
步骤:
- 将头结点记录一下.
- 将头指针指向第二个结点.
- 释放头结点.
void PopFront(SLTNode** pphead) { assert(pphead);//二级指针不可能为空,如果为空就一定是传错了 assert(*pphead);//防止空链表的删除操作 SLTNode* head = *pphead; *pphead = ( * pphead)->next; free(head); }
思考:
需不需要单独去考虑,如果链表只有一个结点的特殊情况?
答案:
不需要,因为如果链表只有一个结点,头删将头指针指向第二个结点,刚好是指向NULL,也是符合要求的.
单链表的"删除"指定的目标结点
步骤:
- 通过查找目标结点函数SListFind(下面牛牛讲了),找到目标结点的地址.
- 将目标结点的前驱结点指向目标结点的后继结点.
- 释放目标结点.
- 特殊情况:如果是头删,需要修改头结点,让其指向第二个结点.
图解:
代码实现:
//告诉位置(建议配合SListFind函数一起使用),删除第一个出现该值的节点 void SlitErase(SLTNode** pphead, SLTNode* pos) { assert(pphead);//二级指针不可能为空,如果为空就一定是传错了 assert(*pphead);//防止空链表的删除操作 assert(pos); SLTNode* cur = *pphead;//创建一个指针代替头指针遍历 if (cur == pos) {//如果目标结点是头结点这种特殊情况 SLTNode* next = cur->next; free(cur); *pphead = next; } else { while (cur->next != pos && cur->next != NULL)//遍历寻找目标结点 { cur = cur->next; } cur->next = pos->next;//将目标结点的前驱指向目标结点的后继 free(pos); } }
2.4 "查找"目标结点函数
单链表查找目标结点只需要遍历一遍这个链表即可,如果目标结点有多个,则只返回第一个遇到的目标结点,找不到目标结点则返回NULL.
函数很简单,牛牛不过多介绍了.
SLTNode* SListFind(SLTNode* phead, DateType x) { SLTNode* cur = phead;//代替头指针遍历链表 while (cur) { if (cur->Date == x) { return cur; } cur = cur ->next; } return NULL; }
2.5 单链表的"打印"
单链表的打印很简单,遍历打印就行了.
void Print(SLTNode* phead)//链表的打印 { //assert(phead); SLTNode* cur = phead; while (cur) { printf("%d->", cur->Date); cur = cur->next; } printf("NULL\n\n"); }
2.6 单链表的"销毁"
步骤:
- 创建next指针保存要删除节点的下一个结点.
- 将要删除的结点释放.
- 将要删除的结点更新到next
- 继续执行1
//单链表的销毁 void SLTDestroy(SLTNode* phead)//这个函数不会将头指针置空,要使用该函数的人自己置空 { SLTNode* del = phead; SLTNode* next = phead;//用于记录下一个结点 while (next) { next = next->next; free(del); del = next; } //保持习惯置空 next == NULL; del = NULL; }
总结:"链表"与"顺序表"的区别
| 顺序表 | 链表 | 区别 |
| 物理上必定是连续的 | 逻辑上连续,但是物理上不一定连续 | 物理存储空间 |
| 访问其中的某个结点支持随机访问( O(1) ) | 不支持随机访问 | 访问元素 |
| 大多数情况下需要移动数据,效率低( O(N) ) | 只需要改变目标指针的指向,但是需要找到该结点 | 删除和插入新节点(任意位置) |
| 容量不够时,动态顺序表需要动态扩容,效率不高 | 没有容量的概念不需要扩容,资源利用率高 | 插入数据时 |
| 元素的存储很高效+频繁访问 | 频繁的对任意位置的插入和删除 | 使用场景 |
| 由于无物理上连续存在,利用率高 | 利用率低 | 缓存利用率 |
三、总代码
测试区(test.c)
//test.c 主函数区域,用于测试接口 #include "SList.h" void test1() { SLTNode* plist=NULL; printf("插入0,1,2,3,4,5,6,7,8,9之后:\n"); PushBack(&plist, 1); PushBack(&plist, 2); PushBack(&plist, 3); PushBack(&plist, 4); PushBack(&plist, 5); PushBack(&plist, 6); PushBack(&plist, 7); PushBack(&plist, 8); PushBack(&plist, 9); //头插 PushFront(&plist, 0); Print(plist); printf("尾删一次后:\n"); PopBack(&plist); Print(plist); printf("头删一次后:\n"); PopFront(&plist); Print(plist); printf("删除第一次出现元素7的结点后:\n"); SlitErase(&plist, SListFind(plist, 7)); Print(plist); printf("在第一个出现5值的结点后面插入一个值为666的结点\n"); SLTInsertBack(SListFind(plist, 5), 666); Print(plist); SLTDestroy(plist); plist == NULL; } int main() { test1(); return 0; }
接口实现区(SList.c)
#include "SList.h" SLTNode* BuyNode(DateType x)//创建新结点 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); assert(newnode); newnode->Date = x; newnode->next = NULL; return newnode; } void PushBack(SLTNode** pphead, DateType x) { assert(pphead); SLTNode*tail = *pphead;//创建一个指针代替头指针遍历 SLTNode* newnode = BuyNode(x); //cur代表代表头指针,phead表示头指针的地址 //如果cur指向NULL,说明为空链表 if (*pphead == NULL) { //这里可以使用tail代替*phead吗? //不能,因为这里要改变的是,头结点的指针,需要用二级指针(解引用)来改变 *pphead = newnode;//空链表是将头指针指向新节点 } else { //找尾巴,画图解析 //这里可以使用tail,是因为,要改变的是结构体的内容,只需要用结构体指针(解引用)就行 while ( tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } //头插(错误示例) //void PushFront(SLTNode** pphead, DateType x) //{ // assert(pphead); // SLTNode* phead = *pphead; // SLTNode* newnode = BuyNode(x); // //下面两句的顺序不能变,除非再创一个结点保phead // newnode->next = phead; // phead= newnode; //} // 正确写法1 //void PushFront(SLTNode** pphead, DateType x) //{ // assert(pphead); // SLTNode* newnode = BuyNode(x); // //下面两句的顺序不能变,除非再创一个结点保phead // newnode->next = *pphead; // *pphead = newnode; //} //写法2 void PushFront(SLTNode** pphead, DateType x) { assert(pphead); SLTNode* newnode = BuyNode(x); SLTNode* phead = *pphead; //顺序随便改 *pphead = newnode; newnode->next = phead; } //尾删 void PopBack(SLTNode** pphead) { assert(pphead);//二级指针不可能为空,如果为空就一定是传错了 assert(*pphead);//防止空链表的删除操作 SLTNode* tail = *pphead;//创建一个指针代替头指针遍历 if (tail->next == NULL) { free(tail); tail= NULL; } else { while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void PopFront(SLTNode** pphead) { assert(pphead);//二级指针不可能为空,如果为空就一定是传错了 assert(*pphead);//防止空链表的删除操作 SLTNode* head = *pphead; *pphead = ( * pphead)->next; free(head); } SLTNode* SListFind(SLTNode* phead, DateType x) { SLTNode* cur = phead; while (cur) { if (cur->Date == x) { return cur; } cur = cur ->next; } printf("找不到:\n"); return NULL; } void SlitErase(SLTNode** pphead, SLTNode* pos) { assert(pphead);//二级指针不可能为空,如果为空就一定是传错了 assert(*pphead);//防止空链表的删除操作 assert(pos); SLTNode* cur = *pphead;//创建一个指针代替头指针遍历 if (cur == pos) {//如果目标结点时头结点 SLTNode* next = cur->next; free(cur); *pphead = next; } else { while (cur->next != pos && cur->next != NULL)//遍历寻找目标结点 { cur = cur->next; } cur->next = pos->next;//将目标结点的前驱指向目标结点的后继 free(pos); } } void SLTInsertBack( SLTNode* pos, DateType x) { assert(pos); SLTNode* newnode = BuyNode(x); newnode->next = pos->next; pos->next = newnode; } void Print(SLTNode* phead)//链表的打印 { //assert(phead); SLTNode* cur = phead; while (cur) { printf("%d->", cur->Date); cur = cur->next; } printf("NULL\n\n"); } void SLTDestroy(SLTNode* phead)//这个函数不会将头指针置空,要使用该函数的人自己置空 { SLTNode* del = phead; SLTNode* next = phead;//用于记录下一个结点 while (next) { next = next->next; free(del); del = next; } //保持习惯置空 next == NULL; del = NULL; }
函数声明区(SList.h)
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int DateType; typedef struct SListN0de { DateType Date; struct SListN0de* next; }SLTNode; //尾插 void PushBack(SLTNode** pphead, DateType x); //尾删 void PopBack(SLTNode** pphead); //头插 void PushFront(SLTNode** pphead, DateType x); //头删 void PopFront(SLTNode** pphead); //告诉值,返回结点的地址 SLTNode* SListFind(SLTNode* phead, DateType x); //告诉位置(建议配合SListFind函数一起使用),删除第一个出现该值的节点 void SlitErase(SLTNode** pphead, SLTNode* pos); //告诉位置,在位置后面插入 void SLTInsertBack( SLTNode* pos, DateType x); struct SListN0de* BuyNode(DateType x);//创建新节点 void Print(SLTNode* phead);//链表的打印 // 单链表的销毁 void SLTDestroy(SLTNode* phead);
