C语言 数据的组织结构(一)

错误赋值方法 vote[10]= {10,2,3,6,8,9,12,7,4,5} 或:vote= {10,2,3,6,8,9,12,7,4,5}
数组输出
for( i=0; i<10; i++) {
printf(“%d\t”, vote[i]); }
#include <stdio.h>
选
开始
数组元素值 为得票数，
二分查找Key
Y
N
存在Key
输出成功
输出失败
结束
开始
low=0；high=NUM-1； P95流程图b
N
low<=high
Y mid=中央位置
Y
value[mid]==key
N
结束
Y
value[mid]<key
N
low=mid+1
high=mid-1
#include <stdio.h> #define NUM 10 main () {
int vote[10]={0}; for( i=0; i<n; i++ )
vote[i]++;
下标表达式的值一定要在下标取值范围内
给数组赋值
利用下标 for( i=0; i<10; i++)
scanf(“%d”, &vote[i]);
或者 for( i=1; i<=10; i++)
scanf(“%d”, &vote[i-1]);
假设排序过程中，待排记录序列的状态为：
有序序列R[1..i-1] 无序序列 R[i..n]
第i趟 选择排序
从中选出 关键字最小的记录
有序序列R[1..i] 无序序列 R[i+1..n]
开始 输入待排序整数数列
显示整数数列
0→ i
N i< N U M -1 Y
将 i~ N U M -1 之 间 最 小 值 的 下 标 → m in Valu e
for (i=0; i<26; i++)
printf("\n\'%c\':%d", 'A'+i, letter[i]);
}
顺序查找
查找是最常见、最基本的操作. 查找成功：依据查找关键字，只要找到 与关键字相同的记录，即查找成功 查找不成功：所有记录数据中没有与关 键字相同的记录
例：某班级35名学生，检查是否存在不 及格的学生。
/* 累加票数 */
2
/* 输出选票 */ printf("\n The amount of votes is :"); for (i=0; i<NUM; i++) {
printf("%4d", vote[i]); }
/* 计算最高得票数量 */ winner = 0; for (i=1; i<NUM; i++) {
#define NUM 10 main( ) {
/* 候选人人数 */
举 问 题 算
定义数据结构
输入数据
下标表示候 选人。
int vote[NUM] = {0}; // 用于存放每位候选人得票数量的数组，初始化0 int code, i, winner;
/* 职工投票 */ printf("\nEnter your selection<0 end 10>:\n");
//有序表二分查找 low = 0; high = NUM-1; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if (value[mid]==key ) break; // 找到待查元素 if ( value[mid]<key ) low = mid + 1; // 继续在后半区间进行查找 else high = mid - 1; // 继续在前半区间进行查找 }
例如: key=20 的查找过程如下：
ST.elem
ST.length
05 13 19 21 37 56 64 75 80 88 92
0 1 2 3 4 5 6 7 8 9 10 11
high mid low
查找不成功的条件：low > high
开始 构造非递减数组value
P95流程图a
输入key
4
例如: key=64 的查找过程如下：
ST.elem
ST.length
05 13 19 21 37 56 64 75 80 88 92
0 1 2 3 4 5 6 7 8 9 10 11
low
low high
high
mid mid mid
low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2
if (vote[i]>vote[winner]) winner = i;
}
/* 输出得票最高的所有候选人 */ printf("\nThe winner :"); for (i=winner; i<NUM; i++) {
if (vote[i]==vote[winner]) printf(“%3d\n",i+1);
void main( )
{
int letter[26] = {0}; //存放26个累加器的一维数组
char ch;
//存放输入的字符
int i;
//循环输入文本字符，并统计每个英文字母出现的次数
printf("\nEnter text line\n");
while ((ch=getchar()) != '\n') {
每个元素均为整型，记录得票数。 数组元素下标从0开始，所以第5个元素 的下标是4，即第5个元素是：vote[4] 存放在10个连续的地址空间。数组占存 储空间的大小：
元素数量*每个元素储存空间大小
通用公式 vote 元素1
vote+m 元素2 ……..
vote+(i-1)*m 元素i ……..
vote+（n-1)*m 元素n
每个元素所占用 的存储单元大小
Loc(i)=Lo+（i-1)*m
一维数组初始化
定义数据结构时即初始化全部元素 int vote[10]={10,2,3,6,8,9,12,7,4,5}
可以省略
int vote[]={10,2,3,6,8,9,12,7,4,5}
有多少个初始值，数组默认大小就是多大。
int vote[10]={0} //全部初始化为0
5
排序
排序是计算机内经常进行的一种操作，其 目的是将一组“无序”的记录序列调整为“有 序”的记录序列。
例如：将下列关键字序列
52, 49, 80, 36, 14, 58, 61, 23, 97, 75
不使用另外数组调整为
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97
选择排序
Y
N
m in Valu e!= i
int score[NUM]; int i;
/* 随机产生35个考试成绩 */
randomize( );
//初始化随机数生成器，tc3
for (i=0; i<NUM; i++) {
score[i] = random(100);
//产生随机数
}
/*返显35名学生的考试成绩，作为测试*/ /*顺序查找是否存在不及格的学生*/ /*输出查找结果*/
}
#define NUM 35 /*学生人数*/ main( ) {
int score[NUM]; int i;
/* 随机产生35个考试成绩 */ ……
/*返显35名学生的考试成绩，作为测试*/ for (i=0; i<NUM; i++) {
printf("\nNo.%d: %d", i+1, score[i]); }
} }
二、编程实例
按条件对数据筛选 /* 获得最高得票数的下标 */
winner = 0; for (i=1; i<NUM; i++) {
if (vote[i]>vote[winner]) winner = i;
}
按条件对数据筛选 /* 获得最高得票数的数值 */
winner = vote[0]; for (i=1; i<NUM; i++) {
1
一维数组初始化
对部分元素赋初值 int vote[10]={10,2,3,6}
不可以省略
只对前4个元素赋了初值。
int vote[10]={10,2,3,,6}
对前3个元素和第5个元素赋了初值。
一维数组元素的引用及基本操作
引用数组元素： <数组变量名>[<下标表达式>]，如： vote[0]，vote[1]，vote[2]，…
第4讲 数据的组织结构（一）
一、一维数组 二、编程实例（顺序查找、二分查找、选择排序） 三、字符数组与字符串 四、二维数组
一、一维数组
数组的特点
每个数组元素数据类型要相同 很方便对每个数组元素实施相同的操作 预知数组元素个数
实例1：某部门，需要由全体员工推选一名办 公室主任。假设有10名候选人。编程序统计每 个候选人的得票数量，得票最多当选，给出选 举结果。 10个人的情况一样（得票数、累计） 统计10人情况给出选举结果。 数据结构---用一维数组存储10个人的得票数。
3
#define NUM 35 /*学生人数*/ void main( ) {
int score[NUM]; int i;
/* 随机产生35个考试成绩 */
/*返显35名学生的考试成绩，作为测试*/
/*顺序查找是否存在不及格ห้องสมุดไป่ตู้学生*/
/*输出查找结果*/ }
#define NUM 35 /*学生人数*/ main( ) {
…… /*输出查找结果*/ if (i<NUM)
printf("\nNot all pass."); else
printf("All pass."); }
二分查找
[P93，例4-5] 例：已知一个非递减有序整数数列 （05，13，19，21，37，56，64，75， 80，88，92）。 请编写一个程序，查找其中是否存在与给定key 值相等的数。 能否用顺序查找？ 尝试另一种效率更高的方法。
/*顺序查找是否存在不及格的学生*/ /*输出查找结果*/ }
#define NUM 35 /*学生人数*/ main( ) {
int score[NUM]; int i; /* 随机产生35个考试成绩 */ /*返显35名学生的考试成绩，作为测试*/
/*顺序查找是否存在不及格的学生*/ for (i=0; i<NUM; i++) {
int value[NUM]={5,13,19,21,37,56,64,75,80,88}; int low,high,mid,key; printf("\nEnter a key:"); scanf("%d", &key); // 二分查找
;
// 输出查找结果 if( low<=high ) printf("\n%d is found at %d", key, mid); else printf("\n%d is not found.", key); }
if ('A'<=ch && ch<='Z') //检测是否为大写字母
letter[ch-'A'] = letter[ch-'A']+1;
else
if ('a'<=ch && ch<='z') // 检测是否为小写字母
letter[ch-'a'] = letter[ch-'a']+1;
}
/* 输出每个英文字母出现的次数 */
法
处理数据
do { scanf("%d", &code); if (code<0 || code>NUM) {
// 检验输入的编码是否有效
printf("\nInvalid vote.");
输出结果
continue; }
if (code!=0)
结束
vote[code-1] = vote[code-1]+1; } while (code!=0); //while(code)
if (vote[i]>winner) winner = vote[i];
}
按条件对数据统计
例：
键盘输入一段文本，以回车换行结束
统计其中每个英文字母出现的频率
分析
存储26个英文字母出现频率：
int letter[26]; 初值为0
循环中逐个输入字母，判别如是字母，对应位置 加1。注意大小写均可。循环结束为输入回车换 行符。
if (score[i]<60) break; }
/*输出查找结果*/ }
#define NUM 35 /*学生人数*/ main( ) {
int score[NUM]; int i; /* 随机产生35个考试成绩 */ /*返显35名学生的考试成绩，作为测试*/ /*顺序查找是否存在不及格的学生*/
类型定义
<元素数据类型> <数组变量名>[<元素数量>];
分析：
全部数组元素都是所定义的元素数据类型 数组变量命名与通常变量命名方式相同 必须说明元素数量，即为常量。 连续的存储空间。 int vote[10]； //存储每个人得票数
int vote[10]；
vote
0 1 2 3 4 5 6 7 8 9 下标