《CC++程序设计》课件-第3章 构造类型

C/C++程序设计

（第三版）第3章构造类型

主要内容3.1数组类型3.2结构类型3.3联合类型和枚举类型3.4文件类型

3.1数组类型数组（array）是由类型相同、内容相关的一组成员组成每个成员是数组的一个元素（element）元素按照一定的顺序排列元素具有相同的名、不同的下标（subscript）元素类型可以是基本类型（整型、实型、字符型）也可以是构造类型（结构、数组、联合等类型）元素类型为整型的数组称整型数组类似的，有实型数组、字符数组、结构数组3.1.1一维数组

定义数组时，要指定名字，长度（元素个数）和元素类型一维数组（one-dimensionalarray）定义格式：

类型说明数组名[E];

元素类型数组名：标识符E：下标界指定数组元素个数整型常量表达式预定义符号常量[]：下标运算符例inta[10];floatb[20],c[2*30];又例#defineN80constintM=12;charch,c[N],d[N+1];inta[M];一维数组元素的引用格式

数组不能整体进行输入输出（一维字符数组除外）更不能直接参与运算以数组元素为单位参与运算（相当于普通变量）一维数组元素引用格如：数组名[E]E是一个下标表达式（Subscriptexpression）E的值是元素的下标，只能是整型表达式（整型常量、变量、带有运算的真表达式）若数组长度为n，下标表达式的值在0~n-1之间例#defineN10inti,a[N];

数组a的元素：a[0],a[1],a[2],…,a[N-1]

数组的存储方式（连续存储）注意事项：1）数组的长度在定义前确定例：

intn;scanf("%d",&n);inta[n];//错误（定义时n的值尚未确定）2）数组名代表数组的首地址（首元素地址）数组名是“符号常量”，其值不能被修改3）数组长度只能是整型，下标从0开始不能超界另外，下标运算符是[]，不是（）

数组的输入/输出for(i=0;i<N;i++)scanf("%d",&a[i]);由于长度为N的数组a，不存在元素a[N]设N=10，元素a[i]下标i的值必须为0到9之一否则（i<0或i>9）就会出现“下标越界”错误一旦发生越界时，便可能产生意想不到的后果使用C++中cin输入（不能带&）for(i=0;i<N;i++)cin>>a[i];//需要头文件iostream.h例3-1输入N个整数，输出其中最大数和最小数（它们共占一行），然后再输出其余各数算法设计思想和描述注意：找到并输出最大数和最小数，再输出其余各数第1步，将N个数输入到数组a[N]中（若要不将读入的数“被忘记”，这是必须的）第2步，在数组a中找到最大、最小元素第3步，输出最大、最小元素第4步，输出除最大、最小元素以外的其余各元素例3-1输入N个整数，输出其中最大数和最小数（它们共占一行），然后再输出其余各数#include<stdio.h>#defineN10voidmain(){inti,max,min,a[N];printf("请输入%d个数据:\n",N);for(i=0;i<N;i++)scanf(“%d”,&a[i]);//读到数组中//程序的主体部分，见下一页！例3-1输入N个整数，输出其中最大数和最小数（它们共占一行），然后再输出其余各数//以下是找最大最小元素值的程序段

max=min=a[0]; //将a[0]定为最大最小值的初值

for(i=1;i<N;i++)if(a[i]>max)max=a[i];//记住最大元素的值

elseif(a[i]<min)min=a[i]; //记住最小元素的值//以下是输出数据程序段

printf("最大数=%d最小数=%d\n",max,min);for(i=0;i<N;i++) //输出其余各数

if(a[i]!=max&&a[i]!=min) //跳过最大值和最小值

printf("%6d",a[i]);printf("\n"); //最后输出一个换行符}例3-1输入N个整数，输出其中最大数和最小数（它们共占一行），然后再输出其余各数//改为记住最大最小元素下标的方法：//找最大最小元素的程序段

max=min=0; //0作为最大最小元素所在下标的初值

for(i=1;i<N;i++)if(a[i]>a[max])max=i; //记住最大元素所在的下标

elseif(a[i]<a[min])min=i; //记住最大元素所在的下标

//输出程序段printf("最大数为：a[%d]=%d，最小数为：a[%d]=%d\n",max,a[max],min,a[min]);printf("最大数是=%d最小数=%d\n",max,min);for(i=0;i<N;i++) //输出其余各数

if(i!=max&&i!=min)//跳过下标为max和min的元素

printf("%6d",a[i]);例3-1输入N个整数，输出其中最大数和最小数（它们共占一行），然后再输出其余各数记住最大最小元素值的方法与记住最大最小元素所在下标的方法输出结果可能不同！一维数组元素的初始化

定义数组的同时，给数组元素赋初值一般格式：类型说明数组名[E]={E1，E2，…}

E1，E2等都是常量表达式例：

inta[4]={1,2,3,4};结果：a[0]=1，a[1]=2，a[2]=3，a[3]=4初始化的有关规定：1）给定的初值个数可以小于或等于数组长度，但不能大于数组长度（若大于，编译时报错）2）如果初值个数小于数组长度，则依次为数组前段元素赋初值，没有对应初值的后段元素自动置为0（对于整型或实型数组）或'\0'（对于字符型数组）例如：inta[6]={1,2,3};相当于inta[6]={1,2,3,0,0,0};charb[6]={'C','W','W'};相当于charb[6]={'C','W','W','\0','\0','\0'};初始化的有关规定：3）如果每个元素都赋初值，可以不指定数组长度其长度由用户给定的常量表达式序列中的数据个数确定例如：inta[]={1,2,3,4};等价于

inta[4]={1,2,3,4};另外，不能用带系数的方法，使多个元素获得相同初值例：

inta[4]={4*12};等价于：inta[4]={48};//或inta[4]={48,0,0,0};不等价于：inta[4]={12,12,12,12};例3-2输入一串字符（以'\n'结束），统计其中大写字母A，B，C，…，Z各出现多少次

附加输出要求：只输出那些至少出现一次的字母（每4个字母占一行）并输出26个大写字母中共出现过多少个（或都没出现过）的信息程序设计方法：用数组count[26]计数各字母出现的次数count[0]表示字母A出现的次数

……count[25]表示字母Z出现的次数例3-2输入一串字符（以'\n'结束），统计其中大写字母A，B，C，…，Z各出现多少次

#include<stdio.h>#include<ctype.h>#defineLINE4voidmain(){inti,k,t,count[26]={0};//数组count各元素清0charch;printf("请输入字符串\n");while((ch=getchar())!='\n')//输入字符串，遇换行符结束

if(isupper(ch))count[ch-'A']++;//统计各大写字母出现次数

//以下是输出数据部分，t用于统计出现过的大写字母个数

例3-2输入一串字符（以'\n'结束），统计其中大写字母A，B，C，…，Z各出现多少次

//以下是输出数据部分，t用于统计出现过的大写字母个数

for(t=0,i=0;i<26;i++)//考查每个大写字母

{k=count[i];if(!k)continue; //跳过出现次数为0的字母

printf("字母%c:出现%-2d次",i+'A',k);if(++t%LINE==0)printf("\n"); //够4个字母，则换行

}printf("\n");if(!t)printf("26个大写字母都没出现过！\n");elseprintf("共出现过%d个大写字母。\n",t);}3.1.2

二维数组

用于描述矩阵等具有行列结构的数据

一般定义格式

类型名数组名[E1][E2]E1和E2：整型常量表达式指明数组的行数和列数

E1行，E2列，共E1×E2个元素例：

inta[3][4];a：3行4列，共12个元素（整型数组）3.1.2

二维数组二维数组元素引用方式

元素的格式数组名[行下标E1][列下标E2]E1和E2都从0开始例，inta[3][4]的元素第一行：a[0][0]，a[0][1]，a[0][2]，a[0][3]第二行：a[1][0]，a[1][1]，a[1][2]，a[1][3]第三行：a[2][0]，a[2][1]，a[2][2]，a[2][3]注意，没有a[3][4]，也没有a[3][0]、a[0][4]等元素每一行是一个“行元素”（一维数组）a的三个行元素：a[0]，a[1]和a[2]第一个元素a[0]：a[0][0]，a[0][1]，a[0][2]，a[0][3]第二个元素a[1]：a[1][0]，a[1][1]，a[1][2]，a[1][3]第三个元素a[2]：a[2][0]，a[2][1]，a[2][2]，a[2][3]二维数组名：存储单元的首地址（首元素地址）数组名a（的值）等于元素a[0][0]的地址，也等于行元素a[0]的地址采用按行顺序的存储方式先存储第一行元素，再存储第二行元素，

……每行元素按列号依次存储例：二维数组a[3][4]的存储形式常用输入输出方法例如，为inta[M][N]输入数据（程序段）

for(i=0;i<M;i++)for(j=0;j<N;j++)scanf("%d",&a[i][j]);

先输入第一行数据，再输入第二行数据…输出成行列结构：

for(i=0;i<M;i++){for(j=0;j<N;j++)printf(“%4d”,a[i][j]);printf(“\n”);//每输入完一行元素，换行

}例3-3求M×N的矩阵最大元和最小元所在的行列号输出要求：先原样输出这个矩阵再输出最大最小元所在的行列号和元素值#include<stdio.h>#defineM3#defineN4voidmain(){inti,j,maxi,maxj,mini,minj,a[M][N];

//maxi,maxj,mini,minj分别用来记录最大最小元素的行列号

//输入矩阵元素的程序段

printf("请输入%d个矩阵元素\n",M*N);for(i=0;i<M;i++)for(j=0;j<N;j++)scanf("%d",&a[i][j]);例3-3求M×N的矩阵最大元和最小元所在的行列号//找最大最小元素所在下标的程序段

maxi=maxj=mini=minj=0; //最大最小元素行列号初值

for(i=0;i<M;i++)for(j=0;j<N;j++){if(a[i][j]>a[maxi][maxj])maxi=i,maxj=j;//最大元素行列号

if(a[i][j]<a[mini][minj])mini=i,minj=j; //最小元素行列号

}

例3-3求M×N的矩阵最大元和最小元所在的行列号//输出矩阵元素的程序段

printf("你输入的矩阵为:\n");for(i=0;i<M;i++){for(j=0;j<N;j++)printf("%6d",a[i][j]);printf("\n");}

//输出最大最小元素的程序段

printf("最大元素:a[%d,%d]=%d\n",maxi,maxj,a[maxi][maxj]);//输出最大元素

printf("最小元素:a[%d,%d]=%d\n",mini,minj,a[mini][minj]);//输出最小元素}二维数组元素的初始化

