数据结构实验二
- 格式：doc
- 大小：86.50 KB
- 文档页数：4
第 1 页 共 4 页 华北水利水电学院 数据结构 实验报告
20 10 ～20 11 学年 第 一 学期 2008级 计算机 专业
实验二 栈和队列的应用
一、 实验目的：
1．深入了解栈和队列的特性；
2．熟练掌握栈和队列的存储结构及实现方式
二、 实验要求：
1．C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．写出算法设计小结和心得。
三、 实验内容：
1．用栈实现：识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。
四、 程序源代码：
#include
#include
#include
using namespace std;
template
void reverseQueue(queue & myQueue)
{
stack tmpStack;
while (!myQueue.empty())
{
tmpStack.push(myQueue.front());
myQueue.pop();
}
while (!tmpStack.empty())
{
myQueue.push(tmpStack.top());
tmpStack.pop();
}
}
int main()
{
queue
for (int i = 0; i< 10; ++i)
{
aa.push(i); 第 2 页 共 4 页 }
reverseQueue(aa);
while (!aa.empty())
{
cout << aa.front() << " "; aa.pop();
}
cout << endl;
}
五、 测试结果
2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列等操作。
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef struct N0de {int data;
struct N0de *next;
}N0de,*QueuePtr;
typedef struct
{QueuePtr rear;
}LinkQueue; 第 3 页 共 4 页
int InintQueue(LinkQueue &Q)
{ Q.rear=(QueuePtr)malloc(sizeof(N0de));
if(!Q.rear) return(OVERFLOW);
Q.rear->next=Q.rear;
return OK;
}
int EnQueue(LinkQueue &Q,int e)
{QueuePtr p;
p=(QueuePtr)malloc(sizeof(N0de));
p->data=e;
p->next=Q.rear->next;
Q.rear->next=p;
Q.rear=p;
return OK;
}
int DeQueue(LinkQueue &Q,int &e)
{ QueuePtr p;
if(Q.rear->next==Q.rear)
return 0;
p=Q.rear->next->next;
e=p->data;
Q.rear->next->next=p->next;
if(Q.rear==p)
{
Q.rear->next=Q.rear->next->next; Q.rear=Q.rear->next;
}
free(p);
return OK;
}
void main()
{LinkQueue Q;
int i,e,n;
InintQueue(Q);
printf("input the number of the data:");
scanf("%d",&n);
for(i=0;i {printf("enter the queue:"); scanf("%d",&e); EnQueue(Q,e); } printf("input the number of the datas to out:"); scanf("%d",&n); for(i=0;i { printf("output first data in the queue:"); DeQueue(Q,e); printf("%d\n",e); } } 测试结果 第 4 页 共 4 页 六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 注：内容一律使用宋体五号字，单倍行间距 了解栈和队列的一些特性；栈和队列的存储结构及实现方式，具体做实验还是有很大难度的，调试试验过程遇到了一些问题。
