数据结构和数据管.ppt

《数据结构和数据管.ppt》由会员分享，可在线阅读，更多相关《数据结构和数据管.ppt（28页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、南通职业大学计算机辅助设计与制造机械工程学院 周昇第三章 数据结构和数据管理南通职业大学3.1 常用数据结构3.2 数据管理技术南通职业大学3.1 CAD/CAM3.1 CAD/CAM系统常用的数据结构系统常用的数据结构3.1.1 数据结构的概念数据结构的概念数据结构：数据结构：是按某种逻辑结构组织起来，按一定的存储表示方是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列操作运算的式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。数据的集合。数据结构非线性结构数据存储结构数据运算数据逻辑结构线性结构线性表队列栈网状结构树结构链式存储

2、顺序存储插入，删除，更新，检索，排序南通职业大学3.1.2 线性表线性表逻辑结构逻辑结构：相同数据元素组成的有限序列，除表头和表尾之外，相同数据元素组成的有限序列，除表头和表尾之外，每每 个数据元素仅有一个前驱和后继。如工资表、学生名册。个数据元素仅有一个前驱和后继。如工资表、学生名册。存储结构存储结构：有顺序存储和有顺序存储和链式存储两种结构链式存储两种结构1）顺序存储顺序存储相邻的存储单元存储逻辑上的顺序数据元素。特点：有序性，存储顺序与逻辑顺序一致；均匀性，每个数据元素所占存储单元长度相同。地址计算：设首址为b，则数据元素ai存储地址为 Loc（a）=b+（i-1）L如线性表（a1,a2

3、,ai,an）顺序存储结构为：南通职业大学线性表插入运算线性表插入运算：南通职业大学2 2）链式）链式存储结构存储结构：用任意的存储单元存放线性表的各个数据元素，用指针指示各元素的前驱和后继。链表结点结构：数据域和指针域。指针域有单向指针和双向指针，可构成单向链表和双向链表。南通职业大学南通职业大学链表插入操作运算步骤：申请新结点存储空间；将待插入元素M存放在新增结点数据域；新增结点指针链接。南通职业大学线性表线性表顺序存储与顺序存储与链式链式存储结构比较存储结构比较顺序存序存储：优点：结构均匀，便于数据元素访问和修改操作；不足：删除插入大量数据元素需移动，运算效率低。应用：多用于查找频繁、很

4、少增删的场合。链式存式存储：优点：删除插入效率高，不需数据元素移动，不需 事先分配存储空间，存储空间利用充分。不足：搜索效率低，需从头结点顺次搜寻。应用多用于事先难以确定容量，频繁增、删场合。南通职业大学3.1.3 3.1.3 栈和队列栈和队列栈栈（Stack）：限定在表尾进行插入或删除操作，且为“后进先出”的线性表。队队列列（Queue）：限定在表一端插入，在另一端删除的“先进先出”线性表。a1a2akan-1an入队出队队列数据结构队列数据结构循环循环队列队列南通职业大学3.1.4 树与二叉树树与二叉树 树树结结构构（层层次次结结构构）：每个结点有一个以上后继，除根结点之外，所有结点仅有一

5、个直接前驱。南通职业大学 树结构相关术语树结构相关术语：结点结点 树的基本单元，包含一个数据元素及若干指向其子树的指针；结点度结点度 搞结点子树个数；树的度树的度 树中最大结点的度，图示树的度为4；叶结点叶结点 度为0的结点或终端结点，如图中C、E、K、G、H、I、L等；分支结点分支结点 度不为0的结点或非终端结点；子结点与父结点子结点与父结点 如图中结点B的子结点为E、F、G、H；B父结点A；结点层数结点层数：根结点为第一层，根的子结点为第二层，其余类推；树的深度树的深度 树的最大层数，图示深度为4；森林森林 森林是n棵互不相交树的集合。南通职业大学南通职业大学二叉树二叉树：各结点仅有左子树

6、和右子树的特殊树结构。若深度为k，其结点数最多是2k-1个。满二叉树满二叉树：拥有2k-1个结点的二叉树，所有结点都有左右子树，所有叶结点都在同一层上。完全二叉树完全二叉树：深度为k结点数为n的二叉树，从1至n每一结点编号都与满二叉树编号一致。南通职业大学二叉树存储结构二叉树存储结构顺序存储顺序存储：仅适合于完全二叉树，若用于一般二叉树，将有许多空存储单元。链式存储链式存储：每结点除数据域外，还包含左右子树指针。南通职业大学二叉树的遍历二叉树的遍历遍历遍历：按一定规律每一节点被访问一次。二叉树常用遍历算法二叉树常用遍历算法：先序遍历；中序遍历；后序遍历。先先序序遍遍历历：先访问根结点，然后先序