多种方法：1）以行为单位（比较直观）例inta[3][2]={{1,2},{3,4},{5,6}};2）只为部分元素赋初值例

inta[3][2]={{1},{3,4},{5}};3）初值不分行（放在一对花括号中）例inta[3][2]={1,2,3,4,5,6};4）所有元素都赋初值时，可不指定行数，只指定列数，行数根据初值个数确定例

inta[][2]={1,2,3,4,5,6};同inta[3][2]={1,2,3,4,5,6}注意：必须指定列数二维数组元素的初始化

推广：多维数组的一般定义格式：

类型说明数组名[E1][E2][E3]…[En]；E1，E2，E3，En是各维的长度（下标界）均是整型常量表达式二维以上的高维数组很少用到3.1.3字符数组

继承普通数组所有操作方法（定义、引用）一维字符数组有特殊输入输出和初始化方法chara[10];//下面以此为例1．初始化方式1）像普通数组那样逐个元素初始化，不足部分填补'\0‘

若给定的初值个数大于数组长度，则出错例如：

chara[10]={'N','a','n','','J','i','n','g'};chara[10];//以此为例1．初始化方式定义长度比实际字符个数至少多1（用于存储结束符）串的有效长度称为串长

2）整体初始化，可以不指定数组长度例如：

chara[]={"Howdoyoudo?"};或

chara[]="Howdoyoudo?";系统取初值串长加1作为数组的定义长度自动在串尾加'\0'chara[10];//以此为例2．输入方式1）逐个字符输入，例如：for(i=0;i<n;i++)a[i]=getchar();或for(i=0;i<n;i++)scanf("%c",&a[i]);这种方式下，输入的字符可以是任意字符包括空格符、〈Tab〉符和换行符系统不会自动在串尾添加'\0'chara[10];//以此为例2．输入方式2）多个字符一起输入，例如：

scanf("%7c",a);一次读入7个字符输入的字符可以是任意字符包括空格符、〈Tab〉符和换行符系统不会自动在串尾添加'\0'chara[10];//以此为例2．输入方式3）整串输入，系统自动在串尾添加'\0'，例如：scanf("%s",a); //方法一或gets(a); //方法二方法一，输入内容不能有空白符（空格、〈Tab〉符和换行符）遇到空白字符时，系统认为用户输入的串已经结束，其后的字符将不读到本串中方法二，输入内容可夹杂空格和〈Tab〉，以换行符作为输入结束标志chara[10];//以此为例3．输出方式1）逐个字符输出，例如：for(i=0;i<n;i++)putchar(a[i]);或for(i=0;i<n;i++)printf("%c",a[i]);2）整串输出，例如：printf("%s",a);

或puts(a);整串输出时，串尾必须含有‘\0’，遇第一个‘\0’时就结束输出若串尾不含'\0'，则继续输出串后内容，直至遇到'\0'为止

4．字符处理函数

#include<ctype.h> //使用ctype.h中的字符处理函数ch是字符表达式，满足测试条件将返回1，否则返回0

isalnum(ch)判断ch（即ch的值，下同）是不是字母或数字isalpha(ch)判断ch是不是字母islower(ch)判断ch是不是小写字母isupper(ch)判断ch是不是大写字母isdigit(ch)判断ch是不是数字（0~9）isxdigit(ch)判断ch是不是十六进制数字（0~9，A~F，或a~f）ispunct(ch)判断ch是不是标点符号（除空格、数字、字母外的可印刷字符）4．字符处理函数

#include<ctype.h> //使用ctype.h中的字符处理函数ch是字符表达式，满足测试条件将返回1，否则返回0

isspace(ch)判断ch是不是空白符（空格、〈Tab〉符、换行符）iscntrl(ch)判断ch是不是控制字符（ASCII码值在0~31之间）isgraph(ch) 判断ch是不是可显示字符（ASCII码值在33~126之间，即不含空格）isprint(ch)判断ch是不是可印刷字符（ASCII码值在32~126之间，含空格）4．字符处理函数

#include<ctype.h> //使用ctype.h中的字符处理函数ch是字符表达式，返回转换后的字母tolower(ch) 将ch（是大写字母）转换成对应的小写字母toupper(ch) 将ch（是小写字母）转换成对应的大写字母5．字符串处理函数

#include<string.h>//使用string.h中的字符串处理函数（1）求串长函数strlen()用法：strlen(str)；//str是字符数组名，或字符串常量返回值为字符串的有效长度（不包括串结束符'\0'）（2）串连接函数strcat()用法：strcat(str1，str2)；//str1是字符数组名

//str2是字符数组名或字符串常量将串str2内容连接到str1串后得到新串存于str1中函数返回值为str1的起始地址。连接时，str1尾部的'\0'将被去掉，但保留结果串的结束符'\0'5．字符串处理函数

#include<string.h>//使用string.h中的字符串处理函数（3）串复制函数strcpy()用法：strcpy(str1,str2)；str1是字符数组名str2是字符数组名或字符串常量将str2中的有效字符（即到第一个'\0'为止）复制到str1中5．字符串处理函数

#include<string.h>//使用string.h中的字符串处理函数（4）串比较函数strcmp()一般用法：k=strcmp(str1,str2);其中，k是一个整型变量str1和str2是字符数组名或字符串常量按“字典序”意义进行的串比较，返回值的含义：

