1、1实验一 线性表一、 实验目的线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。（1）掌握线性表的顺序存储结构；（2）验证顺序表及其基本操作的实现；（3）掌握数据结构及算法的程序实现的基本方法。（4）掌握线性表的链接存储结构；（5）验证单链表及其基本操作的实现；（6）进一步掌握数据结构及算法的程序实现的基本方法。二、实验示例学习顺序表操作实验要求：（1）建立含有若干个元素的顺序表；（2）对已建立的顺序表
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
3、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; i 2void SeqList:Insert(int i, T x)if (length=MaxSize) throw “上溢“;if
4、(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; j int SeqList:Locate(T x)for (i=0; i /定义模板类SeqListclass SeqListpublic:SeqList( )length=0;
5、/无参构造函数，创建一个空表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; /线性表的长度;3#endif/ 以下为 SeqList 类中成员函数的定义部分，文件名为 SeqList.cpp#include “
6、SeqList.h“template SeqList: SeqList(T a , int n)if (nMaxSize) throw “参数非法“;for (int i=0; ivoid 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 (lengt
7、h=0) throw “下溢“;if (ilength) throw “位置“;T x=datai-1;for (int j=i; jint SeqList:Locate(T x) for (int i=0; i4void SeqList:PrintList( )for (int i=0; i /引用输入输出流库函数的头文件#include“SeqList.cpp“ /引用顺序表的类声明和定义using namespace std;void main( )int r =1, 2, 3, 4, 5;SeqList a(r, 5);coutstruct NodeT data;Node *next;
8、 ;其次，定义单链表的数据类型单链表类 LinkList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出单链表的元素。template class LinkListpublic: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(); /遍历单链表，按序号依次输
9、出各元素private:Node *first; /单链表的头指针;再次，设计单链表类 LinkList 的构造函数和析构函数。（1）用头插法或尾插法建立单链表。头插法建立单链表的算法如下：template LinkList: LinkList(T a , int n)first=new Node;first-next=NULL; /初始化一个空链表for (i=0; i; s-data=ai; /为每个数组元素建立一个结点s-next=first-next; /插入到头结点之后first-next=s;（2）析构函数用于释放单链表中所有结点，算法如下：template LinkList: L
10、inkList( )6p=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 /工作指针 p 后移j+;if (!p) throw “位置“;else s=new Node; s-data=x; /向内存申请一个结
11、点 s，其数据域为 xs-next=p-next; /将结点 s 插入到结点 p 之后p-next=s;（2）删除算法template T LinkList:Delete(int i)p=first ; j=0; /工作指针 p 初始化while (p 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=f
12、irst-next; j=1; while (p /工作指针 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 逆置得到(a rbr)r=ba。设 Reverse函数执行将数组元素逆置的操
13、作，对 abcdefgh 向左循环移动 3 个位置的过程如下：Reverse(0, i-1); /得到 cbadefghReverse(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) / 将数组
14、A 中元素从 from 到 to 逆置for (i=0; iusing 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(
15、)/ 建成约瑟夫环 int i=0, n;NodeType *newp, *pre;pre= Head;coutn;for(i=0;inum=i+1; / 结点送值（号码）coutnewp-name; / 读入姓名newp-next=Head;pre-next=newp;pre=newp; / 形成循环链表 pre-next= Head-next; delete Head; / 删除附加头结点HeadHead=pre-next; / 头指针指向第一个数据元素结点 void Jose:outs( ) /约瑟夫问题的方法1 int m,i; NodeType *q=Head, *p;9cout=2)“; cinm;coutnext!=q) for(i=1;inext; / 报数到第m个人coutnumnamenext=q-next; delete q; / 第m个人出列q=p-next;coutnumnameendl; / 输出最后一个结点的数据delete q; int main() / 主函数 Jose h;h.creat(); h.outs();return 0;
