吴文虎 程序设计基础 第2版 PPT第12

1、结结 构构 数数 组组结构也可以构成数组，即数组元素是结构，当然要结构也可以构成数组，即数组元素是结构，当然要求这一类数组的全部元素都应该是同一类结构。求这一类数组的全部元素都应该是同一类结构。先看下例，例中有同宿舍的四名同学的数据，构成先看下例，例中有同宿舍的四名同学的数据，构成一个有四个元素的结构数组。一个有四个元素的结构数组。/*/* 程程 序序 名：名：7_14.cpp */* 作作 者：者：wuwh */* 编制时间：编制时间：2002年年11月月21日日 */* 主要功能：结构数组主要功能：结构数组 */*#include #include struct student/ 定义结构

2、定义结构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 q;/ 定义定义 q

3、 为为student结构结构/ 以下是按年龄大小对四位同学进行排序以下是按年龄大小对四位同学进行排序int i = 0;int j = 0;for (j=0; j3; j+)/ for jfor (i=0; i Roomi+1.birthday)/ ifq = Roomi;Roomi = Roomi+1;Roomi+1 = q;/ if/ for i/ for jfor (i=0; i4; i+)/ for icout R n Roomi.sex n Roomi.birthday n Roomi.height n Roomi.weight n;/ for i/ 主函数主函数说

4、明说明上述程序可完成冒泡排序。在排序过程中数组中上述程序可完成冒泡排序。在排序过程中数组中的元素是结构。按生日大小排序时，学生的的元素是结构。按生日大小排序时，学生的5个数据个数据作为一个整体（结构）来调整在数组中的位置。作为一个整体（结构）来调整在数组中的位置。作业：作业：希望你能按身高排序改写上述程序。希望你能按身高排序改写上述程序。/*/* 程程 序序 名：名：7_15.cpp */* 作作 者：者：wuwh */* 编制时间：编制时间：2002年年11月月21日日 */* 主要功能：主要功能：结构结构指针数组指针数组 */*#include #include struct studen

5、t/ 定义结构定义结构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,

6、59.0f;void main( )/ 定义定义指向指向 student 结构的指针数组，指向结构的指针数组，指向Room数组元素数组元素student *p4=&Room0, &Room1, &Room2, &Room3;student *q;/ 定义一个指向定义一个指向 student 结构的指针，结构的指针，/ 用作中间变量用作中间变量/ 下面仍用冒泡排序将屋中下面仍用冒泡排序将屋中4人依身高从大到小排序人依身高从大到小排序int i=0; int j=0;for (j=0; j3; j+)/ for jfor (i=0; iheight height )

7、q=pi; pi=pi+1; pi+1=q;for (i=0; i4; i+)/ 输出排序结果输出排序结果cout name endl;cout sex endl;cout birthday endl;cout height endl;cout weight height 是名为是名为 pi 的指针通过箭头操作符来访的指针通过箭头操作符来访问问 my 结构成员结构成员 height。3、语句、语句 if (pi-height height) 是说如果是说如果 Roomi 中的中的 height 成员比成员比 Roomi+1 中的中的 height 成员小，就去做下面的语句组：变换指针的指向，成

8、员小，就去做下面的语句组：变换指针的指向，让让 pi 改去指向改去指向 Roomi+1，让，让 pi+1 指向指向 Roomi。这样做就比前一个程序好。当着结构成员很多时，这样做就比前一个程序好。当着结构成员很多时，直接让结构变量相互交换并不是好办法，直接让结构变量相互交换并不是好办法，而现在的而现在的做法做法只需将指针的指向交换一下，极为省力。只需将指针的指向交换一下，极为省力。引用的概念及应用引用的概念及应用古代有的人有名有字还有号古代有的人有名有字还有号。在在 C+ 中，为了方便除了给变量起一个名中，为了方便除了给变量起一个名之外，有时还要给它起一个之外，有时还要给它起一个“别名别名”。

9、这里。这里我们介绍我们介绍“引用引用”的概念和用引用传递参数的概念和用引用传递参数的方法。的方法。比如，我们先定义一个整型变量比如，我们先定义一个整型变量 i 并初始化并初始化为为3。再声明。再声明 j 是对整型数的引用，并初始化是对整型数的引用，并初始化为引用为引用 i 。两个语句为两个语句为int i = 3;/ 是定义是定义int &j = i;/ 是声明是声明比较这两行语句，显然第二行在比较这两行语句，显然第二行在 int 后多了后多了“&”号，号，这个这个“&”在这里为在这里为“引用运算符引用运算符”。&后可以后可以跟任何以英文字符开头的名字作引用的名

