数据结构与算法（C++版）课件第5章 数组和广义表

第5章数组和广义表数据结构与算法

(C++版)(第2版)5.1数组一、数组元素的存储顺序1.以行序为主序(按行排列):

先排最右的下标,依次向左,最后排最左的下标2.以列序为主序(按列排列):

先排最左的下标,依次向右,最 后排最右的下标二、二维数组元素的存储位置例如：

称为基地址或基址。1.C中二维数组的元素的存储位置二维数组a[b1][b2]中任一元素ai,j

的存储位置

Loc(i,j)=Loc(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

对于一般意义二维数组a[c1:d1,c2:d2]，设每个元素占用L个存储单元，Loc(c1,c2)是第一个元素ac1c2的存储位置则按行存放时，aij的存储位置为：Loc(i,j)=Loc(c1,c2)+[(d2-c2+1)(i-c1)+(j-c2)]L则列行存放时，aij的存储位置为：Loc(i,j)=Loc(c1,c2)+[(d1-c1+1)(j-c2)+(i-c1)]L*2.一般意义二维数组元素的的存储位置三、n维数组元素的存储位置推广到一般情况，可得到n维数组数据元素按行序的存储位置有如下的关系数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1<i

n。Loc(j1,j2,...,jn)=Loc(0,0,…,0)+[j1×b2×…×bn +j2×b3×…×bn …… +jn-1×bn +jn]L

=Loc(0,0,...,0)+∑ciji

ni=11.C中n维数组元素的的存储位置对于n维数组的一般情况a[c1:d1,c2:d2,…,cn:dn]，设每个元素占用L个存储单元，Loc(c1,c2,…,cn)是第一个元素ac1c2…cn的存储位置，可以得到如下的计算数组元素存储位置的公式*2.一般意义n维数组元素的的存储位置按行存放时，aj1j2…jn的存储位置如下：Loc(j1j2…jn)=Loc(c1,c2,…,cn)+[(j1-c1)(d2-c2+1)…(dn-cn+1) +(j2-c2)(d3-c3+1)…(dn-cn+1) …… +(jn-1-cn-1)(dn-cn+1) +(jn-cn)]L列行存放时，aj1j2…jn的存储位置如下：Loc(j1j2…jn)=Loc(c1,c2,…,cn)+[(j1-c1) +(d1-c1+1)(j2-c2) …… +(d1-c1+1)…(dn-2-cn-2+1)(jn-1-cn-1) +(d1-c1+1)…(dn-1-cn-1+1)(jn-cn)]L5.2矩阵一、特殊矩阵1.特殊矩阵的概念特殊矩阵指元素（特别是非零元素）在矩阵中的分布有一定规则例如:对称矩阵三角矩阵三对角矩阵2.对称矩阵的压缩存储

a11a12

….

…

…..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：3.三角矩阵的压缩存储

a11

a120

…………….0

a21

a22

a23

0

……………

00

0

…

an-1,n-2an-1,n-1

an-1,n0

0

…

…an,n-1ann.

0

a32a33

a34

0

………

0

……………k=2(i-1)+(j-1)|i-j|≤1a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：4.对角矩阵的压缩存储二、稀疏矩阵

(SparseMatrix)稀疏矩阵是非零元素个数远远少于矩阵元素个数的矩阵1.稀疏矩阵的基本概念以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；2.解决问题的原则2)尽可能减少没有实际意义的运算；3)操作方便。即能尽可能快地找到与下标值(i，j)对应的元素，3.稀疏矩阵基本操作

（1）intGetRows()const

初始条件：稀疏矩阵已存在。

操作结果：返回稀疏矩阵行数。

（2）intGetCols()const

初始条件：稀疏矩阵已存在。

操作结果：返回稀疏矩阵列数。

（3）intGetNum()const

初始条件：稀疏矩阵已存在。

操作结果：返回稀疏矩阵非零元素个数。

（4）boolEmpty()const

初始条件：稀疏矩阵已存在。

操作结果：如稀疏矩阵为空，则返回true，否则返回false

（5）boolSetElem(intr,intc, constElemType&v)

初始条件：稀疏矩阵已存在。

操作结果：设置指定位置的元素值。

（6）boolGetElem(intr,intc,ElemType&v)

初始条件：稀疏矩阵已存在。

