《Visual C++程序设计》课件第4章.ppt

1、【问题问题】从键盘接收从键盘接收10个数，求平均数并输出小于平均数的数个数，求平均数并输出小于平均数的数分析：分析：从键盘接收从键盘接收10个数，求平均数很简单，可以采用简单变个数，求平均数很简单，可以采用简单变量和循环结构相结合的方法，程序段如下：量和循环结构相结合的方法，程序段如下：float aver=0;for(i=0;i10;i+)cout输入第输入第i+1ai;aver+=ai;aver=aver/10;/求求10个数的平均数个数的平均数 但是输出小于平均数的数就比较麻烦了，因为从键盘接收但是输出小于平均数的数就比较麻烦了，因为从键盘接收的的10个数在求和以后没有保存起来，等再比较

2、比平均数小的数个数在求和以后没有保存起来，等再比较比平均数小的数就无法实现。若要输出小于平均数的数，必须再重复输入这就无法实现。若要输出小于平均数的数，必须再重复输入这10个数。这样带来两个问题：个数。这样带来两个问题：（1）输入数据的工作量成倍增加；）输入数据的工作量成倍增加；（2）若本次输入的数与上次不同，则输出的结果不正确。）若本次输入的数与上次不同，则输出的结果不正确。在程序设计中，我们常把具有相同类型的若干变量按在程序设计中，我们常把具有相同类型的若干变量按有序的形式组织起来，这些有序的形式组织起来，这些按序排列的同类型数据元素的按序排列的同类型数据元素的集合称为集合称为数组数组。数

3、组属于。数组属于构造类型构造类型，在计算机中，一个数，在计算机中，一个数组在内存中占用一片连续的存储空间，在程序中用数组名组在内存中占用一片连续的存储空间，在程序中用数组名来标识这一数组，而下标指明数组中各元素的序号，用下来标识这一数组，而下标指明数组中各元素的序号，用下标变量来标识数组的每个元素。标变量来标识数组的每个元素。根据下标的个数不同可以根据下标的个数不同可以把数组分为把数组分为一维一维、二维二维和和多维多维的的，本章重点介绍一维和二，本章重点介绍一维和二维数组。维数组。数组在使用前数组在使用前必须先定义（数组名、类型、大小、维必须先定义（数组名、类型、大小、维数），后使用数），后使

4、用。ss0s1s2s 3 s4正确：正确：const int s=10;int as;float f5;错误：错误：int s=10;int as;float b3.4 下标从下标从0开始开始 数组名是常量，表示数组在内存中的首地址。数组名是常量，表示数组在内存中的首地址。数组长度应该为整型常量表达式，数组长度应该为整型常量表达式，不能是变量不能是变量。如：如：4.2.1 一维数组的定义、存储和初始化一维数组的定义、存储和初始化1.定义形式定义形式 数据类型数据类型 数组名数组名整型常量表达式整型常量表达式;如：如：int s5；2.数组的初始化数组的初始化花括号花括号错误错误:int a10

5、;a=1,3,5,7,9;/数组名是个地址常量，不能被赋值。数组名是个地址常量，不能被赋值。int a10;a10=1,3,5,7,9;/a10不是数组中的元素，不能用花括号为一个元素赋多个值。不是数组中的元素，不能用花括号为一个元素赋多个值。int c3=1,2,3,4;/常量个数超过数组定义的长度。常量个数超过数组定义的长度。2)给部分元素赋初值。给部分元素赋初值。如：如：int a10=1,3,5,7,9;花括号内列出的值赋给了前面的若干个元素，花括号内列出的值赋给了前面的若干个元素，其余元素系其余元素系统自动赋统自动赋0。1)给所有元素赋初值。给所有元素赋初值。如：如：int a5=0

6、,2,4,6,8;或或 int a=0,2,4,6,8;4.2.2 数组元素的引用和基本操作数组元素的引用和基本操作1数组元素的引用数组元素的引用 形式：形式：数组名数组名下标下标 相当于一个普通变量相当于一个普通变量如有：如有：int a10=1,2,3,4,5,6,7,8,9,10,b10,i(2)；则：则：a3=a0+ai；couta2+i；coutaa3；couta10;/数组下标越界数组下标越界 couta;/对数组一般不能作为一个整体进行操作对数组一般不能作为一个整体进行操作 b=a;2基本操作基本操作 假设有定义：假设有定义：int aN;N是已定义过的符号常量。是已定义过的符号

