第36题  求带头结点链表的最小值

在本题程序MODI1.C中,函数fun通过结构体指针形参h接收一个带头结点的单向链表,求链表数据域的最小值并作为函数值返回。

例如:若原始链表的数据成员依次为58,78,24,69,0,34,67,41,则函数返回的最小值为0。

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

MODI1.C:

MODI36-01参考答案:

MODI36-02

运行结果:

MODI36-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开始执行。声明:

NODE ∗head;
int m;

定义NODE型指针head,分配存储,不作初始化,用于指向链表的头结点。定义整型变量m,分配存储,不作初始化,用于接收函数fun返回的链表最小值。凡未经初始化的变量,其初值无意义,仅反映新分配内存的当前随机性物理状态。至此,当前存储状态如下图所示,变量的无意义垃圾值以空白表示。

MODI36-04

首先,执行下面函数调用语句:

head = creatlink(8, 100);

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

在函数creatlink中,声明:

NODE ∗h, ∗s;
int i;

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

MODI36-05

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

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

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

MODI36-06

接着,执行下面语句:

h−>next = NULL;

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

MODI36-07

接着,执行下面语句:

for (i = 1; i <= n; i++) {
­      s = (NODE ∗)malloc(sizeof(NODE));
­      s−>data = rand() % m;
­      s−>next = h−>next;
­      h−>next = s;
}

循控变量 i 依次取值1,2,…,8,9(n+1)。当 i 取9时,循环因条件 i <= n为假而终止。i 每取一值(9除外),均执行一轮循环体:语句s = (NODE ∗)malloc(sizeof(NODE));调用库函数malloc申请一个NODE型动态变量并以指针s指向它;语句s−>data = rand() % m;调用库函数rand、产生一个小于100(m)的伪随机非负整数并赋于s所指结点的data域;语句s−>next = h−>next;和h−>next = s;将s所指结点链接于h所指结点之后(指针变量的值是变量的地址。若p和q是同型指针,则赋值语句p = q;使得p也指向q所指的对象,考生可据此画图进行分析)。当for循环终止后,含有8个数据结点的链表就创建完毕。第1个结点插入后,其效果如下图所示:

MODI36-08

第2个结点插入后,其效果如下图所示:

MODI36-09

全部8个结点插入后,其效果如下图所示。该链表按倒序建立、简单又方便。

MODI36-10

接着,执行下面语句:

return h;

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

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

printlink(head, stdout);

以头指针head和标准流指针stdout为实参调用函数printlink,于是,main的执行被挂起(暂停),函数printlink开始执行。首先,为形参变量h和fp分配存储,完成参数传递:将main的指针head的值和标准流指针stdout的值分别复制于printlink的形参指针h和fp。

printlink的形参声明FILE ∗fp;定义FILE类型的指针fp,FILE是在头文件stdio.h中定义的一种结构体类型,用于支持文件操作。

stdout是头文件stdio.h中定义的符号常量,在程序开始运行之前,已预先与标准输出设备(通常是显示器)关联,因此凡将字符输出到标准流stdout,也就是在标准输出设备(通常是显示器)上输出。

至此,当前存储状态如下图所示。形参h和fp也是printlink的局部变量。相关的局部变量分属函数printlink和main,分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI36-12

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

h = h−>next;

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

MODI36-13

接着,执行下列语句:

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

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

由于这是printlink的最后语句,随即printlink返回main但无返回值,同时收回printlink的存储空间。至此,当前存储状态如下图所示:

MODI36-14

函数printlink返回后,main从挂起点即语句printlink(head, stdout);恢复继续执行,printlink没有返回值。接着,执行下面函数调用语句:

m = fun(head);

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

在函数fun中,声明:

NODE ∗p;
int min = 100;

定义NODE型指针p,分配存储,不作初始化,用于扫描链表、从中找出最小值。定义整型变量min,分配存储,初始化为100(只要大于链表中任意结点的值即可),即假定迄今最小值为100,为找出最小值做准备。至此,当前存储状态如下图所示。形参h也是fun的局部变量。相关的局部变量分属函数fun和main,分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI36-15

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

