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

1、1. 理解和掌握有关数据结构的相关概念；理解和掌握有关数据结构的相关概念；2. 熟练掌握线形表存储结构和相关操作方法；熟练掌握线形表存储结构和相关操作方法；3. 掌握栈、队列、树数据结构的运算方法。掌握栈、队列、树数据结构的运算方法。第一节第一节 基本概念基本概念第二节第二节 线形表线形表第三节第三节 栈、队列和数组栈、队列和数组第四节第四节 树结构树结构本本章章内内容容机械CAD/CAM课程教案教教学学目目的的1. 数据数据(data) 是对客观事物的符号表示，是指所有能输入到计算是对客观事物的符号表示，是指所有能输入到计算 机内并被计算机处理的符号的总称。机内并被计算机处理的符号的总称。2

2、. 数据元素数据元素(data element) 是数据的基本单位，是数据这个集合中相对独立的个体。是数据的基本单位，是数据这个集合中相对独立的个体。3. 数据的逻辑结构数据的逻辑结构(The logical structure of the data) 是指数据之间的逻辑关系。是指数据之间的逻辑关系。表 学生成绩表学号姓名计算机导论高等数学大学物理平均成绩1102044401丁一809085851102044402马二756878741102044403张三908593891102044404李四708486801102044405王五827866754.数据的物理结构数据的物理结构(The

3、 physical structure of the data ) 是数据元素和它们之间的关系在计算机中的存储表示。是数据元素和它们之间的关系在计算机中的存储表示。 计算机处理信息的最小单位叫做计算机处理信息的最小单位叫做位位(bit)，一个位表示一个二，一个位表示一个二进制的数。进制的数。 若干位的组合形成一个位若干位的组合形成一个位串串(string) 。用一个位串表示一个数。用一个位串表示一个数据元素，称这样的位串为一个据元素，称这样的位串为一个结点结点(node) 。6. 数据运算数据运算(data operation) 是指对数据进行的各种操作。是指对数据进行的各种操作。5. 数据类

4、型数据类型(data type) 是程序设计语言提供的变量类别。是程序设计语言提供的变量类别。7.数据结构数据结构(data structure)数据结构非线性结构数据存储结构数据运算数据逻辑结构线性结构线性表队列栈网状结构树结构链式存储顺序存储 插入， 删除， 更新， 检索， 排序， 数学运算， 是按某种逻辑结构组织起来，按一定的存储表示方是按某种逻辑结构组织起来，按一定的存储表示方式把组织好的数据存储到计算机中，并对之定义一系列式把组织好的数据存储到计算机中，并对之定义一系列操作运算的数据的集合。操作运算的数据的集合。 p线性表线性表n(n0)个数据元素按前驱后继关系个数据元素按前驱后继关

5、系排成的有限序列。排成的有限序列。同一表中的数据元素的类型必须相同；同一表中的数据元素的类型必须相同；除了第一个和最后一个数据元素外，每个数据元除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继；素有且只有一个直接前趋，有且只有一个直接后继；如工资表、学生名册。如工资表、学生名册。线性表中数据元素的个数定义为线性表的长度。线性表中数据元素的个数定义为线性表的长度。p线性表的顺序存储结构线性表的顺序存储结构 顺序存储就是用一组连续的存储单元，按照数据元素顺序存储就是用一组连续的存储单元，按照数据元素的逻辑顺序的逻辑顺序依次存放依次存放。 假定每个数据元素占用假

6、定每个数据元素占用L个存储单元，每个数据元素个存储单元，每个数据元素第第1个单元的存储位置为该数据元素的存储位置，若第个单元的存储位置为该数据元素的存储位置，若第1个个数据元素的存储化置为数据元素的存储化置为b，则第，则第i个数据元素的存储位置为个数据元素的存储位置为 Loc(ai)b十十(i1)Lp线性表的顺序存储结构线性表的顺序存储结构特点：特点：1）有序性；）有序性；2）均匀性。）均匀性。操作：操作：1）建表；）建表； 2）访问；）访问； 3）修改；）修改； 4）删除；）删除； 5）插入。）插入。删除或插入删除或插入运算时，数运算时，数据移动量大，据移动量大，运算时间长。运算时间长。顺序

