数组和广义表详解

数组和广义表版详解演示文稿《数据结构（Java版）（第4版）》第5章1目前一页\总数四十三页\编于七点（优选）数组和广义表版《数据结构（Java版）（第4版）》第5章2目前二页\总数四十三页\编于七点3.二维数组的存储结构（1）二维数组的顺序存储结构行主序列主序O(1)，随机存取结构目前三页\总数四十三页\编于七点（2）二维数组的动态存储结构O(1)，随机存取结构目前四页\总数四十三页\编于七点4.Java语言的二维数组动态的，引用模型。不支持类似C/C++的静态二维数组。（1）声明和使用二维数组intelement[][];//声明element=newint[4][5];//动态申请int[][]element={{1,2,3},{4,5,6}};//赋初值element.length//返回二维数组的长度，行数element[0].length//返回一维数组的长度，列数目前五页\总数四十三页\编于七点（2）不规则的二维数组（3）二维数组可作为方法的参数和返回值参数传递规则同赋值，即传递数组引用。voidprint(intelement[][])//方法参数int[][]yanghui(intn)//返回二维数组目前六页\总数四十三页\编于七点【例5.1】矩阵类。设，有设，有设，有设，有《数据结构（Java版）（第4版）》第5章7目前七页\总数四十三页\编于七点矩阵类MatrixpublicclassMatrix//矩阵类{privateintrows,columns;//行数、列数privateint[][]element;//二维数组

publicMatrix(intm,intn)//构造m×n零矩阵publicMatrix(intn)//构造n×n零方阵publicMatrix(intm,intn,int[][]value)//构造m×n矩阵《数据结构（Java版）（第4版）》第5章8目前八页\总数四十三页\编于七点矩阵类Matrix

intgetRows()//行数intgetColumns() //列数intget(inti,intj)//第i行第j列元素voidset(inti,intj,intx)//设置第i行j列元素为xStringtoString()//描述字符串，行主序voidsetRowsColumns(intm,intn)

//设置矩阵为m行n列，矩阵扩容，复制。

//7.2.1节图的邻接矩阵}《数据结构（Java版）（第4版）》第5章9目前九页\总数四十三页\编于七点value数组和mata矩阵存储结构intvalue[][]={{1,2,3},{4,5,6,7,8},{9}}; //各一维数组的长度不同《数据结构（Java版）（第4版）》第5章10目前十页\总数四十三页\编于七点【实验5-1】Matrix矩阵类的方法Matrix(Matrixmat)//深拷贝booleanequals(Objectobj)//比较同阶矩阵相等Matrixtranspose()//返回转置矩阵booleanisTriangular(booleanup)//判断上/下三角矩阵booleanisSymmetric()//判断对称矩阵intsaddlePoint()//返回矩阵的鞍点值voidaddAll(Matrixmat)//矩阵相加，this+=matMatrixunion(Matrixmat)//返回this+mat的矩阵Matrixmulti(Matrixmat)//返回this*mat的矩阵《数据结构（Java版）（第4版）》第5章11目前十一页\总数四十三页\编于七点5.2特殊矩阵的压缩存储5.2.1三角矩阵、对称矩阵和对角矩阵的压缩存储5.2.2稀疏矩阵的压缩存储《数据结构（Java版）（第4版）》第5章12目前十二页\总数四十三页\编于七点5.2.1三角矩阵、对称矩阵和 对角矩阵的压缩存储1.三角矩阵的压缩存储 《数据结构（Java版）（第4版）》第5章13目前十三页\总数四十三页\编于七点（1）线性压缩存储三角矩阵(下)（2）使用三角形的二维数组压缩存储三角矩阵《数据结构（Java版）（第4版）》第5章14目前十四页\总数四十三页\编于七点【思考题5-1】上三角矩阵的压缩存储，习题解答5-6《数据结构（Java版）（第4版）》第5章15目前十五页\总数四十三页\编于七点2.对称矩阵的压缩存储《数据结构（Java版）（第4版）》第5章16目前十六页\总数四十三页\编于七点3.对角矩阵的压缩存储《数据结构（Java版）（第4版）》第5章17目前十七页\总数四十三页\编于七点5.2.2稀疏矩阵的压缩存储稀疏矩阵非零元素三元组((0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,2,36)，(3,5,28)，(4,2,50))行号列号元素值rowcolumnvalue《数据结构（Java版）（第4版）》第5章18目前十八页\总数四十三页\编于七点稀疏矩阵非零元素三元组类TriplepublicclassTripleimplementsComparable<Triple>{introw,column,value;//行号、列号、元素值publicTriple(introw,intcolumn,intvalue)//构造publicTriple(Tripletri)//拷贝构造publicStringtoString()//描述字符串publicTripletoSymmetry()//对称位置元素publicbooleanequals(Objectobj)//比较相等

publicintcompareTo(Tripletri)//比较大小}《数据结构（Java版）（第4版）》第5章19目前十九页\总数四十三页\编于七点2.稀疏矩阵三元组顺序表//三元组顺序表类publicclassSeqMatrix{introws,columns;//行数、列数

SortedSeqList<Triple>list;//排序顺序表}《数据结构（Java版）（第4版）》第5章20目前二十页\总数四十三页\编于七点3.稀疏矩阵三元组单链表publicclassSinglyMatrix//三元组单链表类{introws,columns;//行数、列数