10、字。跟任何以英文字符开头的名字作引用的名字。我们说我们说 int i = 3; 是定义和初始化。是定义就需要是定义和初始化。是定义就需要给变量分配内存空间。有了内存空间，才能将整型给变量分配内存空间。有了内存空间，才能将整型数数 3 装到这个分配好的内存地址中。装到这个分配好的内存地址中。而第二条语句而第二条语句 int &j=i; 是声明和初始化，而不是定义和初始化是声明和初始化，而不是定义和初始化。比较比较 int i，和，和 int &j。前者是定义，需要分配内存单。前者是定义，需要分配内存单元给变量元给变量 i；后者是声明，不是定义，不需要分配内；后者是声明，不是定义，

11、不需要分配内存单元给存单元给 j，仅仅声明了一个引用，或者说仅仅起了，仅仅声明了一个引用，或者说仅仅起了一个一个“别名别名”而已。而已。下面，我们用图示来细说下面，我们用图示来细说定义定义和和声明声明的关系。的关系。int i=3; 定义之后，系统为定义之后，系统为 i 分配了内存地址单元分配了内存地址单元, i为符号地址。为符号地址。int &j=i; 声明声明 j 是是 i 的的“别名别名”。即。即 j 是是 i 的引用，的引用，系统并不去为系统并不去为 j 分配内存单元。而是说分配内存单元。而是说 j 是是 i 的的“别别名名”。别名和正名所代表的符号地址是同一个地址。别名和正名

12、所代表的符号地址是同一个地址。为了验证上述说法，请作如下实验为了验证上述说法，请作如下实验i （ 别名别名 j ）&i=0 x0012FF7C&j=0 x0012FF7C/*/* 程程 序序 名：名：7_16.cpp （引用测试）（引用测试） */* 作作 者：者：wuwh */* 编制时间：编制时间：2002年年11月月25日日 */* 主要功能：主要功能：对对“引用引用”的测试的测试 */*#include / 预编译命令预编译命令int main(void)/ 主函数主函数int i=3;/ 定义和初始化定义和初始化int &j=i;/ 声明声明j是对整数是对整数

13、i的引用，的引用，j初始化为引用初始化为引用icout i的的地址地址&iendl;cout j的的地址地址&jendl;if (&i=&j)cout 名与别名两者所表示的地址相同名与别名两者所表示的地址相同endl;elsecout 名与别名两者所表示的地址不同名与别名两者所表示的地址不同endl;return 0;输出结果为输出结果为i的地址：的地址：0 x0012FF7Cj的地址：的地址：0 x0012FF7C名与别名两者所表示的地址相同。名与别名两者所表示的地址相同。注意：注意：你的运算结果的地址可能和本书所给的不同，但你的运算结果的地址可能和本书所给的

14、不同，但 i 和和 j 的地址会是一样的。的地址会是一样的。利用引用来传递参数利用引用来传递参数我们先来看下面的程序。这个程序是用来输出两我们先来看下面的程序。这个程序是用来输出两个数中之大者的。这个程序在个数中之大者的。这个程序在 7_17.cpp 中，是用指中，是用指针来编写的。现在我们利用引用来编写。之后再比针来编写的。现在我们利用引用来编写。之后再比较两者之异同，看引用的好处。较两者之异同，看引用的好处。/*/* 程程 序序 名：名：7_17.cpp （引用测试）（引用测试） */* 作作 者：者：wuwh */* 编制时间：编制时间：2002年年11月月26日日 */* 主要功能：主

15、要功能：利用引用来传递参数利用引用来传递参数 */*#include / 预编译命令预编译命令/ 交换两浮点数交换两浮点数void swap(float &xx, float &yy)float temp;/ 临时变量临时变量temp = xx;xx = yy;yy = temp;void main()/ 主函数主函数/ 主函数开始主函数开始float x,y;/ 定义两浮点数定义两浮点数x,y/ 提示输入提示输入x,ycoutx;couty;/ 交换交换x,y并输出并输出swap(x,y);coutn调用调用swap(x,y)n;coutx=xendl;couty=yendl

