石大远程在线考试——数据结构课程设计85201441854054813

1、中国石油大学（北京）远程教育学院期末考试数据结构课程设计1. 课程设计题目从下面四个题目中任选一题完成。1.1通讯录的制作用单链表作为数据结构，结合 C或者C+语言基本知识，编写一个班级的通讯录管 理系统。系统包括下面几方面的功能：第1:输入信息：输入某同学的信息；第2:显示信息：显示全部通讯录中学生的信息；第3:查找功能：实现按姓名进行查找，并给出查找信息；第4:删除功能：实现按姓名进行删除，并给出操作结果；第5:每名同学的信息包括：姓名、性别、电话、城市；第6:界面友好，每步给出适当的操作提示；第7:系统具有一定的容错能力。1.2图书管理系统设计一个计算机管理系统完成图书管理几本业务。系统

2、要满足下面基本要求：第1:每种图书的登记内容包括：书名、书号、作者、出版社、现存量和库存量；第2:采编入库：新购图书，确定书号后，登记到图书账目表中，如果表中存在 该书，则只将库存量增加；第3:借阅：如果该书的库存量大于0，贝冷出一本，登记借阅者的书证号和归还期限，改变库存量；第4:归还：注销对借阅者的登记，改变该书的库存量；第5:界面友好，每步给出适当的操作提示；第6:系统具有一定的容错能力。1.3产品进销管理系统针对某个行业的库房产品进销存情况进行管理，系统要求具有下列功能：第1:采用一定的存储结构对库房的货品及其数量进行分类管理；第2:可以进行产品类的添加、产品的添加、产品数量的添加；第

3、3:能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；第4:每种产品至少包含信息：产品名、进货日期、进货数量、销出数量、销售 时间、库存量；第5:界面友好，每步给出适当的操作提示；第6:系统具有一定的容错能力。1.4校园导航问题设计中国石油大学（北京）的校园平面图，至少10个场所，可以实现任意两个场包括所的最短路径。2. 课程设计报告书写规范课程设计报告包括该题目的需求分析、概要设计、详细设计、 程序测试、感想与体会几'k'k'k减法、乘法以及矩 阵分别实现矩阵的相 加、部分内容。下面以“稀疏矩阵运算器”为例说明如何写课程设计报告。题目要求： 设计一个稀疏矩阵

4、计算器，实现两个稀疏矩阵的加法、 的转置运算。 采用菜单为应用程序的界面， 用户通过对菜单进行选 择，相减、相乘以及矩阵转速运算。2.1需求分析1. 稀疏矩阵是指稀疏因子小于等于0.5的矩阵。 利用“稀疏” 特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2. 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，以及两个矩阵的加、减、乘的运算。稀疏矩阵的输入形式采用三元组表示，运算结果以阵列形式列出3. 演示程序以用户和计算机的对话方式进行，数组的建立方式为边输入边建立。 首先输入矩阵的行数和列数，并判别给出的两个矩阵的行列数是否与所要

5、求的运算相 匹配。4. 程序可以对三元组的输入属性不加以限制；根据对矩阵的行列，三元组作之 间插入排序，从而进行运算时，不会产生错误。5. 在用三元组表示稀疏矩阵时，相加、相减和相乘所产生的结果矩阵另外生成。6. 运行环境： VC6.0+。2.2概要设计稀疏矩阵元素用三元组表示:typedefstruct/非零元的行下int i;标/非零元的列下int j;标int e;/矩阵非零元Triple;稀疏矩阵采用三元组顺序表存储:#define MSXSIZE 12500#define MAXRC 10typedef struct in t in t in t-mu ;nu ;tu»/个

