奥鹏数据结构实验报告
《数据结构》课程设计
1.课程设计题目
从下面四个题目中任选一题完成。
通讯录的制作
用单链表作为数据结构,结合C或者C++语言基本知识,编写一个班级的通讯录管理系统。系统包括下面几方面的功能:
第1:输入信息:输入某同学的信息;
第2:显示信息:显示全部通讯录中学生的信息;
第3:查找功能:实现按姓名进行查找,并给出查找信息;
第4:删除功能:实现按姓名进行删除,并给出操作结果;
第5:每名同学的信息包括:姓名、性别、电话、城市;
第6:界面友好,每步给出适当的操作提示;
第7:系统具有一定的容错能力。
图书管理系统
设计一个计算机管理系统完成图书管理几本业务。系统要满足下面基本要求:
第1:每种图书的登记内容包括:书名、书号、作者、出版社、现存量和库存量;
第2:采编入库:新购图书,确定书号后,登记到图书账目表中,如果表中存在该书,则只将库存量增加;
第3:借阅:如果该书的库存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变库存量;
第4:归还:注销对借阅者的登记,改变该书的库存量;
第5:界面友好,每步给出适当的操作提示;
第6:系统具有一定的容错能力。
产品进销管理系统
针对某个行业的库房产品进销存情况进行管理,系统要求具有下列功能:
第1:采用一定的存储结构对库房的货品及其数量进行分类管理;
第2:可以进行产品类的添加、产品的添加、产品数量的添加;
第3:能够查询库房每种产品的总量、进货日期、销出数量、销售时间等;
第4:每种产品至少包含信息:产品名、进货日期、进货数量、销出数量、销售时间、库存量;
第5:界面友好,每步给出适当的操作提示;
第6:系统具有一定的容错能力。
校园导航问题
设计中国石油大学(北京)的校园平面图,至少包括10
个场所,可以实现任意两个场所的最短路径。
2.课程设计报告书写规范
课程设计报告包括该题目的需求分析、概要设计、详细设计、程序测试、感想与体会几部分内容。下面以“稀疏矩阵运算器”为例说明如何写课程设计报告。
题目要求:设计一个稀疏矩阵计算器,实现两个稀疏矩阵的加法、减法、乘法以及矩阵的转置运算。采用菜单为应用程序的界面,用户通过对菜单进行选择,分别实现矩阵的相加、相减、相乘以及矩阵转速运算。
需求分析
1. 稀疏矩阵是指稀疏因子小于等于的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
2. 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现矩阵转置,以及两个矩阵的加、减、乘的运算。稀疏矩阵的输入形式采用三元组表示,运算结果以阵列形式列出。
3. 演示程序以用户和计算机的对话方式进行,数组的建立方式为边输入边建立。首先输入矩阵的行数和列数,并判别给出的两个矩阵的行列数是否与所要求的运算相匹配。
4. 程序可以对三元组的输入属性不加以限制;根据对矩阵的行列,三元组作之间插入排序,从而进行运算时,不
会产生错误。
5. 在用三元组表示稀疏矩阵时,相加、相减和相乘所产生的结果矩阵另外生成。
6. 运行环境:++。
概要设计
稀疏矩阵元素用三元组表示:
typedef struct{
int i; //非零元的行下标
int j; //非零元的列下标
int e; //矩阵非零元
}Triple;
稀疏矩阵采用三元组顺序表存储:
#define MSXSIZE 12500 //假设非零元个数的最大值为200
#define MAXRC 10 //假定矩阵的最大行数为10
typedef struct
{
int mu ; //矩阵的行数
int nu ; //矩阵的列数
int tu ; //矩阵的非零元素个数
Triple data; //非零元三元组表,data没有用
int rpos; //各行第一个非零元素的位置表
}Tabletype;
系统主要函数及功能如下:
Menu( ):主控菜单,接收用户的选项;
Input_Matrix( ):输入矩阵;
Print_matrix( ):输出矩阵;
Cal_matrix( ):计算矩阵每行第一个非零元在三元组中的位序号;
TransposeMatrix( ):矩阵转置;
Add_Matrix( ):矩阵加法运算;
Sub_Matrix( ):矩阵减法运算;
Multi_Matrix( ):矩阵乘法运算。
模块的调用关系如图1所示。
图1 程序调用模块示意图
详细设计
1. 主函数设计
/
for (p=1;p ctemp=0;
=+1;
if(arow
tp= ;
else
tp= +1;
for(p=; p
brow=.j;
if(brow
t=;
else
t=+1;
for (q=;q
ccol=.j;
ctemp+=.e*.e;
}
}//for p
for(ccol=1;ccol
{
if(()>MAXSIZE)
exit(1);
++;
.i=arow;
.j=ccol;
.e=ctemp;
}
}
}
if(ctemp) Print_matrix(a);
Print_matrix(b);
Print_matrix(c);
}
4. 矩阵转置算法
/
for(col=1;col for(p=1;p if( .j==col){ //寻找矩阵a中列为col的非零元
.i=.j;
.j=.i;
.e=.e;
q++;
}//if(p)
}//if()
Print_matrix(b); //输出a的转置矩阵
}
5. 矩阵加法算法
/
if((.i==i)&&(.j==j)){
printf(.e);
k++;
}
else
printf(“0”);
}
printf(" ");
}
}
8. Cal_matrix函数
在矩阵乘法运算时,需要统计矩阵每行第一个非零元在三元组表中的位序号,算法如下:
void cal_matrix(Tabletype *m){
//计算矩阵中每一行中第一个非零元的位序号
for(row=1;rowmu ;row++)
num=0;
for(t=1;ttu ;t++)
num.i]++;
m->rpos =1;
for(row=2;rowmu ;row++)
m->rpos =m->rpos +num;
}
程序测试
在这部分给出程序运行结果的屏幕截图,以及测试分析。
感想与体会
这部分给出算法设计过程中的问题、程序调试过程的问题与收获。
3.要求
源程序没有语法错误,运行结果正确;
设计报告按照规范书写。
课程设计最后提交内容包括:源程序与课程设计报告。