第10章结构体与链表.ppt

1、问题及作业说明：,9.2 将输入字符串(有效字符)按逆序复制到字符串str1。按题意原字符串似不应改变，使用库函数要明确其详细功能（查baidu或测试）,且不使用标准库函数也要会。,#include #include int strReverse (char *str1,char *str2) char *p; p=strrev(str2);/翻转str2并返回首址 strcpy(str1,p); return strlen(str1); void main() char str1100,str2100;/必须是数组 int length; gets(str2); length=strReve

2、rse(str1,str2); puts(str2);puts(str1);printf(“%d”,length); /按此程序源串也被反转！,int strReverse (char *str1,char *str2) char *p=str2; int count=0; while(*p!=0)+p;/定位结束符 -p; /指向最末一个字符 while(p=str2)/从后向前逐个拷贝 *str1=*p;+count; +str1;-p; *str1=0; /注意str1当前位置与0 return count; /较调用strlen高效！ ,问题及作业说明：,作业9.3 字符串连接.其一不

3、应引入新数组str3，其二注意0的处理，其三，测试时注意字符数组的长度,int strCatch(char *str1,char *str2) int count=0; while(*str1!=0) +str1; +count; while(*str2!=0) *str1=*str2;count+; +str1;+str2; *str1=0; return count; ,#include int strCatch(char *str1,char *str2) int count=0; while(*str1) +str1; +count; while(*str1+=*str2+) +cou

4、nt; return count; void main() char str1200,str2100; /注意长度 int length; gets(str1); gets(str2); length=strCatch(str1,str2); puts(str1);puts(str2); printf(%d,length); ,作业9.4 字符串裁剪,/裁剪尾部空格或制表符和换行符 int trim(char *str) int count=0; while(*str) +str; +count; -str; while(*str= |*str=t|*str=n)-str; -count; *

5、(str+1)=0; return count; ,/裁剪头部和尾部空格制表符和换行符 int ntrim(char *str) char *first=str,*last; int count=0; while(*first= |*first=t|*first=n)+first; last=first; while(*last)+last; -last; while(*last= |*last=t|*last=n)-last; *(last+1)=0; while(first=last)*str+=*first+; +count; *str=0;/务必注意str的当前位置 return co

6、unt; ,作业9.4 字符串裁剪,/裁剪全部空格、制表符和换行符 int ntrims(char *str) char *insertLocationPtr=str,*traversePtr=str; int count=0; while(*traversePtr!=0) if(*traversePtr= |*traversePtr=t|*traversePtr=n) +traversePtr; else *insertLocationPtr=*traversePtr; +count; +traversePtr; +insertLocationPtr; *insertLocationPtr=

7、0; return count; ,引,对于学生信息管理系统中某学生的学号/姓名/性别等数据,用前面的知识只能定义一些相互独立的变量,如int num; char name20; char sex;实际上，这些数据应该能够通过该学生的ID统一进行访问。 希望存在一种语法能将不同类型的成员封装到一个变量中(如将学生Tom的上述成员封装到一个变量stuA),之后能类似stuA.num,stuA.age来方便的访问各成员 问题:定义一个能封装多个成员的变量，必须先确定该类变量所属的类型，属于什么类型？属于一种构造类型，用struct+类型名定义类型，后据此类型定义这种类型的变量,struct Stu

