数据结构课程设计

第1章 数据结构课程设计概述

1.1 数据结构简介

1.2 课程设计目标和特点

1.3 编写说明

1.4 课程设计实例的标准格式

第2章 线性表的应用

2.1 存储结构与基本运算的算法

2.2 集合的交、并运算

2.3 学生成绩管理

2.4 多项式求导

2.5 约瑟夫环问题

2.6 数据库管理系统

第3章 栈的应用

3.1 存储结构与基本运算的算法

3.2 括号匹配

3.3 汉诺塔问题

3.4 算术表达式求值

3.5 马踏棋盘

第4章 队列的应用

4.1 存储结构与基本运算的算法

4.2 看病排队候诊问题

4.3 数制的转换

4.4 停车场管理

4.5 基数排序

第5章 串的应用

5.1 存储结构与基本运算的算法

5.2 KMP算法

5.3 最长公共子串

5.4 大整数计算器

第6章 多维数组和广义表的应用

6.1 存储结构与基本运算的算法

6.2 魔方阵

6.3 稀疏矩阵的加法运算

6.4 本科生导师制问题

第7章 树状结构的应用

7.1 存储结构与基本运算的算法

7.2 线索二叉树的创建与遍历

7.3 由遍历确定二叉树

7.4 电文的编码和译码

7.5 家族关系查询系统

第8章 图状结构的应用

8.1 存储结构与基本运算的算法

8.2 地铁建设问题

8.3 安排教学计划

8.4 校园导航

附录A 课程设计实例软件包

参考文献

第1章数据结构课程设计概述

1.1数据结构简介

1.数据结构课程的重要地位

数据结构是计算机理论与技术的重要基石，是计算机科学的核心课程之一。用计算机求解任何问题都离不开程序设计，而程序设计的实质是数据表示和数据处理。著名的瑞士计算机科学家沃思（N.Wirth）教授曾指出：算法+数据结构=程序。这里的数据结构是指数据的逻辑结构和存储结构，而算法则是对数据运算的描述。由此可见，程序设计的实质是对实际问题选择一种好的数据结构，再设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。数据结构不仅是一般程序设计的基础，而且是设计和实现操作系统、数据库及其他系统程序和大型应用程序的重要基础。

1968年，著名的美国算法大师克努特（D.E.Knuth）教授开创了“数据结构”的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和物理结构及其操作的著作。20世纪70年代初，“数据结构”作为一门独立的课程开始进入大学课堂。

数据结构是计算机科学与技术各专业的核心课程，它既是理论性较强的基础课，又是实践性很强的专业技术课，在计算机科学领域的主干课程中具有承上启下的作用。它的先行课程有计算机基础、程序设计语言、离散数学和数学等；后继课程有操作系统、数据库原理、编译原理和软件开发技术等。

“数据结构”的发展趋势包括两个方面：一方面是面向专门领域中特殊问题的数据结构的研究和发展，如图形数据结构、知识数据结构和空间数据结构；另一方面从抽象数据类型的角度出发，用面向对象的观点来讨论数据结构，已成为新的发展趋势。

2.数据结构课程的教学目标

数据结构课程的教学目标是要求学生学会分析数据对象特征，掌握数据在计算机中的组织方法和表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法分析的技巧，培养良好的程序设计技能。

人类解决问题的思维方式可分为两大类：一类是推理方式，凭借公理系统思维方法，从抽象公理体系出发，通过演绎、归纳、推理来求证结果，解决特定问题；另一类是算法方式，凭借算法构造思维方式，从具体操作规范入手，通过操作过程的构造和实施解决特定问题。在开发一个优秀软件系统的全过程中，所凭借的思维方式本质上不同于常规数学训练的公理系统思维方式，而是一种算法构造性思维方式。系统开发是创造性思维过程的实现，因而对于一个开发人员，只知道开发工具的语言规则和简单使用过程是不够的，还需要有科学方法指导开发过程，以及在编程技术和应用技能上的不断积累和提高。让学生理解、熟悉、习惯这一套算法构造思维方式，是计算机软件课程教学的重要内容和主要难点。

学习数据结构对于培养人的抽象思维能力、数据建模能力、算法创新能力、程序设计能力、语言描述能力和综合应用能力等具有特定的作用。在信息社会高速发展的时代，信息素质是一个人适应信息社会生存和发展的最基本、最重要的素质之一。

3.数据结构课程的学习特点

数据结构的学习特点主要表现在以下三个方面：

（1）内容的广泛性。数据结构研究的问题非常广泛，内容极为丰富。1974年，获图灵奖的克努特教授编写了一套巨著《计算机程序设计艺术》，目前已发行4卷，每卷500~600页，可见，数据结构研究的内容之多令人惊叹。

（2）学科的交叉性。数据结构研究的内容包括计算机硬件范围的存储装置和存取方法；软件范围的文件系统、数据的动态管理、信息检索；数学范围的集合、逻辑学等方面的知识。此外，还有一些综合性知识，如数据类型、数据表示、数据运算、数据存取和程序设计方法等。因此，数据结构是由数学、计算机硬件和软件知识交叉形成的一门综合性学科。

（3）知识的抽象性。由学科的交叉性可知，数据结构涉及诸多知识领域，这些知识本身就具有一定的抽象性，难度更大的是利用计算机解决实际问题时，必须将实际问题抽象成计算机能够接受并处理的数据模型才能实现，而数学建模不仅需要具备不同领域和学科的专业知识，更需要敏锐的洞察力、高度的抽象思维能力、独特的创新能力以及精湛的表达实现能力等。

数据结构的学习过程是进行复杂程序设计的训练过程。技能培养的重要程度不亚于知识传授，学生不仅要理解授课内容，还应培养应用知识解答复杂问题的能力，形成良好的算法设计思想、方法技巧与风格，进行构造性思维，强化程序抽象能力和数据抽象能力。因此，学习数据结构，仅从书本上学习是不够的，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计的技术。

在学习中注重广泛阅读，加深理解，把书本越读越厚；再通过归纳总结，提纲挈领，把书本越读越薄。

本书列举了数据结构课程设计实例，通过综合训练，能够培养学生实际分析问题、解决问题、编程和动手操作等多方面的能力，很终目的是帮助学生系统地掌握该门课程的基本内容，并运用所学的数据结构知识去解决实际问题。全书共8章,内容包括数据库课程设计概述、线性表、栈、队列、串、多维数组和广义表、树状结构、图状结构等问题的应用。本书是一本独立于具体的数据结构教材的课程设计辅导书，通过针对每种数据结构的具体实例，循序渐进地启发学生完成设计。书中给出的实例都是完整可运行的，同时给出了测试样例、总结与思考等，是一本很好的教学辅导参考书。本书可作为高等院校计算机专业及相关专业教材或参考书，也可供从事软件开发工作和计算机编程爱好者参考。