量，依次指向链表的每一个结点，从而实现对每一个结点的访问，这样的一个指针变量常 常被称为游动指针。与数组中通过下标的变化来实现对数组中存放的批量数据元素的访问 类似，链表中是通过游动指针的变化，依次指向不同的结点，来实现对其存放的批量数据 元素的访问的。 为了更简洁地表示链表的操作过程，有时需要对前述单链表的结构做一点改动，在单 链表的第一个实际结点之前增加一个虚结点，该虚结点数据域不存放任何实际数值，其指 针域指向单链表的第一个实际结点。该结点被称为单链表的头结点。引入头结点之后，指 向头结点的指针称为头指针。如无特别说明，之后的各种操作均针对带头结点的单链表。 8正一正一a 头指针 头结点 图13.4带头结点的单链表 一个带头结点的单链表如果只包含头结点，称为空链表。 当然，不管是头指针还是游动指针，都是存放结点地址的指针变量，应该是指向结点 的指针类型的变量，如上所定义的结点，其对应链表头指针与 游动指针可以如下定义： struct node head,p; 图135带头结点的空链表 13.3单链表结点的基本操作 单链表结点的操作有很多，其中最基本的操作主要有三个：查找、插入与删除。这三 个操作是链表其他操作功能实现的基础，因此在这里作重点介绍。 13.3.1单链表结点的查找 虽然都用来存储批量数据元素，但从结构特点上看，单链表与数组还是有着很大的差 别。数组由于是用地址连续的空间存放元素，利用“数组名+下标”的方式可以实现对元 素的随机查找：单链表是用地址离散的空间存放元素的，不能直接指向每一个结点的存放 地址，只能从头指针所指结点开始逐个往后找到要访问的结点，因此也称单链表是一种“顺 序存取”的结构。 单链表的查找过程也是基于这样的存取原则，即必须要从头指针所指结点开始往后逐 个查找，才能找到要找的结点信息。因此该过程要用到前面提到的两个重要指针：头指针 与游动指针。其中头指针提供了在链表中查找的起始位置，游动指针从该起始位置开始逐 个往后“游走”，直到找到要找的结点，或者到了链表结束处停止查找。 【例13.1】写一个函数，找到指定单链表中值为k©y的结点，并返回该结点的地址。 6
6 量，依次指向链表的每一个结点，从而实现对每一个结点的访问，这样的一个指针变量常 常被称为游动指针。与数组中通过下标的变化来实现对数组中存放的批量数据元素的访问 类似，链表中是通过游动指针的变化，依次指向不同的结点，来实现对其存放的批量数据 元素的访问的。 为了更简洁地表示链表的操作过程，有时需要对前述单链表的结构做一点改动，在单 链表的第一个实际结点之前增加一个虚结点，该虚结点数据域不存放任何实际数值，其指 针域指向单链表的第一个实际结点。该结点被称为单链表的头结点。引入头结点之后，指 向头结点的指针称为头指针。如无特别说明，之后的各种操作均针对带头结点的单链表。 图 13.4 带头结点的单链表 一个带头结点的单链表如果只包含头结点，称为空链表。 当然，不管是头指针还是游动指针，都是存放结点地址的指针变量，应该是指向结点 的指针类型的变量，如上所定义的结点，其对应链表头指针与 游动指针可以如下定义： struct node *head，*p; 13.3 单链表结点的基本操作 单链表结点的操作有很多，其中最基本的操作主要有三个：查找、插入与删除。这三 个操作是链表其他操作功能实现的基础，因此在这里作重点介绍。 13.3.1 单链表结点的查找 虽然都用来存储批量数据元素，但从结构特点上看，单链表与数组还是有着很大的差 别。数组由于是用地址连续的空间存放元素，利用“数组名+下标”的方式可以实现对元 素的随机查找；单链表是用地址离散的空间存放元素的，不能直接指向每一个结点的存放 地址，只能从头指针所指结点开始逐个往后找到要访问的结点，因此也称单链表是一种“顺 序存取”的结构。 单链表的查找过程也是基于这样的存取原则，即必须要从头指针所指结点开始往后逐 个查找，才能找到要找的结点信息。因此该过程要用到前面提到的两个重要指针：头指针 与游动指针。其中头指针提供了在链表中查找的起始位置，游动指针从该起始位置开始逐 个往后“游走”，直到找到要找的结点，或者到了链表结束处停止查找。 【例 13.1】 写一个函数，找到指定单链表中值为 key 的结点，并返回该结点的地址。 图 13.5 带头结点的空链表
如果有多个值为ky的结点，返回找到的第一个结点的地址：如果没有值为key结点，返 回为NULL。 程序如下： struct node in年da+a: struct node next: struct node search(struct node head,int key) /head为单链表的头指针 struct node pi 1/p为游动指针 p=head->next; //游动指针指向第一个实际结点 while (p!=NULL) /P为NULL表示链表已经访问结束 if(p->data==key) ceturn(p); 1/找到，返回该结点的地址 else p=p->next; 11未找到，指向下一个结点继续查找 return NULL /循环正常结束，说明不存在该结点 本函数由于要返回找到结点的地址，所以返回值的类型为指针，即在指针一章所介绍 的函数是返回指针值的函数。在main函数调用时实参给定单链表的头指针以及要查找的元 素值，便可得到查找的结点的地址信息。其中的语句： p-p->next: 是链表操作中最常用的语句形式，作用是使指针发生改变，由指向当前结点，转而指向 其下一个结点。p与p>next的关系如图13.6所示。 w日正日-□-2 p->next 图13.6p与p->next所指结点 13.3.2单链表结点的插入 单链表与数组的不同之处还体现在单链表是一个动态存储的结构，可以在需要时再分 配空间，用完后马上释放空间。而且，与数组做元素插入、删除需要移动元素不同，单链 表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。 要在单链表中插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只 7
7 如果有多个值为 key 的结点，返回找到的第一个结点的地址；如果没有值为 key 结点，返 回为 NULL。 程序如下： struct node { int data; struct node *next; }; struct node *search(struct node *head,int key) //head 为单链表的头指针 { struct node *p; //p 为游动指针 p=head->next; //游动指针指向第一个实际结点 while(p!=NULL) //p 为 NULL 表示链表已经访问结束 { if(p->data==key) return(p); //找到，返回该结点的地址 else p=p->next; //未找到，指向下一个结点继续查找 } return NULL; //循环正常结束，说明不存在该结点 } 本函数由于要返回找到结点的地址，所以返回值的类型为指针，即在指针一章所介绍 的函数是返回指针值的函数。在 main 函数调用时实参给定单链表的头指针以及要查找的元 素值，便可得到查找的结点的地址信息。其中的语句： p=p->next; 是链表操作中最常用的语句形式，作用是使指针 p 发生改变，由指向当前结点，转而指向 其下一个结点。p 与 p->next 的关系如图 13.6 所示。 图 13.6 p 与 p->next 所指结点 13.3.2 单链表结点的插入 单链表与数组的不同之处还体现在单链表是一个动态存储的结构，可以在需要时再分 配空间，用完后马上释放空间。而且，与数组做元素插入、删除需要移动元素不同，单链 表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。 要在单链表中插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只
有两点：一是为要插入的元素分配空间，生成一个新结点：二是通过指针域的修改，把新 结点插入到链表中 比如对于图13.5中p所指结点之后插入一个值为10的新结点，过程如下。 (1)开辟新结点 struct node·g q=(struct node *malloc (sizeof(struct node)); q->data=10; g->next■NULL: 完成后状态如图13.7所示。 }E-2a p->next 90 图13.7开辟新结点 (2)修改指针域，将新结点插入链表： 执行上面的第一个语句后，链表的状态如图13.8所示。 ✉□一□ p 图13.8修改指针域（一） 执行上面的第二个语句后，链表的状态如图13.9所示。 8
8 有两点：一是为要插入的元素分配空间，生成一个新结点；二是通过指针域的修改，把新 结点插入到链表中。 比如对于图 13.5 中 p 所指结点之后插入一个值为 10 的新结点，过程如下。 （1）开辟新结点 struct node * q; q=(struct node *) malloc (sizeof(struct node)); q->data=10; q->next=NULL; 完成后状态如图 13.7 所示。 图 13.7 开辟新结点 （2）修改指针域，将新结点插入链表： q->next=p->next; p->next=q; 执行上面的第一个语句后，链表的状态如图 13.8 所示。 图 13.8 修改指针域（一） 执行上面的第二个语句后，链表的状态如图 13.9 所示
图13.9修改指针域（二） 【例13.2】根据上述步骤写出一个在链表的p结点之后插入一个值为ky的结点的函数。 程序如下： void insert(struct node p,int key) struct node eq: q=(struct node *malloc(sizeof(struct node)); if(!q) printf("不能分配内存空间！")： exit (0); g->data=key q->next=NULL: 1->next■p->next: p->next=q: 可见，链表中结点的插入并不需要元素的移动，只需要作指针域的修改即可。首先修 改新结点的指针域，指向下一个元素：再修改前一个元素的指针域，指向新元素。并且这 两者的顺序是不能颠倒的，请读者想一想为什么。 13.3.3单链表结点的删除 与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即 可。并且作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所 占的内存空间释放。 要刑除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的 修改操作。比如，要删除图13.10中链表值为6的结点，应该先找到其前一个结点。 图13.10找到欲删结点的前结点 删除过程的指针修改如下： q->p->next; p->next-q->nexti free(q); 9
9 图 13.9 修改指针域（二） 【例 13.2】 根据上述步骤写出一个在链表的 p 结点之后插入一个值为 key 的结点的函数。 程序如下： void insert(struct node *p,int key) { struct node *q; q= (struct node *) malloc(sizeof(struct node)); if(!q) { printf("不能分配内存空间!"); exit(0); } q->data=key; q->next=NULL; q->next=p->next; p->next=q; } 可见，链表中结点的插入并不需要元素的移动，只需要作指针域的修改即可。首先修 改新结点的指针域，指向下一个元素；再修改前一个元素的指针域，指向新元素。并且这 两者的顺序是不能颠倒的，请读者想一想为什么。 13.3.3 单链表结点的删除 与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即 可。并且作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所 占的内存空间释放。 要删除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的 修改操作。比如，要删除图 13.10 中链表值为 6 的结点，应该先找到其前一个结点。 图 13.10 找到欲删结点的前驱结点 删除过程的指针修改如下： q->p->next; p->next=q->next; free(q);