中的数据结构

中的数据结构第一页，共三十一页，编辑于2023年，星期五一、数据的组织形式字段：也称数据项，是数据中最基本的、不可分的和有名字的数据元素。（齿轮零件号、材料牌号、模数、齿宽等）记录：相关的字段组成一个记录，它是字段的集合。这种记录也称为逻辑记录文件：相同性质记录的集合就是文件。数据库：是存储在计算机内部，可以按需要使用的、通用的、综合性的、减少重复存储程序的数据的集合。（数据库不只是文件的集合，还蕴涵对文件的重新组织，以便最大限度的减少文件中的重复数据，并增强数据文件之间和文件数据之间的相互联系）数据库管理系统（DBMS）：应用程序从数据库中存取数据，是在数据库管理系统控制下，根据应用程序中的命令进行的。第二页，共三十一页，编辑于2023年，星期五二、数据的逻辑结构数据的逻辑结构是指用户表达数据的形式，也称为数据的逻辑描述。分为：顺序结构、树状结构、网状结构。1、顺序关系的数据结构（顺序结构）是最简单的逻辑结构，数据节点是顺序排列的。因此每一节点只与它前一个和后一个节点相联系，节点间只存在着线性位置关系，故也称线性并列表。线性并列表是x(1),x(2),…,x(n)(n0)的集合，其约束条件为：当n>0时，x(1)是第一个节点，第k个节点x(k)(1<k<n)的前一节点是x(k-1)，后一节点是x(k+1)，最后节点为x(n)。数组就是该结构的例子。第三页，共三十一页，编辑于2023年，星期五在线性并列表中，栈和队列是用得最广泛的两种重要数据结构。栈：限定只能在表的一端进行插入和删除的线性表。该端称栈顶，另一端称栈底。遵循“后进先出”原则。机械装拆是其例子。队列：限定只能在表的一端进行插入、另一端进行删除的线性表。插入端称队尾，删除端称队首。遵循“先进先出”原则。工件在流水线上的情况是其例子。进栈出栈进队出队队首队尾栈顶栈底第四页，共三十一页，编辑于2023年，星期五2、树状层次关系的数据结构（树状结构）该结构的数据元素之间具有从属关系的层次结构。机器部件4部件3部件2部件1组件3组件2组件1零件3零件2零件1AB1B2B3B4C1C2C3D1D2D3树状结构只有一个根节点，称为树根。树状结构的特点是下一层中的节点只能有一条连线与它的上一层的一个节点相连。树根树叶子树根第一层第二层第三层第四层深度：层次数；度：节点孩子数；树的度：最大的节点度。第五页，共三十一页，编辑于2023年，星期五3、网状关系的数据结构（网状结构）该结构能表达数据间更复杂的关系。网状结构与树状结构的主要区别：树状结构的下层节点只能与一个上层节点连接，而网状结构的下层节点可与几个上层节点连接。第六页，共三十一页，编辑于2023年，星期五三、数据的物理结构数据的物理结构即数据在计算机内的存储形式。设计好数据的逻辑结构后，系统通过特定的软件把数据以及数据间的关系按一定的形式存入计算机存储器中，构成这些数据的存储结构，即物理结构。把逻辑结构变换成物理结构的过程，称为映射。逻辑结构设计一般多从用户的要求来考虑，而存储结构设计除考虑数据的逻辑结构外，还要考虑存储资源的充分利用、减少存取时间、便于数据修改、提高系统可靠性等存储结构本身的一些特点和要求。逻辑结构与物理结构两者一般不一致，同一逻辑结构可以映射出多种物理结构。数据的物理结构有两种最基本方式：顺序式与链式。第七页，共三十一页，编辑于2023年，星期五1、顺序存储结构数据按一定顺序连续存放在计算机的存储单元中，不使用其它单元作为辅助信息。是一种最简单的存储方式，数据元素间相隔固定距离，数据在逻辑上的顺序与它在计算机内的顺序是一致的。如一元数组，任一元素A(i)的地址ai,可用公式：

ai=a1+(i-1)l

