《数据结构》实验指导（一）

实验一 线性表

一、 实验目的

线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。

（1）掌握线性表的顺序存储结构； （2）验证顺序表及其基本操作的实现；

（3）掌握数据结构及算法的程序实现的基本方法。 （4）掌握线性表的链接存储结构； （5）验证单链表及其基本操作的实现；

（6）进一步掌握数据结构及算法的程序实现的基本方法。 二、实验示例学习——顺序表操作 实验要求：

（1）建立含有若干个元素的顺序表；

（2）对已建立的顺序表实现插入、删除、查找等基本操作。 实现提示：

首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。

const int MaxSize=10;

template //定义模板类SeqList class SeqList {

public:

SeqList( ){length=0;} //无参构造函数 SeqList(T a[ ], int n); //有参构造函数

void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素

int Locate(T x ); //按值查找，求线性表中值为x的元素序号 void PrintList( ); //遍历线性表，按序号依次输出各元素 private:

T data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 };

其次，建立含有n个数据元素的顺序表，即设计构造函数。算法如下： template

SeqList:: SeqList(T a[ ], int n) {

if (n>MaxSize) throw \参数非法\ for (i=0; i

最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。

（1）插入算法 template

1

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++; }

（2）删除算法 template T SeqList::Delete(int i) {

if (length==0) throw \下溢\ if (i<1 | | i>length) throw \位置\ x=data[i-1];

for (j=i; j

data[j-1]=data[j]; //注意此处j已经是元素所在的数组下标 length--; return x; }

（3）查找算法 template int SeqList::Locate(T x) {

for (i=0; i

if (data[i]==x) return i+1; //下标为i的元素等于x，返回其序号i+1 return 0; //退出循环，说明查找失败 }

实验程序：

// 以下为头文件，文件名为SeqList.h #ifndef SeqList_H #define SeqList_H

const int MaxSize=100; //100只是示例性的数据，可以根据实际问题具体定义template //定义模板类SeqList class SeqList {

public:

SeqList( ){length=0;} //无参构造函数，创建一个空表 SeqList(T a[ ], int n); //有参构造函数

void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素

int Locate(T x); //按值查找，求线性表中值为x的元素序号 void PrintList( ); //遍历线性表，按序号依次输出各元素 private:

T data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 };

2

#endif

// 以下为SeqList类中成员函数的定义部分，文件名为SeqList.cpp #include \ template

SeqList:: SeqList(T a[ ], int n) {

if (n>MaxSize) throw \参数非法\; for (int i=0; i

template

void SeqList::Insert(int i, T x) {

if (length>=MaxSize) throw \上溢\; if (i<1 || i>length+1) throw \位置\; for (int 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

data[j-1]=data[j]; //注意此处j已经是元素所在的数组下标 length--; return x; }

template

int SeqList::Locate(T x) {

for (int i=0; i

if (data[i]==x) return i+1 ; //下标为i的元素等于x，返回其序号i+1 return 0; //退出循环，说明查找失败 }

template

3

void SeqList::PrintList( ) {

for (int i=0; i

// 以下为主函数，所在文件名为SeqListMain.cpp

#include //引用输入输出流库函数的头文件 #include\ //引用顺序表的类声明和定义 using namespace std;

void main( ) {

int r[ ]={1, 2, 3, 4, 5}; SeqList a(r, 5);

cout<<\执行插入操作前数据为：\<

a.Insert(2,3); }

catch (char *s) {

cout<

cout<<\执行插入操作后数据为：\<

cout<

a.Delete(1); //删除元素1 }

catch (char *s) {

cout<

cout<<\删除后数据为：\<

a.PrintList( ); //输出所有元素 }

三、实验题目

4

题目1. 单链表操作 实验要求：

（1）用头插法（或尾插法）建立带头结点的单链表；

（2）对已建立的单链表实现插入、删除、查找等基本操作。 实现提示：

首先，将单链表中的结点定义为如下结构类型： template struct Node {

T data;

Node *next;

};

其次，定义单链表的数据类型——单链表类LinkList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出单链表的元素。

template class LinkList {

public:

LinkList(T a[ ], int n); //建立有n个元素的单链表 ~LinkList( ); //析构函数

void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点 T Delete(int i); //在单链表中删除第i个结点 int Locate(T x); //求单链表中值为x的元素序号

void PrintList(); //遍历单链表，按序号依次输出各元素 private:

Node *first; //单链表的头指针 };

再次，设计单链表类LinkList的构造函数和析构函数。

（1）用头插法或尾插法建立单链表。头插法建立单链表的算法如下： template

LinkList< T>:: LinkList(T a[ ], int n) {

first=new Node;

first->next=NULL; //初始化一个空链表 for (i=0; i

s=new Node; s->data=a[i]; //为每个数组元素建立一个结点 s->next=first->next; //插入到头结点之后 first->next=s; } }

（2）析构函数用于释放单链表中所有结点，算法如下：

template

LinkList< T>:: ~LinkList( ) {

5

p=first; //工作指针p初始化

while (p) //释放单链表的每一个结点的存储空间 {

q=p; //暂存被释放结点

p=p->next; //工作指针p指向被释放结点的下一个结点，使单链表不断开 delete q; } }

最后，对所建立的单链表设计插入、删除、查找等基本操作的算法。 （1）插入算法

template

void LinkList::Insert(int i, T x) {

p=first; j=0; //工作指针p初始化 while (p && j

p=p->next; //工作指针p后移 j++; }

if (!p) throw \位置\ else {

s=new Node; s->data=x; //向内存申请一个结点s，其数据域为x s->next=p->next; //将结点s插入到结点p之后 p->next=s; } }

（2）删除算法

template T LinkList::Delete(int i) {

p=first ; j=0; //工作指针p初始化

while (p && j

p=p->next; j++; }

if (!p | | !p->next) throw \位置\ //结点p不存在或结点p的后继结点不存在 else {

q=p->next; x=q->data; //暂存被删结点 p->next=q->next; //摘链 delete q; return x; } }

（3）查找算法

template

int LinkList< T>:: Locate(T x) {

p=first->next; j=1;

while (p && p->data!=x)

6

{

p=p->next; //工作指针p后移 j++; }

if (p) return j; else return 0; }

题目2：数组的循环移位

问题描述：

对于一个给定的整型数组循环左移i位。 基本要求：

（1）在原数组中实现循环左移，不另外申请空间； （2）时间性能尽可能好； （3）分析算法的时间复杂度。 设计思想

将这个问题看作是把数组ab转换成数组ba（a代表数组的前i个元素，b代表数组中余下的n-i个元素），先将a逆置得到arb，再将b逆置得到arbr，最后将整个arbr逆置得到(arbr)r=ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3个位置的过程如下： Reverse(0, i-1); //得到cbadefgh Reverse(i, n-1); //得到cbahgfed

Reverse(0, n-1); //得到defghabc. 算法描述：

循环左移算法：

void Converse(int A[ ], int n, int i) {

Reverse(A, 0, i-1); //前i个元素逆置 Reverse(A, i, n-1); //后n-i个元素逆置 Reverse(A, 0, n-1); //整个数组逆置 }

void Reverse(int A[ ], int from, int to) //将数组A中元素从from到to逆置 {

for (i=0; i<(to-from+1)/2; i++)

A[from+i]←→A[to-i]; //交换元素

}

题目3：约瑟夫环问题

问题描述：

约瑟夫问题的一种描述：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。

方法1．报数为m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从1报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和姓名。

方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用

7

无头结点的单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。

基本要求：

下面给出了方法1的程序作为示例，请编写方法2的程序并上机测试。

【方法1的程序清单】 #include using namespace std;

struct NodeType // 结点的结构定义 { int num; // 编号子域 char name[20]; // 姓名子域 NodeType *next; // 指针域 };

class Jose //类声明 { private: NodeType *Head; public:

Jose( ){ Head=new NodeType; // 为头结点申请空间

Head->next=Head; // 头结点Head 形成空环 }; ~Jose(){ }; void creat(); void outs(); };

void Jose::creat()// 建成约瑟夫环 { int i=0, n;

NodeType *newp, *pre; pre= Head;

cout<<\输入总人数 n=\; cin>>n;

for(i=0;i

{ newp=new NodeType; // 申请数据元素结点空间 newp->num=i+1; // 结点送值（号码） cout<<\编号\<>newp->name; // 读入姓名 newp->next=Head; pre->next=newp;

pre=newp; // 形成循环链表 }

pre->next= Head->next; delete Head; // 删除附加头结点Head Head=pre->next; // 头指针指向第一个数据元素结点 }

void Jose::outs( ) //约瑟夫问题的方法1 { int m,i; NodeType *q=Head, *p;

cout<<\ 输入m值(m>=2)\; cin>>m;

8

cout<<\ 根据m值，开始报数输出：\<next!=q)

{ for(i=1;inext;} // 报数到第m个人

cout<<\编号：\<num<<\ 姓名：\<name<next=q->next; delete q; // 第m个人出列 q=p->next; }

cout<<\编号：\<num<<\ 姓名：\<name<

int main() { Jose h;

h.creat(); return 0; }

// 主函数 h.outs(); 9

本文来源：https://www.bwwdw.com/article/zuor.html