SortedSinglyList<Triple>list;//排序单链表}《数据结构（Java版）（第4版）》第5章21目前二十一页\总数四十三页\编于七点4.稀疏矩阵行的单链表《数据结构（Java版）（第4版）》第5章22目前二十二页\总数四十三页\编于七点4.稀疏矩阵行的单链表声明行的单链表矩阵类返回矩阵元素设置矩阵元素输出矩阵比较两个矩阵是否相等设置矩阵行列数矩阵相加《数据结构（Java版）（第4版）》第5章23目前二十三页\总数四十三页\编于七点矩阵类，三元组行的单链表存储publicclassLinkedMatrix{privateintrows,columns;//行数、列数

SeqList<SortedSinglyList<Triple>>rowlist; //行指针顺序表，元素是排序单链表

publicLinkedMatrix(intm,intn)//构造m×n零矩阵

publicLinkedMatrix(intm)//构造m×m零矩阵publicLinkedMatrix(intm,intn,Triple[]tris)

publicintgetRows()//行数

publicintgetColumns()//列数《数据结构（Java版）（第4版）》第5章24目前二十四页\总数四十三页\编于七点LinkedMatrix类intget(inti,intj)//返回元素voidset(inti,intj,intx)//设置元素voidset(Tripletri)StringtoString()//描述字符串voidprintMatrix()//输出矩阵voidsetRowsColumns(intm,intn)//设置行列}【例5.2】稀疏矩阵的存储及运算。《数据结构（Java版）（第4版）》第5章25目前二十五页\总数四十三页\编于七点SortedSinglyList<T>

覆盖父类成员方法《数据结构（Java版）（第4版）》第5章26目前二十六页\总数四十三页\编于七点（6）比较两个矩阵是否相等publicbooleanequals(Objectobj)《数据结构（Java版）（第4版）》第5章27目前二十七页\总数四十三页\编于七点【例5.2】稀疏矩阵

的存储及运算行的单链表《数据结构（Java版）（第4版）》第5章28目前二十八页\总数四十三页\编于七点（7）矩阵相加，A+=B

《数据结构（Java版）（第4版）》第5章29目前二十九页\总数四十三页\编于七点三元组类TriplepublicclassTripleimplementsComparable<Triple>,Addible<Triple>{introw,column,value;//行、列、元素……voidaddAll(Tripleterm)

//三元组相加booleanremovable()//删除条件}《数据结构（Java版）（第4版）》第5章30目前三十页\总数四十三页\编于七点矩阵类（行的单链表存储）publicclassLinkedMatrix{privateintrows,columns;//行数、列数

SeqList<PolySinglyList<Triple>>rowlist;//行指针顺序表，元素是多项式排序单链表//一个三元组就是多项式中的一项

……voidaddAll(LinkedMatrixmat)//矩阵相加}《数据结构（Java版）（第4版）》第5章31目前三十一页\总数四十三页\编于七点矩阵相加，this+=matpublicvoidaddAll(LinkedMatrixmat){

if(this.rows==mat.rows&&this.columns==mat.columns)for(inti=0;i<this.rows;i++)this.rowlist.get(i).addAll(mat.rowlist.get(i)); //调用多项式单链表相加算法

elsethrownewIllegalArgumentException("两个矩阵阶数不同，不能相加");}《数据结构（Java版）（第4版）》第5章32目前三十二页\总数四十三页\编于七点单链表各类的addAll(list)方法《数据结构（Java版）（第4版）》第5章33目前三十三页\总数四十三页\编于七点【实验题5-3】LinkedMatrix类//深度拷贝，复制所有元素对象publicLinkedMatrix(LinkedMatrixmat)//返回this+mat相加的矩阵，不改变this和matpublicLinkedMatrixunion(LinkedMatrixmat)【实验5-1】Matrix矩阵类的方法《数据结构（Java版）（第4版）》第5章34目前三十四页\总数四十三页\编于七点5.稀疏矩阵十字链表稀疏矩阵十字链表结点（data数据域，down行后继结点，next列后继结点）《数据结构（Java版）（第4版）》第5章35目前三十五页\总数四十三页\编于七点十字链表存储的稀疏矩阵类publicclassCrossNode//矩阵十字链表结点类{Tripledata;//数据域表示三元组

CrossNodedown,next;//行后继，列后继结点}publicclassCrossLinkedMatrix//十字链表矩阵类{privateintrows,columns;//行数、列数

privateCrossNoderowheads[],columnheads[];//行指针数组和列指针数组}《数据结构（Java版）（第4版）》第5章36目前三十六页\总数四十三页\编于七点习题5-9

十字链表习题解答，4-0样卷《数据结构（Java版）（第4版）》第5章37目前三十七页\总数四十三页\编于七点习图5.1矩阵的存储结构分类《数据结构（Java版）（第4版）》第5章38目前三十八页\总数四十三页\编于七点5.3广义表

5.3.1广义表ADT广义表定义GList=(a0,a1,…,an-1)中国(北京,上海,江苏(南京,苏州),浙江(杭州),广东(广州))L＝(a,b)//线性表，长度为2，深度为1T＝(c,L)＝(c,(a,b))//L为T的子表，T的长度为2，深度为2G＝(d,L,T)＝(d,(a,b),(c,(a,b)))//L、T为G的子表，G的长度为3，深度为3S＝()//空表，长度为0，深度为1S1＝(S)＝(())//元素是一个空表，长度为1，深度为2Z＝(e,Z)＝(e,