8、dent int num; char name20; char sex; ;,struct Student stuA; scanf(“%d”,typedef struct Student Student; /Student stuA;,类似struct Student将多个数据成员组合成一个整体而形成的类型统称为结构体类型，是一种构造类型。注意struct Student是类型名,可用其声明变量。为简便常给struct Student起别名为Student,第十章 结构体与共用体,10.1.1结构体类型定义,/常见C语言教材用法 struct student int num; char nam

9、e20; char sex; ; /注意分号！ struct student stuA; scanf(“%d”,/数据结构用法 struct Student int num; char name20; char sex; ; /实际该分号前也可定义变量 typedef struct Student Student; Student stuA; scanf(“%d”,/数据结构用法紧凑版 typedef struct Student int num; char name20; char sex; Student;,结构体类型定义举例结构体嵌套,struct date int year; int

10、month; int day; ; struct student int num; char name20; char sex; struct date birthday; float score; ; struct student StuA; stuA.birthday.year=1981;,typedef struct Date int year; int month; int day; Date; typedef struct Student int num; char name20; char sex; DateType birthday; float score; Student;

11、Student StuA; stuA.birthday.year=1981;,结构体类型定义说明, “结构体类型名”与“成员名”遵循命名规则 成员类型可以是除本身所属结构体类型外的任何已有数据类型。 在同一作用域内，结构体类型名不能与变量名、函数名或其它类型名重名。 同一个结构体各成员不能重名，但允许成员名与程序中的变量名、函数名或者不同结构体类型中的成员名相同。 结构体类型的作用域与普通变量的作用域相同：在函数内定义，则仅在函数内部起作用；在函数外定义，则有全局作用域。 结构体类型定义只说明成员组成情况,仅当定义该类型的变量时方在内存中为各成员变量开辟存储空间。故使用结构体必须先定义结构体类

12、型；后定义该结构体类型的变量；两者缺一不可 结构体类型定义的末尾有分号！区分类型名和变量名,typedef struct Date int year; int month; int day; Date; typedef struct Student int num; char name20; char sex; DateType birthday; float score; Student; Student StuA; stuA.birthday.day=5;,10.1.2结构体变量的定义、引用和初始化,1结构体变量的定义 （1）先定义类型，后定义结构体变量。 struct date int

13、year; int month; int day; ; struct date date1,date2; （2）定义结构体类型的同时定义结构体变量。如 struct student int num; char name20; char sex; struct date birthday; float score; stu1,stu2; （3）直接定义结构体变量。如 struct int num; char name20; char sex; struct date birthday; float score; stu1,stu2;,区分结构体类型与结构体变量 结构体变量各成员依据定义顺序顺序存

14、放 结构体变量占据的字节数如何求？ 数据结构中如何定义结构体变量？,2.结构体变量的引用,(1)使用成员运算符.引用结构体变量的成员。 struct student stu1,stu2; stu1.num=1001; gets(); scanf(%d, “(*p).成员名”、“p-成员名”与“stu.成员名”等价，后两种更直观 成员运算符“.”与指向运算符“-”的优先级同，高于指针运算符* 不能将结构体变量当作一个整体进行输入、输出或“赋值” struct date date1,date2; date1=1988,8,5; scanf(“%d%d%d”, 【思考】“(*p).

15、成员名”中的圆括号能否省略？,3结构体变量的初始化,定义结构体变量的同时依次写出全部或部分成员变量的初始值。如： struct student stu1=1001,Zhang San,M,1988,8,10,580; struct student stu2=1002,Li Ping,F,1989,2,5,595; struct student stu3=1002,“Li Ping”,F,1989;/其余默认零 【说明】 初始化前，结构体变量各成员的取值是随机的。 花括号内初值的顺序、类型要与结构体成员的顺序和类型一致。 【注意】初始化时，花括号内的数据不能包含变量。如以下程序片段的最后一行不正

16、确： struct date int year;int month;int day; date1=1988,8,10; struct student int num; char name20; char sex; struct date birthday; float score; stu = 10010,zhangsan,M,date1,580;,10.1.3 结构体程序举例,例10.1 输入一个学生的信息并显示。,#include void main() struct dateint year;int month;int day; struct studentint num;char na

17、me20; char sex; struct date birthday;float score; ; struct student stu; scanf(%d, ,例10.2函数input中输入一学生的信息，函数list中显示,#include struct date int year;int month;int day; ; struct studentint num;char name20;char sex; struct date birthday;float score; ; struct student input() struct student stu; printf(“请输入

18、学生学号:”); /后文提示略 scanf(%d,3个函数中stu对应内存空间是否相同？ 将结构体类型定义放到main函数如何?,例10.3用指针作参数输出结构体数组内的学生信息,#include struct student int num; char name20; float score; ; void print(struct student *p) int i; printf( 学号 姓名 成绩n); for(i=0;inum,p-name,p-score); void main() struct student stu3=101,li,583,102,wu,590,103,han,

19、560; void print(struct student *); print(stu); ,教材图10.4中算法与程序不符 区分p-num+;(p+)-num;(+p)-num,例10.4多人通过输入候选人姓名投票,统计各候选人票数,#include #include #define N 3 #define M 11 void main() struct person char name20; int count; leaderN=zhangsan,0,lisi,0,wangwu,0; int i,j; char name20; for(i=0;iM;i+) printf(请输入候选人姓名

20、：n); gets(name); for(j=0;jN;j+) if(strcmp(,name)=0) leaderj.count+; for(i=0;iN;i+) printf(%8s:%dn,,leaderi.count); ,结构体数组初始化的方式？,例10.5输入学生学号姓名及成绩,求平均分与最高分学生信息,struct student int num; char name20; float score; ; void input(struct student stu); float aver(struct student stu) in

21、t search(struct student stu) void list(struct student student1) void main() struct student stuN; float average; int max; input(stu); average=aver(stu); max=search(stu); printf(平均成绩为%6.2fn,average); printf(最高分学生为:n); list(stumax); ,作业:,10.1 10.2 10.3 10.4,回顾：,结构体变量+结构体类型+结构体成员引用+结构体作函数参数+结构体指针+结构体数组

22、P276input函数中输入姓名scanf(“%s”, char name20; float score; ; /分号！ void print(struct Student *p) int i; printf( 学号 姓名 成绩n); for(i=0;inum,p-name,p-score); /-是(* ).的缩写，如(*p).num (*p).name void main() struct student stus3=101,li,583,102,wu,590,103,han,560; print(stus); ,10.2 链表,引言：数组元素存储在一片连续的内存单元中，从而给数组带来两方

23、面问题：其一，个数不确定时需定义一个最大长度；其二，向数组增加或删除一个数据时，需要移动大量元素。 链表：一种动态地进行存储分配的数据结构，不需要事先确定最大长度，在插入或者删除一个元素时也不会引起大量数据的移动 要求:掌握链表结构、链表的定义与链表的创建/插入/删除/输出,head/L,1、链表结构,【结构】 “首”结点+“尾”结点+中间结点，每个结点包括两部分：一部分是用户需要用的实际数据，称为数据域；另一部分是下一个结点的地址，称为指针域。头指针head指向链表的首结点，首结点与中间结点的指针域指向后继结点,表尾结点的指针域存放空地址（常表示为NULL，是值为0的符号常量,编程时需先定义

24、）。,【说明】（1）链表中各元素在内存中的存储单元通常不连续 （2）查找链表结点必须从头指针开始顺序访问至找到或到表尾(NULL不可缺！)，不如数组快！ （3）头指针至关重要，可标识或者代表整个单链表，声明链表实际就是声明一个基类型为结点类型的头指针,head/L,2、链表的定义,struct student int num; char name20; float score; struct student *next; ; struct student stuA; struct student *head,*L,*p; stuA.num=101; stuA.next=NULL; head=,

25、struct LNode /表结点 char data; /数据域 struct LNode * next;/指针域 ; Strcut LNode node1,node2;/定义两表结点 struct LNode* La,*Lb; /定义两链表 /或typedef struct LNode LNode /typedef struct LNode* LinkList; /LNode node1,node2; LinkList La,Lb;,链表的分类,分类：创建链表结点有两种方式：其一，使用结构体变量或数组元素充当结点；其二，在程序执行过程中动态开辟结点。第一种方式创建的链表称为静态链表，第二种

26、方式创建的链表称为动态链表。 特点：静态链表各结点所占用的存储空间在程序执行完毕后由系统释放；动态链表可在程序执行过程中调用动态存储分配函数释放；后者更灵活 适用范围：链表长度固定且结点个数较少时通常使用“静态链表” ，其它情况用动态链表 动态链表操作:创建+输出+删除+插入,静态链表示例eg10.6含三个学生的静态链表,#include struct student int num; char name20; float score; struct student *next; ; void main() struct student a=10011,zhangsan,592,b=10012

27、,lisi,581, c=10013,wangwu,656; struct student *L,*p; /教材中L一律用head L= ,用数组构造静态链表也可： struct student stus=.,.,.; struct student * L=stus; stus0.next= 如何”顺序“输出？,动态链表示例动态创建三个结点构造链表,#include struct student int num; char name20; float score; struct student *next; ; void main() struct student *L,*p; p=(stru

28、ct student*)malloc(sizeof(struct student); scanf(“%d%s%f”, ,如何创建n个结点的动态链表？,3、链表基本操作动态创建,思路：共循环n次，每次循环开辟一个结点，并令p1指向该新结点，把p1所指向的结点连接到当前表尾结点（p2）的后面。 若首次开辟则让表名或头指针指向首结点,此外注意新结点指针域的赋值,eg10.7设计函数创建含n个顶点的链表,#include #include #define LEN sizeof(struct student); struct student *create(int n) struct student *

29、head=NULL,*p1,*p2; int i; for(i=1;inum, ,3、链表基本操作-输出,#include void print(struct student *head) struct student *p=head; while(p!=NULL)/只要p不空,用for更不容易出错 printf(学号:%d 成绩:%3fn,p-num, p-score); p=p-next; /p+可否？ ,3、链表的基本操作-删除(指定学号的学生结点),思路:定位需删除结点及其前驱，修改前驱结点指针进行删除 定位:设指针prePtr和curPtr,只要curPtr还指向一个结点且指向的结点

30、的学号不符合要求则两个指针均后移。循环结束后若curPtr为NULL说明未找到，否则说明找到。,struct student *ListDelete(struct student *head,int num) /删除指定学号的学生结点，返回删除该结点后的链表的头指针 struct student *prePtr=NULL,*curPtr=head; while(curPtr!=NULL /教材:只要curP非所寻且未到尾结点则继续,循环结束后看有没有找到,3、链表基本操作删除2-教材,只要curP非所寻且未到尾结点则继续,循环结束后看有没有找到 若中间找到则curP-num=num;若中间没找

31、到则不等,例10.9写函数删除指定学号的学生,头指针和学号作参数,struct student *del(struct student *head,int num) /删除指定学号的学生结点，返回删除该结点后的链表的头指针 struct student *p1,*p2; if(head=NULL) printf(原表为空！n); return(NULL); else p1=head; while(p1-num!=num ,注意对比,教材程序需单独处理空表.函数返回类型能否空?,3、链表的基本操作-插入(指定学号的学生结点）,思路:定位第一个大于待插入学生的结点,修改其前驱结点指针 定位:设指针

32、prePtr和curPtr,只要curPtr还指向一个结点且所指结点学号不比num大则两指针都后移。循环结束后通常插入到prePtr后即可,但prePtr为NULL除外，说明插入到表头 注意：分析有等值结点时的插入情况！ 教材:curP逐个遍历并比较到尾结点停,循环结束后看curPtr所指结点的学号是否比待插入结点的学号大，是则插入其前(此处还要看是否插入到表头)，否则插入到表尾之后。,struct student *ListInsert(struct student *head,struct student *q) /插入指定学号的学生使仍然有序，返回插入该结点后链表的头指针 struct

33、student *prePtr=NULL,*curPtr=head; while(curPtr!=NULL /按此算法即使原表为空也不必特殊处理，上例也如此！教材算法不可,3、链表基本操作在特定位置插入结点,只要curP非所寻且未到尾结点则继续,循环结束后看有没有找到: 若中间找到则curP-nump0-num;若中间没找到则此式不成立,例10链表结点按学号小到大排列，插入新结点使仍有序,struct student *insert(struct student *head, struct student *stud) struct student *p0,*p1,*p2; p0=stud;

34、p1=head; if(head=NULL) /*原链表为空则将新结点作为头结点处理*/ head=p0;p0-next=NULL; else while(p0-nump1-num) ,试简化该算法，如尾结点统一化处理，只用一个指针变量，引入头结点，在指定位置插入,回顾基本操作的综合测试,void main() struct student *head,*q; int n,k; printf(请输入学生个数:n); scanf(%d, ,实验报告：,实验11 指针的应用 实验目的：掌握用指针进行字符串操作的方法 实验内容： 9.4 三个Trim函数 要求：写出代码，给出调试说明和总结,实验报告

35、：,实验12 结构体 实验目的： 1. 掌握结构体类型与结构体变量的定义、引用和初始化方法 2. 掌握结构体数组的相关操作 实验内容： 作业本上3 4题写入实验报告 要求写出代码并给出调试说明和总结,实验报告：,实验13 链表 实验目的： 1. 理解链表的概念和定义 2、掌握链表的基本操作 实验内容： 5 6 8 要求写出代码并给出调试说明和总结 为验证正确性需事先将教材中创建链表、输出链表的函数调试好,实验14 文件的使用 实验15 综合性实验,10.3 共用体,例10.12 某门课程，部分学生选修，部分学生必修。对选修学生按等级制打分，分ABCDE五级，对必修课学生按百分制打分。定义图示的

36、结构体数组，之后输入输出,struct Stdent int num; char name20; char optional; float scoreMark; char scoreGrade; ; /若optional为T /缺点：空间浪费,方案一:对于score设置scoreMark和scoreGrade两个成员 方案二:两者占用同一段内存, 通过score.mark或score.grade访问,union Score float mark; char grade; ; struct Stdent int num; char name20; char optional; union Sco

37、re score; ;,struct student stuN; for(i=0;iN;i+) scanf(%c, ,例10.2 代码,#include #define N 3 void main() struct student stuN; int i; printf(请输入%d个学生的信息:n,N); printf( 学号 姓名 是否选修 成绩n); for(i=0;iN;i+) scanf(%d%s %c, ,union Score float mark; char grade; ; struct Stdent int num; char name20; char optional; u

38、nion Score score; ;,共用体基本概念：,共用体：使多个类型相同或不同的成员变量占用同一段内存的结构。它与结构体类似，都属于构造数据类型，都由若干类型可以互不相同的成员组成。不同的是，结构体变量的各个成员拥有自己独立的存储单元，而共用体变量的各个成员“共用”一段内存，该内存段允许各成员在不同的地方分别起作用。更有效利用内存 共用体变量所占存储空间不是全部成员变量空间之和，而是各成员空间中的最大值。 共用体各成员变量的存储空间相互覆盖，一个成员值的改变会影响其他成员（但实际不会出问题，因同一结构体变量中只有一个有意义。 union Score score; /内存内容随机 sco

39、re.mark=0; printf(“%c”,score.grade);,共用体语法：,共用体类型定义,union UNode char c; short i; float f; node1,node2;,union UNode char c; short i; float f; ; union UNode node1;,struct Student int num; char name20; char optional; union float mark; char grade; score; ;,共用体变量的使用,union UNode data1,data2; data1.c=A; sc

40、anf(%f,共用体变量不能整体初始化,如union UNode data=A,5,2.3;,union char c2; short i; data; data.i=0 x4241; printf(“%c%cn”,data.c0,data.c1);/常为AB,10.4 枚举类型,引：表示性别的变量sex最好能且只能用Male和Famale赋值，赋予其它值时都应报错；表示工作日的变量workday最好能且只能用Mon,Tue,Web,Thur,Fri中之一进行赋值。如此能使程序清晰且不易出错 上述变量应属于一种特殊的类型，其取值被限定为几个特定的量。这种类型是一种自定义类型，称为枚举类型 en

41、um SexMale,Female; enum Sex mySex=Male; enum Workdaymon,tue,wed,thr,fri; enum Workday curDay,preDay; curDay=Mon; 说明：类似Male/Female等常称为枚举常量，他们本质上是一些取值为整数的标识符,默认值从0开始依次递增。也可显式指定其值,如enmu SexMale=1,Female=-1; enum Sex mysex=Male; printf(“%d”,mysex) enum WorkdayMon=1,Tue,Wed,Thur,FricurDay=Mon;,枚举相关语法：,1.

42、枚举变量的赋值 用枚举常量赋值，如enum Workday d=mon。 把一个整数进行强制类型转换后再赋给枚举变量，如enum Workday curDay=(enum Workday)1; 枚举常量是一个标识符，可在定义枚举类型时为其赋值，但不能在程序中为其赋值。 枚举常量既非字符常量，也非字符串常量，使用时不可加单引号或双引号,也不可用%s输出一个枚举量常/变量 2.枚举变量的输出：常用switch语句块或if-else if-else块 补充：枚举变量的输入 int n;scanf(“%d”,enum WorkdayMon,Tue,Wed,Thur,Fri; enum Workday

43、d=mon; switch(d) case mon:printf(%-6s,mon);break; case tue:printf(%-6s,tue);break; case wed:printf(%-6s,wed);break; case thr:printf(%-6s,thr);break; case fri:printf(%-6s,fri);break; default:printf(%-6s,error!);break; ,例10.13 假期中周一到周五三人轮流值班,一次一天，输入n求当天是周几，且当天谁值班,思路：编程模拟值班的过程1-n，到第n天直接输出即可,void main()

44、 enum WeekdayMon=1,Tue,Wed,Thur,Fri,Sat,Sun; enum WorkerZhangSan,LiSi,WangWu; enum Weekday curDay=Tue; enum Worker onDuty=ZhangSan; int i,n; scanf(%d, ,习题说明：,10：i=1;printf(“%d%d”,i,+i);得2,2 11 12,10.5 结构体和链表应用举例,例14 链表每个结点存储学生的相关信息，包括学号、姓名及若干门课程的考试成绩形成的数组，定义该结构体类型并编程创建链表，之后输出平均分85分以上的同学的各项信息,struct

45、Student long num; char name20; float scoreN; struct student *next; ;,head=create(M); for(p=head;p!=NULL;p=p-next) sum=0; for(i=0;iscorei; aver=sum/N; if(aver-85-1e-6) /注意浮点数相等的比较办法 printf(学号:%ld 姓名:%s ,p-num, p-name); for(i=0;iscorei); printf(n); ,例10.15 N个学生围成一圈，数到M就出圈，最后剩谁?,思路：用循环链表(尾结点的指针指向首元结点)模

46、拟该圈，之后通过循环模拟出圈的整个过程 改进：避免重复报数,orderM%len-1; 此外对比第六章,head=create(N); for(len=N;len1;len-) p=head; for(order=1;ordernext; p-next=p-next-next;/未释放！ head=p-next; /从下一同学重新报数 ,10.16 学生链表,按姓名排序(冒泡法,注意比较教材),head=create(N); for(i=0;iname,p-next-name)0) if(p=head) head=p-next; p-next=p-next-next; head-next=p;

47、 prep=head; /p已指向第二结点,教材先p=head;后p=p-next else prep-next=p-next; p-next=p-next-next; prep-next-next=p; prep = prep-next; /p已指向下一次两两比较时首结点,书同前 else /教材此处else去掉，因前两种情况也执行下面两句 prep=p; p=p-next; /选择排序难度较大！可考虑结构体数组的排序,注意结构体元素互换,10.3结构体数组排序,#include #include #define N 3 void main() structint num;char name

48、13;float score;stuN,temp; int i,j,min; printf(请输入各个学生的信息：n); for(i=0;i0) min=j; if(min!=i) temp=stumin; stumin=stui;stui=temp; printf(排序后为:n); for(i=0;iN;i+) printf(%d %s %6.1fn,stui.num,,stui.score); ,10.1 输入日期求天数,注意闰年,#include void main() struct int year; int month; int day; date; int i,d

49、ays; int day_tab12=31,28,31,30,31,30,31,31,30,31,30,31; printf(input year,month,day:n); scanf(%d%d%d, ,10.2用指针变量输入学生信息用scanf(“%s”,p-name),#include #define N 3 void main() struct student int num; char name20; float scoreN; ; struct student stu,*p= ,10.3结构体数组排序,#include #include #define N 3 void main(

50、) structint num;char name13;float score;stuN,temp; int i,j,min; printf(请输入各个学生的信息：n); for(i=0;i0) min=j; if(min!=i) temp=stumin; stumin=stui;stui=temp; printf(排序后为:n); for(i=0;iN;i+) printf(%d %s %6.1fn,stui.num,,stui.score); ,10.4删除结构体数组中最低分学生,#include #define N 3 void main() struct int nu

51、m;char name13;float score;stuN; int i,min; printf(请输入各个学生的信息：n); for(i=0;iN;i+) scanf(%d%s%f, ,练习-10.5 编写函数，统计链表中结点的个数。,int NodeCount(struct student *L) int count=1; struct student *p=L; while(p!=NULL) p=p-next; count+; return count-1; /注意边界，特殊值检测 ,思路:p从首结点开始，只要还指向一个结点就让计数器加1,10.6查找指定学号结点的位序，未找到则返回0。,int locate(struct student *head,int num) struct student *p=head; int order=1;