首页 › 中国石油大学北京网院（石大远程） › 石大远程17春《数据结构课程设计》在线答案

homework 发表于 2017-4-12 13:28:05

石大远程17春《数据结构课程设计》在线答案

17春中石油北京《数据结构课程设计》在线考试答案
作业内容
中国石油大学（北京）远程教育学院
期末考试
《数据结构》课程设计
1.课程设计题目
从下面四个题目中任选一题完成。
1.1通讯录的制作
用单链表作为数据结构，结合C或者C++语言基本知识，编写一个班级的通讯录管理系统。系统包括下面几方面的功能：
第1：输入信息：输入某同学的信息；
第2：显示信息：显示全部通讯录中学生的信息；
第3：查找功能：实现按姓名进行查找，并给出查找信息；
第4：删除功能：实现按姓名进行删除，并给出操作结果；
第5：每名同学的信息包括：姓名、性别、电话、城市；
第6：界面友好，每步给出适当的操作提示；
第7：系统具有一定的容错能力。
1.2图书管理系统
设计一个计算机管理系统完成图书管理几本业务。系统要满足下面基本要求：
第1：每种图书的登记内容包括：书名、书号、作者、出版社、现存量和库存量；
第2：采编入库：新购图书，确定书号后，登记到图书账目表中，如果表中存在该书，则只将库存量增加；
第3：借阅：如果该书的库存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变库存量；
第4：归还：注销对借阅者的登记，改变该书的库存量；
第5：界面友好，每步给出适当的操作提示；
第6：系统具有一定的容错能力。
1.3产品进销管理系统
针对某个行业的库房产品进销存情况进行管理，系统要求具有下列功能：
第1：采用一定的存储结构对库房的货品及其数量进行分类管理；
第2：可以进行产品类的添加、产品的添加、产品数量的添加；
第3：能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；
第4：每种产品至少包含信息：产品名、进货日期、进货数量、销出数量、销售时间、库存量；
第5：界面友好，每步给出适当的操作提示；
第6：系统具有一定的容错能力。
1.4校园导航问题
设计中国石油大学（北京）的校园平面图，至少包括10个场所，可以实现任意两个场所的最短路径。

2.课程设计报告书写规范
课程设计报告包括该题目的需求分析、概要设计、详细设计、程序测试、感想与体会几部分内容。下面以“稀疏矩阵运算器”为例说明如何写课程设计报告。

题目要求：设计一个稀疏矩阵计算器，实现两个稀疏矩阵的加法、减法、乘法以及矩阵的转置运算。采用菜单为应用程序的界面，用户通过对菜单进行选择，分别实现矩阵的相加、相减、相乘以及矩阵转速运算。
2.1需求分析
1.稀疏矩阵是指稀疏因子小于等于0.5的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
2.以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，以及两个矩阵的加、减、乘的运算。稀疏矩阵的输入形式采用三元组表示，运算结果以阵列形式列出。
3.演示程序以用户和计算机的对话方式进行，数组的建立方式为边输入边建立。首先输入矩阵的行数和列数，并判别给出的两个矩阵的行列数是否与所要求的运算相匹配。
4.程序可以对三元组的输入属性不加以限制；根据对矩阵的行列，三元组作之间插入排序，从而进行运算时，不会产生错误。
5.在用三元组表示稀疏矩阵时，相加、相减和相乘所产生的结果矩阵另外生成。
6.运行环境：VC6.0++。
2.2概要设计
稀疏矩阵元素用三元组表示：
typedefstruct{
inti//非零元的行下标
intj//非零元的列下标
inte//矩阵非零元
}Triple
稀疏矩阵采用三元组顺序表存储：
#defineMSXSIZE12500//假设非零元个数的最大值为200
#defineMAXRC10//假定矩阵的最大行数为10
typedefstruct
{
intmu//矩阵的行数
intnu//矩阵的列数
inttu//矩阵的非零元素个数
Tripledata//非零元三元组表，data没有用
intrpos//各行第一个非零元素的位置表
}Tabletype
系统主要函数及功能如下：
Menu()：主控菜单，接收用户的选项；
Input_Matrix()：输入矩阵；
Print_matrix()：输出矩阵；
Cal_matrix()：计算矩阵每行第一个非零元在三元组中的位序号；
TransposeMatrix()：矩阵转置；
Add_Matrix()：矩阵加法运算；
Sub_Matrix()：矩阵减法运算；
Multi_Matrix()：矩阵乘法运算。
模块的调用关系如图1所示。

