数据结构 5数组和广义表A

数据结构课程的内容1第5章数组和广义表（Arrays&Lists）①元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。②所有数据元素仍属同一数据类型。5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构数组和广义表的特点：一种特殊的线性表25.1数组的定义

数组：由一组名字相同、下标不同的变量构成答：对的。因为：①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。讨论：“数组的处理比其它复杂的结构要简单”，对吗？一维数组的特点：1个下标，ai

是ai+1的直接前驱3二维数组的特点：2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。N维数组的特点：n个下标，每个元素受到n个关系约束一个n维数组可以看成是由若干个n－1维数组组成的线性表。

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=45.2数组的顺序存储表示和实现问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。5补充：计算二维数组元素地址的通式

设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0。无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L

ac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=单个元素长度aij之前的行数数组基址总列数，即第2维长度aij本行前面的元素个数①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数则行优先存储时的地址公式为：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L6例2：已知二维数组Am,m按行存储的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*L,按列存储的公式是？

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L（尽管是方阵，但公式仍不同）例1〖软考题〗：一个二维数组A[1..6,0..7]，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是

个字节。288例3：〖00年计算机系考研题〗设数组a[1..60,1..70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：请注意审题！利用列优先通式：答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2887Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N维数组，其中任一元素的地址该如何计算？其中Cn=L,Ci-1=bi×Ci，1<i≤n一个元素长度数组基址前面若干元素占用的地址字节总数第i维长度与所存元素个数有关的系数，可用递推法求出教材已给出低维优先的地址计算公式，见P93（5-2）式该式称为n维数组的映像函数：LOC(j1,j2,…,jn)=LOC(c1,c2,…,cn)+[(b2…bn)(j1-c1)+(b3…bn)(j2-c2)+…+bn(jn-1-cn-1)+(jn-cn)]L8#defineMAX_ARRAY_DIM8//假设最大维数为8

typedef

struct{

ELemType*base;//数组元素基址

intdim;//数组维数

int*bound;//数组各维长度信息保存区基址

int*constants;//数组映像函数常量的基址

}Array;即Ci信息保存区数组的基本操作函数说明（有5个）（请阅读教材P93-95）N维数组的顺序存储表示（见教材P93）以销毁数组函数为例91StatusInitArray(Array&A,intdim,…){2//若维数dim和各维长度合法，则构造相应的数组A并返回OK3if(dim<1||dim>MAX_ARRAY_DIM)return

ERROR;4A.dim=dim;5A.bounds=(int*)malloc(dim*sizeof(int));6if(!A.bounds)exit(OVERFLOW);

7//若各维长度合法，则存入A.bounds,并求出A的元素总数elemtotal8elemtotal=1;9va_start(ap,dim);//ap为va_list类型，是存放变长参数表信息的类型数组的基本操作函数说明（5个）（见教材P93-95）10//P93代码1-9行用于检查维数和各维长度是否合法10for(i=0;i<dim;++i){11A.bounds[i]=va_arg(ap,int);12if(A.bounds[i]<0)return

UNDERFLOW;13elemtotal*=A.bounds[i];}14va_end(ap);15A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));16if(!A.base)exit(OVERFLOW);17A.constants=(int*)malloc(dim*sizeof(int));18if(!A.constants)exit(OVERFLOW);19A.constants[dim-1]=1;20for(i=dim-2;i>=0;--i)21A.constants[i]=A.bounds[i+1]*A.constants[i+1];22return

OK;23}111StatusDestroyArray(Array&A)2{//销毁数组A3if(!A.base)return

ERROR;4free(A.base);5A.base=NULL;6if(!A.bounds)return

ERROR;7free(A.bounds);8A.bounds=NULL;9if(!A.constants)return

ERROR;10free(A.constants);11A.constants=NULL;12return

OK;13}数组基址指针各维长度保存区指针映像函数Ci保存区指针121StatusLocate(ArrayA,va_list

ap,int&off)2{3//若ap指示的各下标值合法，则求出该元素在A中，相对地址off4off=0;5for(i=0;i<A.dim;++i)6{7ind=va_arg(ap,int);8if(ind<0||ind>A.bounds[i])return

OVERFLOW;9off+=A.constants[i]*ind;10}11return

