2022年数据结构教程习题答案李蓉蓉安杨等编著第三版答案 .pdf

《2022年数据结构教程习题答案李蓉蓉安杨等编著第三版答案 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构教程习题答案李蓉蓉安杨等编著第三版答案 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.3/*题目：设有三对角矩阵A，将其三对角线上元素逐行存于数组B中求：1：用 i，j 表示 k 的下标变换公式k=2*i+j(下标从 0开始)2：用 k 表示 i，j 的下标公式(下标从 0开始)i=(k+1)/3:(此处取整)j=k-2*i;=k-(k+1)/3*2(此处别化简)什么是三对角矩阵？在线性代数中，一个三对角矩阵是矩阵的一种，它“几乎”是一个对角矩阵。准确来说：一个三对角矩阵的非零系数在主对角线上，或比主对角线低一行的对角线上，或比主对角线高一行的对角线上。例如，下面的是三对角矩阵：1 4 0 0 3 4 1 0 0 2 3 4 0 0 1 3*/*下面是具体的实现*/#inc

2、lude#define size 50/函数的声明void translate(int*b,int asizesize,int n);main()int n;int i,j,k=0;int asizesize;int bsize;printf(输入矩阵的阶数 n);scanf(%d,&n);printf(输入%d 个数据 n,2*(n-1)+(n-1)+1);/2*(n-1)+(n-1)+1 的来历是由上面的公式（2*i+j）推来/三对角矩阵的最后一个元素一定在(n-1,n-1)位置，既然名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 15 页 -/一维组的下标与i，j 有关，那

3、么 k 最大也会在 i=n-1，j=n-1 处/一维数组的下标k 随着 i，j 连续增加的/往三对角矩阵中输入数据while(k2*(n-1)+(n-1)+1)for(i=0;in;i+)for(j=0;jn;j+)if(i=(k+1)/3)&(j=k-(k+1)/3*2)scanf(%d,&aij);k+;else aij=0;printf(你输入的三对角矩是n);for(i=0;in;i+)for(j=0;jn;j+)printf(%d,aij);printf(n);/将三对角矩阵中的元素输入到一位数组b 中translate(b,a,n);printf(压缩后的结果 n);for(i=0

4、;i2*(n-1)+(n-1)+1;i+)printf(%d,bi);printf(n);/进行压缩void translate(int*b,int asizesize,int n)int i,j,k=0;while(k2*(n-1)+(n-1)+1)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 15 页 -for(i=0;in;i+)for(j=0;jn;j+)if(k=2*i+j&0!=aij)bk+=aij;/*输入矩阵的阶数4 输入 10 个数据1 2 3 4 5 6 7 8 9 3 你输入的三对角矩是1 2 0 0 3 4 5 0 0 6 7 8 0 0 9 3 压缩

5、后的结果1 2 3 4 5 6 7 8 9 3 Press any key to continue*/5.5/*题目：设定二维整数数组B0.m-1,0.n-1的数据在行列上都按从小到大的顺序排序，且整型变量 x 中的数据在 B 中存在。试设计一个算法找出一对满足 Bij=i,j 值，要求比较次数不超过m+n 设计;狼影时间：2012.9.30*/*！下面是自己的看法，若有不对之处（或有更好的方式），请留言本空间，万分感谢既然有序，就要好好利用一下喽，首先想到的就是二分查找，那怎么个二分法呢？我 的 方 法 是 将 二 维 当 做 一 维 用。时 间 复 杂 度 是名师资料总结-精品资料欢迎下载

