6 构造数据类型(基础)

六、复合数据的描述

−−构造数据类型（基础部分）主要内容构造数据类型概述枚举类型数组类型结构类型联合类型构造数据类型有些数据不适合用基本数据类型来表示。例如：星期、月份、向量、矩阵、学生信息、...语言往往提供了由基本数据类型来构造新类型的手段。在C++中，由基本数据类型构造出来的新类型称为构造数据类型，它属于用户自定义数据类型。枚举类型如何描述下列数据：星期：星期一、......、星期六、星期天月份：一月、......、十二月颜色：红、绿、蓝、............如果用基本数据类型来表示上述的数据，则会面临下面的问题：它们只能取基本数据类型值集中很少的值基本数据类型的一些运算对它们没有意义取值的含义不清晰例如，如果用一个int型变量day来描述星期这样的数据，将会面临：day只能取int中的7个值，不会取其它的值。day=10;//语义错误对day进行算术运算没有意义。day=day*2;//没有意义1表示什么？星期天用什么表示？0还是7？在C++中用枚举类型来解决上面的问题：枚举类型是由用户自定义的一种简单数据类型。在定义一个枚举类型时，需要列出其值集中的每个值--枚举值。枚举类型的变量只能取这些值。枚举类型的定义枚举类型的定义格式为：enum<枚举类型名>{<枚举值表>};<枚举值表>为用逗号隔开的若干个整型符号常量。例如：enumDay{SUN,MON,TUE,WED,THU,FRI,SAT};enumColor{RED,GREEN,BLUE};enumMonth{JAN,FEB,MAR,APR,MAY,JUN,JUL, AUG,SEP,OCT,NOV,DEC};bool类型可看成是C++语言提供的一个预定义的枚举类型：enumbool{false,true};为了能参加算术、关系以及逻辑运算，每个枚举值都对应一个整型数：默认情况下，第一个枚举值为0，其它的值为前一个值加1。在定义枚举类型时，也可显式地给枚举值指定值。例如：enumDay{SUN=7,MON=1,TUE,WED,THU,FRI,SAT};TUE为2，...注意：运算后的结果不再是枚举类型！枚举类型变量的定义先定义枚举类型，再定义枚举类型变量：enumDay{SUN,MON,TUE,WED,THU,FRI,SAT};Dayd1;或enumDayd1;//C语言的写法枚举类型和枚举类型变量同时定义：enumDay{SUN,MON,TUE,WED,THU,FRI,SAT}d1;或enum{SUN,MON,TUE,WED,THU,FRI,SAT}d1;枚举类型的操作赋值一个枚举类型的变量只能在相应枚举类型的值集中取值。例如：Dayday;day=SUN;//OKday=RED;//Error，RED不属于Day类型的值集相同枚举类型之间可以进行赋值操作，例如：Dayd1,d2;d2=d1;可以把一个枚举值赋值给一个整型变量，例如：inti;i=d1;//OK，将进行类型转换不能把一个整型值赋值给枚举类型的变量，例如：d1=i;//Errord1=(Day)i;//OK，但不安全！不能对枚举类型的值直接进行输入，但可以直接进行输出。例如：Dayd;cin>>d;//Errorcout<<d;//OK，将把d转换成int输出枚举类型输入/输出举例#include<iostream>usingnamespacestd;enumDay{SUN,MON,TUE,WED,THU,FRI,SAT};intmain(){ Dayd; inti; cin>>i; switch(i) { case0:d=SUN; break; case1:d=MON; break; case2:d=TUE; break; case3:d=WED; break; case4:d=THU; break; case5:d=FRI; break; case6:d=SAT; break; default:cout<<"InputError!"<<endl;exit(-1); } ...... switch(d)//输出枚举值的名 { caseSUN: cout<<"SUN"<<endl; break; caseMON: cout<<"MON"<<endl; break; caseTUE: cout<<"TUE"<<endl; break; caseWED: cout<<"WED"<<endl; break; caseTHU: cout<<"THU"<<endl; break; caseFRI: cout<<"FRI"<<endl; break; caseSAT: cout<<"SAT"<<endl; break; } return0;}算术运算枚举值可以进行算术运算，运算前枚举值将转换成对应的整型值。运算的结果类型为算术类型。例如：Dayd;inti;......i=d+1;//OKd=d+1;//Error，因为d+1的结果为int类型。d=(Day)(d+1)//OK比较运算枚举值之间的比较为枚举值所对应的整数之间的比较。例如：MON<TUE（结果为true）结果为逻辑类型逻辑运算0：false；非0：true结果为逻辑类型使用枚举类型有利于提高程序的可读性和可靠性。例如，对不同的颜色做不同的处理：Colorbk_color;......switch(bk_color){caseRED:......caseGREEN:......caseBLUE:......}对某个星期的每一天的数据进行处理：for(Dayd=SUN;d<=SAT;d=(Day)(d+1)){......//数据处理}数组类型如何表示向量和矩阵这样的复合数据？如果用独立的变量来分别表示它们的元素，则会面临：变量数量太多（x1、x2、x3、...、y11、y12、...）。变量之间缺乏显式的联系。C++提供了数组类型来表示上述的数据：数组类型是一种由固定多个同类型的元素按一定次序所构成的复合数据类型。数组类型是一种用户自定义的数据类型，可分为：一维数组：表示向量等具有线性结构的数据二维数组：表示矩阵等具有行列结构的数据多维数组：表示具有三维及三维以上结构的数据一维数组

