实验1-链表及其应用.doc

实验1 链表及其应用
一、实验目的
1. 加深对线性表链式存储结构的理解；
2. 熟练掌握单链表类的描述方法及操作的C++实现；
3. 掌握链表结构的应用；
4. 加强对算法设计能力和程序调试能力的培养。
二、实验学时：建议2~4学时
三、基本知识（略）
四、实验内容
实验内容1 单链表的基本操作
1 问题描述
设计一个带表头结点的单链表类，实现单链表的创建、输出、插入、删除、查找、销毁等操作。
2 数据结构设计
根据问题要求，采用单链表存储结构存储线性表。在头文件LinkList.h中定义。
（1） 结点结构
template<class T>
struct Node //结点结构
{ T data; //结点数据
Node*link;
Node(){ link=NULL;}
Node(T e,Node*next=NULL)
{ data=e;
link=next;
}
};
（2） 单链表类
单链表类的数据成员主要有单链表的头指针，根据要求其成员函数有构造、输出、插入、删除、查找、销毁等操作。
template<class T>
class LinkList //带表头结点的单链表类
{ private:
Node<T> *head; //链表指针
public:
LinkList(); //构造带表头结点的空单链表
LinkList(T data[],int mSize);//构造有mSize个元素的单链表
~LinkList(){Clear();} //析构函数
bool Insert(int pos,const T&x); //在单链表第pos个元素前插入元素x
bool Remove(int pos, T&x); //删除单链表第pos个元素
bool Replace(int pos,const T&x); //将修改单链表第pos个元素为x
int Length()const; //求表长
bool IsEmpty() const ; //判空操作
void Clear() ; //清空操作
void Output() const ; //输出链表
bool search(const T&x) const;//查找元素x在表中是否存在
}; // Class LinkList
3 算法设计与实现
（1） 构造函数
#include"Linklist.h"
template<class T>
LinkList<T>::LinkList() //构造函数1
{ //创建带表头结点的空单链表
head=new Node<T>;//创建表头结点
}
template<class T>
LinkList<T>::LinkList(T data[],int mSize) //构造函数2
{ //创建具有mSize个元素的带表头结点单链表
//用尾插法创建单链表
Node<T> *p,*r;
head= p=new Node<T>;//创建表头结点，p指针指向当前单链表的最后一个结点
for(int i=0;i<mSize;i++)
{
r=new Node<T>(data[i]);
p->link=r; //链接到p指针所指结点之后
p=p->link; //p指针后移
}
}

（2） 插入操作
a) 插入原理：（在p所指结点之后插入s所指结点。）

在进行插入操作时，要先确定待插入结点（s所指结点）的link指针（s->link）指向，再修改链表指针（p->link）指向，如图1.1和图1.2所示,即
s->link= p->link;
p->link=s;
b) 算法描述：（在单链表的第pos个元素之前插入元素x）
① 若pos<1，则插入失败，结束；
② 扫描单链表，寻找单链表中第pos-1个元素结点的指针p；
③ 若p存在（p非空）则在其后插入，操作成功，否则不能插入。
c) 算法实现
template<class T>
bool LinkList<T>::Insert(int pos,const T&x)
{ //在单链表的第pos个元素之前插入元素x，插入成功返回true,否则返回false。
if(pos<1) //插入位置不合法
return false;
Node<T> *s,*p=head;
int i=0; // i是计数器
while(p && i<pos-1)//找第pos-1个元素结点的指针front
{
p=p->link;
i++;
}
if(!p) //插入位置不合法
return false;
s=new Node<T>(x,p->link);
s->data=x;
s->link= p->link;//确定待插入结点（s所指结点）的link指针（s->link）指向
p->link=s; //修改链表中的指针（p->link）指向
return true;
}
（3） 删除操作
a) 删除原理：（删除p所指结点的后继结点s，如下图所示。）

在进行删除操作时，直接修改链表指针（p->link）指向，即
p->next =s->next;
b) 算法步骤：（删除单链表中的第pos个元素）
① 若pos<1，则删除失败，结束；
② 在单链表中找第pos -1个元素结点的指针p；
③ 若p和p->link均非空，则删除p->link所指结点，否则删除失败。
c) 实现
template<class T>
bool LinkList<T>::Remove(int pos,T&x) //删除单链表的第pos个元素，并置入x
{
if(pos<1) //删除位置不合法
return false;
Node<T> *current,*p=head;
int i=0;// i是计数器
while(p->link && i<pos-1)//找第pos-1个元素结点的指针
{
p=p->link;
i++;
}
if(!p->link) //删除位置不合法,pos大于表长
return false;
current=p->link; // current指向被删除结点
p->link=current->link; //修改链表指针
x= current->data;
delete current;
return true;
}
（4） 输出链表
template<class T>
void LinkList<T>::Output() const //输出链表
{
Node<T> *current=head->link;// current指向首元结点
while(current)//依次扫描链表结点
{
cout<<current->data<<" ";
current=current->link;
}
cout<<endl;
}
（5） 单链表清空操作
template<class T>
void LinkList<T>::Clear() //清空操作，将各元素结点空间释放，单链表为空表
{
Node<T> *current=head->link; // current指向首元结点
while(current!=NULL) //依次扫描链表结点，并逐个释放空间
{
Node<T> *r=current;
current=current->link;
delete r;
}
head->link =NULL; //单链表为空
}
（6） 单链表查找
template<class T>
bool LinkList<T>::search(const T&x)//查找元素x在表中是否存在
{
Node<T> *current=head->link;
while(current&&)//查找
if(current->data==x)
break;
else
current=current->link; //指针后移
return current!=NULL;
}
4 测试
（1）测试代码
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#include"Linklist.h"
void menu()//模拟菜单选项
{
cout<<"--------------------------------------------------------"<<endl;
cout<<"| 1____________输出链表 |"<<endl;
cout<<"| 2____________插入元素 |"<<endl;
cout<<"| 3____________删除元素 |"<<endl;
cout<<"| 4____________销毁链表 |"<<endl;
cout<<"| 5____________查找 |"<<endl;
cout<<"| 0____________退出系统 |"<<endl;
cout<<"--------------------------------------------------------"<<endl;
}
const int N=10;
void main()
{
srand(time(NULL));//以系统当前时间初始化随机数发生器
int data[N];
for(int i=0;i<N;i++)
data[i]=rand()%100;//用随机数发生器产生100以内的整数
LinkList<int> L(data,N);//创建N个元素的单链表
menu();
while(1) //模拟菜单工作方式
{
int select;
cout<<"请输入您的选择："; cin>>select;
switch(select)
{
case 1: //输出单链表
L.Output();
break;
case 2: //插入
int pos,elem;
cout<<"请输入插入位置："; cin>> pos;
cout<<"插入元素："; cin>>elem;
if(L.Insert(pos,elem)) //插入成功
cout<<"在第"<< pos <<"个元素前成功插入"<<elem<<endl;
else //插入失败
cout<<"插入位置不合法！"<<endl;
break;
case 3: //删除
cout<<"请输入删除位置："; cin>>pos;
int x;
if(L.Remove(pos,x))//删除单链表的第pos个元素
cout<<"单链表的第"<< pos <<"个元素"<<x<<"已被删除。"<<endl;
else
cout<<"删除位置不合法！"<<endl;
break;
case 4: //销毁链表
char OK;
cout<<"确定要销毁链表吗？（y/n）"<<endl; cin>>OK;
if(OK=='y'||OK=='Y') L.Clear();
break;
case 5: //查找
cout<<"请输入查找元素："<<endl; cin>>elem;
if(L.search(elem))
cout<<"查找成功！"<<endl;
else
cout<<"查找失败！"<<endl;
break;
case 0: //退出
return;
default:
cout<<"您输入的选项有误，请重新输入：";
}
}
}
（2）测试用例

5扩展提高
（1） 删除链表中所有值为x的元素结点；
（2） 单链表类的拷贝构造函数设计；
（3） 随机数使用方法；
（4） 单链表的销毁操作。