7、常量。(1)数组元素的输入数组元素的输入for(j=0;jaj;(2)通过随机函数通过随机函数rand()产生产生0 0100100的的N N个数据个数据 for(i=0;iN;i+)/rand()函数产生函数产生032727之间的整数之间的整数 ai=int(rand()%101);(3)数组元素的求和数组元素的求和 sum=0;for(j=0;jN;j+)sum+=aj;(4)求数组中的最大元素求数组中的最大元素 max=a0;/假设第一个元素值最大假设第一个元素值最大 for(j=1;jmax)max=aj;(5)求最大元素下标求最大元素下标 imax=0;/imax代表最大元素下标代表

8、最大元素下标 for(j=1;jaimax)imax=j;(6)将最大元素放于某一特定位置将最大元素放于某一特定位置(如放在最前头如放在最前头)imax=0;for(j=1;jaimax)imax=j;if(imax!=0)t=a0;a0=aimax;aimax=t;4.2.3 数组排序数组排序 排序是将一组数按递增或递减的次序排列，如按学生排序是将一组数按递增或递减的次序排列，如按学生的成绩、球赛积分等排序。常用的算法有的成绩、球赛积分等排序。常用的算法有:选择法选择法 ()冒泡法冒泡法 ()插入法插入法 快速排序法快速排序法 .1.选择法排序选择法排序基本思想基本思想:(1)从从n个数的序

9、列中选出最小的数个数的序列中选出最小的数(递增递增),与第与第1个数交换位置；个数交换位置；(2)除第除第1个数外，其余个数外，其余n-1个数再按个数再按(1)的方法选出次小的数，与的方法选出次小的数，与第第2个数交换位置个数交换位置;3)重复重复(1)n-1遍，最后构成递增序列。遍，最后构成递增序列。【例例4.2】对存放在数组中的对存放在数组中的6个数，用选择法按递增排序。个数，用选择法按递增排序。下标下标:0 15 1 25 2 35 3 45 4 5for(i=0;i5;i+)min=i;for(j=i+1;j6;j+)if(ajamin)min=j;if(i!=min)temp=ai;

10、ai=amin;amin=temp;2.冒泡法排序冒泡法排序 8 3497K=5348 79K=4 34789K=33 47 8 9K=2for(i=0;i5;i+)for(j=1;jaj)temp=aj-1;aj-1=aj;aj=temp;思考思考:当数据未交换当数据未交换,说明数组已有序说明数组已有序,如何如何结束排序结束排序?（1）从第一个元素开始，对数组中两两相邻的元素比较，将）从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较比值较小的元素放在前面，值较大的元素放在后面，一轮比较比较完毕，最大的数存放在较完毕，最大的数存放在aN-1中

11、；中；（2）然后对）然后对a0到到aN-2的的N-1个数进行同个数进行同(1)的操作，次最大的操作，次最大数放入数放入aN-2元素内，完成第二趟排序；依次类推，进行元素内，完成第二趟排序；依次类推，进行N-1趟趟排序后，所有数均有序。排序后，所有数均有序。【例例4.3】用冒泡排序法实现例用冒泡排序法实现例4.2基本思想总结：基本思想总结：a00 a01 a02 a10 a11 a12 以以“先行后列先行后列”的规则连续存放的规则连续存放:序号序号=当前行号当前行号*每行列数每行列数+当前列号当前列号4.3.1 二维数组的定义和初始化二维数组的定义和初始化 1.数组的定义数组的定义 形式：形式：

12、数据类型数据类型 数组名数组名常量表达式常量表达式1常量表达式常量表达式2；如如:float a23;aa00a01a02a10a11a121000H1004H1008H100CH1010H1014H序号序号:012345（1）按在内存排列顺序对所有元素赋初值。）按在内存排列顺序对所有元素赋初值。int a23=1,2,3,4,5,6;或或 int a3=1,2,3,4,5,6;（2）按行给所有元素赋初值，每一行的数据放于一个花）按行给所有元素赋初值，每一行的数据放于一个花括号内。括号内。int a23=1,2,3,4,5,6;（3）按行给部分元素赋初值，在静态存贮类型）按行给部分元素赋初值，

13、在静态存贮类型static中省中省略的元素初值此时自动为略的元素初值此时自动为0。static int b34=1,2,0,3,4,0,0,5;对应的数组对应的数组b为为:050004300021b002000001c2.数组的初始化数组的初始化（4）按行赋初值也可省略第一维的长度。）按行赋初值也可省略第一维的长度。static int c 3=1,2;对应的数组对应的数组c为为:4.3.2 二维数组的基本操作二维数组的基本操作 1.数组的输入、输出数组的输入、输出【例例4.4】输入两个矩阵输入两个矩阵A、B的值，求的值，求C=A+B。61312753A161361084B分析：分析：A、B矩

14、阵相加，其实质是将两矩阵的对应元素矩阵相加，其实质是将两矩阵的对应元素相加。相加的条件是有相同的行、列数。相加。相加的条件是有相同的行、列数。#include iostream.h#include iomanip.h void main()int a23,b23,c23,i,j;for(i=0;i2;i+)for(j=0;jaij;for(i=0;i2;i+)for(j=0;jbij;for(i=0;i2;i+)/A+B矩阵，每个对应元素相加矩阵，每个对应元素相加 for(j=0;j3;j+)cij=aij+bij;for(i=0;i2;i+)for(j=0;j3;j+)coutsetw(4)

15、cij;coutendl;2.求二维数组中最大（或最小）元素及下标求二维数组中最大（或最小）元素及下标 max=a00;imax=0;jmax=0;for(i=0;i3;i+)for(j=0;jmax)max=aij;imax=i;jmax=j;【例例4.5】对对33方阵，求最大元素及下标。方阵，求最大元素及下标。与一维数组求最大值的方式相同，但要用双重循与一维数组求最大值的方式相同，但要用双重循环来实现。环来实现。3.矩阵转置矩阵转置 1 2 3 1 4 7a=4 5 6 b=2 5 8 7 8 9 3 6 9for(i=0;i3;i+)for(j=0;ji;j+)t=aij;aij=aji

16、;aji=t;将矩阵以主对角线为轴线，将元素的行和列位置调换。将矩阵以主对角线为轴线，将元素的行和列位置调换。【例例4.6】对对33方阵转置方阵转置 4.矩阵相乘矩阵相乘43129631185210741B4234C10nkkjikijbac设矩阵设矩阵A、B为：为：则则矩阵矩阵C C为：为：即即矩阵矩阵C C的第的第i i行第行第j j列元素可通过列元素可通过下边下边公式求得公式求得：c00元素的实现：元素的实现：s=0;for(k=0;k3;k+)s+=a0k*bk0;c00=s;程序：程序：#include iostream.h#define M 2#define N 3#define

17、P 4void main()int aMN=3,5,7,4,6,8,bNP=1,4,7,10,2,5,8,11,3,6,9,12；int cMP,i,j,k,s;for(i=0;iM;i+)for(j=0;jP;j+)s=0;/求一个元素的值求一个元素的值 for(k=0;kN;k+)s+=aik*bkj;cij=s;for(i=0;iM;i+)for(j=0;jP;j+)coutcij ;coutendl;字符串是由一对双引号作定界符的若干个有效字符组字符串是由一对双引号作定界符的若干个有效字符组成的字符序列。存储时自动在最后加入结束标志符成的字符序列。存储时自动在最后加入结束标志符0 。例

18、如对字符串常量：例如对字符串常量：ab123ab1230系统自动添加系统自动添加 0 结束标志符结束标志符处理字符串的方法处理字符串的方法有：有：字符数组、字符数组、CString（string）类和字符指针）类和字符指针。1.字符数组字符数组如：如：char s6；char s126；字符数组字符数组若干个字符若干个字符字符串字符串abcdabcd02.字符数组的初始化字符数组的初始化(1)逐个字符赋初值逐个字符赋初值 char s10=I,a,m,f,i,n,e;/s不是字符串不是字符串(2)用字符串为字符数组初始化用字符串为字符数组初始化 char s10=I am fine;char