一维数组用于表示由固定多个同类型的具有线性次序关系的数据所构成的复合数据类型。例如：向量某门课程的成绩表某班级学生的姓名表......上述数据可抽象为线性表：除了两个元素外，其他每一个元素都有且仅有一个直接前驱和一个直接后继；除外的两个元素中，一个只有前驱，另一个只有后继。一维数组类型定义一维数组类型定义格式为：typedef<元素类型><一维数组类型名>[<元素个数>];

<元素类型>为任意C++类型（void除外）<元素个数>为整型常量表达式例如：typedefintA[10];//由10个int型元素所构成的

//一维数组类型A一维数组类型变量定义格式为： <一维数组类型名><一维数组变量名>;或 <元素类型><一维数组变量名>[<元素个数>];<元素类型>为任意C++类型（void除外）<元素个数>为整型常量表达式例如：（下面两个a等价）typedefintA[10];Aa;//由10个int型元素所构成的数组变量。或inta[10];//由10个int型元素所构成的数组变量。一维数组类型变量定义一维数组变量的初始化用一对花括号把元素的初始值括起来。例如：inta[10]={1,2,3,4,5,6,7,8,9,10};初始化表中的值可以少于数组元素个数，不足部分的数组元素初始化成0。例如：intb[10]={1,2,3,4};//后6个元素初始化为0如果每个元素都进行了初始化，则数组元素个数可以省略。例如：intc[]={1,2,3};//隐含着c由三个元素构成一维数组的操作通常情况下，对数组类型数据的操作要通过其元素来进行。访问一维数组元素：<一维数组变量名>[<下标>]<下标>为整型表达式第一个元素的下标为：0例如：inta[10];//由10个元素构成的数组aa[0]、a[1]、...、a[9]//访问数组元素可把数组的每个元素看成是独立的变量，分别对它们进行操作。例如：inta[10];intsum=0,i;for(i=0;i<10;i++)cin>>a[i];//输入元素值for(i=0;i<10;i++)sum+=a[i];//元素求和不能对两个数组进行整体赋值，需要通过元素来进行：inta[10],b[10];.....a=b;//Errorfor(inti=0;i<10;i++)a[i]=b[i];//OK例：用一维数组实现求前n个费波那契(Fibonacci)数#include<iostream>usingnamespacestd;intmain(){ constintMAX_N=40; intfibs[MAX_N];//用于存放费波那契数 intn; cout<<"请输入n(1-"<<MAX_N<<"):"; cin>>n; if(n>MAX_N) { cout<<"n太大!应不大于"<<MAX_N<<endl; return-1; } fibs[0]=fibs[1]=1;//初始化第1、2个费波那契数

for(inti=2;i<n;i++)//计算第3、4、...、n个费波那契数

fibs[i]=fibs[i-1]+fibs[i-2]; cout<<"前"<<n<<"个费波那契数是：";for(inti=0;i<n;i++)cout<<fibs[i]<<''; return0;}例：从键盘输入n个数，然后按数值从小到大输出它们这是个“排序”（sort）问题：把待排序的若干元素放在一个数组中。按某个算法调整元素的位置使它们按某种次序排列。排序有各种算法，冒泡法是其中的一种排序算法：从左到右依次比较相邻两个数，如果前一个大、后一个小，则交换它们俩的位置。经过上述一轮的“比较--交换”操作之后，最大的数排到了最后一个位置。去掉最大的数（在最后一个位置），在剩下的数中再采用上述的“比较--交换”操作，然后去掉次大的数。依此类推，直到只剩下一个数为止。8

194318

9431894

318493184398194318439第一轮：第二轮：18439148

3

914

38

9第三轮：......//程序......intmain(){ constintN=10; inta[N],n;

cin>>n;//输入待排序的数的个数

if(n>N)return-1;//个数超出数组范围 for(inti=0;i<n;i++)cin>>a[i];//输入待排序的数 intn_r=n;//n_r为剩下的数的个数 while(n_r>1)//只要剩下数的个数大于一，就要进行一轮比较

{

boolexchange=false;//每一轮比较前把交换标记设置为false

for(inti=1;i<n_r;i++)//i为比较的数的下标：1~n_r-1

{if(a[i]<a[i-1])//与前一个数进行比较

{intt=a[i];a[i]=a[i-1];a[i-1]=t;//交换a[i]与a[i-1]的值

exchange=true;//发生了交换，把交换标记设置为true

}

}

if(!exchange)break;//如果本轮比较没有发生交换，不再进入下一轮

n_r--; } for(inti=0;i<n;i++)cout<<a[i]<<'';} 可以优化：如果某一轮没发生交换，就没必要进行下一轮了！例：求解约瑟夫（Josephus）问题约瑟夫（Josephus）问题：有N个小孩（编号为0～N-1）围坐成一圈，从某个小孩开始顺时针报数（1、2、...），报到M的小孩从圈子离开，然后，从下一个小孩开始重新报数，每报到M，相应的小孩从圈子离开，......，最后一个离开圈子的小孩为胜者，问胜者是哪一个小孩？采用一个一维的循环数组in_circle来表示小孩围成一圈：boolin_circle[N];in_circle[i]：true表示编号为i的小孩在圈子里；false表示编号为i的小孩离开了圈子。圈子中位置i的下一个位置为：(i+1)%N

0N-11N-2报数采用下面的方法来实现：从编号为0的小孩开始报数，用变量index表示要报数的小孩的下标，其初始值为N-1（即将报数的前一个小孩的下标）。下一个要报数的小孩的下标：index=(index+1)%N用变量count来对成功的报数进行计数，每一轮报数前，count为0，每成功地报一次数，就把count加1，直到M为止。要使得报数成功，in_circle[index]应为true。成功报数M后，把in_circle[index]设成false。用变量num_of_children_remained表示圈中剩下的小孩数目，其初始值为N。//变量num_of_children_remained表示圈中剩下的小孩数目，其初始值为N//变量count来对成功的报数进行计数//变量index表示要报数的小孩的位置#include<iostream>usingnamespacestd;constintN=20,M=5;intmain(){ boolin_circle[N]; //初始化数组in_circle。

for(inti=0;i<N;i++) in_circle[i]=true; //开始报数

intindex=N-1;//从编号为0的小孩开始报数，

//index为前一个小孩的位置。

intnum_of_children_remained=N;//报数前的圈子中小孩个数

while(num_of_children_remained>1) { intcount=0; while(count<M)//对成功的报数进行计数，直到M。

{ index=(index+1)%N;//计算要报数的小孩的编号。

if(in_circle[index])count++; //如果编号为index的

//小孩在圈子中，该报数为成功的报数。

} in_circle[index]=false;//小孩离开圈子。

num_of_children_remained--;//圈中小孩数减1。

} //找最后一个小孩

for(inti=0;i<N;i++) if(in_circle[i]){index=i;break;}

cout<<"ThewinnerisNo."<< index<<".\n"; return0;}一维数组的存储分配对于一维数组类型的数据，系统将会在内存中给其分配连续的存储空间来存储数组元素。例如：inta[10];其内存空间分配如下：a[0]a[1] ... a[9]一维数组所占的内存空间大小可以用sizeof操作符来计算。例如：cout<<sizeof(a);//输出数组a所占的内存字节数。a[i]的地址可由下面公式计算（以字节为单位）：a的首地址+i*sizeof(int)注意：C++语言注重程序的效率，运行时刻不对数组元素下标越界进行检查，下面代码的执行不会报错：inta[2],b[3],c[4],i;......b[i]=10;//如果i>=3，10存储到哪里去了?因此，程序设计时，一定要对下标进行仔细考虑！为了方便、可靠地实现一些简单的对一维数组元素进行遍历的操作，在C++新国际标准中提供了一种基于范围的for语句。例如，对一维数组元素求和的操作可写成： inta[10],sum=0; for(intn:a)sum+=n;//不改变元素的值再例如，给数组每个元素输入一个值： for(int&n:a)cin>>n;//改变元素的值向函数传递一维数组如果要把一个数组作为参数传给函数，则被调用的函数一般要提供两个形参：一个为不带数组大小的一维数组定义；另一个为数组元素的个数。例如：intmax(intx[],intn)//计算x中最大元素的下标{ inti_max=0;//先假设第0个元素最大

for(inti=1;i<n;i++) if(x[i]>x[i_max])i_max=i; returni_max;}调用者需要把一个一维数组变量的名以及数组元素的个数传给被调用函数。例如：inta[10],b[20],index_max;......index_max=max(a,10);cout<<a[index_max]<<index_max<<endl;index_max=max(b,20);cout<<b[index_max]<<index_max<<endl;注意：为了提高数组传递的效率，数组作为函数参数传递时，C++默认传递的是数组在内存中的首地址，这样，函数的形参数组不再分配内存空间，它共享实参数组的内存空间。例：用选择排序法编写一个排序函数选择排序：设要排序的数有n个。从n个数中找出最大者，与第n个数交换位置；然后，从剩余的n-1个数中再找出最大者，与第n-1个数交换位置；…，一直到剩下的数只有一个为止。3194865207

3174865209

31748

65209

3174065289

......

0123456789

3194865207

voidsort(intx[],intn)//排序函数{

while(n>1)

