《数据结构C语言版数组和广义表》由会员分享，可在线阅读，更多相关《数据结构C语言版数组和广义表（6页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表重点难点理解数组和广义表两种数据结构的特点，并掌握数组在以行为主的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。典型例题 1. 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量 B0.3n-3中，使得 Bk=aij,求：(1)用 i , j 表示 k 的下标变换公式。(2)用 k 表示 i,j 的下标变换公式。【解】(1) 要求 i,j 到 k 的下标变换公式，就是要知道在 k 之前已有几个非零元素，这些非零元素的个数就是 k 的值，一个元素所在行为 i,所在列为 j,则在其前面已有的非零元素个数为：(i*3-1)+
2、j-(i+1) 其中 (i*3-1)是这个元素前面所有行的非零元素个数， j-(i+1)是它所在列前面的非零元素个数化简可得：k=2i+j; / c 下标是从 0 开始的。(2) 因为 K 和 i,j 是一一对应的关系，因此这也不难算出：i=(k+1)/3 /k+1 表示当前元素前有几个非零元素,被 3 整除就得到行号j=(k+1)%3+(k+1)/3-1 /k+1 除以 3 的余数就是表示当前行中第几个非零元素，/加上前面的 0 元素所点列数就是当前列号2. 设二维数组 A5*6 的每个元素占 4 个字节，已知 Loc(a00)=1000，A 共占多少个字节? A 的终端结点 a45 的起始
3、地位为何 ?按行和按列优先存储时， a25 的起始地址分别为何?解：(1)因含 5*6=30 个元素，因此 A 共占 30*4=120 个字节。(2)a45 的起始地址为：Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116(3)按行优先顺序排列时，a25=1000+(2*6+5)*4=1068(4)按列优先顺序排列时：(二维数组可用行列下标互换来计算)a25=1000+(5*5+2)*4=11083. 当稀疏矩阵 A 和 B 均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表 C 中。解：矩阵相加就是将两个矩阵中同一位置的元素值相
4、加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表 C 时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是 A 的，按照矩阵元素的行列去找 A 中的三元组，若有，则加入 C，同时，这个元素如果在 B 中也有，则加上 B 的这个元素值，否则这个值就不变;如果 A 中没有，则找 B，有则插入 C，无则查找下一个矩阵元素。#define MaxSize 10 /用户自定义typedef int DataType; /用户自定义typedef struct /定义三元组int i,j;DataType v;TriTupleNode;typedef struct /定义三
5、元组表TriTupleNode dataMaxSize;int m,n,t;/矩阵行，列及三元组表长度TriTupleTable;/以下为矩阵加算法 void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C)/三元组表表示的稀疏矩阵 A,B 相加int k,l;DataType temp;C-m=A-m;/矩阵行数C-n=A-n;/矩阵列数C-t=0; /三元组表长度k=0; l=0;while (kt<)if(A-datak.i=B-datal.i)&(A-datak.j=B-datal.j)temp=A
6、-datak.v+B-datal.v;if (!temp)/相加不为零，加入 CC-datac-t.i=A-datak.i;C-datac-t.j=A-datak.j;C-datac-t+.v=temp;k+;l+;if (A-datak.i=B-datal.i)&(A-datak.jdatal.j)|(A-datak.idatal.i)/将 A 中三元组加入 CC-datac-t.i=A-datak.i;C-datac-t.j=A-datak.j;C-datac-t+.v=A-datak.v;k+;if (A-datak.i=B-datal.i)&(A-datak.jB-datal.j)|(
7、A-datak.iB-datal.i)/将 B 中三元组加入 CC-datac-t.i=B-datal.i;C-datac-t.j=B-datal.j;C-datac-t+.v=B-datal.v;l+;while (kt)/将 A 中剩余三元组加入 CC-datac-t.i=A-datak.i;C-datac-t.j=A-datak.j;C-datac-t+.v=A-datak.v;k+;while (lt)/ 将 B 中剩余三元组加入 CC-datac-t.i=B-datal.i;C-datac-t.j=B-datal.j;C-datac-t+.v=B-datal.v;l+;习题精选一、.
8、单项选择题1. 假设以行序为主序存储二维数组 A=array1.100,1.100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5,5=（ ） 。A808 B818 C1010 D10202. 设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A5,8的存储首地址为（ ） 。ABA+141 BBA+180 CBA+222 DBA+2253. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a 11 为第一元素，其存储地址为 1，每个元素占一个地
9、址空间，则 a85 的地址为（ ） 。A13 B33 C18 D404. 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组 B1.(n(n+1)/2中，则在 B 中确定 aij（i0) i+;while(iAij) mini=j; /修改第 i 行最小元素的列号.for (i=0;ix， 这情况下向 j 小的方向继续查找；二是 Ai,j=c)if(Aij=x) flag=1;break;else if (Aijx) j-; else i+;if(flag) printf(“A%d%d=%d”,i,j,x); /假定 x 为整型.else
10、printf(“矩阵 A 中无%d 元素” ，x)；算法 search 结束。算法讨论算法中查找 x 的路线从右上角开始，向下（当 xAi,j）或向左（当 xright=rch 时该行无非零元素，用 i 记行号，用一维数组元素 Ai记第 i 行非零元个数。（为方便输出，设元素是整数。 ）int MatrixNum(Olink Hm)/输出由 Hm 指向的十字链表中每一行的非零元素个数Olink rch=Hm-uval.next, p;int A; i=1;/数组 A 记各行非零元个数,i 记行号while(rch!=Hm)/循环完各行列表头p=rch-right; num=0; /p 是稀疏矩阵行内工作指针,num 记该行非零个数while(p!=rch)/完成行内非零元的查找printf(“M%d%d=%d”,p-row,p-col,p-uval.e);num+;p=p-right; printf(“n”);/指针后移 Ai+=num;/存该行非零元个数rch=rch-uval.next;/移到下一行列表头num=0for(j=1;ji;j+)/输出各行非零元个数num+=Aj; printf(“第%d 行非零元个数为%dn”,j,Aj); return(num);/稀疏矩阵非零元个数算法结束
