中北大学机械CADCAM技术第二章机械CAD、CAM常用的数据结构

1.理解和掌握有关数据结构的相关概念；2.熟练掌握线形表存储结构和相关操作方法；3.掌握栈、队列、树数据结构的运算方法。第一节基本概念第二节线形表第三节栈、队列和数组第四节树结构本章内容《机械CAD/CAM》课程教案教学目的第二章机械CAD/CAM常用的数据结构第1节基本概念1.数据(data)是对客观事物的符号表示，是指所有能输入到计算机内并被计算机处理的符号的总称。2.数据元素(dataelement)是数据的基本单位，是数据这个集合中相对独立的个体。3.数据的逻辑结构(Thelogicalstructureofthedata)是指数据之间的逻辑关系。表学生成绩表学号姓名计算机导论高等数学大学物理平均成绩1102044401丁一809085851102044402马二756878741102044403张三908593891102044404李四708486801102044405王五82786675﹍﹍﹍﹍﹍﹍第1节基本概念4.数据的物理结构(Thephysicalstructureofthedata)是数据元素和它们之间的关系在计算机中的存储表示。计算机处理信息的最小单位叫做位(bit)，一个位表示一个二进制的数。若干位的组合形成一个位串(string)

。用一个位串表示一个数据元素，称这样的位串为一个结点(node)

。6.数据运算(dataoperation)是指对数据进行的各种操作。5.数据类型(datatype)是程序设计语言提供的变量类别。7.数据结构(datastructure)数据结构非线性结构数据存储结构数据运算数据逻辑结构线性结构线性表队列栈网状结构树结构链式存储顺序存储插入，删除，更新，检索，排序，数学运算，……第1节基本概念是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。

第2节线形表线性表——n(n≥0)个数据元素按前驱后继关系排成的有限序列。同一表中的数据元素的类型必须相同；除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继；如工资表、学生名册。线性表中数据元素的个数定义为线性表的长度。线性表的顺序存储结构

顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序依次存放。

假定每个数据元素占用L个存储单元，每个数据元素第1个单元的存储位置为该数据元素的存储位置，若第1个数据元素的存储化置为b，则第i个数据元素的存储位置为

Loc(ai)＝b十(i—1)×L第2节线形表第2节线形表线性表的顺序存储结构特点：1）有序性；2）均匀性。操作：1）建表；

2）访问；

3）修改；

4）删除；

5）插入。删除或插入运算时，数据移动量大，运算时间长。顺序表类型定义

#defineListSize100//表空间的大小可根据实际需要而定，这里假设为100typedefintDataType;//DataType的类型可根据实际情况而定，这里假设为int

typedefstruct{

DataTypedata[ListSize]；//向量data用于存放表结点

intlength；//当前的表长度

}SeqList；

顺序表上实现的基本运算

（1）表的初始化

voidInitList（SeqList*L）

{\\顺序表的初始化即将表的长度置为0

L-＞length=0；

}

（2）求表长

intListLength（SeqList*L）

{\\求表长只需返回L-＞length

returnL-＞length;

}

（3）取表中第i个结点

DataTypeGetNode（L，i）

{\\取表中第i个结点只需返回和L-＞data[i-1]即可

if(i<1||i>L-＞length-1)

Error("positionerror")；

returnL-＞data[i-1]；

}

线性表插入运算：第2节线形表线性表的链式存储结构特点：1）存储单元可以不连续、动态分配存储空间；

2）存储结点有两种域：数据域、指针域。单向链表双向链表循环链表单链表类型描述typedefcharDataType;//假设结点的数据域类型为字符

