数据结构之队列小结.ppt

数据结构数据结构 3.4 3.4 队列队列 3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义 队列队列(Queue):(Queue):一种运算受限的线性表。只允许在表的一种运算受限的线性表。只允许在表的 一端进行插入，而在另一端进行删除。允许删除的一端一端进行插入，而在另一端进行删除。允许删除的一端 称为队头称为队头(front)(front)，允许插入的一端称为队尾允许插入的一端称为队尾(rear)(rear)。 先进入队列的成员总是先离开队列。故队列亦称先进先进入队列的成员总是先离开队列。故队列亦称先进 先出先出(First In First Out)(First In First Out)的线性表，简称的线性表，简称FIFOFIFO表。表。 （a a 1 1 , , a a 2 2 , , , , a a n n ） 队尾队尾队头队头 数据结构数据结构 下图是队列的示意图：下图是队列的示意图： 队列的抽象数据定义见书队列的抽象数据定义见书59 59 除了栈和队列之外，还有一种限定性数据结构除了栈和队列之外，还有一种限定性数据结构 ，它们是双端队列，它们是双端队列 a a1 1 a a2 2 a a3 3 入队入队 队尾队尾 队头队头 出队出队 队头队头 端端1 1 端端2 2 插入插入 删除删除 双端队列示意图双端队列示意图 a a1 1 a a2 2 a a i i a a0 0 a a n-1n-1 删除删除 插入插入 数据结构数据结构 3.4.2 3.4.2 链队列链队列队列的链式表示和实现队列的链式表示和实现 队列的链式存储结构简称为链队列，它是限制仅队列的链式存储结构简称为链队列，它是限制仅 在表头删除和表尾插入的单链表。显然仅有单链表的在表头删除和表尾插入的单链表。显然仅有单链表的 头指针不便于在表尾做插入操作，为此再增加一个尾头指针不便于在表尾做插入操作，为此再增加一个尾 指针，指向链表的最后一个结点。指针，指向链表的最后一个结点。 rear front front rear 非空队 rear front a1 an a2 Q rear front Q a1 rear front Q 空队 只有一个元素结点 头尾指针封装在一起的链队 数据结构数据结构 frontrear x入队 x frontrear y入队x y frontrear x出队x y front rear y出队 数据结构数据结构 typedeftypedef structstruct QNodeQNode QElemTypeQElemType data; data; QNodeQNode *next; *next; QNodeQNode ,* ,*QueuePtrQueuePtr; ; typedeftypedef structstruct QueuePtrQueuePtr front,rear; / front,rear; / 队头、队尾指针队头、队尾指针 LinkQueueLinkQueue; ; Status Status InitQueue(LinkQueueInitQueue(LinkQueue exit(OVERFLOW); Q.front-next=NULL; Q.front-next=NULL; return OK; return OK; front rear 空队 数据结构数据结构 Status Status DestroyQueue(LinkQueueDestroyQueue(LinkQueue Q.rear=Q.front-next; free(Q.front); free(Q.front); Q.front=Q.rear; Q.front=Q.rear; return OK; return OK; 数据结构数据结构 Status Status EnQueue(LinkQueueEnQueue(LinkQueue ); p-data=e; p-next= p-data=e; p-next=NULL;Q.rearNULL;Q.rear-next=p; -next=p; Q.rearQ.rear=p;=p; return OK; return OK; p front a2an rear rear a1 e 数据结构数据结构 Status Status DeQueue(LinkQueueDeQueue(LinkQueue if(Q.front=Q.rear) return ERROR; p=Q.front-next; p=Q.front-next; e=p-data; e=p-data; Q.front-next=p-next; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.frontif(Q.rear=p) Q.rear=Q.front; ; free(p); free(p); return OK; return OK; front a1a2 an rear p front a1 p rear rear 数据结构数据结构 3.4.3 循环队列队列的顺序表示和实现 初始空队列：front = rear=0 ; 插入新的元素时, rear+; 删除队头元素时,front+; 0 1 2 3 4 入队出队 a3a4 Q.rearQ.front a5 Q.rear 假溢出 如何解决假溢出？ Q.rear a6 Q.rear 数据结构数据结构 1 1 0 0 maxsize-1maxsize-1 . . Q.frontQ.front Q.rearQ.rear . . 队列队列 当当Q.rear Q.frontQ.rear Q.front时时: Q.rear Q.front = : Q.rear Q.front = 队列中元素个数队列中元素个数 当当Q.rear =0=1,2,.n, n=0 数据关系：数据关系： R R 1 1 = = a ai- i-1. 1., , a a i i | | a a i i DD, , i=2,.ni=2,.n。 基本操作：基本操作： StrAssign( ); StrCopy(); StrEmptyStrEmpty (S); (S); StrCompare(S,TStrCompare(S,T);); StrLength(SStrLength(S); ); ClearString(); Concat( Concat( Substring(); Index(S,T,pos); Replace( Index(S,T,pos); Replace( StrInsert( ); StrDelete(); DestroyString( ;若若S=T,S=T,则返回值则返回值=0;=0; 否则返回值否则返回值 0) n = StrLength(S); m = StrLength(T); i = pos; while(i MAXSTRLEN 时 截断部分 数据结构数据结构 1.1.串联结串联结 Concat( 否则返回0。 if ( S10+S20 s0 | len s0 - pos +1 ) return ERROR; Sub1len = Spospos+len-1; Sub0 = len; return OK; / SubString S Sub 1 pos len 数据结构数据结构 4.2.2 4.2.2 堆分配存储表示堆分配存储表示 也是用一组连续的存储单元存储串值的字符序列. 但存储空间是在程序执行过程中动态分配得到的. 在C语言中,用字符“0”表示串的终结,“0”不计入 串长. typedef struct char *ch; / 若是非空串,则按实际长度分配,否则为NULL; int length; / 串长度 HString; 以下用串插入操作 StrInsert( / pos if ( pos S.length+1) return ERROR; / pos 不合法不合法 if(T.length) / T if(T.length) / T 非空非空, ,则要重新分配空间则要重新分配空间, ,插入插入T T if(!(S.chif(!(S.ch= (char *)= (char *)realloc(S.chrealloc(S.ch, , (S.length+T.length)* (S.length+T.length)*sizeof(charsizeof(char) exit(OVERFLOW); exit(OVERFLOW); for(i=S.length - 1; i=pos-1; -i) / for(i=S.length - 1; i=pos-1; -i) / 为插入为插入T T而腾出位置而腾出位置 S.chi+T.lengthS.chi+T.length = = S.chiS.chi; ; S.chpos-1pos+T.length-2 = T.ch0T.length-1; / S.chpos-1pos+T.length-2 = T.ch0T.length-1; / 插入插入T T S.length += T.length; S.length += T.length; / if / if return OK; return OK; / / StrInsertStrInsert 数据结构数据结构 HstringHstring串类基本操作的算法描述串类基本操作的算法描述 Status Status StrAssign(HStringStrAssign(HString / ); / 释放释放T T原有空间原有空间 i=i=strlen(charsstrlen(chars); / ); / 求求charschars的长度的长度i i if(!i) if(!i) T.chT.ch=NULL; T.length=0;=NULL; T.length=0; else / chars else / chars的长度不为的长度不为0 0 T.chT.ch=(char*)=(char*)malloc(imalloc(i* *sizeof(charsizeof(char); / ); / 分配串空间分配串空间 if(!T.chif(!T.ch) / ) / 分配串空间失败分配串空间失败 exit(OVERFLOW);exit(OVERFLOW); T.ch0i-1=chars0i-1; T.ch0i-1=chars0i-1; T.length=i; T.length=i; return OK; return OK; 数据结构数据结构 intint StrLength(HStringStrLength(HString S) S) / / 返回返回S S的元素个数的元素个数, ,称为串的长度称为串的长度 return S.length;return S.length; intint StrCompare(HStringStrCompare(HString S,HStringS,HString T) T) / / 若若ST,ST,则返回值则返回值0;0;若若S=T,S=T,则返回值则返回值=0;=0;若若S if(posS.length|lenS.length|lenS.length-pos+1)S.length-pos+1) return ERROR; return ERROR; if(Sub.chif(Sub.ch) ) free(Sub.chfree(Sub.ch); / ); / 释放旧空间释放旧空间 if(!len)Sub.chif(!len)Sub.ch=NULL; Sub.length=0