{ inti_max=0; for(inti=1;i<n;i++)//找最大者 if(x[i]>x[i_max])i_max=i; if(i_max!=n-1)//交换x[i_max]和x[n-1]的值

{inttemp=x[n-1];

x[n-1]=x[i_max];

x[i_max]=temp;} n--;

}

return;}

constintN=20;intmain(){inta[N];for(inti=0;i<N;i++)cin>>a[i];sort(a,N);//调用sort对a的元素进行排序for(inti=0;i<N;i++)cout<<a[i];}注意：调用完sort之后，a的值变了！这属于函数的副作用，但它是我们需要的。字符串的一种实现－－一维字符数组C++语言本身没有提供字符串类型。在C++中，通常用元素类型为char的一维数组（字符数组）来表示字符串类型。例如：chars[10];//s为一个字符串类型的变量在定义一个存储字符串的字符数组时，其元素个数应比它能够存储的字符串的最大长度多一个：因为通常要在字符串中最后一个字符的后面放置一个表示字符串结束的字符：'\0'。例如：chars[10];//可表示长度为9的字符串字符数组的初始化字符数组的初始化可以采用下面的形式：chars[10]={'h','e','l','l','o','\0'};chars[10]={"hello"};chars[10]="hello";chars[]="hello";在上面的字符数组初始化中，除了第一种形式，其它形式的初始化都会在最后一个字符的后面自动加上'\0'，而对于第一种形式，程序中必须显式地加上'\0'。字符串的操作一维数组的所有操作都可以用于字符串。字符串可以整体进行输入/输出。例：从键盘输入一个字符串，把其中的大写字母转成小写字母，然后输出这个字符串#include<iostream>#include<iomanip>usingnamespacestd;intmain(){chara[10];cin>>a;//输入一个字符串，末尾会自动加上'\0'

cin>>setw(10)>>a;//最多在a中存储9个字符 for(inti=0;a[i]!='\0';i++)

if(a[i]>='A'&&a[i]<='Z')

a[i]=a[i]-'A'+'a';cout<<a<<endl;//输出a中的字符串

return0;}因为空白符是用于分隔输入数据的，因此用cin和>>无法输入带空格的字符串。解决办法是：chars[10];cin.getline(s,10);//输入以回车结束， //最多存储9个字符，最后加上一个'\0'字符串作为函数参数字符串作为函数参数传递时，只要给出一维字符数组这一个参数就够了，不需要给出元素个数（字符串长度）。例如：intstrlen(charstr[]){inti=0;

while(str[i]!='\0')i++; returni;}......cout<<strlen("abcdef");//输出6例：编写一个函数把一个由数字构成的字符串转换成一个整型数算法："1234"-->((1*10+2)*10+3)*10+4=1234程序：intstr_to_int(charstr[]){if(str[0]=='\0')return0; intn=str[0]-'0';//把字符表示的数字转成数值：'1'->1 for(inti=1;str[i]!='\0';i++) n=n*10+(str[i]-'0'); returnn;}......inti=str_to_int("1234");更精炼的版本intstr_to_int(charstr[]){intn=0; for(inti=0;str[i]!='\0';i++) n=n*10+(str[i]-'0'); returnn;}用cin输入整型数时会自动进行转换：intn;cin>>n;//该操作会把键盘输入从字符串转成intcharstr[10];cin>>str;//该操作不需要转换算法2："1234"-->4+3*10+2*100+1*1000=1234程序：intstr_to_int(charstr[]){intn=0;for(inti=strlen(str)-1,b=1;i>=0;i--,b*=10)

n+=(str[i]-'0')*b;returnn;}例：编写一个函数，在一个字符串（主串）中查找子串，如果找到，返回子串在主串中的位置，否则返回-1。主串：子串：a1xabcdy34dhssdabcd(长度：len)(长度：sub_len)0......i......len-sub_len0...j...sub_len-1算法：程序intstrlen(charstr[]);//计算字符串长度的函数intfind_substr(charstr[],charsub_str[]){intlen=strlen(str),//主串长度

sub_len=strlen(sub_str);//子串的长度for(inti=0;i<=len-sub_len;i++)//从主串的头开始

//循环查找子串{intj;//字串的下标

for(j=0;j<sub_len;j++)//子串中的字符与主串中从位置i

//开始的字符逐个进行比较if(sub_str[j]!=str[i+j])break;if(j==sub_len)returni;//匹配到子串，返回它

//在主串中的位置i

}

