数结的 华中科技大学 计算机学院(5) 200c42
2001 -- 4 --2 华中科技大学 数据结构 计算机学院(5)
第五章数组和广义表 引言: 线性表:L=(a1,a2,,,an),ai是同类型的元素,1≤i≤n 数组:A=(a1,a2,,an) 若a是同类型的元素,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) 其中:a;为元素,i为下标/序号,1≤i≤n (a1,a2,,an)又称为向量
第五章 数组和广义表 引言： 线性表：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,a2, am), 其中:∝1(a1,a;2,,ain)为行向量,1≤i≤m 由m个行向量组成,记作: a11 a12 .. aIn a21a22 a2n 即An*n=((a1a12.a1n),(a21a22...an),,,(an1an2.am)) 或由n个列向量组成,记作: a 12 ain a a a n mxn an
2.二维数组是一个定长线性表(1,2,...,m)， 其中: i=(ai1,ai2,...,ain)为行向量，1≤i≤m 由m个行向量组成，记作： ( a11 a12 ... a1n ) ( a21 a22 ... a2n ) ............ ( am1 am2 ... amn ) Am*n= 即 Am*n=((a11 a12 ...a1n),(a21 a22 ...a2n),...,(am1 am2 ...amn)) 或由n个列向量组成，记作： a11 a12 a1n a21 a22 a2n am1 am2 amn Amxn =
3.三维数组是一个定长线性表(β1,β2,,B) 其中:βk=(1,α2,,am)为定长二维数组,1≤k≤p 例三维数组A[1..3,1..4,1..2],p=3,m=4,n=2 a 312 a211a212 a321a322 a11la112 a221a222 a331a332 a12la122a231a32 A3*4#2 a341a342 a131a132|a241a242 a141a142 第3页 第2页 第1页 5.1.2数组的类型定义和变量说明: 例1inta[10]; //10个整数的一维数组 char b[4[5] //4行5列个字符的二维数组 float c[3][4][2]; //3米4米2个实数的三维数组
3.三维数组是一个定长线性表( 1,2,...,p )。 其中: k=( 1,2,...,m )为定长二维数组，1≤k≤p 例 三维数组A[1..3,1..4,1..2], p=3, m=4, n=2 a111 a112 a121 a122 a131 a132 a141 a142 a211 a212 a221 a222 a231 a232 a241 a242 a311 a312 a321 a322 a331 a332 a341 a342 第1页 第2页 第3页 5.1.2 数组的类型定义和变量说明： 例1 int a[10]； //10个整数的一维数组 char b[4][5]； //4行5列个字符的二维数组 float c[3][4][2]； //3*4*2个实数的三维数组 A3*4*2 =
例2# define m4 /定义符号常量m #define n 5 /定义符号常量n int alm //m个整数的一维数组 char b mlIn //m行n列个字符的二维数组 例3# define m4 /定义符号常量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语言中定义静态数组时,元素数目必须是常量 错例1intm=4,n=5; int am ln] //m,n是变量 错例2intp; scanf(%d, &p) int clp; //p是变量
例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.1.3数组的操作 1.生成一个数组:inta[7];//生成静态一维数组(存储结构) 2.销毁一个数组 3.赋值/修改 a[1]=15;(a[1])++; a 4.取元素的值 0123456 a[0]=a[1]*2 a32|16 3456 5.1.4程序设计举例 例 I main i int i, al10] //生成一维数组a for(i=0;i<10;i++) scanf(9%d,,, &aliD //输入元素 for(i=0;i<10;i++) printf(d”,a[i]*a[i]);//输出元素的平方
5.1.3 数组的操作 1.生成一个数组： int a[7]；//生成静态一维数组(存储结构） 2.销毁一个数组 3.赋值/修改 a[1]=15；(a[1])++； 4.取元素的值： a[0]=a[1]*2； 5.1.4 程序设计举例 例1 main() { int i,a[10]； //生成一维数组a for (i=0；i<10；i++) scanf(”%d”,&a[i])； //输入元素 for (i=0；i<10；i++) printf(”%d ”,a[i]*a[i])； //输出元素的平方 } a 0 1 2 3 4 5 6 a 32 16 0 1 2 3 4 5 6
例2生成动态的10个整数的一维数组 int pa; //指针变量pa pa=(int *)malloc(10*sizeof(int)) /动态数组pa pa 0123456789 main t int i, n, *pa; scanf(2%d?, &n) //动态输入n pa=(int*)ma1loc(n米 sizeof(int));/生成动态数组*pa for (i=0; i<n; i++) 米(pa+i)=2*i; //指针法引用数组元素,赋值 for (i=0; i<n; i++) printf(%d,”,*(pa+i));//输出数组元素0,2,4,6, for (i=0; i<n:i++ scanf(<%d", &pali]) //下标法引用数组元素,输入 for (i=0; i<n; i++) printf( %d, palid) //输出数组元素 free(pa) /释放(销毁)数组空间
例2 生成动态的10个整数的一维数组 int *pa； //指针变量pa pa=(int *)malloc(10*sizeof(int))； //动态数组pa* main() { int i,n,*pa； scanf(”%d”,&n)； //动态输入n pa=(int *)malloc(n*sizeof(int))；//生成动态数组*pa for (i=0；i<n；i++) *(pa+i)=2*i； //指针法引用数组元素,赋值 for (i=0；i<n；i++) printf(“%d,”,*(pa+i))； //输出数组元素0,2,4,6,... for (i=0；i<n；i++) scanf(“%d”,&pa[i])； //下标法引用数组元素, 输入 for (i=0；i<n；i++) printf("%d,",pa[i])； //输出数组元素 free(pa)； //释放(销毁)数组空间 } pa → 0 1 2 3 4 5 6 7 8 9
5.2数组的顺序表示和实现 5.2.1顺序表示(顺序存储结构) 以行序为主序的顺序存储方式 左边的下标后变化,右边的下标先变化 2.以列序为主序的顺序存储方式 左边的下标先变化,右边的下标后变化 例1二维数组a[1..3,1..2],b是首地址,s是元素所占的单元数 序号内存地址 序号内存地址 11al2 all all b a21a22 2|a12b+s 2a21 b+s a31a32 3a21b+2*s a31b+2*s 逻辑结构 4|a22b+3*s a12b+3*S a31b+4*s 5|a22b+4*s 6a32 b+5*s a32b+5*s 以行序为主序 以列序为主序
5.2数组的顺序表示和实现 5.2.1顺序表示(顺序存储结构） 1.以行序为主序的顺序存储方式 左边的下标后变化，右边的下标先变化 2.以列序为主序的顺序存储方式 左边的下标先变化，右边的下标后变化 例1 二维数组a[1..3,1..2],b是首地址,s是元素所占的单元数 a11 a12 a21 a22 a31 a32 a11 a12 a21 a22 a31 a32 a11 a21 a31 a12 a22 a32 序号 内存 地址 1 2 3 4 5 6 1 2 3 4 5 6 序号 内存 地址 b b+s b+2*s b+3*s b+4*s b+5*s b b+s b+2*s b+3*s b+4*s b+5*s 以行序为主序 以列序为主序 逻辑结构
例2三维数组a[1..2,1..3,1..2] 序号内存地址 序号内存地址 alll 1|a111b 2a112b+s 2a211b+s a211 a212 a121b+2*s 3a121b+2*s alll all2 a221 a222 a122b+3*s 4a221b+3*s a121a122 a231a232 a13la132 第2页 456 a131b+4*s 5a131b+4*s a132b+5*s 6a231b+5*s 第1页 7|a211b+6*S 7a112b+6*s 逻辑结构 8a212 8a212 a221 a122 10a222 10a222 a231 a132 12a232b+1712232b+12s 以行序为主序 以列序为主序
例2 三维数组a[1..2,1..3,1..2] a111 a112 a121 a122 a131 a132 a111 a112 a121 a122 a131 a132 a211 a212 a221 a222 a231 a232 序号 内存 地址 1 2 3 4 5 6 7 8 9 10 11 12 序号 内存 地址 b b+s b+2*s b+3*s b+4*s b+5*s b+6*s b+11*s b b+s b+2*s b+3*s b+4*s b+5*s b+6*s b+11*s 以行序为主序 以列序为主序 逻辑结构 a211 a212 a221 a222 a231 a232 第1页 第2页 1 2 3 4 5 6 7 8 9 10 11 12 a111 a211 a121 a221 a131 a231 a112 a212 a122 a222 a132 a232
5.2.2数组的映象函数 数组元素的存储地址 例1一维数组a[0.n-1] ao ala2 al a(n 下标012 n-1 地址bb+sb+2*s b+i*s b+(n-1)*s 设:b为首地址,s为每个元素所占的存储单元数 则:元素a[i的存储地址: Loc(i)=Loc(O)+i*s=b+i*s0≤i≤n-1 例2一维数组a[1.n] al.ai ..I an 下标12 3 n 地址bb+sb+2s b+(i-1)s b+(n-1)s
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 a0 a1 a2 ... ai ... a(n-1) 下标 0 1 2 i n-1 地址 b b+s b+2*s b+i*s b+(n-1)*s a1 a2 a3 ... ai ... an 下标 1 2 3 i n 地址 b b+s b+2s b+(i-1)s b+(n-1)s 例2 一维数组a[1..n]