数据结构第五章数组和广义表.doc

第五章 数组和广义表（一）数组 1数组的基本概念 数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、in称为该元素的下标，并称该数组为 n 维数组。 元素本身可以具有某种结构，属于同一数据类型； 数组是一个具有固定格式和数量的数据集合。2 数组的顺序表示和实现 3 矩阵的压缩存储A 对称矩阵 B （上下）三角矩阵 C 对角矩阵 D 稀疏矩阵 三元组的顺序表#define MAXSIZE 1000typedef struct /三元组结构 int i,j; ElemType e; Triple;typedef struct /三元组顺序表 int mu,nu,tu; /mu行维界,nu列维界,tu 非0的个数 Triple dataMAXSIZE;/静态顺序表 / Triple *data; 动态顺序表 TSMatrix; 三元顺序表存储方式下的矩阵转置： 转置操作方法1：直接取，顺序存 该算法的伪语言描述如下：1. 设置转置后矩阵B的行数、列数和非零元个数；2. 在B中设置初始存储位置pb；3. for (col=最小列号; coltag=ATOM) return(0); for(p=L-UNION.child; p; p=p-next) depth1=GList_Depth(p); if(depth1max) 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-UNION.atom; if(p-tag=ATOM) newp-tag=ATOM; newp-UNION.atom=p-UNION.atom; else newp-tag=LIST;newp-UNION.child=GList_Copy(p-UNION.child); tail-next=NULL; return(head);建立广义表/ 根据str=(a (b c) d)建广义表typedef enum LP=1,RP=2,Atom=3,End=4 ElemFlag;/从str*pi开始读入一个元素ElemFlag GetElem(char str,int *pi,AtomType *pe) while(str*pi= ) (*pi)+; if(str*pi=0) return(End); if(str*pi=() (*pi)+; return(LP); if(str*pi=) (*pi)+; return(RP); *pe=str*pi; (*pi)+; return(ATOM);GLNODE *Glist_Create(char str,int *pi) GLNODE *p; AtomType e; switch(GetElem(str,pi,&e) case ATOM: p=(GLNODE *)malloc(sizeof(GLNODE); p-tag=ATOM; p-UNION.atom=e; p-next=Glist_Create(str,pi); return(p); case LP: p=(GLNODE *)malloc(sizeof(GLNODE); p-tag=LIST; p-UNION.child=Glist_Create(str,pi); p-next =Glist_Create(str,pi); return(p); case RP: return(NULL); case End: return(NULL); （三）数组和广义表的基本习题（1） 二维数组M的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i 的范围是从0到4，列下标j的范围是从0到5，M按行存储时元素M35的起始地址与M按列存储时元素 的起始地址相同 A M24 B M34 C M35 D M44 （2） 一个n*n的矩阵，如果以行或列为主序放入内存，则容量为 （3）设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B1，n(n-1)/2中，对任一下三角部分中的任一元素aij （ij）,在一维数组B的下标位置k的值是 （4）编写一个算法，将数组（a0,a1,a2,an）逆置为(an,a2,a1,a0)（5）设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和（6）广义表（a）,a）