图1程序调用模块示意图

2.3详细设计
1.主函数设计

//*****************************************
//*矩阵运算主函数*
//*****************************************
主函数中，实现用户菜单菜单的打印，并根据用户的选项执行相应的功能，主函数力求简洁、清晰。
voidmain()
{
num=Menu()//打印主菜单
while(num)
{
switch(num)
{
case1
Multi_Matrix()//矩阵相乘
break
case2
TransposeMatrix()//矩阵转置
break
case3
Add_Matrix()//矩阵加法
break
case4
Sub_Matrix()//矩阵减法
case0
break
}//switch
num=Menu()
}//while
}
2.主菜单设计
主控菜单是用来输出提示信息和处理输入，此函数返回用户的选项，提供给main函数中的switch语句。对于不符合要求的选项，提示输入错误并要求用户重新输入。将此函数与main函数合在一起，编译运行程序，即可检查并验证菜单选项是否正确。
主菜单如下：
//*****************************************
//*打印主控菜单函数*
//*****************************************
intmenu()
{
printf(&quot\n主菜单&quot)
printf(&quot\n*********************&quot)
printf(&quot\n1.矩阵乘法&quot)
printf(&quot\n2.矩阵转置&quot)
printf(&quot\n3.矩阵加法&quot)
printf(&quot\n4.矩阵减法&quot)
printf(&quot\n0.退出&quot)
printf(&quot\n*********************&quot)
scanf(&quot%d&quot,&ampnum)
while(num&lt0||num&gt4)//输入非法，重新输入
scanf(&quot%d&quot,&ampnum)
returnnum
}
3.矩阵乘法运算函数
//*****************************************
//*矩阵乘法运算算法*
//*****************************************

