东华理工大学数据结构课程设计.pdf

东华理工大学数据结构课程设计--第1页

数据结构课程设计

论文题目：基于线性表下的查找与排序

姓名：赖德发

学院：理学院

专业：信息与计算科学

班级：1123202

学号：201120320202

2014年1月17日

1

东华理工大学数据结构课程设计--第1页

东华理工大学数据结构课程设计--第2页

一、实验环境

（1）硬件：学生每人一台计算机。

（2）软件：Windows操作系统，VisualC++6.0。

二、实验内容

基于线性表下的查找与排序。

三、实验原理

1.基于线性表的查找法概述

集合结构是数据对象之间关系松散的一种数据结构，对其进行查找是根据给

定的关键字，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返

回该数据元素在列表中的位置。查找的方法分为比较式查找法和计算式查找法，

其中比较式查找法可分为基于线性表的查找法和基于树的查找法；而计算式查找

法也称为Hash(哈希)查找法。基于线性表的查找法是将集合的数据对象组织成

为线性表形式进行查找，即用给定的关键字与线性表中各元素的关键字逐个比

较，直到成功或失败。线性表的存储结构通常是顺序存储结构，也可使用链式存

储结构。

查找时可在表的一端设置一个“监视哨”，存放要查找元素的关键字，从表

的另一端开始查找，若在“监视哨”找到要查找元素的关键字，返回失败信息，

否则返回关键字的位序。基于线性表的查找技术有着非常广泛的应用。

2.基于线性表的排序法概述

排序是计算机程序设计中的一种重要操作，在数值计算或数据处理过程中，

都会直接或间接用到数据的排序问题。排序的功能是将一个数据元素（或称记录）

的无序序列，按数据元素的关键字大小排列成一个递增或递减有序的记录序列。

由于待排序的记录数量不同，使得排序过程中涉及的存储器也不同，因此可

将排序方法分为内排序和外排序。内排序包括插入、交换、选择和归并等几类排

序。

2.1基于插入类的排序概述

插入类排序的基本思想是假定记录序列中前面的一部分记录已经有序，把后

面的一个记录插入已排序的有序子序列中去，使得插入这个记录后得到的依然是

有序序列，从而逐步扩大有序的子序列的长度，直到所有记录都有序为止。直接

插入排序是采用顺序查找法来确定记录的插入位置。折半插入排序是采用折半查

找法来确定记录的插入位置。希尔排序是对待排序记录序列先做宏观直接插入排

序调整，再做微观直接插入排序调整，故称缩小增量排序排序。

2

东华理工大学数据结构课程设计--第2页

东华理工大学数据结构课程设计--第3页

2.2基于交换类的排序概述

交换排序的基本思想是两两比较待排序记录的关键字，当两个记录的次序相

反时进行交换，直到没有反序的记录为止。基于交换类的排序有冒泡排序和快速

排序。

冒泡排序是比较相邻的元素。如果第一个比第二个大，就交换他们两个。对

每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最

后的元素应该会是最大的数。针对所有的元素重复以上的