上一期一起学习了数据结构初阶的顺序表,发现顺序表有一些致命的缺点,比如部分操作时间复杂度高,还是会存在空间浪费的现象,今天为大家介绍的单链表就可以完美地解决这个问题。
还是和顺序表一样创建3个文件:
Seqlist.h: 头文件,放入结构体和函数的声明。
Seqlist.c:函数接口文件,用来存放函数的定义。
test.c: 测试文件,在写代码过程中用来测试函数的可行性。
顾名思义,单链表就是将各个节点像链子一样连起来,每个节点只放一个数据,这样就完美解决了空间浪费地问题,具体地声明如下:
这样我们地数据就像下图一样被连接了起来:
下面就为大家介绍如何在这个链表中进行操作:
如果要对这个链表进行添加数据,必定需要开辟一个空间创造一个节点,所以就需要这么一个函数来实现,代码如下:
SLNode* CreatNew(SListDatetype x)//创建一个新节点,并放入数据x
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
perror("malloc");
return 0;
}
newnode->a = x;
newnode->next = NULL;
return newnode;
}
注意:默认链表的最后一个next指向NULL。
链表的打印和顺序表差不多,不再过多赘述,这里我加上->来区分:
void SLprintf(SLNode* phead)//打印链表
{
assert(phead);
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->a);
cur = cur->next;
}
printf("NULL\n");
}
特别注意:这个函数要修改链表,所以要传二级指针
在尾部插入数据,必定先要创建一个节点,然后使用一个临时结构体变量来找链表的尾部,再令尾部的next指向新节点即可。
注意:当一开始没有节点时要另外讨论,直接赋值即可:
void SLinsertback(SLNode** pphead,SListDatetype x)//尾插
{
SLNode* newnode = CreatNew(x);
if (*pphead == NULL)//如果一开始没节点
{
*pphead = newnode;//直接赋值
}
else
{
SLNode* tail = *pphead;
while (tail->next != NULL)//找尾
{
tail = tail->next;
}
tail->next = newnode;
}
}
放入test.c中测试一下:
完美实现!
在头部插入数据,思路跟尾插差不多,要将*pphead指向新节点,并将新节点的next指向原来的第一个节点:
void SLinserthead(SLNode** pphead, SListDatetype x)//头插
{
SLNode* newnode = CreatNew(x);
newnode->next = *pphead;
*pphead = newnode;
}
测试如下:
完美实现!
在尾部删除一个节点,需要先创建一个临时局部结构体变量tail来找尾,可以用一个while循环来实现,找到尾部节点后,free这个节点然后令倒数第二个节点的next指向NULL:
注意:如果只有一个节点直接free它然后令*pphead为NULL即可:
void SLdelback(SLNode** pphead)//尾删
{
assert(pphead);
SLNode* tail = *pphead;
if (tail->next==NULL)//一个节点
{
free(*pphead);
*pphead = NULL;
}
else//多个节点
{
SLNode* prev = NULL;
while (tail->next != NULL)//找尾
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}
测试如下:
完美实现!
在头部删除数据,和尾删思路差不多,令phead指向第一个数据的next,再free第一个数据:
void SLdelhead(SLNode** pphead)//头删
{
assert(pphead);
SLNode* tail = *pphead;
*pphead = tail->next;
free(tail);
tail = NULL;
}
测试如下:
完美运行!
在链表中查找数据,然后返回这个数据的结构体地址,这个函数可以辅助后面指定数据进行操作函数的实现,遍历这个链表即可:
SLNode* SLfind(SLNode* phead, SListDatetype x)//查找
{
assert(phead);
SLNode* cur = phead;
while (cur)
{
if (cur->a == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
这个函数需要先用查找函数,找到这个数据的结构体地址,再进行操作·,由于是在前面插入函数,单靠一个pos是访问不到上一个数据的,所以用一个prev来先找到pos的前一个数据的结构体地址,思路图如下:
注意:如果链表只有一个节点,就可以直接头插:
void SLinsertpointh(SLNode** pphead, SLNode* pos, SListDatetype x)//在指定数据前插入x
{
// 严格限定pos一定是链表里面的一个有效节点
assert(pphead);
assert(pos);
assert(*pphead);
if (*pphead == pos)
{
// 头插
SLinserthead(pphead, x);
}
else
{
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLNode* newnode = CreatNew(x);
prev->next = newnode;
newnode->next = pos;
}
}
测试如下:
完美实现!
由于pos可以通过->next访问后面的数据,所以这个函数相对简单,思路图如下:
void SLinsertpointb(SLNode** pphead, SLNode* pos, SListDatetype x)//在指定数据后插入x
{
assert(pphead);
assert(pos);
assert(*pphead);
SLNode* newnode = CreatNew(x);
if (pos->next == NULL)//如果pos指向最后一个数据
{
SLinsertback(pphead, x);//尾插
}
else
{
newnode->next = pos->next;
pos->next = newnode;
}
}
测试如下:
先用查找函数找到该数据的地址,然后将这个数据前一个数据的next指向这个数据的下一个数据的结构体地址,然后free掉pos就行:
void SLdelpoint(SLNode** pphead, SLNode* pos)//删除指定数据
{
assert(pphead);
assert(pos);
assert(*pphead);
if (pos->next == NULL)//如果为最后一个数据
{
SLdelback(pphead);//尾删
}
SLNode* prev = *pphead;
while (prev->next != pos)//找到pos的前一个
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
测试如下:
遍历free节点即可:
void SLTDestroy(SLNode** pphead)
{
assert(pphead);
SLNode* cur = *pphead;
while (cur)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
最后这样一个单链表的一些基本操作就可以实现了,火速动手实现吧!