StatusMulti_Matrix()
{
Input_Matrix(&ampa)//输入矩阵a
Input_Matrix(&ampb)//输入矩阵b
Cal_matrix(&ampa)//计算矩阵a每行第一个非零元的位序号
Cal_matrix(&ampb)//计算矩阵b每行第一个非零元的位序号
if(a.nu!=b.mu)//不符合矩阵乘法条件，不能相乘
returnERROR
c.mu=a.mu//对矩阵c初始化
c.nu=b.nu
c.tu=0
if(a.tu*b.tu!=0){
for(arow=1arow&lt=a.muarow++){/*处理矩阵a的每一行*/
for(p=1p&ltMAXRC+1p++)/*当前行各元素累加器清零*/
ctemp=0
c.rpos=c.tu+1
if(arow&lta.mu)
tp=a.rpos
else
tp=a.tu+1
for(p=a.rposp&lttpp++){//求得c中第crow行的非零元
brow=a.data.j
if(brow&ltb.nu)
t=b.rpos
else
t=b.tu+1
for(q=b.rposq&lttq++){
ccol=b.data.j/*乘积元素在矩阵c中的列号*/
ctemp+=a.data.e*b.data.e
}/*forq*/
}//forp
for(ccol=1ccol&lt=c.nuccol++)
if(ctemp)/*压缩存储该行非零元*/
{
if((c.tu)&gtMAXSIZE)
exit(1)
c.tu++
c.data.i=arow
c.data.j=ccol
c.data.e=ctemp
}/*endif*/
}/*forarrow*/
}/*if*/
Print_matrix(a)
Print_matrix(b)
Print_matrix(c)
}
4.矩阵转置算法
//*****************************************
//*矩阵转置算法*
//*****************************************
voidTransposeMatrix(){
Input_Matrix(&ampa)//输入矩阵a
b.mu=a.nu
b.nu=a.mu
b.tu=a.tu
if(b.tu){
q=1/*b.data的下标*/
for(col=1col&lt=a.nucol++)//对a的每一列
for(p=1p&lt=a.tup++)/*p为a的下标*/
if(a.data.j==col){//寻找矩阵a中列为col的非零元
b.data.i=a.data.j
b.data.j=a.data.i
b.data.e=a.data.e
q++
}//if(p)
}//if(b.tu)
Print_matrix(b)//输出a的转置矩阵
}
5.矩阵加法算法
//*****************************************
//*矩阵加法运算函数*
//*c=a+b*
//*****************************************
StatusAdd_Matrix(){
Input_Matrix(&ampa)//输入矩阵a
Input_Matrix(&ampb)//输入矩阵b
if(a.mu!=b.mu||a.nu!=b.nu)//不满足矩阵加法条件
returnERROR
c.mu=a.mu
c.nu=a.nu
ta=1tb=1tc=1
if(a.tu*b.tu!=0){
while((ta&lt=a.tu)&amp&amp(tb&lt=b.tu)){
if(a.data.i==b.data.i){
if(a.data.j==b.data.j){
temp=a.data.e+b.data.e
if(temp!=0){
c.data.i=a.data.i
c.data.j=a.data.j
c.data.e=temp
tc++
}//endif(temp)
ta++tb++
}//endif
else{
if(a.data.j&ltb.data.j){
c.data.i=a.data.i
c.data.j=a.data.j
c.data.e=a.data.e
ta++tc++
}//endofelseif
else{
c.data.i=b.data.i
c.data.j=b.data.j
c.data.e=b.data.e
tb++tc++
}//
}
}//endif
else{
if(a.data.i&ltb.data.i){
c.data.i=a.data.i
c.data.j=a.data.j
c.data.e=a.data.e
tc++ta++
}
else{
c.data.i=b.data.i
c.data.j=b.data.j
c.data.e=b.data.e
tc++tb++
}
}
}//while
while(ta&lt=a.tu){//处理a中剩余非零元
c.data.i=a.data.i
c.data.j=a.data.j
c.data.e=a.data.e
tc++ta++
}
while(tb&lt=b.tu){//处理b中剩余非零元
c.data.i=b.data.i
c.data.j=b.data.j
c.data.e=b.data.e
tc++tb++
}
}//
c.tu=tc
Print_matrix(c)
}
6.矩阵输入算法
用于输入矩阵的行数、列数、非零元个数，以及每个非零元素。输入算法如下：
//*****************************************
//*矩阵输入算法*
//*****************************************
StatusInput_Matrix(Tabletype*t)
{
scanf(t&gtmu,t&gtnu,t&gttu)//获得矩阵行列数、非零元个数
for(i=1i&lt=tui++)
scanf(t&gtdata.i,t&gtdata.j,t&gtdata.e)
returnOK
}
7.矩阵输出算法
将三元组以矩阵方式输出在屏幕上，算法如下：
//*****************************************
//*矩阵输出函数*
//*****************************************
StatusPrint_matrix(Tabletypem){
k=1
for(i=1i&lt=m.mui++){
for(j=1j&lt=m.nuj++){/*非零元素*/
if((m.data.i==i)&amp&amp(m.data.j==j)){
printf(m.data.e)
k++
}
else
printf(“0”)/*零元素*/
}
printf(&quot\n&quot)
}
}
8.Cal_matrix函数
在矩阵乘法运算时，需要统计矩阵每行第一个非零元在三元组表中的位序号，算法如下：
voidcal_matrix(Tabletype*m){
//计算矩阵中每一行中第一个非零元的位序号
for(row=1row&lt=m&gtmurow++)
num=0
for(t=1t&lt=m&gttut++)
num.i]++
m&gtrpos=1
for(row=2row&lt=m&gtmurow++)
m&gtrpos=m&gtrpos+num
}
2.4程序测试
在这部分给出程序运行结果的屏幕截图，以及测试分析。
2.5感想与体会
这部分给出算法设计过程中的问题、程序调试过程的问题与收获。
3.要求
源程序没有语法错误，运行结果正确；
设计报告按照规范书写。
课程设计最后提交内容包括：源程序与课程设计报告。

huangbin123456 发表于 2017-4-25 19:45:06

你好                        赞

查看完整版本: 石大远程17春《数据结构课程设计》在线答案