19、s10=I am fine;s是字符串，是字符串，0 系统自动添加系统自动添加(3)字符串数组初始化字符串数组初始化 对二维数组以字符串形式初始化。对二维数组以字符串形式初始化。char a48=FOXPRO,FORTRAN,“BASIC,C/C+;注意：注意：对于二维字符数组，用两个下标表示数组中的一个对于二维字符数组，用两个下标表示数组中的一个字符。字符。注意注意不要出现下面的错误不要出现下面的错误:char s10=This is a book;char s10;s=I am fine;char s10;s=I,a,m,f,i,n,e;3.字符数组的输入字符数组的输入/输出输出(1)逐个

20、数组元素的输入逐个数组元素的输入/输出输出 char s110;for(i=0;is1i;/s1中是字符，不是字符串中是字符，不是字符串注意：注意：输入时各输入项之间不需加空格分隔输入时各输入项之间不需加空格分隔(2)字符串整体的输入字符串整体的输入/输出输出 char s110,s225;输入：输入：cins1;gets(s1);for(int i=0;is1;语句，字符串中不能有空格。语句，字符串中不能有空格。函数函数gets()和和puts()是是对字符串整体输入对字符串整体输入/输出输出，应，应加加#include stdio.h命令命令。gets(字符数组名或字符指针变量名字符数组名

21、或字符指针变量名);puts(字符数组名或字符指针变量名字符数组名或字符指针变量名);输出：输出：cout s1;puts(s1);for(i=0;i2;i+)puts(s2i);#include stdio.h#include iostream.hvoid main()int i;char c5=C,h,i,n,a;char b =China;for(i=0;i5;i+)/不能用不能用puts(c),也不能用也不能用coutc;cout ci;puts(b);/或或 coutb;for(i=0;bi!=0;i+)/正确的正确的,但不主张用这种方法但不主张用这种方法 cout bi;【例例4.

22、8】字符串的输入字符串的输入/输出输出 有关字符与字符串操作的区别详见有关字符与字符串操作的区别详见P88表表1.4.2。4.字符串处理函数字符串处理函数设设:char str210=aaa,str110;strcpy(str1,str2);str1=“bb;str1=str2;使用下面函数时，使用下面函数时，应应加加#include string.h命令命令。1)strlen(str)功能功能:求求str所指向的字符串长度。不包括字符串结束标志所指向的字符串长度。不包括字符串结束标志0。说明说明:str可为字符串常量、字符数组名或字符指针。可为字符串常量、字符数组名或字符指针。2)strlw

23、r(str)功能功能:将字符串中的大写字母转换成小写字母。将字符串中的大写字母转换成小写字母。说明说明:str为字符字符串常量、数组名或字符指针。为字符字符串常量、数组名或字符指针。3)strupr(str)功能功能:将字符串中的小写字母转换成大写字母。将字符串中的小写字母转换成大写字母。说明说明:str为字符字符串常量、数组名或字符指针。为字符字符串常量、数组名或字符指针。4)strcpy(str1,str2)功能功能:将将str2所指的字符串复制到所指的字符串复制到str1中。中。说明说明:str1和和str2为字符数组名或字符指针为字符数组名或字符指针,str2还可以是字符串常还可以是字

24、符串常量。量。str1要有足够大的空要有足够大的空 间间。5)strcat(str1,str2)功能：功能：将将str2字符串内容连接到字符串内容连接到str1字符串内容的后面字符串内容的后面 说明：说明：str1要有足够大的空间。要有足够大的空间。例如：例如：char s120=abcd;coutstrcat(s1,kkk)endl;/s1中的内容变为中的内容变为abcdkkk 6)strcmp(str1,str2)功能：功能：比较字符串比较字符串str1和和str2的大小。的大小。说明：说明：从左至右逐个字符进行比较从左至右逐个字符进行比较ASCII码值，直到出现不相码值，直到出现不相同字

25、符或遇到同字符或遇到0为止。为止。str1 小于小于str2 返回返回-1str1等于等于str2 返回返回 0str1大于大于str2 返回返回 1strcmp(ABCD,BD);/结果为：结果为：-1#include stdio.h#include string.hvoid main()char s80;while(1)gets(s);if(strcmp(s,pass)puts(Invalid password.n);else break;puts(passn);【例例4.9】字符串处理函数示例字符串处理函数示例&求地址求地址 变量的地址在编程阶段是不知道的，因为只有到程序运行变量的地址在

