在一个循环链队中只有尾指针(记为rear,结点结构为数据源data,指针域为next,没有管理头结点),请给出这个队列的入队、出队实现过程。
时间: 2024-05-29 17:11:47 浏览: 24
入队实现过程:
1.申请一个新的结点,假设为newNode,将待插入元素data存储在newNode的数据源data中。
2.如果队列为空,令rear指向newNode,令newNode的指针域next指向自己,即newNode->next=newNode。
3.如果队列不为空,令newNode的指针域next指向rear的下一个结点,即newNode->next=rear->next。然后令rear的指针域next指向newNode,即rear->next=newNode。最后令rear指向newNode,即rear=newNode。
出队实现过程:
1.如果队列为空,返回错误。
2.如果队列只有一个元素,令rear指向NULL,然后释放该元素的内存空间。
3.如果队列有多个元素,令头结点指向rear的下一个结点,即头结点=head=rear->next。然后令rear的指针域next指向头结点的下一个结点,即rear->next=head->next。最后释放头结点所指向的内存空间。
相关问题
c语言编写一个代码,在一个循环链队中只有尾指针(记为rear,结点结构为数据源data,指针域为next,没有管理头结点),请给出这个队列的入队、出队实现过程。
队列的结构体定义:
```
typedef struct node {
int data;
struct node *next;
} Node;
typedef struct queue {
Node *rear;
} Queue;
```
入队操作:
```
void enqueue(Queue *q, int data) {
Node *new_node = (Node *) malloc(sizeof(Node));
new_node->data = data;
new_node->next = NULL;
if (q->rear == NULL) {
q->rear = new_node;
q->rear->next = q->rear;
} else {
new_node->next = q->rear->next;
q->rear->next = new_node;
q->rear = new_node;
}
}
```
出队操作:
```
int dequeue(Queue *q) {
if (q->rear == NULL) {
printf("Queue is empty.\n");
return -1;
} else if (q->rear == q->rear->next) {
int data = q->rear->data;
free(q->rear);
q->rear = NULL;
return data;
} else {
Node *front = q->rear->next;
int data = front->data;
q->rear->next = front->next;
free(front);
return data;
}
}
```
c语言算法设计:在一个循环链队中只有尾指针(记为rear,结点结构为数据源data,指针域为next,没有头结点),请给出这个队列的入队、出队实现过程并测试。
下面是循环链队列的入队、出队实现过程:
```c
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
} Node;
typedef struct LinkQueue
{
Node *rear; // 队尾指针
} LinkQueue;
// 初始化循环链队列
void InitQueue(LinkQueue *q)
{
q->rear = NULL;
}
// 判断循环链队列是否为空
int IsEmpty(LinkQueue *q)
{
return q->rear == NULL;
}
// 入队
void EnQueue(LinkQueue *q, DataType x)
{
Node *s = (Node *)malloc(sizeof(Node));
s->data = x;
if (IsEmpty(q)) // 如果队列为空,让rear指向新结点
{
q->rear = s;
s->next = s;
}
else // 否则,插入到队尾
{
s->next = q->rear->next;
q->rear->next = s;
q->rear = s; // rear指向新结点
}
}
// 出队
int DeQueue(LinkQueue *q, DataType *x)
{
if (IsEmpty(q))
{
printf("Queue is empty.\n");
return 0;
}
Node *p = q->rear->next;
*x = p->data;
if (q->rear == p) // 如果队列只有一个结点,将rear置为NULL
{
q->rear = NULL;
}
else // 否则删除队头结点
{
q->rear->next = p->next;
}
free(p);
return 1;
}
// 测试
int main()
{
LinkQueue q;
DataType x;
InitQueue(&q);
EnQueue(&q, 1);
EnQueue(&q, 2);
EnQueue(&q, 3);
while (DeQueue(&q, &x))
{
printf("%d ", x);
}
return 0;
}
```
输出结果为:1 2 3
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)