《数据结构的程序实现知识课件》由会员分享，可在线阅读，更多相关《数据结构的程序实现知识课件（132页珍藏版）》请在金锄头文库上搜索。
1、数据结构的程序实现,数据结构的程序实现,数据结构是对程序中数据信息的结构组织，供给定问题求解算法的控制结构来处理。 Niklaus wirth曾经给出“算法+数据结构=程序”的公式，得到了计算机科学界的普遍认可。 在程序设计语言中如何表示数据和控制，很大程度上决定了如何使用这个语言来编写程序；所以在程序设计语言中不仅提供了与程序控制流程有关的控制结构，同时也提供了与程序中数据信息组织有关的数据结构。 程序设计的主要任务就是在选取或组织适当的数据结构的基础上，利用三种基本结构（顺序、选择、重复）把逐级分解得到的一系列基本操作组织起来，形成用某种特定语言书写的源程序。,数据结构的程序实现(续),算
2、法与数据结构课程讨论数据结构的目的，就是为了在设计给定问题的求解算法时，应用这些数据结构来组织程序中的数据；从而降低问题的分析与设计难度，提高程序（或算法）的设计质量，缩短设计周期。 这里就有一个在程序中如何实现各种数据结构的问题。实现是使用的前提，只有在程序中实现了数据结构，才能在程序中利用数据结构对给定问题进行有效地求解。 本章将从几个不同的角度讨论如何在程序中实现各种数据结构的问题。,第9章 数据结构的程序实现,9.1 基本的实现策略 9.2 动态结构的静态实现 9.3 大批量数据的组织策略 9.4 数据结构在问题建模中的应用,9.1 基本的实现策略,9.1.1 简单数据结构的程序实现
3、9.1.2 构造型数据结构的程序实现 9.1.3 数据结构的链式实现 9.1.4 数据结构的数组实现,简单数据结构的程序实现,简单的数据结构，在程序设计语言中已经实现了，并作为数据类型提供给程序设计人员。 诸如整型数据、实型数据、布尔型数据和字符型数据等等。 程序设计人员只要在程序中用相应的类型标识符直接说明程序中数据变量的类型就可以直接使用了，如C语言中的int，unsigned int，long int，short int，unsigned short int，char，float和double等。,9.1 基本的实现策略,9.1.1 简单数据结构的程序实现 9.1.2 构造型数据结构的程
4、序实现 9.1.3 数据结构的链式实现 9.1.4 数据结构的数组实现,构造型数据结构的程序实现,还有一些简单类型和构造类型，也是在程序设计语言中已经实现了的数据结构。如枚举型、子界型、日期型、集合、数组、字符串、记录、文件等。 程序设计语言中提供了程序设计人员在程序中说明这些数据类型的方法，程序设计人员只要在程序中的适当位置按照相应的格式和要求对程序中的数据进行说明就可以使用了。如C语言中的枚举、数组、字符串、结构体、共同体、文件等。,9.1 基本的实现策略,9.1.1 简单数据结构的程序实现 9.1.2 构造型数据结构的程序实现 9.1.3 数据结构的链式实现 9.1.4 数据结构的数组实
5、现,数据结构的链式实现,其它的数据结构，如链表、循环链表、栈、队列、广义表、树、二叉树、图、网和堆等，在程序设计语言中一般都没有提供其相应的数据类型，程序设计人员不能够在程序中用类型说明的办法直接引入。 然而，许多程序设计语言都提供有指针类型，程序设计人员可以利用指针类型在程序中动态建立所需要的某种数据结构。 一般地，在建立某种数据结构之前，先需要说明其数据元素的结点类型，如说明成记录、结构体等，再用指针变量动态建立起相应的数据结构，以供求解问题的程序使用或处理。,9.1 基本的实现策略,9.1.1 简单数据结构的程序实现 9.1.2 构造型数据结构的程序实现 9.1.3 数据结构的链式实现
6、9.1.4 数据结构的数组实现,数据结构的数组实现,如果在程序设计语言中没有提供指针变量，就不能动态实现程序中需要的数据结构；还有一些数据结构，不宜借助指针来实现，如顺序表、顺序栈、顺序队列等。对于这两种情况，程序设计人员都可以在程序中利用数组模拟实现程序中需要的一些数据结构。 数组是每一种高级程序设计语言都提供了的数据结构。可以利用一维数组模拟实现顺序表、顺序栈、顺序队列。可以利用二维数组模拟实现链表或循环链表，其中一列描写一个数据元素（或结点）；若构成数据元素各字段类型不一致，也可改用两个或多个一维数组来模拟实现之。可用三个一维数组来模拟实现二叉树，其中一个数组存放数据域的值，两个数组分别
7、作为左右链域。树可通过左孩子右兄弟表示法转化为二叉树用数组表示，而图和网的邻接矩阵表示法本身就是用二维数组表示的方法。,第9章 数据结构的程序实现,9.1 基本的实现策略 9.2 动态结构的静态实现 9.3 大批量数据的组织策略 9.4 数据结构在问题建模中的应用,动态结构的静态实现,所谓动态数据结构（dynamic data structure）是指可以随着程序的执行而动态地改变大小程形状的一类数据结构，如链表、树和图等。动态结构的数据，在编译时无法预先规定它们所需要分配的存储空间大小，只有在运行时进行动态存储分配，与之相对应的是静态数据结构（static data structure），数
8、据所需存储空间是一个固定的有限区域，可在程序说明中显式规定，在编译时静态进行存储分配。 凡是可以用指针动态实现的数据结构，都可以利用数组静态地模拟实现。有时也把这种利用数组静态模拟实现了的动态结构称之为半静态数据结构（semi-static data structure）。当然，半动态结构中也包含可变数组和变长记录等部分采用静态分配、部分采用动态分配的数据结构。,9.2 动态结构的静态实现,9.2.1 静态链表 9.2.2 二叉树的静态二叉链表表示法 9.2.3 树和森林的双亲表示法 9.2.4 哈夫曼算法的静态实现,静态链表,在利用提供指针类型的高级程序设计语言编写程序时，链表的实现是很简单
9、和很自然的。如果语言中没有提供指针类型，可以用数组来模拟实现链表结构，并称之为静态链表（static linked list），用以记录类型作为基类型的数组来模拟实现静态链表。 模拟实现静态链表的数组可如下定义： #define maxsize 100 typedef struct elementype data; /*数据域为元素类型*/ int next; /*指针域为整型*/ snode; /*snode为结点类型标识符*/ snode smaxsize; /*s为基类型是snode的一维数组，即记录数组*/,静态链表（续）,注意这里的next域说明与单链表中的说明不同，在单链表中是指向
10、结构体的指针类型，值为结点的实际地址；在静态链表中是int类型，值为结点在s数组中的下标值，指针值为空时用-1表示。 对于静态链表实现线性表的各种运算操作与动态的单链表上的实现基本相同，所不同的是在存储区的管理上有差别。 单链表上的运算操作实现不要考虑存储区的管理问题，是通过malloc函数获得结点空间并利用free函数释放结点空间，存储区的管理交由系统完成； 而静态链表的存储区就是这个记录数组s，获得结点空间和释放结点空间都对数组s进行，必须在程序中设计相应的管理程序段。,静态链表及其存储区管理举例,9.2 动态结构的静态实现,9.2.1 静态链表 9.2.2 二叉树的静态二叉链表表示法 9
11、.2.3 树和森林的双亲表示法 9.2.4 哈夫曼算法的静态实现,二叉树的静态二叉链表表示法,对于没有提供指针类型的高级程序设计语言，程序中要用到二叉树结构组织数据信息，可用静态二叉链表（static binary linked list）表示法实现二叉树结构。和静态链表类似，静态二叉链表的存储区管理也是利用以结点类型作为基类型的一维数组实现；获得结点空间的函数malloc和释放结点空间的free函数的实现也是类似的。 用静态二叉链表表示二叉树的类型定义如下： #define maxsize 100 typedef struct /*定义结点类型为结构体*/ elementype data;
12、/*数据域为元素类型*/ int lchild,rchild; /*定义左右孩子域为整型*/ sbinarytree; sbinarytree stmaxsize;,二叉树的静态二叉链表表示法,和静态链表一样，静态二叉链表的左孩子域和右孩子域也都是int类型，其值为数组中的下标值。 静态二叉链表的存储区管理是利用右孩子域形成的静态链栈av，用-1表示指针为NULL的情况。 除了在插入结点时获取一个结点空间以及在删除时释放一个结点空间的存储区管理是要在程序中完成之外，用静态二叉链表表示的二叉树的各种运算操作与用二叉链表表示的二叉树的相应运算操作一致。,二叉树的静态二叉链表表示法举例,9.2 动态
13、结构的静态实现,9.2.1 静态链表 9.2.2 二叉树的静态二叉链表表示法 9.2.3 树和森林的双亲表示法 9.2.4 哈夫曼算法的静态实现,树和森林的双亲表示法举例,在前面我们介绍了树和森林的两种存储表示方法，即孩子链表表示法和左孩子右兄弟表示法；这两种表示方法，都可以通过静态链表和静态二叉链表来实现。 树和森林还有一种存储表示方法，就是双亲表示法。因为树和森林中的每一个结点，其双亲结点是惟一的；利用这一性质，在存储结点信息时为每个结点增加一个指向其双亲的指针parent，就可以惟一地表示树或森林。 若用静态链表实现树和森林的双亲表示法，其类型定义如下： #define maxsize
14、100 typedef struct elementype data; int parent; sptnode; sptnode ptmaxsize;,树和森林的双亲表示法,9.2 动态结构的静态实现,9.2.1 静态链表 9.2.2 二叉树的静态二叉链表表示法 9.2.3 树和森林的双亲表示法 9.2.4 哈夫曼算法的静态实现,哈夫曼算法的静态实现,由于哈夫曼树中没有度为1的结点，一棵有n个叶子结点的哈夫曼树有2n-1个结点，所以可用大小为2n-1个元素的数组构造静态链表来存储哈夫曼树，一个数组元素中存放一个结点。 结点的结构可以这样来考虑，由于每个叶子结点都有一个权重值，构造哈夫曼树的过程
15、中每个分枝结点的权重值等于两个孩子结点权重值的和，所以应该有一个权重域和指向左右孩子的两个指针域； 另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子结点的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。 由此可知每个结点至少应该有一个权重域weight和三个指针域parent、lchild和rchild，也就是说要用静态三叉链表来表示哈夫曼树。,哈夫曼树及其静态三叉链表存储表示示例,哈夫曼算法的静态实现(续),由于在实际构造哈夫曼树时，是由叶子结点的权值逐级构
16、造最后生成树根，且在构造过程中仅与叶子结点的权值有关而与叶子结点的数据域值无关； 所以构造算法的实现中可以不考虑叶子结点的数据域值，并且在静态三叉链表中从叶子结点开始存放，然后不断地把两棵权值最小的子树合并成为一棵权值为其和的较大的子树，逐步生成各内部结点直到树根。 哈夫曼树的类型定义如下： #define maxvalue 10000 #define maxnodenumber 100 typedef struct int weight; int parent,lchild,rchild; htnode; /*定义结点类型标识符*/ type htnode *huffmantree; /*定义哈夫曼树类型*/ htnode htmaxnodenumber;,建立哈夫曼树的算法的描述,在以上类型定义的基础上，对于给定的一组权重值，建立其哈夫曼树的算法可描述如下： huffmantree crthuffmantree(int n) int i,j,m1,m2,k1,k2; for(i=0;i2*n-1;i+) hti
