C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 1
上机说明穷举,列举所有可能情况,逐个测试,如求完数递推,从已知出发,利用递推公式向未知靠拢,如 Fibnacci数列
for(i=1;i<=19;i++)
f1=f1+f2
f2=f2+f1
输出 f1 f2
输出 f1 f2
f1=1;f2=1注意 (循环 )变量初值,
语句位置,
边界分析,
数据类型
for(n=1;n<=1000;n++)
for(i=1;i<n;i++)
n%i==0
Y N
sum+=i
sum=0
sum==nY N
输出 m
for(i=1;i<n;i++)
m%i=0
Y N
出 i
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 2
综合实验:子函数 --迭代法 1:输入 x1,计算 x2,进行迭代,直到相邻两项很接近
while(fabs(x1-x2)>1e-6)
x1=f(x2)
x2=f(x1)
x2= f(x1)
为 x1赋初始迭代值输出 x2
思路要清晰,注意 (循环 )变量初值,注意迭代步长
while(fabs(x1-x2)>1e-6)
x1=x2
x2=f(x2)
x2= f(x1)
为 x1赋初始迭代值输出 x2
法 2:输入 x1,计算 x2,当相邻两项不接近时进行迭代
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 3
二分法说明方法 1,输入两边界点,直到函数值异号。,计算中点与中点值,用中点替换函数值与其同号的端点,,直到中点值接近零方法 2:输入两边界点,当同号时重新输入,当中点值不接近零时,
,用中点替换函数值与其同号的端点,再计算中点与中点值,
直到 y1*y2<0
while(fabs(y0)>1e-6)
y1=f(x1),y2=f(x2) y1
输出 x0
y1*y0>0Y N
x1=x0,y1=y0 x2=x0,y2=y0
x0=(x1+x2)/2,y0=f(x0)
输入 x1与 x2
while(fabs(y0)>1e-6)
x0= (x1+x2)/2,y0=f(x0)
输出 x0
y1*y0>0
Y N
x1=x0,y1=y0 x2=x0,y2=y0
x0=(x1+x2)/2,y0=f(x0)
当 y1*y2>0
y1=f(x1),y2=f(x2)
输入 x1与 x2
输入 x1与 x2,计算 y1,y2
注意 (循环 )变量初值与循环类型的选择第七章
引言实际问题中常需处理同一类型的大批数据,如 1000
个学生的成绩。每个成绩用一个变量存储则需定义的变量过多,使用不方便
C语言引入数组,借助数组可以用名相同、下标不同的变量表示同类型的大批数据,如 s[1]代表 1号学生的成绩,s[2]代表 2号学生的成绩用一组具有相同名字、不同下标的变量表示具有同种类型的一组数据,这就是数组,如 int s[1000]
每个人 3门课,则用 s[1][1],s[1][2],s[1][3],s[2][1]…
,根据下标个数分一维数组与多维数组
主要内容
7.1 一维数组定义、引用、初始化和举例
7.2 二维数组定义、引用、初始化和举例
7.3 字符数组定义、引用、初始化和举例关键:数组的相关算法类型说明符 数组名 [ 常量表达式 ] ;
例如,int a[10]; float b[8],c[9];
§ 7.1.1一维数组的定义
1) 数组元素按顺序存储在一片连续的内存单元中,数组名代表存储区域起始地址,即第一个,元素,地址
2) 常量表达式不能包含变量,长度必须大于 0。
如 int n; scanf(“%d”,&n); int a[n]; 不可,但可用符号常量,如 #define N 10; int a[N];
数组名 [ 下标 ]
如,int a[3];a[1]=80;printf(“%d”,a[1]);
double b[3];scanf(“%lf”,&b[1]);
§ 7.1.2一维数组元素的引用
1) a[i]相当于一个变量,可赋值或输入,而数组名是地址常量,不能被赋值
2) 数组元素的下标从零开始,到 N-1结束 。 如对 int a[3]
,数组元素为 a[0],a[1],a[2];而 a[3]越界
3) C编译系统对数组不作下标越界检查,但越界操作会破坏数组存储区域外的程序或数据,易造成程序出错,甚至系统崩溃 。 如 scanf(“%d”,&a[3]);
例 7.1 定义 10元素的整型数组,元素 0- 9,之后逆序输出
#include <stdio.h>
void main()
{
int i,a[ 10] ;
for (i=0;i<10;i++)
a[ i] =i;
for(i=9;i>=0; i--)
printf("%d ″,a[ i] );
printf("\n″ );
}
定义之后,不能通过数组名对数组进行整体输入,
输出或赋值,如:
int a[3];
a={1,2,3};
printf(“%d%d%d”,a);
注意访问数组元素时循环变量开始和结束条件的表示
§ 7.1.3一维数组的初始化初始化,定义数组的同时为数组元素赋值 。 方式:
1) 全部元素赋初值如 int a[3]={8,5,9};则 a[0]=8,a[1]=5,a[2]=9;
2) 部分元素赋初值,其余元素自动初始化为 0
如 int a[3]={8,2};则 a[0]=8,a[1]=2,a[2]=0;
3) 全部元素赋初值时,数组长度可以省略如 int a[]={8,5,9}等同于 int a[3]={8,5,9}
注 1:部分赋值时只能从首元素开始若干连续元素,如
int a[5]={,2,3};int b[5]={1,,3};错注 2:定义与赋值分开时,只能逐个元素赋值例 7.2:用数组求 Fibonacci数列的前 20个元素,5个一行
int f[ 20] ={1,1};
for(i=2;i<20;i++)/*注意 结束条件的表示 */
f[ i] =f[ i-2] +f[ i-1]
§ 7.1.4一维数组程序举例
f [ 0 ]= 1 ; f [ 1 ]= 1 ;
fo r ( i = 2 ; i < 20 ; i ++)
f [ i ]= f [ i - 1 ]+ f [ i - 2 ]
fo r ( i = 0 ; i < 20 ; i ++)
i % 5 == 0
Y N
换行输出元素 f [ i ]
例 7,2 主函数 N - S 图例 7.3,起泡法对 10个数 由小到大排序思路,每一趟排序时,从首元素开始 相邻两个数进行比较,将小的换到前头,如此,则每趟排序都会使当前,最大,的数,沉到末尾,,小的数逐步,上升,,N-1趟则排序完毕。
第一趟结果
5
4
8
0
9
第 4 次比较
5
4
8
9
0
第 3 次比较
5
4
8
9
0
第 2 次比较
5
8
4
9
0
原始状态
8
5
4
9
0
第 1 次比较
8
5
4
9
0
图 6,7 第一趟冒泡排序过程
fo r ( i = 0 ; i < N ; i ++)
输入元素 a [ i ]
fo r ( i = 1 ; i < = N - 1 ; i ++
fo r ( j = 0 ; j < N - i ; j ++)
Y N
fo r ( i = 0 ; i < N ; i ++)
输出元素 a [ i ]
a [ j ] > a [ j + 1 ]
a [ j ] < = > a [ j + 1 ]
图 6,9 例 6,4 主函数 N - S 图
/*i表趟 数,j表 前者的 下标 */
改进的冒泡排序
§ 7-2二维数组
§ 7.2.1二维数组的定义类型说明符 数组名[常量表达式][常量表达式];
例如,float a[2][3],b[5][5];不能用 float a[3,4]
1) 元素按行优先顺序存储在连续的内存单元中,数组名代表存储区域起始地址,如 float b[2][3]
2)二维数组相当于特殊的,一维数组,,每个,元素,是一行组成的数组,如 float b[2][0]相当于由 b[0],与
[1] 组成的 一维数 组,而 b[0] 相当于 由 b[0][0]
b[0][1] b[0][2]组成的一维数组的数组名
3) 常量表达式不能包含变量,长度必须大于 0
数组名 [下标 1][下标 2]
如 int a[3][4];a[1][1]=80;printf(“%d”,a[1][1]);
double b[3][2];scanf(“%lf”,&b[1][1]);
§ 7.2.2二维数组元素的引用说明,1) a [i][j]相当于一个变量,数组名是地址常量
2) 对 int a[M][N],下标从 [0][0]开始,到 [M-1][N-1]结束如对 int a[3][4],a[3][1]越界
3) C编译系统对数组不作下标越界检查,但易造成程序出错,甚至系统崩溃 。 如 scanf(“%d”,&a[3][1]);
§ 7.2.3二维数组的初始化
1) 按行赋初值,int a[2][3]={{11,12,13},{21,22,23}};
2) 所有元素逐个写入花括号,int a[2][3]={11,12,13,21,22,23};
3) 部分元素赋初值,其余元素自动初始化为 0 int
a[2][3]={{11,12},{21}};int a[2][3]={1,2,3}
4) 省略第一维长度,第二维长度不能省 。 如:
int a[][3]={{11,12,13},{21,22,23}};
int a[][3]={11,12,13,21,22,23};
int a[][4]={{0,0,3},{0},{0,10}}
注 1,VC6.0 中初始化数组时不能出现空花括号,如
P138int[3][4]={{1},{},{9}}与 int a[][4]={{0},{},{1}}错注 2:定义与赋值分开时,只能逐个元素赋值
§ 7.2.4二维数组程序举例例 7.4 求一个整数矩阵的转置,并,输出,
初始化二维数组 a 各元素
for ( i = 0 ; i < 4 ; i ++)
for ( j = 0 ; j < 2 ; j ++)
输出原矩阵 A
图 6,15 例 6,9 主函数 N - S 图
b [ i ][ j ]= a [ j ][ i ]
输出转置矩阵 B
int a[2][4]={0,1,2,3,4,5,6},i,j;
int b[4][2];
for (i=0;i<4;i++)
for (j=0;j<2;j++)
b[i][j]=a[j][i];
printf("原矩阵 A为,\n");
for(i=0;i<2;i++)
{
for(j=0;j<4;j++)
printf("%4d",a[i][j]);
printf("\n");
}………
注意访问数组元素时循环变量开始和结束条件的表示,i=0;i<N
方阵自身转置?
例 7.5,有一个 3× 4的矩阵,编程序求其中值最大的元素,
及其所在的行号和列号。
注意如何记录最小元素的标号多维数组三维数组,float a[ 2] [ 3] [ 4] ;
a[0][0][0]→ a[0][0][1]→ a[0][0][2]→ a[0][0][3]→
a[0][1][0]→ a[0][1][1]→ a[0][1][2]→ a[0][1][3]→
a[0][2][0]→ a[0][2][1]→ a[0][2][2]→ a[0][2][3]→
a[1][0][0]→ a[1][0][1]→ a[1][0][2]→ a[1][0][3]→
a[1][1][0]→ a[1][1][1]→ a[1][1][2]→ a[1][1][3]→
a[1][2][0]→ a[1][2][1]→ a[1][2][2]→ a[1][2][3]→
三维数组的元素排列顺序定义时长度不能含变量,引用时下标从零开始,顺序存储,第一维的下标变化最慢,维数越靠后,下标变化越快 。 数组名代表首址作业,7.1 7.3 7.5 7.7之 N-S图实验报告:
题目:数组程序设计内容,7.2 7.4 7.6 7.8之 N-S图选择排序,每趟都将 找到当前最小的元素 交换 到前边,共 N-1趟 则完成排序。
用 i代表当前的首位置,
min代表最小元素的标号。
筛法求 1- N内素数,
将 1-N之间的数存在数组,
挖去 1(将其值变为 0),
从 2开始,用 未被挖的数除其后未被挖的数,若能整除则挖去,到 sqrt(N)
即可 将所有非素数挖去,
输出未被挖的数即可插入排序,从第一个元素到最末一个元素,每次都将该元素插入其前的有序数组中,使得仍然有序。
为此,将其前元素逐个后移一位,一旦找到比此元素小的元素就停止,将元素放到此位置后矩阵乘法:矩阵乘法公式改进的插入排序自由落体问题,注意 边界分析,重点看第一次、第二次落地时变量的值是否正确,尤其看最后一次所求是否是第 10此落地经过的路程和第 10次反弹的高度作业说明
s=100
h=50
for(i=2;i<=10;i++)
h=h/2
s=s+2*h
输出 s与 h
保证边界不出错的关键在于思路要清晰,且赋予循环变量一定的含义。
§ 7-3字符数组
§ 7.3.1字符数组的定义
char c[ 5] ;
c[0]=′I′;c [ 1] =′ ′;c [ 2] =′a′;
c[ 3] =′m′;c [ 4] =′ ′;c[5]=′l′;c[6]=′k′;
注意:整型与字符型有时可以混用,两者占用的字节数与表示的范围不同。此外,数组名、变量名、
函数名不能重复
§ 7.3.3字符数组的引用例 7.6 输 出一个字符串。
#include <stdio.h>
void main()
{ char c[ 10] ={’I’,’ ’,’a’,’m’,’ ’,’a’,’ ’,
’b’,’ o’,′y′};
int i;
for(i=0;i<10;i++)
printf(″%c″,c[ i] );
printf(″ \ n″);
}
下标从 0开始!
char c[10]={?I?,?’?,?a?,?m?,,?h?,?a?,?p?,?p?,?y?};
char c[]={?I?,?’?,?a?,?m?,,?h?,?a?,?p?,?p?,?y?};
char c[10]={?I?,?’?,?a?,?m?}; /*其后元素自动为
‘ \0’*/
如果在定义字符数组时不进行初始化,则数组中各元素的值是不可预料的
§ 7.3.2&&7.3.4字符数组的初始化使用字符串常量对字符数组初始化:
char c[10]={"China″};
char c[10]=“China”
char c[]=“China”
注,char str[5]=“China”错
§ 7.3.5字符数组的输入输出
逐个字符输入输出,用格式符,%c”
将整个字符数组作为整体输入或输出。用,%s”格式符,输出时遇 第一个 ’ \0?结束(注意没有 \0或多个 \0如何),输入时自动在末尾加 ’ \0?
例,char strl[ 5],str2[ 5],str3[ 5] ;
scanf(″%s%s%s″,str1,str2,str3);
How are you?
注 (1)数组名相当于首地址,故不加地址符
(2)用 scanf函数输入多个字符串时以空格为分隔符
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 26
1,puts函数格式,puts (字符数组名 );
作用:逐个输出字符数组中元素,一旦遇 ‘ \0?,便结束输出并换行,返回换行符,失败时返回 -1
如,char str[]={“China\nBeijing”}; puts(str);
2,gets函数格式,gets(字符数组名 );
作用:从终端输入一个字符串到字符数组,自动在末尾加 \0,以 回车作输入结束标志,返回字符数组首地址如,gets(str); 输入,Computer↙,str赋值为 C o m p u t e r \0,共 9字符注意,用 puts和 gets函数只能输入或输出一个字符串,不能写成
puts(str1,str2) 或 gets(str1,str2);
7.3.6 字符串处理函数 <string.h>
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 27
3,strcat函数格式,strcat(字符数组 1,字符数组 2);
作用,连接两个字符数组中的字符串,把字符串 2接到字符串 1
第一个 \0的位置,返回字符数组 1的首地址如,char str1[30]={“People's Republic of”};
char str2[]=“China”;
printf(“%s”,strcat(str1,str2));
输出,People's Republic of China
4,strcpy函数格式,strcpy(字符数组 1,字符串 2);
作用,将字符串 2第一个 \0及其以前 的元素 复制到字符数组 1。
如,char str1[10],str2[]=“China”;strcpy(str1,str2);
注,变型 strncpy(str1,str2,2);此外,str1=str2不可
????
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 28
5,strcmp函数格式,strcmp(字符串 1,字符串 2);
作用:比较字符串 1和字符串 2。
如,strcmp(str1,str2); strcmp(“China”,“Korea”);
比较规则:两个字符串自左至右逐个字符相比,直到出现不同的字符或遇到‘ \0?为止。如全部字符相同,则认为相等;若出现不相同的字符,则以第一个不相同的字符的比较结果为准。
比较的结果由函数值返回
① 如果字符串 1=字符串 2,函数值为 0。
② 如果字符串 1>字符串 2,函数值为一正整数。
③ 如果字符串 1<字符串 2,函数值为一负整数。
注意:对两个字符串比较,不能用以下形式:
if (str1>str2) printf(“yes”);
而只能用 if (strcmp(str1,str2)>0) printf(“yes”);
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 29
6,strlen函数格式,strlen (字符数组 ) ;
作用:测试字符串长度的函数,返回 字符串有效字符个数 。
如,char str[10]={“China”}; printf(“%d”,strlen(str));
7,strlwr函数格式,strlwr (字符串 ) ;
作用,将字符串中大写字母换成小写字母 。
8,strupr函数格式,strupr (字符串 ) ;
作用,将字符串中小写字母换成大写字母 。
例 7.8 输入一行字符,统计其中有多少个单词
§ 7.3.7字符数组应用举例
flag=0;count=0
str=gets()
i=0
While((c=str[i])!=? \0?)
flag=0&&c!=
Y N
count++
flag=1
c=
Y N
flag=0
i++
输出 count
w o rd = 0 ; c o u n t = 0
对字符串中每个字符 c
图 6,21 例 6,13 主函数 N - S 图输入字符串 str
c 为空格
Y N
w o rd = 0
w o rd == 0
Y N
c o u n t ++
w ord = 1
输出单词个数 c o u n t
标记变量为 0
代表刚读过一个空格,
其它情况为 1
例 7.9 二维字符数组举例:求三个字符数组中最大者
char string[ 20] ;
char str[ 3][ 20] ;
int i;
for (i=0;i<3;i++)
gets (str[ i] );
strcpy(string,str[ 0] )
if (strcmp(str[ 1],string)>0)
strcpy(string,str[ 1] );
if (strcmp(str[ 2],string)>0)
strcpy(string,str[ 2] );
printf(″%s \ n″,string);
作业,7.9 7.12 7.14之 N-S图实验报告:
题目:字符数组程序设计内容,7.10 7.13 7.15之 N-S图操 作类别数组的定义 数组元素的引 用 数组初始化举例一维数组 类型说明符 数组名 [常量表达式 ] 数组名 [下标 ] int a[3]={1,2,3}
二维数组 类型说明符 数组名 [常量表达式 1] [常量表达式 2] 数组名 [下标 1] [下标 2]
int
[2][3]={{1,2,3},{4,5,6}}
一维字符数组
char 数组名 [常量表达式 ] 数组名 [下标 ] char str[4]=”ABC”
注意事项 数组长度表达式中不能含 变量,且大于 0 下标从 0开始,注意越界问题 元素引用前最好赋初 值,否则值随机存储:元素按序存储在连续的内存单元中,数组名代表存储区域起始地址,访问时根据名和下标计算相应元素的地址数组,用一组名同、下标不同的变量表示同一类型大批数据算法:递推 冒泡排序及其改进 选择排序 插入排序筛法 折半查找 数组逆序 出圈 ;矩阵乘法 矩阵自身转置杨辉三角 魔方阵 鞍点 ;字符或单词统计 字符串处理函数筛法求 1- N内素数,
将 1-N之间的数存在数组,挖去 1(将其值变为 0),从 2开始,
用 未被挖的数除其后未被挖的数,
若能整除则挖去,到 sqrt(N)即可 将所有非素数挖去,输出未被挖的数即可
for(i=0;i<100;i++)
a[i]=i+1
a[0]=0
for(i=1;i<sqrt(100);i++)
Y N
a[i]!=0
for(j=i+1;j<100;j++)
a[j]!=0
Y N
a[j]%a[i]=0
Y N
a[j]=0
for(i=0;i<100;i++)
Y N
a[i]!=0
输出 a[i]
( 1) C语言中数组下标从零始,
有两种处理方式,其一,舍弃
a[0]不用,定义 int a[101];其二,习惯 C语言,始终使用标号,
处理时用 for(i=0;i<N;i++)
( 2)中间多个分支结构可合并
(3)根据 N-S图写程序,关键在于花括号的使用冒泡排序,每一趟排序时,从首元素开始 相邻两个数进行比较,将小的换到前头,如此,
则每趟排序都会使当前,最大,
的数,沉到末尾,,小的数逐步,上升,,N-1趟则排序完毕。
fo r ( i = 0 ; i < N ; i ++)
输入元素 a [ i ]
fo r ( i = 1 ; i < = N - 1 ; i ++
fo r ( j = 0 ; j < N - i ; j ++)
Y N
fo r ( i = 0 ; i < N ; i ++)
输出元素 a [ i ]
a [ j ] > a [ j + 1 ]
a [ j ] < = > a [ j + 1 ]
图 6,9 例 6,4 主函数 N - S 图
/*i表趟 数,j表 前者的 下标 */
改进的冒泡排序选择排序,每趟都将 找到当前最小的元素 交换 到前边,共 N-1趟 则完成排序。
用 i代表当前的首位置,
min代表最小元素的标号。
f o r ( i = 0 ; i < 10 ; i ++)
输入元素 a [ i ]
f o r ( i = 0 ; i < 9 ; i ++)
m in = i
f o r ( j = i + 1 ; j < 10 ; j ++)
a [ m in ] > a [ j ]
Y N
m in = j
m in != i
Y N
a [ m in ] < = > a [ i ]
f o r ( i = 0 ; i < 10 ; i ++)
输出元素 a [ i ]
选择排序注意:指导书中 N-S图默认下标从 1开始,最好与 C
语法一致插入排序:从第二个元素到最末一个元素,每次都将该元素插入其前的有序数组中,使得仍然有序。为此,将其前元素逐个后移一位,一旦找到比此元素小的元素就停止,
将元素放到此位置后(自顶向下 逐步细化)
for(i=1;i<N;i++)
{
j=i-1;
temp=a[i];/*记录当前元素备用 */
while(a[j]>temp&&j>=0)
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
注意:数组元素后移时要从后向前逐个移,从前向后不可,务必分析原因魔方阵,int a[N][N]={0};i=0; j=N/2;a[i][j]=1;
for(k=2;k<=N*N;k++)
{
i=i-1;j=j+1;/*右上方 */
if(i<0&&j==N) /*第一行第 N列 */
{
i=i+2; j=j-1;/*因 i,j已改变 */
a[i][j]=k;
}
else if(i<0)/*第一行 */
i=N-1;
else if(j==N)
j=0;
if(a[i][j]!=0)
{i=i+2;j=j-1; /*因 i,j已改变 */}
a[i][j]=k;
}
8 1 6
357
4 9 2
鞍点,for(i=0;i<M;i++)
{
maxj=0;
for(j=1;j<N;j++)if(a[i][maxj]<a[i][j])maxj=j;
flag=1;
for(j=0;j<M;j++)
if(a[j][maxj]<a[i][maxj])flag=0;
if(flag==1)
{
count++;
printf(“第 %d个鞍点:,,count);
printf("a[%d][%d]=%d\n",i,maxj,a[i][maxj]);
}
}
if(count==0)
printf("没有鞍点 ");
8 1 6
357
4 9 2
折半查找,比较待查找数据与数组中间位置上元素,两者相等则找到,程序结束;
否则,前者大于后者说明待查找数据只可能在数组的后半部分,反之说明只可能在前半部分,当然也可能不在数组中。但无论哪种情况,
查找范围都将缩小一半。重复以上步骤,最多比较
log2N次就能得到结果,其中 N为数组长度。
输入待查找数据 num
fla g = 0 ; bo tt = 0 ; to p = N - 1
初始化有序数组 a [ N ]
num < a [ 0 ] || num > a [ N - 1 ]
Y
N
w hi le ( fla g == 0 && bo tt < to p )
m id =( bo tt + to p )/ 2
输出
num
不在数组中
lo c a = m id
to p = m id - 1 b o tt= m id + 1
num == a [ mid ]
N
num < a [ m id ]
Y
Y N
fla g = 1
b o t t = t o p && num = a [ b o t t ]
Y
N
lo c a = bo tt ; fla g = 1
f l a g == 1
Y
N
输出元素位置 不在数组中图 6,13 例 6,7 主函数 N - S 图
上机说明穷举,列举所有可能情况,逐个测试,如求完数递推,从已知出发,利用递推公式向未知靠拢,如 Fibnacci数列
for(i=1;i<=19;i++)
f1=f1+f2
f2=f2+f1
输出 f1 f2
输出 f1 f2
f1=1;f2=1注意 (循环 )变量初值,
语句位置,
边界分析,
数据类型
for(n=1;n<=1000;n++)
for(i=1;i<n;i++)
n%i==0
Y N
sum+=i
sum=0
sum==nY N
输出 m
for(i=1;i<n;i++)
m%i=0
Y N
出 i
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 2
综合实验:子函数 --迭代法 1:输入 x1,计算 x2,进行迭代,直到相邻两项很接近
while(fabs(x1-x2)>1e-6)
x1=f(x2)
x2=f(x1)
x2= f(x1)
为 x1赋初始迭代值输出 x2
思路要清晰,注意 (循环 )变量初值,注意迭代步长
while(fabs(x1-x2)>1e-6)
x1=x2
x2=f(x2)
x2= f(x1)
为 x1赋初始迭代值输出 x2
法 2:输入 x1,计算 x2,当相邻两项不接近时进行迭代
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 3
二分法说明方法 1,输入两边界点,直到函数值异号。,计算中点与中点值,用中点替换函数值与其同号的端点,,直到中点值接近零方法 2:输入两边界点,当同号时重新输入,当中点值不接近零时,
,用中点替换函数值与其同号的端点,再计算中点与中点值,
直到 y1*y2<0
while(fabs(y0)>1e-6)
y1=f(x1),y2=f(x2) y1
输出 x0
y1*y0>0Y N
x1=x0,y1=y0 x2=x0,y2=y0
x0=(x1+x2)/2,y0=f(x0)
输入 x1与 x2
while(fabs(y0)>1e-6)
x0= (x1+x2)/2,y0=f(x0)
输出 x0
y1*y0>0
Y N
x1=x0,y1=y0 x2=x0,y2=y0
x0=(x1+x2)/2,y0=f(x0)
当 y1*y2>0
y1=f(x1),y2=f(x2)
输入 x1与 x2
输入 x1与 x2,计算 y1,y2
注意 (循环 )变量初值与循环类型的选择第七章
引言实际问题中常需处理同一类型的大批数据,如 1000
个学生的成绩。每个成绩用一个变量存储则需定义的变量过多,使用不方便
C语言引入数组,借助数组可以用名相同、下标不同的变量表示同类型的大批数据,如 s[1]代表 1号学生的成绩,s[2]代表 2号学生的成绩用一组具有相同名字、不同下标的变量表示具有同种类型的一组数据,这就是数组,如 int s[1000]
每个人 3门课,则用 s[1][1],s[1][2],s[1][3],s[2][1]…
,根据下标个数分一维数组与多维数组
主要内容
7.1 一维数组定义、引用、初始化和举例
7.2 二维数组定义、引用、初始化和举例
7.3 字符数组定义、引用、初始化和举例关键:数组的相关算法类型说明符 数组名 [ 常量表达式 ] ;
例如,int a[10]; float b[8],c[9];
§ 7.1.1一维数组的定义
1) 数组元素按顺序存储在一片连续的内存单元中,数组名代表存储区域起始地址,即第一个,元素,地址
2) 常量表达式不能包含变量,长度必须大于 0。
如 int n; scanf(“%d”,&n); int a[n]; 不可,但可用符号常量,如 #define N 10; int a[N];
数组名 [ 下标 ]
如,int a[3];a[1]=80;printf(“%d”,a[1]);
double b[3];scanf(“%lf”,&b[1]);
§ 7.1.2一维数组元素的引用
1) a[i]相当于一个变量,可赋值或输入,而数组名是地址常量,不能被赋值
2) 数组元素的下标从零开始,到 N-1结束 。 如对 int a[3]
,数组元素为 a[0],a[1],a[2];而 a[3]越界
3) C编译系统对数组不作下标越界检查,但越界操作会破坏数组存储区域外的程序或数据,易造成程序出错,甚至系统崩溃 。 如 scanf(“%d”,&a[3]);
例 7.1 定义 10元素的整型数组,元素 0- 9,之后逆序输出
#include <stdio.h>
void main()
{
int i,a[ 10] ;
for (i=0;i<10;i++)
a[ i] =i;
for(i=9;i>=0; i--)
printf("%d ″,a[ i] );
printf("\n″ );
}
定义之后,不能通过数组名对数组进行整体输入,
输出或赋值,如:
int a[3];
a={1,2,3};
printf(“%d%d%d”,a);
注意访问数组元素时循环变量开始和结束条件的表示
§ 7.1.3一维数组的初始化初始化,定义数组的同时为数组元素赋值 。 方式:
1) 全部元素赋初值如 int a[3]={8,5,9};则 a[0]=8,a[1]=5,a[2]=9;
2) 部分元素赋初值,其余元素自动初始化为 0
如 int a[3]={8,2};则 a[0]=8,a[1]=2,a[2]=0;
3) 全部元素赋初值时,数组长度可以省略如 int a[]={8,5,9}等同于 int a[3]={8,5,9}
注 1:部分赋值时只能从首元素开始若干连续元素,如
int a[5]={,2,3};int b[5]={1,,3};错注 2:定义与赋值分开时,只能逐个元素赋值例 7.2:用数组求 Fibonacci数列的前 20个元素,5个一行
int f[ 20] ={1,1};
for(i=2;i<20;i++)/*注意 结束条件的表示 */
f[ i] =f[ i-2] +f[ i-1]
§ 7.1.4一维数组程序举例
f [ 0 ]= 1 ; f [ 1 ]= 1 ;
fo r ( i = 2 ; i < 20 ; i ++)
f [ i ]= f [ i - 1 ]+ f [ i - 2 ]
fo r ( i = 0 ; i < 20 ; i ++)
i % 5 == 0
Y N
换行输出元素 f [ i ]
例 7,2 主函数 N - S 图例 7.3,起泡法对 10个数 由小到大排序思路,每一趟排序时,从首元素开始 相邻两个数进行比较,将小的换到前头,如此,则每趟排序都会使当前,最大,的数,沉到末尾,,小的数逐步,上升,,N-1趟则排序完毕。
第一趟结果
5
4
8
0
9
第 4 次比较
5
4
8
9
0
第 3 次比较
5
4
8
9
0
第 2 次比较
5
8
4
9
0
原始状态
8
5
4
9
0
第 1 次比较
8
5
4
9
0
图 6,7 第一趟冒泡排序过程
fo r ( i = 0 ; i < N ; i ++)
输入元素 a [ i ]
fo r ( i = 1 ; i < = N - 1 ; i ++
fo r ( j = 0 ; j < N - i ; j ++)
Y N
fo r ( i = 0 ; i < N ; i ++)
输出元素 a [ i ]
a [ j ] > a [ j + 1 ]
a [ j ] < = > a [ j + 1 ]
图 6,9 例 6,4 主函数 N - S 图
/*i表趟 数,j表 前者的 下标 */
改进的冒泡排序
§ 7-2二维数组
§ 7.2.1二维数组的定义类型说明符 数组名[常量表达式][常量表达式];
例如,float a[2][3],b[5][5];不能用 float a[3,4]
1) 元素按行优先顺序存储在连续的内存单元中,数组名代表存储区域起始地址,如 float b[2][3]
2)二维数组相当于特殊的,一维数组,,每个,元素,是一行组成的数组,如 float b[2][0]相当于由 b[0],与
[1] 组成的 一维数 组,而 b[0] 相当于 由 b[0][0]
b[0][1] b[0][2]组成的一维数组的数组名
3) 常量表达式不能包含变量,长度必须大于 0
数组名 [下标 1][下标 2]
如 int a[3][4];a[1][1]=80;printf(“%d”,a[1][1]);
double b[3][2];scanf(“%lf”,&b[1][1]);
§ 7.2.2二维数组元素的引用说明,1) a [i][j]相当于一个变量,数组名是地址常量
2) 对 int a[M][N],下标从 [0][0]开始,到 [M-1][N-1]结束如对 int a[3][4],a[3][1]越界
3) C编译系统对数组不作下标越界检查,但易造成程序出错,甚至系统崩溃 。 如 scanf(“%d”,&a[3][1]);
§ 7.2.3二维数组的初始化
1) 按行赋初值,int a[2][3]={{11,12,13},{21,22,23}};
2) 所有元素逐个写入花括号,int a[2][3]={11,12,13,21,22,23};
3) 部分元素赋初值,其余元素自动初始化为 0 int
a[2][3]={{11,12},{21}};int a[2][3]={1,2,3}
4) 省略第一维长度,第二维长度不能省 。 如:
int a[][3]={{11,12,13},{21,22,23}};
int a[][3]={11,12,13,21,22,23};
int a[][4]={{0,0,3},{0},{0,10}}
注 1,VC6.0 中初始化数组时不能出现空花括号,如
P138int[3][4]={{1},{},{9}}与 int a[][4]={{0},{},{1}}错注 2:定义与赋值分开时,只能逐个元素赋值
§ 7.2.4二维数组程序举例例 7.4 求一个整数矩阵的转置,并,输出,
初始化二维数组 a 各元素
for ( i = 0 ; i < 4 ; i ++)
for ( j = 0 ; j < 2 ; j ++)
输出原矩阵 A
图 6,15 例 6,9 主函数 N - S 图
b [ i ][ j ]= a [ j ][ i ]
输出转置矩阵 B
int a[2][4]={0,1,2,3,4,5,6},i,j;
int b[4][2];
for (i=0;i<4;i++)
for (j=0;j<2;j++)
b[i][j]=a[j][i];
printf("原矩阵 A为,\n");
for(i=0;i<2;i++)
{
for(j=0;j<4;j++)
printf("%4d",a[i][j]);
printf("\n");
}………
注意访问数组元素时循环变量开始和结束条件的表示,i=0;i<N
方阵自身转置?
例 7.5,有一个 3× 4的矩阵,编程序求其中值最大的元素,
及其所在的行号和列号。
注意如何记录最小元素的标号多维数组三维数组,float a[ 2] [ 3] [ 4] ;
a[0][0][0]→ a[0][0][1]→ a[0][0][2]→ a[0][0][3]→
a[0][1][0]→ a[0][1][1]→ a[0][1][2]→ a[0][1][3]→
a[0][2][0]→ a[0][2][1]→ a[0][2][2]→ a[0][2][3]→
a[1][0][0]→ a[1][0][1]→ a[1][0][2]→ a[1][0][3]→
a[1][1][0]→ a[1][1][1]→ a[1][1][2]→ a[1][1][3]→
a[1][2][0]→ a[1][2][1]→ a[1][2][2]→ a[1][2][3]→
三维数组的元素排列顺序定义时长度不能含变量,引用时下标从零开始,顺序存储,第一维的下标变化最慢,维数越靠后,下标变化越快 。 数组名代表首址作业,7.1 7.3 7.5 7.7之 N-S图实验报告:
题目:数组程序设计内容,7.2 7.4 7.6 7.8之 N-S图选择排序,每趟都将 找到当前最小的元素 交换 到前边,共 N-1趟 则完成排序。
用 i代表当前的首位置,
min代表最小元素的标号。
筛法求 1- N内素数,
将 1-N之间的数存在数组,
挖去 1(将其值变为 0),
从 2开始,用 未被挖的数除其后未被挖的数,若能整除则挖去,到 sqrt(N)
即可 将所有非素数挖去,
输出未被挖的数即可插入排序,从第一个元素到最末一个元素,每次都将该元素插入其前的有序数组中,使得仍然有序。
为此,将其前元素逐个后移一位,一旦找到比此元素小的元素就停止,将元素放到此位置后矩阵乘法:矩阵乘法公式改进的插入排序自由落体问题,注意 边界分析,重点看第一次、第二次落地时变量的值是否正确,尤其看最后一次所求是否是第 10此落地经过的路程和第 10次反弹的高度作业说明
s=100
h=50
for(i=2;i<=10;i++)
h=h/2
s=s+2*h
输出 s与 h
保证边界不出错的关键在于思路要清晰,且赋予循环变量一定的含义。
§ 7-3字符数组
§ 7.3.1字符数组的定义
char c[ 5] ;
c[0]=′I′;c [ 1] =′ ′;c [ 2] =′a′;
c[ 3] =′m′;c [ 4] =′ ′;c[5]=′l′;c[6]=′k′;
注意:整型与字符型有时可以混用,两者占用的字节数与表示的范围不同。此外,数组名、变量名、
函数名不能重复
§ 7.3.3字符数组的引用例 7.6 输 出一个字符串。
#include <stdio.h>
void main()
{ char c[ 10] ={’I’,’ ’,’a’,’m’,’ ’,’a’,’ ’,
’b’,’ o’,′y′};
int i;
for(i=0;i<10;i++)
printf(″%c″,c[ i] );
printf(″ \ n″);
}
下标从 0开始!
char c[10]={?I?,?’?,?a?,?m?,,?h?,?a?,?p?,?p?,?y?};
char c[]={?I?,?’?,?a?,?m?,,?h?,?a?,?p?,?p?,?y?};
char c[10]={?I?,?’?,?a?,?m?}; /*其后元素自动为
‘ \0’*/
如果在定义字符数组时不进行初始化,则数组中各元素的值是不可预料的
§ 7.3.2&&7.3.4字符数组的初始化使用字符串常量对字符数组初始化:
char c[10]={"China″};
char c[10]=“China”
char c[]=“China”
注,char str[5]=“China”错
§ 7.3.5字符数组的输入输出
逐个字符输入输出,用格式符,%c”
将整个字符数组作为整体输入或输出。用,%s”格式符,输出时遇 第一个 ’ \0?结束(注意没有 \0或多个 \0如何),输入时自动在末尾加 ’ \0?
例,char strl[ 5],str2[ 5],str3[ 5] ;
scanf(″%s%s%s″,str1,str2,str3);
How are you?
注 (1)数组名相当于首地址,故不加地址符
(2)用 scanf函数输入多个字符串时以空格为分隔符
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 26
1,puts函数格式,puts (字符数组名 );
作用:逐个输出字符数组中元素,一旦遇 ‘ \0?,便结束输出并换行,返回换行符,失败时返回 -1
如,char str[]={“China\nBeijing”}; puts(str);
2,gets函数格式,gets(字符数组名 );
作用:从终端输入一个字符串到字符数组,自动在末尾加 \0,以 回车作输入结束标志,返回字符数组首地址如,gets(str); 输入,Computer↙,str赋值为 C o m p u t e r \0,共 9字符注意,用 puts和 gets函数只能输入或输出一个字符串,不能写成
puts(str1,str2) 或 gets(str1,str2);
7.3.6 字符串处理函数 <string.h>
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 27
3,strcat函数格式,strcat(字符数组 1,字符数组 2);
作用,连接两个字符数组中的字符串,把字符串 2接到字符串 1
第一个 \0的位置,返回字符数组 1的首地址如,char str1[30]={“People's Republic of”};
char str2[]=“China”;
printf(“%s”,strcat(str1,str2));
输出,People's Republic of China
4,strcpy函数格式,strcpy(字符数组 1,字符串 2);
作用,将字符串 2第一个 \0及其以前 的元素 复制到字符数组 1。
如,char str1[10],str2[]=“China”;strcpy(str1,str2);
注,变型 strncpy(str1,str2,2);此外,str1=str2不可
????
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 28
5,strcmp函数格式,strcmp(字符串 1,字符串 2);
作用:比较字符串 1和字符串 2。
如,strcmp(str1,str2); strcmp(“China”,“Korea”);
比较规则:两个字符串自左至右逐个字符相比,直到出现不同的字符或遇到‘ \0?为止。如全部字符相同,则认为相等;若出现不相同的字符,则以第一个不相同的字符的比较结果为准。
比较的结果由函数值返回
① 如果字符串 1=字符串 2,函数值为 0。
② 如果字符串 1>字符串 2,函数值为一正整数。
③ 如果字符串 1<字符串 2,函数值为一负整数。
注意:对两个字符串比较,不能用以下形式:
if (str1>str2) printf(“yes”);
而只能用 if (strcmp(str1,str2)>0) printf(“yes”);
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 29
6,strlen函数格式,strlen (字符数组 ) ;
作用:测试字符串长度的函数,返回 字符串有效字符个数 。
如,char str[10]={“China”}; printf(“%d”,strlen(str));
7,strlwr函数格式,strlwr (字符串 ) ;
作用,将字符串中大写字母换成小写字母 。
8,strupr函数格式,strupr (字符串 ) ;
作用,将字符串中小写字母换成大写字母 。
例 7.8 输入一行字符,统计其中有多少个单词
§ 7.3.7字符数组应用举例
flag=0;count=0
str=gets()
i=0
While((c=str[i])!=? \0?)
flag=0&&c!=
Y N
count++
flag=1
c=
Y N
flag=0
i++
输出 count
w o rd = 0 ; c o u n t = 0
对字符串中每个字符 c
图 6,21 例 6,13 主函数 N - S 图输入字符串 str
c 为空格
Y N
w o rd = 0
w o rd == 0
Y N
c o u n t ++
w ord = 1
输出单词个数 c o u n t
标记变量为 0
代表刚读过一个空格,
其它情况为 1
例 7.9 二维字符数组举例:求三个字符数组中最大者
char string[ 20] ;
char str[ 3][ 20] ;
int i;
for (i=0;i<3;i++)
gets (str[ i] );
strcpy(string,str[ 0] )
if (strcmp(str[ 1],string)>0)
strcpy(string,str[ 1] );
if (strcmp(str[ 2],string)>0)
strcpy(string,str[ 2] );
printf(″%s \ n″,string);
作业,7.9 7.12 7.14之 N-S图实验报告:
题目:字符数组程序设计内容,7.10 7.13 7.15之 N-S图操 作类别数组的定义 数组元素的引 用 数组初始化举例一维数组 类型说明符 数组名 [常量表达式 ] 数组名 [下标 ] int a[3]={1,2,3}
二维数组 类型说明符 数组名 [常量表达式 1] [常量表达式 2] 数组名 [下标 1] [下标 2]
int
[2][3]={{1,2,3},{4,5,6}}
一维字符数组
char 数组名 [常量表达式 ] 数组名 [下标 ] char str[4]=”ABC”
注意事项 数组长度表达式中不能含 变量,且大于 0 下标从 0开始,注意越界问题 元素引用前最好赋初 值,否则值随机存储:元素按序存储在连续的内存单元中,数组名代表存储区域起始地址,访问时根据名和下标计算相应元素的地址数组,用一组名同、下标不同的变量表示同一类型大批数据算法:递推 冒泡排序及其改进 选择排序 插入排序筛法 折半查找 数组逆序 出圈 ;矩阵乘法 矩阵自身转置杨辉三角 魔方阵 鞍点 ;字符或单词统计 字符串处理函数筛法求 1- N内素数,
将 1-N之间的数存在数组,挖去 1(将其值变为 0),从 2开始,
用 未被挖的数除其后未被挖的数,
若能整除则挖去,到 sqrt(N)即可 将所有非素数挖去,输出未被挖的数即可
for(i=0;i<100;i++)
a[i]=i+1
a[0]=0
for(i=1;i<sqrt(100);i++)
Y N
a[i]!=0
for(j=i+1;j<100;j++)
a[j]!=0
Y N
a[j]%a[i]=0
Y N
a[j]=0
for(i=0;i<100;i++)
Y N
a[i]!=0
输出 a[i]
( 1) C语言中数组下标从零始,
有两种处理方式,其一,舍弃
a[0]不用,定义 int a[101];其二,习惯 C语言,始终使用标号,
处理时用 for(i=0;i<N;i++)
( 2)中间多个分支结构可合并
(3)根据 N-S图写程序,关键在于花括号的使用冒泡排序,每一趟排序时,从首元素开始 相邻两个数进行比较,将小的换到前头,如此,
则每趟排序都会使当前,最大,
的数,沉到末尾,,小的数逐步,上升,,N-1趟则排序完毕。
fo r ( i = 0 ; i < N ; i ++)
输入元素 a [ i ]
fo r ( i = 1 ; i < = N - 1 ; i ++
fo r ( j = 0 ; j < N - i ; j ++)
Y N
fo r ( i = 0 ; i < N ; i ++)
输出元素 a [ i ]
a [ j ] > a [ j + 1 ]
a [ j ] < = > a [ j + 1 ]
图 6,9 例 6,4 主函数 N - S 图
/*i表趟 数,j表 前者的 下标 */
改进的冒泡排序选择排序,每趟都将 找到当前最小的元素 交换 到前边,共 N-1趟 则完成排序。
用 i代表当前的首位置,
min代表最小元素的标号。
f o r ( i = 0 ; i < 10 ; i ++)
输入元素 a [ i ]
f o r ( i = 0 ; i < 9 ; i ++)
m in = i
f o r ( j = i + 1 ; j < 10 ; j ++)
a [ m in ] > a [ j ]
Y N
m in = j
m in != i
Y N
a [ m in ] < = > a [ i ]
f o r ( i = 0 ; i < 10 ; i ++)
输出元素 a [ i ]
选择排序注意:指导书中 N-S图默认下标从 1开始,最好与 C
语法一致插入排序:从第二个元素到最末一个元素,每次都将该元素插入其前的有序数组中,使得仍然有序。为此,将其前元素逐个后移一位,一旦找到比此元素小的元素就停止,
将元素放到此位置后(自顶向下 逐步细化)
for(i=1;i<N;i++)
{
j=i-1;
temp=a[i];/*记录当前元素备用 */
while(a[j]>temp&&j>=0)
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
注意:数组元素后移时要从后向前逐个移,从前向后不可,务必分析原因魔方阵,int a[N][N]={0};i=0; j=N/2;a[i][j]=1;
for(k=2;k<=N*N;k++)
{
i=i-1;j=j+1;/*右上方 */
if(i<0&&j==N) /*第一行第 N列 */
{
i=i+2; j=j-1;/*因 i,j已改变 */
a[i][j]=k;
}
else if(i<0)/*第一行 */
i=N-1;
else if(j==N)
j=0;
if(a[i][j]!=0)
{i=i+2;j=j-1; /*因 i,j已改变 */}
a[i][j]=k;
}
8 1 6
357
4 9 2
鞍点,for(i=0;i<M;i++)
{
maxj=0;
for(j=1;j<N;j++)if(a[i][maxj]<a[i][j])maxj=j;
flag=1;
for(j=0;j<M;j++)
if(a[j][maxj]<a[i][maxj])flag=0;
if(flag==1)
{
count++;
printf(“第 %d个鞍点:,,count);
printf("a[%d][%d]=%d\n",i,maxj,a[i][maxj]);
}
}
if(count==0)
printf("没有鞍点 ");
8 1 6
357
4 9 2
折半查找,比较待查找数据与数组中间位置上元素,两者相等则找到,程序结束;
否则,前者大于后者说明待查找数据只可能在数组的后半部分,反之说明只可能在前半部分,当然也可能不在数组中。但无论哪种情况,
查找范围都将缩小一半。重复以上步骤,最多比较
log2N次就能得到结果,其中 N为数组长度。
输入待查找数据 num
fla g = 0 ; bo tt = 0 ; to p = N - 1
初始化有序数组 a [ N ]
num < a [ 0 ] || num > a [ N - 1 ]
Y
N
w hi le ( fla g == 0 && bo tt < to p )
m id =( bo tt + to p )/ 2
输出
num
不在数组中
lo c a = m id
to p = m id - 1 b o tt= m id + 1
num == a [ mid ]
N
num < a [ m id ]
Y
Y N
fla g = 1
b o t t = t o p && num = a [ b o t t ]
Y
N
lo c a = bo tt ; fla g = 1
f l a g == 1
Y
N
输出元素位置 不在数组中图 6,13 例 6,7 主函数 N - S 图