2024年5月26日发(作者：)

中国石油大学(北京)远程教育学院

期 末 考 试

《数据结构》课程设计

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

#define MAXRC 10

typedef struct

{

int mu ;

int nu ;

int tu ;

//假设非零元个数的最大值为 200

//假定矩阵的最大行数为 10

//矩阵的行数

//矩阵的列数

//矩阵的非零元素个数

//非零元三元组表， data[0]没实用

//各行第一个非零元素的位置表

Triple data[MAXSIZE+1];

int rpos[MAXRC+1];

}Tabletype;

系统主要函数及功能如下：

Menu( )：主控菜单，接收用户的选项；

Input_Matrix( )：输入矩阵；

Print_matrix( )：输出矩阵；

Cal_matrix( )：计算矩阵每行第一个非零元在三元组中的位序号；

TransposeMatrix( )：矩阵转置；

Add_Matrix( )：矩阵加法运算；

Sub_Matrix( )：矩阵减法运算；

Multi_Matrix( ) ：矩阵乘法运算。

模块的调用关系如图 1 所示。

main

Multi_Matrix

TransposeMatrix Add_Matrix

Sub_Matrix

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);

if ( !=)

return ERROR;

//计算矩阵 b 每行第一个非零元的位序号

//不符合矩阵乘法条件，不能相乘

=; //对矩阵 c 初始化

=;

=0;

if(*!=0){

for(arow=1;arow<=;arow++){ /*处理矩阵 a 的每一行*/

for (p=1;p< MAXRC+1;p++) /*当前行各元素累加器清零*/

ctemp[p]=0;

[arow]=+1;

if(arow< )

tp= [arow+1];

else

tp= +1;

for(p=[arow]; p

brow=[p].j;

if(brow<)

t=[brow+1];

else

t=+1;

for (q=[brow];q

ccol=[q].j; /*乘积元素在矩阵 c 中的列号*/

ctemp[ccol]+=[p].e*[q].e;

} /*for q*/

}//for p

for(ccol=1;ccol<=;ccol++)

if(ctemp[ccol]) /*压缩存储该行非零元*/

{

if(()>MAXSIZE)