7、表类型定义顺序表类型定义#defineListSize100/表空间的大小可根据实际需要而定，这里假设为100typedefintDataType;/DataType的类型可根据实际情况而定，这里假设为inttypedefstructDataTypedataListSize；/向量data用于存放表结点intlength；/当前的表长度SeqList； 顺序表上实现的基本运算顺序表上实现的基本运算（1）表的初始化voidInitList（SeqList*L）顺序表的初始化即将表的长度置为0L-length=0；（2）求表长intListLength（SeqList*L）求表长只需返回L-len

8、gthreturnL-length;（3）取表中第i个结点DataTypeGetNode（L，i）取表中第i个结点只需返回和L-datai-1即可if(iL-length-1)Error(positionerror)；returnL-datai-1；线性表插入运算线性表插入运算：p线性表的链式存储结构线性表的链式存储结构特点：特点：1）存储单元可以不连续、动态分配存储空间；）存储单元可以不连续、动态分配存储空间； 2）存储结点有两种域：数据域、指针域。）存储结点有两种域：数据域、指针域。单向链表单向链表 双向链表双向链表循环链表循环链表单链表类型描述单链表类型描述typedefcharData

9、Type;/假设结点的数据域类型为字符typedefstructnode/结点类型定义DataTypedata;/结点的数据域structnode*next;/结点的指针域ListNode;typedefListNode*LinkList;ListNode*p;LinkListhead; 生成结点变量的标准函数生成结点变量的标准函数 p=(ListNode*)malloc(sizeof(ListNode)；/函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数释放结点变量空间的标准函数 free(p)；/释放p所指的结点变量空间

10、结点分量的访问结点分量的访问 利用结点变量的名字*p访问结点分量方法一：(*p).data和(*p).next方法二：p-data和p-next 指针变量指针变量p和结点变量和结点变量*p的关系的关系 指针变量p的值结点地址结点变量*p的值结点内容(*p).data的值p指针所指结点的data域的值(*p).next的值*p后继结点的地址*(*p).next)*p后继结点p单向链表的操作单向链表的操作操作：操作：1）建表；）建表； 2）访问；）访问； 3）修改；）修改； 4）删除；）删除； 5）插入。）插入。p建表建表链表插入操作运算步骤：申请新结点存储空间；将待插入元素M存放在新增结点数据域

11、；新增结点指针链接。 p访问访问p查找查找p修改修改p删除删除p插入插入p双向链表双向链表p双向链表的操作双向链表的操作1）建表）建表p建表建表p查找查找p修改修改p删除删除p插入插入p链式存储相对于顺序存储的特点：链式存储相对于顺序存储的特点：(1)删除或插入运算速度快，因为删除或插入运算过程中数删除或插入运算速度快，因为删除或插入运算过程中数据并不移动；据并不移动；(2)无需事先分配存储空间，以免有些空间不能充分利用；无需事先分配存储空间，以免有些空间不能充分利用；(3)表的容量易于扩充；表的容量易于扩充；(4)按逻辑顺序进行查找的速度慢；按逻辑顺序进行查找的速度慢；(5)比相等长度的顺序

12、存储多占用作为指针域的存储空间。比相等长度的顺序存储多占用作为指针域的存储空间。线性表线性表顺序存储与顺序存储与链式链式存储结构比较存储结构比较顺序存储顺序存储：优点：结构均匀，便于数据元素访问和修改操作；不足：删除插入大量数据元素需移动，运算效率低。应用：多用于查找频繁、很少增删的场合。链式存储链式存储：优点：删除插入效率高，不需数据元素移动，不需 事先分配存储空间，存储空间利用充分。不足：搜索效率低，需从头结点顺次搜寻。 应用多用于事先难以确定容量，频繁增、删场合。p栈栈p栈的结构栈的结构(1)栈的逻辑结构栈的逻辑结构 线形表：后进先出线形表：后进先出(2)栈的存储结构栈的存储结构 一般采

