当前位置：首页 > news >正文

数据结构实验4.1：链队列的基本操作

news 来源：原创 2025/9/18 4:11:10

文章目录

一，问题描述
二，基本要求
三，算法分析
- - 链队列的存储结构设计
  - 基本操作的算法分析
四，示例代码
五，实验操作
六，运行效果

一，问题描述

编程实现有关链队列的下列基本操作。
（1）初始化队列：创建一个空的链队列，为后续操作做好准备，确保队列的头指针和尾指针都指向合适的初始状态（通常为空）。
（2）进队操作：将新的元素添加到链队列的尾部，更新尾指针以指向新的队尾元素，保证队列的逻辑结构正确。
（3）出队操作：从链队列的头部移除并返回一个元素，同时更新头指针，若队列为空则需要进行适当的处理（如返回错误信息）。
（4）调用进队函数建立一个队列：通过多次调用进队函数，将多个元素依次添加到队列中，构建出一个完整的链队列。
（5）输出队列中的所有元素：遍历链队列，按顺序输出队列中存储的所有元素，以便直观地查看队列的内容。

二，基本要求

（1）设计链队列的存储结构：使用结构体来定义链队列的节点，节点包含数据域和指向下一个节点的指针域。同时，定义一个结构体来表示整个链队列，包含头指针和尾指针。
（2）设计基于链队列的几种基本操作的算法：分别为初始化队列、进队、出队、建立队列和输出队列元素设计详细的算法步骤，确保操作的正确性和高效性。
（3）在参考程序中的下划线处填写适当的语句，完成参考程序：仔细分析参考程序的逻辑，根据设计的存储结构和算法，在相应位置补充缺失的代码，使程序完整且能正确运行。
（4）设计测试用例，上机调试、测试参考程序，记录测试结果，对结果进行分析：设计多种测试用例，包括空队列的操作、正常队列的进队和出队、边界情况（如队列满、队列空时的非法操作）等。上机运行程序，记录每个测试用例的输入和输出，分析程序是否按照预期工作，是否存在逻辑错误或异常情况。
（5）要求每完成一个步骤就必须及时输出队列中元素以便观察操作结果：在初始化队列、进队、出队、建立队列等操作完成后，立即调用输出队列元素的函数，显示当前队列的内容，方便直观地了解操作对队列的影响。

三，算法分析

链队列的存储结构设计

使用两个结构体来实现链队列：

节点结构体：

typedef struct Node {int data;  // 数据域，存储节点的值struct Node *next;  // 指针域，指向下一个节点
} Node;

链队列结构体：

typedef struct Queue {Node *front;  // 头指针，指向队列的头部Node *rear;  // 尾指针，指向队列的尾部
} Queue;

基本操作的算法分析

初始化队列：
- 时间复杂度：将头指针和尾指针都设置为 NULL，时间复杂度为 $O (1)$ 。
- 空间复杂度：只需要存储头指针和尾指针，空间复杂度为 $O (1)$ 。

void initQueue(Queue *q) {q->front = q->rear = NULL;
}

进队操作：
- 时间复杂度：创建一个新节点并将其添加到队列尾部，更新尾指针，时间复杂度为 $O (1)$ 。
- 空间复杂度：需要为新节点分配内存，空间复杂度为 $O (1)$ 。

void enqueue(Queue *q, int value) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (q->rear == NULL) {q->front = q->rear = newNode;} else {q->rear->next = newNode;q->rear = newNode;}
}

出队操作：
- 时间复杂度：从队列头部移除一个节点，更新头指针，若队列为空则直接返回，时间复杂度为 $O (1)$ 。
- 空间复杂度：释放被移除节点的内存，空间复杂度为 $O (1)$ 。

int dequeue(Queue *q) {if (q->front == NULL) {return -1;  // 队列为空，返回错误标志}Node *temp = q->front;int value = temp->data;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(temp);return value;
}

建立队列：
- 时间复杂度：通过多次调用进队函数来添加元素，假设添加 $n$ 个元素，时间复杂度为 $O (n)$ 。
- 空间复杂度：需要为 $n$ 个元素分配内存，空间复杂度为 $O (n)$ 。

void buildQueue(Queue *q, int values[], int n) {for (int i = 0; i < n; i++) {enqueue(q, values[i]);}
}

输出队列元素：
- 时间复杂度：遍历整个队列，时间复杂度为 $O (n)$ ，其中 $n$ 是队列中元素的个数。
- 空间复杂度：只需要一些临时变量来遍历队列，空间复杂度为 $O (1)$ 。

void printQueue(Queue *q) {Node *temp = q->front;while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}printf("\n");
}

四，示例代码

#define OK 1
#define ERROR 0
#include<stdio.h>
#include<malloc.h>
typedef int Status;
typedef int QElemType;typedef struct QNode {  	//链表结点类型QElemType data;struct QNode* next;
}QNode, * QueuePtr;typedef struct {     		//队列类型QueuePtr   front;  	//队头指针QueuePtr   rear;  	//队尾指针
}LinkQueue;Status InitQueue(LinkQueue& Q) {//构造一个带附加表头结点的空链队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if (!Q.front)  return ERROR;Q.front->next = NULL;return  OK;
}Status EnQueue(LinkQueue& Q, QElemType e) {//将元素e插入到带头结点的链队列Q中QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));if (!p)  return ERROR;p->data = e;p->next = NULL;Q.rear->next = p;  // 1. 将新节点连接到队尾节点之后Q.rear = p;  // 2. 更新队尾指针指向新节点return  OK;
}Status DeQueue(LinkQueue& Q, QElemType& e) {//若队列不空，则队首元素出队列，用e返回其值，返回OK，否则返回ERRORQueuePtr p;if (Q.rear == Q.front)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;  // 3. 将队头指针的下一个节点指向出队节点的下一个节点if (Q.rear == p)Q.rear = Q.front;  // 4. 若出队节点是队尾节点，更新队尾指针指向头节点（此时队列为空）free(p);return  OK;
}void OutputQueue(LinkQueue Q)
// 输出队列中的所有元素
{QueuePtr p;p = Q.front->next;while (p != NULL) {printf("%d  ", p->data);p = p->next;  // 5. 移动指针到下一个节点}printf("\n");return;
}void main()
{LinkQueue Q;InitQueue(Q);int op, x;while (1) {printf("请选择操作：1.进队  2.出队  0.退出==>");scanf("%d", &op);switch (op) {case 0:            // 退出return;case 1:            // 进队printf("请输入进队元素："); 	// 整数scanf("%d", &x);EnQueue(Q, x);  // 6. 调用进队函数printf("队内元素为：\n");OutputQueue(Q);break;case 2:           // 出队if (DeQueue(Q, x)) {     // 7. 若出队成功printf("出队元素为：[%d]，队内元素为：\n", x);OutputQueue(Q);}elseprintf("  队已空！\n");break;}}
}