typedefstructnode{

//结点类型定义

DataTypedata;

//结点的数据域

structnode*next;//结点的指针域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

①生成结点变量的标准函数

p=(ListNode*)malloc(sizeof(ListNode))；

//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中

②释放结点变量空间的标准函数

free(p)；//释放p所指的结点变量空间

③结点分量的访问

利用结点变量的名字*p访问结点分量

方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next

④指针变量p和结点变量*p的关系

指针变量p的值——结点地址

结点变量*p的值——结点内容

(*p).data的值——p指针所指结点的data域的值

(*p).next的值——*p后继结点的地址

*((*p).next)——*p后继结点第2节线形表单向链表的操作操作：1）建表；

2）访问；

3）修改；

4）删除；

5）插入。第2节线形表建表链表插入操作运算步骤：①申请新结点存储空间；②将待插入元素M存放在新增结点数据域；③新增结点指针链接。

第2节线形表访问第2节线形表查找修改删除插入第2节线形表双向链表第2节线形表双向链表的操作1）建表第2节线形表建表第2节线形表查找修改删除插入第2节线形表链式存储相对于顺序存储的特点：(1)删除或插入运算速度快，因为删除或插入运算过程中数据并不移动；(2)无需事先分配存储空间，以免有些空间不能充分利用；(3)表的容量易于扩充；(4)按逻辑顺序进行查找的速度慢；(5)比相等长度的顺序存储多占用作为指针域的存储空间。线性表顺序存储与链式存储结构比较顺序存储：优点：结构均匀，便于数据元素访问和修改操作；不足：删除插入大量数据元素需移动，运算效率低。应用：多用于查找频繁、很少增删的场合。链式存储：优点：删除插入效率高，不需数据元素移动，不需事先分配存储空间，存储空间利用充分。不足：搜索效率低，需从头结点顺次搜寻。应用－多用于事先难以确定容量，频繁增、删场合。第3节栈、队列和数组栈栈的结构(1)栈的逻辑结构

——线形表：后进先出(2)栈的存储结构

——一般采用顺序存储结构

栈的定义

栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom).当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。栈：限定只能在表的一端进行插入和删除的特殊的线性表.设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；栈顶的当前位置由栈顶指针的位置指示器指示。栈底（bottom):不允许插入和删除的一端。进栈或入栈：栈的插入操作。出栈或退栈：栈的删除操作。a1a2….an进栈出栈栈顶栈底栈的定义空栈：没有元素的栈栈的特性：先进后出（LIFO），即只能在末端（栈顶）进行插、删的操作栈的定义栈中的几种基本操作：

1.设置空栈

初始化：initStack(S);清空：emptyStack(S);2.插入一个新的栈顶元素（进栈）:push(S,x);3.删除栈顶元素（出栈）:pop(S);4.读取栈顶元素:getTop(S);5.判空栈:stackEmpty(S);6.判满栈:stackFull(S);7.显示栈中元素：stackTraverse(S);

第3节栈、队列和数组

第3节栈、队列和数组

第3节栈、队列和数组栈的存储结构顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，一般用一维数组表示必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置链栈采用链表作为存储结构实现的必须设置一个栈顶指针永远指向栈顶栈的表示和实现一、顺序栈

栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的。栈的表示和实现需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。一、顺序栈a1a2top顺序栈的结构#defineStack_Size50typedefstruct{StackElemTypeelem[Stack_Size];

/*用一维数组存放自栈底到栈顶的数据元素*/inttop;/*附设一个位置指针top*/}SeqStack;一、顺序栈

设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–>elem[0]是栈底元素.那么：

进栈：s–>top加1；退栈：s–>top减1；

空栈：s–>top<0；栈满：s–>top=stacksize-1。上溢：当栈满时再做进栈运算必定产生的空间溢出;下溢：当栈空时再做退栈运算产生的溢出。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。一、顺序栈设数组S是一个顺序栈栈S的最大容量stacksize=4，初始状态top=－1

10S[4]2310basetop=top+1s[top]=xtop

10

25

30S[4]2310topbasex=s[top]top=top-1栈空10进栈30出栈S[4]2310Top=-1top栈满top=stacksize-1

10

25

30

40S[4]2310top=3baseS[4]2310Top=-1top进栈算法#defineStatck_Size100intPush(SeqStack*S,intx){if(S->top==Stack_Size－1)return0;S->top++;S->elem[S->top]=x;return(1);}a2a3a4987654321a10top一、顺序栈进栈算法#defineStatck_Size100intPush(SeqStack*S,intx){if(S->top==Stack_Size－1)return(0);

S->top++;S->elem[S->top]=x;return(1);}a2a3a4987654321a10top一、顺序栈进栈算法#defineStatck_Size100intPush(SeqStack*S,intx){if(S->top==Stack_Size－1)return(0);S->top++;

S->elem[S->top]=x;return(1);}a2a3a4987654321a10topx一、顺序栈出栈算法：

intpop(SeqStack*S,StackElementType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{*x=S->elem[S->top];/*返回出栈元素*/S->top--;return(1);}

}通过指针变量x，带回出栈元素a2a3a4987654321a10top一、顺序栈a2a3a4987654321a10topx出栈算法：

