数据结构上机指导书-实验一.doc

数据结构与算法
实验指导书

中国石油大学(北京)计算机科学与技术系

前 言
《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。
一、实验目的
更好的理解算法的思想、培养编程能力。
二、实验要求
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
清华大学出版社（影印版）

实验平台
控制台程序

1、启动Microsoft VC6.0集成开发环境如图所示：

2、单击“文件”菜单，选择“新建”项。

3、选择“Win32 控制台应用程序”选项，如下图所示。

4、在D盘建立文件夹“Test1”，并键入工程名“TestList”。

5、单击“OK”按钮，进入下图界面。

6、选择“An empty project”选项后，点击“Finish”按钮，进入下图界面。

7、单击“文件”菜单，选择“新建”项，如下图所示。

8、在弹出的窗口选择“C/C++HeaderFile”，在名称框内输入“SeqList”，如下图所示。

9、单击“添加”按钮后，进入如下界面。

10、将“实验一”中顺序表定义键入文件SeqList.h中。

11、单击“文件”菜单，选择“新建”项，如下图所示。

12、在弹出的窗口选择“C++ SourceFile”，在名称框内输入“TestSeqList”，如下图所示。

13、将“实验一”中顺序表测试文件代码键入TestSeqList.cpp中。

14、调试并运行程序，完成实验内容1中的要求。

然后参照上述方法，建立链表类的LinkList.h文件和TestLinkList.cpp文件，然后完成实验内容2中的要求。

实验一 线性表的操作
实验类型：验证性
实验要求：必修
实验学时：2学时
一、实验目的：
参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。
二、实验要求：
1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，…，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。
2．设计一个带头结点的单链表类，要求：
1) 生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
2) 设计一个测试主函数，实际运行验证所设计单链表类的正确性。
*3．设计一个不带头结点的单链表类，要求：
1) 不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况。)
2) 设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。
*4．设计一个带头结点的循环双向链表类，要求：
1) 带头结点循环双向链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素。
2) 设计一个测试主函数，实际运行验证所设计循环双向链表类的正确性。
*5．设计一个单链表实现一元多项式求和问题。要求：
（1）设计存储结构表示一元多项式；
（2）设计算法实现一元多项式相加。

四、程序样例
1、顺序表类定义：将该类保存在文件SeqList.h中。
#if !defined SEQ_LIST
#define SEQ_LIST

#include
using namespace std;

const int MaxSize=100; //100只是示例性的数据，可根据实际问题具体定义
template //定义模板类SeqList
class SeqList
{
public:
SeqList( ) {length=0;} //无参构造函数
SeqList(T a[ ], int n); //有参构造函数
~SeqList( ) { } //析构函数为空
int Length( ) {return length;} //求线性表的长度
T Get(int i); //按位查找，取线性表的第i个元素
int Locate(T x ); //按值查找，求线性表中值为x的元素序号
void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素
T Delete(int i); //删除线性表的第i个元素
void PrintList(); //遍历线性表，按序号依次输出各元素
private:
T data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};

template
SeqList::SeqList(T a[ ], int n)
{
if (n>MaxSize) throw "参数非法";
for (int i=0; i
T SeqList::Get(int i)
{
if (i<1 && i>length) throw "查找位置非法";
else return data[i-1];
}

template
int SeqList::Locate(T x)
{
for (i=0; i
void SeqList::Insert(int i, T x)
{
if (length>=MaxSize) throw "上溢";
if (i<1 | | i>length+1) throw "位置";
for (j=length; j>=i; j--)
data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处
data[i-1]=x;
length++;
}

template
T SeqList::Delete(int i)
{
if (length==0) throw "下溢";
if (i<1 || i>length) throw "位置";
T x=data[i-1];
for (int j=i; j
length--;
return x;
}

template
void SeqList :: PrintList( )
{
for (int i = 0; i < length; i++)
cout << data[i]<<" "; //依次输出线性表的元素值
}
#endif

2、顺序表测试，新建TestSeqList.cpp文件。
#include "SeqList.h"
void main( )
{
int r[]={1,2,3,4,5,6,7,8,9,10};
SeqList a(r,50);
cout<<"执行删除操作前数据为："<
using namespace std;

template
struct Node
{
T data
Node *next; //此处也可以省略
};

template
class LinkList
{
public:
LinkList( ){first=new Node; first->next=NULL;} //建立只有头结点的空链表
LinkList(T a[ ], int n); //建立有n个元素的单链表
~LinkList( ); //析构函数
int Length( ); //求单链表的长度
T Get(int i); //取单链表中第i个结点的元素值
int Locate(T x); //求单链表中值为x的元素序号
void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点
T Delete(int i); //在单链表中删除第i个结点
void PrintList( ); //遍历单链表，按序号依次输出各元素
private:
Node *first; //单链表的头指针
};

template
LinkList:: ~LinkList( )
{
Node<T> *p=first; //工作指针p初始化
while (p) //释放单链表的每一个结点的存储空间
{
Node *q=p; //暂存被释放结点
p=p->next; //工作指针p指向被释放结点的下一个结点，使单链表不断开
delete q;
}
}

template
T LinkList::Get(int i)
{
p=first->next; j=1; //或p=first; j=0;
while (p && jnext; //工作指针p后移
j++;
}
if (!p) throw "位置";
else return p->data;
}

template
void LinkList::Insert(int i, T x)
{
p=first ; j=0; //工作指针p初始化
while (p && jnext; //工作指针p后移
j++;
}
if (!p) throw "位置";
else {
s=new Node; s->data=x; //向内存申请一个结点s，其数据域为x
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
}
}

template
T LinkList::Delete(int i)
{
p=first ; j=0; //工作指针p初始化
while (p && jnext;
j++;
}
if (!p | | !p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在
else {
q=p->next; x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q;
return x;
}
}

template
LinkList:: LinkList(T a[ ], int n)
{
first=new Node;
first->next=NULL; //初始化一个空链表
for (int i=0; i *s=new Node;
s->data=a[i]; //为每个数组元素建立一个结点
s->next=first->next; //插入到头结点之后
first->next=s;
}
}

template
void LinkList :: PrintList( )
{

}

#endif

4、链表测试，新建TestLinkList.cpp文件。
#include "LinkList.h"
void main( )
{
int r[ ]={1,-2,3,-4,-5,6,-7,8,9,10};
LinkList List(r, 10);
cout<<"执行操作前数据为："<
void LinkList :: divid ( )