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

第四章机械技术基础数据结构演示文稿现在是1页\一共有138页\编辑于星期一优选第四章机械技术基础数据结构现在是2页\一共有138页\编辑于星期一3

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

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

数据元素

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

一个数据元素可由若干个数据项和组合项组成。数据项是数据的不可分割的最小单位，数据项是对客观事物某一方面特性的数据描述。现在是6页\一共有138页\编辑于星期一数据项

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

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

数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。现在是9页\一共有138页\编辑于星期一数据结构的三个组成部分：逻辑结构：描述数据元素之间的逻辑关系。

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

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

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

现在是10页\一共有138页\编辑于星期一数据元素之间的逻辑结构有四种基本类型:①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中的数据元素之间存在一对一的关系。③树型结构：结构中的数据元素之间存在一对多的关系。④图状结构或网状结构：结构中的数据元素之间存在多对多的关系数据的逻辑结构

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

分别表示某人的名字和电话号码。本问题是一种典型的表格问题。数据与数据成简单的一对一的线性关系。现在是14页\一共有138页\编辑于星期一例如：线性表的逻辑结构现在是15页\一共有138页\编辑于星期一树状结构

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

每个数据元素仅与它前面的一个数据元素相关，可与后面多个数据元素相关。树结构ABCDEFGH现在是16页\一共有138页\编辑于星期一例如：线性表的逻辑结构现在是17页\一共有138页\编辑于星期一例4－2：磁盘目录文件系统

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

，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。现在是18页\一共有138页\编辑于星期一网状结构—结构中的数据元素之间存在多对多的关系。数据元素之间的关系是一种多元关系，即多对多、多对一。9412631078310584538912345678

910工艺路线方案图现在是19页\一共有138页\编辑于星期一例4－3：交通网络图

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

网状结构现在是20页\一共有138页\编辑于星期一

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

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

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

定义:

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

现在是21页\一共有138页\编辑于星期一现在是22页\一共有138页\编辑于星期一特点：1）存储单元少，简单易行，结构紧凑。

2）数据结构缺乏柔性，若要增删数据，必须重新分配存储单元。应用：查询频繁，修改、补充、删除数据量小的场合。现在是23页\一共有138页\编辑于星期一

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

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

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

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

存放直接后继或直接前驱的域称为指针域(point)。指针域中存储的信息称作指针。（2）链接式存储结构现在是24页\一共有138页\编辑于星期一

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

存储内容

指针1345

元素1

14001346

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

1400

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

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

双向链结构多向链结构现在是27页\一共有138页\编辑于星期一在不改变原来存储结构的条件下，只要控制指针即可R1R2R3R4R5R6链接存储结构的记录增删R1R2R3R4R5链接存储结构的记录增、删

现在是28页\一共有138页\编辑于星期一

数据的逻辑结构

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

线性结构

非线性结构

顺序存储

链式存储线性表栈队列树形结构图形结构数据结构的三个方面现在是29页\一共有138页\编辑于星期一数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5

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

数据对象可以是有限的，也可以是无限的。现在是31页\一共有138页\编辑于星期一

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

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

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

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

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

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

(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}现在是37页\一共有138页\编辑于星期一

减速器明细表也属线性表，该表中的数据元素是由4个数据项组成的一个记录。现在是38页\一共有138页\编辑于星期一若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。现在是39页\一共有138页\编辑于星期一

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

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

既可以采用顺序存储，也可以采用链接存储结构。现在是40页\一共有138页\编辑于星期一、线性表的顺序存储结构1、顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

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

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

aiai+1Loc(ai+1)m个字节Loc(ai)现在是41页\一共有138页\编辑于星期一线性表的第i个数据元素ai的存储位置为:a1a2aianLoc(a1)i-1个元素Loc(ai)=(i-1)*m+Loc(a1)

有序性：各数据元素之间的存储顺序与逻辑顺序一致。均匀性：每个数据元素所占存储空间的长度是相等的。线性表的顺序存储结构的特点现在是42页\一共有138页\编辑于星期一2顺序表的基本操作

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

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

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

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

插入一个数据元素ABCDE插入后现在是45页\一共有138页\编辑于星期一#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;}现在是46页\一共有138页\编辑于星期一3)顺序线性表的删除现在是47页\一共有138页\编辑于星期一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’;}现在是48页\一共有138页\编辑于星期一现在是49页\一共有138页\编辑于星期一现在是50页\一共有138页\编辑于星期一4.2.3线性表的链式存储结构为了能正确表示数据元素间的逻辑关系，在存储每个数据元素的域同时，还必须存储指示其后继数据元素的地址（或位置）信息。在链表结构中，一个数据元素由数据域和指针域组成，称为一个结点。datanext数据域(data)指针域(next)现在是51页\一共有138页\编辑于星期一4.2.3线性表的链式存储结构数据元素用指针来保存其直接前趋或直接后继的地址，形成环环相扣的链条，并通过指针来逐个检索数据元素。……...a1a2a3aiai+1annil......a1a2aiai+1an(a1,a2,…ai,ai+1,…an)现在是52页\一共有138页\编辑于星期一链接存储结构的记录增、删

