文档介绍：淮海工学院计算机科学系
实验报告书
课程名: 《数据结构》
题目: 线性数据结构实验
班级:
学号:
姓名:
评语:
成绩: 指导教师:
批阅时间: 年月日
线性表算法实现与应用报告要求
1目的与要求:
1)掌握栈与队列的数据类型描述及特点;
2)掌握栈的顺序和链式存储存表示与基本算法的实现;
3)掌握队列的链式和循环存储表示与基本操作算法实现;
4) 掌握栈与队列在实际问题中的应用和基本编程技巧;
5)按照实验题目要求,独立完成实际程序的编写编写、调试和运行,并通过用例数的运行过程抓获相关屏面验证程序设计的正确性;
7)认真书写实验报告,并在下周一以前按时提交。
2 实验内容或题目
(一)必做题:
1、实现顺序栈的创建(初始化)、压入(插入)、弹出(删除)操作,要求给出栈的操作变化过程;
2、实现链栈的创建(初始化)、压入(插入)、弹出(删除)操作,要求给出栈的操作变化过程;
3、实现循环队列的创建、进队、出队等基本操作,并实时给出队列的操作变化状态;
4、实现链式队列的创建、进队、出队等基本操作,并实时给出队列的操作变化状态;
(二) 选做题(有能力同学建议多做此类应用题目):
1、实现表达式求值算法;
2、用递归算法实现汉诺塔问题;
3、使用循环队列实现打印杨辉三角形算法。
3 实验步骤与源程序
第一题
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
#include <iostream>
using namespace std;
typedef struct
{
int elem[Stack_Size];
int top;
}SeqStack;
void InitStack(SeqStack *S)
{
S->top =-1;
}
int IsEmpty(SeqStack *S)
{
return(S->top==-1?TRUE:FALSE);
}
int IsFull(SeqStack *S)
{
return(S->top==Stack_Size-1?TRUE:FALSE);
}
int Push(SeqStack *S,int x)
{
if(S->top==Stack_Size-1)
return(FALSE);
S->top++;
S->elem[S->top] = x;
return(TRUE);
}
int Pop(SeqStack *S,int *x)
{
if(S->top == -1)
return(FALSE);
else
{
*x = S->elem[S->top];
S->top--;
return(TRUE);
}
}
int GetTop(SeqStack *S,int *x)
{
if(S->top == -1)
return(FALSE);
else
{
*x = S->elem[S->top];
return(TRUE);
}
}
int main()
{
SeqStack S;
int x;
int y;
int i;
InitStack(&S);
if(!IsFull(&S))
cout<<"栈为空"<<endl;
cout<<"输入要压入的元素:"<<endl;
for(i=0;i<10;i++)
{
cin>>y;
Push(&S,y);
}
GetTop(&S,&x);
cout<<"栈首元素:"<<endl;
cout<<x<<endl;
cout<<"弹出的元素为:"<<endl;
while(!IsEmpty(&S))
{
Pop(&S,&x);
cout<<x<<" ";
}
cout<<endl;
return 0;
}
第二题
#define TRUE 1
#define FALSE 0
#include<iostream>
using namespace std;
typedef struct node
{
int data;
struct node *next;
}LinkStackNode;
typedef LinkStackNode *LinkStack;
int GetTop(LinkStack top,int *x)
{
if(NULL==top->next )
return FALSE;
*x=top