第四章机械技术基础数据结构演示文稿

第四章机械技术基础数据结构演示文稿目前一页\总数一百三十八页\编于十一点优选第四章机械技术基础数据结构目前二页\总数一百三十八页\编于十一点3

一个孤立的具体数据往往没有任何意义。各相关数据的集合→描述任何复杂事物。数据之间的关系为数据赋予了丰富的含义。数据结构---------是数据之间的关系车床床身及导轨主轴箱尾座走刀箱溜板箱刀架离合器主轴组件中间变速机构主轴主轴齿轮主轴轴承目前三页\总数一百三十八页\编于十一点第四章机械CAD中常用的数据结构掌握CAD软件开发所需数据结构的基本理论；线性表栈树二叉树目前四页\总数一百三十八页\编于十一点数据

—是对客观事物的符号表示，是指能输入到计算机内中并被计算机接受和处理的符号的总称。用文字符号、数字符号及其它规定的符号（如图形、图像）对现实世界的事物及其活动的抽象描述。4.1基本概念目前五页\总数一百三十八页\编于十一点

数据元素

—数据元素是数据的基本单位，是数据这个集合中相对独立的个体。在程序中通常作为一个整体来进行考虑和处理。在设计产品的过程中，可以把该产品的每个部件的每一个零件看作一个相对独立的单元，这时每个零件就是一个数据元素；圆柱体、长方体可以作为零件形体的数据元素；直线、圆弧可以作为图形的数据元素。

一个数据元素可由若干个数据项和组合项组成。数据项是数据的不可分割的最小单位，数据项是对客观事物某一方面特性的数据描述。目前六页\总数一百三十八页\编于十一点数据项

是数据中最基本的、不可分的并有命名的数据单位，是对客观事物某一方面特性的数据描述。2）组合项由若干个数据项组成。目前七页\总数一百三十八页\编于十一点数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…}

数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。目前八页\总数一百三十八页\编于十一点车床床身及导轨主轴箱尾座走刀箱溜板箱刀架离合器主轴组件中间变速机构主轴主轴齿轮主轴轴承

数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。目前九页\总数一百三十八页\编于十一点数据结构的三个组成部分：逻辑结构：描述数据元素之间的逻辑关系。

D_S=（D，S）存储结构：

数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：

对数据要进行的运算（查找、插入、删除）。

目前十页\总数一百三十八页\编于十一点数据元素之间的逻辑结构有四种基本类型:①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中的数据元素之间存在一对一的关系。③树型结构：结构中的数据元素之间存在一对多的关系。④图状结构或网状结构：结构中的数据元素之间存在多对多的关系数据的逻辑结构

定义：数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度组织和表达数据。目前十一页\总数一百三十八页\编于十一点图4-2四类基本结构图目前十二页\总数一百三十八页\编于十一点线性结构—结构中的数据元素之间存在一对一的关系。每一个数据元素仅与它前面的一个和后面的一个数据元素相联系。特点：数据间的关系很简单，只是顺序排列的位置关系，而且这种位置关系是线性的。这种结构的数据可以用数表的形式表示。又称这类数据结构为“线性表结构”目前十三页\总数一百三十八页\编于十一点姓名电话号码陈四。。。。。例4-1：电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分别表示某人的名字和电话号码。本问题是一种典型的表格问题。数据与数据成简单的一对一的线性关系。目前十四页\总数一百三十八页\编于十一点例如：线性表的逻辑结构目前十五页\总数一百三十八页\编于十一点树状结构

结构中的数据元素之间存在一对多的关系。

每个数据元素仅与它前面的一个数据元素相关，可与后面多个数据元素相关。树结构ABCDEFGH目前十六页\总数一百三十八页\编于十一点例如：线性表的逻辑结构目前十七页\总数一百三十八页\编于十一点例4－2：磁盘目录文件系统

磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推：本问题是一种典型的树型结构问题，如图1-1

，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。目前十八页\总数一百三十八页\编于十一点网状结构—结构中的数据元素之间存在多对多的关系。数据元素之间的关系是一种多元关系，即多对多、多对一。9412631078310584538912345678

910工艺路线方案图目前十九页\总数一百三十八页\编于十一点例4－3：交通网络图

从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。佛山惠州广州中山东莞深圳珠海图1-2

网状结构目前二十页\总数一百三十八页\编于十一点

数据的存储（物理）结构定义:

是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及数据间的关系。常用种类:

顺序存储结构、链接存储结构。(1)顺序存储结构

定义:

利用一组地址连续的存储单元依次存放各数据元素。

