C语言详解无头单向非循环链表各种操作方法

第C语言详解无头单向非循环链表各种操作方法目录链表引入链表介绍创建链表打印链表创建结点单链表尾插单链表头插单链表尾删单链表头删在pos位置之前插入数据在pos位置之后插入数据删除pos位置结点删除pos位置之后的结点销毁链表链表查找

链表引入

问：上次我们看了顺序表，那么顺序表有些什么优缺点呢？

优点：

顺序表是连续的物理空间，方便下标的随机访问。

缺点：

1.增容需要申请新空间，拷贝数据，释放旧的空间。会有一定消耗。

2.头部或者中间位置插入或者删除数据，需要挪动数据，效率较低。

3.可能存在一定空间占用，浪费空间，不能按需申请和释放空间。

为了解决上诉问题，我们引入了链表。首先我们先来看看单链表。

链表介绍

链表是一种物理存储结构上非连续、非顺序的存储结构、数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个节点包含两部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

实际上，链表的结构多样，如下：

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

创建链表

链表是由结点链接而成的，所以创建链表需要创建一个结点类型。该类型由指针域和数据域组成。

typedefintSLTDataType;

typedefstructSListNode

SLTDataTypedata;//用来存放该结点的数据

structSListNode*next;//用来存放下一个结点的地址

}SListNode;

打印链表

从头指针指向的位置开始，依次向后打印，知道cur访问到NULL就结束循环。

voidSListPrint(SListNode*phead);

voidSListPrint(SListNode*phead)

SListNode*cur=phead;//我们一般不会改变头指针，所以我们把头指针赋值给cur

while(cur)//链表结束条件

printf("%d-",cur-data);

cur=cur-next;

printf("NULL\n");//表示数据已经打印完毕

}

创建结点

每当我们需要插入一个数据，我们就需要申请一个结点，如果每次都重新申请就会很麻烦，所以我们将创建一个新结点封装为一个函数。

SListNode*BuySListNode(SLTDataTypex)

SListNode*newnode=(SListNode*)malloc(sizeof(SListNode));

if(newnode==NULL)

printf("BuySListNode::%s\n",strerror(errno));//若申请失败，则打印错误信息

exit(-1);

else

newnode-data=x;//将数据赋值到新点的数据域

newnode-next=NULL;//新结点指针域置为空指针

returnnewnode;//返回新结点的地址

}

单链表尾插

我们需要将尾插分为两种情况：

情况一：链表为空，我们直接让头指针指向新的结点即可。

情况二：链表已经有多个结点，我们需要找到链表的最后一个结点，然后让最后一个结点指向新的结点。

voidSListPushBack(SListNode**pphead,SLTDataTypex);

voidSListPushBack(SListNode**pphead,SLTDataTypex)

assert(pphead);

SListNode*newnode=BuySListNode(x);

//链表为空

if(*pphead==NULL)

*pphead=newnode;//头指针指向新的结点

//链表不为空

else

SListNode*tail=*pphead;

while(tail-next!=NULL)

tail=tail-next;

tail-next=newnode;

}

注意：链表头插函数的参数我们应该传头指针的地址，而不是头指针本身。如果为传值调用，那么形参是实参的一份临时拷贝，对形参的改变不会影响实参。

单链表头插

单链表头插时，我们申请一个新的结点，然后让新结点的指针域指向之前的第一个结点，然后让头指针指向新结点。

注意：这两步操作的顺序不可以颠倒，如果先让头指针指向了新结点，那么将不可能找到第一个结点的位置了。也不可能在找到后面的数据了。

voidSListPushFront(SListNode**pphead,SLTDataTypex);

voidSListPushFront(SListNode**pphead,SLTDataTypex)

assert(pphead);

SListNode*newnode=BuySListNode(x);

newnode-next=*pphead;

*pphead=newnode;

}

单链表尾删

演示一种错误的写法：

对于单链表的尾删，我们需要考虑三种情况：

1.链表为空时，不做任何处理。

2.链表只有一个结点时，释放该结点，然后将头指针置为空。

3.链表有多个结点时，有两种处理方法，详见一下代码。

