c语言数据结构:单链表及其相关基础操作

目录

0.创建一个额外新的结点

1.链表的概念及其结构

2.单链表的概念

3.单链表的结点的创建

?4. 顺序表的打印

5.?链表的尾插

5.1 有关单链表的传参 (重点)

5.1.1 错误的写法

5.1.2 如何修正

5.1.3 正确的写法

5.1.4 看穿二级指针变量

?编辑

?6.链表的头插

7.单链表的尾删

8.单链表的头删

9.?指定位置之前插入数据

10.在指定位置之后插入?

?11.删除指定节点

12.删除指定节点之后的结点

13.链表的销毁

---

1.链表的概念及其结构

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

2.单链表的概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成包括数据域和指针域。数据域用于存储数据元素，指针域则指示后继元素存储位置。单链表通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。每个结点只有一个指针域的链表称为单链表。

3.单链表的结点的创建

//为新结点进行内存开辟,数据指针域的出初始化,最终得到一个新的结点,并且返回,此结点的类型是sltnode*
sltnode* sltbuynode(sldatatype x)
{
?? ?//先将要被插入的结点构建出来,用指针变量newnode为这个新结点开辟一个空间且指针newnode代表这个新结点
?? ?sltnode* newnode = (sltnode*)malloc(sizeof(sltnode));
?? ?newnode->data = x;//其数据域初始化
?? ?newnode->next = NULL;//其指针域初始化
}

?4. 顺序表的打印

//顺序表的打印
void sltprint(sltnode* phead)//phead是链表的第一个结点,或者说是头节点,//phead是plist的一份临时拷贝
{

?? ?sltnode* pcur = phead;//创建一个pcur指针,初始化指向链表的第一个节点,用于对链表的基础操作
?? ?while (pcur)
?? ?{
?? ??? ?printf("%d->", pcur->data);
?? ??? ?pcur = pcur->next;//经验,如果遇见形如"p->next"(p是指向结点的指针,next是一个指针域)放在"="的右边,那么
?? ??? ?//可以直接将它当作p目前所指向结点的下一个结点.如果在左边,那么就是一个指针域
?? ??? ?//所以说这里的?? ?pcur = pcur->next;就是将下一个节点盖到目前指针指向结点
?? ??? ?//放到while或者for等循环语句是可以完成指针p对链表的遍历的
?? ?}
?? ?printf("NULL\n");
}

5.?链表的尾插

//链表的尾插
void sltpushback(sltnode**pphead, sldatatype x)//传递过来的一级指针地址用二级指针接收
{//*pphead是一级指针,一级指针就代表的是一个结点
?? ?assert(pphead);//pphead是二级指针变量
?? ?//分两种情况,链表空和不空

?? ?//开辟空间
?? ?sltnode* newnode = sltbuynode(x);

?? ?//链表为空,那么第一个节点肯定是不存在的
?? ?if (*pphead == NULL)
?? ?{
?? ??? ?*pphead = newnode;
?? ??? ?return;
?? ?}

?? ?//链表不为空,需要去找以遍历的方式尾结点
?? ?sltnode* ptail = *pphead;//构建一个用于对链表进行操作的结点并且将其初始化为指向第一个节点
?? ?while (ptail->next != NULL)//如果找到了一个结点它的指针域指向NULL,那么此结点便是尾结点
?? ??? ?//所以这个循环找到此结点指针域指向空时,就是找到了尾结点,循环停止,并且进行下一步操作
?? ?{
?? ??? ?ptail = ptail->next;//推进指针的遍历
?? ?}

?? ?//将结点连接到单链表上面去
?? ?//要先将被连结的结点的指针域连结到单链表上
?? ?newnode->next = NULL;
?? ?ptail->next = newnode;
}

?

5.1 有关单链表的传参 (重点)

5.1.1 错误的写法

在slisttest02函数中,指向第一节点的指针plist被初始化为NULL,NULL是一个用于初始化指针的特殊的值,但是我们的目的是传递只想第一节点指针的地址,但是我们的操作 sltpushback(plist,1);传递的plist实参变量传递的是一个值,未能达到目的

5.1.2 如何修正

那就实参去取一级指针变量plist的地址plist,一级指针的地址必须要用二级指针去接受,所以

5.1.3 正确的写法

5.1.4 看穿二级指针变量

?6.链表的头插

void sltpushfront(sltnode** pphead, sldatatype x)//传递过来的一级指针地址用二级指针接收
{
?? ?assert(pphead);
?? ?sltnode* newnode = sltbuynode(x);//为新结点申请一块新的空间

?? ?newnode->next = *pphead;
?? ?*pphead = newnode;//让newnode成为新的头结点
}

7.单链表的尾删

//其操作原理就是改变尾结点之前那个结点指针域指向方向
//核心是要找到尾结点之前的那个结点
void sltppopback(sltnode** pphead)
{
?? ?assert(pphead);//pphead表示的是二级指针变量,不可为空
?? ?assert(*pphead);//*phead是指向链表的一级指针变量,这个链表不可为空,否则无法进行删除操作

?? ?//链表不为空的情况下
?? ?//链表只有一个节点和链表有多个结点的两种情况

?? ?//只有一个结点
?? ?if ((*pphead)->next == NULL)
?? ?{
?? ??? ?free(*pphead);
?? ?}
?? ?*pphead = NULL;
?? ?return;

?? ?//如果有很多结点,只能用遍历的方法
?? ?sltnode* ptail = *pphead;
?? ?sltnode* prev = NULL;
?? ?while (ptail->next != NULL)
?? ?{
?? ??? ?prev = ptail;
?? ??? ?ptail = ptail->next;
?? ?}
?? ?//循环着,两个指针一起向着右边走,但是走到?? ?ptail = ptail->next;时ptail比prev快一步,
?? ?//然后再进行?? ?while (ptail->next != NULL)时,发现ptail的指针域指向NULL,循环结束
?? ?//此时ptail比prev快一步
?? ?prev->next = NULL;

?? ?free(ptail);
}