k<0str1<str2k=0str1=str2k>0str1>str25．字符串处理函数

#include<string.h>//使用string.h中的字符串处理函数（5）子串匹配函数strstr()用法：strstr(str1,str2)；其中，str1和str2是字符数组或字符串常量在串str1中寻找串str2（不包括‘\0’）第一次出现的地址（即str2是str1的一个子串）若str1中没有子串与串str2相同，则返回空指针5．字符串处理函数

#include<string.h>//使用string.h中的字符串处理函数（5）子串匹配函数strstr()例如：

charc[]="BeiJingNanJing",d[]="Jing";调用函数：

strstr(c,d)；返回c[3]的地址，因为c[3]~c[6]的内容与d相同。语句：printf("%s",strstr(c,"Jing"));的输出结果为： JingNanJing例3-4判断输入的单词是不是Hello（区分大小写）#include<stdio.h>#include<string.h>voidmain(){charstr[10];printf("请输入单词:\n");gets(str);if(!strcmp(str,"Hello")) //返回值等于0表示两串相等

printf("ThiswordisHello!\n");elseprintf("ThiswordisnotHello!\n");}注：并不要求字符数组的最后元素一定是'\0'（最好加结束符'\0'）例3-5输入若干个字符串直到某字符串是一个回文串为止

回文串：正读与反读相同的字符串例如，回文串：上海自来水来自海上黄山落叶松叶落山黄1234321非回文串：1321算法的描述第1步，将一个字符串输入到字符数组a中第2步，测试字符串a是不是回文串第3步，若a不是回文串，输出必要的信息，转第1步第4步，若a是回文串，输出必要的信息，结束第2步是核心！

从两头向中间比较对应字符，若发现对应字符不同，则不是回文串；若所有对应字符都相等，则是回文串

第2步细化（测试a是不是回文串）第2-1步，求串长k第2-2步，置i=0，k=k-1（a[i]与a[k]对应）置“是回文串否”标记flag=1第2-3步，比较a[i]与a[k]

若不相等置flag=0（不是回文串）转第2-5步否则继续下一步第2-4步，i++，k--；若i<k（未比完）则转第2-3步否则（已比完）转第2-5步第2-5步，检查标记flag的值，若flag=0（不是回文串），执行第3步；否则（flag=1，是回文串），执行第4步例3-5输入若干个字符串直到某字符串是一个回文串为止

#include<stdio.h>#include<string.h>#defineN80 //假定字符串的长度限制voidmain(){chara[N];inti,k,flag;printf("请输入字符串：");

while(1)

//循环到发现回文串为止

{gets(a); //输入一个字符串

puts(a); //原样输出这个字符串

k=strlen(a); //求串长

例3-5输入若干个字符串直到某字符串是一个回文串为止

for(flag=1,i=0,k--;i<k;i++,k--)//测试回文串

if(a[i]!=a[k])//发现对应字符不等，则不是回文串

{flag=0;break;} //非正常退出for循环

//至此，for循环终止

if(flag){printf("得到一个回文串\n程序结束！\n");

break;

//退出外层while循环，终止程序的执行

}elseprintf("这不是一个回文串，请重新输入：\n");

//继续while(1)的下一轮循环

}}例3-5输入若干个字符串直到某字符串是一个回文串为止

例3-6将正整数n输出成“千分位”形式3.1.4程序设计示例例如，将9876543210输出成9,876,543,210程序设计方法先将n拆成一位一位的数字，放在数组digit中然后从高位向低位输出，并考虑输出逗号的时机#include<stdio.h>#defineBASE10 //基数定义为10，表示按十进制拆数voidmain(){unsignedlongn; //定义无符号长整型变量ninti,digit[10]; //假定n的位数不超过10printf("请输入正整数，不超过4294967295\n");scanf("%ld",&n); //输入n的值

printf(“%ld”,n); //原样输出n的值

例3-6将正整数n输出成“千分位”形式//拆数程序段

i=0; //i用于记录n的位数

while(n) //当n不为0时循环拆数

{digit[i++]=n%BASE;n/=BASE;}

//输出程序段

printf("===>"); //为格式美观而输出的记号

for(i--;i>0;i--)if(i%3==0)printf("%d,",digit[i]);//分位时输出数字和逗号

elseprintf("%d",digit[i]); //不分位时只输出数字

printf("%d\n",digit[0]); //输出最末位，并换行

}例3-6将正整数n输出成“千分位”形式#include<stdio.h>#defineBASE10 //基数定义，按BASE进制拆数voidmain(){unsignedlongn; //定义无符号长整型变量ninti,digit[10]; //假定n的位数不超过10printf("请输入正整数，不超过4294967295\n");scanf("%ld",&n); //输入n的值

printf(“%ld”,n); //原样输出n的值

例3-6将正整数n输出成“千分位”形式实际上完成数制转换将基数BASE为2、16、1000分别表示拆成二进制、十六进制和千进制只要修改输出程序段！

//拆数程序段

i=0; //i用于记录n的位数

while(n) //当n不为0时循环拆数

{digit[i++]=n%BASE;n/=BASE;}

//将BASE定义为1000输出程序段

printf("===>");

printf("%d",digit[i]); //首位采用%d输出格式

for(i--;i>=0;i--)printf(",%03d",digit[i]);

//其他位用,%03d输出格式（确保前导输出0）

