《数据结构的程序实现ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构的程序实现ppt课件.ppt（132页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构的程序实现ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望数据结构的程序实现n 数据结构是对程序中数据信息的结构组织，供给定问题求解算法的控制结构来处理。nNiklaus wirth曾经给出“算法+数据结构=程序”的公式，得到了计算机科学界的普遍认可。n在程序设计语言中如何表示数据和控制，很大程度上决定了如何使用这个语言来编写程序；所以在程序设计语言中不仅提供了与程序控制流程有关的控制结构，同时也提供了与程序中数据信息组织有关的数据结构。n程序设
2、计的主要任务就是在选取或组织适当的数据结构的基础上，利用三种基本结构（顺序、选择、重复）把逐级分解得到的一系列基本操作组织起来，形成用某种特定语言书写的源程序。数据结构的程序实现(续)n算法与数据结构课程讨论数据结构的目的，就是为了在设计给定问题的求解算法时，应用这些数据结构来组织程序中的数据；从而降低问题的分析与设计难度，提高程序（或算法）的设计质量，缩短设计周期。n这里就有一个在程序中如何实现各种数据结构的问题。实现是使用的前提，只有在程序中实现了数据结构，才能在程序中利用数据结构对给定问题进行有效地求解。n本章将从几个不同的角度讨论如何在程序中实现各种数据结构的问题。第9章 数据结构的程
3、序实现9.1基本的实现策略9.2动态结构的静态实现9.3大批量数据的组织策略9.4数据结构在问题建模中的应用基本的实现策略n程序设计语言中提供了与程序中数据信息组织有关的数据结构，但没有也不可能提供所有的数据结构。n一方面，受科学技术和生产力发展水平的限制，人类认知世界具有历史局限性；人们不可能在某一天完成对现实世界的认知过程，同样也不可能在某一天说对数据结构的认知过程已经完结，这种认知过程是一个渐进式不断深化和逐步完善的过程。n另一方面，受计算机科学发展和计算机系统本身的限制，人们不可能研制出一种设施包罗万象、功能应有尽有的计算机语言和语言翻译系统。n因此，程序设计语言中只可能提供一些基本的
4、和常用的数据结构设施，并提供一些构造求解现实世界中问题所需数据结构的基本设施和方法手段。9.1 基本的实现策略9.1.1 简单数据结构的程序实现9.1.2 构造型数据结构的程序实现9.1.3 数据结构的链式实现9.1.4 数据结构的数组实现简单数据结构的程序实现 n 简单的数据结构，在程序设计语言中已经实现了，并作为数据类型提供给程序设计人员。n诸如整型数据、实型数据、布尔型数据和字符型数据等等。n程序设计人员只要在程序中用相应的类型标识符直接说明程序中数据变量的类型就可以直接使用了，如C语言中的int，unsigned int，long int，short int，unsigned shor
5、t int，char，float和double等。9.1 基本的实现策略9.1.1 简单数据结构的程序实现9.1.2 构造型数据结构的程序实现9.1.3 数据结构的链式实现9.1.4 数据结构的数组实现构造型数据结构的程序实现n还有一些简单类型和构造类型，也是在程序设计语言中已经实现了的数据结构。如枚举型、子界型、日期型、集合、数组、字符串、记录、文件等。n程序设计语言中提供了程序设计人员在程序中说明这些数据类型的方法，程序设计人员只要在程序中的适当位置按照相应的格式和要求对程序中的数据进行说明就可以使用了。如C语言中的枚举、数组、字符串、结构体、共同体、文件等。9.1 基本的实现策略9.1.
6、1 简单数据结构的程序实现9.1.2 构造型数据结构的程序实现9.1.3 数据结构的链式实现9.1.4 数据结构的数组实现数据结构的链式实现n其它的数据结构，如链表、循环链表、栈、队列、广义表、树、二叉树、图、网和堆等，在程序设计语言中一般都没有提供其相应的数据类型，程序设计人员不能够在程序中用类型说明的办法直接引入。n然而，许多程序设计语言都提供有指针类型，程序设计人员可以利用指针类型在程序中动态建立所需要的某种数据结构。n一般地，在建立某种数据结构之前，先需要说明其数据元素的结点类型，如说明成记录、结构体等，再用指针变量动态建立起相应的数据结构，以供求解问题的程序使用或处理。9.1 基本的
7、实现策略9.1.1 简单数据结构的程序实现9.1.2 构造型数据结构的程序实现9.1.3 数据结构的链式实现9.1.4 数据结构的数组实现数据结构的数组实现n如果在程序设计语言中没有提供指针变量，就不能动态实现程序中需要的数据结构；还有一些数据结构，不宜借助指针来实现，如顺序表、顺序栈、顺序队列等。对于这两种情况，程序设计人员都可以在程序中利用数组模拟实现程序中需要的一些数据结构。n数组是每一种高级程序设计语言都提供了的数据结构。可以利用一维数组模拟实现顺序表、顺序栈、顺序队列。可以利用二维数组模拟实现链表或循环链表，其中一列描写一个数据元素（或结点）；若构成数据元素各字段类型不一致，也可改用
8、两个或多个一维数组来模拟实现之。可用三个一维数组来模拟实现二叉树，其中一个数组存放数据域的值，两个数组分别作为左右链域。树可通过左孩子右兄弟表示法转化为二叉树用数组表示，而图和网的邻接矩阵表示法本身就是用二维数组表示的方法。第9章 数据结构的程序实现9.1基本的实现策略9.2动态结构的静态实现9.3大批量数据的组织策略9.4数据结构在问题建模中的应用动态结构的静态实现n所谓动态数据结构（dynamicdatastructure）是指可以随着程序的执行而动态地改变大小程形状的一类数据结构，如链表、树和图等。动态结构的数据，在编译时无法预先规定它们所需要分配的存储空间大小，只有在运行时进行动态存储
9、分配，与之相对应的是静态数据结构（staticdatastructure），数据所需存储空间是一个固定的有限区域，可在程序说明中显式规定，在编译时静态进行存储分配。n凡是可以用指针动态实现的数据结构，都可以利用数组静态地模拟实现。有时也把这种利用数组静态模拟实现了的动态结构称之为半静态数据结构（semi-staticdatastructure）。当然，半动态结构中也包含可变数组和变长记录等部分采用静态分配、部分采用动态分配的数据结构。9.2 动态结构的静态实现9.2.1 静态链表9.2.2 二叉树的静态二叉链表表示法9.2.3 树和森林的双亲表示法9.2.4 哈夫曼算法的静态实现静态链表n在利
10、用提供指针类型的高级程序设计语言编写程序时，链表的实现是很简单和很自然的。如果语言中没有提供指针类型，可以用数组来模拟实现链表结构，并称之为静态链表（staticlinkedlist），用以记录类型作为基类型的数组来模拟实现静态链表。n模拟实现静态链表的数组可如下定义：#define maxsize 100 typedef struct elementype data;/*数据域为元素类型*/int next;/*指针域为整型*/snode;/*snode为结点类型标识符*/snode smaxsize;/*s为基类型是snode的一维数组，即记录数组*/静态链表（续）n注意这里的next域说
11、明与单链表中的说明不同，在单链表中是指向结构体的指针类型，值为结点的实际地址；在静态链表中是int类型，值为结点在s数组中的下标值，指针值为空时用-1表示。n对于静态链表实现线性表的各种运算操作与动态的单链表上的实现基本相同，所不同的是在存储区的管理上有差别。n单链表上的运算操作实现不要考虑存储区的管理问题，是通过malloc函数获得结点空间并利用free函数释放结点空间，存储区的管理交由系统完成；n而静态链表的存储区就是这个记录数组s，获得结点空间和释放结点空间都对数组s进行，必须在程序中设计相应的管理程序段。静态链表及其存储区管理举例9.2 动态结构的静态实现9.2.1 静态链表9.2.2
12、 二叉树的静态二叉链表表示法9.2.3 树和森林的双亲表示法9.2.4 哈夫曼算法的静态实现二叉树的静态二叉链表表示法n对于没有提供指针类型的高级程序设计语言，程序中要用到二叉树结构组织数据信息，可用静态二叉链表（staticbinarylinkedlist）表示法实现二叉树结构。和静态链表类似，静态二叉链表的存储区管理也是利用以结点类型作为基类型的一维数组实现；获得结点空间的函数malloc和释放结点空间的free函数的实现也是类似的。n用静态二叉链表表示二叉树的类型定义如下：#define maxsize 100 typedef struct /*定义结点类型为结构体*/elementyp
13、e data;/*数据域为元素类型*/int lchild,rchild;/*定义左右孩子域为整型*/sbinarytree;sbinarytree stmaxsize;二叉树的静态二叉链表表示法n和静态链表一样，静态二叉链表的左孩子域和右孩子域也都是int类型，其值为数组中的下标值。n静态二叉链表的存储区管理是利用右孩子域形成的静态链栈av，用-1表示指针为NULL的情况。n除了在插入结点时获取一个结点空间以及在删除时释放一个结点空间的存储区管理是要在程序中完成之外，用静态二叉链表表示的二叉树的各种运算操作与用二叉链表表示的二叉树的相应运算操作一致。二叉树的静态二叉链表表示法举例9.2 动态
14、结构的静态实现9.2.1 静态链表9.2.2 二叉树的静态二叉链表表示法9.2.3 树和森林的双亲表示法9.2.4 哈夫曼算法的静态实现树和森林的双亲表示法举例n在前面我们介绍了树和森林的两种存储表示方法，即孩子链表表示法和左孩子右兄弟表示法；这两种表示方法，都可以通过静态链表和静态二叉链表来实现。n树和森林还有一种存储表示方法，就是双亲表示法。因为树和森林中的每一个结点，其双亲结点是惟一的；利用这一性质，在存储结点信息时为每个结点增加一个指向其双亲的指针parent，就可以惟一地表示树或森林。n若用静态链表实现树和森林的双亲表示法，其类型定义如下：#define maxsize 100 ty
15、pedef struct elementype data;int parent;sptnode;sptnode ptmaxsize;树和森林的双亲表示法9.2 动态结构的静态实现9.2.1 静态链表9.2.2 二叉树的静态二叉链表表示法9.2.3 树和森林的双亲表示法9.2.4 哈夫曼算法的静态实现哈夫曼算法的静态实现n 由于哈夫曼树中没有度为1的结点，一棵有n个叶子结点的哈夫曼树有2n-1个结点，所以可用大小为2n-1个元素的数组构造静态链表来存储哈夫曼树，一个数组元素中存放一个结点。n结点的结构可以这样来考虑，由于每个叶子结点都有一个权重值，构造哈夫曼树的过程中每个分枝结点的权重值等于两个
16、孩子结点权重值的和，所以应该有一个权重域和指向左右孩子的两个指针域；n另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子结点的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。n由此可知每个结点至少应该有一个权重域weight和三个指针域parent、lchild和rchild，也就是说要用静态三叉链表来表示哈夫曼树。哈夫曼树及其静态三叉链表存储表示示例哈夫曼算法的静态实现(续)n由于在实际构造哈夫曼树时，是由叶子结点的权值逐级构造最后生成树根，且在构造过程中仅与
17、叶子结点的权值有关而与叶子结点的数据域值无关；n所以构造算法的实现中可以不考虑叶子结点的数据域值，并且在静态三叉链表中从叶子结点开始存放，然后不断地把两棵权值最小的子树合并成为一棵权值为其和的较大的子树，逐步生成各内部结点直到树根。n哈夫曼树的类型定义如下：#define maxvalue 10000#define maxnodenumber 100 typedef struct int weight;int parent,lchild,rchild;htnode;/*定义结点类型标识符*/type htnode*huffmantree;/*定义哈夫曼树类型*/htnode htmaxnode
18、number;建立哈夫曼树的算法的描述n 在以上类型定义的基础上，对于给定的一组权重值，建立其哈夫曼树的算法可描述如下：huffmantree crthuffmantree(int n)int i,j,m1,m2,k1,k2;for(i=0;i2*n-1;i+)hti.weight=0;/*权重初始化为0*/hti.parent=-1;hti.lchild=-1;hti.rchild=-1;for(i=0;in;i+)scanf(“%d”,&hti.weight);建立哈夫曼树的算法的描述(续)for(i=0;in-1;i+)m1=maxvalue;m2=maxvalue;k1=0;k2=0;
19、for(j=0;jn+i;j+)if(htj.parent=-1&htj.weightm1)m2=m1;k2=k1;m1=htj.weight;k1=j;else if(htj.parent=-1&htj.weightm2)m2=htj.weight;k2=j;建立哈夫曼树的算法的描述(续)htk1.parent=n+i;htk2.parent=n+i;htn+i.weight=htk1.weight +htk2.weight;htn+i.lchild=k1;htn+i.rchild=k2;return ht;/*crthuffmantree end*/n注意，在建立哈夫曼树的算法描述中，有效
20、地利用了每个结点的双亲域parent的值是否为-1来区分该结点是否是哈夫曼森林中一棵树的根结点；每次是在根结点中找出两个权重值weight最小的树作为左右子树构造一棵更大的树。求哈夫曼编码的方法n求哈夫曼编码的方法是，在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得到一位哈夫曼编码值；由于每个叶子结点的哈夫曼编码是从根结点到相应叶子结点的路径上各分枝代码所组成的0、1序列，所以先得到的分枝代码为所求编码的低位码而后得到的为高位码。n对于每个叶子结点的哈夫曼编码可以考虑用一个一维数组bit从后向前依次保存所求得的各位编码值，并用start记住编码在
21、数组bit中的开始位置。由此可做如下的类型定义：#define maxbit 10 typedef struct int bitmaxbit;int start;hcodetype;/*定义哈夫曼编码类型*/求哈夫曼编码的算法描述n从叶子结点到根结点逆向求每个叶子结点所代表值的哈夫曼编码的算法可描述如下：void gethuffmancode(htnode ht,int n)int i,j,c,p;hcodetype cdn;for(i=0;in;i+)c=i;j=maxbit+1;do j-;p=htc.parent;if(htp.lchild=c)/*如果c是p的左孩子*/cdi.bitj
22、=0;else cdi.bitj=1;c=p;while(p!=-1);求哈夫曼编码的算法描述(续)cdi.start=j;for(i=0;in;i+)for(j=cdi.start;jnum=1;p=s;for(i=2;inum=i;p-next=s;p=s;p-next=head;return head;/*creat*/Josephus问题算法描述（续）linklist*select(head,m)linklist*head;int m;linklist*p,*q;int i,t;p=head;t=1;q=p;do p=q-next;t=t+1;Josephus问题算法描述（续）if(t
23、%m=0)printf(“%4d”,p-num);q-next=p-next;free(p);else q=p;while(q=p);head=p;return(head);/*select*/Josephus问题算法描述（续）main()int n,m;linklist*head;printf(“input the total numbern”);scanf(“%d”,&n);printf(“input the number to call:n”);scanf(“%d”,&m);creat(head,n);select(head,m);printf(“the last one is%dn”,
24、head-num);/*main*/Josephus问题算法描述（续）n求解Josephus问题，也可以考虑用静态循环链表组织数据。由于数组下标与n个人的编号可以一致起来（不用下标0），故仅用一维数组即可，其中数组元素作为静态指针指向下一个人，这种实现方法称作环形数组实现方法，程序如下：#include“stdio.h”#include“malloc.h”void Josephus(n,m,k)int m,n,k;int R;int i,j;for(i=1;in;i+)Ri=i+1;Josephus问题算法描述（续）Rn=1;if(k=1)j=n;else j=k-1;/*初始化报数变量j*/
25、while(Rj!=j)for(i=1;i=m;i+)/*由1到m报数*/J=Rj;printf(“%dn”,Rj);/*出列*/Rj=RRj;/*删除第j个结点*/printf(“%dn”,Rj);/*最后一个出列者*/*Josephus end*/Josephus问题算法描述（续）void main()int n,m,k;printf(“Josephus问题求解：”);scanf(“%d%d%d”,&n,&m,&k);printf(“n=%d,m=%d,k=%dn”,n,m,k);Josephus(n,m,k);/*main end*/9.4 数据结构在问题建模中的应用9.4.1 Jose
26、phus问题9.4.2 教务管理与二分图9.4.3 学籍管理系统中的数据组织二分图 n设G=(V，E)是一个无向图，其中V=v1，v2，vn，Ee1，e2，en。如果顶点集合V可以分割成为两个互不相交的子集X和Y，使图中每条边ei=(vi，vj)都具这样的性质：其一个端点vi是X中的顶点（即viX）而另一个端点vj是Y中的顶点（即vjY），则称图G是一个二分图（bipartitegraph）。教务管理与二分图 n在高等学校的教务管理中，处理学生选课是一项日常工作。每个学生可同时选修多门课程，每门课程也允许多个学生同时选修。这种学生与课程之间的关系可以用二分图表示为如右图所示，图中的顶点由学生和
27、课程组成，边（s，c）表示学生s选修课程c。教务管理与二分图（续）n教务员经常需要做如下一些管理工作：n登记学生选修的课程；n撤销学生的修课登记；n查看某个学生选修哪些课程；n查看某个课程有哪些学生选修。n这些管理工作即是对二分图做相应的插入、删除和检索操作。n在现实社会中，诸如商店与商品、商店与顾客、技术人员与技术职称、教师与课程等许多管理问题都和学生与课程问题类似，都可以用二分图来表示。二分图是数据库等应用系统的重要的数据结构。教务管理与二分图（续）n 由于二分图中顶点集合V分割成为两个互不相交的子集X和Y，同一子集中（X中或Y中）的顶点无边相连，这就使得二分图的邻接矩阵呈现为一个对称分块
28、矩阵：n即二分图可以用特殊的存储结构矩阵B阵来表示。n显然，用矩阵B表示二分图比邻接矩阵A节省存储空间。然而矩阵B也可能是一个稀疏矩阵，可针对具体情况作进一步的压缩存储处理，教务管理与二分图举例 n例如，前例中图的二分图SCG的邻接矩阵如下图(a)所示，为一对称分块矩阵；其特殊存储表示即矩阵B如下图(b)所示。教务管理与二分图（续）n 教务管理中的另一项重要的日常工作是安排教师教学工作。在一般情况下，每位教师通常可以胜任多门课程的教学，而在一个学期内只讲授他所胜任的一门课程；反之，在一个学期内一门课程只需一位教师主讲。这就需要对教师和课程作合理安排，我们可以用一个二分图来表示教师与课程之间的这
29、种关系，教师和课程都是图中的顶点，边（t，c）表示教师t胜任课程c，右图给出了五位教师和五门课程之间关系的二分图。教务管理与二分图（续）n为每位教师安排一门课程，相当于为每个教师顶点选择一条和课程顶点相关联的边，使任何两个教师顶点不和同一课程顶点相邻接。这种安排课程给每位教师的问题，实际上是图的匹配问题。图匹配问题的一般描述如下：n给定一个图G=(V，E)，若边集合E的一个子集M中任意两条边都不依附图中的同一个顶点，称M是图G的一个匹配（matching）；G的边数最多的匹配称作G的最大匹配（maximalmatching）。如果在图G的一个匹配中，图中每个顶点都是该匹配中某条边的端点，则称该
30、匹配为图G的完全匹配（completematching）。图G的任何一个完全匹配，一定都是图G的最大匹配。二分图TCG的匹配和最大匹配示例 n下图(a)和(b)的实线边分别给出了前例中二分图TCG的一个匹配和一个最大匹配的示例。二分图TCG的匹配和最大匹配n为了求出一个图的最大匹配，显而易见的办法是列举出该图的全部匹配，然后选出边数最多的一个匹配。然而，这种方法的时间复杂度是边数的指数阶函数。因此，需要一种更有效的匹配算法。n下面介绍一种利用增广路径求最大匹配的有效算法。n设M是图G的一个匹配，我们将M中的边所关联的顶点称为已匹配顶点，其余顶点称为未匹配顶点。若P是图G中一条连通两个未匹配顶点
31、的路径，并且在P上属于M的边和不属于M的边交替出现，则称P为一条关于M的增广路径（augmentingpath）。二分图TCG的匹配和最大匹配（续）n由利用增广路径求最大匹配的有效算法的定义可有如下结论：一条关于M的增广路径的长度必为奇数，且路径上的第一条边和最后一条边都不属于M。对于一条关于M的增广路径P，由对称差集运算MP可以得到一个比M更大的匹配。即这个更大的匹配包括所有在M中但不在P中和在P中但不在M中的边的集合构成。M为G的一个最大匹配，当且仅当不存在关于M的增广路径。n结论和是显而易见的。n对于结论，当存在一条关于M的增广路径时，由结论知M不是最大匹配；反之，当M不是最大匹配时，一
32、定可以找到一条关于M的增广路径。二分图TCG的匹配和最大匹配（续）n事实上，设N是一个比M更大的匹配，并令=(V，MN)；因为M和N都是G的一个匹配，所以V中的顶点最多和M中的一条边相关联，也最多和N中的一条边相关联；于是的每个连通分量都是由M和N中的边交替组成的一条简单路径或环，每个环中所含M和N的边数相等，而每条简单路径是一条关于M的增广路径或关于N的增广路径，由于中的边MN所含N的边数较M多，所以中必含一条关于M的增广路径。n由此，求图G=(V，E)的最大匹配M的算法可描述如下：置M为空集；找出一条关于M的增广路径P，并用MP代替M；重复步骤直至不存在关于M的增广路径，此时得到的匹配M即
33、为G的最大匹配。二分图TCG的匹配和最大匹配（续）n在上述算法中，关键问题是如何根据已有匹配M找出G中关于M的一条增广路径。为简化起见，我们只讨论G是二分图的情形。n设M是G的一个匹配，用类似于图的广度优先搜索过程构造一棵树。设层号为i，当i=0时取G的一个未匹配顶点作为树根；当i为奇数时，将那些与第i-1层中一个顶点相关联但不属于M的边，连同该边相关联的另一个顶点一起添加到树上；当i为偶数时，则是添加那些与第i-1层中一个顶点相关联且属于M的边以及该边所关联的另一个顶点。n如果在上述树的构造过程中，发现一个未匹配顶点v被作为树的奇数层顶点，则从树根到顶点v的路径就是一条关于M的增广路径；如果
34、在树的构造过程中既没有找到增广路径，又无法按要求往树上添加新的边和顶点，则可在剩余顶点中再取一个未匹配顶点作树根构造新的一棵树。这个过程一直进行下去，如果不存在其它未匹配顶点，即最终仍未得到任何增广路径，就说明M已为一个最大匹配了。二分图TCG的匹配和最大匹配举例n例如，对前例图(a)中实线边（图TCG的匹配M）：n按上述方法取未匹配顶点t5作为树根，顶点c1是树上惟一的第一层中的顶点，未匹配边（t5，c1）是树上的一条边；n顶点t2处于树的第二层，边（c1，t2）属于M且关联于c1是树上的又一条边；n与t2相关联但不属于M的边有（t2，c4）和（t2，c5）添加到树中，同时顶点c4和c5添加
35、到树中作为第三层；n由于c5是未匹配顶点，n所以到此找到了一条增广路径P：t5c1t2c5。n由此增广路径得到图G的一个更大的匹配MP如前例图(b)中实线边所示，此时的MP是一个完全匹配，从而也是G的最大匹配。二分图TCG的匹配和最大匹配（续）n设二分图G有n个顶点和e条边，M是G的一个匹配。如果用邻接表表示G，那么求一条关于M的增广路径需要O(e)的时间；n由于每找出一条新的增广路径都将得到一个更大的匹配，所以最多求n/2条增广路径就可以求出图G的最大匹配。n因此，求图G的最大匹配所需时间为O(ne)。9.4 数据结构在问题建模中的应用9.4.1 Josephus问题9.4.2 教务管理与二
36、分图9.4.3 学籍管理系统中的数据组织学籍管理系统中的数据组织 n在一个约四千名学生的学院中，学生的学籍档案就构成了一个学籍文件，该文件中包含学生的标识信息和当前学期所学课程的信息，当然还可以包含诸如入学考试成绩、学费支付情况、健康状况和专长等其它数据信息，为了简化讨论假定这些信息不包含在文件中，并假定文件较小足以在内存中处理不需要访问外存储器。学籍管理系统中的数据组织（续）n对于一个学生而言，需要标识学生的信息（学生数据）和该生学习课程的说明数据（课程数据）。n学生数据有姓名、性别、年龄、住址和学号等。其中学号由两个部分组成：注册年号和编号。注册年号为入学登记时的年号，如2000年入学的注
37、册年号为00；编号是某一年内入学登记的顺序号，从0001开始编号。n课程数据有本学期所学课程门数和每一门课程的课程说明。每门课程的说明包括课程标识符（学科代码、年级号、编号），各周安排情况和成绩记载等。学科代码即专业或系名称代码，年级号为14，编号为具体课程的编号。n每周安排情况包括上课方式（L：讲课，T：辅导，Y：实验）、节数、时间（星期几、几点上）、地点（表示楼号、教室号）和指导教师。成绩记载包括平时成绩、考试成绩和总评成绩。对于每个学生都有这样一张表；表的集合就构成了学籍文件。一个学生记录结构举例学籍管理系统中的运算 n对于上图的记录构成的学籍文件可以相应定义一些运算。如：打印指定学生所
38、学全部课程的名称；对指定学生增添或删除一门课程；更改指定学生指定课程的分数；找出指定学生在指定时间上课的教室；修改指定学生其它域的值；在指定学科指定年级中求学生的平均成绩；按字母顺序列出学习指定学科指定课程的所有学生名；更改学习指定课程的所有学生的成绩；按字母顺序列出指定注册年份的所有学生名；列出指定学科指定年级所开设的全部课程。n这些运算涉及到学生数据、课程数据，或是数据中某个域的值，都是频繁出现的最常用运算。学籍管理系统中的运算（续）n 对于任何实际问题，都应该从效率的观点和经济的观点出发考虑设计方法，一般都有一些限制条件，如本例可以做如下两点限制：n 在每次执行运算时，不允许遍历整个文件
39、；因为这样做的代价太高了；n 同一数据不应重复存放在内存中，即不允许数据冗余。n前一个限制对于小文件似乎不必要，但对于大文件（例如数万人的大学）就十分必要了；后一个限制在实践中常常被放宽，因为有时需要把一个记录的同一部分保存在若干地方，以加快运算执行减少运行时间提高算法效率。学籍管理系统中的运算（续）n考察前面的十种常用运算可以看出，前五种运算主要是访问学生数据，后五种运算主要是访问课程数据。n不同的访问路径将决定一个文件的某些部分重新组织而形成的子结构，以便于实现相应的运算；各个子结构相互独立，共享学生数据和课程数据的有关部分。n此外，还可根据其它运算设立其它子结构，如列出指定教师讲授哪些课
40、程的运算，若不允许查找整个文件则需在教师数据的一条路径或子结构中检索。n类似地，另一个运算列出指定教室被占用的时间，此时教室数据的子结构就十分重要了。下一章讨论的各种检索方法都是可行的，可以将数据用数组、链接表、多重表、哈希表、树等任一结构表示，子结构也使用相应的某种结构形式构成；至于具体采用何种结构形式，要视具体问题的需要而定。1.学生数据子结构 n 标识一个学生通常可使用学生名字和学生号码两种方式。在某个访问中若不明确指出采用哪一种标识，可随意使用其中一种标识方式访问，所以在学生数据子结构中应该准备两种方式。学生名字一般是不同的，但也偶然有重名情况；而学生号码的是惟一的，可以作为主关键字。
41、n 首先考虑按学号访问。假设学号是六位数字组成：Y1Y2X1X2X3X4。Y1Y2注册年号，是从某一年开始的连续数；X1X2X3X4为注册年内的顺序编号，从0001开始连续编号直到该年注册学生总数TYR为止。这样，对于学号可以用一个二维数组来表示，Y1Y2作为第一维的下标，X1X2X3X4作为第二维的下标，数组中的每一个元素就标识一位学生，显然这种表示对于访问来说是相当高效的。n如果给数组元素的值赋以对应学生记录的地址，则此数组就成为学号索引；为了访问任何一个学生，都能根据学号随机访问数组得到学生记录的起始地址，从而快速得到该生的全部信息。学生数据子结构举例学生数据子结构（续）n现在讨论用学生
42、名访问的问题。由于学生名是一字符串，不同学生的名字一般不同且无顺序，还有重名情况，所以不宜用数组结构表示不同学生的数据起始地址。n如果采用二叉树构成学生名字索引，需要 次比较才能确定一个学生名的记录地址；若不是完全二叉树比较次数还要多。n采用什么样的结构较好呢？当关键字范围很宽而实际关键字值较少时，采用下一章要介绍的哈希技术最为有效。n这里，建立含有5000项的学生名字哈希表索引，每一项存放与一个学生名字的哈希值相对应记录的起始地址；当学生名字相同时采用链地址法（拉链法）消解冲突，即在学生数据多重表中设立指向哈希值相同的另一个学生数据的链域。学生数据子结构（续）n 学生子结构的其它部分包括学生
43、数据和课程数据。其中学生数据用多重表结构表示，名字的哈希函数值相同者组成一个链表；由于在一个学期中允许学生改变已登记所学课程的门数，所以课程数据构成一个链表，便于增添和删减。课程数据结构链表，是学生数据多重表的一个子表；在学生数据多重表的每个元素中设立一个链域指向所学课程链表的第一个元素。n根据前例图的学生数据子结构，前五个运算的大部分都能有效地实现。然而如找出指定学生指定时间的上课教室，由于要访问的信息不在学生数据子结构中，需要访问下面介绍的课程数据子结构。2.课程数据子结构 n由于课程是由学科开设的，所以课程数据子结构往往又称为学科/课程子结构。它是学籍文件中十分重要的子结构，对于访问指定
44、学科/课程的所有学生信息是很有用的。n学科/课程子结构，可以采用索引倒排文件或索引多重表结构，两者都有各自的优点和不足之处；对于某些运算而言，选取倒排文件可能比把信息深深嵌放在多重表中要容易实现一些。课程数据子结构运算举例n 例如，某学生要求删减一门课程，需执行：寻找指定课程，查找注册表直到找出指定的学生，删减该学生的指定课程。n执行需要在课程索引的倒排文件中检索所指定课程，若索引是多重表结构检索过程类似；执行需检索由所确定课程的倒排文件，若是多重表结构需从头检索学生数据；执行修改课程索引所指的倒排文件和学生数据的有关项，若是多重表结构则需要修改学生数据，其修改过程稍微复杂一些。课程数据子结构
45、（续）n比上述两种形式都更为合适的学科/课程子结构，是采用一种二叉树的结构形式。n按照学科/课程编码，构造一棵按字典序的中序二叉检索树索引；n树中每个结点表示一个学科，设有三个链域Llink、Clink和Rlink。其中Llink和Rlink分别指向本学科的左右孩子学科；Clink指向该学科所开设的各年级课程向量的始地址，该向量中每个元素分别是指向相应年级具体课程链表的第一个元素的指针。n显然，整个学科/课程子结构是一个复合结构的索引，对于检索课程方面的信息特别有效。课程数据子结构举例n下图给出了学科/课程子结构的学科树(二叉检索树)索引：课程数据子结构举例（续）n下图以英语学科的课程结构为例
46、描绘了一个结点的结构，表示其它学科的其余结点的结构形式与此类似。课程数据子结构（续）n构造前例图中的学科树索引时，应适当选取学科名称的字符数，并按适当次序排列结点，以便构造一棵平衡的二叉检索树，提高检索效率。此例中选三个字符并按中根次序排列结点得到的是一棵平衡二叉树，学科定位所需比较次数最多为 次。n为了确定某一课程，先在该学科树索引中找到相应的学科结点，然后沿结点的Clink指针指向向量中的某一指针检索，就可找到指定的课程。例如，为了检索已登记学习ENG201课程的学生，先在学科树索引中找到学科ENG，然后根据201获得指向二年级所学课程（200）的指针，再通过对课程多重表的检索确定课程EN
47、G201的记录，进而由链接到学生倒排文件的指针找到课程ENG201的学生倒排文件，从而列出学习课程ENG201的所有学生。课程数据子结构（续）n 这个学科/课程子结构的结构形式是比较好的，便于实现多种运算。如实现运算：列出已登记学习计算机科学学科课程的全部学生，或从化学学科所开设课程中删去CHM205等等。n如果学科所开设课程采用完全静态结构，虽然会更快地访问某课程，但却不能适应为各年级所开设课程门数的变化，所以宜采用链表来链接这些课程；n另一方面，链表的平均长度是有限的（一般情况下小于5），检索课程链表的平均时间是短暂的，能够达到人们满意的程度。3.运算的实现 n在上述两个子结构的基础上，就
48、可以设计前述十种常用运算了。在此我们只选其中两个运算加以说明，读者可以自行完成每个算法的具体设计与程序编制。n运算：打印指定学生所学的全部课程的名称。假定采用学号给出指定学生，该运算的实现步骤如下：在学生子结构中，首先找到学号索引数组，以学号找出相应数组元素位置，取其元素获得相应学生数据的存储地址；根据求出的起始地址访问该学生数据多重表，获得课程数据链表的起始地址；把课程数据链表中的每个元素（即每门课程）中的学科代码、年级号、编号打印出来，如ENG201、MAT203、CSC301等，就完成了整个运算。运算的实现（续）n 运算：按字母顺序列出学习指定学科指定课程的所有学生名字。运算实现步骤如下
49、：从学科树的根结点出发，调用二叉检索树的检索算法找到由学科代码指定的学科结点，获得指向各年级课程向量的指针Clink；从Clink所指起始地址出发，根据指定课程的年级号找到该年级所开课程的课程链表起始地址；按照得到的地址，在课程多重表中找到指定的课程；由确定的课程记录中获得登记学习该课程的学生倒排文件起始地址；按照学生倒排文件中各个元素（即学生号码），逐一在学生数据子结构中得到学生的名字，形成学习该课程的所有学生的名字表；调用内部排序算法，将形成的学生名字表按字母顺序排列并打印出来。数据结构在问题建模中的应用n对于一个实际的结构，必须根据已学过的各种数据结构的特点，影响算法效率的因素和算法所需的时间等知识，详细导出每个运算的用时表达式，精确地计算出各种运算所需的时间以评价结构的优劣。对数据结构需要反复推敲，以不断改进达到最优程度，提高系统的效率。n在解决实际问题中，对数据结构的组织、算法的设计与分析等问题，不仅应该一一认真考虑，还应进行必要的实验以决定取舍，从而达到令人满意的程度。