[理学]教学-第4章 数据组织开始到二维数组.ppt

排序中“每一个数据”是指数据位置，如上面第0趟扫描就是第0个数据位置(比较过程可能交换数据，数据发生了变化，但后面的比较仍然是与第0个数据比较)。一趟扫描得到一个最小者放到了最前面。 第i趟扫描就是第i个元素与所有第j个元素比较(j=i+1，i+2，…，N-1)，可能需要交换。 数组的名字与下标决定了数组的所有元素。建议读者反复练习冒泡排序与选择排序，上机实现并理解排序思想，画图理解数据在内存中的存储形式与变化过程。 选择排序的PAD图描述如图4.5所示： 图4.5 “选择排序”的PAD图 i=0 iN-1 i++ j=i+1 jN j++ 交换a[i]与a[j] a[i] a[ j ] 写一个程序，输入一串十六进制数据，输出其十进制数。 【分析】 用数组存储输入的十六进制数据，边输入边存储，并记录数据长度； 设一个变量digit10存放结果，初值为0，从数组读出一个数字字符c,做digit10 ← digit10 *16+c对应的数值，最后的S就是想要的结果； 注意到十六进制数中有数字字符‘0’～‘9’，还有字母‘a’～‘f’和‘A’～‘F’，c对应的数值要相应处理。 4.1.2 二维数组 二维数组在逻辑上组成一个阵列(象线性代数里的矩阵)，但在物理上，占用的内存仍然是一片连续的空间，每一行开头紧接上一行的末尾，每一个数据元素用两个下标索引。在定义二维数组时，规定了行数和每行的列数，所以系统知道在什么位置切分每一行。 【例4-5】打印出以下的杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 【分析】 如果把杨辉三角存成如下形式： 则很容易看出其变化规律：每行第0列的值都为1，对角线上的元素也都为1；其它元素为上一行的同列和左列元素之和。 第 0 列 第 1 列 第 2 列 …… 第0行 第1行 第2行 …… 图4.7 二维数组的存储形式 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 如果把这一片存储空间取个名字叫a, 那么这个规律可以表达为： ai0=aii=1 (i=0，1，2，…，N-1) aij=ai-1,j+ai-1,j-1 (i=2，3，…，N-1；  j=1，2，…， i-1) C语言提供了二维数组(所谓二维就是用行号和列号才能定位一个数据)。上面的表达式用C表达为： a[i][0]=a[i][i]=1 a[i][j]=a[i-1][j] + a[i-1][j-1] 对于i,j的变化可用for循环实现。 上面用两个括号表达了二维数组a的元素下标，在引用这些元素之前，必须先定义才能得到这样一片空间(杨辉三角几乎浪费了一半的空间，但处理方便)。 这些数据都是整数，定义为int a[N][N]就可以了。注意N一定是常数。 算法： ① 生成第0列和对角线元素； ② 生成其它元素； ③ 输出。 【说明】 ① 定义二维数组有三个要素：数组类型、数组名、数组每一维的长度。行长度(行数)和列长度(列数)都必须是常数(或常数表达式)，但行数和列数不一定相等。 二维数组的定义格式： 数据类型 数组名[行数][列数] ② 规定行下标和列下标都从0开始。如本例的下标取值范围从0到N-1. ③ 引用二维数组的元素时，两维的下标可以是表达式，但取值范围千万不能超界。 ④ 二维数组元素在内存中仍然是顺序存放的，元素排列的顺序是按行存放。 如，数组int X[3][4] 的12个元素的存放顺序是： X[0][0]、X[0][1]、X[0][2]、X[0][3] X[1][0]、X[1][1]、X[1][2]、X[1][3] X[2][0]、X[2][1]、X[2][2]、X[2][3] 3 1 4 1 5 9 2 6 5 3 5 8 0 1 2 3 ←列 0 1 2 ↑ 行 1 4 1 3 6 2 9 5 8 5 3 5 内存单元 ↑ 数组首地址 ⑤ 初始化： 二维数组初始化可以像一维数组一样依照存放顺序依次赋值，如： int X[3][4]={0,1,2,3,10,11,12,13,20,21,22,23} 也可以按行进行赋值，如： int X[3][4]={{0,1,2,3},{10,11,12,13},{20,21,22,23}} 同样，初始化时也可以只给部分元