操作结果：求指定位置的元素值。稀疏矩阵的顺序压缩存储三元组表示法稀疏矩阵的链式压缩存储十字链表4.稀疏矩阵的存储方式（1）三元组顺序表当稀疏矩阵的阶很高时，如采用一般矩阵的存储方法将浪费大量的存储空间。一种直观、常用的方法是，对每个非零元素，用三元组（行号，列号，元素值）来表示，这样每个元素的信息就全部记录下来了。//三元组类模板template<classElemType>structTriple{//数据成员: introw,col; //非零元素的行下标与列下标

ElemTypevalue; //非零元素的值//构造函数模板: Triple(); //无参数的构造函数模板

Triple(intr,intc,ElemTypev);

//已知数据成份建立三元组};以顺序表存储三元组表，可得到稀疏矩阵的顺序存储结构——三元组顺序表在三元组顺序表中，用三元组表表示稀疏矩阵时，为避免丢失信息，增设了一个信息元组，形式为：

（行数，列数，非零元素个数）

已知稀疏矩阵三元组顺序表示例三元组表示为//稀疏矩阵三元组顺序表类模板template<classElemType>classTriSparseMatrix{protected://稀疏矩阵三元组顺序表的数据成员: Triple<ElemType>*triElems;

//存储稀疏矩阵的三元组表

intmaxSize; //非零元素最大个数

introws,cols,num;

//稀疏矩阵的行数,列数及非零元个数public://抽象数据类型方法声明及重载编译系统默认方法声明: TriSparseMatrix(intrs=DEFAULT_SIZE,intcs =DEFAULT_SIZE, intsize=DEFAULT_SIZE); //构造一个rs行cs列非零元素最大个数为size //的空稀疏矩阵

virtual~TriSparseMatrix(); //析构函数

intGetRows()const; //返回稀疏矩阵行数

intGetCols()const; //返回稀疏矩阵列数

intGetNum()const; //返回稀疏矩阵非零元个数

boolSetElem(intr,intc,constElemType&v); //设置指定位置的元素值

boolGetElem(intr,intc,ElemType&v);

//求指定位置的元素值

TriSparseMatrix<ElemType>&operator=(const TriSparseMatrix<ElemType>&source);//赋值 ……};稀疏矩阵的转置算法的基本思想：第一次从转置前稀疏矩阵source中取出应该放置到转置后的稀疏矩阵dest中第一个位置的元素，行列号互换后，放于dest中第一个位置；第二次从source中选取应该放到dest中的第二个位置的元素，……，如此进行，依次生成dest中的各元素。由于转置后列号变行号，所以转置后元素的行序排列实质上是原矩阵元素的列序排列。实现算法可形式化描述为：destPos=0;//稀疏矩阵dest的下一个三元组的存放位置for(col=最小列号;col<=最大列号;col++){

在source中从头查找有无列号为col的三元组； 若有，则将其行、列号交换后，依次存入dest

中destPos所指位置，同时destPos加1；}template<classElemType>voidTriSparseMatrix<ElemType>::SimpleTranspose(constTriSparseMatrix<ElemType>&source,TriSparseMatrix<ElemType>&dest)//操作结果：将稀疏矩阵source转置成稀疏矩阵dest的简// 单算法{dest.rows=source.cols; //行数

dest.cols=source.rows; //列数

dest.num=source.num; //非零元素个数

dest.maxSize=source.maxSize; //最大非零元素个数

delete[]dest.triElems; //释放存储空间

dest.triElems=newTriple<ElemType> [dest.maxSize];

//分配存储空间if(dest.num>0){intdestPos=0;

//稀疏矩阵dest的下一个三元组的存放位置

for(intcol=1;col<=source.cols;col++){ //转置前的列变为转置后的行

for(intsourcePos=0;sourcePos<source.num;sourcePos++){//查找第col列的三元组

if(source.triElems[sourcePos].col==col){//找到第col列的一个三元组,转置后存入dest dest.triElems[destPos].row= source.triElems[sourcePos].col; //列变行

dest.triElems[destPos].col=source.triElems[sourcePos].row; //行变列

dest.triElems[destPos].value=source.triElems[sourcePos].value;

//非零元素值不变

destPos++; //新下一个元素的存放位置

}}}}}（二）十字链表5.3广义表

GeneralList一、广义表基础1.广义表的概念，广义表通常简称为表，由