printf("\n"); //最后换行

}例3-6将正整数n输出成“千分位”形式积矩阵元素cij（0≤i＜M，0≤j＜P）的计算公式：

例3-7编制计算两个矩阵乘积的通用程序。完成矩阵相乘的程序段：

for(i=0;i<M;++i)for(j=0;j<P;++j)for(c[i][j]=0,k=0;k<N;k++)c[i][j]+=a[i][k]*b[k][j];例3-7编制计算两个矩阵乘积的通用程序。#include<stdio.h>#defineM5#defineN4#defineP3voidmain(){inta[M][N],b[N][P],c[M][P],i,j,k;

//两个矩阵输入程序段

printf("请输入第一个矩阵a的%d个元素\n",M*N);for(i=0;i<M;++i)for(j=0;j<N;++j)scanf("%d",&a[i][j]);printf("请输入第二个矩阵b的%d个元素\n",N*P);例3-7编制计算两个矩阵乘积的通用程序。for(i=0;i<N;++i)for(j=0;j<P;++j)scanf("%d",&b[i][j]);

//矩阵相乘程序段

for(i=0;i<M;++i)for(j=0;j<P;++j)for(c[i][j]=0,k=0;k<N;k++)c[i][j]+=a[i][k]*b[k][j];//累加

//积矩阵输出程序段

printf("积矩阵c:\n");for(i=0;i<M;++i){for(j=0;j<P;++j)printf("%6d",c[i][j]);printf("\n");}}例3-8将a[N]的元素排列成由小到大形式（排序问题）算法设计思想和描述采用生动有趣的冒泡法（bubblesorting）基本原理：反复比较相邻元素a[i]和a[i+1]若a[i]>a[i+1]则交换小元素上升、大元素下降，像水中泛气泡需要多遍扫描上升法：扫描方向从下到上（最小元素上升到最顶端）下降法：扫描方向从上到下（最大元素下降到最底下）

for(j=0;j<N-1;j++) //外循环N-1遍，控制扫描终点

for(i=N-2;i>=j;i--) //内循环，控制比较对象

if(a[i]>a[i+1])x=a[i],a[i]=a[i+1],a[i+1]=x;//次序不对则交换例3-8冒泡排序算法上升法：扫描方向从下到上（最小元素升到最上面）扫描语句（第一遍j=0，第二遍j=1…）：

for(i=N-2;i>=j;i--)if(a[i]>a[i+1])交换a[i]与a[i+1]；上升法示例原数据1023456191523530288191523530

828191523583028191523

583028191552383028195152383028519152383028iiiiii无序区第一遍j=0

519152383028最小值上升法示例剩余的6个数据第二遍j=11023456519152383028519152382830519152382830519158232830519815232830581915232830iiiii无序区581915232830次小值例3-8冒泡排序算法（上升法的实现程序）#defineN8#include<stdio.h>voidmain(){inta[N],i,j,x;printf("请输入数组s的%d个元素:\n",N);for(i=0;i<N;++i)scanf("%d",&a[i]);printf("\n排序前的数据排列:\n");for(i=0;i<N;++i)printf("%6d",a[i]);printf("\n");

//以下是排序程序段

例3-8冒泡排序算法（上升法的实现程序）//以下是排序程序段

for(j=0;j<N-1;j++)for(i=N-2;i>=j;i--)if(a[i]>a[i+1])x=a[i],a[i]=a[i+1],a[i+1]=x;

//输出排序结果的程序段

printf("\n排好序后:\n");for(i=0;i<N;++i)printf("%6d",a[i]);printf("\n程序结束。\n");}例3-9随意输入N个正整数，按从小到大次序输出它们。算法设计思想和描述采用动态排序方法（有序插入原理）开始时，在数组inta[N+1]之a[0]存放0作为最小元素真正数据将从a[1]起存放，每读入新数x后，有序插入法将x插在有序位置上例如，当前元素（有序排列）：0，1，5，9，12现读入x=4，x将被插在1与5之间若当前有n个元素，读入第n+1个元素x的插入动作：

for(i=n;x<a[i];i--)a[i+1]=a[i];//自右向左查找有序位置

a[i+1]=x; //插入xn++;这就是算法的核心部分！例3-9随意输入N个正整数，按从小到大次序输出它们。#include<stdio.h>#defineN100voidmain(){inti,x,a[N],n=0;a[0]=0; //预置a[0]等于0便于控制有序插入

printf("请随意输入一批正数，0表示输入结束:\n");while(1) //外循环控制读数据

