《数据结构》实验指导(一)

实验一 线性表一、 实验目的线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。（1）掌握线性表的顺序存储结构； （2）验证顺序表及其基本操作的实现；（3）掌握数据结构及算法的程序实现的基本方法。（4）掌握线性表的链接存储结构；（5）验证单链表及其基本操作的实现；（6）进一步掌握数据结构及算法的程序实现的基本方法。二、实验示例学习顺序表操作实验要求：（1）建立含有若干个元素的顺序表；（2）对已建立的顺序表实现插入、删除、查找等基本操作。实现提示：首先定义顺序表的数据类型顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。const int MaxSize=10; template /定义模板类SeqListclass SeqListpublic: 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 dataMaxSize; /存放数据元素的数组 int length; /线性表的长度;其次，建立含有n个数据元素的顺序表，即设计构造函数。算法如下：template SeqList: SeqList(T a , int n) if (nMaxSize) throw 参数非法; for (i=0; in; i+) datai=ai; length=n;最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。（1）插入算法template void SeqList:Insert(int i, T x) if (length=MaxSize) throw 上溢; if (ilength+1) throw 位置;for (j=length; j=i; j-) dataj=dataj-1; /注意第j个元素存在数组下标为j-1处datai-1=x;length+;（2）删除算法template T SeqList:Delete(int i) if (length=0) throw 下溢; if (ilength) throw 位置; x=datai-1; for (j=i; jlength; j+) dataj-1=dataj; /注意此处j已经是元素所在的数组下标 length-; return x;（3）查找算法template int SeqList:Locate(T x) for (i=0; ilength; i+) if (datai=x) return i+1; /下标为i的元素等于x，返回其序号i+1 return 0; /退出循环，说明查找失败实验程序：/ 以下为头文件，文件名为SeqList.h#ifndef SeqList_H#define SeqList_Hconst int MaxSize=100; /100只是示例性的数据，可以根据实际问题具体定义template /定义模板类SeqListclass SeqListpublic: 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 dataMaxSize; /存放数据元素的数组 int length; /线性表的长度;#endif/ 以下为SeqList类中成员函数的定义部分，文件名为SeqList.cpp#include SeqList.htemplate SeqList: SeqList(T a , int n) if (nMaxSize) throw 参数非法; for (int i=0; in; i+) datai=ai; length=n;template void SeqList:Insert(int i, T x) if (length=MaxSize) throw 上溢; if (ilength+1) throw 位置; for (int j=length; j=i; j-) dataj=dataj-1; /注意第j个元素存在数组下标为j-1处 datai-1=x; length+;template T SeqList:Delete(int i) if (length=0) throw 下溢; if (ilength) throw 位置; T x=datai-1; for (int j=i; jlength; j+) dataj-1=dataj; /注意此处j已经是元素所在的数组下标 length-; return x;template int SeqList:Locate(T x) for (int i=0; ilength; i+) if (datai=x) return i+1 ; /下标为i的元素等于x，返回其序号i+1 return 0; /退出循环，说明查找失败template void SeqList:PrintList( ) for (int i=0; ilength; i+)coutdataiendl;/ 以下为主函数，所在文件名为SeqListMain.cpp#include /引用输入输出流库函数的头文件#includeSeqList.cpp /引用顺序表的类声明和定义using namespace std;void main( ) int r =1, 2, 3, 4, 5; SeqList a(r, 5); cout执行插入操作前数据为：endl; a.PrintList( ); /输出所有元素 try a.Insert(2,3); catch (char *s) coutsendl; cout执行插入操作后数据为：endl; a.PrintList( ); /输出所有元素 cout值为3的元素位置为:; couta.Locate(3)endl; /查找元素3，并返回在单链表中位置 cout执行删除第一个元素操作，删除前数据为：endl; a.PrintList( ); /输出所有元素 try a.Delete(1); /删除元素1 catch (char *s) coutsendl; cout删除后数据为：endl; a.PrintList( ); /输出所有元素三、实验题目题目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: LinkList(T a , int n) first=new Node; first-next=NULL; /初始化一个空链表 for (i=0; in; i+) s=new Node; s-data=ai; /为每个数组元素建立一个结点 s-next=first-next; /插入到头结点之后 first-next=s; （2）析构函数用于释放单链表中所有结点，算法如下：template LinkList: LinkList( ) 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 & jnext; /工作指针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 & jnext; 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: Locate(T x) p=first-next; j=1; while (p & p-data!=x) 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); /得到cbahgfedReverse(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+)Afrom+iAto-i; /交换元素 题目3：约瑟夫环问题问题描述：约瑟夫问题的一种描述：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。方法1报数为m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和姓名。方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用无头结点的单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。基本要求：下面给出了方法1的程序作为示例，请编写方法2的程序并上机测试。【方法1的程序清单】#includeusing namespace std;struct NodeType / 结点的结构定义 int num; / 编号子域 char name20; / 姓名子域 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; coutn; for(i=0;inum=i+1; / 结点送值（号码） coutn 编号i+1newp-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=2); cinm; coutn 根据m值，开始报数输出：next!=q) for(i=1;inext; / 报数到第m个人 cout编号：num 姓名：namenext=q-next; delete q; / 第m个人出列 q=p-next; cout编号：num 姓名：nameendl; / 输出最后一个结点的数据 delete q; int main() / 主函数 Jose h; h.creat(); h.outs(); return 0;9