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

数据结构课程设计

一、课程说明

课程编号：090166X11

课程名称：数据结构课程设计/CourseExerciseinDatastructure

课程类别：专业教育课程（集中实践环节）

学时/学分：2周/2学分

先修课程：高级语言程序设计、离散数学

适用专业：智能科学与技术

教材、教学参考书：

⑴《数据结构（C语言版）》，严蔚敏，吴伟民，清华大学出版社,2011

[2]《数据结构（C语言版）（第2版）》，严蔚敏等，人民邮电出版社，2015

二、课程设置的目的意义

本课程设计是为了配合《数据结构》课程而开设的，通过设计完整的大型程

序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成程序并

用上机调试的基本方法。课程的目的是使学生进一步理解和掌握课堂上所学各种

基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的

使用方法；使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化

软件设计的能力；使学生掌握使用各种计算机资料和有关参考资料，提高学生进

行程序设计的基本能力；

三、课程的基本要求

知识：了解各类常用数据结构，包括线性表、队列、栈、树、图等的构成与

特点；了解各类数据结构的创建、插入、删除、遍历、销毁等各种操作；了解各

类数据结构的应用，掌握经典算法的实现，如：模式匹配算法、算符优先法、快

速矩阵相乘算法、各类排序算法等。巩固和加深对数据结构基本知识的理解和掌

握。

能力：通过利用各种数据结构综合解决问题，加深对各类数据结构的逻辑结

构和物理结构的认识，初步体会和理解如何通过相应的结构和算法来解决问题，

培养根据具体问题来设计数据结构和算法的能力；学会将理论知识与实际应用结

合，学会根据提出的问题去分析问题和解决问题，提高综合运用课程知识的能力；

培养学生自学参考书籍，查阅手册、图表和文献资料的能力。

素质：通过实际课程设计，初步掌握简单软件的分析方法和设计方法，了解

与课程有关的工程技术规范，培养软件设计和系统设计素质。

四、实验方式与基本要求

1.学生可以在指导老师给出的课题中选择设计课题，也可以由学生自行提

出设计课题，经指导老师认可后确定设计课题。

2.根据题目的人数要求学生可自由分组，并确定组内成员的分工，进行课程

设计课题的资料搜集。所有学生根据所选课题学会找参考书籍、查阅手册、图表

和文献资料等。通过独立思考，深入钻研有关问题，学会自己分析解决问题的方

法。

3.根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、

并在此基础上进行实现程序功能的算法设计。

4.运用掌握C/C++语言编写程序，实现各个模块功能，进行程序设计，并调

试程序，记录测试情况。

5.每组成员根据自己的工作各自完成课程设计报告。

6.指导教师对每组同学的开发的系统进行综合验收，并由学院考核小组进行

随机抽查评分。

五、课程的基本内容以及重点难点

本课程基本内容为：利用各种数据结构解决实际问题。

重点：数据结构设计、系统设计与调试、性能与功能测试。

难点：系统设计及调试。

六、实验项目的设置与内容提要

验

每组

实验项实验实实验实验

型

人数

类内容摘要

目名称时数要求类别

问题描述：设计一个学生作业管理系

统，实现对学生作业提交情况的检查、

查询、文件名的规范等操作。

系统运行要求：

（1）”学生信息表'’已经存在，初始为

教师的教务管理系统中导出的点名

装,是Excel表格,具林表格■见附作一。

（2）学生提交的作业文档已存在，并

保存在同一目录下，作业文件名由学

号+姓名组成。

系统基本要求：程序采用图形界面下

学生作不超技术进行交互的工作方式，完成如下功能：

综合

础

01业管理2周过5选做基（1）规范学生作业文件名

设计

系统人（2）多种方式建立学生作业信息

（3）检查浏览学生作业提交情况及作

业文档

（4）按照学号对所有学生信息进行升

序、降序排列，并输出

（5）按姓名、学号等方式，实现对学

生作业信息的精确查询、模糊查询，

输出屏幕显示，并能调用word等编辑

器打开选中学生的作业文档

（6）学生作业信息的插入、删除、修

改。

（7）数据的统计功能

问题描述：设计一个哈希表，实现个

个电

人人电话号码查询系统。

话

码

号

不超综合

技术

杳基本要求：

系

设计

02询2周过3选做

基础设每个记录有下列数据项：电话号码、

统人

用户名、用户住址；

从键盘露入各记录'，分别以电话号码

实验

实验项实验每组实验实验

人

要求

数内容摘要

目名称时数类型类别

和用户名为关键字建立哈希表；

可根据用户选择使用不同的哈希函

数，并输出各自的冲突率；

b）在哈希函数确定的前提下，可提供

各种不同类型处理冲突的方法供选

择，并统计对应方法的平均查找长度；

C）能统计不同哈希函数的冲突率，及

不同冲突处理策略的平均查找长度，

列表显示各种不同方法的比较结果；

查找并显示给定电话号码/用户名的记

录；

问题描述：设计一个管理个人通讯录

的程序，完成下列基本功能。

录入和备份通讯录

通讯录管理

通讯录信息浏览

