第 10讲一维数组与字符数组
以后会越来越难,因此一定要对前面的知识及时理解和掌握。
看懂、听懂并不等于会用。
课堂上时间有限,大家一定要及时预习和复习。
复习时注意只需要把我课上讲的几个例题理解透彻并掌握即可
注意:思路!算法!
2
作业 1:求 60个学生的最高分
算法:
输入 60个学生的成绩
依次比较,找出最高分
输出最高分。
3
方法一:
#include <stdio.h>
#define N 60
void main()
{ int a[N],max;
printf("Input %d score:\n",N);
for(i=0;i<=N-1;i++)
scanf("%d",&a[i]);
max=a[0]; /*假设第一个元素最大 */
for(i=1;i<=N-1;i++)/*依次拿当前最大值与下一个元素比较 */
if(a[i]>max)
{ max=a[i]; }
printf("\n The maximum score is %d,\n ",max);
}
4
方法二:
#include <stdio.h>
#define N 60
void main()
{ int a[N],max_i;
printf("Input %d score:\n",N);
for(i=0;i<=N-1;i++)
scanf("%d",&a[i]);
max_i=0; /*假设最大值对应的下标为 0*/
for(i=1;i<=N-1;i++)
if(a[i]>a[max_i])
{ max_i=i; } /*求最大元素对应的下标 */
printf("\n The maximum score is %d,\n ",a[max_i]);
}
5
作业 2:求 60个学生的平均分
算法:
输入 60个学生的成绩
计算总分,平均分
输出平均分
#include <stdio.h>
#define N 60
void main()
{ int a[N],sum;
printf("Input %d score:\n",N);
for(i=0;i<=N-1;i++)
scanf("%d",&a[i]);
sum=0;
for(i=0;i<=N-1;i++) /*求和 */
sum+=a[i];
printf("\n aversge=%.1f,\n ",(float)sum/N);
}
6
例 6- 1 对 200个学生成绩从大到小排序
算法
输入 200个成绩
排序
输入排序结果
7
冒泡法 对 N个数从大到小排序:
第 0趟排序:比较 a[0]和 a[1],不满足顺序交换,
再比较 a[1]和 a[2],不满足顺序交换,依此类推,
直至 a[N-2]和 a[N-1]比较,不满足顺序交换,
通过这一趟的两两比较找到第 1个最小的数放在
a[N-1]的位置
……
第 J趟排序:比较 a[0]和 a[1],不满足顺序交换,
再比较 a[1]和 a[2],不满足顺序交换,依此类推,
直至 a[N-j-2]和 a[N-j-1]比较,不满足顺序交换,通过这一趟的两两比较找到第 j+1个最小的数放在 a[N-j-1]的位置
共 N-1趟
for(j=0;j<=N-2;j++)
{ /*第 j趟排序 */
}
/*通过依次比较 a[I]和 a[I+1],不满足顺序交换 */
for(i=0;i<=(N-1)-(j-1);i++)
if(a[i]<a[i+1])
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
8
#include <stdio.h>
#define N 200
void main()
{ int a[N],i,j,t;
printf("Input %d score:\n",N);
for(i=0;i<=N-1;i++)
scanf("%d",&a[i]);
for(j=0;j<=N-2;j++) /*冒泡法排序 */
for(i=0;i<=N-j-2;i++)
if(a[i]<a[i+1]) /*若从小到大排序,改成 >*/
{ t=a[i]; a[i]=a[i+1]; a[i+1]=t; }
printf(" \n The sorted score:\n");
for(i=0;i<=N-1;i++)
{ if(i%15==0) printf("\n");
printf("%4d ",a[i]);
}
} /*书中 P167的源代码改为 for(i=0;i<=N-j-2;i++) */
例 6- 1完整程序,冒泡法
9
选择法 对 N个数从大到小排序
第 0趟排序:从 a[0]至 a[N-1],比较找出其中最大数所在的下标 k,若 k!=0,说明 a[k]比 a[0]
大,则交换 a[0]和 a[k],通过这一趟的比较找到第 1个最大的数放在 a[0]的位置
……
第 J趟排序:从 a[j]至 a[N-1],比较找出其中最大数所在的下标 k,若 k!=j,说明 a[k]比 a[j]
大,则交换 a[j]和 a[k],通过这一趟的比较找到第 j+1个最大的数放在 a[j]的位置
共 N-1趟
for(j=0;j<=N-2;j++)
{ /*第 j趟排序,通过这一趟排序,找到第 j+1大的数存于 a[j]*/
}
/*从 a[j]至 a[N],比较找出其中最大数所在的下标 max_i */
/*若 max_i!=j,说明 a[max_i]比 a[j]大,则交换 */
max_i=j;
for(i=j+1;i<=N-1;i++)
if(a[i]>a[max_i])
{max_i=i;}
if(max_i!==j)
{t=a[max_i]; a[max_i]=a[j]; a[j]=t; }
10
#include <stdio.h>
#define N 200
void main()
{ int a[N],i,j,max_i,t;
printf("Input %d score:\n",N);
for(i=0;i<=N-1;i++)
scanf("%d",&a[i]);
for(j=0;j<=N-2;j++) /*选择法排序 */
{max_i=j;
for(i=j+1;i<=N-1;i++)
if(a[i]>a[max_i]) /*若从小到大排序,改成 <*/
{max_i=i;}
if(max_i!==j)
{t=a[max_i]; a[max_i]=a[j]; a[j]=t; }
}
printf(" \n The sorted score:\n");
for(i=0;i<=N-1;i++)
{ if(i%15==0) printf("\n");
printf("%4d ",a[i]);
}
}
例 6- 1完整程序,选择法
11
查找算法
顺序查找:按数组下标顺序查找
二分法查找(折半查找)
我们查字典的时候怎样查找?
在 已经排好序的情况下 可以进行二分查找。
过程:先找到查找区域的中点,如果中间比要找的值小,说明要找的值在右半边,反之,在左半边,相等则表示找到。若没有找到,在新的查找区域,继续这样查找,直至所有的区域都找到。
12
二分法程序
#include <stdio.h>
#define N 200
void main()
{ int a[N],left,right,mid,x,find_i=-1;
left = 0;
right = n - 1;
printf(“please input the number to search:”);
scanf(“%d”,&x); /*输入要找的数 x*/
while (left < right&&find==-1) /*还有区域没找,而且目前还未找到 */
{ mid = (left + right) / 2; /*求区域的中点 */
if (x > a[mid]) /*设定右边为新的查找区 */
{ left = mid + 1;
}
else if (x < a[mid]) /*设定左边为新的查找区 */
{ right = mid - 1;
}
else
{ find_i=mid;break; /*找到,结束 */
}
}
if(find_i==-1) /*find_i的值没变,表示没找到 */
printf(“not found!”);
else
printf(“a[%d]=%d”,find_i,x);
}
13
小结
我们已经讲了数组的最常见的应用
查找最大值、特定值
计算总和、平均分
排序?当数组里存储的是字符串时该怎样修改前边例题的程序?
14
例:输入一个字符串,统计这个字符串中有多少个英文字母?
算法:
输入 string
统计英文字母的个数 number
输出 number
15
程序
#include<stdio.h>
void main()
{int i,number=0;
char a[30];
puts(“please input a string:”);
gets(a); /*一次性输入字符串,存入 a数组中 */
for(i=0;a[i]!=?\0?;i++) /*统计 */
{ if(a[i]>?a?&& a[i]<?a?)||(a[i]>?A?&& a[i]>?Z?)
{number++;
}
}
printf(“the string,%s has %d letter!\n",a,number);
}
gets()是 C语言库函数,gets(a)的含义是:将从键盘上 输入 的一串字符存储在数组 a中。
也可用 scanf(“%s”,a);实现输入,
注意 a是数组名,表示数组的起始地址,因此 不用再写&
二者的区别是前者可以接收空格,
后者遇到空格默认输入结束
输出可以用 puts(a),也可以用
printf (“%s”,a);两者的区别在于前者在输出字符串后还多输出一个回车。
/*一般字符数组中存储的字符串长度不定,所以循环条件不能用
I<30这样的语句限定,而应用
a[i]!=?\0?作为循环结束条件 */
16
例 6- 5
查找字符在字符串中出现的位置
算法
定义字符数组用来存储字符串
查找
输出查找结果
17
#include<stdio.h>
void main() /*在一个固定的字符串中查找是否存在空格 */
{int i,counter=0;
char a[30]="I am a teacher.";
/*一般用字符串常量对 字符数组初始化,也可以用
char a[30]={?I?,,?a?,?m?,,?a?,,?t?,?e?,?a?,?c?,?h?,?e?,?r?,?.?};
系统会将未赋值的数组元素自动赋值为 ‘ \0?,*/
for(i=0;a[i]!=?\0?;i++) /*查找 */
{ if(a[i]==)
{printf(“在字符串 %s 中的位置为空格 。 \n",i+1);
counter++;
}
}
printf(“the string,%s has %d space!\n",a,counter);
}
若想实现,在任意字符串中查找是否存在任意要找的字符,。
18
#include<stdio.h>
void main() /*在任意字符串中查找是否存在一个任意字符 */
{ int i,p=-1;
char a[30],ch;
puts(“please input a string:”);
gets(a); /*输入 */
puts(“please input a character to search:”);
ch=getchar();
for(i=0;a[i]!='\0';i++)
{ if(a[i]==ch) /*找到即结束 */
{ p=i;
break;
}
}
if(p!=-1) /*根据 p的值判断是否找到 。 */
printf("字符 %c 在字符串 %s 中的位置为,%d 。 \n",ch,a,p+1);
else
printf("字符 %c 在字符串 %s 中没有找到 。 \n",ch,a);
}
19
字符数组与数值型数组的区别
字符型数组定义时长度要尽量大一些,
至少要为 ‘ \0?留出位置。
字符型数组的输入输出一般 不用循环 实现
对字符型数组进行循环操作时,一般循环条件为:遇到 ‘ \0?结束。或者也可用
i<strlen(a)作为循环条件。
20
与字符串相关的库函数
在 <string.h>中定义了若干专门的字符串处理函数
strlen,
strlen(字符串 );
返回字符串的实际长度,即不包括 ‘ \0?的实际字符个数
strcpy:
strcpy(目的字符串,源字符串 );
strcat:
strcat(目的字符串,源字符串 );
strcmp:
strcmp(字符串 1,字符串 2);
当出现第一对不相等的字符时,就由这两个字符决定所在字符串的大小
返回其 ASCII码比较的结果值
作业 1,P178
还有两个函数,
请自学。
21
求三个字符串中最大的一个
算法:
输入字符串 str1,str2,str3
比较 str1和 str2,将最大值赋给 strmax
再拿 strmax和 str3进行比较,若 str3大,
再将 str3赋值给 strmax。
输出 strmax
22
#include <stdio.h>
#include <string.h>
#define N 50
main()
{ char str1[N],str2[N],str3[N],strmax[N];
printf(“Please enter three strings:\n”);
gets(str1); gets(str2); gets(str3);
/*输入三个字符串 */
if (strcmp(str1,str2) > 0) /*求前两个字符串的最大值 strmax*/
strcpy(strmax,str1);
else
strcpy(strmax,str2);
if (strcmp(str3,strmax) > 0) /*求 strmax和 str3的最大值 */
strcpy(strmax,str3);
}
printf("The max is:");
puts(strmax);
}
程序
23
错误 2,if (str1 > str2)
最容易出现的错误
错误 1,str1 = str2;
字符串不能直接整体复制!
strcpy(str1,str2); /*正确 */
也不能用关系运算符比较大小
if (strcmp(str1,str2) > 0) /*正确 */
写错也不会提示语法错误,为什么?
24
例 6- 7 判断回文数
例,123454321是回文数
再例,12345321不是回文数
算法:
1 2 3 4 5 3 2 1 \0 \0 \0
i=0 j=strlen(str)-1
str
i=1 j=strlen(str)-2……
25
#include <stdio.h>
#include <string.h>
void main()
{ int i,j,equal=1;
char str[20];
printf("Input a string,");
scanf("%s",str);
for(i=0,j=strlen(str)-1;i<j&&equal;i++,j--)
{ if(str[i]!=str[j])
{ equal=0;
}
}
if(equal)
printf("\n %s is a palindrome!\n",str);
else
printf(" %s isn't a palindrome!\n",str);
}/*勘误,P175- sizeof(a)改成 strlen(a),最前边加 #include <string.h> */
例 6- 7 程序
26
本讲小结
一维数组的相关程序设计
求最大值、排序、查找等
注意数值数组与字符数组的区别
几个用于字符串处理的库函数
字符数组的编程题目是经常考的。
下节课讲数组名作函数参数,请提前预习
27
思考题与作业:
思考题:
如何将我们写的这些程序分别写成函数?这些函数又将如何调用?
作业:
仿照例 6- 6的程序实现
strlen(),strcat(),strcmp()三个程序的功能,
但其中不能用到这三个库函数。
自学:本课件中未讲到过的例题。