理解链表,你才真正懂得C语言指针

大家好,今天跟大家分享数据结构中链表的学习方法,下面直接进入正题。

首先,我们来看一下链表的基本单元——节点。节点结构体的定义如下:

//节点结构体

typedef struct node{

u32 num;//数据

struct node *next;//指向下一节点

}Node;

定义了struct node结构体类型,并通过typedef将其等价为Node类型。这个Node类型由两部分构成,一个32位无符号变量num(当然不一定非得是一个),和一个指向下一节点的指针,该指针与其自身的数据类型相同。如果对此有点疑惑,不用太纠结,只要知道C语言允许这样定义就ok了。

为了方便,把Node*指针类型定义为List,如下:

typedef Node* List;//节点指针,(如果是第一个节点指针,就称之为链表指针)

接下来,我们只要建立节点与节点的联系,使前一节点指向后一节点,那么我们便可以得到一条完整的单向链表了。

在主程序中,我们通常以下面的方式来初始化一个链表:

void main()

{

List begin=NULL;//初始化

AddEndNode(&begin,9);//添加尾节点

......

}

即声明一个指向空(NULL)的链表指针——首指针begin。

然后,我们需要编写函数来向该空链表中添加节点。

AddEndNode函数如下:

//函数:添加尾节点

//输入参数:链表指针的地址,以及要存入的数据

//返回:指向尾节点的指针

List AddEndNode(List *plist,u32 num)

{

List current=*plist;//存储首指针所指向的空间

List pnew;//新的节点指针

pnew = (List)malloc(sizeof(Node));//分配新的内存空间给pnew作为一个新的节点

if(pnew == NULL)//分配失败

return NULL;

pnew->num=num;//向新节点中添加数据

pnew->next=NULL;//新节点指向空

if(current == NULL)//头结点为空,即为空链表

{

*plist=pnew;//将头指针指向新开辟的pnew空间

}

else//不是头结点

{

while(current->next != NULL)//遍历到链表结尾,得到旧尾节点

current=current->next;//指针指向下一个节点空间

current->next = pnew;//遍历完成后,使旧尾节点指向新开辟的pnew空间

}

return pnew;//返回新尾结点指针

}

这里有个地方难以理解——在该函数的入口参数中有个List*类型。我们都知道List类型等价于Node*类型,它表示一个节点指针。但是,List*又是什么鬼?

其实,它是一个双重指针。

在主函数中声明的链首指针List begin,如果想要在子函数中修改它的值(或者说修改它指向的空间),必须通过间接调用来进行,即*plist=&begin。然后,我们就可以在子函数中使用*plist来改变begin了。注意!!!虽然我们也定义了List current=*plist,但却不能通过改变current来改变begin,理由如下:

链表头指针调用

从上图我们可以看到,current是一个新的指针,current和*plist不同,他们只是指向相同的空间而已。所以要对首指针begin进行修改,只能通过*plist来进行。

看到这里,你应该对链表结构有了更深的了解。你可以尝试着编写一下其他对链表进行操作的函数,如删除节点、更改节点等。

如果你觉得有用,点个赞如何?

(0)

相关推荐