技术

实用的不超综合

通讯录信息添加

础

基

03小型通2周过3设计选做

通讯录信息删除

讯录人

通讯录信息查询：按照姓名、电话号

码等字段，进行精确、模糊查询，并

在屏幕上输出查询结果。

通讯录信息修改

f）通讯录类别管理

问题描述：用一个字符类型的二维数

组表示迷宫，数组中的每个元素表示

一个小方格，取值“0”（通道）或“1”

（阻塞物）。设计一个模拟小老鼠走迷

宫的程序，为小老鼠寻找一条从迷宫

入口到迷宫出口的途经小方格最少的

综合最短通路。

迷宫问技术

042周1设计选做基本要求：

基础

题用随机函数设置迷宫；

选择合适的数据结构表示迷宫。

迷宫入口和出口由键盘或鼠标输入。

输出从入口到出口的最短通路（如存

在）或不存在通路的信息。

设计出友好的图形化界面，做到很好

的人机交互。

问题描述：设计一个动画演示系统动

态演示栈和队列的各种操作，帮助理

解这两种数据结构中的插入、删除、

向上溢出和向下溢出等概念。特别是

关于两个栈共用一块存储空间和循环

队列的情况。

基本要求：

对单个栈，从键盘或文件中输入入栈

栈与队数据个数和数据序列，动态演示数据

的入栈和出栈过程，包括栈顶指针的

列结构不超综合

技术变化，栈内数据的变化，溢出的情况

05的操作2周过4设计选做

基础的演示等，并显示文字说明对该过程

动画演人

进行讲解；

示系统对两个栈共用空间的情况，从键盘或

文件中输入入栈数据个数和数据序

歹U，动态演示数据的入栈过程，包括

栈顶指针的变化，栈内数据的变化，

溢出的情况的演示等，并显示文字说

明对该过程进行讲解；

对一般队列，从键盘或文件中输入入

队数据个数和数据序列，动态演示入

队和出队过程，包括队头、队尾指针

实验

实验项实验每组实验实验

人

要求

数内容摘要

目名称时数类型类别

值的变化，队内数据的变化，溢出的

情况的演示等，并显示文字说明对该

过程进行讲解；

对循环队列，从键盘或文件中输入入

队数据个数和数据序列，动态演示入

队和出队过程，包括队头、队尾指针

值的变化，队内数据的变化，特别是

队列已满情况的判定条件演示等，并

显示文字说明对该过程进行讲解；

问题描述：哈夫曼编码在通讯、网络、

数据压缩、图像处理中的得到广泛应

用，在一个通讯系统中，采用图形界

面设计m叉哈夫曼树（m^2）,对■通讯褚

息进行编码和解码。

基本要求：

从终端读入字符文件，统计文件中字

符的出现频率作为每个字符的权值，

哈夫曼建立叉哈夫曼树，并将哈夫曼树以

不超m

树编码/综合技术直观的方式（如树形）显示在终端上，

062周过3选做

译码系设计基础同时将字符及其对应的编码写入文件

人

统CodePrint中；

利用编码结果，对文件中的正文进行

编码，然后将结果存入文件CodeFile

中,并输出结果,将文件CodeFile以

紧凑格式显示在终端上，每行50个代

码。

将土件CodeFile中的代码进行译码，

结果存入文件TextFile中，并输出结

果。

问题描述：设计一个校园导游程序，

完成校园信息的维护以及为来访的客

人提供信息查询等服务功能。

基本要求：

根据新校区的校园平面图设计带权无

向网络，所含景点不少于10个，以图

中顶点表示校内各景点，顶点的信息

包括：景点名称、代号、简介等，以

边表示道路，边上信息包括：两点距

不超技术

校园导综合离、所需时间等相关信息。（注：数据

础

072周过2选做基

游系统设计的输入可以是键盘输入或文件输入两

人

种方式）建立相应的图结构。

提供对校园景点信息的编辑（如：添

力口、删除、修改等）的功能；为来访

客人提供图中任意景点相关信息的查

询（可提供多种查询方式）；

为来访客人提供从校门口到图中任意

景点的问路查询（最短路径）；

为来访客人提供图中任意景点间的问

路查询。

问题描述：已知一个无向连通网表示n

个城市以及城市间可能设置的通信线

路，其中网的顶点表示城市，边表示

最小生不超综合两个城市之间的线路，赋于边上的权

技术

成树问周过设计选做值表示相应的代价。对于个点的连

0822基础n

题人通网可以建立许多不同的生成树，每

一棵生成树都可以是一个通信网。现

在，我们要选择这样一棵生成树，使

总的耗费最小。即构造连通网的最小

一每组实验实验实验

序

实验

实验项人数类型要求类别

要

摘

容

号内

时数

称

目名

。

问题

树的

生成

：

要求

基本

。

结构

存储

网的

交通

城市

建立

（1）

文

入或

盘输

是键

可以

输入

数据

（注：

式）

种方

入两

件输

l算法

uska

和Kr

算法

Prim

别用

（2）分

成树

小生

出最

并输

树，

生成

最小

构造