《数据结构域算法设计-数组和广义表 教案》由会员分享，可在线阅读，更多相关《数据结构域算法设计-数组和广义表 教案（12页珍藏版）》请在金锄头文库上搜索。
1、5-1第五章第五章 数数组组和广和广义义表表 继续增加线性表结构的内涵。 数组结构每个子结构是由基本元素组成的大小均等的线性表。 广义表结构 每个子结构或是基本元素，或是由基本元素组成的大 小不等的线性表结构。 本章学习要点： 掌握数组的相关概念 掌握特殊矩阵的压缩存储方式 掌握稀疏矩阵的存储方法 掌握广义表的相关运算 掌握广义表的存储结构 掌握广义表的基本运算的实现第一第一节节 数数组组的的逻辑结逻辑结构构1_Array1_Array=(D, S, P) 定长线性表D = ai| aiElemSet, i=0,1,2, n-1S = | ai-1,aiD, i=1,2,n-12_Array2
2、_Array=(D, S, P) 定长线性表，每个元素又是定长线性表。 D = ai,j| ai,jElemSet, i=0,1,n1-1; j=0,1,n2-1 S = ROW,COL ROW=| i=0,1,n1-1; j=1,n2-1 COL=| i=1,n1-1; j=0,1,n2-13_Array3_Array=(D, S, P) 增加层的关系 基本操作：取值、赋值。第二第二节节 数数组结组结构的构的顺顺序存序存储结储结构构 数组结构是多维的，内存地址是一维的。存储方式：行主序，列主序以行主序为例：5-2一维： LOC(ai) =base+i二维(MxN)： LOC(ai,j) =b
3、ase+i*N +j三维(MxNxP)： LOC(ai,j,k) =base+i*N*P +j*P +k四维(MxNxPxQ)：LOC(ai,j,k,l)=base+i*N*P*Q+j*P*Q+k*Q+lTypedef struct ElemType *base;int dim; 维数int *bounds; 各维元素个数int *constants; 各维包含的基本元素个数 Array; 例：数例：数组组 A3,4,5,6的存储结构A.dim=4 A.bounds=3,4,5,6A.constants=120,30,6,1Ai,j,k,l的地址: A.base+(i*120+j*30+k*6
4、+l) 1 1、初始化数、初始化数组结组结构构 void Array_Init(Array A.bounds=(int *)malloc(dim*sizeof(int); A.constants=(int *)malloc(dim*sizeof(int); if(!A.bounds | !A.constants) printf(“overflow!”); return;for(i=0;i=0;i-)for(A.constantsdim-1=1,i=dim-2;i=0;i-) A.constantsi=A.boundsi+1*A.constantsi+1;A.constantsi=A.bound
5、si+1*A.constantsi+1;/开辟数组空间 elemtotal=A.bounds0*A.constants0;A.base=(ElemTypeA.base=(ElemType *)malloc(elemtotal*sizeof(ElemType);*)malloc(elemtotal*sizeof(ElemType); if(!A.base) printf(“overflow!”); return; printf(“OK!”); 2 2、取、取值值 ElemType Array_GetValue(Array A,int dim_i)/dim存放要求 元素的下表 int offset
6、;for(offset=0,i=0;i=j:i=j: k=i*(i+1)/2+jk=i*(i+1)/2+j 若若 i Sk, k=i(2d+1)+d+(j-i) 改进方案：S(2d+1)n-2dS(2d+1)n-2d，去掉数组前后 2d 个 0。 aij = Sk, k=i(2d+1)+(j-i) 培养摸索数据培养摸索数据规规律的感律的感觉觉。 。数数据据结结构构（C+版版）清清华华大大学学出出版版社社矩矩阵阵中中任任一一元元素素aij在在数数组组中中的的下下标标k与与i、j的的对对应应关关系系：i( (2ni1) )/2ji 当当ijn( (n1) ) /2 当当ijk=上上三三角角矩矩阵阵
7、的的压压缩缩存存储储矩矩阵阵的的压压缩缩存存储储存存储储上上三三角角元元素素对对角角线线上上方方的的常常数数只只存存一一个个3 481 0 c2 946 cc5 7 ccc0 8 cccc7(b)上上三三角角矩矩阵阵3 481 0 c2 946 cc5 7 ccc0 8 cccc7(b)上上三三角角矩矩阵阵(a)下下三三角角矩矩阵阵3 cccc 6 2ccc 4 81cc 746 0c 829 5 7(a)下下三三角角矩矩阵阵3 cccc 6 2ccc 4 81cc 746 0c 829 5 73 cccc 6 2ccc 4 81cc 746 0c 829 5 75-6二、稀疏矩二、稀疏矩阵阵
8、之三元之三元组组表表 稀疏因子很小的大型矩阵：非 0 数很少，且无规律。1 1、三元、三元组组的的顺顺序表序表 #define MAXSIZE 1000 typedef struct /三元组结构 int i,j; ElemType e; Triple; typedef struct /三元组顺序表(按行主序) int mu,nu,tu; Triple dataMAXSIZE;/静态顺序表 /* Triple *data; 动态顺序表 */ TSMatrix;2 2、 、转转置运算置运算 M=TM=T (以 T 为中心)= 03020005000500400010000300 05000300
9、4002000005030001005-7M.data: T.data:i j e i j e0 1 30 0 1 10 1 0 10 1 0 30 1 3 40 1 2 -5 2 1 -5 = 2 3 202 4 50 3 1 403 2 20 3 3 303 3 30 4 2 50Status TSMatrix_Transpose(TSMatrix M,TSMatrix T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu=0) return(OK); for(k=0,col=0;for(k=0,col=0; colTM=T (以 M 为中心)基基本本思思想想：直
10、直接接取取，顺顺序序存存。即即在在A的的三三元元组组顺顺序序 表表中中依依次次找找第第0列列、第第1列列、直直到到最最后后一一列列的的三三元元组组，并并将将找找到到的的每每个个三三元元组组的的行行、列列交交换换后后顺顺序序存存 储储到到B的的三三元元组组顺顺序序表表中中。5-8辅助数据结构： num：M 中每列(T 中每行)的三元组个数。 =pos：T 中每行第一个三元组的下标。 pos0=0; posj=posj-1+numj-1; j1,M.nu-1= 03020005000500400010000300 05000300400200000503000100num0 num1 num2 n
11、um3 num4 1, 2, 1, 2, 1 pos0 pos1 pos2 pos3 pos4 0, 1, 3, 4, 6 M.data: T.data:i j e 下标 i j e 0 1 30 0 0 1 10 1 0 10 1 1 0 30 1 3 40 2 1 2 -5 2 1 -5 = 3 2 3 20 2 4 50 4 3 1 40 3 2 20 5 3 3 30 3 3 30 6 4 2 50Status TSMatrix_FastTranspose(TSMatrix M,TSMatrix T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu=0) re
12、turn(OK);/统计 M 中每列的三元组个数for(i=0;i十字链表。三、稀疏矩三、稀疏矩阵阵之十字之十字链链表表 十字链表的存储结构：真正等价于矩阵的逻辑结构。 1 1、十字、十字链链表表5-10typedef struct OLNode /结点类型 int i,j; ElemType e;struct OLNode *right,*down; OLNODE; typedef struct int mu,nu,tu; OLNODE *rhead,*chead; /行、列头结点表 CrossList; 图图示示：4x5 矩阵的十字链表，含非 0 数： (1,1:1) (3,1:2) (3
13、,4:3) 用 right 构成行行链链表，表，用 down 构成列列链链表表。2 2、建立、打印十字、建立、打印十字链链表的算法表的算法 按行主序打印矩阵 M void CrossList_Print(CrossList M) OLNODE *p; int i;printf(“%d,%d,%dn“,M.mu,M.nu,M.tu);for(i=0; iright)printf(“%d,%d:%dn“,p-i,p-j,p-e); 根据三元组顺序表 T，建立十字链表 M5-11void CrossList_Create(CrossList *M, TSMatrix *T) OLNODE *new; int i;CrossList_Init(M,T-mu,T-nu);for(i=0; itu; i+) /* 插入各个三元组结点 */CrossList_Insert(M,T-datai); 初始化十字链表结构 M void CrossList_Init(CrossList M.mu=mu; M.nu=nu; M.tu=0;/初始化行头表、列头表M.rhead=(OLNODE *)malloc(M.mu*sizeof(OLNODE);for(i=0; iright=NULL;M.chead=(OLNODE *)malloc(M.nu*sizeof(OL