目前二十一页\总数一百三十八页\编于十一点目前二十二页\总数一百三十八页\编于十一点特点：1）存储单元少，简单易行，结构紧凑。

2）数据结构缺乏柔性，若要增删数据，必须重新分配存储单元。应用：查询频繁，修改、补充、删除数据量小的场合。目前二十三页\总数一百三十八页\编于十一点

用一组任意的存储单元存储数据元素(这组存储单元可以是连续的，也可以是不连续的)。信息字段结构形式：

一个数据元素项（结点）由两个字段组成

信息字段（INFO）和指针字段(POINT)指针字段信息字段

存放数据元素本身的域指针字段

存放直接后继或直接前驱的域称为指针域(point)。指针域中存储的信息称作指针。（2）链接式存储结构目前二十四页\总数一百三十八页\编于十一点

链式存储结构1536元素21536元素21346元素31346元素3∧元素4∧元素4存储地址

存储内容

指针1345

元素1

14001346

元素4∧…….……..…….

1400

元素21536…….……..…….1536

元素313461400元素1h1400元素1h目前二十五页\总数一百三十八页\编于十一点structlink{charname;structlink*next};目前二十六页\总数一百三十八页\编于十一点存储结构可独立于逻辑结构。存储的物理顺序不必与逻辑顺序一致而仍能按逻辑要求存取数据。特点：链接存储结构在不改变原来存储结构的条件下，增删记录十分方便，只要控制指针即可。根据指针的数目，链接存储结构有三种类型：单向链结构

双向链结构多向链结构目前二十七页\总数一百三十八页\编于十一点在不改变原来存储结构的条件下，只要控制指针即可R1R2R3R4R5R6链接存储结构的记录增删R1R2R3R4R5链接存储结构的记录增、删

目前二十八页\总数一百三十八页\编于十一点

数据的逻辑结构

数据的存储结构数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队列树形结构图形结构数据结构的三个方面目前二十九页\总数一百三十八页\编于十一点数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5

数据逻辑结构层次关系图逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构目前三十页\总数一百三十八页\编于十一点数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在C语言中，数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例2、整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}

数据对象可以是有限的，也可以是无限的。目前三十一页\总数一百三十八页\编于十一点

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后继。4.2．线性表目前三十二页\总数一百三十八页\编于十一点

线性表(LinearList)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。当n=0时，称为空表。当n>0时，将非空的线性表记作：(a1，a2，…an)a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。线性表的定义4.2．线性表目前三十三页\总数一百三十八页\编于十一点a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱;ai+1，ai+2，…an都是ai(1≦i≦n-1)的后继，其中ai+1是ai的直接后继。目前三十四页\总数一百三十八页\编于十一点线性表逻辑结构

[a(1)，a(2)，a(3)，…,a(i-1)，a(i)，a(i+1)，…，a(n)]

其中，线性表中的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义随具体应用的不同而不同。数据元素ai可以是一个数，可以是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。4.2.1线性表的逻辑结构目前三十五页\总数一百三十八页\编于十一点线性表中的结点可以是单值元素(每个元素只有一个数据项)。例:26个英文字母组成的字母表：(A，B，C、…、Z）光轴轴径系列值表示成线性表形式:（3，6，10，14，18，20，22，…,90）目前三十六页\总数一百三十八页\编于十一点

线性表中的结点可以是记录型元素，每个元素含有多个数据项，每个数据项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。例4：某校2001级同学的基本情况：{(‘2001414101’，‘张强’，‘男’，06/24/1983)，

(‘2001414102’，‘张化司’，‘男’，08/12/1984)…，

(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}目前三十七页\总数一百三十八页\编于十一点

减速器明细表也属线性表，该表中的数据元素是由4个数据项组成的一个记录。目前三十八页\总数一百三十八页\编于十一点若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。目前三十九页\总数一百三十八页\编于十一点

线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。对线性表的数据元素可以访问、插入和删除。

线性表的物理结构（存储结构）

既可以采用顺序存储，也可以采用链接存储结构。目前四十页\总数一百三十八页\编于十一点、线性表的顺序存储结构1、顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

假设线性表的每个元素需占用m个存储单元。则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系：

Loc(ai+1)=Loc(ai)+m

aiai+1Loc(ai+1)m个字节Loc(ai)目前四十一页\总数一百三十八页\编于十一点线性表的第i个数据元素ai的存储位置为:a1a2aianLoc(a1)i-1个元素Loc(ai)=(i-1)*m+Loc(a1)

有序性：各数据元素之间的存储顺序与逻辑顺序一致。均匀性：每个数据元素所占存储空间的长度是相等的。线性表的顺序存储结构的特点目前四十二页\总数一百三十八页\编于十一点2顺序表的基本操作

顺序存储结构中，常用的线性表的操作：

建表、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论。1）建表staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};2）访问charc;C=listc[2];3）修改listc[2]=‘T’;目前四十三页\总数一百三十八页\编于十一点在线性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

4)顺序线性表的插入为保证线性表的均匀性，新的数据元素必须和表内已有元素的类型一致；为了保证线性表的有序性，原线性表第i至最后一个元素要向后移动一个数据元素所占存储空间的长度。目前四十四页\总数一百三十八页\编于十一点5)顺序线性表的插入ABCXDE实现步骤(1)将线性表L中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。(3)线性表长度加1。[例4-5]

