《数据结构》是一门综合性较强的计算机软件、程序设计理论和技术相结合的重要基础课程。它主要讨论抽象数据关系和算法在计算机中的表示与实现,涉及到的数据在计算机中的表示、组织和处理,以及相应结构上的算法设计和算法性能上的分析技术。为解决《数据结构》课程中ADT(抽象数据类型)定义和C++标准模板库的操作名称不一致问题，方便学习和使用，开发了一个严格按照《数据结构》定义的类型模板库，并实现了常用排序算法。该类库具有操作便捷、可读性好、易于维护等特点；对于深化对数据结构算法的理解，提高计算机程序设计水平具有很好的促进作用；而且具有一定的实用价值，能有效地改善数据结构算法教学的质量和效率，对于其他类似系统也有很大的借鉴意义。

[关键词] 数据结构；面向对象；排序；模板

1.4 系统开发的内容和目标

本课题开发的主要内容是数据结构中，对顺序表、单链表、栈、队列、二叉链表等结构中数据处理的算法。关键是如何使用C++语言实现这些算法。排序主要包括直接插入排序、冒泡排序、简单选择排序、快速排序和堆排序。

具体开发目标是：

1.用C++语言实现顺序表、单链表、栈、队列、二叉链表的模板库；

2.用C++语言实现的排序算法模板，包括直接插入排序、冒泡排序、简单选择排序、快速排序和堆排序；

3.有完成的可发布代码，且能正确运行；

4.有详细文档，并以论文的形式记录和总结。

3.2.1 顺序表模板库的设计

1.顺序表的定义

(1)顺序存储方法

即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。

    (2)顺序表(SeqList)

　  用顺序存储方法存储的线性表简称为顺序表(SeqList)。

将一个表存储到计算机中，可以采用许多不同的方法，其中既简单又自然的是顺序存储方式，即将表中的元素逐个存放于数组的一些连续的存储单元中。在这种表示方式下，容易实现对的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的形也是类似的。如果被删除的元素不是表中最后一个元素，则必须将后面的所有元素前移，以填补由于删除所造成的空缺[11]。

用数组实现表时，为了适应表元素类型的变化，将表类型定义为一个结构。在该结构中，用ListItem来表示用户指定的元素类型。其数据成员为n,maxsize和元素数组table。用n记录表长。当表为空时n的值为0,maxsize表示表的最大长度。table是记录表中元素的数组。表中第k个元素(0<k<n+1)存储在数组的第k-1个单元中

目    录

1. 引言 1

1.1 什么是数据结构 1

1.2 系统开发的意义 1

1.3 系统开发现状 2

1.4 系统开发的内容和目标 2

2. 系统开发的相关知识软件的架构平台分析 3

2.1 C++语言概述 3

2.2 面向对象 3

2.2.1 面向过程和面向对象 3

2.2.2 面向对象的特征 5

2.3 抽象数据类型 5

2.4 算法 6

2.4.1 算法的特征 6

2.4.2 算法的评价 7

2.4.3 算法设计与分析的基本方法 7

2.5 系统开发工具和平台 9

3. 系统的详细设计 10

3.1 系统结构 10

3.1.1 系统模块图设计 10

3.1.2 系统功能各模块简单介绍 10

3.2 系统详细设计 11

3.2.1 顺序表模板库的设计 11

3.2.2 单链表模板库的设计 13

3.2.3 栈模板库的设计 16

3.2.4 队列模板库的设计 17

3.2.5 二叉树模板库的设计 19

3.2.6 直接插入排序算法的设计 21

3.2.7 冒泡排序算法的设计 22

3.2.8 简单选择排序算法的设计 23

3.2.9 快速排序算法的设计 24

3.2.10 堆排序算法的设计 25

4. 系统发布和测试 26

4.1 类库的发布 26

4.1.1 类库的导入 26

4.1.2 类库的使用 27

4.2 类库的测试 27

4.2.1 测试环境 27

4.2.2 测试的目的 27

4.2.3 测试的步骤 28

4.2.4 测试的主要内容 28

4.2.5 类库的部分测试结果 28

结束语 30

参考文献 32

致谢 33