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

PAGEPAGE4实验一线性表实验目的线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。（1）掌握线性表的顺序存储结构；（2）验证顺序表及其基本操作的实现；（3）掌握数据结构及算法的程序实现的基本方法。（4）掌握线性表的链接存储结构；（5）验证单链表及其基本操作的实现；（6）进一步掌握数据结构及算法的程序实现的基本方法。二、实验示例学习——顺序表操作实验要求：（1）建立含有若干个元素的顺序表；（2）对已建立的顺序表实现插入、删除、查找等基本操作。实现提示：首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。constintMaxSize=10;template<classT>//定义模板类SeqListclassSeqList{public:SeqList(){length=0;}//无参构造函数SeqList(Ta[],intn);//有参构造函数voidInsert(inti,Tx);//在线性表中第i个位置插入值为x的元素TDelete(inti);//删除线性表的第i个元素intLocate(Tx);//按值查找，求线性表中值为x的元素序号voidPrintList();//遍历线性表，按序号依次输出各元素private:Tdata[MaxSize];//存放数据元素的数组intlength;//线性表的长度};其次，建立含有n个数据元素的顺序表，即设计构造函数。算法如下：template<classT>SeqList::SeqList(Ta[],intn){if(n>MaxSize)throw"参数非法";for(i=0;i<n;i++)data[i]=a[i];length=n;}最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。（1）插入算法template<classT>voidSeqList::Insert(inti,Tx){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<classT>TSeqList::Delete(inti){if(length==0)throw"下溢";if(i<1||i>length)throw"位置";x=data[i-1];for(j=i;j<length;j++)data[j-1]=data[j];//注意此处j已经是元素所在的数组下标length--;returnx;}（3）查找算法template<classT>intSeqList::Locate(Tx){for(i=0;i<length;i++)if(data[i]==x)returni+1;//下标为i的元素等于x，返回其序号i+1return0;//退出循环，说明查找失败}实验程序：//以下为头文件，文件名为SeqList.h#ifndefSeqList_H#defineSeqList_HconstintMaxSize=100;//100只是示例性的数据，可以根据实际问题具体定义template<classT>//定义模板类SeqListclassSeqList{public:SeqList(){length=0;}//无参构造函数，创建一个空表SeqList(Ta[],intn);//有参构造函数voidInsert(inti,Tx);//在线性表中第i个位置插入值为x的元素TDelete(inti);//删除线性表的第i个元素intLocate(Tx);//按值查找，求线性表中值为x的元素序号voidPrintList();//遍历线性表，按序号依次输出各元素private:Tdata[MaxSize];//存放数据元素的数组intlength;//线性表的长度};题目1.单链表操作实验要求：（1）用头插法（或尾插法）建立带头结点的单链表；（2）对已建立的单链表实现插入、删除、查找等基本操作。实现提示：首先，将单链表中的结点定义为如下结构类型：template<classT>structNode{Tdata;Node<T>*next;};其次，定义单链表的数据类型——单链表类LinkList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出单链表的元素。template<classT>classLinkList{public:LinkList(Ta[],intn);//建立有n个元素的单链表~LinkList();//析构函数voidInsert(inti,Tx);//在单链表中第i个位置插入元素值为x的结点TDelete(inti);//在单链表中删除第i个结点intLocate(Tx);//求单链表中值为x的元素序号voidPrintList();//遍历单链表，按序号依次输出各元素private:Node<T>*first;//单链表的头指针};再次，设计单链表类LinkList的构造函数和析构函数。（1）用头插法或尾插法建立单链表。头插法建立单链表的算法如下：template<classT>LinkList<T>::LinkList(Ta[],intn){first=newNode<T>;first->next=NULL;//初始化一个空链表for(i=0;i<n;i++){s=newNode<T>;s->data=a[i];//为每个数组元素建立一个结点s->next=first->next;//插入到头结点之后first->next=s;}}（2）析构函数用于释放单链表中所有结点，算法如下：template<classT>LinkList<T>::~LinkList(){p=first;//工作指针p初始化while(p)//释放单链表的每一个结点的存储空间{q=p;//暂存被释放结点p=p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开deleteq;}}最后，对所建立的单链表设计插入、删除、查找等基本操作的算法。（1）插入算法template<classT>voidLinkList::Insert(inti,Tx){p=first;j=0;//工作指针p初始化while(p&&j<i-1){p=p->next;//工作指针p后移j++;}if(!p)throw"位置";else{s=newNode<T>;s->data=x;//向内存申请一个结点s，其数据域为xs->next=p->next;//将结点s插入到结点p之后p->next=s;}}（2）删除算法template<classT>TLinkList::Delete(inti){p=first;j=0;//工作指针p初始化while(p&&j<i-1)//查找第i-1个结点{p=p->next;j++;}if(!p||!p->next)throw"位置";//结点p不存在或结点p的后继结点不存在else{q=p->next;x=q->data;//暂存被删结点p->next=q->next;//摘链deleteq;returnx;}}（3）查找算法template<classT>intLinkList<T>::Locate(Tx){p=first->next;j=1;while(p&&p->data!=x){p=p->next;//工作指针p后移j++;}if(p)returnj;elsereturn0;}题目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);//得到cbadefghReverse(i,n-1);//得到cbahgfedReverse(0,n-1);//得到defghabc.算法描述：循环左移算法：voidConverse(intA[],intn,inti){Reverse(A,0,i-1);//前i个元素逆置Reverse(A,i,n-1);//后n-i个元素逆置Reverse(A,0,n-1);//整个数组逆置}voidReverse(intA[],intfrom,intto)//将数组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报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用无头结点的单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。基本要求：下面给出了方法1的程序作为示例，请编写方法2的程序并上机测试。【方法1的程序清单】#include<iostream>usingnamespacestd;structNodeType//结点的结构定义{intnum;//编号子域charname[20];//姓名子域NodeType*next;//指针域};classJose//类声明{private:NodeType*Head;public:Jose(){Head=newNodeType;//为头结点申请空间Head->next=Head;//头结点Head形成空环};~Jose(){};voidcreat();voidouts();};voidJose::creat()//建成约瑟夫环{inti=0,n;NodeType*newp,*pre;pre=Head;cout<<"\n输入总人数n=";cin>>n;for(i=0;i<n;i++)//循环{newp=newNodeType;//申请数据元素结点空间newp->num=i+1;//结点送值（号码）cout<<"\n编号"<<i+1<<"的人姓名=";cin>>newp->name;//读入姓名newp->next=Head;pre->next=newp;pre=newp;