插入一个数据元素ABCDE插入后目前四十五页\总数一百三十八页\编于十一点#defineLEN6Main（）{staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};inti,j;charc1；

printf(“\n输入插入新的数据元素：”);c1=getche（）；

printf(“\n输入新的数据元素的位置：”);Scanf(“%d”,&i);For(j=LEN；j>i;j--)

listc[j]=listc[j-1];Listc[j-1]=c1;}目前四十六页\总数一百三十八页\编于十一点3)顺序线性表的删除目前四十七页\总数一百三十八页\编于十一点3)顺序线性表的删除[例4-4]删除一个数据元素。#defineLEN5Main（）{staticcharlistc[5]={‘A’,’B’,’C’,’D’,’E’};inti,j;printf(“\n删除第几个数据元素？”);Scanf(“%d”,&i);For(j=i;j<LEN,;j++)

listc[j-1]=listc[j];

//第i个元素（下标为i-1)开始

Listc[j]=‘\0’;}目前四十八页\总数一百三十八页\编于十一点目前四十九页\总数一百三十八页\编于十一点目前五十页\总数一百三十八页\编于十一点4.2.3线性表的链式存储结构为了能正确表示数据元素间的逻辑关系，在存储每个数据元素的域同时，还必须存储指示其后继数据元素的地址（或位置）信息。在链表结构中，一个数据元素由数据域和指针域组成，称为一个结点。datanext数据域(data)指针域(next)目前五十一页\总数一百三十八页\编于十一点4.2.3线性表的链式存储结构数据元素用指针来保存其直接前趋或直接后继的地址，形成环环相扣的链条，并通过指针来逐个检索数据元素。……...a1a2a3aiai+1annil......a1a2aiai+1an(a1,a2,…ai,ai+1,…an)目前五十二页\总数一百三十八页\编于十一点链接存储结构的记录增、删

在不改变原来存储结构的条件下，只要控制指针即可R1R2R3R4R5R6链接存储结构的记录增删R1R2R3R4R5目前五十三页\总数一百三十八页\编于十一点根据指针的数目，链接存储结构有三种类型：单向链结构

双向链结构多向链结构目前五十四页\总数一百三十八页\编于十一点2.单向链表单向链表的结点指针域中的指针存放该节点直接后继的存放地址。第一个结点的地址存放在链表头指针head中；链表的最后一个结点的指针城设为NULL。OFC如线性表为：L=(A，B，C，D，E，F)A302BB06E663F∧DEFFC238OFCHEAD302B06238EFF663各个数据元素由一个指针域和一个数据域组成，通过指针构成一个链状结构，且链接方向单一。目前五十五页\总数一百三十八页\编于十一点头结点：数据域不存放任何元素，其指针域存放第一个元素的存储地址。头指针：第一个数据元素的存储地址；a1h头结点

特点：

存储空间不一定连续；

元素之间的后继关系是由指针来体现的；

逻辑上相邻，物理上不一定相邻；

目前五十六页\总数一百三十八页\编于十一点正向链：连接方向与逻辑顺序相同反向链：连接方向与逻辑顺序相反R1R2R3R4R5R1R2R3R4R5目前五十七页\总数一百三十八页\编于十一点单向环链：最后一个数据元素与第一个数据元素通过指针链接．特点：①可以从任意一个元素进入，按指针逐个存取各条记录；②某个指针损坏不影响整个结构。单向环链R1R2R3R4R5目前五十八页\总数一百三十八页\编于十一点结点的描述

C语言中用带指针的结构体类型来描述typedefstructLnode{intdata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/}LNode;/*结点的类型*/2)结点的实现

结点是通过动态分配和释放来的实现，即需要时分配，不需要时释放。分别使用C语言提供的标准函数：malloc()，realloc()，sizeof()，free()。目前五十九页\总数一百三十八页\编于十一点动态分配