{scanf("%d",&x);if(!x)break;//读到结束标记0，则终止读数据

例3-9随意输入N个正整数，按从小到大次序输出它们。for(i=n;x<a[i];i--)a[i+1]=a[i];//自右向左查找有序位置

a[i+1]=x; //插入xn++; //数组有效长度增1}printf("共输入%d个数,从小到的次序是：\n",n);for(i=1;i<=n;i++)printf("%5d",a[i]);printf("\n程序结束\n");}例T3-1将a[N]中所有值为x的元素删去，其他元素向前移。

理解题意：原有10个元素：12，3，24，5，3，67，3，3，27，8删去3后：12，24，5，67，27，8算法设计思想和描述找到值为x的元素，用循环语句：

for(i=0;i<N;++i)if(a[i]==x)…;else…；用计数器k，记录等于x的元素个数

for(i=0,k=0;i<N;++i)if(a[i]==x)k++;else…；else（a[i]≠x）部分，a[i]向前移k位：

for(i=0,k=0;i<N;++i)if(a[i]==x)k++;elsea[i-k]=a[i];

例T3-1将a[N]中所有值为x的元素删去，其他元素向前移。#include<stdio.h>#defineN10voidmain(){inta[N],x,i,k;printf("请输入数组a的%d个元素:\n",N);for(i=0;i<N;++i)scanf("%d",&a[i]);printf("请输入要删除的元素值,x=");scanf("%d",&x);

for(i=0,k=0;i<N;++i)if(a[i]==x)k++;elsea[i-k]=a[i];printf("共删除了%d个元素,

剩下的%d个元素为:\n",k,N-k);for(i=0;i<N-k;++i)printf("%5d",a[i]);printf("\n程序结束\n");}此句可改成：for(i=0,k=0;i<N;++i)if(a[i]!=x)a[k++]=a[i];K用于记录不等于x的元素个数例T3-1将a[N]中所有值为x的元素删去，其他元素向前移。

#include<stdio.h>#defineN10voidmain(){inta[N],x,i,k;printf("请输入数组a的%d个元素:\n",N);for(i=0;i<N;++i)scanf("%d",&a[i]);printf("请输入要删除的元素值,x=");scanf("%d",&x);

for(i=0,k=0;i<N;++i)if(a[i]!=x)a[k++]=a[i];printf("共删除了%d个元素,

剩下的%d个元素为:\n",N-k,k);for(i=0;i<k;++i)printf("%5d",a[i]);printf("\n程序结束\n");}例T3-2找出2~M之间所有素数（比如，M=100）算法设计思想和描述可用多种方法：方法一，只要：

for(n=2;n<=M;n++)if(n是素数)输出n;

for(n=2;n<=M;n++)

{for(i=2,p=1;i*i<=n;i++)if(n%i==0){p=0;break;}if(p)printf("%6d",n);}判n是不是素数前面已有程序例T3-2找出2~M之间所有素数（比如，M=100）方法二，对方法一进行优化：测试n是不是素数，用已找出的素数试除以n用数组t[N]存放已找出的素数开始，2（最小的素数）存放在t[0]以后，每找出新素数，放在数组t当前尾部只要测试3~M之间所有的奇数是不是素数例T3-2找出2~M之间所有素数（比如，M=100）方法二的实现程序#include<stdio.h>#defineM100#defineNM/2voidmain(){intn,i,p,t[N],j;t[0]=2;//第一个素数

for(j=0,n=3;n<=M;n+=2)

{for(i=0,p=1;i<=j;i++)if(n%t[i]==0){p=0;break;}if(p)t[++j]=n;}//得到一个新素数

for(i=0;i<=j;i++)printf("%8d",t[i]);//输出所有素数

printf("\n");}例T3-2找出2~M之间所有素数（比如，M=100）方法三，筛法：主体想法：筛去2~M中所有合数，剩下的全是素数，即去掉2的所有倍数、3的所有倍数、5的所有倍数，…下面以M=60为例，演示筛选过程第一遍筛选，去掉2的所有倍数（保留素数2）之后：2357911131517192123252729313335373941434547495153555759第二遍筛选，去掉3的所有倍数（保留素数3）：2

357911131517192123252729313335373941434547495153555759余下：2

3571113171923252931353741434749535559例T3-2找出2~M之间所有素数（筛法）第三遍筛选，去掉5的所有倍数（保留素数5）：

2

3

571113171923252931353741434749535559去掉2的倍数时，第一个被筛下去的是4（2的平方）去掉3的倍数时，第一个被筛下去的是9（3的平方）去掉5的倍数时，第一个被筛去的是25（5的平方）去掉7的倍数时，第一个被筛去的是49（7的平方）下一步将要筛去11的所有倍数（从11的平方121开始筛）121超出M=60的范围不再筛选（留下的全是素数）第四遍筛选，去掉7的所有倍数（保留素数7）：

2

3

5

71113171923293137414347495359例T3-2找出2~M之间所有素数（筛法）#include<stdio.h>#defineM100voidmain(){inti,j,a[M+1];for(i=2;i<=M;i++)a[i]=1; //把数2~M放到筛子中

for(i=2;i*i<=M;i++) //i不超过根号Mif(a[i]) //i是上一轮保留下来的素数

for(j=i*i;j<=M;j+=i)a[j]=0;//从i2开始筛，去掉i的倍数

//以下输出筛子中剩下的全部素数

for(i=2;i<=M;i++)if(a[i])printf("%8d",i);printf("\n");}例T3-3N只猴子排成一个圆圈，顺时针地反复1~M报数凡报数为M者退到圈外（输出其编号，猴子编号0到N-1）josephus问题例如，13个猴子（编号0到12），1~5报数，输出结果：

4917083121126105多种解法，介绍其中的三种：前挤法、空位法、链表法

例T3-3josephus问题前挤法的描述：数组a[N]表示一圈椅子，a[i]代表i号椅子（i：0~N-1）开始时，让第i号猴子坐在第i号椅子上（a[i]=i）

a[0]认为是接在a[N-1]之后的（表示圆圈）从0号起沿圆圈数，数到M时，输出该猴子的编号后面的猴子向前挤，猴子总数减1然后重新数1~M直到输出所有N个猴子为止例T3-3josephus问题（前挤法）#include<stdio.h>#defineN13#defineM5voidmain(){inta[N],j,k,n;printf("%d个猴子，1至%d报数，输出结果：\n",N,M);for(j=0;j<N;j++)a[j]=j; //猴子就位

例T3-3josephus问题（前挤法）n=N; //n表示当前剩余的猴子数目

k=0; //k表示报数起点

while(1)//外循环每执行一次退出一个猴子

{for(j=1;j<M;j++)k=(k+1)%n;

//猴子报数

printf("%4d",a[k]);//输出这一轮退出的猴子编号

for(j=k+1;j<n;j++)a[j-1]=a[j]; //后面的猴子向前挤

n--; //猴子总数减1if(!n)break;//所有猴子都退出，程序结束

}printf("\n");}可改为：k=(k+M-1)%n;

