资源描述：
《数据结构课件CD 第05章 数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章 数组和广义表数据结构主讲教师：周时阳本章主要介绍串，它属于线性结构，是数据元素的内部结构确定为符号的特殊线性表。讨论串的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。重点研究串的概念、基本运算、顺序结构和链式存储结构及其主要运算的实现算法及其效率分析。内容摘要2重点讲解5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构小结3数组名下标5.1.1数组的逻辑结构定义及术语1维数组是数据元素个数固定的特殊线性表。一般记为A＝(a1,a2,…,an)(n≥1)5.1数
2、组的定义序号：1，2，…，n下标：0,1,…,n-1(C、JAVA语言)一般情况下，下标的取值范围：下界,下界＋1,…,i,…,上界下标的作用：A[i]——表示数组元素，高级语言称为“下标变量”。下界上界重要关系：元素个数＝上界－下界＋142维数组是数据元素为1维数组的1维数组。一般记为A＝(A1,A2,…,An)(n≥1)其中，Ai＝(ai,1,ai,2,…,ai,m)(1≤i≤n,m≥1)ai,1ai,2…ai,ma1,1a1,2…a1,ma2,1a2,2…a2,man,1an,2…an,m……2维数组的矩阵表示2维数组的元素表示A[i][j]或A[i,j]行下标
3、列下标提示：行列下标的下界也可以从任意值开始！每个aij具有行列两种线性关系5ai,1ai,2…ai,ma1,1a1,2…a1,ma2,1a2,2…a2,man,1an,2…an,m……重要关系：行元素个数＝列数＝列上界－列下界＋1列元素个数＝行数＝行上界－行下界＋1数组元素个数＝行数×列数注解：C、JAVA语言中约定下界为0。n维数组是数据元素为n-1维数组的1维数组。65.1.2基本运算定义（1）创建InitArray(&A，n，bound1，…，boundn)初始化下标界为boundi的、n维数组A。boundi＝下界i‥上界i(1≤i≤n)或者boundi＝上
4、界i－下界i＋1(1≤i≤n)约定下界为0（注：C、java语言是这样定义的！）（2）销毁DestroyArray(&A)（3）取值Value(A，index1，…，indexn)＝…A[index1，…，indexn]…（4）赋值Assign(A，e，index1，…，indexn)A[index1，…，indexn]＝“界差”75.2.11维数组顺序存储结构5.2数组的顺序表示和实现…线性表的顺序物理结构的示意图…a下界a下界＋1a上界L:m＝n是固定常量A=(A[下界]，A[下界＋1]，…，A[下界＋i]，…，A[上界])nnelemlengthlistsize
5、85.2.11维数组顺序存储结构5.2数组的顺序表示和实现A=(A[下界]，A[下界＋1]，…，A[下界＋i]，…，A[上界])物理结构的示意图A:……a下界a下界＋1a下界+ia上界basedimbound1下界上界上界－下界＋19A=(A[下界]，A[下界＋1]，…，A[下界＋i]，…，A[上界])寻址公式Loc(a[i])=loc(a[下界])+(i-下界)×la[i]首地址=a[下界]首地址+存储在a[i]之前元素个数×每个数据元素占用的字节数令元素x的首地址为Loc(x)每个元素占用字节数为l则寻址公式如下：……a下界a下界＋1aia上界物理结构的示意图10
6、C、JAVA语言的存储结构elemtypeA[n];或elemtype[]A=newelemtype[n];A=(A[0]，A[1]，…，A[i]，…，A[n－1])“界差”“数据元素个数”物理结构的示意图A:……a0a1aian-1下界上界寻址公式:Loc(A[I])=LOC(A[0])+I*l11a行下界,列下界a行下界,列下界+1…a行下界,列上界……A:a行下界+1,列下界a行下界+1,列下界+1…a行下界+1,列上界ai,列下界ai,列下界+1…ai,列上界a行上界,列下界a行上界,列下界+1…a行上界,列上界5.2.22维数组顺序存储结构物理结构的示意图（
7、行优先方式）A:……a行下界,列下界basedimbound2行下界行上界列下界列上界a行下界,列下界＋1a行下界,列上界a行下界＋1,列上界a行下界＋2,列上界…a行上界,列上界…元素个数12寻址公式a[i,j]首地址=a[行下界，列下界]首地址+存储在a[i,j]之前元素个数×每个数据元素占用的字节数Loc(a[i,j])=loc(a[行下界,列下界])+{(列上界-列下界＋1)×(i-行下界)+(j-列下界)}×l令元素x的首地址为Loc(x)每个元素占用字节数为l则寻址公式如下：……a行下界,列下界a行下界,列下界＋1a行下界,列上界a行下界