p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。动态释放

free(p);系统回收由指针变量p所指向的内存区。P必须是最近一次调用malloc函数时的返回值。目前六十页\总数一百三十八页\编于十一点3)最常用的基本操作及其示意图⑴结点的赋值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL目前六十一页\总数一百三十八页\编于十一点⑵常见的指针操作①q=p;操作前pa……q操作后②q=p->next;bpa……操作前操作后qbpa……③p=p->next;bpa……操作前操作后pba……bpa……目前六十二页\总数一百三十八页\编于十一点操作前ypx……bqa…操作后ypx……bqa…④q->next=p;⑤q->next=p->next;操作前ypx……bqa…操作后ypx……bqa…目前六十三页\总数一百三十八页\编于十一点

在链表建立过程中，首先要建立第一个结点，然后不断地在其尾部增加新结点，直到不需再有新结点，即尾指针指向NULL为止。定义结点数据结构，有两个成员DATA和NEXT：

在数据域（data）中定义数据的类型，数据域中的数据可能只有一个也可能有多个，它们的类型可以一样也可以不一样，存放结点数据元素本身；在指针域（next）中定义指向数据结构本身的指针，存放该结点直接后继的地址。

4)建立单向链表目前六十四页\总数一百三十八页\编于十一点定义结构指针变量：

structnode*p,*p1,*head;

head：用来标志链表头；

p：在链表建立过程中，p总是不断先接受系统动态分配的新结点地址。

p1—>next：存储新结点的地址。然后通过动态分配内存给每个结点赋值。申请动态分配一个存储空间的表示形式为：

(structnode*)malloc(sizeof(structnode))

4)建立单向链表目前六十五页\总数一百三十八页\编于十一点链表建立的步骤：第-步：建立第一个结点structnode/*定义结点数据结构*/{intdata;/*数据域*/structnode*next;}/*指向直接后继的指针*/structnode*p,*p1,*head;/*定义结构指针变量*/head=p1=p=(structnode*)malloc(sizeof(structnode);/*申请动态分配一个存储地址，为第一个结点地址*/dataheadp,p1目前六十六页\总数一百三十八页\编于十一点第二步：给第一个结点成员data赋值并产生第二个结点scanf(“%d”,&p—>data);

/*输入10*/p=(structnode*)malloc(sizeof(structnode);datanextnext10第一结点第二结点headp1p链表建立的步骤：目前六十七页\总数一百三十八页\编于十一点第三步：将第一个结点与第二个结点连接起来

p1—＞next=p;10nextnextdata第一结点P1第二结点Pheadp1p链表建立的步骤：目前六十八页\总数一百三十八页\编于十一点第四步：给第二个结点成员data赋值并产生第三个结点p1=p;scanf(“%d”,&p->data);/*输入8*/p=(structnode*)malloc(sizeof(structnode);链表建立的步骤：10nextnext8第一结点第二结点p1第三结点pnext10第一结点headp18next第二结点p1datanext第三结点p第五步：将第二个结点与第三个结点连接起来

p1—＞next=p;nextdata目前六十九页\总数一百三十八页\编于十一点

以后步骤都是重复第四、五步,直到给出一个结束条件，不再建新的结点时，要有：

p—>next＝NULL；它表示尾结点。目前七十页\总数一百三十八页\编于十一点[例4－6]建立链表。用C语言建立单向链表的程序如下：

#include<stdio．h>#include<alloc．h>#defineLENsizeof(structnode)structnode/*定义结点数据结构*/{intdata；

structnode*next；

}；

main(){structnode*p,*pl,*head；

head＝p＝(structnode*)malloc(LEN)；/*申请动态分配一个存储地址，为第一个结点地址*/scanf(“％d”,&p->data)；/*输入第一个结点的数据成员*/目前七十一页\总数一百三十八页\编于十一点while(p->data!＝0)/*结束条件：当输入0时，退出循环*/{p1＝p；

p＝(structnode*)malloc(LEN)；/*申请动态分配一个存储地址，为下一个结点地址*/scanf(”％d”,&p->data)；

/*输入中间结点数据成员*/p1->next=p；

/*中间结点的指针成员值，将前后两个结点连接起来*/

}p->next＝NULL；/*尾结点的指针成员值*/

……}目前七十二页\总数一百三十八页\编于十一点

为了证实已建链表是所需要的，应在上程序的省略处加入下列程序段：

p＝head；/*头指针*/printf(”链表数据成员是：”)；／*链表显示*／

while(p->next!=NULL){printf(”％d”，p->data)；／*显示中间结点数据成员*／

p＝p->next；

}printf(”％d＼n”，p->data)；【结果】

1086420／*建链表时输入的数据*／链表数据成员是：1086420／*显示所建的链表*／目前七十三页\总数一百三十八页\编于十一点打印：没找到访问P开始输入iP=head,j=0i=j+1P=P－﹥nextP为空吗？i=j？返回返回YYNN5)单向链表的访问访问单向链表的第i个结点，应从表头开始检索．根据指针域的值逐个查直到找到第i个结点。目前七十四页\总数一百三十八页\编于十一点5)单向链表的访问[例4－7]对[例4－1]所建链表的第i个结点的访问程序如下（注意：在调用之前，应将p指向表头）：