7、遍历左子树，再先序遍历右子树。如上图先后顺序为ABDGHCEIF。preorder(struct btree*node)preorder(struct btree*node)if(!node)return if(!node)return；printf(printf(“%d%d”，node-data)node-data)；preorder(node-lchild)preorder(node-lchild)；preorder(node-rchild)preorder(node-rchild)；南通职业大学 inorder(struct btree*node)inorder(struct btree

8、*node)if(!node)return if(!node)return；inorder(node-lchild)inorder(node-lchild)；printf(printf(“%d%d”，node-data)node-data)；inorder(node-rchild)inorder(node-rchild)；postorder(struct btree*node)postorder(struct btree*node)if(!node)return if(!node)return；postorder(node-lchild)postorder(node-lchild)；posto

9、rder(node-rchild)postorder(node-rchild)；printf(printf(“%d%d”，node-data)node-data)；中序遍历：中序遍历：先中序遍历左子树，然后访问根结点，再中序遍历右子树。访问顺序为GDHBAEICF。后序遍历：后序遍历：先后序遍历左子树、后序遍历右子树，再访问根结点。结点访问顺序为GHDBIEFCA。南通职业大学树的二叉树表示的转换步骤：树的二叉树表示的转换步骤：将各层兄弟结点用线连起来；除最左子结点外，去掉各结点与其子结点连线；以根为中心，将整棵树顺时针旋转45，最终得到所需二叉树。南通职业大学3.2 数据管理技术常用数据管理

10、技术文件管理系统数据库管理系统工程数据库产品数据管理（PDM)CAD/CAM系统数据管理方法南通职业大学1、文件管理系统：数据文件数据文件：具有相同性质和结构记录的集合。文件管理系统文件管理系统：由操作系统提供，定义数据文件结构，规定数据文件的存取方法，管理文件存储地址。特点特点：系统简单、实现方便灵活、处理效率高。不足不足：数据冗余度大，缺乏数据独立性，数据完整性、安全性难以保证。南通职业大学2、数据库管理系统：数据存储独立于应用程序；实现数据的共享；数据完整和安全性得到保证。南通职业大学数据库常用结构形式 层次模型：树结构，表示“一对多”关系；网状模型：各节点可有多个父节点，表示“多对多”

11、关系；关系模型：二维表结构。a)层次模型b)网状模型南通职业大学3、工程数据库 商用数据库工程数据库用途用于计划事务，数据共享用于工程、产品设计和分析特征数据类型少，关系简单，每种数据大量调用数据类型多，数据间关系复杂，每类数据调用量少处理查询、增删、更改，每次处理周期短，涉及记录少从查询到分析均依赖数据库，每次处理周期长，涉及记录量大服务对象静态，客体间关系清楚，建库前模型已定动态，岁设计过程展开，最终形成设计模型和结果数据性质数值、字符串，数据量大，稳定除数值字符外，还有图形数据，随设计过程，数据量迅速增长结构模型模式简单，联系不强，记录相对稳定模式复杂，数据节点表现为“多对多”的递归关系

12、工程数据库与一般商用数据库的比较工程数据库与一般商用数据库的比较南通职业大学4、数据管理PDMPDM定义：PDM是管理所有与产品相关的信息信息和过程过程的技术。与产品相关的信息与产品相关的信息：CAD/CAM文件、材料清单、产品配置、电子表格、供应商及用户清单等。与产品相关的过程与产品相关的过程：加工工序、工作流程、审批发放过程、产品变更过程等。南通职业大学关系数据库管理系统面向对象管理系统系统工作文档工作系产品配零件分项目管理环境管理统流程置管理类管理管理用户界面开发工具工作站微机网络计算机用户层功能层对象层支持层PDM系统的体系结构系统的体系结构南通职业大学l电子资料室管理和检索电子资料室

13、管理和检索 PDM最基本的功能，PDM核心。l产产品品配配置置管管理理 以电子资料室为底层支持，以物料清单BOM为组织核心，把产品所有工程数据和文档联系起来，对产品相互关系管理。l工工作作流流程程管管理理 实现产品设计与修改过程的跟踪与控制，包括工程数据资料的提交、修改控制、监视审批、文档的分布控制、自动通知控制等。l项项目目管管理理功功能能 实现项目实施过程中的计划、人员以及相关数据的管理与配置，进行项目运行状态监控，完成计划反馈。PDMPDM功能功能南通职业大学基于PDM的集成平台 南通职业大学基于文件基于文件记录的的专用数据管理用数据管理：根据实际需要设计数据文件，应用程序与数据文件一一对应，针对性强，缺乏通用性。在商用在商用DBMSDBMS基基础上建立上建立软件接口件接口：将DBMS提供的数据操作语言（SQL）嵌入宿主语言，建立CAD/CAM的高级应用接口。用工程数据用工程数据库系系统建立数据建立数据库：将是下一代CAD/CAM集成系统数据管理的主流。5、CAD/CAM系统数据管理方法