从问题到程序-结构和其他数据机制课件

1、第九章结构和其他数据机制第九章结构和其他数据机制介绍C语言的其他数据描述机制，包括结构（struct）、联合（union）、枚举（enum）等。各种数据机制的概念、意义和用途。在写处理复杂数据的程序，在定义复杂数据类型和结构时，这些机制应用广泛。 “数据结构” 课程中将大量使用这些机制。这里主要介绍概念，给出一些程序实例。并介绍一些相关的概念和技术。后续课程和其他书籍中可以看到大量实例。介绍C语言的其他数据描述机制，包括结构（struct）、联合9.1 结构（struct）被处理的数据常形成一些逻辑整体，有紧密内在联系。各成分的性质类似（同类型）时可以用数组。数据体成分类型不同的情况很普遍。如

2、居民身份证，成分有：姓名、性别、民族、出生日期、住址、身份证号码、发证日期、有效期限和发证单位，照片。这组信息共同描述了一个居民。无法用数组表示。许多语言提供了可将多个相同或不同类型的数据组合起来的机制，常称记录(record)。C称为结构(structure)。结构是复合数据对象，其中的数据项称为结构的成分或成员。成员给定名字，通过成员名访问结构成员。9.1 结构（struct）被处理的数据常形成一些逻辑整体结构说明与结构变量定义结构说明由struct引导，基本形式：struct 成员说明序列 ;成员说明形式同变量定义：struct int n; double x, y; 单独的结构说明只描

3、述了结构本身（的结构）。struct int n; double data100; 结构说明与结构变量定义struct 一个结构里可以有任意多个成员，成员可为任何类型，如基本类型、指针或数组成员。成员也可以是结构。一个结构里各个成员的名字不能相互冲突。不同结构完全可以包含名字相同的成员，相互无关。定义结构变量把结构说明当作类型，就可以定义结构变量：struct int n; double x, y; st1, st2;st1和st2都是这种结构的变量，包含相应的成分。一个结构里可以有任意多个成员，成员可为任何类型，如基本类型、结构标志及其使用：加结构标志可避免反复写同样结构描述。标识符表示。s

4、truct point double x, y;struct circle struct point center; double radius; /* 定义结构成员时利用结构标志 */struct rectangle struct point lu; struct point rd;结构标志及其使用：struct point 利用结构标志定义结构变量：struct point pt1, pt2;struct circle circ1, circ2;与结构有关的函数的原型说明：double dist(stuct point p1, struct point p2);结构标志可用于定义指向结构的