在不改变原来存储结构的条件下，只要控制指针即可R1R2R3R4R5R6链接存储结构的记录增删R1R2R3R4R5现在是53页\一共有138页\编辑于星期一根据指针的数目，链接存储结构有三种类型：单向链结构

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

特点：

存储空间不一定连续；

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

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

现在是56页\一共有138页\编辑于星期一正向链：连接方向与逻辑顺序相同反向链：连接方向与逻辑顺序相反R1R2R3R4R5R1R2R3R4R5现在是57页\一共有138页\编辑于星期一单向环链：最后一个数据元素与第一个数据元素通过指针链接．特点：①可以从任意一个元素进入，按指针逐个存取各条记录；②某个指针损坏不影响整个结构。单向环链R1R2R3R4R5现在是58页\一共有138页\编辑于星期一结点的描述

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

结点是通过动态分配和释放来的实现，即需要时分配，不需要时释放。分别使用C语言提供的标准函数：malloc()，realloc()，sizeof()，free()。现在是59页\一共有138页\编辑于星期一动态分配

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

free(p);系统回收由指针变量p所指向的内存区。P必须是最近一次调用malloc函数时的返回值。现在是60页\一共有138页\编辑于星期一3)最常用的基本操作及其示意图⑴结点的赋值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL现在是61页\一共有138页\编辑于星期一⑵常见的指针操作①q=p;操作前pa……q操作后②q=p->next;bpa……操作前操作后qbpa……③p=p->next;bpa……操作前操作后pba……bpa……现在是62页\一共有138页\编辑于星期一操作前ypx……bqa…操作后ypx……bqa…④q->next=p;⑤q->next=p->next;操作前ypx……bqa…操作后ypx……bqa…现在是63页\一共有138页\编辑于星期一

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

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

4)建立单向链表现在是64页\一共有138页\编辑于星期一定义结构指针变量：

structnode*p,*p1,*head;

head：用来标志链表头；

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

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

(structnode*)malloc(sizeof(structnode))

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

/*输入10*/p=(structnode*)malloc(sizeof(structnode);datanextnext10第一结点第二结点headp1p链表建立的步骤：现在是67页\一共有138页\编辑于星期一第三步：将第一个结点与第二个结点连接起来

p1—＞next=p;10nextnextdata第一结点P1第二结点Pheadp1p链表建立的步骤：现在是68页\一共有138页\编辑于星期一第四步：给第二个结点成员data赋值并产生第三个结点p1=p;scanf(“%d”,&p->data);/*输入8*/p=(structnode*)malloc(sizeof(structnode);链表建立的步骤：10nextnext8第一结点第二结点p1第三结点pnext10第一结点headp18next第二结点p1datanext第三结点p第五步：将第二个结点与第三个结点连接起来

p1—＞next=p;nextdata现在是69页\一共有138页\编辑于星期一

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

p—>next＝NULL；它表示尾结点。现在是70页\一共有138页\编辑于星期一[例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)；/*输入第一个结点的数据成员*/现在是71页\一共有138页\编辑于星期一while(p->data!＝0)/*结束条件：当输入0时，退出循环*/{p1＝p；

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

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

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

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

……}现在是72页\一共有138页\编辑于星期一

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

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

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

p＝p->next；

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

1086420／*建链表时输入的数据*／链表数据成员是：1086420／*显示所建的链表*／现在是73页\一共有138页\编辑于星期一打印：没找到访问P开始输入iP=head,j=0i=j+1P=P－﹥nextP为空吗？i=j？返回返回YYNN5)单向链表的访问访问单向链表的第i个结点，应从表头开始检索．根据指针域的值逐个查直到找到第i个结点。现在是74页\一共有138页\编辑于星期一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中，返回*/现在是75页\一共有138页\编辑于星期一p＝p－＞next;/*结点指针指向下一结点*/}Pritnf(“\n序号超出范围”);return(0);}现在是76页\一共有138页\编辑于星期一

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

[例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）单向链表查找现在是77页\一共有138页\编辑于星期一p＝p－＞next;/*结点指针指向下一结点*/}Pritnf(“\n没找到该数据”);return(0);}现在是78页\一共有138页\编辑于星期一

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

e=q->data;delete(q);pq7）单向链表删除现在是79页\一共有138页\编辑于星期一[例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;}现在是80页\一共有138页\编辑于星期一p＝p－＞next;/*

如果p不是第i-1个结点，结点指针指向下一结点*/}Pritnf(“\n序号超出范围”);return(0);}现在是81页\一共有138页\编辑于星期一

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

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

<……ai-1,ai…>

改变为

<…ai-1,x,ai…>现在是82页\一共有138页\编辑于星期一

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

i

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

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

newnode

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

链表结点的插入过程：xnwenodeaitemp现在是84页\一共有138页\编辑于星期一(3)将第i-1个节点的指针指向新节点的地址，

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

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

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