13、用顺序存储结构一般采用顺序存储结构 栈的定义栈的定义 栈栈(Stack)(Stack)是限制在表的一端进行插入和删除运算是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶的线性表，通常称插入、删除的这一端为栈顶(Top)(Top)，另一端为栈底另一端为栈底(Bottom).(Bottom).当表中没有元素时称为当表中没有元素时称为空栈空栈。 假设栈假设栈S=(aS=(a1 1，a a2 2，a a3 3，aan n) )，则，则a a1 1称为栈底元素，称为栈底元素，a an n为栈为栈顶元素顶元素。栈中元素按。栈中元素按a a1 1，a a2 2，a a3 3，a a

14、n n的次序进的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为修改是按后进先出的原则进行的。因此，栈称为后进先后进先出表（出表（LIFOLIFO）。栈：栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表. . 设栈设栈s=s=（a a1 1，a a2 2，. . . ,a. . . ,ai i，. . . . . . ，a an n），其中其中a a1 1是是栈底栈底元素，元素， a an n是是栈顶栈顶元素。元素。栈顶（栈顶（top)top)：允许插

15、入和删除的一端；允许插入和删除的一端； 栈顶的当前位置由栈顶指针的位置指示器指示。栈顶的当前位置由栈顶指针的位置指示器指示。栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。进栈或入栈：进栈或入栈：栈的插入操作。栈的插入操作。出栈或退栈：出栈或退栈：栈的删除操作。栈的删除操作。 a1 a2 . an进栈进栈出栈出栈栈顶栈顶栈底栈底栈的定义栈的定义空栈：空栈：没有元素的栈没有元素的栈栈的特性：栈的特性：l先进后出（先进后出（LIFOLIFO），即只能在末端（栈顶）进），即只能在末端（栈顶）进行插、删的操作行插、删的操作栈的定义栈的定义栈中的几种基本操作：

16、栈中的几种基本操作： 1.1.设置空栈设置空栈 初始化：初始化：initStack(S);initStack(S); 清空：清空：emptyStack (S);emptyStack (S); 2. 2.插入一个新的栈顶元素插入一个新的栈顶元素（进栈）（进栈）:push(S,x);:push(S,x); 3. 3.删除栈顶元素删除栈顶元素（出栈）（出栈）: pop(S);: pop(S); 4. 4.读取栈顶元素读取栈顶元素:getTop(S);:getTop(S); 5. 5.判空栈判空栈:stackEmpty(S);:stackEmpty(S); 6. 6.判满栈判满栈:stackFull(

17、S);:stackFull(S); 7. 7.显示栈中元素显示栈中元素：stackTraverse(S);stackTraverse(S); 栈的存储结构栈的存储结构顺序栈顺序栈l利用一组地址连续的存储单元依次存放自栈底到利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，一般用栈顶的数据元素，一般用一维数组一维数组表示表示l必须附设一个位置指针必须附设一个位置指针toptop（栈顶指针）来动态（栈顶指针）来动态地指示地指示栈栈顶元素顶元素在顺序栈中的位置在顺序栈中的位置链栈链栈l采用链表作为存储结构实现的采用链表作为存储结构实现的l必须设置一个栈顶指针永远指向栈顶必须设置一个栈顶指针永

18、远指向栈顶栈的表示和实现栈的表示和实现一、顺序栈一、顺序栈 栈的顺序存储结构简称为栈的顺序存储结构简称为顺序栈顺序栈，它，它是运算受限的线性表。因此，可用数组来是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的实现顺序栈。因为栈底位置是固定不变的, ,所以可以将栈底位置设置在数组的两端的所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退任何一个端点；栈顶位置是随着进栈和退栈操作而变化的。栈操作而变化的。栈的表示和实现栈的表示和实现 需用一个整型变量需用一个整型变量top来指示当前栈顶的位来指示当前栈顶的位置，通常称置，通常称top为为栈顶指针栈顶指针