intpop(SeqStack*S,StackElementType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{

*x=S->elem[S->top];/*返回出栈元素*/

S->top--;return(1);}

}一、顺序栈为两个栈申请一个共享的一维数组空间S[M]将两个栈的栈底分别放在一维数组的两端，分别是0，M－1a1a2a3b5b4b3b2b10M－1top[0]top[1]一、顺序栈顺序栈的共享共享栈的结构定义a1a2a3b5b4b3b2b10M－1top[0]top[1]#defineM100typedefstruct{StackElementTypeelem[M];inttop[2];}DqStack;一、顺序栈a1a2a3b5b4b3b2b10M－1top[0]top[1]判空：

top[0]=-1; top[1]=M;判满：

top[0]+1==top[1];共享栈的操作共享栈的进栈操作intPush(DqStack*S,StackElementTypex,inti){if(S->top[0]+1==S->top[1])return(0);switch(i){case0:S->top[0]++;S->elem[S->top[0]]=x;break;case1:S->top[1]++;S->elem[S->top[1]]=x;break;default:return(0);}return(1);}共享栈的出栈操作intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S->top[0]==-1)return(0);*x=S->elem[S->top[0]];S->top[0]--;break;case1:if(S->top[1]==M)return(0);*x=S->elem[S->top[1]];S->top[1]--;break;default:return(0);}return(1);}二、链栈

栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。

a1

an∧top栈底

用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。链栈的类型说明如下：typedefstructLnode{intdata；structLnode

next；}Lnode，

LinkStack；top头指针永远指向头结点二、链栈进栈算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}a1a2an∧basetop栈s进栈元素e二、链栈进栈算法intPush(LinkStacktop,StackElementTypee){Lnode*p;

p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}

Pa1a2an∧basetop二、链栈进栈算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}

ePa1a2an∧basetop二、链栈进栈算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}

ePa1a2an∧basetop进栈算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;

p->next=top->next;

top->next=p;return(1);}

ePa1a2an∧basetop二、链栈出栈算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}栈s指针变量带回出栈元素的值a1a2an∧basetop二、链栈tempa1a2an∧basetop出栈算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;

temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}二、链栈tempa1a2an∧basetop出栈算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);

top->next=temp->next;*x=temp->data;free(temp);}二、链栈tempa1a2an∧basetop出栈算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}xa1二、链栈tempa1a2an∧basetop出栈算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}xa1二、链栈队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。2.3队列的定义队列（Queue）：限定在表一端插入，在另一端删除的“先进先出”线性表。a1a2……ak……an-1an入队出队队列数据结构循环队列第3节栈、队列和数组

第3节栈、队列和数组队列

第3节栈、队列和数组队列尾追头为满头追尾为空尾指‘+1’判断下图是队列的示意图：出队入队队头队尾a1a2…an

队尾：在队列中，允许插入的一端队头：在队列中，允许删除的一端队列的主要运算设置一个空队列；插入一个新的队尾元素，称为进队；删除队头元素，称为出队；读取队头元素；等2.3队列的定义队列的存储结构（1）顺序存储结构(a)线性队列(b)循环队列（2）链式存储结构队列的表示和实现队列的类型定义：#defineMAXSIZE50typedefstruct{QueueElementTypeelem[MAXSIZE];intfront;intrear;}SeqQueue;e1,e2出队，e4入队队满e1e2e3

(b)rearfronte1,e2,e3入队队空时，令rear=front=0，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素的位置，而尾指针始终指向队尾元素后一个位置rear=front=0(队空)front

3210(a)rearrear=4(c)e3e4front队列的顺序存储和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”（假溢出）现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。队列的顺序存储为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：

if(i+1==QueueSize)i=0;elsei++;利用模运算可简化为：i=(i+1)%QueueSize队列的顺序存储显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。

解决此问题的方法至少有三种：其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；队列的顺序存储其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。

#defineQueueSize100typedefstruct{Queuedatatypedata[queuesize]intfront，rear;intlen;}sqqueue;队列的顺序存储（1）置空队voidinitqueue(sqqueue*q){q–>front=q–>rear=-1;q–>len=0;}（2）判断队空intqueueempty(sqqueue*q){returnq–>len==0;}（3）判断队满intqueuefull(sqqueue*q){returnq–>len==queuesize;}队列的顺序存储（4）入队voidinqueue(sqqueue*q,datatypex){if(queuefull(q)){printf(“queueoverflow”);return;}q–>len++;q–>data[q–>rear]=x;

