资源描述：
《数据结构第五章数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表（一）数组1数组的基本概念数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。Ø元素本身可以具有某种结构，属于同一数据类型；Ø数组是一个具有固定格式和数量的数据集合。16162数组的顺序表示和实现163矩阵的压缩存储A对称矩阵16B（上下）三角矩阵16C对角矩阵16D稀疏矩阵三元组的顺序表#defineMAXSIZE1000typedefstruct//三元
2、组结构{inti,j;ElemTypee;}Triple;typedefstruct//三元组顺序表{intmu,nu,tu;//mu行维界,nu列维界,tu非0的个数Tripledata[MAXSIZE];//静态顺序表//Triple*data;动态顺序表}TSMatrix;16三元顺序表存储方式下的矩阵转置：转置操作方法1：直接取，顺序存16该算法的伪语言描述如下：1.设置转置后矩阵B的行数、列数和非零元个数；2.在B中设置初始存储位置pb；3.for(col=最小列号;col<=最大列号;col++)3.1在A中查找列号为col的三
3、元组；3.2交换其行号和列号，存入B中pb位置；3.3pb++；见课本P99具体算法转置操作方法2顺序取，直接存16该算法的伪语言描述如下：1.设置转置后矩阵B的行数、列数和非零元素的个数；2.计算A中每一列的非零元素个数；3.计算A中每一列的第一个非零元素在B中的下标；4.依次取A中的每一个非零元素对应的三元组；4.1确定该元素在B中的下标pb；4.2将该元素的行号列号交换后存入B中pb的位置；4.3预置该元素所在列的下一个元素的存放位置；见课本P100具体算法16E十字链表typedefstructOLNode{introw,col;/
4、/非零元的行列号ElemTypeelem;structOLNode*right,*down;//行列的后继链域}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;//行头结点和列头结点向量introws,cols,vals;//稀疏矩阵的行数，列数和非零元素数}CrossList;16二广义表1广义表的基本概念广义表：n（n≥0）个数据元素的有限序列，记作：LS＝(a1，a2，……，an)其中：LS是广义表的名称，ai（1≤i≤n）是LS的成员（或直接元素），它可以是单个的数据元素，也可以是一个广
5、义表，分别称为LS的单元素（或原子）和子表。通常用大写字母表示广义表，用小写字母表示单元素。2广义表的基本操作取表头和表尾16求深度3广义表的存储结构typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;//区别子表结点、原子结点union{AtomTypeatom;structGLNode*child;//指向子表的指针、16}structGLNode*next;//后继指针}GLNODE,*Glist;广义表的另一存储结构示例typedefenum{ATOM,LIST}
6、ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*child,*next;}ptr;};}GLNODE,*Glist;164广义表基本操作的实现求表深度intGList_Depth(GLNODE*L){GLNODE*p;intdepth1,max=0;if(L->tag==ATOM)return(0);for(p=L->UNION.child;p;p=p->next){depth1=GList_Depth(p);if(depth1>ma
7、x)max=depth1;}return(max+1);}复制广义表//类似于“复制单向链表”GLNode*GList_Copy(GLNode*L){GLNODE*head=NULL,*p,*newp,*tail;if(!L)return(NULL);for(p=L;p!=NULL;p=p->next){newp=(GLNODE*)malloc(sizeof(GLNODE));if(head==NULL)head=tail=newp;else{tail->next=newp;tail=newp;}//newp->UNION.atom=p->
8、UNION.atom;if(p->tag==ATOM){newp->tag=ATOM;newp->UNION.atom=p->UNION.atom;}else{newp->tag