p = h−>next;

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

MODI36-16

接着,执行下列语句:

while (p != NULL) {
­      if (p−>data < min)
­            min = p−>data;
­      p = p−>next;
}

若循环条件p != NULL为真,即p尚未指向链表尾,准确说,p尚未取得NULL的值,则执行循环体:if语句测试条件p−>data < min,若为真,即p所指结点的data域小于迄今最小值min,则执行语句min = p−>data;以其取代min作为新的迄今最小值。语句p = p−>next;令指针p指向下一结点。一轮循环之后,再次测试循环条件,若仍为真,则再次执行循环体,如此重复,直到循环条件p != NULL为假,即p取得NULL的值,迫使循环终止。当while循环终止后,min的值就是全部结点中的最小值。while循环过程是以指针p依次扫描链表结点的过程。因为NULL的值为0,所以代码片段while (p != NULL)可简写为while (p)。至此,当前存储状态如下图所示:

MODI36-17

接着,执行下列语句:

return min;

将所求得的最小值min返回函数main,同时收回函数fun的存储空间。至此,当前存储状态如下图所示:

MODI36-18

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

printresult(m, stdout);

以变量m和标准流指针stdout为实参调用函数printresult,于是,main的执行被挂起(暂停),函数printresult开始执行。首先,为形参变量s和fp分配存储,完成参数传递:将main的变量m的值和标准流指针stdout的值分别复制于printresult的形参指针s和fp。

printresult的形参声明FILE ∗fp;定义FILE类型的指针fp,FILE是在头文件stdio.h中定义的一种结构体类型,用于支持文件操作。

stdout是头文件stdio.h中定义的符号常量,在程序开始运行之前,已预先与标准输出设备(通常是显示器)关联,因此凡将字符输出到标准流stdout,也就是在标准输出设备(通常是显示器)上输出。

至此,当前存储状态如下图所示。形参s和fp也是printresult的局部变量。相关的局部变量分属函数printresult和main,分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI36-19

在函数printresult中,执行其唯一语句:

fprintf(fp, ″链表中的最小值是: %d\n″, s);

将s中的最小值转换成十进制格式的字符序列、并输出到文本流fp中,即标准文本流stdout中,也就是在标准输出设备(通常是显示器)上输出。

由于这是printresult的唯一语句,随即printresult返回main但无返回值,同时收回printresult的存储空间。至此,当前存储状态如下图所示:

MODI36-20

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

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

知识点:

① 程序执行是动态过程,语句不断执行,变量值不断变化,同时伴随函数局部变量(含形参变量)的创生与消亡。当函数进入时,局部变量因自动分配存储而创生;当函数返回时,因自动收回存储而消亡。形参变量经参数传递获得初值且有意义,非形参局部变量若未经显式初始化,则其初值无意义,称为垃圾值,仅反映新分配内存的当前随机性物理状态。参数传递发生在函数进入后、函数的语句开始执行前,实参表达式(含变量)的值被复制于形参变量之中,名曰″传值″。不同函数的局部变量可以同名,不会冲突,驻留各自的存储空间,只能被所属函数自己的语句访问,这就是局部变量的作用域。函数通过对形参指针的间接引用可以访问调用者函数内的变量,是函数之间双向通信的重要方式,既能从调用者接收数据,又能向调用者回送计算结果。函数通过非指针形参只能从调用者函数接收数据,通过函数返回值只能向调用者回送计算结果,都只是单向通信。

② 结构体是将若干相互关联的变量捆绑而成的集成体变量。例如:本题将整型数据成员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所指的对象,如本题中的语句s−>next = h−>next;、h−>next = s;等等。

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

⑩ 不必关心函数creatlink、printlink、printresult的具体实现,知道其生成链表、输出链表、输出最小值结果的功能即可,把焦点集中于函数fun的具体实现即可得分。

练习题:

试改变代码行int min = 100;中的100,改变代码行if (p−>data < min)中的<,为自己命新题,举一反三。

返回