《机械CAD数据结构课件》由会员分享，可在线阅读，更多相关《机械CAD数据结构课件（38页珍藏版）》请在金锄头文库上搜索。
1、第二章 机械CAD/CAM常用的数据结构,第一节 基本概念 一、数据和数据结构 数据 是一切描述客观事物并能被计算机接受和处理的符号的集合。 数据结构 是描述物体数据元素之间关系的组织形式。,具有8各顶点的图形,数据结构,数据结构包含的内容,数据结构一般包含着三个内容： 1）数据的逻辑结构，既数据元素之间的逻辑关系。 2）数据的物理结构，既数据元素及其关系在计算机中的存储表示。 3）数据的运算，即对数据进行的各种操作。,二、数据的逻辑结构和物理结构,数据的逻辑结构是从解决问题的需要出发，为实现必要的功能所建立起来的数据关系，是面向问题的，它的结构形式与存储形式无关。,汽车组成的逻辑结构图,数据
2、的物理结构,数据的物理结构是数据在计算机中的存储形式，是面向计算机的。物理结构根据问题所要求的响应速度、处理时间、修改时间、存储空间和单位时间的处理量等建立，是逻辑数据在计算机中的存储映像。同一逻辑结构的数据可以映像出多种物理结构形式。,以数组构成的树型物理结构,三、 数据项、记录、数据文件,数据项描述对象性质的数值和字符统称为属性值。数据结构中把描述属性的数据称为数据项（也称为字段），数据项是构成数据的最小单位。 记录 数据结构中把描述一个对象的数据称为记录（也称为数据元素、结点），记录是组成数据的基本单位。记录是相对的 数据文件 若干个记录组成的数据表称为数据文件。,数据的逻辑结构分为两大
3、类,线性结构的特征是所有结点最多只有一个直接前驱结点和一个直接后继结点。 非线性结构的特征是一个结点可以有多个直接前驱的结点（如网状结构）和多个后继结点（如树状结构和网状结构）。,第二节 线 性 表,一、线性表的定义 线性结构中的所有结点按前驱后继关系可以排成是一个线性序列： （a1，a2，a3，ai，an） 这个序列称为线性表。,线性表的存储结构,分类 1）顺序存储结构 2）非顺序存储结构,二、 线性表的顺序存储结构,线性表的顺序存储就是用一组连续的存储单元按线性表数据元素的逻辑结构依次存放表中所有数据元素。 知道前一个元素的地址和元素所占用的空间，也就知道它下一个或上一个元素的地址,线性顺
4、序表的基本运算,插入,删除,线性表的特点 1）一般是静态表 2）插入删除操作时间长 3）存储，读入方便,三、 线性表的链式存储结构,链表 链表的存储单元可以是连续的，也可以是不连续的，不连续的链表存储单元可以通过指针来实现线性表中各数据元素之间的逻辑关系。 特点 不需要事先知道一张表的长度 增删操作方便等优点,1.单向链表,1.单向链表,typedef struct linknode Elem Type data； struct linknode *link； node；,1）建立一个单向链表,2）遍历单向链表 3）查找接点 4）插入接点 5）删除接点 单向链表不能反向查询和操作,2、双向链表
5、,定义 建立 遍历 插入 删除 应用,第三节 栈、队列和数组,一、 栈 表中结点的插入、删除运算只能在表的一端进行 （LIFO表）。,栈的定义,typedef struct Elem Type s m0 ; Int top; stack;,1.栈的压入,viod push (ST, x) stack * ST; int x; if (STtop = =m0) printf ( “栈上溢出! n” ); else STtop =STtop +1; STs STtop = x; ,2.栈的弹出,void pop (ST) stack * ST; if (STtop = =0) printf (“栈
6、下溢出!n”); / * 若栈空则显示相应信息 * / else STtop; / * 否则栈指针减1，即栈顶为下一个元素* / 3.读栈顶元素 4.判断栈是否为空,二、队列,它只允许在表的一端进行插入，而在另一端删除(FIFO表）。,第四节 树结构,树是n（n0）个结点的有限集合T。在一棵树中要满足两个条件： 1）有且仅有一个特定的称为根（root）的结点。 2）其余的结点可分为m（m0）棵互不相交的有限集合T1，T2，Tn，其中每一个集合又都是一棵树，称其为根的子树（subtree）。,一般树,概念,根 子树 子结点、父结点、兄弟结点 边 度 一个结点具有的子树数目称为该结点的度 结点A、
7、B、C的度分别为2、3、1树的度为3 树高 叶子结点或终端结点层次,树的存储结构,不定长存储 定长存储,二、 二叉树,它的特点是每个结点下只有左右两棵子树，且左右子树不能颠倒，否则为另一棵二叉树。 二叉树有五种基本形态，如图2-20 所示，其中（a）空二叉树，（b）只有一个根结点的二叉树，（c）右子树为空的二叉树，（d）左子树为空的二叉树，（e）左右子树均为非空的二叉树。,二叉树与一般树的区别在于：,1）一般树至少有一个结点，而二叉树可以为空。 2）一般树的子树不区分其次序，而二叉树有左右之分，且不能颠倒。 3）一般树的每一个结点可以有任意个子树，而二叉树每一个结点的子树不能超过2个。,一般树
8、的二叉树表示：,一般树表示为二叉树可以节省存储空间，处理也方便。 转换表示方法： 树的根结点为二叉树的根结点。 根结点最左端的孩子为二叉树的左子树。 根结点的其余孩子（兄弟结点）为其左端结点的右子树。,二叉树的存储,struct btree struct btree *lchild; char data; struct btree *rchild; ,应用（CSG树）,三、 二叉树的遍历,按一定的次序访问二叉树的每一个结点，且每个结点仅访问一次称为二叉树的遍历， 对于右图所示的二叉树，按三种遍历的结果分别为： 先序遍历（DLR）的结果： A、B、C、D、E、F、G、H、I 中序遍历（LDR）的
9、结果： C、D、B、E、A、H、G、F、I 后序遍历（LRD）的结果： D、C、E、B、H、G、I、F、A,先序遍历（递归调用）,void preorder(struct btree *node) if(! node ) return; printf(n%c,node-data); /coutdata; preorder(node-lchild); preorder(node-rchild); ,中序遍历,void inorder(struct btree *node) if(! node ) return; inorder(node-lchild); printf(n%c,node-data); inorder(node-rchild); ,后序 遍历,void postorder(struct btree *node) if(! node ) return; postorder(node-lchild); postorder(node-rchild); printf(n%c,node-data); ,