19、。因此，。因此，顺序栈的顺序栈的类型定义只需将顺序表的类型定义中的长度类型定义只需将顺序表的类型定义中的长度属性改为属性改为top即可。即可。一、顺序栈一、顺序栈 a1 a2 top顺序栈的结构顺序栈的结构#define Stack_Size 50#define Stack_Size 50typedef structtypedef structStackElemType elemStack_Size;StackElemType elemStack_Size; / /* *用一维数组存放自栈底到栈顶的数据元素用一维数组存放自栈底到栈顶的数据元素* */ / int top; int top; /

20、*附设一个位置指针附设一个位置指针top*/SeqStack;SeqStack;一、顺序栈一、顺序栈 设设S S是是SeqStackSeqStack类型的指针变量。若栈底位置在向量类型的指针变量。若栈底位置在向量的低端，即的低端，即s selem0elem0是栈底元素是栈底元素. . 那么：那么： 进栈：进栈：s stoptop加加1 1；退栈：退栈：s stop top 减减1 1； 空栈：空栈：s stoptoptop =stacksize-1top =stacksize-1。 上溢：上溢：当栈满时再做进栈运算必定产生的空间溢出当栈满时再做进栈运算必定产生的空间溢出; ;下溢：下溢：当栈空

21、当栈空时再做退栈运算产生的溢出。时再做退栈运算产生的溢出。 上溢是一种出错状态，应该设法避免之；下溢则可能上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。空栈，所以下溢常常用来作为程序控制转移的条件。一、顺序栈一、顺序栈设数组设数组S S是一个顺序栈是一个顺序栈栈栈S S的最大容量的最大容量stacksize=4 stacksize=4 ，初始状态，初始状态top=top=1 1 10S42310basetop=top+1stop=xtop 10 25

22、 30S42310topbasex=stoptop=top-1栈空栈空1010进栈进栈3030出出栈栈S42310Top=-1top栈满栈满 top=stacksize-1 10 25 30 40S42310top=3baseS42310Top=-1top进栈算法进栈算法#define Statck_Size 100#define Statck_Size 100int Push(SeqStack int Push(SeqStack * *S, int x)S, int x) if(S-top=Stack_Size if(S-top=Stack_Size1)1) return 0; return

23、 0; S-top+; S-top+; S-elemS-top=x; S-elemS-top=x; return(1); return(1); a2 a3 a4987654321 a10top一、顺序栈一、顺序栈进栈算法进栈算法#define Statck_Size 100#define Statck_Size 100int Push(SeqStack int Push(SeqStack * *S, int x)S, int x) if(S-top=Stack_Size if(S-top=Stack_Size1)1) return(0); return(0); S-top+;S-top+; S

24、-elemS-top=x; S-elemS-top=x; return(1); return(1); a2 a3 a4987654321 a10top一、顺序栈一、顺序栈进栈算法进栈算法#define Statck_Size 100#define Statck_Size 100int Push(SeqStack int Push(SeqStack * *S, int x)S, int x) if(S-top=Stack_Size if(S-top=Stack_Size1)1) return(0); return(0); S-top+; S-top+; S-elemS-top=x;S-elemS

25、-top=x; return(1); return(1); a2 a3 a4987654321 a10topx一、顺序栈一、顺序栈出栈算法出栈算法： i n t p o p ( S e q S t a c k * S , StackElementType *x) if(S-top= =1) p r i n t f ( “ s t a c k e m p t y ” ) ; return(0); else *x=S-elemS-top; /*返回出返回出栈元素栈元素*/ S-top- -; return(1); 通过指针变量通过指针变量x x，带回出栈元素，带回出栈元素 a2 a3 a49876

