数据结构上机实验二-栈和链队列.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）假设以Ｉ和Ｏ分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由Ｉ和Ｏ组成的序列，称可以操作的序列为合法序列，否则为非法序列。编写一个算法，判断所给的序列S1：ＩＯＯＩＩＯＩＯＯ ，S２：ＩＯＯＩＯＩＩＯ及S３： ＩＩＩＯＩＯＩＯ，S４： ＩＩＩＯＯＩＯＯ是否合法。（1分）
（4）二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。（1分）
（5）基于堆栈，编写迷宫求解程序。（3分）
（1）编制程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M向任意进制（2-9进制）的转换。（1分）
#include stdio.h
#include malloc.h
#include math.h
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=Q.front-next;p!=Q.rear;p=p-next)
printf(%d ,p-data);
printf(%d ,p-data);
}
void main()
{
LinkQueue Q;
int e,m[100],i;
QueuePtr p;
Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); //初始化链队列
Q.front-next=NULL; //初始化结束
printf(Put in the elems:\n);
scanf(%d,e); //入队列
while(e!=-1)
{
p=(QueuePtr)malloc(sizeof(QNode));
p-data=e;
p-next=NULL;
Q.rear-next=p;
Q.rear=p;
scanf(%d,e);
} //入队列结束
printf(The queue is:\n);
QueueTraverse(Q);
printf(\n);
printf(The nums become:\n);
p=Q.front-next; //转换数制
do{
e=p-data;
i=0;
while(e=8) //修改数制改变这里1
{
m[i]=e%8; //修改数制改变这里2
e=e/8; //修改数制改变这里3
i++;
}
m[i]=e;
for(;i=0;i--)
printf(%d,m[i]);
printf(\n);
p=p-next;
}
while(p!=Q.rear);
e=p-data;
i=0;
while(e=8)
显示全部