链表
概念
链表是一种物理存储结构上非连续、非顺序的存储结构，
数据元素的逻辑顺序是通过链表中的指针链接次序实现的，
单链表一般不会单独使用，
只有头插和头删实现简单且效率高
结构
链表也属于线性表，线性表在物理上存储时，
通常以数组（顺序表）和链式结构（链表）的形式存储，
链式结构在逻辑上是连续的，但在物理上不一定连续
现实中的结点一般是从堆上申请出来的
从堆上申请的空间，是按照一定的策略来分配的，
两次申请的空间可能连续，也可能不连续
链表的分类
单向链表和双向链表
单向链表(常用)
双向链表
带头(哨兵位) 或 不带头(哨兵位) 链表
带头(哨兵位) 链表
不带头(哨兵位) 链表
循环链表
带头双向循环链表(常用)
顺序表和链表的优缺点
| 顺序表 | 链表 | |
| 存储空间 | 物理上一定连续 | 逻辑上连续,物理上不一定连续 |
| 访问 | 随机访问 | 不支持随机访问 |
| 任意位置插入或删除元素 | 效率低 | 修改指针指向 |
| 应用 | 空间不够扩容,元素高效存储,随机访问 | 分节点,开节点,可以在任意位置插入或删除 |
在SList.h文件中
定义单链表的结构
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; //数据 struct SListNode* next; //指针域next }SLTNode;
实现单链表的接口/方法
//打印链表 void SLTPrint(SLTNode* phead); //头部插入删除/尾部插入删除 void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode** phead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDesTroy(SLTNode** pphead);
在SList.c文件中
打印单链表(遍历链表)
//SLTNode*，表示 phead 是一个指向 SLTNode 类型的指针。 void SLTPrint(SLTNode* phead) //接收一个指向链表头节点的指针 phead 作为参数 { //一级指针 SLTNode* pcur = phead; while (pcur) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL"); printf("\n"); }
开辟空间
//开辟空间 SLTNode* SLTBuyNode(SLTDataType x) { //为一个 SLTNode 类型的结构体分配内存,以便访问和操作这个新分配的 SLTNode 结构体 //所以返回值为SLTNnode* SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; }
开辟空间molloc返回值问题
函数原型:
尾部插入元素
//尾部插入元素 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); //头结点为空 if (*pphead == NULL) { *pphead = newnode; return; } //头结点不为空 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; }
传参的时候为什么要传二级指针?
二级指针，在函数内部修改头指针本身的值
一级指针，用于遍历和访问链表
以下的 打印链表和销毁链表函数 说明一级和二级指针的意思
测试尾插
头部插入元素
//头部插入元素 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead; // *pphead表示头结点 *pphead = newnode; }
测试
尾部删除元素
free作用:
①free(ptail);之后，ptail指针本身的值并未改变，但它所指向的内存已经被释放，因此不应该再使 用这个指针访问已经被释放的内存。
②我们只需要确保不要再使用这个指针来访问内存，而不必将其置为NULL
//尾部删除元素 void SLTPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); //保证头结点不为空 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } //有多个结点 SLTNode* ptail = *pphead; SLTNode* prev = NULL; while (ptail->next) { prev = ptail; ptail = ptail->next; } //单链表最后一个结点,只有数据域data且指针域的值是NULL // 释放尾节点的内存 free(ptail); // 将尾节点的前驱节点的next置为NULL，实现删除尾节点 prev->next = NULL; }
测试
头部删除元素
void SLTPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); //保证头结点不为空 SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
测试
查找元素
//查找 SLTNode* SLTFind(SLTNode** phead, SLTDataType x) { assert(phead); SLTNode* pcur = *phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }
在指定位置之前插入数据
//在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(*pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x); //pos刚好是头节点 if (newnode->next == *pphead) { SLTPushBack(pphead, x); return; } //pos刚好不是头节点 SLTNode* pcur = *pphead; while (pcur->next != pos) { pcur = pcur->next; } pcur->next = newnode; newnode->next = pos; }
测试
删除pos节点
//删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(*pphead); assert(pos); //刚好是头节点 if (pos == *pphead) { SLTPopFront(pphead); return; } //不是头节点 SLTNode* pcur = *pphead; while (pcur->next != pos) { pcur = pcur->next; } pcur->next = pos->next; free(pos); pos = NULL; }
测试
在指定位置之后插入数据
//在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); SLTNode* pcur = pos->next; pos->next = newnode; newnode->next = pcur; }
删除pos之后的节点
//删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos); SLTNode* p1 = pos->next; SLTNode* pcur = pos->next->next; pos->next = pcur; free(p1); p1 = NULL; }
测试
销毁链表
//销毁链表 //SLTNode**，表示 pphead 是一个指向 SLTNode* 类型的指针的指针 void SListDesTroy(SLTNode** pphead) { /* pphead：(二级指针)*/ assert(pphead); //一级指针 assert(*pphead);//头结点不为空,链表不为空 SLTNode* pcur = *pphead; //*pphead 是头指针本身(一级指针)，用于遍历和访问链表 //先释放,后置空 while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