(l为各数组元素占用的字节数）A(1)A(2)A(3)……A(n-2)A(n-1)A(n)a1a1+la1+2la1+(n-3)la1+(n-2)la1+(n-1)l第八页，共三十一页，编辑于2023年，星期五2、链式存储结构存储单元不是按逻辑结构的顺序分配的，数据元素在存储器中可按任意顺序存放在任意位置上，数据元素的逻辑元素顺序与在存储器内部的存放顺序可以不同。为了能正确地存放数据元素，随同每一个元素的存储还必须存储另一个元素的地址，称为链指针。每个存储单元由数据域和指针域两部分构成。数据域存放节点的值；指针域用来实现关系，即用来存放与该节点有某种关系的节点的存储单元地址。这种通过指针来实现逻辑结构中的顺序关系的方法，称为链接法或链地址法。第九页，共三十一页，编辑于2023年，星期五左图为磁盘中的实际存储结构，其存储结构的模型如右图。R1R4R2R3R1R2R3R4*数据域指针域结束标记尽管链接法的物理存储结构分散而不按逻辑顺序，但通过指针仍可按顺序来存储各记录，实现逻辑结构的顺序关系。这样物理存储独立于逻辑结构，是链式存储结构的基本特点。第十页，共三十一页，编辑于2023年，星期五链式存储需要额外的存储空间来存放指针，占用的存储区域较大。但节点的插入和删除比较简单，可以不改变原来的物理存储结构，只需要改变相应的指针域数据即可实现。R1R2R3R4链地址法的数据结构又可分为链结构、环结构、树结构。R5*R6删除节点R4插入节点R610111112131420121314地址142012第十一页，共三十一页，编辑于2023年，星期五正向链结构R1R2R3R4反向链结构R5*R1*R2R3R4R5双向链结构R1*R2R3R4*环结构R1R2R3R4R5第十二页，共三十一页，编辑于2023年，星期五树结构：在链式存储结构中，可以设置多个指针，分别指向多个不同的存储单元，从而可以构成多种多样复杂的物理结构，实现数据间更为复杂的逻辑关系。定长方式：一具有最大度数的节点结构作为该树所有节点的结构。A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C90000第十三页，共三十一页，编辑于2023年，星期五A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C9不定长方式：每个节点增加一个存放度数的域，节点的长度随着度数的增加而增加。3324第十四页，共三十一页，编辑于2023年，星期五四、二叉树1、二叉树的逻辑结构二叉树是一种不同于树的数据结构，它的每个节点至多有两棵子树，子树有左右之分，即不能颠倒。二叉树可以是空的，其深度与度的定义与树同。满二叉树：深度为k的有2k-1个节点的二叉树。顺序二叉树：深度为k、节点为n的二叉树，它从1到n的序号与深度为k的满二叉树的节点序号相同。完全二叉树：节点的度数或者为0、或者为2的二叉树。第十五页，共三十一页，编辑于2023年，星期五2、二叉树的存储结构对于满二叉树或顺序二叉树：可用顺序存储形式。对于节点i，若i=1，此节点是根节点；若i=k，k/2是节点i的双亲节点,节点2k是节点i的左孩子,节点2k+1是节点i的右孩子。对于一般二叉树：通常采用链表结构。此存储结构特点：节省存储空间，可用公式随机地访问每个节点和它的双亲节点及左、右孩子，但不便于删除或插入运算。该存储结构会多占一些存储空间，但便于删除或插入运算。每个节点设三个域：值域存放节点的值，左子树域存放左子树的地址，右子树域存放右子树的地址。第十六页，共三十一页，编辑于2023年，星期五3、二叉树的遍历遍历二叉树是按一定的规律走遍二叉树的的每个节点，使每个节点被访问一次且只访问一次。即按一定规律将二叉树的的节点排成一个线性序列。由于二叉树是由根节点、左子树、右子树三个基本单元组成的，若能依次遍历着三部分信息，就能遍历整个二叉树。按根节点、左子树、右子树三者不同的先后次序遍历，可得到六种遍历二叉树的方案，即：根节点、左子树、右子树左子树、根节点、右子树左子树、右子树、根节点根节点、右子树、左子树右子树、根节点、左子树右子树、左子树、根节点左边三种是按照先左后右的次序，是常用的遍历方式。第十七页，共三十一页，编辑于2023年，星期五先序遍历先序遍历的次序是：若二叉树为空，则退出；否则，访问根节点，遍历左子树，遍历右子树，退出。ABDHECFGIVoidpreorder(structbtree*node){if(!node)return;printf(“%d”,node->data);preorder(node->lchild);preorder(node->rchild);}第十八页，共三十一页，编辑于2023年，星期五中序遍历中序遍历的次序是：若二叉树为空，则退出；否则，遍历左子树，访问根节点，遍历右子树，退出。ABDHECFGIVoidinorder(structbtree*node){if(!node)return;inorder(node->lchild);printf(“%d”,node->data);inorder(node->rchild);}第十九页，共三十一页，编辑于2023年，星期五后序遍历后序遍历的次序是：若二叉树为空，则退出；否则，遍历左子树，遍历右子树，访问根节点，退出。ABDHECFGIVoidpostorder(structbtree*node){if(!node)return;postorder(node->lchild);postorder(node->rchild);printf(“%d”,node->data);}第二十页，共三十一页，编辑于2023年，星期五4、树的二叉树表示一般的树可以转换为二叉树。当以链表作为树的存储结构时，树的先序遍历与后序遍历可借用遍历二叉树的方法。树转化为二叉树的规则：树的根节点作为二叉树的根节点；根节点最左端的孩子作为二叉树的左子树；根节点左端第二个孩子是左端第一个孩子的右子树。树转化为二叉树的过程：保留每个节点与最左孩子的边，去掉其余边；连接每个节点与其原相邻兄弟节点的边；以树根节点为轴心，将整棵树顺时针旋转45°，即可。第二十一页，共三十一页，编辑于2023年，星期五示例说明ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI保留去掉连边转旋第二十二页，共三十一页，编辑于2023年，星期五五、图形数据结构数据结构包括逻辑结构与存储结构。逻辑结构是数据及其关系的抽象表示，此处图形数据结构指的是直接存入计算机内的存储结构。图形数据可分为几何信息与拓扑信息两大类。几何信息是表示构成图形的几何元素的量值大小。拓扑信息是表示图形的几何元素之间的连接关系。第二十三页，共三十一页，编辑于2023年，星期五1、确定图形形状的完整信息图形形状的信息包括两个方面：顶点信息（几何信息）与连接关系信息（拓扑信息）。表2给出了长方体各顶点的坐标值，是最基本信息（几何信息）。表3表示了各边的起点号与终点号，体现出顶点与边之间的联系，是长方体的拓扑信息。它们共同构成了长方体最基本的图形形状信息数据。第二十四页，共三十一页，编辑于2023年，星期五说明几何信息与拓扑信息缺一不可。只有连接关系而无顶点信息，不能绘出图形；只有顶点信息而无连接关系，也不能唯一地确定图形形状，往往会产生二义性。第二十五页，共三十一页，编辑于2023年，星期五2、单个三维形体的存储结构目前采用的三维形体的数据结构有三种：单链三表结构、双链表的翼边结构、双链三表结构。若不考虑形体之间的相互联系，而只研究一个形体在计算机内的表示，则通常只需要面、棱边、顶点三张表，用单链指示它们之间的连接关系即可，即单链三表结构。这种数据结构关系清楚，节省存储空间，查找不麻烦。但不太适合对形体频繁进行交互修改，修改一个面，则整个链表内容几乎要全部随之改。第二十六页，共三十一页，编辑于2023年，星期五单链三表结构把形体的拓扑关系与几何信息结合在一起进行处理，不利于拓扑关系相同而尺寸、形状不同的形体。双链表的翼边结构是在数据结构中分别处理形体拓扑和几何信息。从外边观察平面立体时，可以看到每一个棱边都有左右两个邻面及构成着两面的四个邻边，像是长出的翅膀，故称为翼边结构。在体素拼合的几何造型中，最