计算机二级 构造型数据结构.ppt

计算机二级 构造型数据结构
第1页，共20页，编辑于2022年，星期三
1
一维数组的定义
一维数组的定义形式：
类型名 　数组名 [常量表达式]
『说明』
类型名：数组元素的类型，它们可以是基本类型，如int 、f素初值为0。
定义动态数组时，如果不赋初值，数组元素的值不确定， 如 int a[10] 的每个元素的值可以是-32768～32767之间的一个整数
一维数组的初始化
第8页，共20页，编辑于2022年，星期三
8
一维数组初始化的一般形式：
static 数据类型 数组名[常量表达式]＝{初值表}
对所有数组元素赋初值：
int a[5]={1,2,3,4,5}; —— a: 1 2 3 4 5
static int b[3]={3,4,5}; —— b: 3 4 5
对部分数组元素赋初值
int a[5]={1,2,4}; —— a: 1 2 4 0 0
static b[3]={0,3}; —— b: 0 3 0
按顺序赋值，不能跳过前面的元素给后面的元素赋值
初值个数少于元素个数，自动给后面的元素补0；初值个数多于元素个数，出错！
初始化不指定数组长度，元素个数等于所赋初值的个数
int a[]={1,2}; —— a: 1 2 即等同于 int a[2]={1,2}
第9页，共20页，编辑于2022年，星期三
9
一维数组引用举例：使用冒泡法对数据进行排序
冒泡法思想：
通过相邻两个数之间的比较和交换，使数值较小的数逐渐从底部移向顶部，数值较大的数逐渐从顶部移向底部。就像水底的气泡一样逐渐向上冒，故而得名。
冒泡排序的过程
设有A[1] ～A[n] 组成的n个数据，要从小到大排序：
首先将相邻的A[1]与A[2]进行比较，如果A[1]的值大于A[2]的值，则交换两者的位置，使较小的上浮，较大的下沉；接着比较A[2]与A[3]，同样使小的上浮，大的下沉。依此类推，直到比较完A[n-1]和A[n]后，A[n]为具有最大数值的元素，称第一趟排序结束。
然后在A[1]~A[n-1]区间内，进行第二趟排序，使剩余元素中数值最大的元素下沉到A[n-1]；
重复进行n-1趟后，整个排序过程结束。
第10页，共20页，编辑于2022年，星期三
10
『』用冒泡法对10个整数排序（由小到大）
main( )
{
int i, j, t, a[10];
printf("input 10 numbers:\n");
for (i=0; i<10; i++) /*输入数组元素数据，使用a[1]～a[10]*/
scanf(“%d”,&a[i]);
printf(“\n”);
for (i=0; i<=8; i++) /*外循环：控制比较趟数*/
for (j=0; j<=8-i; j++) /*内循环：进行每趟比较*/
if (a[j]>a[j+1]) /*如果a[j]大于a[j-1],交换两者的位置*/
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
printf(“The sorted numbers: \n”);
for (i=0; i<10; i++) /*输出排序后数据*/
printf(“%3d”,a[i]);
}
重要例题
第11页，共20页，编辑于2022年，星期三
11
一维数组引用举例：使用选择法对数据进行排序
选择法思想：
设有A[1] ～A[n] 组成的n个数据，从小到大排序：
首先在A[1]和A[n]范围内，选择最小的数与A[1]交换，然后在A[2]~A[n]区间内，再选出最小的数与A[2]交换，重复进行n-1趟后，整个排序过程结束。
从A[i]~A[n]中选出最小的值并与A[i]交换可以采用下面的方法：引入变量j和k，j初值为i+1，k初值为i，反复比较A[k]和A[j]的值，若A[k]>A[j]，则将j的值赋给k，每进行一次比较后，j加1。当j=n，同时k≠i时，交换A[i]和A[k]。
第12页，共20页，编辑于2022年，星期三
12
『』用排序法对10个整数排序（由小到大）
main( )
{
int i, j, k,t, a[11];
printf("input 10 numbers:\n");
for