数据结构C语言版第五章数组和广义表.doc

第五章 数组和广义表重点难点理解数组和广义表两种数据结构的特点，并掌握数组在以行为主的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。典型例题 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)+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的起始地位为何?按行和按列优先存储时，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中。解：矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表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 /定义三元组表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-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)|(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+;习题精选一、.单项选择题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，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B33 C18 D404. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i5.AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN(N+1)/2中，则对任一上三角元素aij对应Tk的下标k是（ ）。Ai(i-1)/2+j Bj(j-1)/2+i Ci(j-i)/2+1 Dj(i-1)/2+16.设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai,j在一维数组B中的下标为（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-17.数组A0.4,-1.-3,5.7中含有元素的个数（ ）。A55 B45 C36 D168. 对稀疏矩阵进行压缩存储目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度9. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。A. 60 B. 66 C. 18000 D. 33 10. 数组A0.4,-1.-3,5.7中含有元素的个数（ ）。A. 55 B. 45 C. 36 D. 16二、算法设计1.设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂性为0(n)）。 题目分析本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。void Arrange(int A,int n) /n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 int i=0,j=n-1,x; /用类C编写，数组下标从0开始 while(ij)while(i0) i+;while(ij & Aj0) j-; if(ij) x=Ai; Ai+=Aj; Aj-=x; /交换Ai 与Aj /算法Arrange结束.算法讨论对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0.n-1。空间复杂度为O(1).2. 请编写完整的程序。如果矩阵A中存在这样的一个元素Ai,j满足条件:Ai,j是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。题目分析 寻找马鞍点最直接的方法,是在一行中找出一个最小值元素,然后检查该元素是否是元素所在列的最大元素,如是,则输出一个马鞍点,时间复杂度是O(m*(m+n).本算法使用两个辅助数组max和min,存放每列中最大值元素的行号和每行中最小值元素的列号,时间复杂度为O（m*n+m），但比较次数比前种算法会增加，也多使用向量空间。int m=10, n=10; void Saddle(int Amn) /A是m*n的矩阵,本算法求矩阵A中的马鞍点. int maxn=0, /max数组存放各列最大值元素的行号,初始化为行号0;minm=0, /min数组存放各行最小值元素的列号,初始化为列号0;i, j; for(i=0;im;i+) /选各行最小值元素和各列最大值元素.for(j=0;jn;j+) if(AmaxjjAij) mini=j; /修改第i行最小元素的列号. for (i=0;ix， 这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否则，若下标已超出范围，则查找失败。void search(datatype A , int a,b,c,d, datatype x) /n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. i=a; j=d; flag=0; /flag是成功查到x的标志 while(i=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 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记该行非零个数 whi