return-1;//未找到子串，返回-1}标准库中的字符串处理函数（头文件cstring或string.h）计算字符串的长度unsignedintstrlen(constchars[]);字符串复制把src中的字符串复制到dst中，最后加一个'\0'。 char*strcpy(chardst[],constcharsrc[]);把src中的字符串复制到dst中，最多复制n个字符。复制的字符个数少于n时会自动在最后加一个'\0'，否则不加！ char*strncpy(chardst[],constcharsrc[],intn);字符串拼接把src中的字符串拼接到dst中已有字符串的后面，最后加上'\0'。 char*strcat(chardst[],constcharsrc[]);把src中的字符串拼接到dst中已有字符串的后面，最多拼接n个字符。拼接的字符个数少于n时会自动在最后加一个'\0'，否则不加！ char*strncat(chardst[],constcharsrc[],intn);字符串比较比较两个字符串的大小（按字典次序），返回值：0：相等；负数：s1小；正数：s1大 intstrcmp(constchars1[],constchars2[]);比较两个字符串的大小，最多比较n个字符。intstrncmp(constchars1[],constchars2[],intn);cout<<strlen("1234");//4charstr[5];strcpy(str,"1234");//str[4]='\0';strcpy(str,"12345");//error!

str[5]='\0';strncpy(str,"1234",5);//str[4]='\0';strncpy(str,"12345",5);//str最后没'\0'strcpy(str,"12");//使得str有2个字符cout<<str;//12strcat(str,"ab");cout<<str;//12abstrcpy(str,"12");strcat(str,"abc");//error!

str[5]='\0';strcpy(str,"12");strncat(str,"ab",3);//str[4]='\0';strcpy(str,"12");strncat(str,"abc",3);//str最后没'\0'实数的精确表示C++中的float、double、longdouble类型不能精确表示一些实数，如0.1（十进制）！如何在C++中精确表示实数？十进制数的另一种二进制表示－－BCD码BCD（BinaryCodedDecimal）码是分别对十进制数的每一位用二进制码来表示。BCD码有多种形式，常用的是8421码，每一位十进数用4位二进制表示，不允许出现1010～1111六种组合。0 0000 4 0100 810001 0001 5 0101 910012 0010 6 0110

10000100003 0011 7 0111 123000100100011小数点和正负号可以采用其它策略来表示，例如，用1010表示正号，用1011表示负号，1111表示小数点，则，-123.4可表示成：10110001001000111111

0100BCD码的优点：能用二进制来精确地表示十进制小数。长度不固定，能表示较长的十进制数。BCD码的不足之处：CPU指令一般不能对BCD码表示的数直接进行运算，它们需要通过一段程序来完成。在程序中，十进制数的BCD码表示可用一维字符数组来实现，但算术运算要自己实现：bcd_add(charn1[],charn2[],charn[]);bcd_subtract(charn1[],charn2[],charn[]);......为了节省空间，可采用压缩形式存贮BCD码：用一个字符（字节）表示二个BCD码。二维数组二维数组通常用于表示由固定多个同类型的具有行、列结构的数据所构成的复合数据，如：矩阵棋盘迷宫......二维数组所表示的是一种具有两维结构的数据，第一维称为二维数组的行，第二维称为二维数组的列。二维数组的每个元素由其所在的行和列唯一确定。二维数组类型定义二维数组类型定义格式：

typedef<元素类型><二维数组类型名>[<行数>][<列数>];<元素类型>为任意C++类型（void除外）<行数>和<列数>为整型常量表达式例如：typedefintA[10][5];//由10行、5列int型元素

//所构成的二维数组类型二维数组类型变量的定义二维数组类型变量的定义格式：<二维数组类型名><二维数组变量名>;或<元素类型><二维数组变量名>[<行数>][<列数>];或<一维数组类型名><二维数组变量名>[<元素个数>];<元素类型>为任意C++类型（void除外）<行数>、<列数>和<元素个数>为整型常量表达式例如，下面定义了一个二维数组a：（下面3个a等价！）typedefintA[10][5];Aa;或inta[10][5];或typedefintB[5];Ba[10];//a是10个元素构成的一维数组，

//但每个元素又是一个一维数组。 //这里，a语法上是一维数组，

//实际上是一个二维数组二维数组的初始化inta[2][3]={{1,2,3},{4,5,6}};inta[2][3]={1,2,3,4,5,6};//以上初始化按照数组的行依次来进行inta[2][3]={1,2,3,4};//第一行初始化为1、2、3，第二行初始化为4、0、0

inta[2][3]={{1,2},{3,4}};//第一行初始化为1、2、0，第二行初始化为3、4、0inta[][3]={{1,2,3},{4,5,6},{7,8,9}};//行数为3二维数组的操作访问二维数组元素，格式是：<二维数组变量名>[<下标1>][<下标2>]

<下标1>和<下标2>为整型表达式，均从0开始。例如：inta[10][5];a[0][0]、a[0][1]、...、a[9][0]、...、a[9][4]访问二维数组的行（只要一个下标）。例如：inta[10][5];a[0]、a[1]、...、a[9]上面每一个都为一个一维数组，代表二维数组中的一行对二维数组的操作通常是通过其元素来进行。例如：inta[10][5],sum=0;......//计算所有元素的和for(inti=0;i<10;i++) for(intj=0;j<5;j++) sum+=a[i][j];例：从键盘输入一个N×N的矩阵，把它转置后输出11111222223333344444555551234512345123451234512345x11112x22233x33444x45555x以主对角线为对称轴交换对称位置上的元素：(i,j)<-->(j,i)算法：程序如下：#include<iostream>usingnamespacestd;intmain(){ constintN=3; inta[N][N]; inti,j;//用于表示行、列的下标 //输入矩阵数据

