一、实验目的
- 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
二、实验环境
已安装 CodeBlocks 软件的计算机；
三、实验学时
2学时
四、实验要求
- 熟悉c语言的语法知识；
- 掌握队列的链式存储结构的定义、构造、销毁、插入、删除等基本操作；
- 完成实验报告。
五、实验内容
注：所写代码要有良好的输入和输出提示
参考课本代码，完成队列的链式存储结构的定义、取队头、出队、入队等函数的编写，并自己独立完成链式队列的输出函数编写（从队头开始输出）。要求在主函数中实现对以上操作的调用，实现以下功能：
- 第一步：队列初始化为空队列。
- 第二步：键盘输入奇数时，入队。
- 第三步：每输入一个整数，显示操作后队列中的值。
- 第四步：键盘输入0时，算法结束。
- 附加题：使用队列打印杨辉三角形。参考原文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node
{
DataType data;
struct Node *link;
};
typedef struct Node *PNode;
struct Queue
{
PNode f;
PNode r;
};
typedef struct Queue *LinkQueue;
LinkQueue SetNullQueue_Link() // 创建空队列
{
LinkQueue lqueue;
lqueue = (LinkQueue)malloc(sizeof(struct Queue));
if (lqueue != NULL)
{
lqueue->f = NULL;
lqueue->r = NULL;
}
else
{
printf("内存分配失败！\n");
}
return lqueue;
}
int IsNullQueue_Link(LinkQueue lqueue) // 判断队列是否为空
{
return lqueue->f == NULL;
}
void EnQueue_Link(LinkQueue lqueue, DataType x) // 入队操作
{
PNode p;
p = (PNode)malloc(sizeof(struct Node)); // 申请节点空间
if (p == NULL)
{
printf("内存分配错误！\n");
}
else
{
p->data = x; // 数据域赋值
p->link = NULL; // 指针域赋值
if (lqueue->f == NULL) // 空队列的特殊处理
{
lqueue->f = p;
lqueue->r = p;
}
else
{
lqueue->r->link = p; // 修改队尾
lqueue->r = p; // 修改队尾指针
}
}
}
int DeQueue_Link(LinkQueue lqueue) // 出队
{
struct Node *p;
if (lqueue->f == NULL) // 判断队列是否为空
{
printf("队列为空！\n");
return NULL;
}
else
{
p = lqueue->f; // p 指向队头结点，以方便后面的释放
lqueue->f = lqueue->f->link; // 修改队头指针
DataType n = p->data;
free(p); // 释放节点空间
return n;
}
}
DataType FrontQueue_Link(LinkQueue lqueue) // 取对头元素
{
if (lqueue->f == NULL) // 判断队列是否为空
{
printf("队列为空！\n");
return NULL;
}
else
{
return lqueue->f->data; // 返回队头节点数据域
}
}
void PrintQueue_Link(LinkQueue lqueue) // 打印队列
{
PNode p;
p = lqueue->f;
while (p != NULL)
{
printf("%d ", p->data);
p = p->link;
}
printf("\n");
}
void printPascalTriangle(int n) // 打印杨辉三角
{
int i, s, e, k;
// 由于杨辉三角越往下，值的位数越多，为了保持输出数据的形状，杨辉三角第一行中的1需要空多个格
for (i = 1; i <= n; i++)
{
printf(" ");
}
// 输出 1，需要控制其所占位数
printf("%-5d\n", 1);
// 初始化队列，同时将三角的第二行作为起始行，向下推导
LinkQueue lqueue = SetNullQueue_Link();
EnQueue_Link(lqueue, 0);
EnQueue_Link(lqueue, 1);
EnQueue_Link(lqueue, 1);
k = 1;
while (k < n)
{
// 每往下一行，其第一个数字都需往左移动 1 个占位
for (i = 1; i <= n - k; i++)
{
printf(" ");
}
// 0 作为转行符，入队列
EnQueue_Link(lqueue, 0);
do
{
// 队头元素出队列
s = DeQueue_Link(lqueue);
// 取新的队头元素
e = FrontQueue_Link(lqueue);
// 如果所取元素非 0，则输出，否则做转行操作
if (e)
{
printf("%-5d", e);
}
else
{
printf(" \n");
}
EnQueue_Link(lqueue, s + e);
} while (e != 0); // 一旦 e 值为 0，即做转行操作，退出循环，开始新一行的排列
k++;
}
// 出循环后，队列中还存有下一行的数据
e = DeQueue_Link(lqueue);
while (!IsNullQueue_Link(lqueue))
{
printf("%-5d", DeQueue_Link(lqueue));
}
}
int main()
{
// 队列初始化为空队列
LinkQueue lqueue = SetNullQueue_Link();
// 键盘输入奇数时，入队
int n;
while (1)
{
printf("请输入一个数，奇数入队，偶数出队，输入“0”结束算法：");
scanf("%d", &n);
if (n == 0)
{
break;
}
if (n % 2 == 1)
{
EnQueue_Link(lqueue, n);
printf("当前队列：");
PrintQueue_Link(lqueue);
}
// 键盘输入偶数时，出队
else
{
if (DeQueue_Link(lqueue) != NULL)
{
printf("当前队列：");
PrintQueue_Link(lqueue);
}
}
}
// 使用队列打印杨辉三角形
printf("请输入要打印的杨辉三角行数：");
scanf("%d", &n);
printPascalTriangle(n);
return 0;
}
|
Zuwei
支付宝
微信