OK;12}131StatusValue(ArrayA,ElemType&e,…){2//A是n维数组，e为元素变量，随后是n个下标值，若各下标不超界，则e赋值为所指定的A的元素值，即将指定元素值读到e变量中。3va_start(ap,e);4if((result=Locate(A,ap,off))<=0)returnresult;5e=*(A.base+off);6return

OK;7}141StatusAssign(Array&A,ElemTypee,…){2//A是n维数组，e为元素变量，随后是n个下标值，若各下标不超界，则e的值赋为所指定的A的元素值，即：将e值写入指定数组单元。3va_start(ap,e);4if((result=Locate(A,ap,off))<=0)returnresult;5*(A.base+off)=e;6return

OK;7}15LispandJohnMaCarthyLisp–LIStProcessor条件表达式、递归函数、广义表、程序即数据（本身也同所有其他数据一样用表结构形式表示）、垃圾回收McCarthy-“人工智能之父”。1971年图灵奖–Lisp,AI,分时概念等麦卡锡是一个天赋很高的人，还在上初中时，他就弄了一份加州理工大学的课程目录，按目录自学了大学低年级的高等数学教材，做了教材上的所有练习题。这使他1944年进入加州理工学院以后可以免修头两年的数学，并使他虽因战时环境(第二次世界大战当时正在进行之中，美国也在珍珠港事件后宣布参战)要在军队中充任一个小职员，占去了部分时间，仍得以·在1948年按时完成学业。然后到普林斯顿大学研究生院深造，于1951年取得数学博士学位。165.4广义表的定义广义表是线性表的推广，也称为列表（lists）记为：LS=(a1,a2,……，an)广义表名表头(Head）表尾(Tail)1、定义：①第一个元素是表头，而其余元素组成的表称为表尾；②用小写字母表示原子类型，用大写字母表示列表。n是表长在广义表中约定：讨论：广义表与线性表的区别和联系？广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。172、特点：有次序性有长度有深度可递归可共享一个直接前驱和一个直接后继＝表中元素个数＝表中括号的重数(递归的情况除外)自己可以作为自己的子表可以为其他广义表所共享特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。18E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E为递归表1）A=()2）B=(e)3）C=(a,(b,c,d))4）D=(A,B,C)5）E=(a,E)例1：求下列广义表的长度。n=0，因为A是空表n=1，表中元素e是原子n=2，a为原子，(b,c,d)为子表n=3，3个元素都是子表n=2，a为原子，E为子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表19ABDCeabcd②A=(a,(b,A))例2：试用图形表示下列广义表.（设代表原子，代表子表）

e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的长度为3，深度为3②的长度为2，深度为∞深度＝括号的重数＝结点的层数20介绍两种特殊的基本操作：GetHead(L)——取表头(可能是原子或列表);GetTail(L)——取表尾(一定是列表)

。广义表的抽象数据类型定义见教材P107-108211.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;3.GetTail【((a,b),(c,d))】＝

;4.GetTail【GetHead【((a,b),(c,d))】】＝

;例：求下列广义表操作的结果（严题集5.10②）(k,p,h)（b）(a,b)5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))225.5广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示，通常用链式结构，每个元素用一个结点表示。1.原子结点：表示原子，可设2个域或3个域，依习惯而选。valuetag=0标志域数值域注意：列表的“元素”还可以是列表，所以结点可能有两种形式tpatomtag=０标志域值域

表尾指针法2：标志域、值域、表尾指针指向下一结点法1：标志域，数值域23tphptag=1标志域表头指针表尾指针2.表结点：表示列表，若表不空，则可分解为表头和表尾，用3个域表示：标志域，表头指针，表尾指针。①A=()

^10e③C=(a,(b,c,d))1^110a0b0d0c1^1例：②B=(e)A=NULL指向子表指向下一结点^^124⑤E=(a,E)④D=(A,B,C)＝((),(e),(a,(b,c,d)))

0a^11^10e1^11^110a0b0d0c1^1^1本章结束（参见教材P109图）25一、稀疏矩阵的压缩存储问题：如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路：对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法：将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。二、稀疏矩