代码一：找到最后一个结点的前一个结点，释放最后一个结点。将前一个结点的指针域置为空指针。

voidSListPopBack(SListNode**pphead);

voidSListPopBack(SListNode**pphead)

assert(pphead);

if(*pphead==NULL)

return;

elseif((*pphead)-next==NULL)

free(*pphead);

*pphead=NULL;

else

SListNode*prev=NULL;

SListNode*tail=*pphead;

while(tail-next!=NULL)

prev=tail;

tail=tail-next;

free(tail);

tail=NULL;

prev-next=NULL;

}

代码二：找到最后一个结点的前一个结点，将后一个结点释放掉，然后在置为空就可以了。

voidSListPopBack(SListNode**pphead);

voidSListPopBack(SListNode**pphead)

assert(pphead);

if(*pphead==NULL)

return;

elseif((*pphead)-next==NULL)

free(*pphead);

*pphead=NULL;

else

SListNode*tail=*pphead;

while(tail-next-next!=NULL)

tail=tail-next;

free(tail-next);

tail-next=NULL;

}

单链表头删

若链表为空，则不处理。若链表不为空，让头指针指向第二个结点，释放掉第一个结点。

voidSListPopFront(SListNode**pphead);

voidSListPopFront(SListNode**pphead)

assert(pphead);

if(*pphead==NULL)//链表为空

return;

else

SListNode*head=*pphead;

*pphead=head-next;//让头指针指针域中的地址指向头指针

free(head);//释放第一个结点

head=NULL;

在pos位置之前插入数据

若pos是第一个结点，我们直接调用之前写的头插。若pos不是第一个结点，我们找到pos位置的前一个结点，让新的结点指向地址为pos的结点，然后让前一个结点指向新结点。

voidSListInsertBefore(SListNode**pphead,SListNode*pos,SLTDataTypex);

voidSListInsertBefore(SListNode**pphead,SListNode*pos,SLTDataTypex)

assert(pphead);

assert(pos);

if(*pphead==pos)

SListPushFront(pphead,x);//头插函数

else

SListNode*prev=*pphead;

while(prev-next!=pos)//找到pos的前一个结点

prev=prev-next;

SListNode*newnode=BuySListNode(x);

newnode-next=prev-next;//让新结点指向pos结点

prev-next=newnode;//让前一个结点指向新结点

}

在pos位置之后插入数据

让新结点指向该位置的下一个位置，然后让该位置的结点指向新结点。

voidSListInsertAfter(SListNode**pphead,SListNode*pos,SLTDataTypex);

voidSListInsertAfter(SListNode**pphead,SListNode*pos,SLTDataTypex)

assert(pphead);

SListNode*newnode=BuySListNode(x);

newnode-next=pos-next;

pos-next=newnode;

}

删除pos位置结点

voidSListErase(SListNode**pphead,SListNode*pos);

voidSListErase(SListNode**pphead,SListNode*pos)

assert(pphead);

assert(pos);

if(*pphead==pos)

SListPopFront(pphead);

else

SListNode*prev=*pphead;

while(prev-next!=pos)

prev=prev-next;

prev-next=pos-next;

free(pos);

pos=NULL;

}

删除pos位置之后的结点

voidSListEraseAfter(SListNode*pos);

voidSListEraseAfter(SListNode*pos)

assert(pos);

SListNode*next=pos-next;

if(next)//如果next不为空，则条件为真

pos-next=next-next;//让pos指向要删除位置的后一个结点

free(next);//释放pos的下一个结点

next=NULL;

}

销毁链表

在销毁链表时。首先我们将头指针赋值给一个新的指针，用该指针依次遍历链表，先把该结点的下一个结点的地址保存，然后在释放该结点，最后将头指针置为空。

注意：一定要在释放该指针之前保存该指针的下一个结点的地址，否则就找不到下一个结点了。

voidSListDestroy(SListNode**pphead);

voidSListDestroy(SListNode**pphead)

assert(pphead);

SListNode*cur=*pphead;

while(cur)

SListNode*next=cur-next;//存放下一个结点地址

free(cur);//释放当前结点

cur=NULL;

*pphead=NUL