?

8.单链表的头删

sltnode* sltfind(sltnode** pphead, sldatatype x)//找到的结点返回,此结点的类型是sltnode*
{
?? ?assert(pphead);
?? ?//遍历链表
?? ?sltnode* pcur = *pphead;//pphead是指向第一结点的指针,pcur适用于对链表操作的指针
?? ?while (pcur!=NULL)//如果表达式为NULL,则while循环结束
?? ?{
?? ??? ?if (pcur->data == x)
?? ??? ?{
?? ??? ??? ?return pcur;
?? ??? ?}
?? ??? ?pcur = pcur->next;
?? ?}
?? ?//没有找到
?? ?return NULL;
}?

9.?指定位置之前插入数据

void sltinsert(sltnode** pphead, sltnode* pos, sldatatype x)//*pphead是指向头结点的指针.pos是用于对链表进行操作的指针
{//在指定位置pos之前插入x
?? ?assert(pphead);
?? ?assert(pos);
?? ?//链表不能为空
?? ?assert(*pphead); ?

?? ?//pos是头结点
?? ?if (pos == *pphead)
?? ?{
?? ??? ?//头插
?? ??? ?sltpushfront(pphead, x);
?? ??? ?return;
?? ?}

?? ?//pos不是头结点
?? ?sltnode* newnode = sltbuynode(x);//申请一个新结点newnode用来指向新的结点
?? ?sltnode* prev = *pphead;//定义并且初始化prev
?? ?while (prev->next != pos)
?? ?{
?? ??? ?prev = prev->next;
?? ?}

?? ?//务必记住,将新节点插入时要先将被连接结点的指针域插上去
?? ?newnode->next = pos;
?? ?prev->next = newnode;
}
?

10.在指定位置之后插入?

void sltinsertafter(sltnode* pos, sldatatype x)
{
?? ?assert(pos);
?? ?sltnode* newnode = sltbuynode(x);

?? ?newnode->next = pos->next;
?? ?pos->next = newnode;
}
//指定位置插入
//如果是指定位置之前插入,由于单链表仅可单向移动的特性,所以我们需要重新定义一个指针从头开始遍历到指定节点之前
// 还有一个办法实现指定位置之前插入,就是在指定结点之后插入,然后交换被插入结点的数据域和指定节点的数据域
//如果是指定位置之后插入,那么直接在指定位置之后直接连结

?11.删除指定节点

void slerase(sltnode** pphead, sltnode* pos)
{
?? ?assert(pphead);
?? ?assert(*pphead);
?? ?assert(pos);

?? ?sltnode* prev = *pphead;
?? ?while (prev->next != pos)//让前驱结点从头向后遍历,只要前驱节点的指针域不指向pos,那么循环就不会停止
?? ?{
?? ??? ?prev = prev->next;
?? ?}
?? ?//释放指定节点
?? ?free(pos);
?? ?pos = NULL;
}
//先找到指定节点pos的前驱结点prev
//然后改变prev的指针域指向方向
//最后释放pos

12.删除指定节点之后的结点

void sleraseafter(sltnode* pos)
{
?? ?assert(pos);
?? ?assert(pos->next);

?? ?//对结点pos ? pos->next ? pos->next->next进行操作
?? ?//NULL不能free
?
?? ?pos->next = NULL;

?? ?assert(pos->next);
?? ?pos->next = pos->next->next;
?? ?sltnode* del = pos->next->next;//将要被删除的节点保存下来
?? ?pos->next = pos->next->next;//将结点pos的指针域指向为NULL,那么pos的后继节点pos->next也指向为空
?? ?//free(pos->next);//那么这里就是free(NULL),这是不合法的
?? ?//pos->next = NULL;
?? ?free(del);
?? ?del = NULL;
?? ?//所以说这里最好的做法就是先将将要被删除的结点保存下来,然后再改变被删除的结点del之前的那个结点指针域所指方向
?? ?//形如"pos->next"不仅仅是放在等号右边可以看作就是pos的下一个结点
?? ?//在"pos->next=pos->next->next"中
?? ?//而且放在等号的右边一来可以表示结点pos的指针域,二来可以代表将pos的指针域直接顶替掉pos的后继节点pos->next
?? ?//连结到结点pos->next->next;
?? ?//所以说需要将pos的将要被删除的后继节点pos->next用del保存起来
}

13.链表的销毁

void slistdestroy(sltnode** pphead)
{
?? ?assert(pphead);
?? ?assert(*pphead);
?? ?//将pcur指向结点删除,然后移动到next位置,再将next向后移动一个位置,再删除pcur指向结点,如此反复,直到next=NULL

?? ?sltnode* pcur = *pphead;
?? ?while (pcur)//依次销毁头结点的循环
?? ?{
?? ??? ?sltnode* next = pcur->next;//在pcur指针后创建一个指针next
?? ??? ?free(pcur);
?? ??? ?pcur = next;
?? ?}
?? ?*pphead = NULL;
}

封面?