hi !
目录
———————————————— 《 你的名字 》 ————————————————
正文开始——
前言:
前面我们学习了顺序表,实现了对数组内容增删查改等操作,但是顺序表仍然存在一些缺陷。
- 中间/头部的插入删除,时间复杂度为O(N);
- 增容需要申请新空间,拷贝数据,释放旧空间,这是不小的消耗;
- 增容一般是成2倍的增长,大概率会有一些空间的浪费。
那我们该如何解决上面的问题呢?下面我们来学习一下链表 。
1、链表的概念和结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现。
2、单链表(Single List,简写SList)的实现
上面我们了解了链表的概念和结构,链表又分为很多种,今天我们先学习链表之一单链表。
2.1 定义链表(结点)的结构
//定义链表(结点)的结构
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
}SLTNode;
2.2 创建一个链表
这里申请空间使用 malloc,在链表里面不存在增容的操作,想插入数据直接申请一个新的结点即可!用 calloc 也可以,calloc会让申请空间的内容初始化为0。
【代码】
test.c
//创建一个链表
void creatSList()
{
//链表是由一个一个的结点组成的
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;
//将结点之间连接起来
node1->next=node2;
node2->next=node3;
node3->next=node4;
node4->next = NULL;
}
2.3 打印链表
【思路图解】
【代码】
//链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
2.4 尾插
【思路图解】
【代码】
SList.c
//申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc file!");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//申请一个新结点
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* pcur = *pphead;
//找尾结点
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
//plist为指向第一个结点的指针
SLTPushBack(&plist,100);
SLTPrint(plist);
}
int main()
{
SListTest01();
return 0;
}
【验证】
【注意】
- 在 test.c 里面尾插时传的是&plist ,而不是 plist。我们希望形参的改变影响实参,所以我们取实参的地址。plist 作为参数传的是一个指针变量而不是一个地址,只有 &plist (有&)才算是真正的取地址使得形参的改变影响实参。用二级指针来接收。
- 找尾结点。循环的条件是 pcur->next,而不是 pcur。因为 pcur->next 为NULL跳出循环时,说明 pcur 为尾结点,当 pcur 为空跳出循环时,说明 pcur 是尾结点的下一个节点,而不是尾结点。
- pphead==&plist;*pphead==plist(指向第一个结点的指针) 。
- assert (pphead);传过来的地址不能为空。
2.5 头插
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//申请一个新结点
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
test.c
void SListTest01()
{
//验证尾插
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);
//验证头插
SLTPushFront(&plist, 200);
SLTPrint(plist);
}
int main()
{
SListTest01();
return 0;
}
【验证】
2.6 尾删
各结点的地址应为0x0012FF...,在此纠正下面的错误。谅解哈~~~
【思路图解】
当链表内不止一个结点时
当链表内只有一个结点时
【代码】
SList.c
//尾删
void SLTPopBack(SLTNode** pphead)
{
//链表为空,不可删除
assert(pphead && *pphead);
//处理只有一个结点的情况,要删除的就是头结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找 ptail 和 prev
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
SLTPopBack(&plist);
SLTPrint(plist);
}
int main()
{
/*createSList();*/
SListTest01();
return 0;
}
【验证】
2.7 头删
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//头删
void SLTPopFront(SLTNode** pphead)
{
//链表不为空
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/
SLTPopFront(&plist);
SLTPrint(plist);
}
int main()
{
/*createSList();*/
SListTest01();
return 0;
}
【验证】
2.8 查找
各结点的地址应为0x0012FF...,在此纠正下面的错误。
思路简单,直接上代码:
SList.c
//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
【注意】SLTNode* pcur = phead,重新定义一个指针变量 pcur 指向第一个结点,让 pcur 来遍历链表,防止头结点丢失。
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPushBack(&plist,100);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* find = SLTFind(plist, 2);
if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
}
}
【验证】
2.9 在指定位置之前插入数据
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
//申请一个新的结点
SLTNode* newnode = SLTBuyNode(x);
//找pos的前一个结点prev
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/
SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);
}
【验证】
2.10 在指定位置之后插入数据
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/
/*SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);*/
SLTNode* find = SLTFind(plist, 2);
SLTInsertAfter(find, 100);
SLTPrint(plist);
}
【验证】
2.11 删除pos结点
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
assert(pphead && *pphead);
//这里对pos进行限制,链表中必须有pos这个结点,在查找中若没有pos结点则返回NULL
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
//找到prev:pos的前结点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/
/*SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);*/
/*SLTNode* find = SLTFind(plist, 2);
SLTInsertAfter(find, 100);
SLTPrint(plist); */
SLTNode* find = SLTFind(plist, 2);
SLTErase(&plist, find);//这里的find由pos接收,SLTFind若没找到存储2这个结点则返回NULL
SLTPrint(plist);
}
【验证】
2.12 删除pos之后的结点
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
test.c
void SListTest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);
/*SLTPushFront(&plist, 200);
SLTPrint(plist);*/
/*SLTPopBack(&plist);*/
/*SLTPrint(plist);*/
//SLTPopFront(&plist);
//SLTPrint(plist);
//SLTNode* find = SLTFind(plist, 2);
/*///*if (find == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了\n");
//}*/
/*SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 100);
SLTPrint(plist);*/
/*SLTNode* find = SLTFind(plist, 2);
SLTInsertAfter(find, 100);
SLTPrint(plist); */
//SLTNode* find = SLTFind(plist, 2);
//SLTErase(&plist, find);
//SLTPrint(plist);
SLTNode* find = SLTFind(plist, 2);
SLTEraseAfter(find);
SLTPrint(plist);
}
【验证】
2.13 销毁链表
各结点的地址应为0x0012FF...,在此纠正下面的错误。
【思路图解】
【代码】
SList.c
//销毁链表
void SListDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//*pphead=plist,链表为空,也要把*pphead置为空
*pphead = NULL;
}
【验证】
今天单链表的深度学习就结束啦,拜拜~~~
完——
———————————————— 《 你的名字 》 ————————————————
重要的人,不能忘记的人,不想忘记的人,你,是谁?
不管在哪里,不管过多久,不管是要跨过高山,还是跨过湖海,我一定会去见你一面。
至此结束——
再见——
标签:pphead,结点,单链,SLTNode,SLTPrint,next,初阶,数据结构,plist From: https://blog.csdn.net/lrq13965748542/article/details/140621731