数据结构第五章 第一节.ppt

1、第五章 数组和广义表,数组的定义 数组的顺序表示和实现 矩阵的压缩存储 广义表的定义 广义表的存储结构 广义表的递归算法,数组的抽象数据类型,Ab1b2bn-1,数组名,维数,数组的抽象数据类型,Ab1b2bn-1,基本操作:,(1) InitArray ( /数组元素基址, int dim; /数组维数 int *bounds; /数组维界基址 int *constants; /数组映象函数常量基址 Array;,Array a; a. base = NULL; a.bounds = NULL; a.constants = NULL;,补充知识_C中可变参数函数,printf( ) / sc

2、anf( ) printf( “%d %d”, k, l); printf( “%s, %d, %d”, szName, k, l); 函数的参数个数是可变的 考虑方法： 在函数调用时，依次把实参入栈，在函数中出栈，其中并没有指明栈的数据元素的数据类型，只是根据参数类型不同，入栈的字节数也不同，栈并不解释数据类型，实际只关心每个参数的字节数。即栈的数据元素为BYTE。 栈也不关心入栈的字节数，入栈数和出栈字节数相同，是通过函数定义和函数调用完全匹配来保证的。 因此可以利用栈做可变参数传递，只要保证入栈字节数和出栈字节数相同,补充知识_C中可变参数函数,考虑方法 函数调用可能是变化的，因此无法限

3、制，需要在被调用函数中处理。 正确解释每个参数 判断可变参数的开始位置 所占的字节数。 函数定义： 一定要有一个确定的参数，用来标定可变参数的开始位置（可变参数从该位置的下一个开始） 每个参数的数据类型，依靠用户自己掌握； 参数列表的长度系统无法控制，由用户自己负责解释。,补充知识_C中可变参数函数,C处理方法_stdarg.h 定义数据类型：va_list，用来表示参数存放的空间类型（实际就是栈的类型）； typedef void*va_list; 找可变参数的开始位置： va_start( ap, argm ); 取参数 va_arg( ap, int );/ 数据类型已知 结束 va_e

4、nd( ap );,C中可变参数函数_例1,#include “stdarg.h” int avg( int a, );/ 求均值 main( ) int k; k = avg( 2, 3, 4, 5, -1 );/ -1表示可变参数的结束位置 printf( “%d”, k); ,C中可变参数函数_例1,int avg( int a, ) int m, n = 0; va_list ap; va_start( ap, a );/开始位置为a后 while( ( m = va_arg( ap, int ) != -1 )/ 数据类型为int a += m; n+; / 通过-1判断结束位置 v

5、a_end( ap ); return a/n; ,C中可变参数函数_例2,#include “stdarg.h” int avg( int n, );/ n用于表示实际可变参数的个数 main( ) int k; k = avg( 4, 2, 3, 4, 5 ); printf( “%d”, k); ,C中可变参数函数_例2,int avg( int n, ) int m, i, a = 0; va_list ap; va_start( ap, n );/ 取实际个数 for( i = 0; i n; i+ ) a += va_arg( ap, int );/ int的数据类型 va_end

6、( ap ); return a/n; ,Status InitArray (Array ,1. 构造数组,va_end(ap); A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType); if(!A.base) exit(OVERFLOW); /求映象函数的常数ci,并存入A.constanti-1,i=1,.,dim if(!A.constants) exit(OVERFLOW); A.constantsdim-1=1; /L=1,指针的增减以元素的大小为单位 for(i=dim-2;i=0;-i) A.constantsi=A.bound

7、si+1*A.constantsi+1; return OK; /InitArray,Status DestroyArray(Array ,2. 销毁数组,Status Locate(Array A, va_list ap, int /Locate,3. 取数组元素的值,Status Value(Array A, ElemType /Value,3. 取数组元素的值,Status Assign(Array /Assign,4. 数组元素赋值,5.3 矩阵的压缩存储,压缩存储的含义: 为多个相同的元只分配一个存储空间 对零元不分配空间,对称矩阵,假设以数组sa0.n(n+1)/2来存储A,则sa

8、k和矩阵元aij之间有,N阶对称矩阵A,对称矩阵的存储格式,三角矩阵,对角矩阵,非零元素较少，分布稀疏 稀疏因子： = t/(m*n) = 0.05 存贮结构 顺序存贮结构 链式存贮结构,稀疏矩阵,稀疏矩阵,ADT SpareMatrix,数据对象：,数据关系：,(1) CreateSMatrix ( /非零元素的行下标和列下标 ElemType e; Triple; typedef union Triple dataMAXSIZE+1; /非零元三元组表，data0未用 int mu,nu,tu; /矩阵的行数，列数和非零元个数 TSMatrix,M.data,T.data,点将法,矩阵的转

9、置,（1）将矩阵的行列值相互交换 （2）将每个三元组中的i和j相互调换 （3）重排三元组之间的次序,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,稀疏矩阵转置算法,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,T.data,Status TransposeSMatrix(TSM

10、atrix M,TSMatrix /TransposeSMatrix,M.data,T.data,q,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,

11、T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,

12、TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,

13、p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix

14、M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=

15、1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatri

16、x M,TSMatrix /TransposeSMatrix,M.data,q,col=1,T.data,p,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,T.data,p,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,co

17、l=1,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=2,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=2,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=2,p,T.data,Status TransposeSMatrix(TSMat

18、rix M,TSMatrix /TransposeSMatrix,M.data,q,col=2,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=2,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,col=2,p,T.data,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,M.data,q,

19、col=7,p,T.data,a.data,b.data,填坑法,M中每一列第一个非零元素的位置,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,快速转置算法,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,T.data,M.data,Status

20、 FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M

21、.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTran

22、sposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,M.data,Status FastTransposeSMatrix(TSMatrix M,TS

23、Matrix /FastTransposeSMatrix,t,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=3,M.data,S

24、tatus FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=4,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=4,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=5,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatri

25、x /FastTransposeSMatrix,t,col=5,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=7,M.data,Status

26、 FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,col=7,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,t,T.data,1,2,3,4,6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,M.data,Status FastTransposeSMatrix(T

27、SMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,col=2,q,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=2,M.data,Status FastTransp

28、oseSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Statu

29、s FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,

30、M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=1,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,

31、4,6,q,col=1,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=1,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=1,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T

32、.data,1,2,3,4,6,q,col=1,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTranspos

33、eSMatrix,p,T.data,1,2,3,4,6,q,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /

34、FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=6,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix

35、M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=3,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransposeSMatrix,p,T.data,1,2,3,4,6,q,col=2,M.data,Status FastTransposeSMatrix(TSMatrix M,TSMatrix /FastTransp