行列的学习

队列的学习
定义队列（queue）是只允许在一端进行插入，在另一端进行删除的运算受限的线性表。

允许插入的一端叫做队尾（rear）允许删除的一端叫做队头（front）当队列中没有元素时叫做空队列队列是一种先进先出的线性表，也称为FIFO表

顺序队列顺序队列的定义队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表顺序队列的表示

顺序队列用一个向量空间来存放当前的队列中的元素由于队列中队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的位置在队列初始化时均应置为0

顺序队列的基本操作

入队时：将新元素插入rear所指的位置，并将rear+1出队时：删除front所指的元素，并将front+1

注意：

当头尾指针相等时，队列为空在非空队列里，队头指针始终指向队头元素，队尾指针始终指向队尾元素的下一个位置

顺序队列中的溢出现象

下溢：队列为空时，做出队操作产生的溢出现象真上溢：当队列满时，做入队操作产生的空间溢出现象。假上溢：由于入队和出队操作中，队头指针只增加不减少，致使被删除的元素空间永远无法重新利用，从而导致入队操作时产生假上溢现象。

循环队列为了充分利用初始分配的向量空间，克服“假上溢”的方法是：将向量空间想像成一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(circular queue).循环队列的基本操作当循环队列进行入队和出队操作时，队头和队尾指针仍要+1。只不过当头指针指向向量上界（queuesize - 1）时，其+1操作是指向向量空间的下界0.这种循环意义下的+1操作用代码描述为

/** * Description:构造链队列 */void InitQueue(struct linkqueue *Q){Q -> front = Q -> rear = NULL;}/** * Description:判队空 */int QueueEmpty(struct linkqueue *Q){int flag;flag = (Q -> front == NULL && Q -> rear == NULL)? 1 : 0;return flag;}/** * Description:入队 */void EnQueue(struct linkqueue *Q, int data){struct qnode *s;s = malloc(sizeof(struct qnode));s -> data = data;s -> next = NULL;if(QueueEmpty(Q)){//将x插入空队列Q -> front = Q -> rear = s;}else{//将x插入非空队列Q -> rear -> next = s;Q -> rear = s;}}/** * Description:出队 */void DeQueue(struct linkqueue *Q){struct qnode *p;if(QueueEmpty){printf("队为空\n");}else{p = Q -> front;Q -> front = Q -> front -> next;if(p == Q -> rear){//队里只有一个节点，删去后需要将尾节点置空Q -> rear = NULL;}free(p);}}

查看更多 下一篇