循环队列和链式队列的结构及其基本操作（入队、出队、取队头、查看对内元素） |
您所在的位置：网站首页 › 循环队列入队出队 › 循环队列和链式队列的结构及其基本操作（入队、出队、取队头、查看对内元素） |
|
循环队列
队列：只允许在一端进行插入操作，在另一端进行删除操作；数据存储在一个一维数组中
特点：先进先出（FIFO）结构
队头（front）：删除数据的一端
队尾（rear）：插入数据的一端
顺序队列的缺点：空队时front和rear都指向下标-1处，进队时rear先+1，再放入数据，出队时front先+1，再删数据
队满时一个个删数据，当front和rear都指向最后的位置时，前面的空间空余出来不能再使用。 循环队列的特点：存放数据的数组空间可以反复使用，单需要空出一个空间来区分队头队尾（以下程序中默认front的指向位置不存数据）。 反复使用存储空间的实现操作：front（rear）的操作：front（rear） = （front（rear）+1） % SIZE(存储数据的数组大小) 原因：当front（rear）走到队列最后（数组最大下标=SIZE-1）时，想要返回队列开头（数组最小下标=0）时，利用上述公式 (( SIZE-1) +1) % SIZE == SIZE % SIZE ==0(数组最小下标)。 队满情况：（rear+1）%SIZE ==front 队列长度：（rear-front+SIZE）% SIZE 队列结构和基本操作函数 #include #define ERROR 0 #define OK 1 #define SIZE 11//队列空间大小 typedef struct queue { int data[SIZE]; int front;//队头，删除 int rear;//队尾，新增 }Queue; //创建 int InitQueue(Queue *q) { if(q == NULL) return ERROR; //初始化 q->front = 0; q->rear = 0; return OK; } //新增 int Add(Queue *q, int data) { if(q == NULL || q->front == (q->rear + 1)%SIZE) return ERROR; q->rear = (q->rear + 1) % SIZE;//最开始空队列状态时，rear == front == 0；数据进队要先将rear往后移一位再存数据 q->data[q->rear] = data; return OK; } //删除 int Delete(Queue *q, int *x) { if (q == NULL || q->rear == q->front) return ERROR; q->front = (q->front + 1) % SIZE;//front所在的位置不存（不读取）数据，删除数据就让front指向该数据的位置（队列只能从头开始依次删除数据） *x = q->data[q->front];//main函数中的x获取删除的数据 return OK; } //取队头数据 int GetFront(Queue *q, int *x) { if (q == NULL) return ERROR; int data = (q->front+1) % SIZE; *x = q->data[data]; return OK; } //打印数据 void print(Queue q) { if (q.rear == q.front) { printf("队列为空\n"); return; } int begin = (q.front + 1)%SIZE;//队列开头数据的下标,队头标志front所在位置的数据不读取（不存值） int beyond = (q.rear + 1)%SIZE;//队列结尾数据的下一个位置的下标 int i; for (i = begin; i != beyond; i = (i+1)%SIZE)//i从队列开头数据下标开始，依次往后加1，到队里最后时需要返回操 { //作，一直到beyond的前一个位置 printf("%-4d", q.data[i]);//从队头第一个数据开始一直打印到最后一个数据 } printf("\n"); } //队列长度 int Length(Queue q) { return (q.rear - q.front + SIZE)%SIZE; } 主函数，举例实践 int main() { Queue q; InitQueue(&q); int i; for (i = 1; i < 11; i++) { Add(&q, i); } printf("当前队列中数据\n"); print(q); int front; printf("队头数据：%d\n", GetFront(&q, &front)); int x; printf("出队数据\n"); for (i = 1; i < 3; i++)//出队两个 { Delete(&q, &x); printf("%-4d", x); } printf("\n"); //进队两个 Add(&q, 9); Add(&q, 10); printf("当前队列中数据\n"); print(q); return 0; }链式队列 链式队列没有队满情况，可以添加任意个结点，操作特点：尾插头删 #include #include #define ERROR 0 #define OK 1 typedef struct node { int data; struct node *next; }Node; typedef struct queue { Node* front;//队头，删除 Node* rear;//队尾，新增 }Queue; //创建 Queue* InitQueue() { Queue* q = (Queue*)malloc(sizeof(Queue)); if (q == NULL) return ERROR; q->front = NULL; q->rear = NULL; return q; } //新增 int Add(Queue *q, int data) { if(q == NULL) return ERROR; //创建一个新结点 Node* node = (Node*)malloc(sizeof(Node)); if (NULL == node) return ERROR; node->data = data; node->next = NULL;//尾插 if (q->front == NULL)//队列为空情况,队头队尾指针都指向新结点 { q->front = node; q->rear = node; } else//队列不空 { q->rear->next = node;//队尾结点指向新结点 q->rear = node;//队尾指针指向队尾（新建结点插在队尾） } return OK; } //删除 int Delete(Queue *q, int *x) { if (q == NULL || q->front == NULL) return ERROR; Node* p = q->front;//保存当前队列的第一个结点地址 *x = p->data; q->front = p->next;//队头指针指向原先队列的第二个结点（原先第二结点充当新队列的第一结点） free(p);//释放（删除）原先第一结点的空间 if (q->front == NULL)//如果删除一个结点后，队列为空 q->rear == NULL;//原先队列只有一个结点的情况下，rear指向被删结点的空间，删除结点后需要置空 return OK; } //打印数据 void print(Queue *q) { if (NULL == q->front) { printf("队列为空\n"); return; } Node* tmp = q->front;//tmp指向队列第一个结点 while (tmp) { printf("%-4d", tmp->data); tmp = tmp->next; } printf("\n"); } int main() { Queue* q = InitQueue(); int i; for (i = 1; i < 11; i++) { Add(q, i); } printf("当前队列中数据\n"); print(q); int x; printf("出队数据\n"); for (i = 1; i < 11; i++)//出队 { Delete(q, &x); printf("%-4d", x); } printf("\n"); printf("当前队列中数据\n"); print(q); return 0; } |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |