工程数据处理及数据库技术

1第4章工程数据处理及数据库技术24.4数据文件数表与线图程序化处理与文件化对比：程序化简单、方便、快捷，仅适用于数据不变化且数据量不太多的情况；当数据量很大时，会使程序冗长，调试困难，且占用内存过多。数据文件把数据以文件的形式存储于外存储器(磁盘)上，独立于应用程序；当程序需要有关数据时，打开数据文件，直接读取数据，数据变化时，只需更改文件，应用程序不变。3数据文件是计算机操作系统提供的、对数据管理的最基本技术，文件中的数据可以有多种组织形式。数据文件按组织形式和管理方式可分为顺序文件、索引文件和散列文件等。4.4.1文件组织形式1、顺序文件顺序文件是指数据的物理存储顺序与逻辑顺序一致的文件，即它的物理存储空间是连续的。顺序文件可分为两种：1）组成文件的记录没有任何次序规律，只是按写入的先后顺序进行存储，称为无序顺序文件；2）组成文件的记录是按照某个关键字递增(递减)的顺序进行存储，称为有序顺序文件。4顺序文件的查找方式一般可以采用顺序扫描、折半查找、分块查找等方法。2、索引文件在文件组织中采用了索引表，目的是提高查找速度。在索引文件中，把文件中所有记录的关键码及对应的入口地址集中在一起，另外组成一个记录或文件，称之为索引表，存入存储器的某个区域。当要查找某个记录时，先在索引表中找到这个需要查找的关键码，根据其提供的指针，即所找记录的地址来找到所需的数据记录。3、散列文件散列文件就是一种直接存取文件。在这种文件中，把记录的关键字通过某种计算处理，直接转换成为该记录的相应地址。5表1平键尺寸和键槽尺寸（GB1095/T—1993）轴径槽轴t轮壳t1bh＞8～10331.81.4＞10～12442.51.8＞12～175532.3……………＞75～85221495.4图1平键与键槽剖面按记录将表中的平键和键槽尺寸建立数据文件，一行一个记录。平键和键槽尺寸的检索是根据轴径进行，而此表中的轴径给出了一个下限和上限范围，可将该下限和上限轴径数据连同平键和键槽尺寸一起存储在数据文件中，这样一个记录将包含有轴径下限值d1、轴径上限值d2、键宽b、键高h、轴颈键槽深t、轮壳键槽深t1共6个数据项。4.4.2数表文件化6平键和键槽尺寸数据文件c语言程序如下：#includestdio.hstructkey_GB{floatd1,d2,b,h,t,t1;}key;main(){inti,j,n;FILE*fp;if((fp=fopen(key.dat,w))==NULL){printf(Cannotopenthedatafile!);exit();}printf(inputthen=);scanf(%d,&n);for(i=0;in;i++){printf(\nrecord/%d:d1,d2,b,h,t,t1=,i);scanf(%f,%f,%f,%f,%f,%f,&key.d1,&key.d2,&key.b,&key.h,&key.t,&key.t1);fwrite(&key,sizeof(structkey_GB),1,fp);}fclose(fp);}7上述程序编译、连接、然后运行，逐行输入各记录数据项，便在磁盘上建立了名为“key.dat”的数据文件。利用所建的数据文件“key.dat”，通过设计得到的轴径尺寸检索所需的平键和键槽尺寸，其c语言程序略。84.5数据结构、数据库技术及应用4.5.1机械CAD中常用的数据结构随着CAD技术的发展及其应用范围的扩展，在CAD技术的具体应用过程中，计算机所处理的数据不再是简单的、孤立的数据，而是相互间存在某种关系的批量数据。这就需要事先对这些数据进行组织构造，即确定合理的数据结构，数据结构的合理与否直接影响程序所占用的空间和程序运行所需要的时间。本节主要讲述机械CAD中几种常用的数据结构。一、基本概念1、数据数据是描述客观事物的数、字符及所有能输入到计算机中处理的符号的集合。92、数据元素数据元素是数据的基本单位，是数据这个集合中的一个个体。例如：在设计产品的过程中，可以把产品的每个部件看作一个相对独立的单元。这样每个部件就是一个数据元素。如果设计一个部件，可以把该部件的每一个零件看作一个相对独立的单元，这时每个零件就是一个数据元素。因此，数据元素本身可能是简单的，也可能是复杂的，它只是相对独立的个体。103、数据的逻辑结构和物理结构数据的逻辑结构仅考虑数据之间的逻辑关系，它独立于数据的存储介质。通常所说的数据结构一般指数据的逻辑结构。数据的物理结构也称存储结构，是数据结构在计算机中的映象。它包括数据元素的映象和关系的映象。在计算机中数据元素是用位串来表示的（位是计算机处理信息的最小单位，一个位表示一个二进制的数。若干位组合起来形成一个位串）。一个位串称为一个结点。结点是数据元素在计算机中的映象。映象的方法不同，数据元素在计算机中的存储结构也不同。顺序映象得到顺序的存储结构。非顺序映象得到非顺序的存储结构（即链式存储结构）。114、数据类型数据类型是程序设计语言允许变量的种类。每一种程序设计语言都提供一组基本的数据类型。如c语言提供字符型、整型、浮点型和双精度4种基本的数据类型。不同的数据类型确定了其所占有位串的大小、也决定了可表示的数值的范围。二、几种常用的数据结构机械CAD中常用的数据结构有：线性表、栈、树及二叉树等。1、线性表（1）线性表的逻辑结构线性表是一种最常用、最简单的数据结构。是一个由n（n＞0）个数据元素a1、a2、…ai…、an组成的有限序列，记为（a1、a2、…ai…、an）。ai可以是一个数、一个符号，甚至是更复杂的数据元素。但同一表中的数据元素的类型是相同的。表中的每个数据元素ai，除第一个（i＝1）和最后一个（i＝n）外，仅有唯一的数据元素ai-1(称为直接前驱)和唯一的数据元素ai+1(称为直接后继)。n称为线性表的长度。当n=0时，称为空表。12（2）线性表的物理结构线性表的物理结构可以采用顺序存储结构，也可以采用链式存储结构。①线性表的顺序存储结构顺序存储就是用一组连续的存储单元，按照线性表中数据元素的逻辑存储顺序依次存放。假定每个数据元素占用l个存储单元，第一个数据元素占有的第一个存储单元的地址为该数据元素的存储位置，则第i个数据元素的存贮位置为lialocaloci）（）（）（1113线性表顺序存储结构的特点是：a、有序性各数据元素之间的存储顺序与逻辑顺序一致。即存储结构体现了逻辑结构。b、均匀性每个数据元素所占存储空间的长度是相等的。程序设计语言中的数组是典型的顺序存储的线性表。在对表中的数据元素进行查找、修改数据内容时速度较快，但要增加或删除数据元素，必然要进行大量的数据移动，增加了运算时间。因此，这种存储结构多用于查找频繁、较少增删的场合，例如各种标准数据、数表等的存储。14②线性表的链式存储结构是指用一组任意的存储单元存放表中的数据元素，存储单元可以是不连续的，为了表示表中元素的逻辑关系，除了存储元素本身的信息之外，还要存储这个元素直接后继或直接前驱的存储位置。这两种信息组成数据元素的存储映象，称为结点。结点包括两种域，存放数据元素本身的域称为数据域，存储直接后继或直接前驱的域称为指针域。指针域内存储的信息称作指针。A、单向链表结点只有一个指针域（通常存放直接后继地址），在顺序存储的线性表中，数组名即为线性表的首地址，也是表的第一个数据元素的地址。在链式存储的线性表中，一般不建数组，所以第一个元素的地址需专门存放在某指针型变量的存储单元中，通常设置一个与链表结点相同的一个结点，它的指针域存放第一个元素的地址。数据域可以是空的，也可以存放表长等其他信息。该结点通常称为链头结点，最后一个结点的指针域是空的。如图：15插入：在第i个数据元素前插入一个数据值为M的数据元素。首先申请该元素的存储空间，得到一个新结点，在新结点的数据域存放数值M，然后找到第i-1个结点，令新结点指针域的指针等于第i-1个结点指针域的指针，再将第i-1个结点的指针域存放这个新结点的地址即可。16删除：若删除第i个数据元素，需找到第i－1和第i个结点，将第i－1个结点的指针域中第i个结点的地址改为第i十1个结点的地址。然后释放第i个结点所占存储空间。见图17B、双向链表每个结点比单向链表多一个指针域，存放结点的直接前驱的地址，即第i个结点的这个指针域存放第i－1个结点的地址。第一个是空的。需再设一个链尾结点，在它的指针域存放最后一个结点的地址。如图：18插入：若在第i个数据元素前插入一个新的数据值为M的数据元素，首先为该元素申请存储空间，得到一个新结点。新结点的数据域存放数值M。然后找到第i－1和第i个结点，令新结点的指针域next存放第i－1个结点的指针域next的内容，指针域last存放第i个结点指针域1ast的内容；结点i－1的指针域next和结点i指针域1ast改存放新结点的地址。删除：若删除第i个数据元素，将涉及第i－1，i，i+1三个结点。将结点i－1的指针域next存放结点i指针域next的内容，将结点i十1的指针域last存放结点i指针域1ast的内容。然后释放结点i所占存储空间。见图：19特点：(1)删除或插入运算时，数据元素不需要移动。(2)不需事先分配存储空间，以免有些空间不能充分利用。(3)表的容量易于扩充。(4)按逻辑位置进行查找的速度慢。链式存储刚好弥补了顺序存储的不足。它多用于事先难以确定容量大小且增删频繁的线性表的存储结构，例如图形系统的实体数据表。202、栈（1）栈的逻辑结构从逻辑结构上看，栈也是线性表。它与普通线性表的区别在于对它的运算仅限定在表尾的一端。假定栈s＝（a1、a2、…、an），a1为栈底元素，an为栈顶元素。栈中元素个数为零时称为空栈。进栈的顺序是a1、a2、…、an，出栈的顺序是an、an-1、…、a1。它的显著特点是后进先出，见图进栈出栈栈底栈顶…a3a2a1an21（2）栈的存储结构和线性表一样，顺序存储或链式存储都可以作为栈的存储结构。但由于栈的容量一般是可以预见的，而且运算仅限于栈顶，所以通常采用顺序存储作为栈的存储结构。（3）栈的运算栈的运算仅限于栈顶，先进后出的原则。223、树（1）树的逻辑结构如图所示，树是具有层次关系的数据结构，树的层次数量称为树的深度或高度。A，B，…，K称为树的结点，其中结点A是树根，称为根结点；结点E，F，G，H，J，K是树叶，也称为终端结点；结点间的连线称为边。从图中可看出：除根结点外，每个结点有且只有一个直接前驱；除终结点外，每个结点可以有不只一个直接后继。结点的直接前驱称为该结点的双亲，结点的直接后继称为该结点的孩子，同一双亲的孩子间称为兄弟。结点的孩子数量称为度。树的所有结点中最大的度数称为这棵树的度数。图中树的深度为4，树的度数也为4。ABCDEFGHIJK树叶子树根树根第二层第一层第四层第三层23（2）树的存储结构由于树的逻辑结构为非线性的，因此只能采用链式存储，根据分配链表指针方式的不同，可采用定长和不定长两种方式确定树的结点。①定长方式以最大度数结点的结构作为该树所有结点的结构。每个结点都具有相同数量的子树域。度数少于树的度数的结点，其指针要空闲下来。如图（b）所示。②不定长方式每个结点增加一个存放度数的域，结点的长度随着度数的增加而增加。如图（c）所示。24(a)(b)(c)ABCDEFGHABCDEFGH00000000000000000ABDCEFGH21310000254、二叉树（1）二叉树的逻辑结构二叉树不同于一般的数据结构，每个结点至多有两棵子树，子树有左右之分。不能颠倒，二叉树可以是空的，二叉树的深度和度的定义与树相同。如图所示为几种特殊的二叉树。①深度为k的有2k－1个结点的二叉树称为满二叉树，如图（a）所示。②深度为k、结点为n的二叉树，它从1到n的序号如果与深度为k的满二叉树的结点序号一致，就称为顺序二叉树，如图（b）所示。③结点的度数或者为0、或者为2的二叉树称为完全二叉树，如图（c）所示。（a）（b）（c）ABCDEFG