i个节点的地址值赋给新结点指针newnode->next中，即newnode->next=tempxai-1xai-1ai现在是85页\一共有138页\编辑于星期一[例4－9]在下面所建链表的第i个节点之前插入一个新结点的程序如下：现在是86页\一共有138页\编辑于星期一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个结点*/现在是87页\一共有138页\编辑于星期一{/*将第i个结点地址存放在temp中*/temp=node->next;

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

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

return;}node=node->next;/*结点指针指向下一结点*/}}现在是88页\一共有138页\编辑于星期一注意

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

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

进栈

出栈

栈顶

an

…

a3

a2

栈底

a1

图4-13-

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

栈底:栈的操作:

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

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

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

4.3.1栈的基本概念现在是92页\一共有138页\编辑于星期一

进栈

出栈

栈顶

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)。现在是93页\一共有138页\编辑于星期一现在是94页\一共有138页\编辑于星期一现在是95页\一共有138页\编辑于星期一现在是96页\一共有138页\编辑于星期一现在是97页\一共有138页\编辑于星期一工程手册的数据处理

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

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

(2)数据库存储。将数表及线图(经离散化)中的数据按数据库中的规定进行文件结构化，如确定文件名、字段名、字段类型、字段宽度等，存放在数据库中，数据独立于应用程序，但又能为所有应用程序提供服务。现在是98页\一共有138页\编辑于星期一3．1数表的程序化3．1数表的程序化

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

程序化:本来就无表达公式，或一时难以找到原来公式，在设计手册或规范中，有各种形式的数表，从函数角度看，有单变量表，也有双变量及多变量表。现在是99页\一共有138页\编辑于星期一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．现在是100页\一共有138页\编辑于星期一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}；现在是101页\一共有138页\编辑于星期一2．平键和键槽的剖面尺寸现在是102页\一共有138页\编辑于星期一2．平键和键槽的剖面尺寸

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

，决定它位于表3—2轴径的哪个范围内，由此查出b，h，t，t1的值。轴径D是一个数值范围，编程时可将它的上限或下限记入一维数组内，表中其余列的值也放入各自的一维数组内。现在是103页\一共有138页\编辑于星期一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值*／存放表中^值*／现在是104页\一共有138页\编辑于星期一现在是105页\一共有138页\编辑于星期一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节)，即可求出实际的系数值。现在是106页\一共有138页\编辑于星期一4．齿轮传动工况系数KA(见表3—4)现在是107页\一共有138页\编辑于星期一决定工况系数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}}现在是108页\一共有138页\编辑于星期一图3—3齿轮传动工况系数KA查表流程图现在是109页\一共有138页\编辑于星期一表3-5轴肩圆角处理论应力集中系数αα现在是110页\一共有138页\编辑于星期一

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

线性插值

(两点插值）X

x1x2x3……….xn

Y

y1y2y3……….yn

列表函数现在是113页\一共有138页\编辑于星期一

线性插值C语言函数程序floatinter(floatx,floatx1,floatx2,floaty1,floaty2){floaty;y=y1+(y2-y1)/(x2-x1)*(x-x1);return(y);}现在是114页\一共有138页\编辑于星期一抛物线插值（三点插值）

现在是115页\一共有138页\编辑于星期一抛物线插值（三点插值）

现在是116页\一共有138页\编辑于星期一拉格朗日插值（多点插值）现在是117页\一共有138页\编辑于星期一3.3.3函数拟合

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

、拉格朗日插值曲线2、函数拟合曲线现在是118页\一共有138页\编辑于星期一最小二乘法函数拟合：曲线到各结点误差平方和最小。步骤：

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

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

3）用最小二乘法求出待定系数。误差函数：求导数：解方程求得方程系数a,b:例：直线段f(x)=a+bx的拟合：现在是119页\一共有138页\编辑于星期一指数函数最小二乘法拟合：

y=abx

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

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

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

y=abx现在是120页\一共有138页\编辑于星期一3.4

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

VisualFoxPro数据库管理系统

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

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

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

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

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

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

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

—

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

现在是122页\一共有138页\编辑于星期一数据库的应用实例

支承块（GB2235-80）数据库表文件现在是123页\一共有138页\编辑于星期一数据库的应用实例

表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

深沟球轴承现在是124页\一共有138页\编辑于星期一数据库结构定义：数据记录输入：

APPEND

或：EDIT

或：BROWSE轴承型号：内径d:外径D：宽度B：轴肩D1：孔径D3：动负荷：现在是125页\一共有138页\编辑于星期一现在是126页\一共有138页\编辑于星期一现在是127页\一共有138页\编辑于星期一现在是128页\一共有138页\编辑于星期一现在是129页\一共有138页\编辑于星期一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)。现在是130页\一共有138页\编辑于星期一

条件是给定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)现在是131页\一共有138页\编辑于星期一从图3—4可以看出，这种插值存在一定误差，但当表格中自变量间隔较小，而插值精度又不要求很高时，是可以满足使用要求的。线性插值程序的流程图见图3—5。符号说明如下：

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

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