湖北工业大学：《数据结构》第3章 堆栈和队列（3/3）

五、链式队列 1、链式队列采用链式存储结构的队列。 2、链式队列的存储结构 链式队列的队头指针指在队列的当前队头结点 位置,队尾指针指在队列的当前队尾结点位置。 下图是一个不带头结点的链式队列的结构:rear head a o a1

1 五、链式队列 1、链式队列 采用链式存储结构的队列。 2、链式队列的存储结构 链式队列的队头指针指在队列的当前队头结点 位置，队尾指针指在队列的当前队尾结点位置。 下图是一个不带头结点的链式队列的结构：rear head a０ a1 a /\ …… n-1

链式队列中结点的结构体定义为: typedef struct gnode DataType data struct gnode * next LQNode 为了方便参数调用,通常把链式队列的队头指针 fron和队尾指针rear也定义为结构体类型,如下: typedef struct LQNode *front LQNode krear 3 Queue

2 链式队列中结点的结构体定义为： typedef struct qnode { DataType data; struct qnode *next; }LQNode; 为了方便参数调用，通常把链式队列的队头指针 front和队尾指针rear也定义为结构体类型，如下： typedef struct { LQNode *front; LQNode *rear; }Lqueue;

3、链式队列操作的实现 (1)入链队列 算法说明:向链队列的队尾插入一个元素 分析: 1)申请一个链结点 p=( LQNode *)malloc(sizeof ( LQNode)) p->data= x: p->next= NULL 2)插入动作 if( Q->rear != NULL)Q->rear->next=p; Q->rear=p if(Q->front==NULLQ->front=p; 入链队列的完整算法如下:

3 ３、链式队列操作的实现 (1)入链队列 算法说明：向链队列的队尾插入一个元素 分 析： 1)申请一个链结点 p=(LQNode *)malloc(sizeof(LQNode))； p->data = x; p->next = NULL; 2)插入动作 if(Q->rear != NULL) Q->rear->next = p; Q->rear = p; if(Q->front == NULL) Q->front = p; 入链队列的完整算法如下：

int QueueAppend LQueue *Q, DataType x) t LQnode *p if((p=(lQnode *)malloc(sizeof(LQNode)))==NUlL) printf("内存空间不足!" return U: p->data =X p->next= NULL f( Q->rear NULL)Q->rear->next =p Q->rear=p if( Q->front = NULL)Q->front=p return 1

4 int QueueAppend(LQueue *Q, DataType x) { LQNode *p; if((p = (LQNode *)malloc(sizeof(LQNode))) == NULL) { printf("内存空间不足！"); return 0; } p->data = x; p->next = NULL; if(Q->rear != NULL) Q->rear->next = p; Q->rear = p; if(Q->front == NULL) Q->front = p; return 1; }

(2)出链队列 算法说明:删除链队列的队头元素。 分析: (1)在删除前应当判断链队列是否空? if(Q->front==NULL) return 0; (2)删除动作 * d=Q->front->data p=Q->front; Q->front=Q->front->next if( Q->front== NULL Q->rear= NULL;

5 (2)出链队列 算法说明：删除链队列的队头元素。 分 析： （1） 在删除前应当判断链队列是否空？ if(Q->front == NULL) return 0; （2）删除动作 *d = Q->front->data; p = Q->front; Q->front = Q->front->next; if(Q->front == NULL) Q->rear = NULL;

出链队列的完整算法如下: int Queue Delete(LQueue *Q, Data Type*d) LQNode *p: if(Q->front = NULL) { printf("队列已空无数据元素出队列!n"; return o;} else *d=Q->front->data; p=Q->front; Q->front =Q->front->next if(Q->front = NULL)Q->rear NULL; free(p); return 1; J

6 出链队列的完整算法如下： int QueueDelete(LQueue *Q, DataType *d) { LQNode *p; if(Q->front == NULL) { printf("队列已空无数据元素出队列! \n");return 0;} else { *d = Q->front->data; p = Q->front; Q->front = Q->front->next; if(Q->front == NULL) Q->rear = NULL; free(p); return 1; } }

六、队列的应用 例:编程序判断一个字符序列是否是回文 编程思想: 设字符数组str中存放了要判断的字符串 把字符数组中的字符逐个分别存入队列和堆 栈,然后逐个出队列和退栈并比较出队列的 字符和退栈的字符是否相等,若全部相等则 该字符序列是回文,否则就不是回文

7 六、队列的应用 例：编程序判断一个字符序列是否是回文。 编程思想： 设字符数组str中存放了要判断的字符串。 把字符数组中的字符逐个分别存入队列和堆 栈，然后逐个出队列和退栈并比较出队列的 字符和退栈的字符是否相等，若全部相等则 该字符序列是回文，否则就不是回文

#include #include <string. h #define MaxQueueSize 100 #define maxStackSize 100 typedef char dataType #include SegCQueue h #include SeqStack h" void Hui Wen(char strl t Seq CQueue myQueue Seqstack myStack char x, y; int i, length;

8 #include #include #define MaxQueueSize 100 #define MaxStackSize 100 typedef char DataType; #include "SeqCQueue.h" #include "SeqStack.h“ void HuiWen(char str[]) { SeqCQueue myQueue; SeqStack myStack; char x, y; int i, length;

ength= strlen(str方h QueueInitiate(&my Queue); StackInitiate(&myStack); for(i=0; i length; i++) Queue Append ( &my Queue, str[D); StackPush(&myStack, str[); while(Queue NotEmpty(my Queue)==1&& StackNotEmpty(my Stack)==l)t if(Queue Delete (&my Queue, &x)==1 & Stack Pop(&my Stack, &y)==1&&x= y) printf(("‰%s不是回文Nn",str); return: 1

9 length = strlen(str); QueueInitiate(&myQueue); StackInitiate(&myStack); for(i = 0; i < length; i++) { QueueAppend(&myQueue, str[i]); StackPush(&myStack, str[i]); } while(QueueNotEmpty(myQueue)==1 && StackNotEmpty(myStack)==1){ if(QueueDelete(&myQueue, &x) == 1 && StackPop(&myStack, &y) == 1 && x != y) { printf("%s不是回文!\n", str); return; } }

if(Queue NotEmpty(myQueue)lI StackNotEmpty(my Stack)) printf(("%s不是回文!n",str); else printf("‰%s是回文!n",str) void main(void) char str1[]="ABCDEDCBA char str2[]="ABCDEDCAB HuiWen(strI) HuiWen(str2);

10 if(QueueNotEmpty(myQueue) || StackNotEmpty(myStack)) printf("%s不是回文!\n", str); else printf("%s是回文!\n", str); } void main(void) { char str1[] = "ABCDEDCBA"; char str2[] = "ABCDEDCAB"; HuiWen(str1); HuiWen(str2); }