1、高级语言程序设计高级语言程序设计第第8章章 客观对象的描述客观对象的描述 结构体程序设计结构体程序设计本章要解决的问题本章要解决的问题1.学生成绩管理系统的实现学生成绩管理系统的实现(数组和链表）数组和链表）2.志愿者管理问题志愿者管理问题3.扑克牌洗牌和发牌模拟扑克牌洗牌和发牌模拟 学习目标学习目标理解客观对象的描述方法理解客观对象的描述方法结构体结构体掌握结构体类型变量的定义和使用方法掌握结构体类型变量的定义和使用方法学会结构体或指向结构体的指针作为函数学会结构体或指向结构体的指针作为函数参数的参数的了解了解自引用结构体及链表结构自引用结构体及链表结构了解了解共用体类型和枚举类型共用体类型
2、和枚举类型的定义和使用的定义和使用方法方法 1 学生成绩管理系统的实现学生成绩管理系统的实现问题描述：假设我们要为学校问题描述：假设我们要为学校教务部门教务部门开开发一个学生成绩管理系统，要求能用这个发一个学生成绩管理系统，要求能用这个系统系统录入学生成绩录入学生成绩、修改学生成绩、统计修改学生成绩、统计学生成绩、查询学生成绩学生成绩、查询学生成绩、输出学生成绩输出学生成绩（报表）。为了简单，现在只考虑某（报表）。为了简单，现在只考虑某一门一门课程课程的成绩的成绩，每个同学的成绩包括，每个同学的成绩包括平时、平时、期中、期末和平均成绩期中、期末和平均成绩。分析分析在第在第5章已经把这个问章已经
3、把这个问题题模块化模块化了了它的主流程是它的主流程是 当时还没有能力实现当时还没有能力实现，每个函，每个函数模块用了数模块用了一个树桩一个树桩stub或存或存根根先占在那里先占在那里 void input(void) printf(“okn”); 现在到了可以实现的时候了现在到了可以实现的时候了 假设现在要管理的某门课程的学生数是固定假设现在要管理的某门课程的学生数是固定的的60，首先要解决的是，首先要解决的是如何存放这如何存放这60个学个学生的生的某门某门课程的课程的成绩相关的信息成绩相关的信息？某门课程成绩相关的信息应该包括：某门课程成绩相关的信息应该包括：姓名、学号、平时成绩、期中成绩、
4、期末成绩、总评成绩用前面学过的方法：数组用前面学过的方法：数组用多个一维数组用多个一维数组char *num60；char *name60;int dailyGrade60;int midGrade60；int endGrade60;float average60;这时各个模块函数的原型可定义为这时各个模块函数的原型可定义为 void input (char *num, char *name, int dg, int mg, int eg, int ag); 其它几个略其它几个略 void print (char *num, char *name, int dg, int mg, int eg
5、, int ag); 请大家自己实现这个版本请大家自己实现这个版本这种方法有什么特点？这种方法有什么特点？数组的内存映像数组的内存映像 1390788978839272950001000200030004aaaabbbbccccdddd001004F30C330D80907889780533数据在内存中的分布数据在内存中的分布比较分比较分散散希望的内存分配图希望的内存分配图 0001aaa男1999908372820002bbb男1999789288780003ccc女1999897298660004ddd女19997895879015每一组属性每一组属性（也叫一个记录，二维表格的一行）（也叫
6、一个记录，二维表格的一行）放在一起放在一起看成一个整体看成一个整体，同组成员彼此相邻同组成员彼此相邻不同组的属性也彼此相邻不同组的属性也彼此相邻 这样的这样的一组属性数据一组属性数据所表达的所表达的客观对客观对象象怎么定义呢？怎么定义呢？能不能像整数用能不能像整数用int类型，字符用类型，字符用char类型那样定义问题中类型那样定义问题中的对象为一的对象为一种类型呢？种类型呢？如学生类型如学生类型如果能，就可以如果能，就可以用这个用这个自定义的学生自定义的学生类型类型去创建问题中涉及的学生对象啦。去创建问题中涉及的学生对象啦。学生对象的描述学生对象的描述你能不能给你能不能给学生下个定义学生下个
7、定义？不同的人可能关注学生不同的不同的人可能关注学生不同的一组特征一组特征/属性属性如：学生处关心的是学生注册相关的属性如：学生处关心的是学生注册相关的属性 姓名，学号，年龄，性姓名，学号，年龄，性 别，出生日期，别，出生日期，籍贯，家庭住址，籍贯，家庭住址，.不同的学生只是属性值不同而已不同的学生只是属性值不同而已教务部门把学生对象描述成教务部门把学生对象描述成学号，姓名，平时成绩，期中成学号，姓名，平时成绩，期中成绩，期末成绩，总评成绩绩，期末成绩，总评成绩确定了对象的属性，对象就基本确定了对象的属性，对象就基本确定了确定了C语言允许用语言允许用结构体类型结构体类型表达客观表达客观世界的对
8、象世界的对象 struct 结构体类型名结构体类型名 成员成员列表；列表； ;其中其中struct 是关键字是关键字，成员列表，成员列表给出成员的类型和名字，注意这给出成员的类型和名字，注意这个定义的个定义的结尾必须跟一个分号结尾必须跟一个分号；表示结构体类型定义结束。表示结构体类型定义结束。例例1 学生结构体类型的定义学生结构体类型的定义 （成绩信息相关的）（成绩信息相关的）struct student char *num; char *name; int dailyGrade; int midGrade; int endGrade; float average; 这样我们就定义了一种这样我
9、们就定义了一种新的类型新的类型它叫它叫struct student，它与我它与我们熟悉的们熟悉的int，float等具有同等等具有同等地位。地位。 例例2 平面上的点结构体类型定义平面上的点结构体类型定义 struct point int x; int y; ;任何一类客观世界的对象均可抽任何一类客观世界的对象均可抽象成一个结构体类型象成一个结构体类型结构体结构体变量变量的定义和初始化的定义和初始化有了结构体有了结构体类型类型之后就可以用它定义具之后就可以用它定义具体的客观体的客观对象（结构体类型的变量）对象（结构体类型的变量）struct student li, wang; struct s
10、tudent zhang;注意现在的类型名是注意现在的类型名是 struct student 对象对象li, wang, zhang的属性是的属性是什么？什么？定义之后分别给各个成员赋值，定义之后分别给各个成员赋值，要用要用成员运算符成员运算符 . 如如li.num=00002;li.name=lihong;li.dailyGrade=85;li.midGrade=95;li.endGrade=88;li.average=89.2;在定义时直接初始化在定义时直接初始化struct student zhang = 0001, zhangqiang , 80, 70, 100, 83.3;结构体类
11、型的变量支持结构体类型的变量支持整体赋值整体赋值wang = li; 有时在有时在定义结构类型定义结构类型的时候定义的时候定义结构结构体变量体变量struct student char *num; char *name; int dailyGrade; int midGrade; int endGrade; float average;zhang, li, wang; 也可以省略结构体类型名也可以省略结构体类型名struct char *num; char *name; int dailyGrade; int midGrade; int endGrade; float average;zhan
12、g, li, wang;这样意味着在其它地方不需要定义这种类型这样意味着在其它地方不需要定义这种类型的其它结构体变量。的其它结构体变量。你有没有注意到定义结构体类型的变量挺你有没有注意到定义结构体类型的变量挺麻烦的，其类型名是两个单词，如学生结麻烦的，其类型名是两个单词，如学生结构体类型构体类型 struct student，C/C+的标准类型的标准类型 int，float，double，char等都是一个单词等都是一个单词能不能也把结构体类型名定义成一个单词能不能也把结构体类型名定义成一个单词给结构体类型起给结构体类型起别名别名：typedef typedef struct char *nu
13、m; char *name; int dailyGrade; int midGrade; int endGrade; float average; STUD;这样就可以用这样就可以用STUD直接定义结直接定义结构体变量构体变量STUD zhang, wang; 实际上实际上typedef 还可以定义一个数组的还可以定义一个数组的别名，一个指针的别名等，如别名，一个指针的别名等，如typedef int iarray1010; l定义了有定义了有10个元素的整型数组的别名个元素的整型数组的别名为为iarry10。liarray10 a,b;typedef int* iptr; l它定义了整型指针
14、的别名它定义了整型指针的别名 liptr x,y;指向结构体的指针指向结构体的指针STUD zhang，wang；STUD *sPtr=&zhang；同样可以像从前那样使用间接运同样可以像从前那样使用间接运算符访问。算符访问。 (*sPtr).num=”00005” ; (*sPtr).dailyGrade = 80;等等，等等，C/C+又提供一种新的运算符又提供一种新的运算符称为称为指向运算符指向运算符，访问结构体访问结构体对象的成员，对象的成员， sPtrnum=”00005”; sPtr dailyGrade = 80;思考题思考题 STUD结构体类型的结构体类型的变量变量在内存中占多在
15、内存中占多少字节？少字节？如果定义如果定义typedef structlchar a;lint b;lchar c;TEST;呢？呢？结构体变量内存映像的大小未必结构体变量内存映像的大小未必一定是它的成员变量大小之和一定是它的成员变量大小之和 结构体类型的定义可以嵌套结构体类型的定义可以嵌套从学生管理的角度看学生对象，有一个从学生管理的角度看学生对象，有一个属性是生日，生日也可以定义成一个结属性是生日，生日也可以定义成一个结构类型如构类型如struct date int year； int month; int day;这样学生结构类型中就可以包含一个这样学生结构类型中就可以包含一个生生日成员
16、日成员，即，即struct student2 char *num; char *name; struct date birthday； ;那么在利用那么在利用student结构类型创建学生结构类型创建学生对象时就可以对象时就可以 struct student2 zhang； zhang.birthday.year = 1980; zhang.birthday.month=9;结构体数组和指向结构体数组的指针结构体数组和指向结构体数组的指针struct student stu60 或或STUD stu60; STUD *sPtr = stu;完整的实例图完整的实例图8.3代码中有两点需要注意代码
17、中有两点需要注意一是由于一是由于STUD的的name和和num成员是字符型指针，是不能直接成员是字符型指针，是不能直接使用使用scanf输入字符串的，见第输入字符串的，见第24行到第行到第31行的代码。行的代码。第二点需要注意的就是每个结构第二点需要注意的就是每个结构体的体的数值成员数值成员在在scanf语句中必语句中必须用取地址运算获得地址。须用取地址运算获得地址。结构体作为函数的参数结构体作为函数的参数 思考题：思考题：如果一个结构体类型的成员非常如果一个结构体类型的成员非常多，用结构体作为函数的参数有多，用结构体作为函数的参数有什么不好？什么不好？改为改为传递指针传递指针如何？如何？结构
18、体指针作为函数的参数结构体指针作为函数的参数传地址传地址类似的还有类似的还有让函数返回一个结构体让函数返回一个结构体STUD zhang = createStudent(zhangli, 00003, 90, 80, 85);抽象数据类型抽象数据类型结构体类型作为一种抽象的类型结构体类型作为一种抽象的类型仅仅对客观对象所具有的仅仅对客观对象所具有的属性属性进进行了抽象，行了抽象， 然而客观世界的对象不仅有丰富然而客观世界的对象不仅有丰富的属性，还应该具有各种各样的的属性，还应该具有各种各样的行为。行为。例如例如STUD类型的抽象行为类型的抽象行为选课选课：STUD createStudent
19、( char* name, char* num, int dgrade, int mgrade, int egrade); 查分查分：float searchGrade(STUD stud, float average);比较比较：bool compareStudent(STUD stud1, STUD stud2);汇报汇报：void printStudent(STUD stud);用对象的用对象的一组抽象属性和一组抽一组抽象属性和一组抽象的行为象的行为定义的数据类型才是真定义的数据类型才是真正的正的数据类型数据类型(abstract data type)，缩写为，缩写为ADT。抽象数据。抽
20、象数据类型的类型的行为行为是与外界其它对象进是与外界其它对象进行交流的行交流的接口接口。再如字符串再如字符串typedef char * string 或者或者 typedef char string size string zhangName=“zhang qiang”; string liName = “lihong”;一组操作一组操作(创建、比较、连接、计算长度、创建、比较、连接、计算长度、查找查找)，就构成了，就构成了 string抽象数据类型抽象数据类型实际上我们更关心的是这组表达对象行为实际上我们更关心的是这组表达对象行为的的操作操作。 在面向对象的程序设计中把抽象在面向对象的程序
21、设计中把抽象数据类型数据类型封装为一个封装为一个类类。一些典型的抽象数据类型构成了一些典型的抽象数据类型构成了数据结构课程数据结构课程中的主要研究对象，中的主要研究对象，如如线性表、栈、队列、树、图等线性表、栈、队列、树、图等。SGMS的实现（的实现（结构体数组结构体数组版本）版本）学生成绩管理系统学生成绩管理系统Student Grade Management System缩写为缩写为SGMS 录入成绩模块录入成绩模块void input(STUD *&stud, int &num); /引用参数版本引用参数版本或者或者 void input(STUD * stud, int *num);
22、/二级指针版二级指针版本本统计成绩模块统计成绩模块void statistic(STUD stud &, int m); /引用参数版本引用参数版本或或void statistic(STUD stud *, int m); /二级指针版本二级指针版本输出报表模块：输出报表模块：void print(const STUD &stud, int m); 或或void print(const STUD stud*, int m);其它略其它略看完整的代码看完整的代码结构体数组方法的特点结构体数组方法的特点通过结构体数组方法或指向结构通过结构体数组方法或指向结构体数组的指针，可以比较好的实体数组的指针
23、，可以比较好的实现学生成绩管理问题，现学生成绩管理问题，特别是数组特别是数组下标的索引功能下标的索引功能使上使上述几个模块的实现都很方便述几个模块的实现都很方便， 但是但是一个数组一旦申请其大小就相对一个数组一旦申请其大小就相对固定，增加更多的元素比较困难固定，增加更多的元素比较困难在某个元素的位置插入一个元素，在某个元素的位置插入一个元素，不能直接进行，必须把那个位置不能直接进行，必须把那个位置之后的元素向后移一个位置。之后的元素向后移一个位置。把某个位置的元素删除，必须把把某个位置的元素删除，必须把那个位置之后的元素向前移。那个位置之后的元素向前移。另一种存储数据的方法另一种存储数据的方法
24、链表链表自引用结构体自引用结构体 请大家看下面这个结构定义有意义吗？请大家看下面这个结构定义有意义吗？ struct something struct something obj1; struct something obj2;下面的呢？下面的呢？typedef struct something char data10; struct something* next;Node，*nPtr;一个结构体对象的指针成员赋以和它相邻一个结构体对象的指针成员赋以和它相邻的那个结构体对象的首地址，则这个结构的那个结构体对象的首地址，则这个结构体对象便指向了那个和它同类的相邻的结体对象便指向了那个和它同类的
25、相邻的结构体对象。构体对象。自引用结构自引用结构 链表节点（链表节点（Node），），注意，链表的最后注意，链表的最后一个节点的指针成员应该令其为空指针，一个节点的指针成员应该令其为空指针，也称为接地；还可以为链表的第一个节点也称为接地；还可以为链表的第一个节点定义一个指针指向它，作为定义一个指针指向它，作为链表的头链表的头（head）。）。链表存储结构与结构体数组的不同链表存储结构与结构体数组的不同各个结构体变量之间是各个结构体变量之间是借助指针联系借助指针联系在一在一起的。起的。各个结构体变量是独立存在于内存中，它各个结构体变量是独立存在于内存中，它们可能们可能不是连续存储不是连续存储。如
26、果查找第几个结构体变量必须从链表的如果查找第几个结构体变量必须从链表的头开始逐个通过指针查找，头开始逐个通过指针查找，不能像数组下不能像数组下标那样直接定位。标那样直接定位。在链表中在链表中插入插入一个节点一个节点如果要在某个节点前或后如果要在某个节点前或后插入插入一个新节点，一个新节点，找到位置后只需修改相关的指针，无须做找到位置后只需修改相关的指针，无须做任何移动，任何移动， 如果要在节点如果要在节点n1和和n2之间插入之间插入一个已经一个已经准备好的节点准备好的节点n3，在找到节点，在找到节点n1，n2之之后，只需先令后，只需先令 n3next=n2next; n1next=&n3; 链
27、表中节点的删除链表中节点的删除如果要如果要删除删除某个节点，找到位置后只需修某个节点，找到位置后只需修改相关的指针，也无须做任何移动。改相关的指针，也无须做任何移动。 例如，如果要删除节点例如，如果要删除节点n2，只需令，只需令 n1next=n1nextnext;一个链表如果它的节点不是根据需要动态一个链表如果它的节点不是根据需要动态产生的，那么它就是产生的，那么它就是静态链表静态链表。它不需要。它不需要动态地增加和开辟节点，也不能动态地删动态地增加和开辟节点，也不能动态地删除和回收节点的存储空间。除和回收节点的存储空间。 如果节点的个数事先如果节点的个数事先未知未知，可以动态生成可以动态生
28、成一个节点，一个节点，插入到链表的指定位置或追加插入到链表的指定位置或追加到链表的末尾。也可以根据需要动态地删到链表的末尾。也可以根据需要动态地删除不需要的节点。这样的链表就是除不需要的节点。这样的链表就是动态链动态链表。表。 学生链表节点类型学生链表节点类型 struct student char *num; /data part char *name; int dailyGrade; int midGrade; int endGrade; float average; struct student *next; /link pointer;typedef struct student ST
29、UD;例例1 建立静态学生链表（基本算法）建立静态学生链表（基本算法） 1) 定义三个学生节点变量及头指针定义三个学生节点变量及头指针 STUD s1,s2,s3,*head;2)让让Head指向第一个学生对象指向第一个学生对象 head=&s1;3)给学生节点数据成员赋值给学生节点数据成员赋值s1.name=aaaaaaaa; s1.num=00001; 4) 把把s2链接到链接到s1尾部尾部 s1.next=&s2;类似的给类似的给s2数据成员赋值，把数据成员赋值，把s3链接到链接到s2的尾部的尾部注意注意s3的指针成员赋值的指针成员赋值NULL查看完整代码查看完整代码例例2 建立动态学生
30、链表的建立动态学生链表的基本算法基本算法1) 定义一个指向头节点的指针定义一个指向头节点的指针head，一个指，一个指向尾节点的指针向尾节点的指针r和一个指向新建节点的指针和一个指向新建节点的指针p；2) 创建一个空表创建一个空表(头指针头指针head=NULL);3) 动态申请新节点，并用动态申请新节点，并用 p指向它。指向它。4) 输入新节点的数据且输入新节点的数据且指针成员赋值为空指针成员赋值为空。5) 把新节点链入把新节点链入head为头指针的链表为头指针的链表 若链表为空，将新节点直接链接到头指针若链表为空，将新节点直接链接到头指针head=p，同时，同时r = p； 若链表非空，将
31、新节点接到表尾，即若链表非空，将新节点接到表尾，即rnext=p，同时，同时 r = p（r指针始终指向尾节指针始终指向尾节点）；点）；6) 继续吗？如果继续转到继续吗？如果继续转到3)，否则结束。，否则结束。查看完整代码查看完整代码思考题思考题：如何把新建节点插入到链表的如何把新建节点插入到链表的第一个节点第一个节点之前作为新头节点？之前作为新头节点？这种方法可以使节点逆序链接起来。这种方法可以使节点逆序链接起来。Sgms的实现（链表版本）的实现（链表版本）函数原型为：函数原型为：STUD *createLink(STUD *head);/从空链表开始从空链表开始void modify();/略略void query(); /略略void statistic(); /略略void printLink(STUD *head); /打印成绩单打印成绩单STUD *insertNode(STUD *head); /在学号为在学号为num 的节点前插入一个节点的节点前插入一个节点STUD *deleteNode(STUD *head); /删除学号为删除学号为num的节点的节点 查看完整代码查看完整代码小结小结作业作业