visit(inti){Intj=1;intdata;Sructnode*p;p=head;while(p)/*当结点指针非空时*/{if(j++＝＝i)/*如果是第i个结点*/{data＝p—>data；return；}/*将第i个结点数据保存在data中，返回*/目前七十五页\总数一百三十八页\编于十一点p＝p－＞next;/*结点指针指向下一结点*/}Pritnf(“\n序号超出范围”);return(0);}目前七十六页\总数一百三十八页\编于十一点

在链表中查找是否有指定的数据元素，若有就输出第一次出现这个数据元素的逻辑位置，否则输出没由这个数据元素的信息。

[例4－8]查找指定数据，程序如下

intsearch(){intj=1;intdata;sructnode*p;p=head;Pritnf(“\n输入要查找的数据：”);scanf(”％d”,&data)；

/*输入要查找的数据*/while(p)/*当结点指针非空时*/{if(p—>data＝＝data；return（j）；)/*如果是第j个结点*/j++；6）单向链表查找目前七十七页\总数一百三十八页\编于十一点p＝p－＞next;/*结点指针指向下一结点*/}Pritnf(“\n没找到该数据”);return(0);}目前七十八页\总数一百三十八页\编于十一点

在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1ai+1ai-1q=p->next;（引入一个结点q）p->next=q->next;