//一步跨M-1位

例T3-3josephus问题空位法的描述（主体思想）：猴子退出后，其坐的位子空着，后面的猴子不向前挤数猴子时，只数非空椅子（跳过空椅子）下标i表示猴子编号，a[i]=1表示猴子i尚未退出a[i]=0表示猴子i已经退出例T3-3josephus问题（空位法）#include<stdio.h>#defineN13#defineM5voidmain(){inta[N],j,k,n;printf("%d个猴子，1至%d报数，输出结果：\n",N,M);for(j=0;j<N;j++)a[j]=1;//猴子就位

n=N; //n表示当前剩余的猴子数目

k=N-1; //k表示报数起点的前一点

while(1){j=0;//准备报数

例T3-3josephus问题（空位法）while(j<M) //报数循环

{k=(k+1)%N; //向前一步

if(a[k])j++; //若位子不空，则报数加1}printf("%4d",k);a[k]=0; //退出一个猴子

n--;if(!n)break;}printf("\n");}例T3-3josephus问题静态链表法的描述（主体思想）：让猴子“手拉着手”围成圆圈开始时，0号拉着1号，1号拉着2号，…，N-1号拉着0号（形成循环链）若第j个猴子所拉的那个猴子k退出，则第j个猴子就拉猴子k所拉的那个猴子

数组元素next[i]=j（表示猴子i拉着猴子j）开始时，next[0]=1，next[1]=2，…，next[N-1]=0设next[i]=j，next[j]=k，若猴子j退出，则猴子i就拉猴子k用语句描述成：next[i]=next[j]；等价于next[i]=next[next[i]]；例T3-3josephus问题（静态链表法）#include<stdio.h>#defineN13#defineM5voidmain(){intnext[N],i,j,k,m;printf("%d个猴子，1至%d报数，输出结果：\n",N,M);for(i=0;i<N-1;i++)next[i]=i+1;next[N-1]=0; //猴子们拉成初始链表

例T3-3josephus问题（静态链表法）j=N-1; //j表示报数起点的前一点

for(i=0;i<N-1;i++){if(N-i<M)m=M-N;elsem=M;//改变报数的数目

for(k=1;k<m;k++)j=next[j]; //报数m-1次

printf("%4d",next[j]); //输出这一轮退出的猴子编号

next[j]=next[next[j]];//修改next[j]}printf("%4d\n",j); //输出最后一个猴子编号}第3章构造类型（续）

主要内容3.1数组类型3.2结构类型3.3联合类型和枚举类型3.4文件类型

3.2结构类型3.2.1定义方式和引用方式结构（structure）类型用于描述同一事物中含有多个数据项各数据项的类型相同或不同复数（两个数据项）：实部和虚部（同类型）学生信息：学号、姓名、语文成绩、数学成绩、英语成绩平均成绩、升/留级（多数据项，不同类型）3.2.1

定义方式和引用方式

一般定义格式

struct结构类型名

{域表}

变量名表；罗列出所有的域（成员），排列不分先后每个域形如：类型说明域名；相同类型的域，可以合并定义：类型说明域名1，域名2…；

struct是保留字3.2.1

定义方式和引用方式

一般定义格式

struct结构类型名

{域表}

变量名表；二者可缺少其一

缺结构类型名：只定义结构变量，不定义类型名

缺变量名表：当前定义结构类型名，后用此类型名定义变量定义方式如下：struct

已定义的结构类型名变量名表；C++中，struct可省略

定义存储学生信息的结构类型（1）

structstudent //定义结构类型student{charnumber[12];//学号域

charname[20]; //姓名域

intChinese,math,eng; //三门功课成绩域

floatave; //平均成绩域

charupdown; //升留域Y/N}huang,zhao,grp[50]; //定义student的变量定义结构类型的同时，定义结构变量和结构数组定义存储学生信息的结构类型（2）

structstudent

//定义结构类型student{charnumber[12];charname[20];intChinese,math,eng;floatave;charupdown;}；//此处分号不能少先定义结构类型，再定义结构变量和结构数组：struct

studenthuang,zhao,grp[50]；C++中，struct可省略

定义存储学生信息的结构类型（3通用）

typedefstruct{charnumber[12];charname[20];intChinese,math,eng;floatave;charupdown;}student；//定义结构类型student

用typedef定义结构类型，再定义结构变量和结构数组：studenthuang,zhao,grp[50]；结构型变量的引用方式：1）按域引用2）同类型结构变量之间可以赋值结构的域称为域变量引用域变量的一般格式：结构变量名.域名变量名和域名之间的“点”是分量运算符指明域的所属关系域域变量的作用同一般变量

huang.math //学生huang的数学成绩grp[i].name //第i个学生的姓名结构类型变量的初始化方法

按定义的域次序，依次给各域赋初值后段缺少初值的域，初值为0或'\0'

例如，结构变量的初始化studenthuang={2012080219,"Huangsan",88,97,90};初始化结果：huang.number=2012080219="Huangsan"huang.chinese=88huang.math=97huang.eng=90huang.ave=0.0 //缺少初值

huang.updown='\0' //缺少初值结构类型数组的初始化普通数组的初始化与结构类型简单变量初始化的结合初值形式为：{{第一个元素的初值}，

{第二个元素的初值}，

……{最后一个元素的初值}}结构类型变量的初始化方法

