C语言实现——单链表-创新互联
单链表就是利用指针和结构体对数据的一种存储和管理模式,定义一个结构体变量,成员一个用于存放数据,一个是用于链接下一个数据的指针,每一个独立的结构体变量在单链表中通常被叫作节点,一个个节点通过指针相连,像一个链子一样,清楚定义的前提下,结合图形去一一实现这个链表的定义和增删查改。
创新互联公司自2013年起,先为恒山等服务建站,恒山等地企业,进行企业商务咨询服务。为恒山企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。二、单链表的定义 1.节点的声明(结构体的声明)节点要包含一个放数据的成员和指向下一个节点的指针:
#define SLT_Data_Type int//方便更改链表的数据类型
typedef struct SLT
{
SLT_Data_Type data;//数据
struct SLT* next;//指针
}SLT;
2.节点的定义由于节点的开辟是个重复多次的动作,在后面的增加数据也要用,因此将开辟节点分装成一个函数
SLT* Buy_SLT_Data(SLT_Data_Type k)//开辟节点
{
SLT* p=(SLT*)malloc(sizeof(SLT));
if(p==0)
{
perror("malloc error");
exit(-1);
}
p->data=k;
p->next=NULL;
return p;
}
参数是在节点放的数据,将指针默认指向NULL,最后返回开辟好节点的地址。
3.链表的定义我们定义一个函数,参数为我们想要一次性开辟的节点数,由这个函数实现将节点串联起来,由于为了方便调试,因此数据上一开始先不采用自主输入的方式,最后返回链表的头地址。
SLT* InitSLT(int n)//创建链表
{
int i;
SLT* phead=NULL;
SLT* fail=NULL;
for(i=0;inext=Buy_SLT_Data(i);
fail=fail->next;
}
}
return phead;
}
三、打印链表为了方便调试和展示效果,我们先将链表的打印实现,由一个指针,从头开始,打印一个后,找到下一个继续打印,直到该指针指向空即为结束。
void SLTPrint(SLT* phead)
{
SLT* fail=phead;
while(fail)
{
printf("%d ->",fail->data);
fail=fail->next;
}
printf("NULL\n");
}
四、尾插与尾删
1.尾插先考虑边界条件,若链表为空可以尾插吗?
可以,但如果链表为空,意味着要改变最开始的地址,而最开始的地址作为形参传到函数中是不够的,要使用二级指针去对最初的地址进行操作。
考虑好边界条件以后,若列表不为空,所有的其他情况是否采用同一套逻辑执行?
是的,因此我们将情况分成两种,一个是当头地址为空,我们将用二级指针对头地址进行更改为新开辟的节点,若头地址不为空,我们将找到最后一个节点,将新开辟的节点进行链接。
void SLTPushBack(SLT** pphead,SLT_Data_Type k)
{
SLT* tail=*pphead;
SLT* newdata=Buy_SLT_Data(k);
if(*pphead == NULL)//空链表
{
*pphead=newdata;
}
else
{
while(tail->next)//找到最后一个节点
{
tail=tail->next;
}
tail->next=newdata;
}
}
2.尾删还是优先考虑下边界条件,当链表为空,能不能删?
不能删,因此我们要对空的头地址进行断言
当链表只有一个节点的时候,我们要删除的是最初传入的地址,因此对头地址需要修改,要穿二级指针,因此同样分两种逻辑。
当只有一个的时候,对二级指针进行操作,删除外面的头地址指向的空间,并且要把地址置空
当多个的时候,用指针遍历到倒数第二个,先将下一个数据空间释放,再将next指针指向空。
void SLTPopBack(SLT** pphead)
{
SLT *tail=*pphead;
assert(*pphead);
if((*pphead)->next == NULL)
{
free(*pphead);
*pphead==NULL;
}
else
{
while(tail->next->next)
{
tail=tail->next;
}
free(tail->next);
tail->next=NULL;
}
}
五、头插和头删
1.头插先考虑边界条件,若为空链表可以头插吗?
可以,而且每次头插本质上都是更改头地址,因此也是要用二级指针,我们将新开辟的节点直接链接到原先的头地址上,并且将头地址更新即可
void SLTPushFront(SLT** pphead,SLT_Data_Type k)//头插
{
SLT* newhead=Buy_SLT_Data(k);
newhead->next=*pphead;
*pphead=newhead;
}
2.头删考虑边界情况,空链表可以删除吗
显然不能,因此应该加上断言,只有一个的情况能删除吗?
可以,而且头删都会改变头地址,因此得传二级指针
void SLTPopFront(SLT** pphead)//头删
{
SLT* newhead=(*pphead)->next;
assert(*pphead);
free(*pphead);
*pphead=newhead;
}
六、指定数后插和后删
1.查找由于链表的地址不连续,要实现指定数位置的后插和后删,我们都需要先找到这个数的地址,因此我们先分装出个函数,专门实现对指定数字进行查找的。
查找的思路就是那一个指针去遍历整个链表当找到的时候返回地址,当没找到的时候,我们返回空指针,同样考虑边界问题,空链表不能被查找,又或者查找以后返回NULL(这个是否选择要断言可根据自己选择设计)
SLT* SLTFine(SLT* phead,SLT_Data_Type n)
{
SLT* cur=phead;
assert(phead);
while(cur)
{
if(cur->data==n)
return cur;
cur=cur->next;
}
return NULL;
}
2.指定数后插我们要在指定的数字后插入,首先我们应该要传参的时候给到指定的数或者指定数的地址,从用户的角度上考虑,我这里参数选择是给指定的数。
同样我们要考虑边界问题,当链表为空时,可以指定数字插入吗?实际上我们压根就找不到这个数,更别说后插了,再者,如果我们找不到指定数的地址,也就是返回的是空指针,说明这个数不存在链表或者链表为空,因此我们需要对指定数的地址进行断言
接下来就是设计如何进行一般情况下的链接
通过画图,我们可以看到,指定位置的next一开始指向的地方,如果我们不注意赋值的顺序,就可能会丢失地址信息,图中1和2的顺序不可逆,实在要反过来,就得创建临时变量去存指定位置next的地址。
void SLTInsertAfter(SLT* phead,SLT_Data_Type n,SLT_Data_Type k)
{
SLT* newdata=Buy_SLT_Data(k);//新的节点
SLT* pn=SLTFine(phead,n);//插入的位置在该地址后一位
assert(pn);//找不到位置
//链接
newdata->next=pn->next;
pn->next=newdata;
}
2.指定后删指定位置往后删除,我们同样传指定位置的数字,在函数内部找地址,同样,如果找不到,什么可能是空链表或者没有这个指定的数,因此也需要断言
而接下来是这个功能的设计考虑,我们要删除一个指定位置的后一位,我们还得将该位置的后两位的节点往前链接上来,因此我们的边界考虑,出来空链表的情况,还有假如只有一个节点,删除该节点的后一节点,相当于什么都不做,或者也可以断言警告它后面没东西可以删。
此外,一般情况的逻辑
1.将指定位置的后两位节点指针(指定位置的next的next)交给一个临时变量指针存着
2.通过指定位置的next找到要删除的节点,free掉该空间
3.将临时指针里存放的地址给到指定位置的next进行链接
void SLTEraseAfter(SLT* phead,SLT_Data_Type n)
{
SLT* pn=SLTFine(phead,n);//删除该位置的下一个节点
SLT* cmp=NULL;
assert(pn && pn->next);//找不到或者要删的下一个是个空的
cmp=pn->next->next;
free(pn->next);
pn->next=cmp;
}
七、指定删除大家可能再刚学到指定位置往后增删的操作的时候,会有些不理解,插入也就算了,为什么删除不是指定哪个就删哪个,而要删后一个呢?
我们假设现在要实现指定位置删除,那么我们同样的需要指定数字的地址,函数参数的设计上和是一个指定后删没差别
考虑边界情况,空链表和找不到指定删除的数字时,都是没办法删除的,空链表必然找不到指定数字,因此断言指定数字的地址即可
此外指定位置为头位置时,我们也需要对头地址进行更改,因此需要二级指针
除开头地址的删除,就是一般情况下的指定删除,我们通过画图设计实现思路
我们看着图思考,假设要删除指定的节点,我们删完后还需要将它的前后两个链接起来,但是目前我们只能知道的是传参的头地址和指定位置的地址,因此相比于指定位置后一位删除,这个指定删除要一个指针去遍历一遍链表,找到指定位置的前一个地址,才能完成链接,在数据较多的情况下,效率上肯定是低于删后一项的,但对于用户使用上却是更加方便的。
实现思路:
1.分逻辑,如果指定位置是头位置,单独一个逻辑删除头位置后,将新的头地址用二级指针传给链表开头。
2.如果不是头地址,先用一个指针遍历链表找到指定位置的前一项
3.指定位置前一项记录下指定位置的后一项(链接)
4.释放指定位置的空间(删除)
void SLTErase(SLT** pphead,SLT_Data_Type n)
{
SLT* pn=SLTFine(*pphead,n);//要删除的位置
SLT* cur=*pphead;
assert(*pphead);
if(pn == cur)//头删
{
SLTPopFront(pphead);
}
else//若要删除位置不在头
{
while(cur->next != pn)//找到删除位置的前一个
cur=cur->next;
cur->next=pn->next;
free(pn);
}
}
八、销毁链表在使用完链表后,由于动态开辟的内存是堆上的空间,因此我们还需要对链表的空间进行释放,
释放链表就是两个指针并肩走的思路(该思路在很多题目和操作中十分重要)
void SLTDeastroy(SLT** pphead)
{
SLT* tail=NULL;
if(*pphead == NULL)
return;
tail=(*pphead)->next;
free(*pphead);
*pphead=NULL;
while(tail)
{
SLT* pnext=tail->next;
free(tail);
tail=pnext;
}
}
总结本篇用C语言实现了一个最基本的单链表,逐步对每一步进行了分析和设计,捋清楚了链表的实现思路,并且附上了代码,如果有哪里不足,欢迎大家指出。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站名称:C语言实现——单链表-创新互联
网页网址:http://scyanting.com/article/cdgpgs.html