下列程序是队列基本操作函数,请填写相应的代码,实现出队函数的功能。 int DeQueue(/*********代码填空***********/) { /*出队函数*/ LinkLi
时间: 2024-05-28 09:06:46 浏览: 24
stNode *p;
if(QueueEmpty(Q))
{
printf("队列为空!");
return NULL;
}
else
{
p = Q->front;
Q->front = p->next;
Q->length--;
if(Q->front == NULL) // 如果队列为空,尾指针也要指向NULL
Q->rear = NULL;
return p;
}
其中,LinkList是队列的链式存储结构,LinkListNode是队列的结点类型,Queue是队列的顺序存储结构。
相关问题
《4》 编写函数int getWidth(BiTNode *T),计算二叉树的最大宽度,并给出完整代码
以下是计算二叉树最大宽度的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef struct QueueNode {
BiTree data;
struct QueueNode *next;
} QueueNode, *LinkQueuePtr;
typedef struct {
LinkQueuePtr front;
LinkQueuePtr rear;
} LinkQueue;
// 初始化队列
void InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (LinkQueuePtr) malloc(sizeof(QueueNode));
if (!Q->front) {
exit(-1);
}
Q->front->next = NULL;
}
// 判断队列是否为空
int QueueEmpty(LinkQueue Q) {
return Q.front == Q.rear;
}
// 入队
void EnQueue(LinkQueue *Q, BiTree e) {
LinkQueuePtr p = (LinkQueuePtr) malloc(sizeof(QueueNode));
if (!p) {
exit(-1);
}
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
// 出队
void DeQueue(LinkQueue *Q, BiTree *e) {
if (Q->front == Q->rear) {
return;
}
LinkQueuePtr p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) {
Q->rear = Q->front;
}
free(p);
}
// 获取二叉树深度
int GetDepth(BiTree T) {
if (!T) {
return 0;
}
int left_depth = GetDepth(T->lchild);
int right_depth = GetDepth(T->rchild);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
// 计算二叉树最大宽度
int getWidth(BiTree T) {
if (!T) {
return 0;
}
LinkQueue Q;
InitQueue(&Q);
EnQueue(&Q, T);
int width = 1;
while (!QueueEmpty(Q)) {
int count = Q.rear - Q.front + 1;
if (count > width) {
width = count;
}
while (count--) {
BiTree node;
DeQueue(&Q, &node);
if (node->lchild) {
EnQueue(&Q, node->lchild);
}
if (node->rchild) {
EnQueue(&Q, node->rchild);
}
}
}
return width;
}
int main() {
// 构建二叉树
BiTree A = (BiTree) malloc(sizeof(BiTNode));
BiTree B = (BiTree) malloc(sizeof(BiTNode));
BiTree C = (BiTree) malloc(sizeof(BiTNode));
BiTree D = (BiTree) malloc(sizeof(BiTNode));
BiTree E = (BiTree) malloc(sizeof(BiTNode));
BiTree F = (BiTree) malloc(sizeof(BiTNode));
A->data = 'A';
B->data = 'B';
C->data = 'C';
D->data = 'D';
E->data = 'E';
F->data = 'F';
A->lchild = B;
A->rchild = C;
B->lchild = D;
B->rchild = NULL;
C->lchild = E;
C->rchild = F;
D->lchild = D->rchild = NULL;
E->lchild = E->rchild = NULL;
F->lchild = F->rchild = NULL;
// 测试计算二叉树最大宽度函数
int width = getWidth(A);
printf("The max width of the binary tree is: %d\n", width);
return 0;
}
```
其中,我们使用了队列来辅助计算二叉树的最大宽度。具体来说,我们先将根节点入队,然后按层次遍历二叉树,每层统计节点个数并更新最大宽度值,然后将下一层的节点入队。最终返回的就是二叉树的最大宽度值。
使用C++创建一个链队列的完整程序代码,并且编写main函数测试队列的基本功能以及正确性
以下是使用C++实现链队列的完整程序代码:
```cpp
#include <iostream>
using namespace std;
// 链队列结点定义
struct Node {
int data; // 数据域
Node* next; // 指针域
};
// 队列定义
class Queue {
private:
Node* front; // 队头指针
Node* rear; // 队尾指针
public:
Queue() { // 构造函数,初始化队头和队尾指针
front = rear = new Node;
front->next = NULL;
}
~Queue() { // 析构函数,释放队列中的内存空间
while (front) {
rear = front->next;
delete front;
front = rear;
}
}
void EnQueue(int x); // 入队操作
int DeQueue(); // 出队操作
bool IsEmpty() { return front == rear; } // 判断队列是否为空
};
void Queue::EnQueue(int x) {
Node* s = new Node;
s->data = x;
s->next = NULL;
rear->next = s;
rear = s;
}
int Queue::DeQueue() {
if (IsEmpty()) {
cout << "队列为空,无法出队" << endl;
return -1;
}
Node* p = front->next;
int x = p->data;
front->next = p->next;
if (rear == p) rear = front;
delete p;
return x;
}
int main() {
Queue q;
int x;
cout << "请输入入队元素(以-1结束):" << endl;
while (cin >> x && x != -1) {
q.EnQueue(x);
}
cout << "出队元素为:" << endl;
while (!q.IsEmpty()) {
cout << q.DeQueue() << " ";
}
cout << endl;
return 0;
}
```
在上述代码中,我们定义了结构体 `Node` 作为链队列的结点,其中包含了数据域和指针域。我们还定义了一个 `Queue` 类来实现链队列,其中包含了队头指针和队尾指针。类中封装了入队 (`EnQueue`) 和出队 (`DeQueue`) 操作,以及判断队列是否为空 (`IsEmpty`) 的操作。在 `main` 函数中,我们通过输入一些元素来测试队列的基本功能以及正确性。
编译运行输出结果如下:
```
请输入入队元素(以-1结束):
1 2 3 4 5 -1
出队元素为:
1 2 3 4 5
```