第4章 CAD中的数据结构.ppt

后序遍历二叉树的程序 postorder(struct btree *node){if (! node )return ;postorder(node -lchild); postorder(node -rchild); printf(“%d”,node -data); } 4、树的二叉树表示 一般的树可以转换为二叉树。当以链表作为树的存储结构时，树的先序遍历与后序遍历可借用遍历二叉树的方法。 树转化为二叉树的规则： 树的根节点作为二叉树的根节点； 根节点最左端的孩子作为二叉树的左子树； 根节点左端第二个孩子是左端第一个孩子的右子树。 树转化为二叉树的过程： 保留每个节点与最左孩子的边，去掉其余边； 连接每个节点与其原相邻兄弟节点的边； 以树根节点为轴心，将整棵树顺时针旋转45°，即可。 示例说明 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 保留去掉 连边 转旋 第4章 机械CAD中常用的数据结构 4.1基本概念 数据是对客观事物的符号表示，是指所有能输入到计算机内并被计算机处理的符号的总称。数值、字符、图形、图像都是数据。 数据元素是数据的基本单位，是数据集合中相对独立的个体。 数据的逻辑结构：只考虑数据之间的逻辑关系，它独立于数据的存储介质，数据结构指的是逻辑结构。 数据的物理结构：也称为存储结构，是数据元素和它们之间的关系在计算机中的表示。计算机处理的最小数据单位是位（bit）。 数据结构：是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。 数据结构 非线性结构 数据存储结构 数据运算 数据逻辑结构 线性结构 线性表 队列 栈 网状结构 树结构 链式存储 顺序存储 插入，删除，更新，检索，排序 数据的物理结构即数据在计算机内的存储形式。 设计好数据的逻辑结构后，系统通过特定的软件把数据以及数据间的关系按一定的形式存入计算机存储器中，构成这些数据的存储结构，即物理结构。 把逻辑结构变换成物理结构的过程，称为映射。 逻辑结构设计一般多从用户的要求来考虑，而存储结构设计除考虑数据的逻辑结构外，还要考虑存储资源的充分利用、减少存取时间、便于数据修改、提高系统可靠性等存储结构本身的一些特点和要求。 逻辑结构与物理结构两者一般不一致，同一逻辑结构可以映射出多种物理结构。 数据的物理结构有两种基本结构：顺序结构与链式结构。 4.2线性表 逻辑结构：相同数据元素组成的有限序列，除表头和表尾之外，每 个数据元素仅有一个前驱和后继。如下图： 存储结构： 有顺序存储结构和链式存储两种结构 A(1) A(2) A(3) …… A(n-2) A(n-1) A(n) 4.2.1 线性表的顺序存储结构 数据按一定顺序连续存放在计算机的存储单元中，不使用其它单元作为辅助信息。 是一种最简单的存储方式，数据元素间相隔固定距离，数据在逻辑上的顺序与它在计算机内的顺序是一致的。如一元数组，任一元素A(i)的地址ai,可用公式： ai = a1+(i-1)l (l为各数组元素占用的字节数） A(1) A(2) A(3) …… A(n-2) A(n-1) A(n) a1 a1+l a1+2l a1+(n-3)l a1+(n-2)l a1+(n-1)l 特点： 有序性，存储顺序与逻辑顺序一致； 均匀性，每个数据元素所占存储单元长度相同。 1）建表 char listc[6] = {‘A’,’B’,’C’,’D’,’E’}; 2）访问 若访问第i个元素，只要指出它的下标即可。 注意：C语言的数组下标从0开始，到i-1。例如访问第3个元素： char c; c = listc[2]; 3）修改 将第3个元素修改为‘T’ Listc[2] = ‘T’; 4）删除 main(){ char listc[6] = {‘A’,’B’,’C’,’D’,’E’}; int i, j; printf(“\n删除第几个数据元素？”); scanf(“%d”, i); for(j=i; j6; j++) { listc[j-1]=listc[j]; } } 5）插入 由以上运算过程的程序可以看出： 因为线性表在顺序存储结构中是均匀有序的，只要知道线性表的地址和数据元素的长度和序号，就能知道每个元素的实际地址，因此对表内数据元素的访问和修改速度快。但在插入和删除运算时，由于产生大量的数据移动，因此增加了运算时间。所以，这种存储结构多用于查找频繁、很少删除的场合，例如工程手册中的数据表。 4.2