数5-数组 数据结构 幻灯片课件.pptVIP

2001 -- 4 --2; 第五章 数组和广义表 引言： 线性表：L=(a1,a2,...,an)，ai是同类型的元素，1≤i≤n 数组: A=(a1,a2,...,an) 若ai是同类型的元素，A是一维数组，1≤i≤n 若ai是同类型的定长线性表，A是多维数组，1≤i≤n 广义表：Ls=(a1,a,...,an) ai可以是同类型的元素或不定长的线性表，1≤i≤n 5.1 数组及其操作 简单地说，向量和矩阵称为数组。 5.1.1 数组的递归定义 1.一维数组是一个定长线性表(a1,a2,...,an )。 其中：ai为元素，i为下标/序号，1≤i≤n (a1,a2,...,an )又称为向量。;2.二维数组是一个定长线性表(?1,?2,...,?m)， 其中: ?i=(ai1,ai2,...,ain)为行向量，1≤i≤m 由m个行向量组成，记作：;3.三维数组是一个定长线性表( ?1,?2,...,?p )。 其中: ?k=( ?1,?2,...,?m )为定长二维数组，1≤k≤p 例 三维数组A[1..3,1..4,1..2], p=3, m=4, n=2;例2 #define m 4 //定义符号常量m #define n 5 //定义符号常量n int a[m]； //m个整数的一维数组 char b[m][n]； //m行n列个字符的二维数组 例3 #define m 4 //定义符号常量m #define n 5 //定义符号常量n typedef int ara[m]； //一维数组类型ara typedef char arb[m][n]； //二维数组类型arb ara a； //ara类型的变量a arb b； //arb类型的变量b ?? C语言中定义静态数组时，元素数目必须是常量 错例1 int m=4,n=5； int a[m][n]； //m,n是变量 错例2 int p； scanf(”%d”,p)； int c[p]； //p是变量;5.2数组的顺序表示和实现 5.2.1顺序表示(顺序存储结构） 1.以行序为主序的顺序存储方式 左边的下标后变化，右边的下标先变化 2.以列序为主序的顺序存储方式 左边的下标先变化，右边的下标后变化 例1 二维数组a[1..3,1..2],b是首地址,s是元素所占的单元数 ;例2 三维数组a[1..2,1..3,1..2];5.2.2数组的映象函数 数组元素的存储地址 例1 一维数组a[0..n-1] 设:b为首地址,s为每个元素所占的存储单元数 则:元素a[i]的存储地址： Loc(i)=Loc(0)+i*s=b+i*s 0≤i≤n-1 ; 元素a[i]的存储地址 Loc(i)=Loc(1)+(i-1)*s=b+(i-1)*s 1≤i≤n 例3 二维数组a[1..m,1..n],假定无零行零列;例3 二维数组a[1..m,1..n],假定无零行零列;例4 二维数组a[0..m-1,0..n-1]（有零行零列）;例4 二维数组a[0..m-1,0..n-1]（有零行零列）;例5 三维数组a[1..p,1..m,1..n],假定无0页0行0列 1)以行序为主序，a[k][i][j]的地址为 Loc(k,i,j)=Loc(1,1,1)+(m*n*(k-1)+n(i-1)+j-1)*s =b+(m*n*(k-1)+n(i-1)+j-1)*s 1≤k≤p, 1≤i≤m, 1≤j≤n 其中： b为首地址，s为每个元素所占的存储单元数 p---页数 n--列数 m-行数 (2)以列序为主序，a[k][i][j]的地址为 Loc(k,i,j)=Loc(1,1,1)+(p*m*(j-1)+p*(i-1)+k-1)*s =b+(p*m*(j-1)+p*(i-1)+k-1)*s 1≤k≤p, 1≤i≤m, 1≤j≤n 其中： b为首地址，s为每个元素所占的存储单元数 p-