n(0)个表元素组成的有限序列,记作

GL=(a1,a2,a3,…,an)，GL是表名,ai为表元素,简称为元素，它可以是表(称为子表元素，简称为子表),可以是数据元素(称为原子元素，简称为原子)2.n为表的长度。n=0的广义表为空表3.n>0时,表的第一个表元素称为广义表的表头(head),除此之外,其它表元素组成的表称为广义表的表尾(tail)

由于广义表中的元素又可以是广义表，因此对于广义表有深度的概念。广义表GL的深度Depth(GL)定义如下：广义表的深度本质上就是广义表表达式中括号的最大嵌套层数。例如: 2 深度为0(括号层数为0) () 深度为1(括号层数为1) (2,(3,6)) 深度为2(括号层数为2)

广义表基本操作1．GenListNode<ElemType>*First()const初始条件：广义表已存在。操作结果：返回广义表的第一个元素。2．GenListNode<ElemType>*Next(GenListNode<ElemType>*elemPtr)const初始条件：广义表已存在，elemPtr指向广义表的元素。操作结果：返回elemPtr指向的广义表元素的后继3．boolEmpty()const初始条件：广义表已存在。操作结果：如广义表为空，则返回true，否则返回false4．voidPush(constElemType&e)初始条件：广义表已存在。操作结果：将元子元素e作为表头加入到广义表最前面。5．voidPush(GenList<ElemType>&subList)初始条件：广义表已存在。操作结果：将子表subList作为表头加入到广义表最前面。6．intDepth()初始条件：广义表已存在。操作结果：返回广义表的深度。二、广义表的存储结构广义表通常借助引用数链式存储结构——引用数法广义表。在这种方法中，每一个表结点由三个成份组成，结点可分为三类：（1）头结点：用标志成份tag=HEAD标识，数据成份ref用于存储引用数，广义表的引用数表示能访问此广义表的广义表或指针个数，后面章节将对引用数的内涵作详细的介绍。（2）原子结点：用标志成份tag=ATOM标识，原子元素用原子结点存储，数据成份atom用于存储原子元素的值。（3）表结点：用标志成份tag=LIST标识，指针成份subLink用于存储指向子表头结点的指针。A=()，B=(x,y,z)，C=(B,y,z)，D=(x,(y,z))，E=(x,E)//引用数法广义表类模板template<classElemType>classRefGenList{protected://引用数法广义表类的数据成员: RefGenListNode<ElemType>*head; //头指针

//辅助函数模板: voidShowHelp(RefGenListNode<ElemType>*hd) const; //显示以hd为头结点的广义表

intDepthHelp(constRefGenListNode<ElemType> *hd); //计算以hd为表头的广义表的深度

voidClearHelp(RefGenListNode<ElemType>*hd);

//释放以hd为表头的广义表结构 voidCopyHelp(constRefGenListNode<ElemType> *sourceHead,RefGenListNode<ElemType> *&destHead); //将以destHead为头结点的广义表复制成以

//sourceHead为头结点的广义表

staticvoidCreateHelp(RefGenListNode<ElemType> *&first); //创建以first为头结点的广义表public://抽象数据类型方法声明及重载编译系统默认方法声明: RefGenList(); //无参数的构造函数模板

RefGenList(RefGenListNode<ElemType>*hd);

//由头结点指针构造广义表

virtual~RefGenList(); //析构函数模板 RefGenListNode<ElemType>*First()const;

//返回引用数法广义表的第一个元素

RefGenListNode<ElemType> *Next(RefGenListNode<ElemType>*elemPtr) const; //返回elemPtr指向的广义表元素的后继

boolEmpty()const; //判断广义表是否为空

voidPush(constElemType&e);

//将e作为表头加入到广义表最前面

voidPush(RefGenList<ElemType>&subList);

//将子表subList作为表头加入到广义表最前面

intDepth(); //计算广义表深度

RefGenList(constRefGenList<ElemType>&source); //复制构造函数

RefGenList<ElemType>&operator=(const RefGenList<ElemType>&source);//重载赋值

voidInput(); //输入广义表

voidShow()const; //显示广义表 };

template<classElemType>RefGenList<ElemType>::RefGenList()//操作结果：构造一个空引用数法广义表{ head=newRefGenListNode<ElemType>(HEAD); head->ref=1; //引用数}template<classElem