《清华大学C语言教学课件(共16个PPT)第11个教学提纲.ppt》由会员分享,可在线阅读,更多相关《清华大学C语言教学课件(共16个PPT)第11个教学提纲.ppt(45页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、清华大学C语言教学课件(共16个PPT)第11个依上图有依上图有7个结点个结点(x1,y1)(x1,y1)(x2,y2)(x2,y2)(x6,y6)(x6,y6)(x7,y7)(x7,y7)为了表示这种既有数据又有指针的情况,引入结构为了表示这种既有数据又有指针的情况,引入结构这种数据类型。这种数据类型。2结构结构是一种构造类型的数据类型。结构是数是一种构造类型的数据类型。结构是数目固定、类型不同的若干变量的有序集合。结目固定、类型不同的若干变量的有序集合。结构与数组的区别在于结构内允许有不同类型的构与数组的区别在于结构内允许有不同类型的数据。数据。结构的定义结构的定义,格式如下:,格式如下:
2、struct 3例如跳马棋局可如下定义例如跳马棋局可如下定义struct TMint x,y;/结构结构TM的成员,的成员,x,y为整数型为整数型struct TM*next/结构结构TM的成员,属的成员,属TM型型下面的表是马的跳步方案,从左下角跳到右上角下面的表是马的跳步方案,从左下角跳到右上角结点结点结点结点n1n1n2n2n3n3n4n4n5n5n6n6n7n7x xy y0 00 01 12 22 24 44 43 36 64 47 72 28 84 448 84 4NULLNULLNULLNULL为空地址为空地址下面是形成链表的一个参考程序下面是形成链表的一个参考程序(分三页)(分
3、三页)2 24 4&n4&n41 12 2&n3&n30 00 0&n2&n2&n1head5/结构结构1.c#include/预编译命令预编译命令#define null 0/定义空指针常量定义空指针常量struct TM/定义结构定义结构TMint x,y;/整型变量整型变量x,ystruct TM*next;/指向指向TM结构的指针结构的指针;void main()/主函数主函数/主函数开始主函数开始 int i;/声明整型变量声明整型变量 /声明声明TM结构结构n1n7,结构指针结构指针head,p struct TM n1,n2,n3,n4,n5,n6,n7,*head,*p;6/分
4、别对分别对TM结构结构n1n7中的中的x,y赋值赋值 n1.x=0;n1.y=0;n2.x=1;n2.y=2;n3.x=2;n3.y=4;n4.x=4;n4.y=4;n5.x=6;n5.y=4;n6.x=7;n6.y=2;n7.x=8;n7.y=4;/head赋值为赋值为n1,即,即head指向指向n1 head=&n1;/n1n7构成链表构成链表 n1.next=&n2;n2.next=&n3;n3.next=&n4;n4.next=&n5;n5.next=&n6;n6.next=&n7;/n7的的next指针赋值为空指针指针赋值为空指针 n7.next=null;7p=head;/p赋值为
5、赋值为head,即,即p指向指向head所指的内容所指的内容i=1;/i赋值为赋值为1do/直到型循环直到型循环/循环体开始循环体开始/输出结点信息输出结点信息printf(结点结点%d:x=%d,y=%dn,i,p-x,p-y);p=p-next;/p指向下一个结点指向下一个结点 i=i+1;/计数加计数加1 while(p!=null);/未到达链表尾部,则继续循环未到达链表尾部,则继续循环/主函数结束主函数结束8用结构数组,利用键盘输入结点中的数据。用结构数组,利用键盘输入结点中的数据。重点看重点看scanf(“%d”,&a);ni.x=a;结构数组,数组中的元素为结构类型的数据,如结构
6、数组,数组中的元素为结构类型的数据,如n8/结构结构2.c#include/预编译命令预编译命令#define null 0/定义空指针常量定义空指针常量struct TM/定义定义TM结构结构int x,y;/整型变量整型变量x,ystruct TM*next;/指向指向TM结构的指针结构的指针;9void main()/主函数主函数/主函数开始主函数开始 int i,a,b;/声明整型变量声明整型变量i,a,b /声明声明TM型结构数组型结构数组n8,TM结构指针结构指针head,p struct TM n8,*head,*p;for(i=1;i=7;i=i+1)/循环循环/循环体开始循环
7、体开始 printf(输入输入n%d的的xn,i);/提示输入第提示输入第i个结构的个结构的x值值 scanf(%d,&a);/输入输入a ni.x=a;/将将a的值赋给结构的值赋给结构ni的元素的元素x printf(输入输入n%d的的yn,i);/提示输入第提示输入第i个结构的个结构的y值值 scanf(%d,&b);/输入输入b ni.y=b;/将将b的值赋给结构的值赋给结构ni的元素的元素y/循环体结束循环体结束10head=&n1;/链表头部指向链表头部指向n1for(i=1;ix,p-y);p=p-next;/p指向相邻的下一个结点指向相邻的下一个结点 i=i+1;/计数计数i加加
8、1 while(p!=null);/未到链表尾部,则继续循环未到链表尾部,则继续循环/主函数结束主函数结束11下面的程序与上面的程序区别仅在下面的程序与上面的程序区别仅在scanf(“%d”,&(ni.x);去替换去替换scanf(“%d”,&a);ni.x=a;/结构结构3.c#include/预编译命令预编译命令#define null 0/定义空指针常量定义空指针常量struct TM/定义定义TM结构结构int x,y;/整型变量整型变量x,ystruct TM*next;/指向指向TM结构的指针结构的指针;12void main()/主函数主函数/主函数开始主函数开始 int i,a
9、,b;/声明整型变量声明整型变量i,a,b /声明声明TM型结构数组型结构数组n8,TM结构指针结构指针head,p struct TM n8,*head,*p;for(i=1;i=7;i=i+1)/循环循环/循环体开始循环体开始 printf(输入输入n%d的的xn,i);/提示输入第提示输入第i个结构的个结构的x值值 scanf(%d,&(ni.x);/输入输入ni.x printf(输入输入n%d的的yn,i);/提示输入第提示输入第i个结构的个结构的y值值 scanf(%d,&(ni.y);/输入输入ni.y/循环体结束循环体结束13head=&n1;/链表头部指向链表头部指向n1fo
10、r(i=1;i=6;i=i+1)/循环循环/循环体开始循环体开始 ni.next=&ni+1;/ni.next指向指向ni+1/循环体结束循环体结束n7.next=null;/链表尾部赋值为空指针链表尾部赋值为空指针p=head;/p指向链表头部指向链表头部headi=1;/i赋值为赋值为1do/直到型循环直到型循环/循环体开始循环体开始/提示输入结点信息提示输入结点信息 printf(结点结点%d:x=%d,y=%dn,i,(*p).x,(*p).y);p=(*p).next;/p指向相邻的下一个结点指向相邻的下一个结点 i=i+1;/i加加1 while(p!=null);/未到达链表尾部
11、,则继续循环未到达链表尾部,则继续循环/主函数结束主函数结束14任务:任务:我们要作一张登记表,登记排队求职信息,包括:姓名、年我们要作一张登记表,登记排队求职信息,包括:姓名、年龄、性别、电话四个参数。希望便于管理,即可以插入和删龄、性别、电话四个参数。希望便于管理,即可以插入和删除,这时可用队列,采用结构类型变量。除,这时可用队列,采用结构类型变量。struct STchar name20;/字符串,姓名字符串,姓名int age;/整数,年龄整数,年龄char sex;/字符,性别字符,性别long num;/电话号码电话号码struct ST*next;/ST结构的指针结构的指针;/注
12、意,这里必须有分号注意,这里必须有分号声明结构指针变量用下列形式声明结构指针变量用下列形式struct ST*head,*p,*q;上面的上面的 head,p,q 为结构指针。为结构指针。15结构的成员可以是指针,意味着这种结构指针可以指结构的成员可以是指针,意味着这种结构指针可以指向结构变量。向结构变量。结构变量和指向结构变量的指针可以作为函数的参数结构变量和指向结构变量的指针可以作为函数的参数与返回值。用结构变量作函数返回值的函数称之为与返回值。用结构变量作函数返回值的函数称之为结构函数。结构函数。struct ST*create(void)就是结构函数,就是结构函数,为了了解结构变量成员
13、的地址情况,我们给出了程为了了解结构变量成员的地址情况,我们给出了程序序“结构结构5.c”,在这个程序中我们重点看,在这个程序中我们重点看1、#include 这是预编译命令,为了分配结构变量的内存地址用这是预编译命令,为了分配结构变量的内存地址用的。的。2、#define null 0这是定义空指针变量常量,这是定义空指针变量常量,null 代表代表 0。3、#define LEN sizeof(struct ST)定义常量定义常量LEN,表示结构,表示结构ST中的变量的全部单元的中的变量的全部单元的长度,分配内存空间时需要知道这个长度信息。长度,分配内存空间时需要知道这个长度信息。164、
14、结构、结构ST的定义的定义5、函数、函数create的定义的定义6、给结构指针、给结构指针p分配内存空间。分配内存空间。p=(struct ST*)malloc(LEN);7、查看指针、查看指针p所在的地址所在的地址printf(“指针指针p所在的地址所在的地址&p=%Xn”,&p);8、查看指针、查看指针p所指向的地址所指向的地址printf(“指针指针p所指向的地址所指向的地址p=%Xnn”,p);9、输入姓名,查看姓名所在的地址、输入姓名,查看姓名所在的地址scanf(“%s”,&(*p).name);10、输入年龄,查看年龄数据所在的地址、输入年龄,查看年龄数据所在的地址scanf(“
15、%d”,&(*p).age);printf(“年龄数据所在地址年龄数据所在地址%Xnn”,&(*p).age);17/结构结构5.c(分四页)(分四页)#include/预编译命令预编译命令#include/预编译命令,内存空间分配预编译命令,内存空间分配#define null 0/定义空指针常量定义空指针常量#define LEN sizeof(struct ST)/定义常量定义常量LEN,/表示结构表示结构ST的长度的长度struct ST/结构结构ST定义定义char name20;/字符串,表示名字字符串,表示名字int age;/整数类型,表示年龄整数类型,表示年龄char sex
16、;/字符类型,表示性别字符类型,表示性别long num;/长整型,表示电话号码长整型,表示电话号码struct ST*next;/ST结构指针结构指针;struct ST*head,*p,*q;/声明,结构指针变量声明,结构指针变量head,p,q18void create(void)/定义一个名为定义一个名为create的函数,无形参和返回值的函数,无形参和返回值/函数体开始函数体开始int n=0;/整型变量整型变量n,赋初值为,赋初值为0head=null;/ST结构指针结构指针head,赋初值为,赋初值为nullp=(struct ST*)malloc(LEN);/给结构指针给结构指
17、针p分配内存空间分配内存空间/输出指针输出指针p所在地址所在地址printf(指针指针p所在地址所在地址&p=%Xn,&p);/输出指针输出指针p所指向的地址所指向的地址 printf(指针指针p所指向的地址所指向的地址 p=%Xnn,p);q=p;/q赋值为赋值为p,即,即q指向指向p所指的内容所指的内容/输出指针输出指针p所在地址所在地址printf(指针指针q所在地址所在地址&q=%Xn,&q);/输出指针输出指针p所指向的地址所指向的地址 printf(指针指针q所指向的地址所指向的地址 q=%Xnn,q);19/提示输入第提示输入第n+1个结点的数据个结点的数据printf(输入第输
18、入第%d个结点的数据个结点的数据n,n+1);printf(依次为依次为name,age,sex,numn);/提示输入姓名数据,并输出其所在地址提示输入姓名数据,并输出其所在地址printf(输入姓名数据输入姓名数据%dn,n+1);scanf(%s,&(*p).name);printf(姓名数据所在地址姓名数据所在地址%Xnn,&(*p).name);/提示输入年龄数据,并输出其所在地址提示输入年龄数据,并输出其所在地址printf(输入年龄数据输入年龄数据%dn,n+1);scanf(%d,&(*p).age);printf(年龄数据所在地址年龄数据所在地址%Xnn,&(*p).age)
19、;/提示输入性别数据,并输出其所在地址提示输入性别数据,并输出其所在地址printf(输入性别数据输入性别数据%dn,n+1);scanf(%s,&(*p).sex);printf(性别数据所在地址性别数据所在地址%Xnn,&(*p).sex);20printf(输入电话号码数据输入电话号码数据%dn,n+1);/输出提示信息输出提示信息/从键盘输入电话号码从键盘输入电话号码scanf(%ld,&(*p).num);/输出电话号码所在地址输出电话号码所在地址printf(电话号码所在地址电话号码所在地址%Xnn,&(*p).num);printf(输出姓名输出姓名%sn,p-name);/输出
20、姓名输出姓名printf(输出年龄输出年龄%dn,p-age);/输出年龄输出年龄printf(输出性别输出性别%cn,p-sex);/输出性别输出性别printf(输出电话号码输出电话号码%ldn,p-num);/输出电话号码输出电话号码void main()/主函数主函数/主函数开始主函数开始create();/调用函数调用函数create(),建立链表,建立链表/主函数结束主函数结束21struct ST*create(void)2223/结构结构6.c(分四页)(分四页)#include/预编译命令预编译命令#include/内存空间分配内存空间分配#define null 0/定义空
21、指针常量定义空指针常量#define LEN sizeof(struct ST)/定义常量,表示结构长度定义常量,表示结构长度struct ST/结构声明结构声明char name20;/名字,字符串名字,字符串int age;/年龄,整型数组年龄,整型数组char sex;/性别,字符型变量性别,字符型变量long num;/电话号码,长整型变量电话号码,长整型变量struct ST*next;/ST结构指针结构指针;struct ST*head;/声明全局变量声明全局变量head为为ST结构指针结构指针void create(void)/被调用函数,用于建立链表被调用函数,用于建立链表/函
22、数体开始函数体开始struct ST*p,*q;/声明声明ST结构指针结构指针p,qint n=0;/整型变量,用于记录输入的人数整型变量,用于记录输入的人数char tmpStr20;/字符串,作为临时变量字符串,作为临时变量head=null;/链表头部指针,初始化为空链表头部指针,初始化为空p=null;/链表当前结构指针,初始化为空链表当前结构指针,初始化为空q=null;/链表尾部指针,初始化为空链表尾部指针,初始化为空24do/直到型循环,用于循环输入人员信息直到型循环,用于循环输入人员信息 n=n+1;/人数加人数加1printf(输入第输入第%d个结点的数据个结点的数据n,n)
23、;/提示信息提示信息 printf(输入姓名数据输入姓名数据%dn,n);/提示输入姓名提示输入姓名scanf(%s,tmpStr);/输入姓名信息,并存入临时变量输入姓名信息,并存入临时变量/判断输入是否结束,如果为判断输入是否结束,如果为.,则结束,则结束if(strcmp(tmpStr,.)=0)break;p=(struct ST*)malloc(LEN);/为为p分配空间分配空间if(p=null)/判断分配是否成功判断分配是否成功/如果分配出错,则输出出错信息如果分配出错,则输出出错信息printf(Insufficient memory availablen);break;/退出
24、循环退出循环25strcpy(*p).name,tmpStr);/将名字存入将名字存入p结构中的结构中的name单元单元printf(输入年龄数据输入年龄数据%dn,n);/提示输入年龄提示输入年龄scanf(%d,&(*p).age);/输入年龄输入年龄printf(输入性别数据输入性别数据%dn,n);/提示输入年龄提示输入年龄scanf(%s,&(*p).sex);/输入性别输入性别printf(输入电话号码数据输入电话号码数据%dn,n);/提示输入电话号码提示输入电话号码scanf(%ld,&(*p).num);/输入电话号码输入电话号码if(n=1)head=p;/如果是第一个结构
25、,则将如果是第一个结构,则将head指向此结构指向此结构else(*q).next=p;/如果不是第一个结构,如果不是第一个结构,/则将此结构加到链表尾部则将此结构加到链表尾部q=p;/q指针指向此结构,表示新的链表尾部指针指向此结构,表示新的链表尾部 while(1);/循环体结束,循环体结束,1表示死循环表示死循环 if(q!=null)/链表尾部是否为空链表尾部是否为空q-next=null;/如果不为空,则链表尾部的如果不为空,则链表尾部的next指向空指针指向空指针26void print()/被调用函数,形参为被调用函数,形参为ST结构指针结构指针int k=0;/整型变量,用于计
26、数整型变量,用于计数struct ST*r;/声明声明r为为ST结构指针结构指针r=head;/r赋值为赋值为head,即指向,即指向head所指向的内容所指向的内容 while(r!=null)/当型循环,链表指针不为空当型循环,链表指针不为空/循环体开始循环体开始k=k+1;/计数加计数加1printf(输出排队求职者信息输出排队求职者信息%d:%s,%d,%c,%ldn ,k,r-name,r-age,r-sex,r-num);/输出人员信息输出人员信息r=r-next;/循环体结束循环体结束/被调用函数结束被调用函数结束void main()/主函数开始主函数开始/函数体开始函数体开始
27、create();/调用调用create函数建立链表函数建立链表print();/调用调用print函数,输出链表内容函数,输出链表内容/主函数结束主函数结束27字符串处理函数简介字符串处理函数简介1、strcmp(s1,s2)例例printf(“#%dn”,strcmp(“b”,”b”);输出输出#0printf(“#%dn”,strcmp(“b”,”f”);输出输出#-1结论:结论:当当s1s2时时 strcmp(s1,s2)的值为的值为1当当s1s2时时 strcmp(s1,s2)的值为的值为0当当s1next=null;2、第二种情况,链表已建成,待插入结点、第二种情况,链表已建成,待
28、插入结点p的数据要的数据要比头结点的数据还要小,这时有比头结点的数据还要小,这时有p-num num当然当然p结点要插在结点要插在head结点前。结点前。326 6head8 85 51212nullnullheadpp-next=head;head=p;语句为语句为null333、第三种情况,链表已建成,待插入结点、第三种情况,链表已建成,待插入结点p的数的数据比头结点的数据大,需要找到正确的插入位置。据比头结点的数据大,需要找到正确的插入位置。这时,可以借助两个结构指针这时,可以借助两个结构指针r和和q,利用循环比,利用循环比较来找到正确位置。然后将结点较来找到正确位置。然后将结点p插入到
29、链表中正插入到链表中正确的位置。确的位置。参见下面的图示参见下面的图示346 6head8 812121313nullnullp1515qr说明:说明:这种情况下,这种情况下,p结点已经与链表的第一个结点比结点已经与链表的第一个结点比较过了,所以从链表的下一个结点开始比较。较过了,所以从链表的下一个结点开始比较。138,继续比较。,继续比较。356 6head8 812121313nullnullp1515qr说明:说明:1312,继续比较。,继续比较。366 6head8 812121313p1515qrnull说明:说明:13next=p;p-next=q;37/结构结构7.c#inclu
30、de/预编译命令预编译命令#include/内存空间分配内存空间分配#define null 0/定义空指针常量定义空指针常量#define LEN sizeof(struct numST)/定义常量,表示结构长度定义常量,表示结构长度struct numST/结构声明结构声明int num;/整型数整型数struct numST*next;/numST结构指针结构指针;参考程序参考程序38/被调用函数被调用函数insert(),两个形参分别表示链表和待插入的结点,两个形参分别表示链表和待插入的结点void insert(struct numST*phead,struct numST*p)/函
31、数体开始函数体开始struct numST*q,*r;/定义结构指针定义结构指针q,rif(*phead)=null)/第一种情况第一种情况,链表为空,链表为空*phead=p;/链表头指向链表头指向preturn;/完成插入操作,返回完成插入操作,返回else/链表不为空链表不为空/第二种第二种情况情况,p结点结点num值小于链表头结点的值小于链表头结点的num值值if(*phead)-num p-num)/将将p结点插到链表头部结点插到链表头部 p-next=*phead;/将将p的的next指针指向链表头指针指向链表头(*phead)*phead=p;/将链表头赋值为将链表头赋值为p r
32、eturn;/返回返回39/第三种第三种情况情况,循环查找正确位置,循环查找正确位置r=*phead;/r赋值为链表头赋值为链表头q=(*phead)-next;/q赋值为链表的下一个结点赋值为链表的下一个结点while(q!=null)/利用循环查找正确位置利用循环查找正确位置/判断当前结点判断当前结点num是否小于是否小于p结点的结点的numif(q-num num)r=q;/r赋值为赋值为q,即指向,即指向q所指的结点所指的结点q=q-next;/q指向链表中相邻的下一个结点指向链表中相邻的下一个结点else/找到了正确的位置找到了正确的位置break;/退出循环退出循环/将将p结点插入
33、正确的位置结点插入正确的位置r-next=p;p-next=q;40/被调用函数,形参为被调用函数,形参为ST结构指针结构指针,用于输出链表内容用于输出链表内容void print(struct numST*head)int k=0;/整型变量,用于计数整型变量,用于计数struct numST*r;/声明声明r为为ST结构指针结构指针r=head;/r赋值为赋值为head,即指向,即指向链表头链表头 while(r!=null)/当型循环,链表指针不为空当型循环,链表指针不为空则则继续继续/循环体开始循环体开始k=k+1;/计数加计数加1printf(%d%dn,k,r-num);r=r-n
34、ext;/取链表中相邻的下一个结点取链表中相邻的下一个结点/循环体结束循环体结束41void main()/主函数开始主函数开始/函数体开始函数体开始struct numST*head,*p;/ST型结构指针型结构指针head=null;/分配两个分配两个ST结构的内存空间,用于构造链表结构的内存空间,用于构造链表head=(struct numST*)malloc(LEN);head-next=(struct numST*)malloc(LEN);/为链表中的两个结点中的为链表中的两个结点中的num赋值为赋值为5和和10head-num=5;head-next-num=10;head-nex
35、t-next=null;/链表尾赋值为空链表尾赋值为空/构造一个结点构造一个结点p,用于插入链表,用于插入链表p=(struct numST*)malloc(LEN);p-num=8;p-next=null;insert(&head,p);/调用调用create函数建立链表,函数建立链表,print(head);/调用调用print函数,输出链表内容函数,输出链表内容/主函数结束主函数结束42说明:说明:函数函数insert()的第一个形参为的第一个形参为struct numST*类型,即类型,即“指针的指针指针的指针”。调用时送入的实参是。调用时送入的实参是链表头指针的地址,即程序中的链表头指针的地址,即程序中的&head。这样对。这样对head的修改才会在函数返回后仍有效。如果形参的修改才会在函数返回后仍有效。如果形参为为struct numST*,则传入的为指针,当函数返回,则传入的为指针,当函数返回后,后,head无法改变。无法改变。43结结 束束44此课件下载可自行编辑修改,仅供参考!此课件下载可自行编辑修改,仅供参考!感谢您的支持,我们努力做得更好!谢谢感谢您的支持,我们努力做得更好!谢谢