《[IT计算机]吴文虎《程序设计基础第2版》PPT12.ppt》由会员分享，可在线阅读，更多相关《[IT计算机]吴文虎《程序设计基础第2版》PPT12.ppt（63页珍藏版）》请在三一办公上搜索。
1、声明：本课件版权归清华大学计算机系语音技术中心 所有未经许可 不得扩散,结 构 数 组,结构也可以构成数组，即数组元素是结构，当然要求这一类数组的全部元素都应该是同一类结构。先看下例，例中有同宿舍的四名同学的数据，构成一个有四个元素的结构数组。,/*/*程 序 名：7_14.cpp*/*作 者：wuwh*/*编制时间：2002年11月21日*/*主要功能：结构数组*/*#include#include,struct student/定义结构studentchar name20;char sex;unsigned long birthday;float height;float weight;s
2、tudent Room4=/定义student结构数组，并初始化Lixin,M,19840318,1.82f,65.0f,Zhangmen,M,19840918,1.75f,58.0f,Helei,M,19841209,1.83f,67.1f,Geyujian,M,19840101,1.70f,59.0f;,void main()/主函数student q;/定义 q 为student结构/以下是按年龄大小对四位同学进行排序int i=0;int j=0;for(j=0;j Roomi+1.birthday)/ifq=Roomi;Roomi=Roomi+1;Roomi+1=q;/if/for
3、i/for jfor(i=0;i4;i+)/for icout Roomi.name n Roomi.sex n Roomi.birthday n Roomi.height n Roomi.weight n;/for i/主函数,说明上述程序可完成冒泡排序。在排序过程中数组中的元素是结构。按生日大小排序时，学生的5个数据作为一个整体（结构）来调整在数组中的位置。作业：希望你能按身高排序改写上述程序。,/*/*程 序 名：7_15.cpp*/*作 者：wuwh*/*编制时间：2002年11月21日*/*主要功能：结构指针数组*/*#include#include struct student/定
4、义结构studentchar name20;char sex;unsigned long birthday;float height;float weight;,下面我们用结构指针数组来完成排序任务,student Room4=/定义student结构数组，并初始化Lixin,M,19840318,1.82f,65.0f,Zhangmen,M,19840918,1.75f,58.0f,Helei,M,19841209,1.83f,67.1f,Geyujian,M,19840101,1.70f,59.0f;void main()/定义指向 student 结构的指针数组，指向Room数组元素st
5、udent*p4=/定义一个指向 student 结构的指针，/用作中间变量,/下面仍用冒泡排序将屋中4人依身高从大到小排序int i=0;int j=0;for(j=0;jheight height)q=pi;pi=pi+1;pi+1=q;for(i=0;iname sex birthday height weight endl;,说明：1、p 是指向 student 结构的指针数组，经初始化赋入的是 Room 数组中元素所在的地址，指向关系见图1,2、pi-height 是名为 pi 的指针通过箭头操作符来访问 my 结构成员 height。3、语句 if(pi-height height
6、)是说如果 Roomi 中的 height 成员比 Roomi+1 中的 height 成员小，就去做下面的语句组：变换指针的指向，让 pi 改去指向 Roomi+1，让 pi+1 指向 Roomi。这样做就比前一个程序好。当着结构成员很多时，直接让结构变量相互交换并不是好办法，而现在的做法只需将指针的指向交换一下，极为省力。,1.87 p0 p1 1.85 p2 p3 1.62 1.76,引用的概念及应用,古代有的人有名有字还有号。在 C+中，为了方便除了给变量起一个名之外，有时还要给它起一个“别名”。这里我们介绍“引用”的概念和用引用传递参数的方法。比如，我们先定义一个整型变量 i 并初始
7、化为3。再声明 j 是对整型数的引用，并初始化为引用 i。,两个语句为int i=3;/是定义int 是声明和初始化，而不是定义和初始化。比较 int i，和 int&j。前者是定义，需要分配内存单元给变量 i；后者是声明，不是定义，不需要分配内存单元给 j，仅仅声明了一个引用，或者说仅仅起了一个“别名”而已。,下面，我们用图示来细说定义和声明的关系。int i=3;定义之后，系统为 i 分配了内存地址单元,i为符号地址。int 声明 j 是 i 的“别名”。即 j 是 i 的引用，系统并不去为 j 分配内存单元。而是说 j 是 i 的“别名”。别名和正名所代表的符号地址是同一个地址。为了验证
8、上述说法，请作如下实验,i（别名 j）,&i=0 x0012FF7C&j=0 x0012FF7C,/*/*程 序 名：7_16.cpp（引用测试）*/*作 者：wuwh*/*编制时间：2002年11月25日*/*主要功能：对“引用”的测试*/*#include/预编译命令int main(void)/主函数int i=3;/定义和初始化int,输出结果为i的地址：0 x0012FF7Cj的地址：0 x0012FF7C名与别名两者所表示的地址相同。注意：你的运算结果的地址可能和本书所给的不同，但 i 和 j 的地址会是一样的。,利用引用来传递参数,我们先来看下面的程序。这个程序是用来输出两个数中
9、之大者的。这个程序在 7_17.cpp 中，是用指针来编写的。现在我们利用引用来编写。之后再比较两者之异同，看引用的好处。,/*/*程 序 名：7_17.cpp（引用测试）*/*作 者：wuwh*/*编制时间：2002年11月26日*/*主要功能：利用引用来传递参数*/*#include/预编译命令,/交换两浮点数void swap(float/主函数结束,void swap(float,void main()float x,y;coutx;couty;/交换x,y并输出swap(x,y);coutn调用swap(x,y)n;coutx=xendl;couty=yendl;,说明：1、子函数中
10、两个形式参数被声明为引用，都是对浮点类型的数的引用。2、主函数在键盘输入 x,y 值之后，执行 swap(x,y);这时实参为 x,y的值，形参为 xx,yy。将实参传递给形参的过程相当于在做float 使 xx 成为 x 的引用，yy 成为 y 的引用。或者说 xx 成为变量 x 的地址（&x）的符号名的别名；yy 成为变量 y 的地址（&y）的符号名的别名。,本来子函数是不能直接对变量 x,y 进行操作的。经过引用之后，两个“别名”xx 与 yy 替代了 x,y。表面上看，主函数在调用子函数时，传递的是变量 x,y，而实际上传递给子函数的是 x,y 变量的地址。形式上看是对 xx,yy 进
11、行操作，实质上在对 x,y 进行操作。3、从这个例子看出，引用具有指针的强大功能，但在传递参数、调用函数时却有良好的可读性。,比较 swap(float xx,float yy)与 swap(float&xx,float&yy),x y 3.0 5.0 xx yy 3.0 2 5.0 5.0 3.0 1 temp 3 3.0,x(别名xx)y(别名yy)3.0 5.0 5.0 2 3.0 1 temp 3 3.0,本来子函数是不能直接对变量 x,y 进行操作的。经过引用之后，两个“别名”xx 与 yy 替代了 x,y。表面上看，主函数在调用子函数时，传递的是变量 x,y，而实际上传递给子函数的
12、是 x,y 变量的地址。形式上看是对 xx,yy 进行操作，实质上在对 x,y 进行操作。,思 考几种参数传递方式的比较,/*/*程 序 名：7_18.cpp*/*作 者：wuwh*/*编制时间：2002年11月27日*/*主要功能：参数传递比较*/*#include/传引用void swap1(int,/传引用void swap1(int,/传地址（指针），修改指针所指地址的内容void swap2(int*xx,int*yy)int temp;temp=*xx;*xx=*yy;*yy=temp;cout子函数：*xx=*xx*yy=*yy endl;,/传值void swap3(int x
13、x,int yy)int temp;temp=xx;xx=yy;yy=temp;cout子函数：xx=xx yy=yy endl;,/传地址（指针），修改指针本身void swap4(int*xx,int*yy)int*p;p=xx;xx=yy;yy=p;cout子函数：*xx=*xx*yy=*yy endl;,void main()/主函数int x,y;x=100;y=200;cout初始值：x=x y=y endl;cout endl;,/传引用cout 传引用：swap1(x,y)endl;swap1(x,y);cout主函数：x=x y=y endl;cout endl;,/传地址（
14、传址）x=100;y=200;cout 传地址，修改指针所指的内容：swap2(,/传值x=100;y=200;cout 传 值：swap3(x,y)endl;swap3(x,y);cout主函数：x=x y=y endl;cout endl;,/传地址x=100;y=200;cout 传地址，修改指针：swap4(,链 表,【例】某电视台希望王小二同学为他们编一个程序。该程序可以将节目串在一起，形成一份有序的节目预告。节目列表有如下三项,1、节目名称包括新闻联播（CCTV News）祖国各地（Motherland）体育之窗（Sports）学校见闻（College）电影展播（Movie）2、节
15、目主持人（Director）3、播放时间长度（Time）,我们可以将每一个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一条链表。用一个所谓的头指针 head 指向链表的第一个结点。如下图所示,head,头指针,下面的程序是建立链表的过程。,/*/*程 序 名：7_19.cpp*/*作 者：wuwh*/*编制时间：2002年11月26日*/*主要功能：链表*/*#include struct ActList/定义一个名为 ActList 结构char ActName20;/节目名为字符数组char director20;/主持人为字符数组int Mtime;/节目长度为分
16、钟ActList*next;/指向 ActList 结构的指针;ActList*head;/链头指针,ActList char ActName20;char director20;数据域 int Mtime;ActList*next;指针域,/AcitList 结构的指针函数ActList*Create()ActList*p=NULL;/指向待插入的结点 ActList*q=NULL;/指针，用于在其后插入结点head=NULL;/一开始链表为空int Time;/节目时长，如为0则退出,/以下是给新结点输入节目信息cout Time;while(Time!=0)/当该节目的时长不为0时，将其
17、/纳入链表中p=new ActList;/分配内存空间给p结点/让Time赋给p结点的结构成员Mtimep-Mtime=Time;cout p-ActName;/输入节目名称cout p-director;/输入主持人,void displayList(ActList*head)cout Mtime ActName director next;void main()/主函数开始/调用子函数displaList()/调用时的实参为Create()函数的返回值displayList(Create();/主函数结束,说明1、先从主函数说起主函数只有一条语句 displayList(Create();
18、这是调用子函数 displayList，该子函数的形参为 ActList*head 是一个指向 ActList 结构的名为 head 的指针变量。在主函数调用 displayList 时所用的实际参数来自运行 Create()函数的返回值。从 Create()的定义ActList*Create()看出 Create()函数的返回值应该是一个指向 ActList 的指针。主函数在调用子函数时，又遇到该函数的实参又是调用另一个函数之后的返回值。看起来的确显得复杂，但是我们耐心分析之后，感到并不难。,2、程序开头为结构定义。在这里我们称这样的一个结构为一个结点。这个结点包含两个域：数据域和指针域,结
19、 点,数据域中装有节目的信息，而指针域装的是指向另一个结点的地址。显然这是为形成链表而专门设置的。,3、在定义 Create 函数之前，先定义了一个指向结构的头指针 head，即ActList*head;4、定义 Create函数，该函数可返回指向 ActList 结构的指针，即ActList*Create()分析这个函数的功能可分如下4块,定义ActList*p=NULL;ActList*q=NULL;head=NULL;int Time;定义了两个指向结构 ActList 的指针 p 和 q，并初始化为空，即未指向任何地址。同时让头指针 head 也为空。再定义一个临时变量 Time，是一
20、个整型数。,提示“输入节目时长”，之后用键盘输入，用了下面两句：cout Time;这部分程序语句是为下面的 while 循环做准备的。如果 Time 不为 0，才做下面的内容。,while(Time!=0)循环在当循环的循环体内完成建立链表的过程。首先给 p 结点分配内存空间。这个内存空间的大小要根据 p 结点的定义（p 结点是 ActList 结构）来确定。p 结点有了内存空间，就可以给它的各个成员赋值了。接着下面就是几个赋值语句p-MTime=Time;cout p-ActName;/用键盘输入节目名称cout p-director;/用键盘输入主持人,接着是一个分支语句if(head=
21、NULL)head=p;这是说如果头指针为空，表示链表还是空的，这时 p 结点就是第一个结点。让 head 赋值为 p，即让 head 指向 p 结点。之后让 q=p;这是让 q 指向刚进入链表的结点，让 p 再去指向待加入的结点。如果 p 结点已不是第一个结点了，head 必不为 NULL，因此要走 else 分支，即else q-next=p;,将此时的 p 结点放到 q 所指向的结点后面。之后让 q=p;即让 q 指向刚进入链表的结点，腾出 p 去指向下一个待加入的结点。接下来输入下一个节目时长，cout Time;至此，while 语句的循环体结束。当 Time 值不为0，就会有结点加
22、入链表，继续执行循环体。一旦 Time 为 0，则会跳出 while 循环。,执行两条语句if(head!=NULL)q-next=NULL;return(head);第一条是说，如果 head 不空说明链表已建成，这时 q 一定是最后一个结点，将该结点的指针域置成空，以表明它是链尾。第二条 return(head);将这条链表的头指针 head 返回。这件事意味着执行完 Create函数后得到 head 指针所指向的地址，这个地址就是链表中的第一个结点的地址。这时对主函数而言displayList(Create()就是dispalyList(head)调用 dsplayList(head)就
23、会将整个链表从头至尾输出。,1、定义 ActList 结构，结构中包含数据域和指针域。将一个结构看作一个结点。2、定义一个指向结构的指针 head，准备用来指向链表的第一个结点。3、定义一个指向ActList 结构的指针函数，起名为 Create 函数，该函数返回的是创建好的链的头指针 head。下面是 Create 函数所要做的事情：定义指向 ActList 结构的两个指针 p 和 q，定义后立即初始化为 NULL，即不指向任何地址。再让头指针 head 为 NULL，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。然后定义一个中间变量“节目时长 Time”，当 Time 为 0 时
24、，建立链表的过程应该结束。,建立链表的过程可归纳为如下三个步骤,下面程序的构思是，只要 Time 不为 0，就要构建链表。构建的思路是将一个一个的结点加至链表里来。首先给 p 找一个能够指向的内存空间，我们说这是给 p 结点分配一片内存空间。如下图,建立链表的过程可归纳为如下三个步骤,p,然后，通过键盘往这个空间中装入与节目有关的信息。装完之后判断一下 head 为空否，如为空则 p 结点为第一个结点，让 head 指向 p 结点就完成了有一个结点的链表。之后让 q 赋值为 p，即使让 q 指针去指向刚加入链表的结点，将 p 指针腾出来去做下一个结点的工作。,head,p,q,图 链表的第一个
25、结点建成,当 Time 不为 0，p 又被分配了内存空间，形成了第二个结点，装入节目信息后，判断 head 不再为空，说明前面已有结点在链表中，这时要将第二个结点放到 q 所指向的结点的后面。执行 q-next=p 之后就完成了。之后再将 q 指针移到第二个结点上，将 p 指针腾出来去做下一个结点的工作。,head,p,q,指针移到第二个结点上，将 p 指针腾出来去做下一个结点的工作。,head,q,第三个结点加入链表的过程为,head,q,p,最末一个结点连至链表的尾部之后，要在 q 指针所指向的最后一个机诶但的指针域加上一个 NULL，表示这里是链尾了，后面再也不连结点了。,head,q,
26、推 荐 练 习1、编程计算 105 的所有约数。2、使用一角、二角、五角的硬币组成一元钱，编程输出有多少种组成方法，输出格式为方法号 一角硬币个数 二角硬币个数 五角硬币个数 1 10 0 0 2 8 1 0 3 6 2 0 4 4 3 0 5 2 4 0 6 0 5 0 7 5 0 1,3、求出所有用7、8、9三个数字组成的，且各位数字互不相同的三位数。4、角夫（日本数学家）猜想：任意一个自然数，比如奇数，将其乘以 3 再加 1；如果是偶数将其除以 2，反复运算，会出现什么结果。试编程试之。5、“数学黑洞”。任意一个四位自然数，将组成该数的各位数字重新排列，形成一个最大数和一个最小数，之后两数相减，其差仍为一个自然数。重复进行能够上述运算，你会发现一个神秘的数。,结 束,
