数据结构与算法
第二次实验报告
姓名：许恺
学号：2014011329
班级：计算机14-1
中国石油大学(北京)计算机科学与技术系
前 言
《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。
一、实验目的
更好的理解算法的思想、培养编程能力。
二、实验要求
1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。
2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。
3、实验结束后总结实验内容、书写实验报告。
4、遵守实验室规章制度、不缺席、按时上、下机。
5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣 10 分。
6、实验报告有一次不合格，扣 5 分，两次以上不合格者，平时成绩以零分记。
三、实验环境 VC++6.0 或者 VC2010
四、说明
1、本实验的所有算法中元素类型可以根据实际需要选择。
2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成 70%，否则实验不合格）。
3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。
五、实验报告的书写要求
1．明确实验的目的及要求；
2．记录实验的输入数据和输出结果；
3．说明实验中出现的问题和解决过程；
4．写出实验的体会和实验过程中没能解决的问题；
六、参考书目《数据结构》（C++语言描述） 王红梅等 清华大学出版社《DATA STRUCTURE WITH C++》 William Ford,William Topp 清华大学出版社（影印版）
实验二 栈、队列、串的操作
实验类型：验证性
实验要求：必修
实验学时： 2 学时
一、实验目的：
参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表
类实现有关串的操作。
二、实验要求：
1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1. 堆栈类测试和应用问题。要求：
(1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素 1,2,3,4,5 入栈，然后出栈堆栈中的数据元素并在屏幕上显示。
(2)定义数据元素的数据类型为如下形式的结构体：
typedef struct
{ char taskname[10];//任务名
int taskno; //任务号
｝DataType；
设计一个包含 5 个数据元素的测试数据，并设计一个主函数实现依次把 5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。
2. 队列类测试和应用问题。要求：
设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素 1,2,3,4,5 入队，然后出队中的数据元素并在屏幕上显示。
3．设计串采用顺序存储结构，编写函数实现两个串的比较 Compare(S, T)。要求比较结果有大于、等于和小于三种情况。
*4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。
*5. 设计串采用静态数组存储结构，编写函数实现串的替换 Replace(S, start, T, V)，即要求在主串 S 中，从位置 start 开始查找是否存在子串 T，若主串 S 中存在子串T，则用子串 V 替换子串 T，且函数返回 1；若主串 S 中不存在子串 T，则函数返回０。并要求设计主函数进行测试。一个测试例子为：S＝”I am a student”，T=”student”，V=”teacher “。
四、实验操作计划
实验第一部分（25 分钟） ：
一．源代码：
1.LinkStackMain.cpp文件
#include <iostream>
using namespace std;
#include "LinkStack.h"
void main( )
{
LinkStack<int>a;
if (a.Empty( ))
{
cout<<"栈空，执行操作"<<endl;
cout<<"对 10 进行压栈操作:"<<endl;
try
{
a.Push(10);
}
catch(char* wrong)
{
cout<<wrong;
}
cout<<"读取栈顶元素:"<<endl;
cout<<a.GetTop( )<<endl;
cout<<"对 15 栈进行压栈操作:"<<endl;
try
{
a.Push(15);
}
catch(char* wrong)
{
cout<<wrong;
}
cout<<"读取栈顶元素: ";
cout<<a.GetTop( )<<endl;
cout<<"进行出栈操作:"<<endl;
a.Pop( );
cout<<"读取栈顶元素:"<<endl;
cout<<a.GetTop( )<<endl;
}
else{
cout<<"栈不空"<<endl;
}
//a.~LinkStack( );
}
2.LinkStack.h文件
#ifndef LINKSTACK_H
#define LINKSTACK_H
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class LinkStack
{
public:
LinkStack( );
~LinkStack( );
void Push(T x);
T Pop( );
bool Empty( );
T GetTop( );
private:
Node<T> *top;
Node<T> *head;
};
template <class T>
LinkStack<T>::LinkStack( )
{
head=new Node<T>;
head->next=NULL;
top = head->next;
}
template <class T>
LinkStack<T>::~LinkStack()
{
Node <T> *p=head;
Node <T> *q;
while(p)
{
q=p;
p=p->next;
delete q;
}
delete p;
}
template<class T>
void LinkStack<T>::Push(T x)
{
Node<T> *p;
p=new Node<T>;
p->data=x;
p->next=NULL;
if(top==NULL)
{
top=p;
head->next = p;
}
else
{
top->next=p;
top=p;
}
}
template <class T> T LinkStack<T>::Pop( )
{
T x;
Node<T> *p= head;
if (top==head) throw "下溢";
while(p->next!=top)
p=p->next;
x=p->data;
top=p;
return x;
}
template <class T>
T LinkStack<T>::GetTop( )
{
if (top!=NULL)
return top->data;
else return NULL;
}
template <class T>
bool LinkStack<T>::Empty( )
{
if(top==NULL)
return 1;
else
return 0;
}
#endif;
3.SeqStackMain.cpp文件
/*#include <iostream>
using namespace std;
#include "SeqStack.h"
void main()
{
SeqStack<int> a;
if (a.Empty( ))
{
cout<<"栈空,执行入栈操作:"<<endl;
cout<<"对 15 和 10 执行入栈操作:"<<endl;
try
{
a.Push(15);
a.Push(10);
}
catch(char* wrong)
{
cout<< wrong;
}
cout<<"栈顶元素为:"<<endl;
cout<<a.GetTop( )<<endl;
cout<<"执行出栈操作:"<<endl;
cout<<a.Pop( )<<endl;
cout<<"栈顶元素为:"<<endl;
cout<<a.GetTop( )<<endl;
}
else{
cout<<"栈不空"<<endl;
}
}*/
4.SeqStack.h文件
#ifndef SEQSTACK_H
#define SEQSTACK_H
const int StackSize=10;
template <class T>
class SeqStack
{
public:
SeqStack( ) ;
~SeqStack( );
void Push(T x);
T Pop( );
T GetTop( );
bool Empty( );
private:
T data[StackSize];
int top;
};
template <class T>
SeqStack<T>::SeqStack( )
{
top=-1;
}
template <class T>
SeqStack<T>::~SeqStack( )
{
}
template <class T>
void SeqStack<T>::Push(T x)
{
if (top== StackSize-1) throw "上溢";
top++;
data[top]=x;
}
template <class T>
T SeqStack<T>::Pop( )
{
T x;
if (top==-1) throw "下溢";
x=data[top--];
return x;
}
template <class T>
T SeqStack<T>::GetTop( )
{
if (top!=-1)
return data[top];
}
template <class T>
bool SeqStack<T>::Empty( )
{
if(top==-1) return 1;
else return 0;
}
#endif
二．运行程序贴图：
三．报告总结：
报告并不难，只是连老师给的代码太考验我们了，我知道可能是老师故意设的陷阱，也费了不少时间修改原来的代码。主要问题出在了析构函数的使用，其实程序结束会自动调用的，但是，我却又调了一遍，导致报错。嗯，就这些。
（真是后悔当时怎么没有多写点注释和报告总结，可是现在让我写现在的总结同样还是不会写的很详细，人类真的是很烦的物种。。。）