实验四  循环链表

一、实验目的与要求

1）熟悉循环链表的类型定义和基本操作；

2）灵活应用循环链表解决具体应用问题。

二、实验内容

题目一：有n个小孩围成一圈，给他们从1开始依次编号，从编号为1的小孩开始报数，数到第m个小孩出列，然后从出列的下一个小孩开始重新报数，数到第m个小孩又出列，……如此反复直到所有的小孩全部出列为止，求整个出列序列，例如：当n=6,m=5 时的出列序列是5,4,6,2,3,1 . 

题目二：围绕着山顶有10个洞，一只狐狸和一只兔子住在各自的洞里。狐狸想吃掉兔子。一天，兔子对狐狸说：“你想吃我有一个条件，先把洞从1－10编上号，你从10号洞出发，先到1号洞找我；第二次隔1个洞找我，第三次隔2个洞找我（第一次看1号洞，第二次看3号洞，第三次看6号洞），以后依次类推，次数不限，若能找到我，你就可以饱餐一顿。不过在没有找到我以前不能停下来。”狐狸满口答应，就开始找了。它从早到晚进了100次洞，也没找到兔子，请问，兔子可能躲在几号洞里，打印输出所有安全洞的编号。（使用一个循环单链表解决问题）

三、实验结果

1）请将调试通过的源代码粘贴在下面。（代码注意书写规范、主要模块要有功能注释）

题目一源代码：

#include <cstdio>
#include <malloc.h>
#include <iostream>
using namespace std;

typedef struct node{
	int no;//小孩编号
	struct node *next;		
}child;

//创建无头结点
void createlist(child *&head, int n){
	int i;
	child *p,*tail;//指向新建循环单链表的尾结点
	head=(child*)malloc(sizeof(child));
	head->no=1;//建立no为1结点的单链表
	tail=head;
	for(i=2;i<=n;i++){
		p=(child*)malloc(sizeof(child));
		p->no=i;//建立一个存放编号i的结点
		tail->next=p;
		tail=p;//将p结点链到末尾
	}
	tail->next=head;//构成一个首结点为head的循环单链表
}

//求出列顺序（约瑟夫问题） 
void joseph(int n,int m){
	//n->总数 m->出列数 
	int i,j; 
	child *head,*p,*q;
	createlist(head,n);//初始化列表 
	
	//出列n个小孩
	for(i=1;i<=n;i++){
		p=head; 
		j=1;
		//从head结点开始报数，报到第m-1个结点
		while(j<m-1){
			j++;//报数递增
			p=p->next;//移到下一个结点
		}
		q=p->next;//q指向第m个结点
		cout<<q->no<<" ";//该结点出列
		p->next=q->next;
		free(q);//删除q结点（出列结点） 
		head=p->next;//从下一个结点重新开始
	}
}

int main(){
	int n,m;//n->总数 m->出列数
	cin>>n>>m;
	joseph(n,m);
	return 0;
}

题目一结果展示：

 

 题目二源代码：

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

//创建结点 
typedef struct node{
    int a,b;//a为安全洞的标记，b为洞的序号
    struct node *next;
}node;

//主函数->find safe holes
int main(){
    node *p,*q;
    p=(node*)malloc(sizeof(node));
    p->b=1;
    p->a=1;
    q=p;//记录头结点 
     
    int i=0;
    while(i<9){
    	//创建十个结点 
        p->next=(node*)malloc(sizeof(node));
        p=p->next;//移动到下一个新结点 
        p->b=i+2;//洞的序号
        p->a=0;
        i++;
    }
    p->next=q;//构建循环 
    p=p->next;//回到头结点 
    
    //寻找安全洞并标记狐狸洞（进100次洞） 
    for(i=0;i<100;i++){
    	int j;
    	int temp=(i+2)%10;//序号归类为1-10 
        for(j=0;j<temp;j++){
            p=p->next;
        }
		p->a=1;//标记狐狸洞 
    }
    
    //输出安全洞 
    for(i=0;i<10;i++){
        if(p->a==0){
        	//非兔子洞已经进行标记 
        	cout<<"可能在第"<<p->b<<"个洞里面"<<endl;
		}
        p=p->next;//遍历，移动到下一个结点 
    }
    return 0;
}

题目二结果展示：

 

2）请分析你程序中每个功能模块的算法时间复杂度。

题目一：

构建含有n个元素的循环链表。时间复杂度为O(n)。

本段代码由两层循环构成。内层循环通过从head结点开始报数，报到第m-1个结点，此时寻找到第m个结点（利用第m-1个结点的后继结点）并删除。外层循环在每剔除一个结点后再一次进行遍历。时间复杂度为O(n²)。

题目二：

构建含有n个元素的循环链表，a为安全洞的标记，b为洞的序号。时间复杂度为O(n)。