26、编程阶段是不知道的，因为只有到程序运行时才为变量分配存储空间，但在程序中可以使用时才为变量分配存储空间，但在程序中可以使用&运算符求得运算符求得变量的地址。变量的地址。int x;&x就是变量的地址就是变量的地址4.5.1 指针指针1.基本概念基本概念 每个变量在内存中存放都要占用一定的空间，变量占用的每个变量在内存中存放都要占用一定的空间，变量占用的内存空间的第一个字节的编号就是变量的地址，将内存空间的第一个字节的编号就是变量的地址，将存放地址的存放地址的变量称为指针变量变量称为指针变量。取内容取内容*(地址地址)表示根据地址取内容表示根据地址取内容如上图所示，如上图所示，*(&x)的值为的

27、值为4指针指针指针是一种变量，存放另一个变量的地址。指针是一种变量，存放另一个变量的地址。int x=4;int *p;p=&x;p就是一个指针，存放就是一个指针，存放x的地址。的地址。10014pxp指向指向x，*p就是就是x，值为，值为4。出现出现x的地方可以用的地方可以用*p代替，出现代替，出现*p的地方可以用的地方可以用x代替。代替。2.定义及初始化定义及初始化 定义：定义：例如：例如：int *p；float *q;初始化：初始化：在定义的同时赋初值，称为指针变量的初始化。在定义的同时赋初值，称为指针变量的初始化。例如：例如：float d=1.5,*p=&d；可改写为：可改写为：f

28、loat d=1.5,*p;p=&d;/注意不能写做注意不能写做*p=&d数据类型数据类型 *标识符；标识符；指针所指对象的类型指针所指对象的类型不是指针名的一部分不是指针名的一部分&d1.5p pd d 假定有定义：假定有定义：int*p,a;v p=NULL;指针的值为指针的值为NULL(0)表示不指向任何对象。表示不指向任何对象。v p=&a;p指向变量指向变量a。v p1=&a;p2=p1;相同类型的指针变量可以相互赋值。相同类型的指针变量可以相互赋值。例例,假设有定义假设有定义:int a,*p;float f;则以下形式不允许：则以下形式不允许：()p=&f;()p=100;3.运

