数据结构讲义.doc

绪论本章我们讲述如下内容：1数据结构的研究内容2基本术语3抽象数据类型的表示和实现4算法及其分析1. 数据结构的研究内容数据结构是一门研究非数值计算的程序设计问题中的计算机的操作对象以及它们之间的关系和操作的学科。数据结构研究的三种逻辑结构是：线性结构、树、图。数据结构课程的体系是由Donald.E.Knuth开创的，在其著作The Art of Compute Programming第1卷中首次系统地描述了各种数据结构在计算机中的存储和操作，由此奠定了数据结构课程的基础。Donald.E.Knuth2. 基本术语数据：是客观事物的符号表示，在计算机科学中是指所有输入到计算机中并被计算机程序处理的符号总称。数据元素：是数据的基本单位，在计算机程序中作为一个整体来考虑。如图书管理系统中的图书。数据元素通常有多个成员（属性）组成，这些成员又称为数据项。数据对象：是性质相同的数据元素的集合。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。教材中列举了四种数据结构：集合、线性、树、图。集合我们不做深入的阐述，重点是后三种。数据结构的形式定义：数据结构是一个二元组Data_Structure = (D,S)；其中：D是数据元素的有限集，S是D上的关系的有限集。例如：ds1 = (D,S)其中D = a1,a2,a3,a4;S = ,ds1描述的是一个线性结构。ds1 = (D,S)其中D = a1,a2,a3,a4;S = ,ds1描述的是一个树状结构。要求：给出一个数据结构的形式化定义，大家应该能够画出它所描述的结构的拓扑图。逻辑结构：数据结构形式化定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。物理结构（存储结构）：逻辑结构在计算机中的存储方式，通常分为顺序存储方式和链式存储方式。顺序存储方式指的是采用一组连续的内存空间来存储数据。链式存储方式指的是采用一组随机的内存空间（这些内存空间可以是连续的，也可以是不连续的）在存储数据，在链式存储方式中，需要用到指针。同一种逻辑结构通常会对应多种物理结构。数据类型：指的是一个值的集合以及定义在这个集合上的一组操作的总称。抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组操作。3. 抽象数据类型的表示和实现如何将教材中抽象数据类型的伪码转换成可执行的C程序（以Triplet程序为例）：1、 首先新建一个项目文件夹，在此例中，我们建了一个名为triplet的文件夹。2、 编写常用的常量头文件const.h，该文件内容如下：这个头文件在本学期内，只需要编写一次。3、 编写抽象数类型的头文件，triplet.h，其内容如下：4、编写抽象数据类型的基本操作函数库，其文件为bo_tri.c。由于代码太多，大家参考源码即可。5、编写用于测试的主程序，其文件为testtri.c，代码如下：#include e:tctripletconst.h#include e:tctriplettriplet.h#include e:tctripletbo_tri.cmain()Triplet t1,t2;ElemType a,b;InitTriplet(&t1,3,4,5);InitTriplet(&t2,100,50,25);Max(t1,&a);Min(t1,&b);printf(a = %d n,a);printf(b = %d n,b);if(IsAscending(t1)printf(t1