6、-名师精心整理-第 3 页，共 15 页 -O(log2(m*n)=O(log2m+log2n)O(m+n)*/#include int i=-1,j=-1;/函数声明void print_arry(int a55);void find_x(int a55,int x);main()int x;int a55=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25;print_arry(a);printf(输入要查找的数 n);scanf(%d,&x);/在数组中寻找x find_x(a,x);if(-1=i|-1=j

7、)printf(没有要查找的数据n);else printf(x 的位置是(%d,%d)n,i,j);/输出数组中的内容void print_arry(int a55)int i,j;for(i=0;i5;i+)for(j=0;j5;j+)printf(%2d,aij);printf(n);名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 15 页 -/寻找 x 的位置void find_x(int a55,int x)int mid;int x1=0,y1=24;while(x1a0mid)x1=mid+1;else y1=mid-1;/*1 2 3 4 5 6 7 8 9 10

8、 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 输入要查找的数21 x 的位置是(4,0)Press any key to continue*/5.6/*题目：编写一个算法，计算一个三元组表示的稀疏矩阵的对角线之和设计：狼影时间：2012.9.28*/*名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 15 页 -这里求的是行和列相等的矩阵对角线元素和，如果你会行和列不相等的矩阵对角线元素法，告诉一声啊，万分感激（不用三元组页可以哦！）*/#include#define size 100 typedef struct int x;/存放某