e=q->data;delete(q);pq7）单向链表删除目前七十九页\总数一百三十八页\编于十一点[例4-8]删除第i个结点。Voiddelete(inti){intj=1;sructnode*p，*q;p=q=head;if(i==1){head=q－>next;free(q);return;}/*将头结点指向第一个结点的后继点*/while(p)/*当结点指针非空时*/{if(++j==i-1)/*如果p是第i-1个结点*/{(q=p—>next；/*q指向第i个结点*/if(q==NULL){Pritnf(“\n序号超出范围”);return;}p->next=q->next;/*将第i-1个结点指针指向第i+1个结点*/；

delete(q);

return;}目前八十页\总数一百三十八页\编于十一点p＝p－＞next;/*

如果p不是第i-1个结点，结点指针指向下一结点*/}Pritnf(“\n序号超出范围”);return(0);}目前八十一页\总数一百三十八页\编于十一点

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。xai-1ai8）单向链表插入

在单链表中的实现：有序对

<……ai-1,ai…>

改变为

<…ai-1,x,ai…>目前八十二页\总数一百三十八页\编于十一点

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。首先找到ai-1所在的结点node，然后生成一个数据域为x的新结点newnode，newnode结点作为node的直接后继结点，newnode结点的指针指向ai所在的结点。目前八十三页\总数一百三十八页\编于十一点(1)查找到第i-1个节点，将第

i

个结点的地址node->next取出，存放在指针变量temp中，

即temp＝node->next;(2)为新节点申请一个存储空间，

newnode

＝(structnode*)malloc(LEN)；(指针变量newnode指向该地址);

链表结点的插入过程：xnwenodeaitemp目前八十四页\总数一百三十八页\编于十一点(3)将第i-1个节点的指针指向新节点的地址，

即将新结点的地址赋给第i-1个节点指针

node->next中，即node->next=newnode

(4)将新节点的指针指向第i个节点的地址，即将原链表中第

i个节点的地址值赋给新结点指针newnode->next中，即newnode->next=tempxai-1xai-1ai目前八十五页\总数一百三十八页\编于十一点[例4－9]在下面所建链表的第i个节点之前插入一个新结点的程序如下：目前八十六页\总数一百三十八页\编于十一点Insert(structlink*node，inti，newdata)/*注意：在调用之前，应将node指向表头*/{intj=0;structlink*newnode，*temp;

node=head；

/*给新结点动态分配内存*/newnode＝(structlink*)malloc(sizeof(structlink));newnode->data=‘X’;/*给新结点的数据域赋新值*/Wile(node)/*当结点指针非空时*/{ifj++==i-1/*如果node是第i-1个结点*/目前八十七页\总数一百三十八页\编于十一点{/*将第i个结点地址存放在temp中*/temp=node->next;

/*将第i-1结点指针指向新节点的地址*/node->next=newnode；

/*新结点的指针指向第i个节点的地址*/newnode->next=temp；

return;}node=node->next;/*结点指针指向下一结点*/}}目前八十八页\总数一百三十八页\编于十一点注意

(1)本节仅描述在某结点后插入，若想在某结点之前插入，怎么做？？。

(2)在插入操作中，多增加了两个结构指针变量newnode，temp目前八十九页\总数一百三十八页\编于十一点顺序存储结构和链式存储结构的特点顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。目前九十页\总数一百三十八页\编于十一点链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。目前九十一页\总数一百三十八页\编于十一点

进栈

出栈

栈顶

an

…

a3

a2

栈底

a1

图4-13-

栈的逻辑结构4.3．栈栈是一种特殊的线性表，它的插入与删除操作只能在表的一端进行。定义:栈顶:

栈底:栈的操作:

允许插入和删除操作的一端称为栈顶。

不允许插入和删除操作的一端称为栈底。

是按照后进先出的原则进行的。

4.3.1栈的基本概念目前九十二页\总数一百三十八页\编于十一点

进栈

出栈

栈顶

an

…

a3

a2

栈底

a1

图4-13-

栈的逻辑结构

栈的逻辑结构：s=(a1,a2,a3,,…,,ai,…,an)，则a1称为栈底元素，an为栈顶元素。进栈的顺序：a1,a2,a3,,…,an

；出栈的顺序是：an,an-1,…,a3,a2,a1。特点：后进先出(LIFO---LastInFirstOut)。目前九十三页\总数一百三十八页\编于十一点目前九十四页\总数一百三十八页\编于十一点目前九十五页\总数一百三十八页\编于十一点目前九十六页\总数一百三十八页\编于十一点目前九十七页\总数一百三十八页\编于十一点工程手册的数据处理

设计资料的处理方法有以下两种：

(1)程序化。即在应用程序内部对这些数表及线图进行查表、处理或计算。具体处理方法有两种，第一种数组化:将数表中的数据或线图经离散化后存入一维、二维或三维数组，用查表、插值等方法检索所需数据；第二种公式化:将数表或线图拟合成公式，编入程序计算出所需数据。

(2)数据库存储。将数表及线图(经离散化)中的数据按数据库中的规定进行文件结构化，如确定文件名、字段名、字段类型、字段宽度等，存放在数据库中，数据独立于应用程序，但又能为所有应用程序提供服务。目前九十八页\总数一百三十八页\编于十一点3．1数表的程序化3．1数表的程序化

公式化:适用数表有精确的计算公式找到原来的理论计算公式或经验公式，编入应用程序

程序化:本来就无表达公式，或一时难以找到原来公式，在设计手册或规范中，有各种形式的数表，从函数角度看，有单变量表，也有双变量及多变量表。目前九十九页\总数一百三十八页\编于十一点3．1．1六个实例1．普通V带型号及截面尺寸(见表3—1)

此表查表时，只有一个自变量，即型号，且为非数值型，查得的函数值为V带的顶宽、带高等，均为离散型实型数。程序化时可定义3个一维数组，并将表中数值填写在程序中使数组初始化，再定义一个整型变量i代表型号以此类推。如用户给定i=2(即A型)，则程序可立即查出b[2]=13.0，h[2]=8.0，bp[2]=11.0．目前一百页\总数一百三十八页\编于十一点IntI;floatb[7]={6.0．10.13.0．17.0，22.0，32.0，38.0}；

floath[7]={4.0．6.0，8.0，10.5，13.5，19.0，23.5}；

floatbp[7]={5.3．8.5，11.0，14.0，19.0，27.0·32.0}；目前一百零一页\总数一百三十八页\编于十一点2．平键和键槽的剖面尺寸目前一百零二页\总数一百三十八页\编于十一点2．平键和键槽的剖面尺寸

查表时，根据设计中计算出来的直径dgiven

，决定它位于表3—2轴径的哪个范围内，由此查出b，h，t，t1的值。轴径D是一个数值范围，编程时可将它的上限或下限记入一维数组内，表中其余列的值也放入各自的一维数组内。目前一百零三页\总数一百三十八页\编于十一点Int1；floatdgiven．h，h，t．Tl；／*driven为已知轴径*／float：D[12]一·{10．0．12．O，…，75．0，85．0)；／*float：kb[112]一{3．0，4．0，…，20．O，22．O}；／*floatkh[2]一{3．0，4．O，·一，12．O，14．0)；／*存放表中D的上}存放表中6值*／存放表中^值*／目前一百零四页\总数一百三十八页\编于十一点目前一百零五页\总数一百三十八页\编于十一点3．包角影响系数K2(见表3—3)3．包角影响系数K2(见表3—3)