5、指针，做类型转换，计算大小，建立存放结构的存储块：struct circle *p;p = (stuct circle *) malloc(sizeof(struct circle);. .利用结构标志定义结构变量：定义结构类型在程序里反复使用的结构最好是定义为类型：typedef struct double x, y; POINT;typedef struct POINT center; double radius; CIRCLE;typedef struct POINT lu; POINT rd; RECTANGLE;定义结构类型定义结构类型使程序更简短清晰。例：居民身份证信息的结构类型定

6、义：typedef struct /* 数据表示问题 */ char name20; /* 名字字符串用多长？ */ int sex; /* . */ char nationality10; int born_in3; char address50; int date_of_issue3; int valid_years; char issued_by30; char id_number18; char photo10064; IDCARD;定义结构类型使程序更简短清晰。例：居民身份证信息的结构类型定无效结构定义结构成员不能是被描述的结构本身。非法结构描述的例子：struct invalid

7、int n; struct invalid iv;这种描述定义的结构里包含自身，引起了无穷嵌套，不合理，也不可能在计算机里实现。无效结构定义结构的实现一个结构占一块连续存储，各成员顺序存放。CIRCLE对象的存储方式。typedef struct POINT center; double radius; CIRCLE;结构的实现对齐问题结构成员类型可不同，引起对齐问题：struct exam char aa; int nn; double xx;基本数据存放有规定：2字节整数从偶地址开始；8字节double可能从4（或8）的倍数地址开始。1）结构成员的存放位置之间可能有空位；2）结构大小未必等

8、于成员大小之和。应该用sizeof计算结构大小（例如动态存储分配时）。对齐问题1）结构成员的存放位置之间可能有空位；结构变量的初始化与使用定义结构变量时可以直接初始化。例：POINT pt1 = 2.34, 3.28, pt2;CIRCLE circ1 = 3.5,2.07,1.25, circ2 = 12.35,10.6,2.56;初值表达式应能静态求值，顺序赋给基本成员。嵌套结构可加括号。项数不得多于结构变量所需，不够补0。未提供初始值时外部和静态局部结构变量的成员初始化为0；自动变量不初始化。初值式只能用于变量定义。结构变量的初始化与使用未提供初始值时外部和静态局部结构变量的结构变量的使

9、用整体赋值同类型结构变量可整体赋值，效果是各成员分别赋值：pt2 = pt1;结构不能做相等/不等比较。成员访问访问结构成员用圆点运算符（.），最高优先级，自左向右结合。例子：pt2.y = pt1.y + 2.4;circ1.center.x = 2.07;circ1.center.y = pt1.y;结构变量的使用成员访问将结构circ2所表示的圆做平移，可以写：circ2.center.x += 2.8;circ2.center.y += 0.24;结构成员相当于相应类型的变量，操作由类型决定。int main () POINT pt1 = 2.34, 3.28, pt2; CIRCLE

10、 circ1 = 3.5, 2.07, 1.25; double x, y; pt2.x = 8.0; pt2.y = circ1.center.y + 3.44; x = pt2.x - pt1.x; y = pt2.y - pt1.y; printf(distance: %fn, sqrt(x*x + y*y); return 0;将结构circ2所表示的圆做平移，可以写：int main 结构、数组与指针结构可以有数组成员（身份证例子）。也可以定义以一组结构为元素的数组（结构数组）。例：用结构数组重构C程序关键字统计程序。已讨论两种实现，1）两维字符数组和计数器数组；2）用字符指针数组和

11、计数器数组。更合理方式是用一个结构表示与一个关键字有关的所有信息。为此可定义结构类型。typedef struct char * key; int count; KEYC; /* “关键字计数器”类型 */结构、数组与指针更合理方式是用一个结构表示与一个关键字有关的程序数据结构就是一个KEYC数组，定义时初始化：KEYC keytable32 = auto, 0, break, 0, . . volatile,0, while, 0; /*初始化中也可写嵌套的括号*/程序的主循环可写为：int i; .while (getident(., s) 0) for (i = 0; i 0) for

12、(p=keytable; p ： p-key 等价于 (*p).key也可以用指针方式写：注意(*p).key写法，这里必须写括号-具有最高优先级（与圆点，函数调用()及数组元素访问一样），从左向右结合。while (getident(s, .) 0) for (p=keytable; p key) = 0) p-count+; break; 已经讨论了C语言的所有运算符，附录A列出这些运算符：意义/优先级/结合方式。请自己查阅。-具有最高优先级（与圆点，函数调用()及数组元素访问一结构可作为函数参数和函数返回值。将结构数据传给函数有三种方式（返回值情况类似）：1）传结构成员的值，只要该成员能

13、赋值。2）传递整个结构的值。结构参数。3）传结构的地址（指针）。结构指针参数。结构参数：实参结构变量的值整个赋给形参，函数内对形参的操作不会影响实参。结构指针参数：传结构指针可以避免复制整个结构。 可以对实参结构做任何操作，包括修改。若结构很大，复制费时间，也可考虑用指针方式传递。9.2 结构与函数结构可作为函数参数和函数返回值。将结构数据传给函数有三种方式例：由参数值构造POINT类型的结构值，函数定义：POINT mkpoint1(double x, double y) POINT temp; temp.x = x; temp.y = y; return temp;返回值可赋给同类型变量。

14、这种函数从成员值构造结构值，可称为结构值构造函数。使用：pt1 = mkpoint1(3.825, 20.7);pt2 = mkpoint1(pt1.x, 0.0);temp随函数结束而撤消，值返回，与局部变量的撤消无关。返回大的结构值时需要复制大批数据。例：由参数值构造POINT类型的结构值，函数定义：例：由参数值构造CIRCLE类型的结构值，函数定义：CIRCLE mkcircle(POINT c, double r) CIRCLE temp; temp.center = c; temp.radius = r; return temp;函数有一个结构参数。用例：circ1 = mkcirc

15、le(pt1, 5.254);circ2 = mkcircle(circ1.center, 11.7);circ3 = mkcircle(mkpoint1(2.05, 3.7), 3.245);第三个例子：mkpoint返回POINT值，传给mkcircle的POINT类型参数是合理的。例：由参数值构造CIRCLE类型的结构值，函数定义：定义计算两个点之间距离的函数，采用结构参数： double distance(POINT p1, POINT p2) double x = p1.x-p2.x, y = p1.y-p2.y; return sqrt(x*x + y*y);复制整个结构，语义清楚

16、。缺点是整体复制开销较大。例：打印身份证中身份证号和姓名的函数：void prtIDCard0(IDCARD ic) printf(%sn, ic.id_number); printf(%snn, );复制整个结构，大部分复制工作没有价值。定义计算两个点之间距离的函数，采用结构参数： 复制整个结构，可考虑传递结构指针，下面函数完成同样工作：void prtIDCard(IDCARD *icp) printf(%sn%snn, icp-id_number, icp-name);只复制一个指针，更合理。设idc是IDCARD变量：prtIDCard(&idc);例，打印一个身份证结构

17、数组中的各身份证的信息：IDCARD idcs10000, *p;. /* 假设idcs的元素都有了值 */for(p = idcs; p x = x; p-y = y; return p;调用时用指向POINT的指针接收函数返回值。POINT *q;q = mkpoint2(2.22, 1.784);有时需要建立新结构，不希望去破坏已有东西。可采用动态存储管理pp1 = mkpoint2(2.57, 3.86);pp2 = mkpoint2(pp1-y + 2.6, pp1-x 0.7);. . /* 使用建立的结构 */free(pp1); free(pp2); /*最后释放存储*/使用实

18、例：POINT *pp1, *pp2;. .采用动态管理优点：所建立结构的存在期不受建立位置约束，传递指针不必复制整个结构。这种方式在复杂软件里用的很多。数据结构课程中大量采用这种方式。pp1 = mkpoint2(2.57, 3.86);使用实程序实例基于结构设计实现第8章的账目管理系统。 需要记录每笔收支的日期、项目简记和相应金额。负数表示支出，正数表示收入。设程序输入按行进行，每行输入一笔账目。这里考虑相关数据结构和输入问题。显然，有关一笔账的信息是一个逻辑整体，应考虑用一种结构表示。为此设计下面的结构类型：typedef struct int year, month, day; /*

19、年月日 */ char outlineLINELEN; /* 项目简记 */ double amout; /* 金额 */ ACCITEM; 程序实例需要记录每笔收支的日期、项目简记和相应金额。负数表示账本就是ACCITEM的数组。例如可以定义：enum NACC = 400 ;ACCITEM accbookNACC; 作为程序里的基本数据表示。 考虑输入。应定义为函数，由它填充一个ACCITEM的数组。为使同一函数能适应各种输入源，可引进一个文件指针参数，用下面原型：int readall(FILE *fp, int limit, ACCITEM accbook);使定义方便，可以增加一个基

20、本账目项输入函数：int readitem(FILE *fp, ACCITEM *ip); 需要用结构指针参数，将实际结构地址传递给函数。 账本就是ACCITEM的数组。例如可以定义：考虑输入。应定义readitem输入可能出现几种情况：1）正常完成一项读入；2）出错；3）已读完所有数据。让readitem分别返回1，0和-1。readall的读入循环可以写成：while (1) switch(readitem(fp, &accbooki) case 1: +i; continue; case 0: . /* 处理输入出错 */ continue; case -1: break; /*有许多其

21、他写法，例如用if语句*/readitem输入可能出现几种情况：1）正常完成一项读入；readitem的最简单实现： int readitem(FILE *fp, ACCITEM *ip) int n = fscanf(fp, %d%d%d %s %lf, &ip-year, &ip-month, &ip-day, ip-outline, &ip-amount); return n=5 ? 1 : n=EOF ? -1 : 0;注意，假设了帐目条目对应于输入行，readitem里的输入错误处理也应反映输入行的概念。不应企图在这里给出错误信息或重新输入（按照设计，处理这些事项是readall的责

22、任）。 readitem的最简单实现： 注意，假设了帐目条目对应于输实现交互的主函数（驱动程序）：int main(void) int n, inum = 0; ACCITEM accbkNACC; initialization(); /*系统的初始化处理（可能有）*/ while (n = getcommand() = 0) switch (n) case 0: /* 要求账目文件名并读入 */ inum = readfile(NACC, accbook); break; case 1: /* 计算最终余额 */ balance(inum, accbook); break; default:

23、 errmessage(); break; finalization(); /*系统终止处理（可能有）*/ return 0; 实现交互的主函数（驱动程序）：开始调用initialization完成启动准备，如输出一些信息，介绍程序使用。最后finalization完成退出前的处理。如果增加有关一次执行所处理的文件总统计信息，可能就要增加一些全局变量，由上述函数完成其初始化和最后统计输出。 作业提出了一些扩充建议。getcommand应输出提示信息并读入用户命令，返回命令编码。可能采用各种方式。实现时要考虑处理用户错误输入，这里用的方式是命令错误时返回某个大数，当用户要求结束时返回负数。 re

24、adfile完成与输入有关的所有工作，返回实际输入的账目条数。工作包括：要求账目文件名，处理文件无法正常打开情况，调用readall实际读入等。 开始调用initialization完成启动准备，如输出一些errmessage()输出错误信息，应对本程序的使用方式给出一些提示。 其他函数完成的工作很明确，写函数的工作作为练习。还可以根据自己的考虑扩充这个系统。日期用3个整数表示有缺点：比较不方便，用3个整数表示也浪费空间。可考虑用如下结构：typedef struct unsigned long date; /* 年月日 */ char outlineLINELEN; /* 项目简记 */ d

25、ouble amout; /* 金额 */ ACCITEM; errmessage()输出错误信息，应对本程序的使用方式给帐目项读入函数改为： int readitem(FILE *fp, ACCITEM *ip) int y, m, d; int n = fscanf(fp, %d%d%d %s %lf, &y, &m, &d, ip-outline, &ip-amount); if (n != 5) return n = EOF ? -1 : 0; ip-date = y*10000 + m*100 + d; return 1;其中的年、月、日很容易提取。例：m = (item.date

26、/ 100) % 100; 帐目项读入函数改为： 其中的年、月、日很容易提取。例：9.3 联合（union）联合是几个成员的组合，各成员有名字，所有成员共享同一存储位置。联合变量每时只能保存一个成员的值。联合说明形式上与结构说明类似，用union：union int n; double x; char c; u1, u2;union data fun10(int m, union data u);union data u1, u2, u3, u4, *up;up = (union data *) malloc(sizeof(union data); data 9.3 联合（union）联合是几

27、个成员的组合，各成员有名联合变量的初始化和使用联合变量可以在定义时直接初始化，但这个初始化只能对第一个成员做。例：union data u1 = 3, u2 = 5;联合变量使用形式与结构变量相同，可整体赋值、成员访问、取地址。几个例子：n = u1.n;u1.c = n;m = u2.n + 167;可定义指向联合的指针，可从这种指针出发，通过-运算符访问被指联合变量的成员。 联合变量的初始化和使用可定义指向联合的指针，可从这种指针出发联合变量的存储实现成员共用同一存储位置，存储区大小由大成员决定。对union data，n是整数，d是双精度数，c是字符。需要足以存放双精度数的存储区。成员安

28、排如下图：联合变量的存储实现联合变量使用的基本规则联合变量可看成能改变面目的变量，不同时刻可能以不同性质出现，表示不同东西。使用原则：应该按所保存成员的方式使用：最近对本变量用什么方式赋值（当作哪个成员），就用同样方式（通过同样成员）取值。遵受本规则的使用有效，取值与赋值的一致性由编程者保证，C系统不检查。未遵守规则的使用（取值方式与前面赋值不一致），语言定义未规定效果，结果依赖于具体系统。介绍枚举之后有一个程序例子。联合变量使用的基本规则9.4 枚举（enum）枚举用于定义一组命名常量，枚举常量。描述形式：enum 枚举标志 枚举常量名, .;枚举说明不但引进一组常量名，还为每个常量确定一个

29、整数值。第一个给值0，顺序递增。枚举常量不能重名，多个枚举说明的常量名也必须互不相同。enum color RED, GREEN, BLUE;枚举标志可用于写变量定义等。例：enum color cr1, cr2;定义枚举类型（用typedef）：typedef enum WHITE, BLACK COLOR1;COLOR1 c3, c4; 9.4 枚举（enum）枚举用于定义一组命名常量，枚举常量下面是这种变量在程序里使用的几个例子：cr1 = RED; . .if (cr2 = GREEN) .; . .switch (cr1) case RED: . .; break; case GRE

30、EN: . .; break; case BLUE: . .; break;枚举类型变量实际看作整型变量。主要是提高可读性。枚举常量由编译处理，一次可定义一组常量，很方便。可给枚举常量指定值，随后的枚举常量递增取值。例：enum color RED = 1, GREEN, BLUE, WHITE = 8, GREY = 12, BLACK, PINK = 15;下面是这种变量在程序里使用的几个例子：枚举类型变量实际看作整程序实例使用联合通常是为定义一些函数，使几种不同类型的数据都可以传递给它们处理。例：角度可以表示为弧度（0到2）或角度（度分）。可定义类型ANGLE，所有处理程序都基于该类型。

31、ANGLE数据有两种表示形式，可定义为联合类型。但处理时怎么能知道具体ANGLE变量用的是那种形式？ 解决方案是在ANGLE类型里加标签（表示具体ANGLE变量数据情况的成员）。标签可用整数或其他类型，采用枚举特别合适，因为枚举符是标识符，有助理解。程序实例解决方案是在ANGLE类型里加标签（表示具体ANGL可以定义：enum ANGLETAG DEGREE, RADIAN;typedef struct enum ANGLETAG tag; union struct int deg, mnt degree; double radian; dt; ANGLE;tag是表示标签的枚举成员，dt是表

32、示实际数据的联合，或是结构degree，或者是双精度数radian。有了这个类型后就可以定义相关函数了。 可以定义：例：定义输出角度的函数： void prtdegree(FILE* fp, ANGLE a) switch (a.tag) case DEGREE: fprintf(fp,%d degs %d minutes, a.dt.degree.deg,a.dt.degree.mnt); break; case RADIAN: fprintf(fp, %f radian, a.dt.radian); break; 其他函数类似。例：定义输出角度的函数： 9.5 编程实例数据组排序：考虑用结

33、构重实现学生成绩实例。还想介绍排序的概念及标准库排序函数的使用。 记录文件应包含学生姓名和成绩。下面采用如下形式：02001014 zhangsan 8602001016 lisi 77为在程序里处理这样的学生成绩，定义结构类型： enum MAXNUM = 400; /* 还可以根据需要增加其他常量定义 */typedef struct unsigned long num;char name20; double score; StuRec;9.5 编程实例数据组排序：考虑用结构重实现学生成绩实例。还定义一个外部（学生记录）数组（也可用动态分配）： StuRec studentsMAXNUM;

34、 程序可参考第6章程序实例。现在想增加功能：按成绩排列输出学生记录。可采用多次扫描结构数组的方法，从高到低或从低到高输出（自己想想可能怎么做，要什么假定）。显然不好，效率太低。另一方法是把学生记录按成绩重排而后顺序打印。计算机应用中将一组数据按某种顺序重排是最常见的操作，排序，人们开发了许多有趣的算法。排序是数据结构课的重要内容，这里只想介绍标准库qsort，它能将各种数组的元素按指定顺序排列。定义一个外部（学生记录）数组（也可用动态分配）： 程序可参考排序函数qsort在里定义。 void qsort(void *base, size_t n, size_t size, int (*cmp)

35、(const void *, const void *);void指针是被排序数据组起始位置（qsort不知道数组元素类型）。size_t是无符号整数类型，n表示被排序的数据项数，size表示被排序的数组元素的大小。用qsort时必须通知所需排列方式（比较元素大小的准则），它把“较小”元素排在前面。cmp是比较准则，必须符合qsort对比较函数的类型要求和功能要求。 要对数组students里的snum个学生记录排序，调用形式（scrcmp是自定义的比较函数，下面讨论）：qsort(students, snum, sizeof(StuRec), scrcmp);排序函数qsort在里定义。 用

36、qsor比较函数的类型在qsort原型的参数中描述得很清楚。将比较学生分数函数取名scrcmp，其原型应是：int scrcmp(const void *vp1, const void *vp2); qsort对被排序元素调用比较函数。为正确写出比较函数，需弄清qsort：1）通过参数传给函数什么；2）要求函数以什么方式表示元素比较结果。 qsort传给函数的是指向被排序元素的指针。qsort不知道被排序元素的类型，只能用(void*)。我们应在函数里将指针转换为实际元素类型的指针后使用。qsort要求比较函数在第一个元素“大于”第二个元素时返回正值，两元素相等时返回0，第一个元素较小时返回负

37、值。“大小”关系应根据排序需要确定。 比较函数的类型在qsort原型的参数中描述得很清楚。将比较学为清晰，下面定义先转换到StuRec指针并取出score成员值后再比较大小：int scrcmp(const void *vp1, const void *vp2) double s1 = (StuRec*)vp1)-score, s2 = (StuRec*)vp2)-score; return s1 s2 ? 1 : s1 = s2 ? 0 : -1; qsort“通用”，按排序准则工作。对另一准则，qsort就能对同一组数据做另一种排序。例如希望将学生记录按5分一段分段排列，那么可以采用下面比

38、较函数： int scr5cmp(const void *vp1, const void *vp2) int n1 = (StuRec*)vp1)-score, n2 = (StuRec*)vp2)-score; return n1/5 - n2/5; 为清晰，下面定义先转换到StuRec指针并取出score成员要按姓名排序，可用标准strcmp函数。qsort提供的是指向学生记录的void指针。这里要比较是其中的名字字符串，用char* 指针。可定义下面转接函数： int scmp(const void *vp1, const void *vp2) char *p1 = (StuRec*)v

39、p1)-name, *p2 = (StuRec*)vp2)-name; return strcmp(p1, p2); 函数可简写为：int scmp(const void *vp1, const void *vp2) return strcmp(StuRec*)vp1)-name, (StuRec*)vp1)-name);程序其他部分的修改完善请自己做。要按姓名排序，可用标准strcmp函数。qsort提供的是指一组数据可能有许多不同的排序要求。例如一个超级市场的商品食品记录，可能需要将这些记录按商品名称排序，按食品出厂日期排序，按食品的过期日期排序，按商品的单价排序，按一段时间的销售额排序，