29、算运算 赋值运算赋值运算算术运算算术运算vp+n(或或p-n)：p+n：指向后面的第个元素。：指向后面的第个元素。p-n：指向前面的第个元素。：指向前面的第个元素。p+n的值为：的值为：p的值的值n*sizeof(p指向的类型）指向的类型）如，有定义：如，有定义：int a,*p=&a;假设假设a的地址为的地址为1000,则：则：p的值为：的值为：1000p+3的值为：的值为：1000+3*sizeof(int)=1000+3*4=1012*p+*(p+)*p p+(*p)+*p (*p)+v自增（自增（+）和自减（）和自减（-）p+p+、+p+p、p-p-、-p-p自增或自减后自增或自减后p

30、 p指向前一个或后一个元素指向前一个或后一个元素指针相减指针相减 两个类型相同的指针可以相减，结果为这两个地址差之间两个类型相同的指针可以相减，结果为这两个地址差之间能够存放的数据个数（数据类型为指针所指的类型）。能够存放的数据个数（数据类型为指针所指的类型）。如，有定义：如，有定义：int*p1,*p2；假设假设p1指向指向1000，p2指向指向1008，则，则p2-p1的值为：的值为：(1008-1000)/sizeof(int)=21.new运算符运算符 用于向系统申请动态存储空间，并把首地址作为运算结果。用于向系统申请动态存储空间，并把首地址作为运算结果。形式为形式为:指针指针=new

31、 数据类型数据类型;指针指针=new 数据类型数据类型(初值初值);或或2.delete运算符运算符 用于释放用用于释放用new申请的动态存储空间，申请的动态存储空间，形式为：形式为：delete 指针指针;delete 指针指针;或或无需指明数组长度无需指明数组长度只能释放由只能释放由new申请的动态变量申请的动态变量4.5.2 动态存储空间动态存储空间例：例：int a=3,*p=&a,*q;q=new int(6);delete p;()delete q;【例例2-3】指针运算示例指针运算示例#include void main()int*p=new int;*p=3;cout*pend

32、l;coutpendl;delete p;cout*pendl;数组的地址是制是指数组存放的起始地址，以数组名表示。数组的地址是制是指数组存放的起始地址，以数组名表示。设有定义：设有定义：int a6=10,20,30,40,50,60，*p=a;下面介绍引用数组元素的三种方式。下面介绍引用数组元素的三种方式。1.下标方式下标方式形式：形式：数组名数组名下标下标 2.地址方式地址方式 形式：形式：*(地址地址)3.指针方式指针方式 形式：形式：*指针变量名指针变量名 假设有定义假设有定义:float a10,*p=a;则如下的等价关系成立：则如下的等价关系成立：(1)p a&a0(2)p+i

33、a+i&ai(3)*(p+i)*(a+i)ai(4)指针可以作数组名用指针可以作数组名用 即：即：pi ai4.5.3 指针和一维数组指针和一维数组设有：设有：int a10,*p;则则:p=a;for(i=0;iai;等价于：等价于：p=a;for(i=0;i*p+;p=a;for(i=0;i*p;p=a;for(i=0;i*(p+i);/*(p+i)pi 思考：思考：第三种方法与其它二种区别何在第三种方法与其它二种区别何在？int a10a0a1a2a3a4a5a6a7a8a9p使用指针来引用数使用指针来引用数组元素速度快，但组元素速度快，但直观性、安全性要直观性、安全性要差些！差些！分析

34、下列程序：分析下列程序：#include void main()int a10,i,*p;p=a;for(i=0;i*p+;for(i=0;i10;i+,p+)cout*p;思考：思考：数组元素能否正确输出？数组元素能否正确输出？注意：注意：p与与a的区别的区别:p是地址变量，而是地址变量，而a是地址常量。是地址常量。p+、p-、p=p+2 a+、a=a+2*p+与与(*p)+区别区别 *p+的的+运算符作用于指针变量运算符作用于指针变量 (*p)+的的+运算符作用于指针变量所指对象运算符作用于指针变量所指对象设有定义：设有定义：int a6=10,20,30,40,50,60，*p=a+2;

35、cout*p+;/输出输出30cout*p;/输出输出40cout(*p)+;/输出输出30 cout*p;/输出输出31+级别高于级别高于*数组名数组名a可以解释为指向可以解释为指向int类型的二级指针常量；类型的二级指针常量；a可以可以看成是由两个元素看成是由两个元素a0、a1构成的一维数组，构成的一维数组，a0可以看成是由可以看成是由a00、a01、a02 3个整型变量个整型变量组成的一维数组，可将组成的一维数组，可将a0解释为指向解释为指向int类型的一级指针类型的一级指针常量；常量；a1具有具有a0相同的性质。相同的性质。设有定义设有定义：int a23;4.5.4 指针和二维数组指

36、针和二维数组指针方式引用二维数组元素的两种方式：指针方式引用二维数组元素的两种方式：1.指针变量引用数组元素指针变量引用数组元素 设有定义：设有定义：int a23,*p=a0;/&a00通过通过p指针显示二维数组的各元素：指针显示二维数组的各元素：for(i=0;i6;p+,i+)cout*p;if(i%3=0)couts;gets(s);p=china;/指向指向字符串常量的首地址字符串常量的首地址 p=new char6;或或 p=s;/应使字符指针有确定指向后才应使字符指针有确定指向后才能从键盘进行输入操作能从键盘进行输入操作 cinp;或或 gets(s);运算运算字符数组名字符数组

37、名s不能进不能进行自增或自减运算行自增或自减运算 p是指针变量，可以进行自增或自减是指针变量，可以进行自增或自减运算运算 可通过字符指针来访问字符数组，可通过字符指针来访问字符数组，二者的区别：二者的区别：【例例4.15】输入一串字符存储在字符数组中，用指针方式输入一串字符存储在字符数组中，用指针方式逐一显示字符，并求其长度。逐一显示字符，并求其长度。#include iostream.h#include stdio.hvoid main()char s80,*p;gets(s);p=s;/p指向数组的第一个元素指向数组的第一个元素 cout输出每个字符：输出每个字符：;while(*p!=0

38、)cout*p+;/指针下移，直到指针下移，直到p指向字符串结束符指向字符串结束符 coutn 字符串长度字符串长度:p-sendl;字符指针数组常用于处理若干字符串。字符指针数组常用于处理若干字符串。设有定义：设有定义：char*book=Fortran90,C/C+,Delphi,Visual Basic;按字符串的实际长度存储，以按字符串的实际长度存储，以00表示每个字符串的结表示每个字符串的结束。束。采用交换指针值的方法改变指针的指向。采用交换指针值的方法改变指针的指向。字符指针数组排序前字符指针数组排序前字符指针数组排序后字符指针数组排序后【例例4.16】对对4个字符串，按字典顺序将

39、它们排序输出。个字符串，按字典顺序将它们排序输出。#include iostream.h#include string.hvoid main()char*book=Fortran90,C/C+,Delphi,Visual Basic,*p;int i,j,k;for(i=0;i3;i+)k=i;for(j=i+1;j0)k=j;if(i!=k)p=booki;booki=bookk;bookk=p;for(i=0;i4;i+)coutbooki-成员名成员名通过指向结构的指针引用结构变量成员通过指向结构的指针引用结构变量成员成员访问运算符成员访问运算符优先级最高的优先级最高的四个运算符之一四个

40、运算符之一 括号不能少括号不能少假设有定义假设有定义:man m,*p=&m;则可如下引用结构成员则可如下引用结构成员strcpy(m.name,Fang Min);p-birthday.month=8;#include#include struct personchar name10;/姓名姓名 bool sex;/性别性别 int age;/年龄年龄 float pay;/工资工资a10;void main()int n,i,k;person x;coutn;cout从键盘输入具有从键盘输入具有person结构的结构的n个记录：个记录：endl;【例例】用结构体数组保存数据用结构体数组保存

41、数据 for(i=0;ix.name;cink;if(k=1)x.sex=true;else x.sex=false;/1为男，非为男，非1为女为女 cinx.agex.pay;ai=x;/结构赋值结构赋值 cout显示具有显示具有person结构的结构的n个记录：个记录：endl;for(i=0;in;i+)coutai.name;if(ai.sex=true)coutman;else coutwoman;coutai.age ai.payendl;4.6.2 链表链表1.线性链表概念线性链表概念 在结构体成员中有一种特殊类型，它除了包含一般的在结构体成员中有一种特殊类型，它除了包含一般的数

42、据域外，还包含一个指向自身结构的指针域。这种类型数据域外，还包含一个指向自身结构的指针域。这种类型的对象又称为结点，每个结点的指针域用来指向下一个结的对象又称为结点，每个结点的指针域用来指向下一个结点，由此形成一个链表。点，由此形成一个链表。地址值地址值 data next整数值整数值例如：例如：struct item int data;/结点值域结点值域 struct item*next;/结点指针域结点指针域;head.2.4.5NULL1datanext2.线性链表线性链表 用链指针链在一起的自引用结构的线性集合。用链指针链在一起的自引用结构的线性集合。例：例：在一个链表中，指向第一个结

43、点的指针称为在一个链表中，指向第一个结点的指针称为表头指针表头指针，第一个结点又称为第一个结点又称为表头结点表头结点，每个结点的指针域所指向的，每个结点的指针域所指向的结点称为该结点的后继结点，而该结点又称为后继结点的结点称为该结点的后继结点，而该结点又称为后继结点的前驱结点，链表中的第一个结点无前驱结点，最后一个结前驱结点，链表中的第一个结点无前驱结点，最后一个结点（又称为点（又称为表尾结点表尾结点）无后继结点。）无后继结点。.2.4.5NULL1head.2.4.5.1headhead.2NULL.4.5.NULL1.单向链表单向链表(以正向链表为例以正向链表为例)双向链表双向链表循环链表

44、循环链表(以单向循环链表为例以单向循环链表为例)建立一个简单的链表建立一个简单的链表静态链表静态链表head2000H2400HNULLtail#include iostream.h#include iomanip.hstruct stud long num;double score;struct stud*next;void main()struct stud a,b,c,*head,*p;a.num=9901;a.score=90.8;b.num=9902;b.score=89.5;c.num=9903;c.score=76.0;head=&a;a.next=&b;b.next=&c;c.

45、next=NULL;p=head;docoutsetw(6)numsetw(6)scorenext;while(p!=NULL);2000H2400H2600H2600H9901 90.89902 89.59903 76.0 该方法虽能实现简单链该方法虽能实现简单链表结构，但事先必须定义确表结构，但事先必须定义确定个数的结构体变量，缺乏定个数的结构体变量，缺乏灵活性，要想增加一个结点，灵活性，要想增加一个结点，必须修改程序，不能动态地必须修改程序，不能动态地进行存储分配。进行存储分配。对链表的主要操作有以下几种对链表的主要操作有以下几种:建立或生成一个链表建立或生成一个链表查找链表元素查找链表

46、元素插入一个链表新表元素插入一个链表新表元素v插表头插表头将每一新元素固定插入至当前已生成将每一新元素固定插入至当前已生成 链表的表头位置链表的表头位置v插表尾插表尾将每一新元素固定插入至当前已生成将每一新元素固定插入至当前已生成 链表的表尾位置链表的表尾位置v有序表有序表将每一新元素插入至链表中适当位置将每一新元素插入至链表中适当位置 (表头、表中或表尾表头、表中或表尾)，以保持链表的有序性，以保持链表的有序性删除一个链表元素删除一个链表元素遍历链表，输出遍历链表，输出(显示、打印显示、打印)各表元素有关信息。各表元素有关信息。3.线性链表生成与遍历线性链表生成与遍历【例例】键入简化的学生数

47、据，把它们组成线性链表，并键入简化的学生数据，把它们组成线性链表，并输出各学生信息。要求每一新表元素都插入至已生成链输出各学生信息。要求每一新表元素都插入至已生成链 表的表头位置。编写程序实现之。表的表头位置。编写程序实现之。分析：第一阶段：第一阶段：生成生成 依次键入学号依次键入学号(假设互不相同假设互不相同)，创建新的表元素，创建新的表元素，并并插入至表头位置插入至表头位置。遇结束标志。遇结束标志(-1)即止，此时已生成即止，此时已生成所需链表。所需链表。第二阶段：第二阶段：遍历遍历 从表头开始，从表头开始，“顺藤摸瓜顺藤摸瓜”遍历所有表元素并输出遍历所有表元素并输出各表元素中的有关信息各

48、表元素中的有关信息学号，直至表尾。学号，直至表尾。程序要点：程序要点：设置两个指针变量：设置两个指针变量：head和和temp。#include#includestruct item int xh;item*next;void main()item*head=NULL,*temp;/初始表头为NULL int stno;coutstno;while(stno!=-1)temp=new item;temp-xh=stno;temp-next=head;/初始表尾为NULL /以后实现表元素的连接 head=temp;/更新表头 cinstno;cout输出为:endl;temp=head;/非空

49、表可略 while(temp!=NULL)coutsetw(4)xh;temp=temp-next;coutxh=stno;temp-next=head;/表尾初始化为表尾初始化为NULLhead2NULLhead=temp;/更新表头更新表头temp=new item;temp-xh=stno;temp-next=head;/实现表元素的连接实现表元素的连接 head=temp;/更新表头更新表头 headtemphead2NULL5temp5temphead2NULL52NULL请输入学号请输入学号,-1 停止停止:2 5 4 1-1 输出为输出为:1 4 5 2运行示例运行示例:.1.4

50、.5NULL2headtemp执行完第一阶段后所生成的线性链表及指针变量位置：执行完第一阶段后所生成的线性链表及指针变量位置：思考：思考：如要求每一新表元素都插入至已生成链表的表尾位如要求每一新表元素都插入至已生成链表的表尾位置，该如何修改程序？置，该如何修改程序？1.1.插入数据插入数据基本思想：基本思想：1 1）首先要查找待插入数据在数组中的位置）首先要查找待插入数据在数组中的位置k k；2 2）然后从最后一个元素开始往前直到下标为）然后从最后一个元素开始往前直到下标为k k的元素依次往后的元素依次往后移动一个位置；移动一个位置；3)3)第第k k个元素的位置空出，将欲插入的数据插入。个元