语言程序设计-课件

语言程序设计C语言程序设计第9章结构体类型用户自定义数据类型用指针处理链表59.5.1 什么是线性链表数组：静态分配存储单元，容易造成内存浪费。链表：根据需要，动态分配内存单元。head1249135614751021A 1356B 1475C 1021D Null 1249datanextheaddatanextdatanextdataNULL用指针处理链表59.5.1 什么是线性链表链表各结点的特点：在内存中可以不连续，访问某结点应找上一结点提供的地址，每一结点有一指针变量存放下一结点的地址。链表的每个结点实际上是一个结构体变量，它有若干成员组成，包括的内容有两部分：u数据部分：整、实、字符、结构体等类型。u指针变量：通常具有指向自身结构体类型的指针变量，此指针变量用来存放下一结点的地址，以便一环扣一环而形成链表。struct student int num;int score;struct Link*next;用指针处理链表5例例9.8 建立静态链表建立静态链表 处理学生信息处理学生信息 1.问题提出：问题提出：2.解题思路：解题思路：构成链表？构成链表？head？p？3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:#include#define NULL 0 struct student long num;float score;struct student*next;int main()struct student a,b,c,*head,*p;a.num=10101;a.score=89.5;b.num=10103;b.score=90;c.num=10107;c.score=85;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do printf(“%ld%5.1fn”,pnum,pscore);p=pnext;while(p!=NULL);用指针处理链表59.5.3 建立动态链表malloc函数：void *malloc(unsigned int size);calloc函数：void *calloc(unsigned n,unsigned size);作用：在动态区分配一个长度为size的连续空间，函数返回值是一个指向分配域起始地址的指针，如内存空间不足，返回空指针NULL。(此处：void为无确定类型)作用：在内存动态区分配n个长度为size的连续空间，函数返回指向分配域起始地址的指针，若分 配不成功，返回NULL值。free函数：void free(void *p);作用：释放由p指向的内存区，使这部分内存区能被其它变量使用。P所指向的是最近一次calloc或malloc分配的存储区域。free函数无返回值。#include “malloc.h”用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p，head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:#include “stdio.h”#include “malloc.h”#define NULL 0#define LEN sizeof(struct student)struct student long num;float score;struct student *next;int n;Int main()struct student *head;struct student *p;head=p=(struct student *)malloc(LEN);scanf(“%ld,%f”,&p num,&p score);head-next=NULL;p=head;printf(“n 结点结点1：%d,%6.2fn”,p-num,p-score);p=p-next;printf(“n 结点结点2：%d,%6.2fn”,p-num,p-score);return 0;用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p，head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:n=n+1n=1 head=p1 p2next=p1 真真 假假(把把p1所指结点作所指结点作为第一个结点为第一个结点)(把把p1所指结点所指结点连接到表尾连接到表尾)p2=p1(p2移到表尾）移到表尾）再开辟一个新结点，使再开辟一个新结点，使p1指向它指向它读入一个学生数据给读入一个学生数据给p1所指结点所指结点表尾结点的指针变量置表尾结点的指针变量置NULL开辟一个新结点，并使开辟一个新结点，并使p1,p2指向它指向它读入一个学生数据给读入一个学生数据给p1所指向的结点所指向的结点head=NULL,n=0当读入的当读入的p1 num 不是零不是零用指针处理链表5(n=1)9910189.5headp1p2(a)(n=2)headp2p19910189.59910390headp2p19910189.59910390(b)(n=2)p2=p1headp2p19910189.59910390(c)(n=2)用指针处理链表59910189.59910390headp2p19910785(a)n=39910189.59910390headp2p19910785(b)n=39910189.59910390p2p19910785(a)n=3head00009910189.59910390p2p19910785NULL(b)n=3head用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点#include “stdio.h”#include “malloc.h”#define NULL 0#define LEN sizeof(struct student)struct student long num;float score;struct student *next;int n;struct student*creat(void)struct student *head;struct student *p1,*p2;n=0;p1=p2=(struct student *)malloc(LEN);scanf(“%ld,%f”,&p1 num,&p1 score);head=NULL;while(p1 num!=0)n=n+1;if(n=1)head=p1;else p2 next=p1;p2=p1;p1=(struct student *)malloc(LEN);scanf(“%ld,%f”,&p1 num,&p1 score);p2 next=NULL;return(head);建立链表用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点void print(struct student *head)struct student*p;printf(“n Now,these%d records are:n”,n);p=head;if(head)!=NULL)do printf(“%ld,%5.2fn”,p num,p score);p=p next;while(p!=NULL);P=head,使使p指向第一个结点指向第一个结点 P指向的不是尾结点指向的不是尾结点 真真 假假输出输出p所指向的结点所指向的结点p=p next当当p指的不是表尾指的不是表尾NULLheadPP输出链表用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点99101headp19910399107NULL(a)初始状态初始状态p2(b)下移一个结点下移一个结点 headp199107NULL9910199103p2=p1head=p1 nextheadp1(c)选中第一个结点选中第一个结点9910199107NULL99103headp2p1p2 next=p1 next(d)第二个结点被删除第二个结点被删除99107NULL9910199103删除链表用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点删除链表 p1是要删除的结点是要删除的结点 是是 否否 链表是一个空表链表是一个空表真真 假假输出输出 空表空表p1=head 当当num p1 num 以及以及p1 所指的结点不是表尾结点所指的结点不是表尾结点p2=p1 (p2后移一个位置）后移一个位置）p1=p1 next (p1后移一个位置）后移一个位置）输出输出“找不找不 到到”的信息的信息 P1所指是头结点所指是头结点 是是 否否head=p1 next(删除头结点）删除头结点）p2next=p1next(删除一个结点）删除一个结点）用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点struct student *del(struct student*head,long num)struct student *p1,*p2;if(head=NULL)printf(“n list null!n”);goto end;p1=head;while(num!=p1 num&p1 next!=NULL)p2=p1;p1=p1 next;if(num=p1 num)if(p1=head)head=p1 next;else p2 next=p1 next;printf(“delete:%dn”,num);n=n-1;else printf(“%ld not been found!n”,num);return(head);删除链表用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点head991019910399107NULL99102p0p1(a)准备将准备将p0插入链表中插入链表中插入结点用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点插入结点head991019910399107NULL99102p0p1p2(b)插入点位于链表中间插入点位于链表中间 p0nump1nump2=p1,p1=p1next用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点插入结点9910399107NULLp1head9910199102p0p2(c)链接新结点链接新结点 p0num p1nump2next=p0,p0next=p1用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点插入结点99107NULLhead991009910399101p0p1(d)结点插在表首结点插在表首 p0num p1 num 以及以及p1所指的不是表尾结点所指的不是表尾结点 p2=p1 p1=p1 next p0 num p1 num 真真 假假 P0指向头结点指向头结点 是是 否否head=p0 p0 next=p1(插到表头之前插到表头之前)p2 next=p0 p0 next=p1(插到表中间插到表中间)p1 next=p0 p0 next=NULL(插到表尾之后插到表尾之后)将将p0所所 指的结指的结 点作为点作为 唯一结唯一结 点点 n=n+1用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点struct student *insert(struct student*head,struct student*stud)struct student *p0,*p1,*p2;p1=head;/*使使p1指向第一个结点指向第一个结点*/p0=stud;/*p0指向要插入的结点指向要插入的结点*/if(head=NULL)/*原来的链表是空表原来的链表是空表*/head=p0;p0next=NULL;/*使使p0指向的结点作为头结点指向的结点作为头结点*/else while(p0num p1num)&(p1next!=NULL)p2=p1;/*使使p2指向刚才指向刚才p1指向的结点指向的结点*/p1=p1 next;/*p1后移一个结点后移一个结点*/if(p0num=p1num)if(head=p1)head=p0;/*插到原来第一个结点之前插到原来第一个结点之前*/else p2next=p0;/*插到插到p2指向的结点之后指向的结点之后*/p0next=p1;else p1next=p0;p0next=NULL;/*插到最后的结点插到最后的结点之后之后*/n=n+1;/*结点数加结点数加1*/return(head);插入结点用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点void main()struct student *head,*stu;long del_num;printf(“input records:n”);head=creat();/*建立链表，返回头指针建立链表，返回头指针*/print(head);/*输出全部结点输出全部结点*/printf(“n input delete number:”);scanf(“%ld”,&del_num);/*输入要删除的学号输入要删除的学号*/while(del_num!=0)head=del(head,del_num);/*删除后链表的头地址删除后链表的头地址*/print(head);/*输出全部结点输出全部结点*/printf(“input the delete number:”);scanf(“%ld”,&del_num);/*输入要删除的学号输入要删除的学号*/printf(“n input the inserted record:”);stu=(struct student*)malloc(LEN);综合操作用指针处理链表5例例9.9 单向动态链表单向动态链表 1.问题提出：问题提出：2.解题思路：解题思路：malloc（）：（）：p1,p2 head 输入数据输入数据 NULL：链表结束：链表结束 3.编写程序编写程序:4.运行结果运行结果:5.程序分析程序分析:6.程序改进程序改进:3个以上结点个以上结点scanf(“%ld,%f”,&stunum,&stuscore);/*输入输入要插入的结点要插入的结点*/while(stunum!=0)head=insert(head,stu);/*插入新结点，返回地址插入新结点，返回地址*/print(head);/*输出全部结点输出全部结点*/printf(“input the inserted record:”);stu=(struct student*)malloc(LEN);scanf(“%ld,%f”,&stunum,&stuscore);综合操作提高部分共用体6structstruct sample sample shortshort i;i;charchar ch;ch;floatfloat f;f;0 x0037b00unionunion sample sample shortshort i;i;charchar ch;ch;floatfloat f;f;printf(%dn,sizeof(struct sample);printf(%dn,sizeof(struct sample);8个字节个字节i ichchf f4个字节个字节printf(%dn,sizeof(union sample);printf(%dn,sizeof(union sample);i ichchf f提高部分共用体6union 共用体名共用体名 类型标识符类型标识符 成员名；成员名；类型标识符类型标识符 成员名；成员名；.；例例 union data int i;char ch;float f;fchi提高部分共用体6sizeof(union number)取决于占空间最多占空间最多的那个成员变量0 x0037b00同一内存单元在每一瞬时只能存放其中一种类型的成员同一内存单元在每一瞬时只能存放其中一种类型的成员起作用的成员是起作用的成员是最后一次存放最后一次存放最后一次存放最后一次存放的成员，不能作为函数参数的成员，不能作为函数参数不能进行比较操作，只能对第一个成员初始化不能进行比较操作，只能对第一个成员初始化f f4个字节个字节提高部分共用体6提高部分共用体6提高部分枚举类型6枚举枚举（EnumerationEnumeration）数据类型数据类型 描述的是一组整型值的集合 用于当某些量仅由有限个数据值组成时 enum weeks SUN,MON,TUE,WED,THU,FRI,SAT;enum weeks today;enum response no,yes,none;enum response answer;today =TUE;answer=yes;enum response no=-1,yes=1,none=0;其值为其值为2 2其值为其值为1 1enum 枚举类型名枚举类型名 枚举元素列表枚举元素列表 枚举变量列表；枚举变量列表；提高部分枚举类型6例例11.13 口袋中有红、黄、蓝、白、黑口袋中有红、黄、蓝、白、黑5种颜色的球若干个。每次从口袋中先后取出种颜色的球若干个。每次从口袋中先后取出3个球，问得到个球，问得到3种不同色的球的可能取法，打印出每种排列的情况。种不同色的球的可能取法，打印出每种排列的情况。要判断各球是否同色，应用枚举类型变量处理。设取出的球为要判断各球是否同色，应用枚举类型变量处理。设取出的球为要判断各球是否同色，应用枚举类型变量处理。设取出的球为要判断各球是否同色，应用枚举类型变量处理。设取出的球为i,j,ki,j,k。根据题意，。根据题意，。根据题意，。根据题意，i i、j j、k k分别是分别是分别是分别是5 5种种种种色球之一，并要求色球之一，并要求色球之一，并要求色球之一，并要求ijkijk。可以用穷举法，即一种可能一种可能地试，看哪一组符合条件。可以用穷举法，即一种可能一种可能地试，看哪一组符合条件。可以用穷举法，即一种可能一种可能地试，看哪一组符合条件。可以用穷举法，即一种可能一种可能地试，看哪一组符合条件。n=0n=n+1输出一种取法输出一种取法 ij和和 k j 真真 假假 k从从red变到变到black ij 真真 假假 j从从red变到变到black输出取法的总数输出取法的总数n i从从red变到变到blackloop由1到3loop的值1 2 3i prii prii pripri的值 redyellowbluewhiteblack 打印 “red”打印“yellow”打印“blue”打印“white”打印“black”提高部分枚举类型6#include void main()enum colorred,yellow,blue,white,black;enum color i,j,k,pri;int n,loop;n=0;for(i=red;i=black;i+)for(j=red;j=black;j+)if(i!=j)for(k=red;k=black;k+)if(i!=j)&(k!=j)n=n+1;printf(“%-4d”,n);for(loop=1;loop成员名成员名4.结构体变量指针、函数参数结构体变量指针、函数参数5.链表：建立、输出、删除、插入链表：建立、输出、删除、插入6.共用体、枚举类型共用体、枚举类型