40、按出品厂商名称排序等。只要提供适当比较函数，这些都可借助于qsort完成。还可以用qsort对数组中的一段元素排序。 一组数据可能有许多不同的排序要求。复数的表示和处理C语言提供了许多数值类型，但也不完全，例如这里缺乏复数类型。要写处理复数数据的程序时该怎么办？当然可以用两个double表示一个复数，定义函数：addcomplex(double r1, double i1, double r2, double i2); 结果很难返回。改为：addcomplex(double r1, double i1, double r2, double i2 double *rr, double *ri);

41、参数多，需要记住各个位置，使用很麻烦。注意，这里一个复数是一个逻辑数据体，应定义为类型，再定义一批以复数类型为操作对象的函数。复数的表示和处理C语言提供了许多数值类型，但也不完全，例如这定义为类型后，程序其他部分就会变得清晰简单。人们在程序设计实践中认识到，设计实现一个较复杂的程序时，最重要的是找出所需的一批数据类型。将它们的结构和功能分析清楚，设计并实现。在这些类型的基础上实现整个程序。这样得到的程序更清晰，各个部分功能划分较明确，更容易理解和修改。 考虑复数类型的实现。复数可有多种数学表示方式：平面坐标，极坐标等。某种表示可能更适合某个特定应用，需仔细斟酌。作为例子，这里选择平面坐标，实部