本段代码由两层循环构成。内层循环通过题目所给的狐狸进洞的规律，对其所有进入过的洞进行标记（即a=1），便于后续锁定兔子安全洞的位置。外层循环为题目所给的狐狸进洞的总次数（即100次进洞寻找兔子），并继承上一次进洞的位置。时间复杂度为O(n²)。

通过之前化简进洞的序号，本段代码利用遍历输出安全洞的位置，即通过从开始的结点中遍历，寻找a标记为0的结点序号并输出。时间复杂度为O(n)。

---

 其他参考：

#include<iostream>
using namespace std;

// 定义结构体 
struct CLNode  
{
	int num;
	CLNode *next;
};
// 初始化链表 
void Initlist(CLNode *&L){  //注意引用！！！ 
	L=new CLNode;
	L->next=L;
}
// 创建链表元素
void Creatlist(CLNode *&L,int n){
	CLNode *p=L;
	for(int i=1;i<=n;i++){
		CLNode *q=new CLNode;
		q->num=i;
		q->next=L;   //循环链表的指针指向 
		p->next=q;
		p=q;
	}
}
// 输出链表元素
void Outlist(CLNode *&L){
	CLNode *p=L;
	cout<<"输出小孩序号如下："<<endl; 
	while(p->next!=L){
		p=p->next;
		cout<<p->num<<" ";
	}
	cout<<endl; 
}
// 输出出列序列
void Output(CLNode *&L,int m){
	CLNode *p=L->next;
	CLNode *pre=L;//定义pre指针以便删除元素操作 
	for(int i=1;i<=m;){
		if(p->next==L){
			if(p->next->next==L)//循环结束条件 
			break;
			else{
				pre=pre->next->next;
				p=p->next->next;
			}
		}
		else{
			pre=pre->next;
			p=p->next;
		}
		i++;
		if(i==m){
			cout<<p->num<<" ";
			pre->next=p->next;
			CLNode *q=p;
			p=p->next;
			q->next=NULL;
			delete q;
			if(p!=L) //注意条件！ 
			i=1;
			else
			i=0;  //注意避开头结点 
		}
	}
}
// 释放空间 
void Destroylist(CLNode *&L){
	 delete L;//删除头结点 
}

int main(){
	CLNode *L;       //定义头指针 
	Initlist(L);     //初始化链表 
	
	int n,m;
	cout<<"请输入小孩的总人数："<<endl;
	cin>>n; 
	Creatlist(L,n);  //插入链表元素 
	
	Outlist(L);      //输出链表元素 
	
	cout<<"请输出出列序号："<<endl;
	cin>>m;
	cout<<"当n="<<n<<"，m="<<m<<"时的出列序号为："<<endl;
	Output(L,m);    //根据序号输出依次链表元素 
	Destroylist(L);//释放空间 
}

#include<iostream>
using namespace std;
// 定义结构体
struct CLNode  
{
	int num;
	CLNode *next;
};
// 初始化链表
void Initlist(CLNode *&L){  //注意引用！！！ 
	L=new CLNode;
	L->next=L;
}
// 创建链表元素
void Creatlist(CLNode *&L,int n){
	CLNode *p=L;
	for(int i=1;i<=n;i++){
		CLNode *q=new CLNode;
		q->num=i;
		q->next=L;   //循环链表的指针指向 
		p->next=q;
		p=q;
	}
}
// 输出链表元素 
void Outlist(CLNode *&L){
	CLNode *p=L;
	cout<<"输出山洞序号如下："<<endl; 
	while(p->next!=L){
		p=p->next;
		cout<<p->num<<" ";
	}
	cout<<endl; 
}
// 寻找安全洞 
void Safenum(CLNode *&L){
	cout<<"安全洞的编号可能为："<<endl;
	CLNode *p=L;
	int a[101];    //储存被循环到的链表元素 
	int i=1;
	while(i<=100){   //使循环次数足够多 
		for(int j=0;j<i;j++){
			if(p->next==L)
			p=p->next->next;
			else
			p=p->next;
		}
		a[i-1]=p->num;
		i++;
	}
	for(int j=1;j<=10;j++){
		for(i=0;i<100;i++){
	    	if(a[i]==j)
	    	break;
    	} 
    	if(i>=100)
    	cout<<j<<" ";
	}
}
// 释放空间
void Destroylist(CLNode *&L){
	CLNode *p=L->next;
	while(p!=L){ //除了头结点的所有结点 
		CLNode *q=p;
		p=p->next;
		q->next=NULL;
		delete q;
	}
	 delete p;//删除头结点 
}

int main(){
	CLNode *L;       //定义头指针 
	Initlist(L);     //初始化链表 

	Creatlist(L,10);  //插入链表元素 
	
	Outlist(L);      //输出链表元素 
	
	Safenum(L);    //找到安全洞 
	Destroylist(L);//释放空间 
}