五、链式队列 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;