26、54321 a10top一、顺序栈一、顺序栈 a2 a3 a4987654321 a10topx出栈算法：出栈算法： i n t p o p ( S e q S t a c k * S , StackElementType *x) if(S-top= =1) p r i n t f ( “ s t a c k e m p t y ” ) ; return(0); else *x=S-elemS-top; /*返回出返回出栈元素栈元素*/ S-top- -; return(1); 一、顺序栈一、顺序栈为两个栈申请一个共享的一维数组空间为两个栈申请一个共享的一维数组空间SMSM将两个栈的栈底分别放

27、在一维数组的两端，分别是将两个栈的栈底分别放在一维数组的两端，分别是0 0，M M1 1a a1 1 a a2 2 a a3 3 b b5 5 b b4 4 b b3 3 b b2 2 b b1 10 0M M1 1top0top0top1top1一、顺序栈一、顺序栈顺序栈的共享顺序栈的共享共享栈的结构定义共享栈的结构定义a a1 1 a a2 2 a a3 3 b b5 5 b b4 4 b b3 3 b b2 2 b b1 10 0M M1 1top0top0top1top1#define M 100#define M 100typedef structtypedef structStac

28、kElementType elemM;StackElementType elemM; int top2; int top2;DqStack;DqStack;一、顺序栈一、顺序栈a a1 1 a a2 2 a a3 3 b b5 5 b b4 4 b b3 3 b b2 2 b b1 10 0M M1 1top0top0top1top1判空：判空：top0=-1;top0=-1;top1=M;top1=M;判满：判满：top0+1= =top1;top0+1= =top1;共享栈的操作共享栈的操作共享栈的进栈操作共享栈的进栈操作int Push(DqStack int Push(DqStack

29、* *S,StackElementType x,int i)S,StackElementType x,int i)if(S-top0+1= =S-top1) return(0);if(S-top0+1= =S-top1) return(0); switch(i) switch(i) case 0: case 0: S-top0+; S-top0+; S-elemS-top0=x; break; S-elemS-top0=x; break; case 1: case 1: S-top1+; S-top1+; S-elemS-top1=x; break; S-elemS-top1=x; break

30、; default: default: return(0); return(0); return(1); return(1);共享栈的出栈操作共享栈的出栈操作int Pop(DqStack int Pop(DqStack * *S,StackElementType S,StackElementType * *x,int i)x,int i)switch(i)switch(i) case 0: case 0: if(S-top0= =-1) return(0); if(S-top0= =-1) return(0); * *x=S-elemS-top0;x=S-elemS-top0; S-top0

31、- -; break; S-top0- -; break; case 1: case 1: if(S-top1= =M) return(0); if(S-top1= =M) return(0); * *x=S-elemS-top1;x=S-elemS-top1; S-top1- -; break; S-top1- -; break; default: default: return(0); return(0); return(1); return(1);二、链栈二、链栈栈的链式存储结构称为栈的链式存储结构称为链栈链栈，它是运算，它是运算受限的单链表，插入和删除操作仅限制在表头受限的单链表，插入

32、和删除操作仅限制在表头位置上进行位置上进行.由于只能在链表头部进行操作，由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。顶指针就是链表的头指针。 a1 antop栈底栈底 用指针来实现的栈叫链栈。栈的容量事先不用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。能估计时采用这种存储结构。链栈的类型说明如下：链栈的类型说明如下：typedef struct Lnodetypedef struct Lnode int data int data； struct Lnode struct Lnode ne

33、xtnext； LnodeLnode， LinkStackLinkStack；toptop头指针永头指针永远指向头结点远指向头结点二、链栈二、链栈进栈算法进栈算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);a1a2anbasetop栈栈 s s进栈元素进栈元素e e二、链栈二、链栈进栈算法进栈算法i n t P u s h ( L

34、 i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1); Pa1a2anbasetop二、链栈二、链栈进栈算法进栈算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-nex

35、t; top-next=p; return (1); ePa1a2anbasetop二、链栈二、链栈进栈算法进栈算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1); ePa1a2anbasetop进栈算法进栈算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)L

36、node *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1); ePa1a2anbasetop二、链栈二、链栈出栈算法出栈算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);栈栈 s s指针变量带回指针

37、变量带回出栈元素的值出栈元素的值a1a2anbasetop二、链栈二、链栈temptempa1a2anbasetop出栈算法出栈算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);二、链栈二、链栈temptempa1a2anbasetop出栈算法出栈算法i n t P o p ( L i n k S t a c k t o p

38、 , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);二、链栈二、链栈temptempa1a2anbasetop出栈算法出栈算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=te

39、mp-data; free(temp);x xa1二、链栈二、链栈temptempa1a2anbasetop出栈算法出栈算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);x xa1二、链栈二、链栈 队列队列(Queue)(Queue)也是一种运算受限的线性表。它也是一种运算受限的线性表。它只允许在只允许在表的一端进行插入，而

40、在另一端进行删除。表的一端进行插入，而在另一端进行删除。允许删除的一端允许删除的一端称为称为队头队头(front)(front)，允许插入的一端称为，允许插入的一端称为队尾队尾(rear)(rear)。例如：排队购物。操作系统中的作业排队。例如：排队购物。操作系统中的作业排队。 先进入队列的成员总是先离开队列。因此队列亦称作先进入队列的成员总是先离开队列。因此队列亦称作先先进先出进先出(First In First Out)(First In First Out)的线性表的线性表，简称，简称FIFOFIFO表。表。当队列中没有元素时称为当队列中没有元素时称为空队列空队列。在空队列中依次加入。在

41、空队列中依次加入元素元素a a1 1,a,a2 2,a,an n之后，之后，a a1 1是队头元素，是队头元素，a an n是队尾元素。显然退是队尾元素。显然退出队列的次序也只能是出队列的次序也只能是a a1 1,a,a2 2,a,an n ，也就是说队列的修改是，也就是说队列的修改是依依先进先出先进先出的原则进行的。的原则进行的。2.3 2.3 队列的定义队列的定义队列（队列（Queue）：限定在表一端插入，在另一端删除的“先进先出”线性表。a1a2akan-1an入队出队队列数据结构队列数据结构循环循环队列队列 队列队列 队列队列尾追头为满尾追头为满头追尾为空头追尾为空尾指尾指+1判判断断

42、下图是队列的示意图：下图是队列的示意图：出队出队入队入队队头队头队尾队尾 a a1 1a a2 2a an nn队尾：在队列中，允许队尾：在队列中，允许插入插入的一端的一端n队头：在队列中，允许队头：在队列中，允许删除删除的一端的一端队列的主要运算队列的主要运算设置一个空队列；设置一个空队列；插入一个新的队尾元素，称为进队；插入一个新的队尾元素，称为进队；删除队头元素，称为出队；删除队头元素，称为出队；读取队头元素；等读取队头元素；等2.3 2.3 队列的定义队列的定义队列的存储结构队列的存储结构（1 1）顺序存储结构）顺序存储结构(a) (a) 线性队列线性队列 (b) (b) 循环队列循环

43、队列（2 2）链式存储结构）链式存储结构队列的表示和实现队列的表示和实现队列的类型定义：队列的类型定义：#define MAXSIZE 50#define MAXSIZE 50typedef structtypedef structQueueElementType elem MAXSIZE;QueueElementType elem MAXSIZE; int front;int rear; int front;int rear;SeqQueue;SeqQueue;e1,e2e1,e2出队，出队，e4e4入队队满入队队满 e1 e2 e3 (b)rearfronte1,e2,e3e1,e2,e3

44、入队入队 队空时，队空时， 令令rear=front=0rear=front=0，当有新元素入队时，尾指针加当有新元素入队时，尾指针加1 1，当有元素出队时，头指针加当有元素出队时，头指针加1 1。故。故在非空队列中，在非空队列中，头指针头指针始终指向始终指向队队头元素的位置头元素的位置，而，而尾指针尾指针始终指向始终指向队尾元素后一个位置队尾元素后一个位置rear=front=0(rear=front=0(队空队空) )front 3 2 1 0 (a)rearrear=4 (c) e3 e4front队列的顺序存储队列的顺序存储 和栈类似，队列中亦有上溢和下溢现象。和栈类似，队列中亦有上溢

