数据结构C语言版第五章数组和广义表.doc_第1页
数据结构C语言版第五章数组和广义表.doc_第2页
数据结构C语言版第五章数组和广义表.doc_第3页
数据结构C语言版第五章数组和广义表.doc_第4页
数据结构C语言版第五章数组和广义表.doc_第5页
已阅读5页,还剩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)+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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论