数据结构课程设计教学大纲（051003）

学院： 计算机科学与技术学院 专业：计算机科学与技术

周数： 2周 学分：2

大纲主撰人：张先伟 编写日期：2004年6月30日

一、课程设计的目的和任务

1、提高对数据逻辑结构的特点以及存储表示方式的认识，培养在具体应用中选择合适的数据结构和存储结构的能力；

2、熟悉软件开发的基本过程，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等阶段的基本任务和技能方法；

3、培养学生的算法设计和算法分析能力，提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法、作风和相互合作的精神。

二、课程设计的主要内容与要求

1. 课程设计选题（一个题目为一个小组，人数不超过3人）

[1] 文章编辑

功能：输入一页文字，程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。

存储结构使用线性表，分别用几个子函数实现相应的功能；

输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；

[2] 通讯录的制作

设计目的：用〈〈数据结构〉〉中的双向链表作数据结构，结合C/C++语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。

设计内容：本系统应完成一下几方面的功能：

输入信息——enter();

显示信息———display( );

查找以姓名作为关键字 ———search( );

删除信息———delete( );

存盘———save ( );

装入———load( ) ;

设计要求：

1) 每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项

2) 作为一个完整的系统，应具有友好的界面和较强的容错能力

3) 上机能正常运行，并写出课程设计报告

[3]宿舍管理查询软件

任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：

采用交互工作方式

建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)

查询菜单: (用二分查找实现以下操作)

按姓名查询

按学号查询

房号查询

打印任一查询结果（可以连续操作）

[4]顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。

设有一元多项式Am(x)和Bn(x).

Am(x)=A0+A1x+A2x+A3x+? +Amx

Bn(x)=B0+B1x+B2x+B3x+? +Bnx

请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。

要求：

1) 首先判定多项式是否稀疏

2) 分别采用顺序和动态存储结构实现； 123n123m

3) 结果M(x)中无重复阶项和无零系数项；

4) 要求输出结果的升幂和降幂两种排列情况

[5] 二叉排序树的实现

用顺序和二叉链表作存储结构

1） 回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；

2） 对二叉排序树T作中序遍历，输出结果；

3） 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍

历(执行操作2)；否则输出信息“无x”；

[6]学生搭配问题

一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.

请设计一系统模拟动态地显示出上述过程,要求如下:

1) 输出每曲配对情况

2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.

3) 尽量设计出多种算法及程序,可视情况适当加分

提示:用队列来解决比较方便.

[7]敢死队问题

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。

[8]长整数四则运算

要求见严蔚敏习题集P80—1.4

[9]停车场管理

要求见严蔚敏习题集P96—2.1

[10]魔王语言解释

要求见严蔚敏习题集P97—2.2

[11]车厢调度

要求见严蔚敏习题集P97—2.3

[12]算术表达式求值演示

要求见严蔚敏习题集P99—2.5

[13]银行业务模拟

要求见严蔚敏习题集P100—2.6

[14]电梯模拟

要求见严蔚敏习题集P102—2.8

[15]重言式判别

要求见严蔚敏习题集P148—5.1

[16]哈夫曼编码译码器

要求见严蔚敏习题集P148—5.2

[17]图遍历的应用

要求见严蔚敏习题集P150—5.3

[18]全国交通咨询模拟

要求见严蔚敏习题集P151—5.8

[19]图书管理

要求见严蔚敏习题集P166—6.3

[20]平衡二叉树操作的演示

要求见严蔚敏习题集P166—6.4

2、课程设计调研

根据具体题目要求，由学生查阅指导教师提供的参考书目，以设计小组为单位进行需求分析，初步明确所选用的逻辑结构和存储结构。

3、课程设计方案制定

根据讨论，明确解决问题的基本算法，完成每个部分的算法设计说明（可以是描述算法的流程图）和每个程序中使用的存储结构设计说明。