机械CADCAM的支撑技术.ppt

例： 二叉树与一般树的区别在于： 1）一般树至少有一个结点，而二叉树可以为空。 2）一般树的子树不区分其次序，而二叉树有左右之分，且不能颠倒。 3）一般树的每一个结点可以有任意个子树，而二叉树每一个结点的子树不能超过2个。 第二节　数据管理技术 3.2.1基本概念 数据项：也称字段或数据元素。是描述事物的一个属性的最小单位。 记录：是数据项的有序集合，用以描述一个事物的一组属性特征。 文件：是记录的集合。 关键字：用来标识一个记录的数据项的值。能够惟一标识一个记录的关键字称为主关键字；不能惟一标识一个记录的关键宇称为次关键字或辅助关键字。 3.2.2 数据文件 　　１.顺序文件 数据的物理存储顺序与逻辑顺序一致，即它的物理存储空间是连续的。顺序文件又可分为两种：一组成文件的记录没有任何次序规律，只是按写入的先后顺序进行存储，称为无序顺序文件；另一种是组成文件的记录是按照某个关键字递增(或递减）的顺序进行存储，称为有顺序文件。 顺序文件的记录存储空间是连续的，因此占用的存储空间少，连续存取记录的速度快，但对于记录的插入、与原记录不等长的修改和删除等操作都十分困难。 2、索引文件 索引即用索引法列出关键字k与相应记录的的地址的对应表。带有索引的文件称为索引文件。 索引文件是与主体数据文件配合使用的，它的索引项是按关键字排过序的，主体数据文件可以是有序或无序顺序文件。 栈的定义 typedef struct { Elem Type s [ m0 ]; Int top; } stack; 1．建立一个栈 用数组作为栈的存储结构，例如 int s[10]。说明这个栈的名称为s，它的深度为10，栈内的数据元素是整型的。top为栈顶指针。在C语言中第一个元素的下标是0，因此top=-1时表示栈空，top=9时表示栈满。 栈的运算 2．进栈（压入） 首先检查栈顶指针top。若top=9，表明栈满，显示“栈满”信息，此时进栈将发生上溢。如果top9，令top等于top+1，再令s[top]等于要进栈的数据元素。 栈的运算 栈的压入 viod push (ST, x) stack * ST; int x; { if (ST－＞top = =m0) printf ( “栈上溢出! \n” ); else { ST－＞top =ST－＞top +1; ST－＞s [ST－＞top] = x; } } 3．出栈（弹出） 首先检查栈践顶指针top。若top=-1，表明栈空，显示“栈空”信息，此时出栈将发生下溢。如果top-1，引用栈顶元素s[top]，再令top=top-1。 栈的运算 栈的弹出 void pop (ST) stack * ST; { if (ST－＞top = =0) printf (“栈下溢出!\n”); else ST－＞top－－; } 读栈顶元素 void top (ST, x) stack * ST; { if (ST－＞top = =0) printf (“无栈顶元素!\n”); else x= ST－＞＞s[ST－＞top]; } 判断栈是否为空 int sempty (ST) stack * ST; { if (ST－＞top = =0) return (1); else return (0); } 实例： 栈的运算 2、树的存储结构 树的逻辑结构为非线性的，所以只能采用链式存储结构。可采用定长或不定长两种方式确定树的结点。 1)定长方式 以具有最大度数的结点的结构作为该树所有结点的结构。每个结点都具有相同数量的子树域。 2、树的存储结构 2)不定长方式 每个结点增加一个存放度数的域，结点的长度随着度数的增加而增加。 采用定长方式存储结构，所有的结点是同构的，运算方便，但浪费一定存储空间。用不定长方式存储结构，可节省一些存储空间，但运算不方便。