16、;/ 主函数结束主函数结束说明：说明：1、子函数中两个形式参数被声明为引用，都是对浮点、子函数中两个形式参数被声明为引用，都是对浮点类型的数的引用。类型的数的引用。2、主函数在键盘输入、主函数在键盘输入 x, y 值之后，执行值之后，执行 swap(x,y); 这这时实参为时实参为 x, y的值，形参为的值，形参为 xx, yy。将实参传递给形。将实参传递给形参的过程相当于在做参的过程相当于在做float &xx=x;float &yy=y;使使 xx 成为成为 x 的引用，的引用，yy 成为成为 y 的引用。或者说的引用。或者说 xx 成为变量成为变量 x 的地址（的地址（&

17、amp;x）的符号名的别名；）的符号名的别名； yy 成成为变量为变量 y 的地址（的地址（&y）的符号名的别名。）的符号名的别名。本来子函数是不能直接对变量本来子函数是不能直接对变量 x, y 进行操作的。进行操作的。经过引用之后，两个经过引用之后，两个“别名别名” xx 与与 yy 替代了替代了 x, y。表面上看，主函数在调用子函数时，传递的是变量表面上看，主函数在调用子函数时，传递的是变量 x, y，而实际上传递给子函数的是，而实际上传递给子函数的是 x, y 变量的地址。形变量的地址。形式上看是对式上看是对 xx, yy 进行操作，实质上在对进行操作，实质上在对 x, y 进

18、行进行操作。操作。3、从这个例子看出，、从这个例子看出，引用具有指针的强大功能，但在引用具有指针的强大功能，但在传递参数、调用函数时却有良好的可读性。传递参数、调用函数时却有良好的可读性。思思 考考几种参数传递方式的比较几种参数传递方式的比较/*/* 程程 序序 名：名：7_18.cpp */* 作作 者：者：wuwh */* 编制时间：编制时间：2002年年11月月27日日 */* 主要功能：参数传递比较主要功能：参数传递比较 */*#include / 传引用传引用void swap1(int &xx, int &yy)int temp;temp = xx;xx = yy;

19、yy = temp;cout子函数：子函数：xx=xx yy=yy endl;/ 传地址（指针），修改指针所指地址的内容传地址（指针），修改指针所指地址的内容void swap2( int *xx, 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

20、endl;/ 传地址（传址）传地址（传址）x=100; y=200;cout 传地址，修改指针所指的内容：传地址，修改指针所指的内容： swap2(&x,&y) endl;swap2(&x, &y);cout主函数：主函数：x=x y=y endl;cout endl;链链 表表【例例】某电视台希望王小二同学为他们编一个程序。该程某电视台希望王小二同学为他们编一个程序。该程序可以将节目串在一起，形成一份有序的节目预告。序可以将节目串在一起，形成一份有序的节目预告。节目列表有如下三项节目列表有如下三项1、节目名称、节目名称包括包括新闻联播（新闻联播（CCTV Ne

21、ws）祖国各地（祖国各地（Motherland）体育之窗（体育之窗（Sports）学校见闻（学校见闻（College）电影展播（电影展播（Movie）2、节目主持人（、节目主持人（Director）3、播放时间长度（、播放时间长度（Time）我们可以将每一个节目单独放在一个结构里，用我们可以将每一个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一一个指针把两个结构连在一起，一天的节目形成一条链表。用一个所谓的头指针条链表。用一个所谓的头指针 head 指向链表的第一指向链表的第一个结点。如下图所示个结点。如下图所示head头指针头指针下面的程序是建立链表的过程。下面的程序

22、是建立链表的过程。/*/* 程程 序序 名：名：7_19.cpp */* 作作 者：者：wuwh */* 编制时间：编制时间：2002年年11月月26日日 */* 主要功能：链表主要功能：链表 */*#include struct ActList/ 定义一个名为定义一个名为 ActList 结构结构char ActName20;/ 节目名为字符数组节目名为字符数组char director20; / 主持人为字符数组主持人为字符数组int Mtime;/ 节目长度为分钟节目长度为分钟ActList *next;/ 指向指向 ActList 结构的指针结构的指针;ActList *head;/