cout<<"请输入"<<N<<"×"<<N<<"矩阵：\n"; for(i=0;i<N;i++) for(j=0;j<N;j++) cin>>a[i][j]; //矩阵转置：交换a[i][j]和a[j][i]的值，i=0~N-1，j=i+1~N-1 for(i=0;i<N;i++) for(j=i+1;j<N;j++) { //交换a[i][j]与a[j][i]的值

inttemp=a[i][j]; a[i][j]=a[j][i]; a[j][i]=temp;

} //输出转置后的矩阵

cout<< "转置后为：\n"; for(i=0;i<N;i++) { for(j=0;j<N;j++) cout<<a[i][j]<<''; cout<<endl; } return0;}xxxxx

xxxx

xxx

xx

x二维数组的存贮在C++中，二维数组元素是按照行的次序存储在连续的内存空间中，即先是第一行的元素；再是第二行的元素；...。例如：inta[10][5];其内存空间分配如下：二维数组所占的内存空间大小可以用sizeof操作符来计算。例如：cout<<sizeof(a);//输出数组a所占的内存字节数。a[i][j]的地址计算：a的首地址+i*5+ja[0][0]...a[0][4]a[1][0]...a[1][4]......a[9][0]...a[9][4]了解二维数组的存储方式，在某些情况下有利于设计出高效的程序。例如，对于一个很大的按行存储的二维数组a（M行、N列），下面按列来访问数组元素的程序效率可能会不高：（为什么？）按行访问for(intlin=0;lin<M;lin++) for(intcol=0;col<N;col++) ...a[lin][col]...按列访问for(intcol=0;col<N;col++) for(intlin=0;lin<M;lin++) ...a[lin][col]...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx另外，有些语言（如FORTRAN）中的二维数组是按列来存储的。在混合语言编程中，如果一个二维数组被各种语言的程序片段所共享，那么就必须给出专门的处理，否则会产生错误的结果。向函数传递二维数组被调用函数的形参应为不带数组行数的二维数组定义（列数为常量）及其行数。例如：intsum(intx[][5],intlin)//对lin行、5列的二维数组求和{ ints=0; for(inti=0;i<lin;i++) for(intj=0;j<5;j++) s+=x[i][j]; returns;}注意：作为形参的二维数组，列数必须要写！因为，二维数组作为函数参数传递时实际传递的是数组的首地址，函数中x[i][j]的地址则是按下面公式计算的：x[i][j]的地址=x的首地址+i×列数

+j调用者需要提供一个二维数组变量（列数要与形参相同）和行数。例如：intsum(intx[][5],intlin);......inta[10][5],b[20][5];......cout<<"a的元素之和为："<<sum(a,10)<<endl;cout<<"b的元素之和为："<<sum(b,20)<<endl;下面的二维数组c就不能调用函数sum来计算其元素的和，因为c的列数与函数sum要求的列数不符：intc[40][20];......sum(c,40);//Error二维数组降为一维数组处理intsum(intx[],intnum)//一维数组元素求和函数{ ints=0; for(inti=0;i<num;i++)s+=x[i]; returns;}......inta[10][5],b[20][5],c[40][20];......//把二维数组的第一行传给函数sum，//元素个数为二维数组的所有元素的个数cout<<sum(a[0],10*5)<<endl;cout<<sum(b[0],20*5)<<endl;cout<<sum(c[0],40*20)<<endl;结构类型结构类型用于表示由固定多个类型可以不同的元素（称为成员或属性）所构成的复合数据，它是一种用户自定义类型。例如，一个学生数据由以下成员构成：学号姓名性别...结构成员之间在逻辑上没有先后次序关系。结构类型的定义结构类型定义格式：struct<结构类型名>{<成员表>};<成员表>列出结构类型的成员及其类型。成员类型可以是任意的C++类型（void和本结构类型除外）。成员的说明次序会影响成员的存储安排。例如，下面的Student和Date就是结构类型：structStudent{ intno; charname[20];

Sexsex;

Datebirth_date; charbirth_place[40]; Majormajor;};enumSex{MALE,FEMALE};structDate{intyear,month,day;};enumMajor{MATHEMATICS,PHYSICS,CHEMISTRY,COMPUTER,GEOGRAPHY,ASTRONOMY,ENGLISH,CHINESE,PHILOSOPHY};结构类型变量的定义结构类型变量的定义格式如下：<结构类型名><结构类型变量名>;

struct<结构类型名><结构类型变量名>;

struct<结构类型名>{<成员表>}<结构类型变量名>;struct

