《数据结构（C语言描述）（第2版）》教学课件3-05 链队列及其操作

1、2016数据结构Data structure讲授：司蕾3.5 链队列及其操作常州信息职业技术学院02031链队列（Linked Queue） 队列的链式存储结构称为链队列，它是限制仅在表头删除和在表尾插入的单链表。由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾结点的指针。链队列-描述3.5041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rear041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearA041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearBA041链队列（Linke

2、d Queue）链队列-描述3.5Q-frontQ-rearCAB041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearDABC041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearDBC041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearDC041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearD041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rear041链队列（Linked Queue）链队列-描述3.5Q-frontQ-rearDABC0

3、52、链队列的描述typedef char DataType; /定义队列元素类型typedef struct queuenode/队列中结点的类型 DataType data; struct queuenode *next;QueueNode;typedef struct QueueNode *front;/队头指针 QueueNode *rear; /队尾指针LinkQueue;LinkQueue *Q; /定义链队列Q链队列-描述3.5三、链表的插入063、说明：（1）设Q是LinkQueue类型的指针变量，则Q是指向链队列的指针，队头指针、队尾指针可分别表示为Q-front、Q- re

4、ar。（2）设p是QueueNode类型的指针变量，则p是指向链队列某结点的指针，该结点的数据域可表示为p -data，该结点的指针域可表示为p - next。链队列-描述3.5三、链表的插入071、入队2、算法思路：生成一个新结点p，将x写入数据域，p-data=x; p-next=NULL;再将新结点插入队列。插入结点时需考虑队列是否为空队列。链队列-入队3.5Q-frontQ-rearQ-frontQ-rearx当队列空时if(QueueEmpty(Q) Q-front=Q-rear=p;p三、链表的插入071、入队2、算法思路：生成一个新结点p，将x写入数据域，p-data=x; p-

5、next=NULL;再将新结点插入队列。插入结点时需考虑队列是否为空队列。链队列-入队3.5Q-frontQ-rearQ-frontQ-rearx当队列空时if(QueueEmpty(Q) Q-front=Q-rear=p;p081、入队2、算法思路：生成一个新结点p，将x写入数据域，p-data=x; p-next=NULL;再将新结点插入队列。插入结点时需考虑队列是否为空队列。链队列-入队3.5Q-frontQ-rearQ-frontQ-rearA当队列非空时Q-rear-next=p;/p链到原队尾结点后Q-rear=p;/队尾指针指向新的尾px093、具体算法：int EnQueue(

6、LinkQueue *Q,DataType x)/入队QueueNode *p;p=(QueueNode *)malloc(sizeof(QueueNode);if(p=NULL) puts (空间申请失败!); return 0;p-data=x;p-next=NULL;if(QueueEmpty(Q) Q-front=Q-rear=p;/将x插入空队列else /x插入非空队列的尾 Q-rear-next=p;/*p链到原队尾结点后 Q-rear=p;/队尾指针指向新的尾 return 1;链队列-入队3.5三、链表的插入101、出队2、算法思路： 判断队列Q是否队空， 当队列为空时，提示

7、“队空”，返回0Q-frontQ-rearif(QueueEmpty(Q)puts(队空); return 0;链队列-出队3.5三、链表的插入51、出队2、算法思路： 判断队列Q是否队空， 当队列为空时，提示“队空”，返回0 当队列为非空时，先将队头元素的值存入指针x指向的变量，再将队头结点删除。p=Q-front;/指向队头结点 *x=p-data;/保存队头结点的数据Q-front=p-next;/将对头结点从链上摘下free(p);/释放被删队头结点Q-frontQ-rearBAp链队列-出队3.5三、链表的插入121、出队2、算法思路： 判断队列Q是否队空， 当队列为空时，提示“队空

8、”，返回0 当队列为非空时，先将队头元素的值存入指针x指向的变量，再将队头结点删除。注意：一般只需要修改队头指针Q-front=p-next ，但是只有一个结点时，该结点既是队头也是队尾，故删去此结点时也需修改尾指针，且删去此结点后队列变空。if(Q-rear=p)Q-rear=NULL;Q-frontQ-rearB链队列-出队3.5133、具体算法：int DeQueue(LinkQueue *Q, DataType *x)/出队QueueNode *p;if(QueueEmpty(Q)puts(队空); return 0;p=Q-front;/指向队头结点*x=p-data;/保存队头结点的数据Q-front=p-next;/将队头结点从链上摘下if(Q-rear=p)/队列中只有一个结点的处理Q-rear=NULL;free(p);/释放被删队头结点return 1; 可将队列Q和指针x作为参数。保存队头结点的数据，删除队头结点。出队操作成功时，返回1，否则返回0。链队列-出队3.5141、取队头元素 取队头元素和出队类似，但是不需改变队头指针、队尾指针的值 可将队列Q和指针x作为参数。保存队头元素的数据。操作成功时，返回1，否则返回0。2、具体算