23、链头指针链头指针/ 以下是给新结点输入节目信息以下是给新结点输入节目信息cout Time;while(Time != 0)/ 当该节目的时长不为当该节目的时长不为0时，将其时，将其/ 纳入链表中纳入链表中p = new ActList;/ 分配内存空间给分配内存空间给p结点结点 / 让让Time赋给赋给p结点的结构成员结点的结构成员Mtimep-Mtime = Time;cout p-ActName; / 输入节目名称输入节目名称cout p-director; / 输入主持人输入主持人void displayList(ActList *head)cout 显示节目列表显示节目列表n;whi

24、le(head!=NULL) / 当指针当指针head不空，则输出不空，则输出cout Mtime endl ActName endl director endl next;void main()/ 主函数开始主函数开始/ 调用子函数调用子函数displaList()/ 调用时的实参为调用时的实参为Create()函数的返回值函数的返回值displayList(Create();/ 主函数结束主函数结束说明说明1、先从主函数说起、先从主函数说起主函数只有一条语句主函数只有一条语句 displayList(Create( );这是调用子函数这是调用子函数 displayList，该子函数的形参为

25、，该子函数的形参为 ActList *head 是一个指向是一个指向 ActList 结构的名为结构的名为 head 的指针变量。在主的指针变量。在主函数调用函数调用 displayList 时所用的实际参数来自运行时所用的实际参数来自运行 Create( ) 函函数的返回值。从数的返回值。从 Create( ) 的定义的定义ActList *Create( )看出看出 Create( ) 函数的返回值应该是一个指向函数的返回值应该是一个指向 ActList 的指针。的指针。主函数在调用子函数时，又遇到该函数的实参又是调用另主函数在调用子函数时，又遇到该函数的实参又是调用另一个函数之后的返回值

26、。看起来的确显得复杂，但是我们耐心一个函数之后的返回值。看起来的确显得复杂，但是我们耐心分析之后，感到并不难。分析之后，感到并不难。2、程序开头为结构定义。在这里我们称这样的一个结构、程序开头为结构定义。在这里我们称这样的一个结构为一个为一个结点结点。这个结点包含两个域：。这个结点包含两个域：数据域数据域和和指针域指针域结结 点点数据域中装有节目的信息，而指针域装的是指向数据域中装有节目的信息，而指针域装的是指向另一个结点的地址。显然这是为形成链表而专门设另一个结点的地址。显然这是为形成链表而专门设置的。置的。3、在定义、在定义 Create 函数之前，先定义了一个指向结构函数之前，先定义了一

27、个指向结构的头指针的头指针 head，即，即ActList *head;4、定义、定义 Create函数，该函数可返回指向函数，该函数可返回指向 ActList 结构结构的指针，即的指针，即ActList *Create( )分析这个函数的功能可分如下分析这个函数的功能可分如下4块块 定义定义ActList *p = NULL;ActList *q = NULL;head = NULL;int Time;定义了两个指向结构定义了两个指向结构 ActList 的指针的指针 p 和和 q，并，并初始化为空，即未指向任何地址。同时让头指针初始化为空，即未指向任何地址。同时让头指针 head 也为空。

28、再定义一个临时变量也为空。再定义一个临时变量 Time，是一个，是一个整型数。整型数。 提示提示“输入节目时长输入节目时长”，之后用键盘输入，用了，之后用键盘输入，用了下面两句：下面两句：cout Time;这部分程序语句是为下面的这部分程序语句是为下面的 while 循环做准备的。循环做准备的。如果如果 Time 不为不为 0，才做下面的内容。，才做下面的内容。 while( Time != 0 ) 循环循环在当循环的循环体内完成建立链表的过程。首在当循环的循环体内完成建立链表的过程。首先给先给 p 结点分配内存空间。这个内存空间的大小要结点分配内存空间。这个内存空间的大小要根据根据 p 结

29、点的定义（结点的定义（p 结点是结点是 ActList 结构）来确结构）来确定。定。p 结点有了内存空间，就可以给它的各个成员结点有了内存空间，就可以给它的各个成员赋值了。接着下面就是几个赋值语句赋值了。接着下面就是几个赋值语句p-MTime = Time;cout p-ActName;/ 用键盘输入节目名称用键盘输入节目名称cout p-director;/ 用键盘输入主持人用键盘输入主持人接着是一个分支语句接着是一个分支语句if (head=NULL) head=p;这是说如果头指针为空，表示链表还是空的，这时这是说如果头指针为空，表示链表还是空的，这时 p 结点就是第一个结点。让结点就是

30、第一个结点。让 head 赋值为赋值为 p，即让，即让 head 指向指向 p 结点。之后让结点。之后让 q=p; 这是让这是让 q 指向刚进指向刚进入链表的结点，让入链表的结点，让 p 再去指向待加入的结点。如果再去指向待加入的结点。如果 p 结点已不是第一个结点了，结点已不是第一个结点了，head 必不为必不为 NULL，因此要走因此要走 else 分支，即分支，即else q-next = p;将此时的将此时的 p 结点放到结点放到 q 所指向的结点后面。之所指向的结点后面。之后让后让 q=p; 即让即让 q 指向刚进入链表的结点，腾出指向刚进入链表的结点，腾出 p 去指向下一个待加入的

31、结点。去指向下一个待加入的结点。接下来输入下一个节目时长，接下来输入下一个节目时长，cout Time;至此，至此，while 语句的循环体结束。当语句的循环体结束。当 Time 值不值不为为0，就会有结点加入链表，继续执行循环体。一，就会有结点加入链表，继续执行循环体。一旦旦 Time 为为 0，则会跳出，则会跳出 while 循环。循环。 执行两条语句执行两条语句if (head != NULL) q-next = NULL;return (head);第一条是说，如果第一条是说，如果 head 不空说明链表已建成，这时不空说明链表已建成，这时 q 一定是最后一个结点，将该结点的指针域置成

32、空，以表明一定是最后一个结点，将该结点的指针域置成空，以表明它是链尾。它是链尾。第二条第二条 return (head); 将这条链表的头指针将这条链表的头指针 head 返回。返回。这件事意味着执行完这件事意味着执行完 Create函数后得到函数后得到 head 指针所指向的指针所指向的地址，这个地址就是链表中的第一个结点的地址。这时对地址，这个地址就是链表中的第一个结点的地址。这时对主函数而言主函数而言displayList( Create( ) ) 就是就是dispalyList( head )调用调用 dsplayList(head) 就会将整个链表从头至尾输出。就会将整个链表从头至尾

33、输出。1、定义、定义 ActList 结构，结构中包含数据域和指针域。将一个结结构，结构中包含数据域和指针域。将一个结构看作一个结点。构看作一个结点。2、定义一个指向结构的指针、定义一个指向结构的指针 head，准备用来指向链表的第一，准备用来指向链表的第一个结点。个结点。3、定义一个指向、定义一个指向ActList 结构的指针函数，起名为结构的指针函数，起名为 Create 函数，函数，该函数返回的是创建好的链的头指针该函数返回的是创建好的链的头指针 head。下面是下面是 Create 函数所要做的事情：函数所要做的事情： 定义指向定义指向 ActList 结构的两个指针结构的两个指针 p

34、 和和 q，定义后立即初，定义后立即初始化为始化为 NULL，即不指向任何地址。再让头指针，即不指向任何地址。再让头指针 head 为为 NULL，也是不指向任何地址，表示该链表尚未建立，一个，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。然后定义一个中间变量结点也没有。然后定义一个中间变量“节目时长节目时长 Time”，当当 Time 为为 0 时，建立链表的过程应该结束。时，建立链表的过程应该结束。建立链表的过程可归纳为如下三个步骤建立链表的过程可归纳为如下三个步骤 下面程序的构思是，只要下面程序的构思是，只要 Time 不为不为 0，就要构建链表。，就要构建链表。构建的思路是将

35、一个一个的结点加至链表里来。构建的思路是将一个一个的结点加至链表里来。首先给首先给 p 找一个能够指向的内存空间，我们说这是给找一个能够指向的内存空间，我们说这是给 p 结点分配一片内存空间。如下图结点分配一片内存空间。如下图建立链表的过程可归纳为如下三个步骤建立链表的过程可归纳为如下三个步骤p 然后，通过键盘往这个空间中装入与节目有关的信息。然后，通过键盘往这个空间中装入与节目有关的信息。装完之后判断一下装完之后判断一下 head 为空否，如为空则为空否，如为空则 p 结点为第一个结点为第一个结点，让结点，让 head 指向指向 p 结点就完成了有一个结点的链表。之结点就完成了有一个结点的链表。之后让后让 q 赋值为赋值为 p，即使让，即使让 q 指针去指向刚