{<成员表>}<结构类型变量名>;上述第三、四种格式是把结构类型和变量同时定义。例如：Studentst;//C++的写法structStudentst;//C语言的写法structStudent{......}st;struct{......}st;结构类型变量的初始化在定义结构类型的变量时，可依次给出成员的初始化值。例如：Studentsome_student={2,"李四",FEMALE,{1970,12,20},"北京",MATHEMATICS};注意：在定义一个结构类型时，不能对其成员进行初始化。例如：structA{inti=1;//Errordoubled=1.2;//Error};因为类型一般不是运行时刻的实体，运行时它们没有内存空间！结构类型的操作访问结构的成员访问结构的成员要用结构变量名来“受限”（通过操作符“.”来实现）：<结构类型变量>.<结构成员名>例如：Studentst;...st.no

....//访问结构类型变量st的成员no...

...//访问结构类型变量st的成员name......每个结构成员都可以看作是一个独立的变量，可以分别操作它们，例如：st.no=1;//把st的成员no赋值为1strcpy(,"张三");//把st的成员name赋值为"张三"......结构赋值可以对相同结构类型的数据进行整体赋值，例如：Studentst1,st2;st1=st2;//OK不同的结构类型之间不能相互赋值，例如：Studentst;Datetoday;st=today;//Error

结构类型的存储结构类型的变量在内存中占用一块连续的存储空间，其各个成员按它们在结构类型中的定义次序存储在这块内存空间中。例如：Studentst;其内存空间安排如下：st.nost.sexst.birth_datest.birth_placest.major可用sizeof计算结构类型的大小。例如，cout<<sizeof(st);//输出结构st所占的内存字节数。虽然内存是以字节为单位编址的，但cpu往往以“字”为单位访问内存（因为cpu内的寄存器存的是一个字），并且，cpu访问内存的地址往往是“字长”的倍数。例如，在32位的计算机上，“字”为32位（占4个字节）：cpu每次到内存至少取4个字节。cpu访问内存的地址往往是4的倍数。如果一个4字节的数据没有存储在4的倍数的地址处，则cpu要访问内存2次才能得到这个数据。结构的内存地址对齐在C++实现中，为了提高cpu对整个结构以及某些成员的访问效率，在为结构类型的变量分配内存空间时，往往要对整个结构以及某些结构成员所占的空间按某种方式（编译时可以指定）进行地址对齐。例如，下面的结构按4个字节进行地址对齐：structA//对齐到地址为4的倍数的边界上{charch1; inti1;//对齐到地址为4的倍数的边界上

charch2;inti2;//对齐到地址为4的倍数的边界上}a;cout<<sizeof(a);//16，假设char占1个字节，int占4个字节因此，结构成员的内存空间之间可能会存在“空隙”，使得整个结构类型数据的内存空间大于各个成员的内存空间之和。怎么处置这个问题！向函数传递结构数据结构可作为参数传给函数，默认参数传递方式为值传递，例如：voidf(Studentst){......}......Studentst1;......f(st1);结构可作为函数返回值返回给调用者，例如：Studentg(){Studentst;......returnst;}......Studentst1=g();结构与数组的结合

--名表（Name-Table）名表是指一系列由“名字”及其相关信息所构成的表格，可以通过某个“名字”获得相关的信息。这里的“名字”称为关键词。例如，下面的学生信息表就是个名表：可以通过关键词姓名“李四”或学号20160002查到与之相关的信息：李四，20160002，女，......对名表可以做各种统计操作，如男生有多少、...namenosexbirth_date......张三20160001男...李四20160002女...王五20160003男...:名表的表示名表可以用一个一维数组来表示，数组的每个元素是一个结构类型，它表示表中的一行。例如，下面定义了一个通用的名表name_table：constintMAX_NAME_LEN=20;structTableItem//表中行的数据类型{charname[MAX_NAME_LEN];

intno;......//其它信息};

constintMAX_TABLE_LEN=100;TableItemname_table[MAX_TABLE_LEN];//整个名表数据名表数据的输入/输出intn;//名表元素的个数（行数）cin>>n;if(n>MAX_TABLE_LEN)exit(-1);for(inti=0;i<n;i++)//依次输入名表中的每一行数据{cin>>setw(MAX_NAME_LEN)>>name_table[i].name;

cin>>name_table[i].no;......}......for(inti=0;i<n;i++)//按行输出名表数据{cout<<name_table[i].name<<'';

cout<<name_table[i].no<<'';......

cout<<endl;}名表数据的统计把前面的名表的元素类型TableItem换成Student，它就成了一个学生信息表，可以对它做一些有意义的操作。统计表中“男生”的人数intcount=0;for(inti=0;i<n;i++)

if(name_table[i].sex==MALE)count++;cout<<"男生的人数是："<<count<<endl;统计表中“北京”籍的人数intcount=0;for(inti=0;i<n;i++)

if(find_substr(name_table[i].birth_place,"北京")!=-1)