45、和下溢现象。此外，顺序队列中还存在此外，顺序队列中还存在“假上溢假上溢”（假溢出假溢出）现象。因为在入队和出队的操作中，头尾指针现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。该现象称为假上溢。队列的顺序存储队列的顺序存储 为充分利用向量空间。克服上述假上溢现象的方法

46、是为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列为循环向量，存储在其中的队列称为循环队列Circular Circular Queue)Queue)。在循环队列中进行出队、入队操作时，头尾指。在循环队列中进行出队、入队操作时，头尾指针仍要加针仍要加1 1，朝前移动。，朝前移动。 只不过当头尾指针指向向量上界（只不过当头尾指针指向向量上界（QueueSize-1QueueSize-1）时，）时，其加其加1 1操作的结果是指向向量的下界操作的结果是指向向量的下界0

47、 0。这种循环意义下的加这种循环意义下的加1 1操作可以描述为：操作可以描述为： if(i+1=QueueSize) i=0;if(i+1=QueueSize) i=0; else i+; else i+;利用模运算可简化为：利用模运算可简化为： i=(i+1)%QueueSizei=(i+1)%QueueSize队列的顺序存储队列的顺序存储 显然，因为循环队列元素的空间可以被利用，除非向量显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是些简单的应用外，真

48、正实用的顺序队列是循环队列循环队列。 如图所示：由于入队时尾指针向前追赶头指针，出队时如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过因此，我们无法通过front=rearfront=rear来判断队列来判断队列“空空”还是还是“满满”。 解决此问题的方法至少有三种解决此问题的方法至少有三种： 其一是另设一个布尔变量以区别队列的空和满；其二是其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义少用一个元素的空间，约定入队前，测

49、试尾指针在循环意义下加下加1 1后是否等于头指针，若相等则认为队满（注意：后是否等于头指针，若相等则认为队满（注意：rearrear所指的单元始终为空）；所指的单元始终为空）；队列的顺序存储队列的顺序存储 其三是其三是使用一个计数器记录队列中元素的总数使用一个计数器记录队列中元素的总数（实际（实际上是队列长度）。上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。为此先给出循环队列的类型定义。 #define QueueSize 100 typedef struct Queuedatatype dat

