【C语言】翻转队列内容 |
您所在的位置：网站首页 › c语言反转函数 › 【C语言】翻转队列内容 |
【C语言】翻转队列内容
|
队列
前言队列的表示顺序表示链式表示
循环队列/链式队列的简单操作初始化入队出队
例题链队的实现(入队翻转出队)
前言
由于对队列学习不扎实导致利用队列解题时出现很多基础错误，浪费了很多时间，所以重新记录队列的相关知识，并结合例题更好地运用队列。例题中的代码仅供参考，切忌抄袭。 队列的表示队列有两种存储表示，顺序表示和链式表示。 顺序表示 typedef struct SqQueue { int *base;//存储空间的基地址 int front;//头指针，指向队列头元素 int rear;//尾指针，指向队列尾元素 }SqQueue;拓：顺序表示也分为两种，一种为顺序队，一种为环形队即循环队列。循环队列的引入是为了解决“假溢出”问题。 循环队列可以将队列想像成一个环状，头、尾指针以及队列元素之间的关系不变，通过取模，头、尾指针可以在顺序空间内以头尾衔接的方式“循环”移动。当元素不断入队时，我们很容易预测到头尾指针指向同一个数组空间的情况，这个时候循环队列是空还是满呢？所以，在循环队列中队空队满的条件如下： SqQueue Q; 队空条件：Q.front==Q.rear; 队满条件：(Q.rear+1)%MAXSIZE==Q.front; MAXSIZE是队列可能到达的最大长度。由此我们知道，循环队列队满，实际上还保留了一个元素空间。 链式表示 typedef struct QNode//结点描述 { int data;//数据域 struct QNode* next;//指针域 }QNode; typedef struct//队列描述 { QNode *front;//队头指针 QNode *rear;//队尾指针 }LinkQueue;为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。 循环队列/链式队列的简单操作 初始化 //循环队列 #include #define MAXSIZE 200 void initQueue(SqQueue* Q) { Q->base = (SqQueue*)calloc(MAXSIZE, sizeof(SqQueue)); if (!Q->base) exit(0); Q->front = Q->rear = 0; } int main() { SqQueue Q; initQueue(&Q); } //链式队列 void initQueue(LinkQueue* Q) { Q->front=Q->rear= (QNode*)malloc(sizeof(QNode)); Q->front->next = NULL;//头结点指针域置空 } int main() { LinkQueue Q; initQueue(&Q); } 入队 //循环队列 void enQueue(SqQueue* Q) { int store[5] = { 2,8,9,10,15 }; for (int i = 0;i SqQueue Q; initQueue(&Q); enQueue(&Q); } //链式队列 void enQueue(LinkQueue* Q) { int store[5] = { 2,4,3,6,9 }; for (int i = 0;i LinkQueue Q; initQueue(&Q); enQueue(&Q); } 出队 //循环队列 int deQueue(SqQueue* Q) { if (Q->front == Q->rear) return 0; int e = Q->base[Q->front];//按需求将队头元素存好 Q->front = (Q->front + 1) % MAXSIZE;//修改头指针 return 1; } int main() { SqQueue Q; initQueue(&Q); enQueue(&Q); deQueue(&Q); } //链式队列 int deQueue(LinkQueue* Q) { if (Q->front == Q->rear)//判断队列是否为空，为空则没有元素出队 return 0; QNode *display = (QNode*)malloc(sizeof(QNode)); display = Q->front->next; int e = display->data;//按需求存好出队的元素 Q->front->next = display->next;//修改头指针 if (Q->rear == display)//判断出队的是否为队列中唯一的元素，如果是，手动将队列置空 Q->rear = Q->front; free(display);//不要忘记释放原队头元素的空间 return 1; } int main() { LinkQueue Q; initQueue(&Q); enQueue(&Q); deQueue(&Q); } 例题 链队的实现(入队翻转出队)（1）用随机函数生成10个3位整数（100~999），把这些整数应用入队操作存于队列中； （2）应用遍历操作输出队列的内容； （3）把队列的内容翻转，应用出队操作输出队列的内容。 #include #include #define number 10 typedef struct QNode { int data; struct QNode *next; }QNode; typedef struct { QNode *front; QNode *rear; }LinkQueue; void initQueue(LinkQueue *Q) { Q->front = Q->rear = (QNode*)malloc(sizeof(QNode)); Q->front->next = NULL; } void enQueue(LinkQueue *Q) { printf("--------------运用入队存入队列--------------\n"); srand((int)time(NULL)); for (int i = 0;i QNode *q = Q->front->next; while (q) { printf("%d ", q->data); q = q->next; } printf("\n"); } void reverse(LinkQueue *Q) { QNode *m = Q->front->next;//暂存原队列首元素空间 QNode *move = Q->front->next; Q->front->next = Q->rear;//将首元素替换成末尾元素 for (int i = 0;i if (move->next == Q->rear) { Q->rear->next = move; Q->rear = move; break; } move = move->next; } move = m; } move->next = NULL;//最后一个元素的指针域置空 Q->rear = move; printf("\n---------------翻转后队列元素---------------\n"); display(Q); } void deQueue(LinkQueue *Q) { printf("\n-------------运用出队输出队列元素-------------\n"); while (Q->front != Q->rear) { QNode *out = Q->front->next; printf("%d ", out->data); Q->front->next = out->next; if (Q->rear == out) Q->rear = Q->front; free(out); } printf("\n"); } int main() { LinkQueue Q; initQueue(&Q); enQueue(&Q);//将随机生成的整数通过入队存入队列 printf("\n--------------遍历输出队列元素--------------\n"); display(&Q);//遍历输出队列元素 reverse(&Q);//翻转队列 deQueue(&Q);//通过出队输出队列元素 }
|
由于“队尾入队，队头出队”的原则，我们可以看到，当队列最末尾的数组空间被a5占有时，rear往后指，就会产生溢出问题。但实际上，队列0和1的空间并没有被占用，这就是“假溢出”。以上借用了其他博客的图片，如有冒犯，可以评论区留言，在这里先表示抱歉。
（notice：有空补上例题2.队列求解迷宫问题）【本文地址】