count++;cout<<"北京籍的人数是："<<count<<endl;把表中数据按学号排序，并输出排序后的表数据......名表的查找（检索）名表查找：根据某个关键词在名表中查找与该关键词相关的信息。名表查找通常采用下面两种方法：顺序查找折半查找（二分法）名表查找（顺序）从表的第一行开始逐行比较//下面的函数按“姓名”在表中进行检索intlinear_search(charkey[],//待搜索的关键词（姓名）

TableItemt[],//名表

intnum_of_items)//表的长度{ for(intindex=0;index<num_of_items;index++) if(strcmp(key,t[index].name)==0)returnindex; return-1;}......TableItemname_table[MAX_TABLE_LEN];intmain(){intn;//存储名表元素的个数（长度）

......//获取名表name_table的数据，包括元素个数n

charname[MAX_NAME_LEN];//存储待查找的姓名

cin>>setw(MAX_NAME_LEN)>>name;//获取待查找的姓名

intresult=linear_search(name,name_table,n); if(result==-1){cout<<"Notfound！\n";return-1;}......//输出name_table[result]各成员的信息

return0;}名表查找（二分法）如果名表的元素（行）已经按某个关键词（如姓名）排了序，则可以采用二分法（折半）查找：用要查找的值与名表中间位置上的元素与进行比较：若相等，则找到；若大于中间位置上的元素，则在名表的后半部分中继续进行查找；若小于中间位置上的元素，则在名表的前半部分中继续进行查找。在前半部分或后半部分中查找时，仍然采用二分法查找策略，直到找到或表中元素都比较完为止。intbinary_search(charkey[],TableItemt[],

intnum_of_items){ intfirst,last; first=0; last=num_of_items-1; while(first<=last) { intmiddle=(first+last)/2; intr=strcmp(key,t[middle].name); if(r==0)//key等于t[middle].name returnmiddle; elseif(r>0)//key大于t[middle].name first=middle+1; else//key小于t[middle].name last=middle-1; } return-1;}算法分析顺序查找最好情况：比较1次最坏情况：比较N次平均情况：(1+2+...+N)/N=(N+1)/2次二分法查找最好情况：比较1次最坏情况：比较log2(N+1)次（取上整）平均情况：log2(N+1)-1次137152485691011121413N：4~7，log2(N+1)：2.x~3，上整：3联合（union）类型如何表示一组图形数据？图形可以是：线段、矩形、圆等：structLine//线段{ doublex1,y1,x2,y2;};structRectangle//矩形{ doubleleft,top,right,bottom;};structCircle//圆{ doublex,y,r;};？figures[100];//100个图形，元素类型怎么定义？联合类型：用一个类型表示多种类型的数据。语法上，联合类型与结构类型类型类似，只是用union替换了struct。语义上，联合类型的成员是互斥的，不能同时使用！例如，下面的A就是联合类型，它既可以表示int类型的数据，也可以表示char或double类型的数据：union

A//A为联合类型{inti;charc;doubled;};对于一个联合类型的变量：在程序中可把它作为不同的类型来使用。要给它赋上某类型的值，需要通过相应的成员来实现。例如：unionA{inti;charc;doubled;};Aa;//a是一个联合类型的变量//把a当作int型来用a.i=1;//要通过成员i来给变量a赋一个int型的值...a.i...//要通过成员i取a的值//把a当作char型来用a.c='A';//要通过成员c来给变量a赋一个char型的值...a.c...//要通过成员c取a的值//把a当作double型来用a.d=2.0;//要通过成员d给变量a赋一个double型的值...a.d...//要通过成员d取a的值当给一个联合类型的变量赋了一个某种类型的值之后，如果以另外一种类型来使用这个值，将得不到原来的值。例如：a.i=12;cout<<a.d;//输出什么呢？实际上，联合类型的所有成员共享同一块内存空间，该内存空间的大小为其最大成员所需要的内存空间的大小。例如，下面联合类型变量a的成员i、c和d占有同一块内存空间：unionA{inti;charc;doubled;};Aa;cout<<sizeof(a);//输出：8（假设double占8个字节）例：从键盘输入一组图形数据，然后输出相应的图形。其中的图形可以是：线段、矩形和圆。图形数据的表示一组图形数据可用一个一维数组表示：constintMAX_NUM_OF_FIGURES=100;Figurefigures[MAX_NUM_OF_FIGURES];数组元素的类型Figure是什么？structLine{ doublex1,y1,x2,y2;};structRectangle{ doubleleft,top,right,bottom;};structCircle{ doublex,y,r;};union

Figure//可以表示Line、Rectangle或Circle类型的数据{ Lineline; Rectanglerect; Circlecircle;};Figurefigures[MAX_NUM_OF_FIGURES];解决方案一（不可行）在一个数组元素figures[i]中存储一个图形时，可以通过figures[i].line、figures[i].rect或figures[i].circle来进行。例如，在数组元素figures[0]中存储一个线段：

figures[0].line.x1=10;

figures[0].line.y1=20;

figures[0].line.x2=100;

figures[0].line.y2=200;再例如，在数组元素figures[1]中存储一个矩形：

figures[1].rect