内容2 约瑟夫（Joseph）环问题
1 问题描述
约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从某人开始，从1起，报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止，最后一人称为优胜者。求优胜者的编号。
2 数据结构设计
对于n个人的编号（1，2，…，n）可用线性表进行组织，因是n个人按顺时针方向围坐一圈，故可用循环链表存储方式存储，要设计循环链表类和约瑟夫环类。
首先要解决好约瑟夫环类和循环链表类的关系问题，二者关系可以有三种处理方式：一是循环链表类作为约瑟夫环类的基类；二是约瑟夫环类中含有循环链表类的一个对象作为其成员；三是循环链表仅作为约瑟夫环类求优胜者操作的过程中所借助的手段，即作为为约瑟夫环类求优胜者编号成员函数int GetWinner()的局部变量来处理。这里仅以第三种方式为例给出设计过程。
（1） 循环链表结点结构
template<class T>
struct Node //结点结构
{
T data; //结点数据
Node*link;
Node(){ link=NULL;}
Node(T e,Node*next=NULL)
{
data=e;
link=next;
}
};
（2） 循环链表类
循环链表类主要提供构造、输出、插入、删除、查找、后移、销毁等操作，其数据成员主要有循环链表的头指针（其实指向循环链表中任一结点的指针均可，故设置current）。
template<class T>
class CircleLinkList
{ //不带表头结点的循环链表类
private:
Node<T> *current,*front; //current指向某结点，front指向current前驱
public:
CircleLinkList ():current(NULL),front(NULL){} //构建空循环链表
CircleLinkList (T *d,int mSize); //利用d数组元素构建循环链表
~ CircleLinkList (); //析构函数
bool InsertAfter(const T&x); //在current所指结点之后插入x
bool RemoveCurrent(T&x); //删除current所指结点
void movenext(int n=1); //current后移n次
T GetCurrentData(){return current->data;}
bool toLocatioin(T &t);//让current指向t结点，若没有则current不移动
void Output() const ; //输出循环链表
}; // Class CircleLinkList

（3） 约瑟夫环类
约瑟夫环类提供构造和设置圈中人数numOfBoy（编号为1~numOfBoy）、报数起始点startPosition、报数间隔interval，并能由此求得最终优胜者。
class Joseph // 约瑟夫环类
{
private:
int numOfBoy; //圈中人数
int startPosition; //报数起始点
int interval; //报数间隔
public:
Joseph(int boys,int start,int m):
numOfBoy(boys),startPosition(start),interval(m){}//构造函数
void setNumOfBoy(int num){numOfBoy=num;}//重置圈中人数
void setStartPosition(int start){startPosition=start;}//重置起始点
void setInterval(int inter){interval=inter;}//重置报数间隔
int GetWinner();//求得最终优胜者编号
void print(); //输出约瑟夫环
};
3 算法设计与实现
（1） 求约瑟夫环优胜者
a) 原理：

