第37题  创建带头结点的单向链表

在本题程序MODI1.C中,函数fun通过整型形参n接收一个整型值,创建一个含有n个结点(不计头结点)的带头结点的单向链表,并将头指针作为函数值返回。

请改正程序中的错误,使之得出正确结果。                                                                注意:不许改动 main函数,不许增行或删行,也不许更改程序结构。

MODI1.C:

MODI37-01

参考答案:

MODI37-02运行结果:

MODI37-03

程序解析:

#include <stdio.h>
#include <stdlib.h>

typedef struct a {
­      int data;
­      struct a ∗next;
} NODE;

文件包含预处理指令#include <stdio.h>支持标准库函数printf、scanf的正常调用。程序要调用某个库函数,就必须包含与之对应的头文件。预处理指令通常位于源文件开头处,单独占一行,行尾无标点。#include <stdlib.h>支持标准库函数rand、malloc。

定义结构体类型NODE,包含2个成员:整型数据域data和链接指针域next。在程序下文,就可用该自定义类型NODE定义变量,就像用int定义变量一样。

程序从函数main开始执行。声明:

int n;
NODE ∗head;

定义整型变量n,分配存储,不作初始化,用于从标准输入设备(通常是键盘)读取链表的结点个数。定义NODE型指针head,分配存储,不作初始化,用于指向创建链表的头结点。凡未经初始化的变量,其初值无意义,仅反映新分配内存的当前随机性物理状态。至此,当前存储状态如下图所示,变量的无意义垃圾值以空白表示。

MODI37-04

首先,执行下列语句:

printf(″请输入链表结点总数(不含头结点): ″);
scanf(″%d″, &n);

printf语句在标准输出设备(通常是显示器)给出提示信息。语句scanf(″%d″, &n);从标准输入设备(通常是键盘)读取一个整型值并赋值于n。注意:scanf的实参必须是指针,&n是指向变量n的int型指针,&叫做取地址运算符。至此,当前存储状态如下图所示:

MODI37-05

接着,执行下面函数调用语句:

head = fun(n);

以整型变量n为实参调用函数fun,于是,main的执行被挂起(暂停),函数fun开始执行。首先,为形参变量n分配存储,完成参数传递:将main中的变量n的值复制于fun的形参n,此所谓 ″传值″。

在函数fun中,声明:

NODE ∗h, ∗p, ∗s;

定义NODE型指针h、p、s,分配存储,不作初始化,用于创建链表。至此,当前存储状态如下图所示。形参n也是fun的局部变量。这时有两个变量n,同名同型,但不会冲突,因为它们分属函数fun和main,分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI37-06

在函数fun中,首先执行下面语句:

p = (NODE ∗)malloc(sizeof(NODE));

调用库函数malloc申请一块NODE型变量大小的动态存储空间,将返回的void型指针强制转换为NODE型指针并赋于p,作为链表的头结点。所谓动态变量就是在程序执行期间通过调用库函数malloc申请而来的变量,动态变量存在于动态变量存储空间,动态变量空间与函数的存储空间不同。至此,当前存储状态如下图所示:

MODI37-07

接着,执行下面语句:

p−>next = NULL;

将符号常量NULL的值赋于p所指结点的指针域next、本题数据域data空闲不用(也可存储链表结点的总个数等一些特别值),至此,带头结点的空链表创建完成。头结点会对链表操作带来方便。图中符号∧表示空指针NULL,符号常量NULL在头文件stddef.h、stdio.h、stdlib.h中均有其定义,其值为0,是个特别指针值,在程序中用作标志,通常标示链表结尾,就像空字符′\0′充当字符串结尾标志一样。至此,当前存储状态如下图所示:

MODI37-08

接着,执行下面语句:

h = p;

令指针h指向p所指的结点,作为链表头结点。至此,当前存储状态如下图所示:

MODI37-09

接着,执行下面语句:

for ( ; n > 0; n−−) {
­      s = (NODE ∗)malloc(sizeof(NODE));
­      s−>data = rand()%50 + 50;
­      s−>next = NULL;
­      p−>next = s;
­      p = s;
}

这是递减型for循环,因为n是函数fun的形参,经参数传递已获得初值8,所以for语句的第1表达式缺省,但分号不能省略。循控变量 n 依次取值8,7,…,1,0。当 n 取0时,循环因条件 n > 0为假而终止。n 每取一值(0除外),均执行一轮循环体:语句s = (NODE ∗)malloc(sizeof(NODE));调用库函数malloc申请一个NODE型动态变量并以指针s指向它;语句s−>data = rand()%50 + 50;调用库函数rand、产生一个大于等于50、且小于100的伪随机整数并赋于s所指结点的data域;语句s−>next = NULL;将空指针NULL赋于s所指结点的指针域next;语句p−>next = s;令p所指结点的next指针指向s所指的结点,即将s所指结点链接于p所指结点后面;语句p = s;令p指向s所指的结点(指针变量的值是变量的地址。若p和q是同型指针,则赋值语句p = q;使得p也指向q所指的对象,考生可据此画图进行分析)。当for循环终止后,含有8个数据结点的链表就创建完毕。在创建链表的循环过程中,h指向头结点始终保持不变,p指向并跟踪链表的尾结点,s用于临时申请动态结点,每当申请到一个结点,先填写其数据域和指针域,再把它链接于p所指尾结点后面,作为新的尾结点,同时令p指向新的尾结点,从而链表不断向后延长。

下面图解第1轮循环,看第1个数据结点是如何链接进来的:语句s = (NODE ∗)malloc(sizeof(NODE));的执行效果如下图所示:

MODI37-10

语句s−>data = rand()%50 + 50;的执行效果如下图所示:

MODI37-11

语句s−>next = NULL;的执行效果如下图所示:

MODI37-12

语句p−>next = s;的执行效果如下图所示:

MODI37-13

语句p = s;的执行效果如下图所示:

MODI37-14

至此,第1个数据结点链接进来了。这样再循环7次,第8个数据结点也链接进来了,至此,当前存储状态如下图所示:

MODI37-15

接着,执行下面语句:

return h;

将链表头指针h的值返回函数main,同时收回函数fun的存储空间。至此,当前存储状态如下图所示:

MODI37-16

函数fun返回后,main从挂起点即语句head = fun(n);恢复继续执行,将fun返回的头指针值赋于main中的头指针head。至此,当前存储状态如上图所示。接着,执行下面函数调用语句:

printlink(head);

以头指针head为实参调用函数printlink,于是,main的执行被挂起(暂停),函数printlink开始执行。首先,为形参变量h分配存储,完成参数传递:将main的指针head的值复制于printlink的形参指针h。至此,当前存储状态如下图所示。形参h也是printlink的局部变量。相关的局部变量分属函数printlink和main,分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI37-17

在函数printlink中,首先执行下面语句:

h = h−>next;

令指针h指向其后继结点,即第1个数据结点,为扫描并输出链表各结点的数据做好准备。至此,当前存储状态如下图所示:

MODI37-18

接着,执行下列语句:

printf(″链表各结点为:\n Head ″);
while (h != NULL) {
­      printf(″−>%d ″, h−>data);
­      h = h−>next;
}
printf(″\n″);

首先,在标准输出设备输出提示信息。然后,执行while循环语句,若循环条件h != NULL为真,即h尚未指向链表尾,准确说,h尚未取得NULL的值,则执行循环体:语句printf(″−>%d ″, h−>data);将h所指结点data域的值转换成十进制格式的字符序列、在标准输出设备(通常是显示器)上输出。语句h = h−>next;令指针h指向下一结点。一轮之后,再次测试循环条件,若仍为真,则再次执行循环体,如此重复,直到循环条件h != NULL为假,即h取得NULL的值,迫使循环终止。当while循环终止后,全部结点数据输出完毕。while循环过程是以指针h依次扫描链表结点的过程。因为NULL的值为0,所以代码片段while (h != NULL)可简写为while (h)。至此,当前存储状态如下图:

MODI37-19

最后,语句printf(″\n″);输出换行符。由于这是printlink的最后语句,随即printlink返回main但无返回值,同时收回printlink的存储空间。至此,当前存储状态如下图所示:

MODI37-16

函数printlink返回后,main从挂起点即语句printlink(head);恢复继续执行,printlink没有返回值。

由于这是main的最后语句,随即函数main执行结束、同时收回其存储空间。动态变量存储空间也随整个程序执行结束而被遗弃。

知识点:

① 库函数int  rand(void)返回0至RAND_MAX之间的随机整数,0和RAND_MAX这两个端点值也可能出现。 RAND_MAX是头文件stdlib.h中定义的宏,即符号常量,至少为32767。要使用rand库函数,必须要有#include <stdlib.h>指令,通常写在程序开头处。语句s−>data = rand()%50 + 50;调用库函数rand生成一个0至RAND_MAX之间的随机整数,再除50取其余数,得到小于50的、具有一定随机性的非负整数,再加50得到一个大于等于50、且小于100的随机整数并赋于s所指结点的data域。

② 结构体是将若干相互关联的变量捆绑而成的集成体变量。例如:本题将整型数据成员data和指针成员next捆绑成一个结构体,含有指针域的结构体可用来构造链表;还可以将2个浮点坐标变量集成一个结构体,表示几何平面上的一个点,等等。

③  结构体类型定义的一种简单格式如下:

typedef  struct  结构体标签  {
­        成员1声明
­        成员2声明
­        ……
­}  类型名;

例如:本题中的链表结点结构体类型定义:

typedef struct a {
­      int data;
­      struct a ∗next;
} NODE;

其中NODE叫做自定义结构体类型,是一个标识符。结构体成员可以是指向同型结构体的指针,如next,用于链接结构体结点来构造链表。

④ 结构体变量和结构体指针的一种简单声明格式如下:

类型名    变量名;

例如:int   i;     定义i为int类型的变量。

NODE   t;     定义t为NODE类型的结构体变量,NODE相当于int,都是类型名。

NODE ∗p;    定义p为指针,指向NODE类型的结构体变量。

⑤ 若a是结构体变量,则只能利用圆点运算符访问结构体的成员。例如:a.no、a.name、a.score[2]。

⑥ 若p是结构体指针变量,则可利用−>或圆点运算符访问结构体的成员。例如:p−>data、p−>next或其等价式(∗p).data、(∗p).next。注意:其中的圆括号不能省,这是因为∗的优先级低于圆点。

⑦ 结构体和结构体指针均可作为函数参数被整体传递,也可作为函数值被整体返回,还可以整体赋值。而数组只能通过指针被函数间接访问,数组也不能整体赋值。

⑧ 指针变量的值是变量的地址。若p和q是同型指针,则赋值语句p = q;使得p也指向q所指的对象,如本题中的语句p−>next = s; 、p = s;等等。

⑨ 若p是指针变量,则可利用p直接访问该指针变量,还可利用∗p间接访问p所指向的变量或对象,∗叫做指针间接访问运算符。

⑩ 不必关心函数printlink的具体实现,知道其输出链表的功能即可,把焦点集中于函数fun的具体实现即可得分。

练习题:

试改变代码行 s−>data = rand()%50 + 50; 中的rand()%50 + 50,为自己命新题,举一反三。

返回