6、数/ 非零元三元组data0表，/假设非零元个数的最大值 为/假定矩阵的最大行数为10矩阵的行数矩阵的列数 矩阵的非零元素Triple dataMAXSIZE+1; in trposMAXRC+1； bletype;系统主要函数及功能如下：Menu():主控菜单，接收用户的选项;Input_Matrix():输入Print_matrix(/各行'Ta):输出矩阵；:计算矩阵每行第Cal_matrix() 序号；Tran$poseMatrix()Add_Matrix()Sub_Matrix() Multi_Matrix()个非零元在三元组中的位 :矩阵转置；200模块的调用关系如图:矩阵

7、加法运算；:亜阵减法运算；矩阵乘法运算。1所示。mainMulti MatrixTransposeMatrixAdd Matrix第一个非零元素的位置表Sub_MatrixCal Matrix2.3详细设计1.主函数设计Input_MatrixPrint Matrix图1程序调用模块示意图图1程序调用模块示意图/*矩阵运算主函数主函数中， 实现用户菜单菜单的打印，并根据用户的选项执行相应的功能，主函数力求简洁、清晰。void main()num=Menu();/ 打印主菜单while(num)switch(num)case 1:Multi_Matrix(); / 矩阵相乘break;case

8、2:TransposeMatrix(); /矩阵转置break;case 3:Add_Matrix();/ 矩阵加法break;case 4:Sub_Matrix();/ 矩阵减法case 0:break;"/switchnum=Menu();/while2. 主菜单设计主控菜单是用来输出提示信息和处理输入，此函数返回用户的选项，提供给main函数中的switch语句。对于不符合要求的选项，提示输入错误并要求用户重新输入。将此函数与main函数合在一起，编译运行程序，即可检查并验证菜单选项是否正确。主菜单如下：/*/*打印主控菜单函数*/*int menu()printf("

9、;n主菜单");printf ("n*");printf("n 1.矩阵乘法"printf("n 2.矩阵转置"printf("n 3.矩阵加法"printf("n 4.矩阵减法"printf("n 0.退出");printf ("n*");););););scanf("%d",&num);while(num<0|num>4)/输入非法，重新输入scanf("%d",&num);

10、return num;3. 矩阵乘法运算函数*/*矩阵乘法运算算法*Status Multi_Matrix()输入矩阵a输入矩阵blnput_Matrix(&a); / lnput_Matrix(&b); /Cal_matrix(&a); Cal_matrix(&b); if (a.nu!=b.mu)/计算矩阵a每行第一个非零元的位序号/计算矩阵b每行第一个非零元的位序号/不符合矩阵乘法条件，不能相乘return ERROR;c.mu=a.mu;/对矩阵c初始化c.nu=b.nu;c.tu=0;if(a.tu*b.tu!=O)for(arow=1;arowv=a

11、.mu;arow+) /*处理矩阵a的每一行*/*/for (p=1;p< MAXRC+1;p+) /* 当前行各元素累加器清J I零ctempp=0;c.rposarow=c.tu+1;if(arow<a.mu )tp=a.rpos arow+1;elsetp=a.tu +1;for(p=a.rposarow; p<tp;p+) /求得 c 中第 crow 行的非零元 brow=a.datap.j;if(browvb.nu)t=b.rposbrow+1;elset=b.tu+1;for (q=b.rposbrow;q<t;q+)/*乘积元素在矩阵c中的列号*/ccol

12、=b.dataq.j;ctempccol+=a.datap.e*b.dataq.e; /*for q*/ /for pfor(ccol=1;ccolv=c.nu;cc ol+)/*压缩存储该行非零元 */if(ctempccol)if(c.tu)>MAXSIZE)exit(1);c.tu+;c.datac.tu.i=arow;c.datac.tu.j=ccol;c.datac.tu.e=ctempccol;/*end if*/*for arrow*/*if*/Print_matrix(a);Print_matrix(b);Print_matrix(c);4. 矩阵转置算法/*/*矩阵转置

13、算法*/*/输入矩阵avoid TransposeMatrix() lnput_Matrix(&a); b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu)/*b.data 的下标 */q=1;for(col=1;colv=a.nu;col+) 一列for(p=1;pv=a.tu;p+) /*pif( a.datap.j=col) 矩阵/对a的每的下标*/寻找col的非零元a中列为输入矩阵输入矩阵b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.e=a.datap.e;q+;/if(p)/if(b.tu)Print_

14、matrix(b); /输出a的转置矩阵 5矩阵加法算法/*/*矩阵加法运算函数/*c=a+b*Input_Matrix(&a); / aInput_Matrix(&b); /-bif(a.mu !=b.mu |a.nu !=b.nu )return ERROR;Status Add_Matrix()/不满足矩阵加法条件c.mu =a.mu ;c.nu =a.nu ;ta=1;tb=1;tc=1;if(a.tu *b.tu !=0)while(ta<=a.tu) && (tb<=b.tu)if(a.datata.i=b.datatb.i)if(a.d

15、atata.j=b.datatb.j) temp=a.datata.e+b.datatb.e;if(temp!=0)c.datatc.i=a.datata.i;c.datatc.j=a.datata.j;c.datatc.e=temp;tc+;/end if (temp)ta+;tb+;/end ifelseif(a.datata.j<b.datatb.j)c.datatc.i=a.datata.i;c.datatc.j=a.datata.j;c.datatc.e=a.datata.e; ta+;tc+;/end of else ifelsec.datatc.i=b.datatb.i;c

16、.datatc.j=b.datatb.j;c.datatc.e=b.datatb.e; tb+;tc+;/end ifelseif(a.datata.i<b.datatb.i)c.datatc.i=a.datata.i;c.datatc.j=a.datata.j;c.datatc.e=a.datata.e; tc+;ta+;elsec.datatc.i=b.datatb.i;'k'k'kc.datatc.j=b.datatb.j;c.datatc.e=b.datatb.e;tc+;tb+;/whilewhile(ta<=a.tu) /处理a中剩余非零元c.d

17、atatc.i=a.datata.i;c.datatc.j=a.datata.j;c.datatc.e=a.datata.e;tc+;ta+;while(tb<=b.tu) /处理b中剩余非零元c.datatc.i=b.datatb.i;c.datatc.j=b.datatb.j;c.datatc.e=b.datatb.e;tc+;tb+;/c.tu=tc;Print_matrix(c);6矩阵输入算法用于输入矩阵的行数、列数、非零元个数，以及每个非零元素。输入算法如下:/*/*矩阵输入算法* /*Status lnput_Matrix(Tabletype *t)scanf(t->

18、mu, t->nu, t->tu); /获得矩阵行列数、非零元个数for(i=1;iv=tu;i+)scanf(t->data i.i, t->data i.j,t->data i.e);return OK;7矩阵输出算法将三元组以矩阵方式输出在屏幕上，算法如下：/*/*矩阵输出函数*/*Status Print_matrix(Tabletype m)k=1;for(i=1;i<=m.mu;i+)for(j=1;jv=m.nu ;j+) /*非零元素*/if(m.datak.i=i)&&(m.datak.j=j) printf(m.datak.e); k+;elseprintf(“0”)； /* 零元素 */printf("n");8. Cal_matrix 函数算法如下:在矩阵乘法运算时，需要统计矩阵每行第一个非零元在三元组表中的位序号，void cal_matrix(Tabletype *m)/计算矩阵中每一行中第一个非零元的位序号for(row