50、aqueuesize int front， rear; int len; sqqueue;队列的顺序存储队列的顺序存储（1）置空队置空队 void initqueue(sqqueue *q) qfront=qrear=-1; qlen=0; （2）判断队空判断队空 int queueempty(sqqueue *q) return qlen=0; （3）判断队满判断队满 int queuefull(sqqueue *q) return qlen=queuesize; 队列的顺序存储队列的顺序存储（4 4）入队入队 void inqueue(sqqueue void inqueue(sqqueu

51、e * *q,datatype x)q,datatype x) if(queuefull(q) if(queuefull(q) printf(“queue overflow”); printf(“queue overflow”); return; return; q qlen+;len+; q qdataqdataqrear=x;rear=x; q qrear=(qrear=(qrear+1)%queuesize;rear+1)%queuesize; 队列的顺序存储队列的顺序存储（5 5）出队出队 queuedatatype dequeue(sqqueue queuedatatype dequ

52、eue(sqqueue * *q)q) datatype temp; datatype temp; if(queueempty(q) if(queueempty(q) printf(“queue underflow”); printf(“queue underflow”); return; return; temp=q temp=qdataqdataqfront;front; q qlen-; len-; q qfront=(qfront=(qfront+1)%queuesize;front+1)%queuesize; return temp; return temp; 队列的顺序存储队列的顺

53、序存储（6 6）取头元素取头元素 queuedatatype queuefront(sqqueue queuedatatype queuefront(sqqueue * *q)q) if(queueempty(q) if(queueempty(q) printf(“queue is empty.”); printf(“queue is empty.”); return(0); return(0); return q return qdataqdataqfront;front; 队列的顺序存储队列的顺序存储区分队列空与满另一种方法区分队列空与满另一种方法 少用一个元素的空间，约定入队前，测试尾指

54、针在少用一个元素的空间，约定入队前，测试尾指针在循环意义下加循环意义下加1 1后是否等于头指针后是否等于头指针, ,若相等则认为队满若相等则认为队满（注意：（注意：rearrear所指的单元始终为空）；所指的单元始终为空）；队列的顺序存储队列的顺序存储循环队列循环队列 rear front 0 1 2 3(3) 队空队空队满条件队满条件：(Q.rear+1)%MAX=Q.front注：实际上为了避免与队空标注：实际上为了避免与队空标志冲突，还留有一个空间。志冲突，还留有一个空间。将头尾连接成将头尾连接成一个环，形成一个环，形成循环队列。循环队列。(1)1)一般情况一般情况 rear front

55、 0 1 2 3e4e3 (2) 队满队满 front e3 e4 0 1 2 3 reare5队列的顺序存储队列的顺序存储#define MAXSIZE 50#define MAXSIZE 50typedef structtypedef structQueueElementType elementMAXSIZE;QueueElementType elementMAXSIZE; int front;int rear; int front;int rear;SeqQueue;SeqQueue;注意事项：注意事项：1 1、出队时，头指针的变化为、出队时，头指针的变化为front=(front+1)

56、 mod MAXSIZEfront=(front+1) mod MAXSIZE2 2、入队时，尾指针的变化为、入队时，尾指针的变化为rear=(rear+1) mod MAXSIZErear=(rear+1) mod MAXSIZE3 3、凡是遇到指针要发生变化，头和尾指针的有效范围为、凡是遇到指针要发生变化，头和尾指针的有效范围为0,MAXSIZE-10,MAXSIZE-1，所以用取模运算来保证头尾指针的取值，所以用取模运算来保证头尾指针的取值循环队列的类型定义循环队列的类型定义循环队列中加入一个元素的算法：循环队列中加入一个元素的算法： int EnQueue(SeqQueue int E

57、nQueue(SeqQueue * *Q,int x) Q,int x) Q Q为已有的为已有的循环队列循环队列将插入将插入的值的值循环队列循环队列循环队列中加入一个元素的算法：循环队列中加入一个元素的算法： int EnQueue(SeqQueue *Q,int x) if(Q-rear+1)%MAXSIZE= =Q-front) return(0); else Q-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3rearrearX X循环队列循环队列循环队列中删除一个元素的算法：循环队列中删除一个元素的

58、算法：int DeQueue(SeqQueue int DeQueue(SeqQueue * *Q Q，int int * *py) py) 已有的循环已有的循环队列队列返回删返回删除的值除的值的地址的地址循环队列循环队列循环队列中删除一个元素的算法：循环队列中删除一个元素的算法：int DeQueue(SeqQueue *Q，int *py) if(Q-rear= =Q-front) return(0); else*py=QQ-front; Q-front=(Q-front+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3frontfront循环队列

59、循环队列链式存储结构链式存储结构 an a2 a1 Q.frontQ.rear队头队头队尾队尾typedef struct Nodetypedef struct NodeQueueElementType data;QueueElementType data; struct Node struct Node * *next;next;LinkQueueNode;/LinkQueueNode;/* *结点的定义结点的定义* */ /typedef structtypedef structLinkQueueNode LinkQueueNode * *front;front; LinkQueueNod

60、e LinkQueueNode * *rear;rear;LinkQueue;/LinkQueue;/* *队列的定义队列的定义* */ /注意：注意：队头永远指向头结点，队尾永远指向最后一个元素。队头永远指向头结点，队尾永远指向最后一个元素。3.3.2 3.3.2 队列的表示和实现队列的表示和实现e a1 a2 anQ.frontQ.rear 链队列添加操作链队列添加操作Q.rearnewNode=(LinkQueueNode newNode=(LinkQueueNode * *) )malloc(sizeof(LinkQueueNode);malloc(sizeof(LinkQueueNo