C语言实现利用队列设计一个算法,实现存储在数组A[n]中的n个元素循环左移k(0<k<n)位
时间: 2024-05-13 17:17:22 浏览: 61
以下是利用队列实现数组循环左移k位的C语言代码:
```c
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
int isQueueEmpty(Queue *q) {
return (q->front == q->rear);
}
int isQueueFull(Queue *q) {
return ((q->rear + 1) % MAXSIZE == q->front);
}
int enQueue(Queue *q, int x) {
if (isQueueFull(q)) {
return 0;
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE;
return 1;
}
int deQueue(Queue *q, int *x) {
if (isQueueEmpty(q)) {
return 0;
}
*x = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
return 1;
}
void reverse(int a[], int left, int right) {
while (left < right) {
int temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
void leftRotate(int a[], int n, int k) {
k %= n;
if (k == 0) {
return;
}
Queue q;
initQueue(&q);
for (int i = 0; i < k; i++) {
enQueue(&q, a[i]);
}
for (int i = k; i < n; i++) {
int x;
deQueue(&q, &x);
enQueue(&q, a[i]);
a[i] = x;
}
for (int i = 0; i < k; i++) {
int x;
deQueue(&q, &x);
a[i] = x;
}
reverse(a, 0, n - 1);
reverse(a, 0, k - 1);
reverse(a, k, n - 1);
}
int main() {
int a[] = {1, 2, 3, 4, 5};
int n = sizeof(a) / sizeof(a[0]);
int k = 3;
leftRotate(a, n, k);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
```
这里利用队列的思路是,先将数组中的前k个元素入队,然后从第k个元素开始,每次将队头元素出队并入队到队尾,同时将数组中的当前位置设置为出队的元素值,直到遍历完整个数组。接着将队列中剩余的元素依次出队,并将它们赋值给数组中前k个位置。最后对数组进行三次翻转操作,即可得到循环左移k位后的数组。
需要注意的是,由于数组是循环的,所以k可能超过n,因此在实际计算中需要先对k取模,以确保k在合理的范围内(0<k<n)。同时,队列的实现中需要注意队列满和队列空的判断条件。
阅读全文