查表时根据a查K2值，a和K2、均为数值型，可设计两个一维数组来实现。但因计算所得的实际包角a。可能不会正好是表3—3中所列的a值，自然相应的K2值也不会正好是表中之值，因此要用一元函数插值求解(后面将叙述)。已知包角值为口1，定义两个一维数组：floataIpha．[1O]={90．O，100．O，…，170．O，180．0)；floatK2[1O]一(O．68，O．74，…，·O．98，1．oo}；调用一元函数的插值函数(见3．1．2节)，即可求出实际的系数值。目前一百零六页\总数一百三十八页\编于十一点4．齿轮传动工况系数KA(见表3—4)目前一百零七页\总数一百三十八页\编于十一点决定工况系数KA值时有两个自变量，即原动机的载荷特性和工作机的载荷特性，它们原本无数值概念，现分别定义整型变量主一O～2及歹一O～2代表不同工况，用一个二维数组KK(3，3)记录表中系数值。因为表中自变量及函数的值均为离散值，因此查表时无须插值。有关变量及数组的定义如下：

floatKA；／*查得的系数值*／

inti，j；’

floatKK[3][3]={{1．O，1．25，1．75}，{1．25，1．5，2．O}，{1．5，1．75，2.25}}目前一百零八页\总数一百三十八页\编于十一点图3—3齿轮传动工况系数KA查表流程图目前一百零九页\总数一百三十八页\编于十一点表3-5轴肩圆角处理论应力集中系数αα目前一百一十页\总数一百三十八页\编于十一点

决定系数αα时有两个自变量，即r／d和D／d，因此这是一个二维查表问题。将表中系数αα值记录在一个二维数组AA(6，10)中。这个查表问题的特殊之处是两个自变量及系数αα均有可能是连续量，这是因为由设计所得的D，d及r值在一定范围内是随机的，因此必须采用二元函数插值。实际编程时，设已知Dgiven，dgiver，rgiven，再定义及初始化二维数组AA(6，1O)，调用二元插值函数(见3．1．3节)即可求得实际的αα值。目前一百一十一页\总数一百三十八页\编于十一点目前一百一十二页\总数一百三十八页\编于十一点3.3数表的公式化处理改写成为：可见，g(x)是两个基本插值多项式的线性组合。

线性插值