42、和虚部。针对一般复数运算，可用两个double值表示一个复数。 定义为类型后，程序其他部分就会变得清晰简单。考虑复数类型的实应该用什么机制将这两部分结合起来呢？两部分类型相同，可以用两个double元素的数组，或用两个double成员的结构。由于需要定义许多运算，用结构表示有利于将复数作为参数传递和作为结果返回。因此有下面定义：typedef struct double re, im; Complex;下面考虑基于这个类型的运算。由于Complex对象的数据项很少，可以考虑直接传递Complex类型的值和结果，避免复杂存储管理问题。 应该用什么机制将这两部分结合起来呢？由于需要定义许多运算，用

43、基本的算术函数，原型：Complex addComplex(Complex x, Complex y);Complex subComplex(Complex x, Complex y);Complex tmsComplex(Complex x, Complex y);Complex divComplex(Complex x, Complex y);还需考虑如何构造复数。我们不希望使用复数的程序直接访问Complex的成分，否则程序里的错误将很难控制。如果所有使用都经过我们定义的函数，只要这些函数正确，程序里的正确使用就有保证了。下面是几个构造函数：Complex mkComplex(doubl

44、e re, double im);Complex d2Complex(double d);Complex n2Complex(int n);基本的算术函数，原型：还需考虑如何构造复数。我们不希望使用复后两个函数也可看作由double和int到复数的“数值转换”函数，定义它们是为了使用方便：Complex mkComplex(double r, double i) Complex c; c.re = r; c.im = i; return c;Complex d2Complex(double d) Complex c; c.re = d; c.im = 0; return c;Complex n