q–>rear=(q–>rear+1)%queuesize;}队列的顺序存储（5）出队queuedatatypedequeue(sqqueue*q){datatypetemp;if(queueempty(q)){printf(“queueunderflow”);return;}temp=q–>data[q–>front];q–>len--;q–>front=(q–>front+1)%queuesize;returntemp;}队列的顺序存储（6）取头元素queuedatatypequeuefront(sqqueue*q){if(queueempty(q)){printf(“queueisempty.”);return(0);}returnq–>data[q–>front];}队列的顺序存储区分队列空与满另一种方法少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满（注意：rear所指的单元始终为空）；队列的顺序存储循环队列

rearfront

0123(3)队空队满条件：(Q.rear+1)%MAX=Q.front注：实际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。(1)一般情况

rearfront0123e4e3

(2)队满fronte3

e40123reare5队列的顺序存储#defineMAXSIZE50typedefstruct{QueueElementTypeelement[MAXSIZE];intfront;intrear;}SeqQueue;注意事项：1、出队时，头指针的变化为front=(front+1)modMAXSIZE2、入队时，尾指针的变化为rear=(rear+1)modMAXSIZE3、凡是遇到指针要发生变化，头和尾指针的有效范围为[0,MAXSIZE-1]，所以用取模运算来保证头尾指针的取值循环队列的类型定义循环队列中加入一个元素的算法：

intEnQueue(SeqQueue*Q,intx)Q为已有的循环队列将插入的值循环队列循环队列中加入一个元素的算法：intEnQueue(SeqQueue*Q,intx){if((Q->rear+1)%MAXSIZE==Q->front)return(0);else{Q->rear=x;Q->rear=(Q->rear+1)%MAXSIZE;return(1);}}

rearfront0123e4e3rearX循环队列循环队列中删除一个元素的算法：intDeQueue(SeqQueue*Q，int*py)已有的循环队列返回删除的值的地址循环队列循环队列中删除一个元素的算法：intDeQueue(SeqQueue*Q，int*py){if(Q->rear==Q->front)return(0);else{*py=Q[Q->front];Q->front=(Q->front+1)%MAXSIZE;return(1);}}

rearfront0123e4e3front循环队列链式存储结构ana2a1

Q.frontQ.rear队头队尾typedefstructNode{QueueElementTypedata;structNode*next;}LinkQueueNode;/*结点的定义*/typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;/*队列的定义*/注意：队头永远指向头结点，队尾永远指向最后一个元素。3.3.2队列的表示和实现

e^a1a2anQ.frontQ.rear

链队列添加操作Q.rearnewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));newNode->data=e;newNode->next=0;Q->rear->next=newNode;Q->rear=newNode;newNodeana2a1

ana2a1

Q.frontQ.rear删除一个元素链队列删除操作Q.frontQ.rearQ.front->next=Q.front->next->next;设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，队Q的状态是（）。（1）删除队Q中的元素，将删除的元素插入栈S，直到队Q为空。（2）依次将栈S中的元素插入队Q，直到栈S为空。(a)abcd(b)acbd(c)dcba(d)bacddcbafrontreartop队Q栈Sfrontreardcbatop队Q栈Sabcdfrontreartop队Q栈Sc设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是（） A）A，B，C，D B）D，C，B，A C）A，C，D，B D）D，A，B，C实现A的过程：Push(A)、Pop(A)、Push(B)、Pop(B)、Push(C)、Pop(C)、Push(D)、Pop(D)实现B的过程：Push(A)、Push(B)、Push(C)、Push(D)、Pop(A)、Pop(B)、Pop(C)、Pop(D)实现C的过程：Push(A)、Pop(A)、Push(B)、Push(C)、Pop(C)、Push(D)、Pop(D)、Pop(B)D

第3节栈、队列和数组数组树结构（层次结构）：除根结点之外，所有结点仅有一个直接前驱。

第4节树结构结点

结点的度树的度

叶子结点分支结点子结点与父结点结点层数树的深度

森林

一个结点具有的子树个数树中最大结点的度，图示树的度为4