(两点插值）X

x1x2x3……….xn

Y

y1y2y3……….yn

列表函数目前一百一十三页\总数一百三十八页\编于十一点

线性插值C语言函数程序floatinter(floatx,floatx1,floatx2,floaty1,floaty2){floaty;y=y1+(y2-y1)/(x2-x1)*(x-x1);return(y);}目前一百一十四页\总数一百三十八页\编于十一点抛物线插值（三点插值）

目前一百一十五页\总数一百三十八页\编于十一点抛物线插值（三点插值）

目前一百一十六页\总数一百三十八页\编于十一点拉格朗日插值（多点插值）目前一百一十七页\总数一百三十八页\编于十一点3.3.3函数拟合

：函数插值存在的不足：①严格通过每个结点，复印了原有的结点误差；②仍需将各结点数据进行存贮，占用存贮空间。函数拟合:曲线不要求通过已知结点，仅反映数据变化趋势。1

、拉格朗日插值曲线2、函数拟合曲线目前一百一十八页\总数一百三十八页\编于十一点最小二乘法函数拟合：曲线到各结点误差平方和最小。步骤：

1）在坐标纸上绘出各结点，根据其趋势绘制曲线图形；

2）确定近似函数，可为多项式、对数函数或指数函数等；

3）用最小二乘法求出待定系数。误差函数：求导数：解方程求得方程系数a,b:例：直线段f(x)=a+bx的拟合：目前一百一十九页\总数一百三十八页\编于十一点指数函数最小二乘法拟合：

y=abx

对上式两边取对数，转化为线性函数：

lgy=lga+xlgb令:y’=lgy,u=lga,v=lgb，则：

y’=u+vx求出线性方程系数u和v，再根据u,v求出a和b，可得:

y=abx目前一百二十页\总数一百三十八页\编于十一点3.4

数据库在CAD/CAM作业中的应用

VisualFoxPro数据库管理系统

是一种关系型模式，为目前应用最广泛的微机型系统，被称之为大众型数据库管理系统；提供友好的集成环境，具有Windows窗口功能；可通过系统菜单、工具条或命令窗口进行数据库的创建、维护和各种应用操作，包括数据记录的输入、修改、插入、删除、剪切、拷贝、粘贴等作。有较强的数据管理功能、丰富的开发工具，用户可利用编辑器、设计器、项目管理器等工具，开发功能齐全的应用程序。目前一百二十一页\总数一百三十八页\编于十一点FoxPro数据类型

—字符型(character)：用于表示包括汉字和各类字符在内的字符型变量数值，一个字符占用一个字节，字符型变量最多为254个字节。

—数字型(numeral)：用于表示包括正号、负号、小数点及0-9的数字型变量的数值，占用8个字节的内存。

—日期型(Data)：用于表示月、日、年的日期型变量的数值，占8个字节。

—逻辑型(logical)：用于表示由逻辑真或逻辑假构成的逻辑型变量的数值，只用1个字节。

—备注型（Memory）：用于存放由可变长度的ASCⅡ码组成的字段的数值，用10字节引用备注文件。

—货币型（Current）：用于表示货币值的变量数值，占用8个字节。

—

通用型（General）：用于存放OLE对象的数值，占用10字节。

目前一百二十二页\总数一百三十八页\编于十一点数据库的应用实例

支承块（GB2235-80）数据库表文件目前一百二十三页\总数一百三十八页\编于十一点数据库的应用实例

表3-9深沟球轴承轻（2）系列轴承型号尺寸/mm安装尺寸mm额定动负荷kN额定静负荷kN极限转速r/minDDBD1D32001030915254.702.702600020112321017274.802.702400020215351120306.003.552200020317401222357.504.5020000204204714264110.006.3018000205255215314611.007.1016000206306216365615.2010.2013000207357217426520.1013.9011000208408018477325.6018.1010000209458519527825.6018.109000210509020578327.5020.208500

深沟球轴承目前一百二十四页\总数一百三十八页\编于十一点数据库结构定义：数据记录输入：

APPEND

或：EDIT

或：BROWSE轴承型号：内径d:外径D：宽度B：轴肩D1：孔径D3：动负荷：目前一百二十五页\总数一百三十八页\编于十一点目前一百二十六页\总数一百三十八页\编于十一点目前一百二十七页\总数一百三十八页\编于十一点目前一百二十八页\总数一百三十八页\编于十一点目前一百二十九页\总数一百三十八页\编于十一点3·1．2一元函数的插值设有一用数据表格给出的列表函数y--f(x)，如表3—7所示。表3·7列表函数由于列表函数只能给出结点z·，z2，…，z"处的函数值y。，y2，…'Yn当自变量为结点的中间值时，就要用插值法求取其函数值。插值法的基本思想是在插值点附近选取几个合适的结点，过这些选取的点构造一个简单函数g(z)，在此小段上用g(z)代替原来函数厂(z)，这样插值点的函数值就用g(z)的值来代替。因此，插值的实质问题是如何构造一个既简单又具有足够精度的函数g(z)。目前一百三十页\总数一百三十八页\编于十一点

条件是给定z，求其函数值Y。由图3—4可知，步骤如下：图3—4线性插值示意图

(1)选取网个相邻自变量Xi与zH1，满足条件zi<z<zi+l；

(2)过(zi，Yi)及(zm，Yi+·)两点连直线参(z)代替原来的函数厂(z)，则y为了一警(x--x,)+yi(3—1)

。Zi+1一Zi’。，为了与后面抛物线插值的公式在形式上取得一致，可将公式(3—1)改写成．(3-2)目前一百三十一页\总数一百三十八页\编于十一点从图3—4可以看出，这种插值存在一定误差，但当表格中自变量间隔较小，而插值精度又不要求很高时，是可以满足使用要求的。线性插值程序的流程图见图3—5。符号说明如下：

z(行)，y(咒)——一维数组，存放列表函数中z，了值；九——列表函数中结点数；

z咖en，ygiven——已知的z插入值及求出的函数值。．．藉读者注意，C语言中一维数组下标是从0开始的，但图3—5中的下标均从1开始，最简单的办法是在定义C语言数组时，设其体积为以+1，而对下标为0的数组元素不使用就是了。目前一百三十二页\总数一百三十八页\编于十一点厂(z)上取三点，过三点作抛物线g(z)，以g(z)替代厂(z)，显然可以获得比线性插值精度好的结果，图解示意图如图3—6所示。。