45、2Complex(int n) Complex c; c.re = n; c.im = 0; return c; 后两个函数也可看作由double和int到复数的“数值转换”加法函数的定义：Complex addComplex(Complex x, Complex y) Complex c; c.re = x.re + y.re; c.im = x.im + y.im; return c;减法函数与此类似。乘法函数的算法复杂一点，根据数学定义也不难给出。除法函数有个新问题：除数为0时该怎么办？复数除法的数学定义是（c 和 d 都为 0 时出问题）： 加法函数的定义：除法函数有个新问题：除数为0

46、时该怎么办？C语言内部类型除0的规定是“其行为没有定义”，编程者自己负责。我们实现复数操作时有两种选择：1）沿用C方式，要求用复数类的人保证不出现除0。2）检查除0的情况，提供动态信息并返回某个特殊值。 采用第一种方式时可直接按公式定义函数。下面函数定义检查除0情况，输出错误信息并返回1的复数。 C语言内部类型除0的规定是“其行为没有定义”，编程者自己负责Complex divComplex(Complex x, Complex y) Complex c; double den = y.re * y.re + y.im * y.im; if (den = 0.0) fprintf(stderr

47、,ComplexErr: div 0.n); c.re = 1; c.im = 0; else c.re = (x.re*y.re + x.im*y.im) / den; c.im = (x.im*y.re - x.re*y.im) / den; return c;Complex divComplex(Complex x, 为了使用方便，还可以定义复数的输出和函数。输出函数向某个流输出一个复数。实现这个函数前先要为复数确定一种输出形式，函数定义： void prtComplex(FILE *fp, Complex x) fprintf(fp, (%f, %f), x.re, x.im);输入函

48、数：int readComplex(FILE *fp, Complex *xp);xp的实参应是Complex地址。函数设计应参考标准库输入函数：实际完成复数输入时返回1，转换失败时返回0，遇文件结束出错误时返回EOF。IO函数最好统一设计，使prtComplex输出能由readComplex输入。 为了使用方便，还可以定义复数的输出和函数。输出函数向某个流输9.6 链接结构（自引用结构）问题的提出（词频统计）设要统计正文文件里各单词出现的次数。典型应用。语言学要统计单词出现频率。分析文献或计算机程序等都要做类似统计工作。新情况：统计前不知道有多少不同的词，无法在编程时准备好统计中使用的完整数

49、据结构。可能方案：动态分配计数器数组，必要时调整大小（用realloc）。问题：新词逐个遇到，反复调整分配效率比较，而且需要使用很大的块，不够灵活。能否找到足够大的存储块也会成为问题。9.6 链接结构（自引用结构）问题的提出（词频统计）希望有一种能方便地动态变化的组织结构，满足被存储数据项动态增加/减少的需要。链接结构。链接结构用指针（指针的最重要用途）、结构（struct）和动态存储管理实现，基本构件是自引用结构。自引用结构的对象分为两部分：一个结构通过指针引用同类结构，多个结构通过指针建立联系。指向结构的指针称为链接，形成的复杂数据结构称为链接结构。希望有一种能方便地动态变化的组织结构，满

50、足被存储数据项动态增最简单的链接结构是线性链接形成的表/链接表。每个自引用结构有一个链接指针，一批结构一个链接到一个形成序列，如下图。表像链条，自引用结构是链节，表结点，结点间由指针连接形成整个结构。所有结点（结构）来自动态分配。从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。最简单的链接结构是线性链接形成的表/链接表。每个自引用结构有以自引用结构为基本构件可构造出许多复杂的数据结构。另一种典型结构是二叉树，其中结点有两个链接指针。下面是一个二叉树结构。数据结构课将进一步讨论这方面问题。以自引用结构为基本构件可构造出许多复杂的数据结构。

51、另一种典型在C中定义和使用自引用结构以词频统计为例。用链接表作为基本数据结构。对应于词的相关信息包括词本身及其计数。为简单，假设词长不超过19个字符（无此限制，就要设法保存和处理任意长的词。这个问题可作为一个大程序练习），设整数表示范围足以应付词的统计（否则考虑用其他类型，如 unsigned long）。在这些假设下，在统计用的结构里，两个基本数据成员可定义为：char word20;int count;在C中定义和使用自引用结构在这些假设下，在统计用的结构里，两新问题：自引用结构里有一个指向本类结构的指针。下面介绍两种方法，在简洁性或清晰性方面各有长短。应该把所需自引用结构定义为类型。不但

52、要定义结构类型，还应定义一个指向结构的指针类型。第一种定义方式：typedef struct node NODE, *LINK;struct node char word20; int count; LINK next;C允许写不完全结构说明。先定义两个类型：结点类型NODE和指向该结构的指针类型LINK。结构未描述。新问题：自引用结构里有一个指向本类结构的指针。下面介绍两种方使用的例子：LINK p, q;p = (LINK)malloc(sizeof(NODE);q = (LINK)malloc(sizeof(NODE); /* p 所指结点其他成分的赋值 */p-next = q; /*

53、 q 所指结点其他成分的赋值 */q-next = NULL;使用的例子：第二种方式，定义了同样的两个类型：typedef struct node char word20; int count; struct node *next; NODE, *LINK;较紧凑。但不易看清结构的next成员是LINK类型的指针成员。可以根据自己的喜好选用。有了结构类型定义后，主函数部分：第二种方式，定义了同样的两个类型：#inlcude #include /* 需要判断字符类型 */#include /* 要做串复制和比较 */#include /* 做动态存储分配 */enum MAXLEN = 20 ;

54、typedef struct node NODE, *LINK; struct node char wordMAXLEN; int count; LINK next;int getword(int limit, char w); LINK addword(LINK l, char w);void printwords(LINK l);LINK list = NULL; /* 表的头指针 */char wordMAXLEN; /* 临时字符数组 */#inlcude int main (void) while (getword(MAXLEN, word) 0) list = addword(li

55、st, word); printwords(list); return 0;addword完成对一个词的统计动作，返回修改后的统计表。主函数对每个词调用addword，更新统计表。int main (void) printwords用循环实现，借助一个指针（参数也是局部变量）实现对表各结点的顺序访问：void printwords(LINK p) for ( ; p != NULL; p = p-next) printf(%d %sn, p-count, p-word);表最后空指针用于循环终止判断。链接表基本处理方式：用一个指针从表头结点开始顺序处理结点，利用链接指针，直到表结束。这种指针称为扫描指针。参数p就是扫描指针，函数调用时它得到表头结点地址。printwords用循环实现，借助一个指针（参数也是局部变LINK addword(LINK l, char w);addword是最关键的部分，第一个参数是统计表（或部分），第二个参数是当时处理的词。addword完成一个词的统计，