3.2.2typedef的用法用于定义新类型名一般定义格式

typedef类型说明类型名；typedef是保留字例如：

typedefintINT;typedeffloatREAL;其后，INT等同于int，REAL等同于float3.2.2typedef的用法intarr10[10];arr10是数组名typedefintarr10[10];arr10是数组类型名arr10a; 等价于 inta[10];无typedef，表示现定义的是变量名有typedef，表示现定义的是类型名（导出新类型）3.2.2typedef的用法typedef主要用来定义复杂类型（比如结构类型）用typedef定义结构类型名的一般格式为：typedefstruct{域表}结构类型名；定义结构类型名和结构指针类型名（链表中常用）：typedefstruct{域表}结构类型名，*结构指针类型名；3.2.3结构的嵌套和位域一个结构类型的域又是另一个结构类型对域的引用也出现嵌套例如，定义文件信息类型：structfiletype{charname[8],exname[3],ftype[10];

//文件名，扩展名，文件类型域

struct//修改日期（年月日）域是另一结构类型

{intyear,month,day;}date;intlength;//文件长度域（所占字节数）

}afile,directory[1000],*fptr;变量afile的修改日期中的月份表示成：afile.date.month通信录的数据结构姓名：职务：电话：工作单位：通信地址和邮编：E-mail地址：住所：住宅电话:单位电话:手机:省（市）名称：城市：街道：门牌号码：邮编：

行政职务：技术职务：位域结构类型中可以有若干个（甚至全部）域是位域含有位域的结构称为位结构

位域定义格式为：域类型位域名:域长;域类型通常为：int、unsigned、char连续定义的同类型位域将占据同一分配单位

位域名可以缺省（无名位域）1）缺少位域名，且域长为0：表示让下一个位域存放在另一个分配单位2）缺少位域名，且域长不为0：表示预留相应的位数不用位域某单位工作人员信息的结构类型定义：

structemployee_info{charname[20]; //姓名

intage; //年龄

structaddraddress;//住址（已定义结构类型addr）

floatpay; //工资数额

unsignedstate:1; //位域（1：已退休，0：未退休）

unsignedpayoff:1;//位域（1：工资已发；0：未发）

}employee[100];//假定人数为100

位域引用方式（同普通域）如：

employee[i].state=1;

位域定义含有4个位域的位结构

structsample{intf1:4;intf2:2;//域f1和f2存储在一个分配单位

int:0;//表示给下面的域重新分配存储单元

intf3:1;//f3存储在新的分配单位

int:2;//表示留出2位不用

intf4:1;//f3和f4之间空2位

}使用位域可以节省存储单元常用来模拟汇编语言中的控制字3.2.4程序设计示例

例3-13用结构类型编写复数四则运算的程序

将复数定义为结构类型，含有实部域和虚部域实部和虚部均为实型（float）

例3-10用结构类型编写复数四则运算的程序

#include<stdio.h>voidmain(){structcomplex{floatre,im;//实部和虚部域

}x,y,a,b,c,d;//定义5个复数类型变量

floatr;printf("请输入两个复数的实部和虚部：\n");scanf("%f%f%f%f",&x.re,&x.im,&y.re,&y.im);a.re=x.re+y.re;a.im=x.im+y.im;//求a=x+y

b.re=x.re-y.re;b.im=x.im-y.im;//求b=x-yc.re=x.re*y.re-x.im*y.im;//求c=x×yc.im=x.re*y.im+x.im*y.re;例3-10用结构类型编写复数四则运算的程序

r=y.re*y.re+y.im*y.im;//求d=x÷yd.re=(x.re*y.re+x.im*y.im)/r;d.im=(x.im*y.re-x.re*y.im)/r;

//以下输出x、y及其和a、差b、积c、商dprintf("x=%4.1f%+4.1fi\n",x.re,x.im);printf("y=%4.1f%+4.1fi\n",y.re,y.im);printf("a=x+y=%4.1f%+4.1fi\n",a.re,a.im);printf("b=x-y=%4.1f%+4.1fi\n",b.re,b.im);printf("c=x×y=%4.1f%+4.1fi\n",c.re,c.im);printf("d=x÷y=%4.1f%+4.1fi\n",d.re,d.im);}例3-11编程处理学生的学习成绩先输出留级人员名单，再输出升级人员名单一个学生的数据项：学号、姓名、语文成绩、数学成绩、英语成绩平均成绩、升/留级前几项为输入内容，后二项为计算内容平均成绩不及格（低于60分），则该生留级，否则升级

例