数据结构上机实验二-栈和链队列.doc

文档介绍：数据结构上机实验二
实验内容:栈和链队列的基本操作
实验目的:
1)熟悉C/C++基本编程,培养动手能力.
2)通过实验,加深对堆栈和队列的理解.
实验要求:
1) 栈和队列的显示要作为函数被调用.
2) 把自己使用的栈和队列结构明确的表达出来.
分组要求:可单独完成,也可两人一组。
评分标准:
1) 只完成第一或第二题,3分;
2)完成一和二题,得5分;
3)在2)基础上,可选做三)中的题目。
题目:
一)堆栈题(顺序栈):创建一个栈+入栈+出栈
(1)由键盘一个一个的输入正整数,建立相应的堆栈,输入-1时,堆栈结束;
(2)在(1)中创建的堆栈中添加一个元素;
(3)在(1)中创建的堆栈中删除一个元素;(要求在显示器可见);
二)链队列题目:初始化队列+入队列+出队列+销毁队列
(1)初始化一个链队列;
(2)在初始化好的链队列中放入数,入队列,完成后要求显示;
(3)从队列中出队列,要求显示出来的元素和之后的队列;
(4)销毁创建的队列,释放内存;
三)应用题
(1)编制程序,将输入的十进制数据M 转换为八进制数据M8,将其调试通过。在此基础上修改程序,实现十进制数据M向任意进制(2-9进制)的转换。(1分)
(2)编制程序,从键盘接收一个字符串(长度最长设为100),检测其中的括号(),[],{}匹配情况,若有成对括号则在屏幕输出括号对及其所包含的字符内容。(2分)
(3)假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则为非法序列。编写一个算法,判断所给的序列S1:IOOIIOIOO ,S2:IOOIOIIO及S3: IIIOIOIO,S4: IIIOOIOO是否合法。(1分)
1
1 1
1 2 1
1 3 3 1
……
(4)二项式(a+b)n展开后,其系数构成杨辉三角形,利用队列写出打印杨辉三角形的前n行的程序。(1分)
(5)基于堆栈,编写迷宫求解程序。(3分)
(1)编制程序,将输入的十进制数据M 转换为八进制数据M8,将其调试通过。在此基础上修改程序,实现十进制数据M向任意进制(2-9进制)的转换。(1分)
#include <>
#include <>
#include <>
typedef struct Qnode{//队列结点
int data;
struct Qnode *next;
}QNode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
void QueueTraverse (LinkQueue Q){//遍历显示队列
QueuePtr p;
for(p=->next;p!=;p=p->next)
printf("%d ",p->data);
printf("%d ",p->data);
}
void main()
{
LinkQueue Q;
int e,m[100],i