Ch04-SW-CMM模型

《Ch04-SW-CMM模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Chapter4-2ListdevelopmentTwo---Array数组(Array)---多维定长线性表是线性表的推广，表中的数据元素本身也是一个线性表。举例：二维数组---可看作由定长一维表组成的定长一维表。n维数组：各维定长的n维表。-bi（1<=i<=n)是数组第i维的长度。则数组元素的第i维下标ji的取值范围0~bi-1。ADT接口：InitArray(&A,n,b1,b2,…,bn)---数组初始化DestroyArray(&A)----撤销数组Value(A,&e,index1,…,indexn)---取数组元素值Assign(&A,e,index1,…,i

2、ndexn)---数组元素赋值A=（A0,A2,…,An-1)Ai=(ai0,ai1,….,ain-1)数组的顺序存储方式：1）一维数组LOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0352749186054778341020123456789lllllllllla+i*la2）二维数组行优先存放：设数组开始存放位置LOC(0,0)=a,每个元素占用d个存储单元。LOC(j,k)=a+(j*m+k)*d列优先存放：列优先存放：设数组开始存放位置LOC(0,0)=a,每个元素占用d个存储单元LOC(j,k)=a+(k*n+j)*d3）三维数组各维元素个数为b1,

3、b2,b3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列顺序存放）LOC(i1,i2,i3)=a+(i1*b2*b3+i2*b3+i3)*li1*b2*b3_——前i1页总元素个数i2*b3——第i1页的前i2行总元素个数i3——第i2行前i3列元素个数4）n维数组各维元素个数为b1,b2,b3,…,bn下标为j1,j2,j3,…,jn的数组元素的存储地址：LOC(j1,j2,…,jn)=a+(j1*b2*b3*…*bn+j2*b3*b4*…*bn++……+jn-1*bn+jn)*lCi，有Ci=bi*Ci-1数组的应用：1）矩阵的压缩存储特殊矩阵的存储——三角矩

4、阵只存储上三角元素或下三角元素一维数组元素的个数-对称阵aij=aji，可以利用三角阵压缩存储方式实现。2）稀疏矩阵用三元组来表示每个数据：（行，列，数值）数组元素操作变成三元组表的操作元素定位==〉三元组顺序表查找（数组）元素插入、删除===〉三元组表插入、删除rpos[]、cpot[]：行、列起始索引矩阵操作：转置、加、减、乘===〉三元组表上运算实现，3）十字链表----三元组链表存储用链表实现稀疏矩阵的存储。行向头结点向量+列向头结点向量非零元素结点同时隶属于行列两条链表广义表的定义：n(0)个表元素组成的有限序列，记作L=(a1,a2,…,an)L是表名，ai是

5、表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。n>0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。广义表的ADT说明GetHead(L)-----取表头操作GetTail(L)-----取表尾操作Chapter4-3ListdevelopmentThree---generalizedList例子：A=()对空表不求表头、表尾B=(6,2)GetHead(B)=6,GetTail(b)=(2)C=(‘a’,(5,3,‘x’))GetHead(C)=‘a’,GetTai

6、l(C)=((5,3,’x’))D=(B,C,A)GetHead(D)=B,GetTail(D)=(C,A)E=(B,D)GetHead(E)=B,GetTail(E)=(D)F=(4,F)GetHead(F)=4,GetTail(F)=(F)特性：有次序性，有长度，可共享，可递归，有深度广义表的应用（1）求对应关系()((NIL))(())NIL((()))(NIL)(()())(NIL(NIL))(()(()))(NILNIL)（2）L=（a,(b,(c),e))利用求表头和求表尾操作将原子e分离出来T(L)=L1=((b,(c),e))H(L1)=L2=(b,(c),

7、e)T(L2)=L3=((c),e)T(L3)=L4=(e)H(L4)=eH(T(T(H(T(L)))))(3)整数序列中，是否存在一个子序列（不一定是连续的）其和等于给定的整数x（12379）12True（12379）-1False可以将整数序列看成是一个广义表：Truex=0表尾中存在一个子序列其和等于x-head(L)表尾中存在一个子序列其和等于xFalseL为空表BoolSublist_sum(L,x){Ifx=0returntrue;If!Lreturnfalse;else{