数据结构在程序设计中的应用

天津大学全国统考应用型硕士生入学考试

业务课程大纲

课程编号：901 课程名称：数据结构和程序设计

一、 考试的总体要求

本考试内容由两部分组成，数据结构和程序设计，各占总分的

50％。

数据结构是计算机科学与技术专业基础课,要求学生掌握基本的数据结构及相关的存储方式、基本运算、算法和应用,并能运用盒图、结构化语言、类C、高级语言（C或C++）等方法之一编写算法。

程序设计指采用C++语言，应用数据结构的知识进行面向对象程序设计。要求学生掌握面向对象的程序设计方法，掌握C＋＋语言的基本概念，语法及编程方法。

二、 考试的内容及比例

数据结构考试的内容包括：（ 占总分50%）

1、 线性表、顺序表、链表的定义、特点、存储结构及相关的基本算法

2、 栈的定义、特点、顺序与链式存储表示、基本算法；栈的应用；队列的定义、特点；链队列、循环队列相关的定义、特点、基本算法；栈与递归的实现

3、 广义表的定义及存储结构

4、 二叉树的定义、性质及存储结构；遍历二叉树定义、过程及其算法；二叉树的应用；森林与二叉数的转换；哈夫曼树及其应用；与二叉树应用相关的递归算法

5、 图的定义、存储结构；图的遍历过程及算法；最小生成树构造过程及算法；拓扑排序过程及算法；关键路径相关内容；最短路径相关内容；与图的应用相关的递归算法

6、 静态表查找过程及算法、动态表查找过程及算法；哈希表的构造及处理冲突方法

7、 插入排序、快速排序、选择排序、归并排序、基数排序等内部排序的特点、过程及算法

程序设计考试的内容包括：（ 占总分50％ ）

1、 基本语法与常用语句，面向对象的基本概念

2、 函数的调用，函数参数，函数的重载及函数作用域

3、 类的概念，类的定义与说明，类的成员函数，作用域

4、 对象的概念，对象的初始化，对象的特殊生成方法，对象的生存期

5、 对象指针和对象引用，对象数组

6、 类的继承性和派生类

衡阳师范学院

工科课程设计 -《数据结构》

题 目：迷宫问题（栈）

学 号：******** ********

姓 名：鲁向阳 肖吟月

班 级：物联网班（1405）

指导教师：王杰老师

日 期： 2016年 6月

课程设计报告 - 2 - 目录

1概述 ...................................................................................................... 4

1.1 课程设计目的 ........................................................................... 4

1.2 开发环境 .................................................................................. 4

1.3 任务分配 .................................................................................. 4

2需求分析 .............................................................................................. 5

2.1 题目内容 .................................................................................. 5

2.2 设计思想说明 ........................................................................... 5

数据结构的设计与应用

摘要：数据结构是数据的逻辑结构、物理存储结构及算法的封装，本文从这三个方面讨论如何应用数据结构解决非数值计算的实际问题，并用具体实例说明数据结构的应用。

关键词：数据结构；栈；逻辑结构

中图分类号：tp311.12文献标识码：a文章编号：1007-9599 (2013)

06-0000-02

1什么是数据结构

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素的集合。它包含三方面的内容，逻辑关系、存储关系以及操作。

数据的逻辑结构大致上可以分为线性结构和非线性结构。线性结构的数据元素之间存在一对一的关系，其特点是除了开头和最后一个节点外，其他的任意一个节点都只有一个直接前驱节点后后继节点。线性结构主要包括有线性表、栈和队列。树、集合、图都是非线性结构，其中树形结构模拟层次，图形结构模拟对称和非对称关系。研究数据结构是程序设计的需要，是为了使得程序设计更加的健壮、高效，使得程序的开发更加的方便。

2如何进行数据结构的设计

应用数据结构解决生活中的问题的首要前提是研究应用什么数据结构解决生活中的问题。其分析步骤为：首先分析任务中的操作对象，即找出任务中涉及到的数据，从中总结和抽象出操作对象，并且分析操作对象之间的逻辑关系；其次根据任务中对操作对象的操作，研究应用何种存储方式来存储数据才能高效的执行程序并且占用较小的存储空间。选择数据结构的接口要最接近软件的需求。通常当有多个满足需要的接口数据结构实现时，可以根据比较他们的接口操作的运行时间以及数据结构消耗的空间来进行选择，有的时候时间和空间可以相互转换，比如可以用空间来交换操作的效率；最后在物理存储方式的基础上设计正确的算法实现操作，完成任务。

生活中所要处理的数据之间可以抽象出来不同的逻辑关系，建立不同的数据结构，但是针对实际问题要从中选取能够准确描述问题的基本特性并且易于实现的逻辑结构。例如八枚硬币中其中有一枚硬币是较为轻的，要求用一个天平将这枚轻的硬币判断出来，判断的过程采用将硬币分析两组或者三组，分别使用天平比较的方式来判断。这一判断过程可以用一个树形图来表示，所以可以将该问题抽象为判定树，构建树形结构。

数据结构

——数据结构在生活中的应用

专 业：

学 号：

姓 名：

数据结构在生活中的应用

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。 数据结构包括的主要内容有数组 (Array) 栈 (Stack) 队列 (Queue) 链表

(Linked List)树 (Tree) 图 (Graph) 堆 (Heap) 散列表 (Hash)等。

数据结构在生活中的很多地方又有应用，在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查找、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求；等等。

具体内容的应用也有很多，例如：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系等;。

栈是数据结构中重要的线性结构，是一种特殊的线性表，只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。栈项的当前位置是动态的，对栈顶当前位置的标记称为栈项指针。当栈中没有数据元素时，称为空栈。栈的插入操作称为进栈或入栈，栈的删除操作称为退栈或出栈。栈的应用非常广泛，在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上。相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。在计算机中进行算术表达式的计算是通过栈来实现的。除此之外，栈还在游戏中应用到，例如迷宫问题。