您现在的位置是:首页 >技术教程 >数据结构--不带头的单向链表网站首页技术教程
数据结构--不带头的单向链表
不带头的单向链表
链表的结构
分为物理结构和逻辑结构。物理结构是在内存中实实在在的是怎么存储的。逻辑结构是为了方便理解,形象化画出来的。
下面通过链表打印函数,来理解链表的逻辑结构。
SLTNode* cur = phead;
把phead变量里的地址给到了cur,cur里面存放的是phead变量里的地址0x12ffa,这时候我们就认为cur指向了第一个结点,
实际上cur一直没有像逻辑结构里面那样,在结点中变动后移。
cur->data
cur是一个结构体指针,通过结构体的规则,取到data变量里的内容,
cur = cur->next;
通过结构体的规则,取到next变量中的内容,也就是地址0x0012ffb0,并将其给到cur,这时候我们就认为cur指向了第2个结点,
依次类推,cur被不断赋值。当cur里面放置0x0012ffd0的时候,这时候cur指向最后一个结点,
cur不等于NULL,进入循环,打印出最后一个结点的data,之后,取到next变量中的内容,也就是NULL(0x00000000),并将其给到cur,
再进入循环条件cur==NULL,循环停止。
注意点(贯穿于整个链表的注意事项)
以下注意事项涉及各个接口。是一个问题汇总。
1 链表打印函数和顺序表打印函数中的phead和ps,为什么一个需要assert,另一个不需要?
- phead指向第一个存有数据的结点,当存在空链表时,phead=NULL;空链表也是链表,因此不需要assert;
- 顺序表的指针指向一个结构体,顺序表中的数据不是存放在结构体上的,而是存放在其成员指针所指向的空间,其数据为空,表示size为0,只要size不为0,就存在数据。即使当顺序表为空时,结构体的指针也不能为NULL,因此,ps不能为空。
2 在打印链表的函数中为什么不能使用cur++
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur!=NULL)
{
printf("%->",cur->data);
//cur = cur->data;
cur++; x
}
printf("NULL
");
}
- 对于顺序表而言,其存放数据的空间是一个连续的空间,指针++,就可以找到下一个数据所在的位置;
- 对于链表来说,其每一个结点都是malloc函数单独开辟的一段空间,其地址不一定是连续的,即使指针能够++,但是在这里也是无效的,无法找到下一个结点的地址。
3 cur->data,结构体的指针加上->data,取到的data的内容。
4 如果在打印链表的函数中的while判断语句改为cur->next!=NULL
,他会判断当前结点的下一个结点的地址是否为NULL,而不是在判断当前结点的地址是否为NULL,当链表走到最后一个结点时,由于下一个结点的地址为空,因此,他不会打印这个结点的数据,会造成少打印一个结点的数据。
5 指针,是一个变量,这个变量的内容是地址。对指针赋值,就是放一个地址进去,对指针解引用,
∗
*
∗p,就是得到这个地址上(也就是一个指针所指向的)空间的内容。用于理解链表的结构。
6 下面关于尾插中的
SLTNode* tail = phead;
while (tail!=NULL)
{
tail = tail->next;
}
tail = newnode;
tail的赋值方式是不对的。因为无法将链表链接起来。
根据链表的结构,分析如下:
假设我们新创建的结点的data为6,新结点的newnode地址为0x0012ffe0。根据代码赋值语句SLTNode* tail = phead;
,将phead中的地址赋值给tail,则tail中存放的是0x12FFA0;
进入循环,依次类推,当tail中存放的地址为0x0012ffc0时,来到最后一个结点,此时tail不为NULL,进入循环,取到next变量中的内容,也就是地址0x00000000(NULL),并将其给到tail
再判断循环条件,不成立,执行语句tail = newnode;
newnode中存放的是地址0x0012ffe0,将其赋值给tail,那么tail中存的就是0x0012ffe0。
但是,虽然过程没有问题,但tail是一个局部变量,出了尾插函数后不起作用。这样并没有起到链接起来的作用。链接起来的意思是上一个结点的next存放下一个结点的地址。要改变的是结构体的内容。正确的写法如下:
SLTNode* tail = phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
虽然tail是一个局部变量,但是tail指向的是一个结构体,是让结构体的next指针指向newnode,next中存放的是newnode 的地址。改变了结构体的内容。
7 对于函数调用中的传值和传地址。无论时传值还是传地址,形参都是实参的一份拷贝。对于拷贝地址来说,就是将地址放到了形参中。
- 传递变量,形参是变量的临时拷贝;
- 传递地址,形参是地址的拷贝。
想要改变int,得传递int的地址,即int
∗
*
∗;
想要改变int
∗
*
∗,得传递int
∗
*
∗的地址,int
∗
∗
**
∗∗二级指针
以下图main函数为例,传递px,传的是px的地址,那么ptr中放的是px的地址,改变ptr的值,不会影响px,因为会把px的地址给覆盖掉。
想要改变px的值,可以进行如下操作
关于上图的分析如下
8 关于尾插中的头指针在函数做实参时的一个问题。
将尾插函数写好后,如下:
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
//申请一个新结点
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
if (newnode==NULL)
{
perror("malloc fail");
return;
}
//对结点初始化
newnode->data = x;
newnode->next = NULL;
//找尾
if (phead==NULL)
{
phead = newnode;
}
else
{
SLTNode* tail = phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
通过TestSLTList1()函数,在主函数中调用并打印。
void TestSLTList1()
{
SLTNode* plist = NULL;
SLTPushBack(plist, 1);
SLTPushBack(plist, 2);
SLTPushBack(plist, 3);
SLTPushBack(plist, 4);
SLTPrint(plist);
}
程序结果并没有产生我们想要的结果。
分析可参考7
分析如下:
因此,我们需要修改使用二级指针
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//申请一个新结点
SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));
if (newnode==NULL)
{
perror("malloc fail");
return;
}
//对结点初始化
newnode->data = x;
newnode->next = NULL;
//找尾
if (*pphead==NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void TestSLTList1()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
对二级指针的关键语句分析如下:
可以看到如下结果:
9 pphead的二级指针和tail的一级指针
上面的左图,函数的形参是二级指针,当pphead为NULL,我们是对二级指针解引用进行赋值;当pphead不为NULL时,我们是用一级指针tail(因为是结构体指针,可以使用->来得到结构体成员的内容,这里可以理解为解引用)解引用进行赋值,如上面右图所示。这里可以理解为当需要改变头指针的内容(即头结点的地址)时,使用二级指针;当需要改变结点间的地址(即是改变结构体的内容),使用一级指针.
10 单链表不适合在前面插入,因为需要从头指针处开始遍历.单链表适合在pos位置后插入,它不需要头指针来进行遍历。删除也是同理。
11 关于pphead,
∗
*
∗pphead,phead是否需要断言
- 在查找函数中,不需要对phead断言,这是因为会存在空链表的情况,空链表也是可以打印的。
- 在pos位置之前插入函数中,需要对pphead进行断言,因为传递过来的&plist永远不会为空。
- 在尾插函数中,需要对pphead进行断言,不需要对 ∗ * ∗pphead(此时 ∗ * ∗pphead为plist)断言,因为空链表可以尾插。
- 在头插函数中,需要对pphead进行断言,不需要对 ∗ * ∗pphead(此时 ∗ * ∗pphead为plist)断言,因为空链表可以头插。
- 在尾删函数中,需要对pphead进行断言,需要对 ∗ * ∗pphead(此时 ∗ * ∗pphead为plist)断言,因为空链表不可以删除。先检查pphead,再检查 ∗ * ∗pphead,即:
assert(pphead);
assert(*pphead);
等。
12 在pos位置之后插入的函数中,下面代码的写法是不正确的
SLTNode* newnode = BuySTLNode(x);
pos->next = newnode;
newnode->next = pos->next;
其中, pos->next = newnode; newnode->next = pos->next;
的顺序不能颠倒,这里会造成newnode结点的死循环。
13 在pos之后删除的函数中,pos->next = pos->next->next;
单独写这句代码是不正确的,因为对pos->next进行赋值后,原来的pos->next所指向的结点会丢失,无法对其执行free操作。可以改为以下代码:
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
结点类型的定义
typedef int SLTDataType;//为了方便改变数据的类型
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
这里的next是下一个结点的地址。
- 如果将
struct SListNode* next;
换成SListNode* next
,在c语言中是不允许的,但是在c++中是可行的。 - 如果将
struct SListNode* next;
换成SLTNode* next
,是不起作用的。SLTNode在结构体后面才定义的,不符合结构体的查找类型。
申请新结点函数
SLTNode* BuySTLNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
//对结点初始化
newnode->data = x;
newnode->next = NULL;
return newnode;
}
链表的打印
只需要传递头指针;
此函数内不需要断言phead,因为存在空链表时,phead=NULL;
空的顺序表也可以打印,只是不存在数据;
空链表也可以打印;
cur是一个变量,他里面存放的是当前结点的地址。
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur!=NULL)
{
printf("%->",cur->data);
cur = cur->next;
}
printf("NULL
");
}
这里的while (cur!=NULL)
,也可以直接换成while (cur)
链表的尾插
创建一个新的结点,并对结点里的data和next进行初始化。
找尾;
这里创建一个指针变量tail用于寻找尾,尾的特征是tail->next=NULL
尾插的本质:原尾结点中要存储新的尾结点的地址。
如果是一个空链表,就可以直接将newnode的地址给到phead;
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySTLNode(x);
//找尾
if (*pphead==NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
链表的头插
当为空链表的时候,下列代码也是成立的。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySTLNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
链表的尾删
在tail走到下一个结点之前,定义一个变量prev用来存储tail在当前结点的地址,以便于在删除最后一个结点之后,改变倒数第二个结点的内容next。
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
或者使用tail->next->next。
在使用tail->next->next,我们分为3种情况:
1 空链表,
2 只有一个结点 ,
3 有两个以及以上个结点。
void SLTPopBack(SLTNode** pphead)
{
//SLTNode* prev = NULL;
//SLTNode* tail = *pphead;
//while (tail->next != NULL)
//{
// prev = tail;
// tail = tail->next;
//}
//free(tail);
//tail = NULL;
//prev->next = NULL;
//空链表
assert(*pphead);
//单个结点
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//多个结点
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
链表的头删
需要断言空链表,不需要判断一个结点的情况,这里可以用一个first结点来记录第一个结点,以便找到第一个结点的next
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
链表的查找和修改
遍历链表,找到指定结点内的值后,返回该结点,利用结构体指针,将结构体的内容进行变动。
查找:
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
SLTNode* cur = *pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
修改:
SLTNode* ret=SLTFind(&plist, 3);
ret->data = 6;
SLTPrint(plist);
结果如下:
在pos之前插入
因为在pos之前插入,需要判断前面一个结点的next是否等于pos,因此,需要保证pos位置之前必须要有结点;
当pos之前没有结点的时候,此时的插入就是头插。因此,在pos之前插入可以分为头插和任意位置(除去头插和尾插,头插和尾插调用专门的函数)的插入;
这里我们用prev遍历,直到它为pos前面的那一个结点。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos==*pphead)
{
SLTPushFront(pphead,x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySTLNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
因为我们是在结构体指针pos之前插入,可以先利用find函数找到某个数据对应的结点(结构体)指针。如下,
SLTNode* ret = SLTFind(&plist, 3);
SLTInsert(&plist, ret, 11);
SLTPrint(plist);
结果如下:
在pos位置删除
因为在pos位置删除需要找到前一个结点,因此,这里分为pos为pos为头结点和其它位置的结点。
在将pos结点删除后,需要将其指向NULL,不能再函数的内部赋值,要想改变pos,因为传递的是pos的值,只有在函数的外部赋NULL。
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead==pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
SLTNode* ret = SLTFind(&plist, 3);
SLTErase(&plist, ret);
ret = NULL;
SLTPrint(plist);
运行结果如下:
在pos之后插入(通过交换值,达到在pos之前插入的目的)–没有头指针
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySTLNode(x);
SLTDataType temp;
temp = newnode->data;
newnode->data = pos->data;
pos->data = temp;
newnode->next = pos->next;
pos->next = newnode;
}
SLTNode* ret = SLTFind(&plist, 3);
SLTInsertAfter(ret, 111);
SLTPrint(plist);
结果如下:
在pos位置后面删除(通过交换值,达到删除pos位置的目的)–没有头指针
因为是需要和pos后面的那个结点交换数值的,所以要求pos->next不能为NULL;
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTDataType temp;
temp = pos->next->data;
pos->next->data = pos->data;
pos->data = temp;
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
SLTNode* ret = SLTFind(&plist, 3);
SLTEraseAfter(ret);
SLTPrint(plist);
运行结果如下:
全部代码
测试函数
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void TestSLTList1()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
void TestSLTList2()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushFront(&plist, 5);
plist = NULL;
SLTPushFront(&plist, 6);
SLTPrint(plist);
}
void TestSLTList3()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushFront(&plist, 5);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
void TestSLTList4()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPopFront(&plist);
SLTPrint(plist);
}
void TestSLTList5()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* ret=SLTFind(&plist, 3);
ret->data = 6;
SLTPrint(plist);
}
void TestSLTList6()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* ret = SLTFind(&plist, 3);
SLTInsert(&plist, ret, 11);
SLTPrint(plist);
}
void TestSLTList7()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* ret = SLTFind(&plist, 3);
SLTErase(&plist, ret);
ret = NULL;
SLTPrint(plist);
}
void TestSLTList8()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* ret = SLTFind(&plist, 3);
SLTInsertAfter(ret, 111);
SLTPrint(plist);
}
void TestSLTList9()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* ret = SLTFind(&plist, 3);
SLTEraseAfter(ret);
SLTPrint(plist);
}
int main()
{
//TestSLTList1();
//TestSLTList2();
//TestSLTList3();
//TestSLTList4();
//TestSLTList5();
//TestSLTList6();
//TestSLTList7();
//TestSLTList8();
TestSLTList9();
return 0;
}
函数定义
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL
");
}
SLTNode* BuySTLNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
//对结点初始化
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySTLNode(x);
//找尾
if (*pphead==NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySTLNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
//SLTNode* prev = NULL;
//SLTNode* tail = *pphead;
//while (tail->next != NULL)
//{
// prev = tail;
// tail = tail->next;
//}
//free(tail);
//tail = NULL;
//prev->next = NULL;
//空链表
assert(*pphead);
//单个结点
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//多个结点
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
SLTNode* cur = *pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos==*pphead)
{
SLTPushFront(pphead,x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySTLNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead==pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySTLNode(x);
SLTDataType temp;
temp = newnode->data;
newnode->data = pos->data;
pos->data = temp;
newnode->next = pos->next;
pos->next = newnode;
}
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTDataType temp;
temp = pos->next->data;
pos->next->data = pos->data;
pos->data = temp;
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
函数声明
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;//为了方便改变数据的类型
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);//打印链表只需要传递头指针
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//查找
void SLTInsert(SLTNode** pphead, SLTNode* pos ,SLTDataType x);//在pos之前插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//在pos位置处删除
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
void SLTEraseAfter(SLTNode* pos);//在pos之后删除