9、一个非零元的行int y;/存放某一个非零元的列int data;/存放某一个非零元DATA;typedef struct int row;/存储矩阵的总行数int col;/存储矩阵的总列数int number;/存储非零元的个数DATA arrysize;/三元组数组NODE;/函数的声明void reduce(int asizesize,NODE*MA,int n);void print_arry(NODE MA);int cal_sum(NODE MA,int n);main()int n;NODE MA;int i,j;int sum=0;int asizesize;printf(输

10、入矩阵的阶数 n);scanf(%d,&n);/对矩阵进行赋值printf(输入矩阵元素 n);for(i=0;in;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 15 页 -for(j=0;jcol=n;MA-row=n;MA-number=0;for(i=0;in;i+)for(j=0;jarryMA-number.x=i;MA-arryMA-number.y=j;MA-arryMA-number.data=aij;MA-number+;/打印压缩矩阵void print_arry(NODE MA)int i;if(0=MA.number)名师资料总结-精品资料欢迎下

11、载-名师精心整理-第 7 页，共 15 页 -printf(三元组空 n);return;for(i=0;iMA.number;i+)printf(%d,%d)*%dn,MA.arryi.x,MA.arryi.y,MA.arryi.data);/求对角线的和int cal_sum(NODE MA,int n)int sum=0;int i;if(0=MA.number);else for(i=0;iMA.number;i+)if(MA.arryi.y=MA.arryi.x|(n-1)=(MA.arryi.x+MA.arryi.y)/是矩阵对角线的条件 sum+=MA.arryi.data;re

12、turn sum;/*输入矩阵的阶数3 输入矩阵元素1 2 3 4 5 6 0 4 0(0,0)*1(0,1)*2(0,2)*3(1,0)*4(1,1)*5 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 15 页 -(1,2)*6(2,1)*4 对角线的和是 9 Press any key to continue*/5.8/*题目：设计一个算法same(*h1,*h2)判断两个广义表相同设计;狼影时间：2012.9.29*/*此算法根据线性表推倒而出，若测试有不对之处，请留言本人空间，你的留言将是对本人学习的最大帮助，万分感谢*/#include#include#include

13、#define size 100/节点的定义typedef struct node int tag;/标记union char data;struct node*sublist;VALUE;struct node*pNext;NODE;/函数的声明NODE*new_node(void);NODE*creat(void);void output(NODE*p);int same(NODE*p1,NODE*p2);名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 15 页 -char*s;main()NODE*h1;NODE*h2;int n;char s1size;char s2si

14、ze;/输入广义表的内容printf(输入广义表1内容，格式为(a,(b,c)n);gets(s1);fflush(stdin);printf(输入广义表2内容，格式为(a,(b,c),(a,f)n);gets(s2);/构造广义表s=s1;h1=creat();s=s2;h2=creat();printf(输出广义表的内容是n);/输出广义表（此处只是对广义表的输出，如果只是向完成题目要求并且嫌麻烦，接下来的四句可以省略）output(h1);printf(n);output(h2);printf(n);/*n=same(h1-V ALUE.sublist,h2-VALUE.sublist)

15、;if(0=n)printf(两广义表不相等 n);else printf(两个广义表相等 n);/建立广义表NODE*creat()名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 15 页 -char ch;NODE*pNew;ch=*s+;if(ch!=0)pNew=new_node();if(=ch)pNew-tag=1;/1标记子表pNew-VALUE.sublist=creat();/递归的建立子表 else if()=ch)pNew=NULL;else pNew-tag=0;/0标记原子pNew-VALUE.data=ch;else pNew=NULL;if(pNe

16、w!=NULL)ch=*s+;if(,=ch)pNew-pNext=creat();/建立兄弟表else pNew-pNext=NULL;return pNew;/创建新的节点NODE*new_node(void)NODE*pNew;pNew=(NODE*)malloc(sizeof(NODE);if(NULL=pNew)名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 15 页 -printf(内存分配错误 n);exit(-1);pNew-pNext=NULL;return pNew;/输出广义表的内容void output(NODE*p)if(NULL!=p)if(1=p-

17、tag)printf();if(NULL=p-V ALUE.sublist)printf();else output(p-VALUE.sublist);else printf(%c,p-VALUE.data);if(1=p-tag)printf();if(p-pNext!=NULL)printf(,);output(p-pNext);/判断两个广义表是否相等int same(NODE*p1,NODE*p2)int n=0;if(NULL=p1&NULL=p2)n=1;else if(NULL!=p1&NULL=p2|NULL=p1&NULL!=p2)n=0;else 名师资料总结-精品资料欢迎

18、下载-名师精心整理-第 12 页，共 15 页 -if(1=p1-tag&1=p2-tag)n=(same(p1-VALUE.sublist,p2-VALUE.sublist)&same(p1-pNext,p2-pNext);if(0=p1-tag&0=p2-tag&p1-VALUE.data=p2-VALUE.data)n=1;n=same(p1-pNext,p2-pNext);return n;/*输入广义表 1 内容，格式为(a,(b,c)(a,f),(),(),(),b,f)输入广义表 2 内容，格式为(a,(b,c),(a,f)(a,f),(),(),()输出广义表的内容是(a,f)

19、,(),(),(),b,f)(a,f),(),(),()两广义表不相等Press any key to continue*/*下面是两个链表比较是否相同的递归方法，根据它，来写广义表的比较方法（从某种意义说，广义表也是线性表，它有着和线性表相同的的性质）很多基本算法都可以根据线性表来推出广义表的算法*(仅供参考)*/*typedef struct node int data;struct node*pNext;NODE;/函数的声明NODE*init_list(void);名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 15 页 -void creat_list(NODE*pH

20、ead,int n);int same(NODE*p1,NODE*p2);main()NODE*pHead1,*pHead2;int s;int n,m;pHead1=init_list();pHead2=init_list();printf(输入第一个链表的个数n);scanf(%d,&n);creat_list(pHead1,n);printf(输入第二个链表的个数n);scanf(%d,&m);creat_list(pHead2,m);s=same(pHead1-pNext,pHead2-pNext);if(1=s)printf(相等 n);else printf(不相等 n);/初始化

21、头节点NODE*init_list(void)NODE*pHead=(NODE*)malloc(sizeof(NODE);if(NULL=pHead)printf(内存分配失败 n);exit(-1);pHead-pNext=NULL;return pHead;/创建链表void creat_list(NODE*pHead,int n)int i;NODE*pNow=pHead,*pNew;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 15 页 -printf(输入%d 个数据 n,n);for(i=0;ipNext=NULL;scanf(%d,&pNew-data);pNow-pNext=pNew;pNow=pNew;/用递归的方式比较两个链表是不是相等int same(NODE*p1,NODE*p2)int s=0;if(NULL=p1&NULL=p2)s=1;else if(NULL=p1&NULL!=p2|NULL=p2&NULL!=p1)s=0;else if(p1-data=p2-data)s=same(p1-pNext,p2-pNext);else s=0;return s;*/*/*/名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 15 页 -