|
大家好，今天跟大家分享数据结构中链表的学习方法，下面直接进入正题。 首先,我们来看一下链表的基本单元——节点。节点结构体的定义如下: //节点结构体 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来进行。 看到这里，你应该对链表结构有了更深的了解。你可以尝试着编写一下其他对链表进行操作的函数，如删除节点、更改节点等。 如果你觉得有用，点个赞如何？ |
|
|