根据总人数numOfBoy建立编号分别为1~numOfBoy的循环链表，如上图所示，设立一个报数器，先找到报数起始点，然后从起始点开始，从1开始报数，报到间隔interval则出圈（即删除该结点），如此下去，直到循环链表中只有一个元素为止，最后一个元素即为优胜者。
b) 算法步骤：
① 给定圈中人数numOfBoy、报数起始点startPosition、报数间隔interval；
② 以编号1~numOfBoy创建循环链表；
③ 找到报数起始结点startPosition；
④ 当圈中人数大于1时，重复做：
从当前结点依次从1报到interval，则删除当前结点，并将当前指针指向下一结点。
⑤ 返回圈中最后剩下的人的编号。
c) 实现
int Joseph::GetWinner()//获得最终优胜者
{
CircleLinkList<int> boys;
for(int i=0;i<numOfBoy;i++)//创建循环链表,编号依次为1~numOfBoy
{
int temp=i+1;
boys.InsertAfter(temp);
}
boys.toLocatioin(startPosition); //找到报数起点
cout<<endl<<"依次出列的小孩是："<<endl;
for(i=1;i<numOfBoy;i++) //numOfBoy-1个小孩出圈
{
int x;
boys.movenext(interval-1); //报数
boys.RemoveCurrent(x); //出圈
cout<<x<<" "; //输出出圈编号
}
return boys.GetCurrentData(); //返回优胜者编号
}
（2） 输出约瑟夫环
void Joseph::print() //输出约瑟夫环
{
cout<<"圈中人数:"<< numOfBoy<<endl;
cout<<"报数起始点:"<< startPosition <<endl;
cout<<"报数间隔:"<< interval <<endl;
}
（3） 构造循环链表
template<class T>
CircleLinkList<T>::CircleLinkList(T *d,int mSize)
{ //构造函数,将d数组中的mSize个元素创建循环链表
//采用前插法创建。
int i;
Node<T> *p;
current=new Node<T>;
current->data=d[mSize-1];
front=current;
for(i=mSize-2;i>=0;i--)
{
p=new Node<T>(d[i],current);
current=p;
}
front->link=current;
}
（4） 析构循环函数
template<class T>
CircleLinkList<T>::~CircleLinkList() //析构函数
{
while(current!=front)//销毁循环链表
{
Node<T> *r=current;
current=current->link;
delete r;
}
delete current;
}
（5） 循环链表插入操作
template<class T>
bool CircleLinkList<T>::InsertAfter(const T&x)
//在current所指结点之后插入x,current指向x结点
{
Node<T> *s=new Node<T>(x);
if(!s)return false;
if(!current) //原循环链表为空
current=front=s->link=s;
else //原循环链表非空
{
s->link=current->link;
current->link=s;
front=current;
current=s;
}
return true;
}
（6） 循环链表删除操作
template<class T>
bool CircleLinkList<T>::RemoveCurrent(T&x) //删除current所指结点
{
if(!current)//循环链表为空
return false;
x=current->data;
if(current==front)//链表中只有一个元素
{
delete current;
current=front=NULL;
}
else
{
front->link=current->link;//修改链表指针
delete current;
current=front->link;
}
return true;
}
（7） 循环链表输出
template<class T>
void CircleLinkList<T>::Output() const //输出循环链表
{
if(!current)//循环链表为空
return ;
Node<T> *p=current;
do
{
cout<<p->data<<" ";
p=p->link;
}while(p!=current);
cout<<endl;
}
（8） 循环链表后移操作
template<class T>
void CircleLinkList<T>:: movenext(int k) //current后移k次
{
for(int i=1;i<=k;i++)
{
front=current; // front后移
current=current->link; //current后移
}
}
（9） 循环链表定位操作
template<class T>
bool CircleLinkList<T>:: toLocatioin(T &t)
//将current指向元素为t的结点，若没有则current不移动
{
if(!current)//循环链表为空
return false;
Node<T> *current1=current,*front1=front;
while(current1->data!=t) //寻找元素t
{
front1=current1;
current1=current1->link;
if(current1==current)// 已寻找一圈没有元素为t的结点
return false;
}
current=current1; //current指向元素为t的结点
front=front1;
return true;
}
4 测试
（1）测试代码
void main()
{
int total,interv,startboy;
cout<<"请输入初始数据：小孩数，起始小孩号码，间隔数：\n";
cin>>total>>startboy>>interv;
Joseph jose(total,startboy,interv);
jose.print();
cout<<"优胜者编号为： "<<jose.GetWinner()<<endl;
}
（2）测试结果

5 扩展提高
（1） 约瑟夫问题的改进算法：在人数n、k及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码Ki（整数），留作其出圈后下一次的报到间隔Ki。密码Ki可用随机数产生。这样事前无法确定谁是最后一人。
（2） 约瑟夫问题的报数方法若采用顺时针报数和逆时针报数交替进行，则如何设计数据结构？
内容3 多项式的存储和运算
1 问题描述
建立带表头结点的链式多项式类，并设计算法实现多项式的求值、相加、相减等运算。
2 数据结构设计（略）
3 算法设计与实现（略）
4 选做内容 多项式的减法、乘法及除法运算，计算多项式在给定点处的函数值。
5 问题思考
建立不带表头结点的链表,与带表头结点的链表在操作实现上有何差异?