石大远程在线考试数据结构专业课程设计.doc

中国石油大学（北京）远程教育学院
期 末 考 试
《数据结构》课程设计
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概要设计
稀疏矩阵元素用三元组表示：
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[MAXSIZE+1]; //非零元三元组表，data[0]没有用
int rpos[MAXRC+1]; //各行第一个非零元素位置表
}Tabletype;
系统关键函数及功效以下：
Menu( )：主控菜单，接收用户选项；
Input_Matrix( )：输入矩阵；
Print_matrix( )：输出矩阵；
Cal_matrix( )：计算矩阵每行第一个非零元在三元组中位序号；
TransposeMatrix( )：矩阵转置；
Add_Matrix( )：矩阵加法运算；
Sub_Matrix( )：矩阵减法运算；
Multi_Matrix( )：矩阵乘法运算。
模块调用关系图1所表示。
Multi_Matrix
main
Add_Matrix

Sub_Matrix

TransposeMatrix
Cal_Matrix
Input_Matrix
Print_Matrix

图1 程序调用模块示意图

2.3具体设计
1. 主函数设计

//*****************************************
//* 矩阵运算主函数 *
//*****************************************
主函数中，实现用户菜单菜单打印，并依据用户选项实施对应功效，主函数努力争取简练、清楚。
void main( )
{
num=Menu(); //打印主菜单
while(num)
{
switch(num)
{
case 1:
Multi_Matrix(); //矩阵相乘
break;
case 2:
TransposeMatrix(); //矩阵转置
break;
case 3:
Add_Matrix(); //矩阵加法
break;
case 4:
Sub_Matrix(); //矩阵减法
case 0:
break;
}//switch
num=Menu();
}//while
}
2. 主菜单设计
主控菜单是用来输出提醒信息和处理输入，此函数返回用户选项，提供给main函数中switch语句。对于不符合要求选项，提醒输入错误并要求用户重新输入。将此函数和main函数合在一起，编译运行程序，即可检验并验证菜单选项是否正确。
主菜单以下：
//*****************************************
//* 打印主控菜单函数 *
//*****************************************
int menu( )
{
printf("\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);
return num;
}
3. 矩阵乘法运算函数
//*****************************************
//* 矩阵乘法运算算法 *
//*****************************************

Status Multi_Matrix()
{
Input_Matrix(&a); //输入矩阵a
Input_Matrix(&b); //输入矩阵b
Cal_matrix(&a); //计算矩阵a每行第一个非零元位序号
Cal_matrix(&b); //计算矩阵b每行第一个非零元位序号
if (a.nu!=b.mu) //不符合矩阵乘法条件，不能相乘
return ERROR;
c.mu=a.mu; //对矩阵c初始化
c.nu=b.nu;
c.tu=0;
if(a.tu*b.tu!=0){
for(arow=1;arow<=a.mu;arow++){ /*处理矩阵a每一行*/
for (p=1;p< MAXRC+1;p++) /*目前行各元素累加器清零*/
ctemp[p]=0;
c.rpos[arow]=c.tu+1;
if(arow<a.mu )
tp=a.rpos [arow+1];
else
tp=a.tu +1;
for(p=a.rpos[arow]; p<tp;p++){ //求得c中第crow行非零元
brow=a.data[p].j;
if(brow<b.nu)
t=b.rpos[brow+1];
else
t=b.tu+1;
for (q=b.rpos[brow];q<t;q++){
ccol=b.data[q].j; /*乘积元素在矩阵c中列号*/
ctemp[ccol]+=a.data[p].e*b.data[q].e;
} /*for q*/
}//for p
for(ccol=1;ccol<=c.nu;ccol++)
if(ctemp[ccol]) /*压缩存放该行非零元*/
{
if((c.tu)>MAXSIZE)
exit(1);
c.tu++;
c.data[c.tu].i=arow;
c.data[c.tu].j=ccol;
c.data[c.tu].e=ctemp[ccol];
}/*end if*/
}/*for arrow*/
}/*if*/
Print_matrix(a);
Print_matrix(b);
Print_matrix(c);
}
4. 矩阵转置算法
//*****************************************
//* 矩阵转置算法 *
//*****************************************
void TransposeMatrix(){
Input_Matrix(&a); //输入矩阵a
b.mu=a.nu;
b.nu=a.mu;
b.tu=a.tu;
if(b.tu){
q=1; /*b.data下标*/
for(col=1;col<=a.nu;col++) //对a每一列
for(p=1;p<=a.tu;p++) /*p为a下标*/
if( a.data[p].j==col){ //寻求矩阵a中列为col非零元
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].e=a.data[p].e;
q++;
}//if(p)
}//if(b.tu)
Print_matrix(b); //输出a转置矩阵
}
5. 矩阵加法算法
//*****************************************
//* 矩阵加法运算函数 *
//* c=a+b *
//*****************************************
Status Add_Matrix(){
Input_Matrix(&a); //输入矩阵a
Input_Matrix(&b); //输入矩阵b
if(a.mu !=b.mu ||a.nu !=b.nu ) //不满足矩阵加法条件
return ERROR;
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.data[ta].i==b.data[tb].i){
if(a.data[ta].j==b.data[tb].j){
temp=a.data[ta].e+b.data[tb].e;
if(temp!=0){
c.data[tc].i=a.data[ta].i;
c.data[tc].j=a.data[ta].j;
c.data[tc].e=temp;
tc++;
}//end if (temp)
ta++; tb++;
}//end if
else{
if(a.data[ta].j<b.data[tb].j){
c.data[tc].i=a.data[ta].i;
c.data[tc].j=a.data[ta].j;
c.data[tc].e=a.data[ta].e;
ta++; tc++;
}//end of else if
else{
c.data[tc].i=b.data[tb].i;
c.data[tc].j=b.data[tb].j;
c.data[tc].e=b.data[tb].e;
tb++; tc++;
}//
}
}//end if
else{
if(a.data[ta].i<b.data[tb].i){
c.data[tc].i=a.data[ta].i;
c.data[tc].j=a.data[ta].j;
c.data[tc].e=a.data[ta].e;
tc++; ta++;
}
else{
c.data[tc].i=b.data[tb].i;
c.data[tc].j=b.data[tb].j;
c.data[tc].e=b.data[tb].e;
tc++; tb++;
}
}
}//while
while(ta<=a.tu){ //处理a中剩下非零元
c.data[tc].i=a.data[ta].i;
c.data[tc].j=a.data[ta].j;
c.data[tc].e=a.data[ta].e;
tc++; ta++;
}
while(tb<=b.tu){ //处理b中剩下非零元
c.data[tc].i=b.data[tb].i;
c.data[tc].j=b.data[tb].j;
c.data[tc].e=b.data[tb].e;
tc++; tb++;
}
}//
c.tu=tc;
Print_matrix(c);
}
6. 矩阵输入算法
用于输入矩阵行数、列数、非零元个数，和每个非零元素。输入算法以下：
//*****************************************
//* 矩阵输入算法 *
//*****************************************
Status Input_Matrix(Tabletype *t)
{
scanf(t->mu, t->nu, t->tu); //取得矩阵行列数、非零元个数
for(i=1;i<=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;j<=m.nu ;j++) {/*非零元素*/
if((m.data[k].i==i)&&(m.data[k].j==j)){
printf(m.data[k].e);
k++;
}
else
printf(“0”); /*零元素*/
}
printf("\n");
}
}
8. Cal_matrix函数
在矩阵乘法运算时，需要统计矩阵每行第一个非零元在三元组表中位序号，算法以下：
void cal_matrix(Tabletype *m){
//计算矩阵中每一行中第一个非零元位序号
for(row=1;row<=m->mu ;row++)
num[row]=0;
for(t=1;t<=m->tu ;t++)
num[m->data [t].i]++;
m->rpos [1]=1;
for(row=2;row<=m->mu ;row++)
m->rpos [row]=m->rpos [row-1]+num[row-1];
}
2.4程序测试
在这部分给出程序运行结果屏幕截图，和测试分析。
2.5感想和体会
这部分给出算法设计过程中问题、程序调试过程问题和收获。
3.要求
源程序没有语法错误，运行结果正确；
设计汇报根据规范书写。
课程设计最终提交内容包含：源程序和课程设计汇报。