线性表的相关操作数据结构实验报告第二个

谁借莪１个温暖的怀抱￠ 2022-08-10 12:55 175阅读 0赞

实验内容：约瑟夫（Joseph)问题的一种描述是：编号为1，2，……，n的n个人按顺序…………………………。

利用循环链表为存储结构模拟此过程，按照出列的顺序输出依次出列人的编号。

我写出来的代码如下：（在这里为了读者的理解方便，我写出了我的一点点注释）

/********************************************************************
    **************************内江师范学院*******************************
    *********************************************************************
    *********************************************************************
    *************************计算机科学学院******************************
    *********************************************************************
    *********************************************************************
    **************************-by puhaiyang******************************
    *********************************************************************
    *********************************************************************
    ****************************2013级3班********************************
    ********************************************************************/
    
    #include<iostream>
    using namespace std;
    #define M 5 //定义一个报数上限值
    #define MAX 20//定义总人数，即题目中的n
    typedef struct node//链表的结构体
    {
    	int data;
    	struct node * next;
    }NODE,*PNODE; 
    int lenth = 0;//定义一个链表的长度，开始时为0。因为链表里还没有放值
    PNODE create_list()//创建链表的函数,主要是创建头结点
    {
    	PNODE pHead = new NODE;
    	pHead->data=1;
    	pHead->next = NULL;
    	lenth=1; 
    	return pHead;
    }
    void insert_data(PNODE pHead)//插入其他结点的函数
    {
    	PNODE pTail = new NODE;
    	pTail = pHead;
    	int i=2;//因为头结点里的data的值为1，所以这里从2开始
    	while(i<=MAX)
    	{
    		PNODE pNew = new NODE;
    		pNew->data=i;
    		pNew->next=NULL;
    		pTail->next=pNew;
    		pTail=pNew;
    		i++;
    		lenth++;//每插入一个结点，链表的长度加1
    	}
    	pTail->next=pHead;
    	
    }
    void show_list(PNODE pHead)//显示总链表的函数
    {
    	PNODE pTemp = pHead;
    	while(pTemp->next!=pHead)
    	{
    		cout<<pTemp->data<<endl;
    		pTemp=pTemp->next;
    	}
    	cout<<pTemp->data<<endl;
    }
    void myFun(PNODE pHead)//模拟Joseph过程的函数，这是主要的
    {
    	PNODE pTemp = pHead;
    	PNODE pTempt = NULL;
    	int i = 1;
    	while(1)
    	{
    		while(i<=M-2)//在这里实现计数
    		{
    			cout<<"Now Data:"<<pTemp->data<<endl;
    			pTemp=pTemp->next;
    			i++;
    		}
    		cout<<"Now Data:"<<pTemp->data<<endl;
    		_sleep(1000);//为了演示的方便，用系统的sleep函数来实现一点等待效果
    
    		pTempt = pTemp->next;
    
    
    		cout<<"pop:..............."<<pTempt->data<<endl;
    		lenth--;//每出列一个，长度减1
    		pTemp->next=pTempt->next;
    		pTemp=pTempt->next;
    		if(lenth==0)break;//当长度为0时，值全部出列完了，就不再操作了
    		
    
    		i=1;
    		
    	}
    	
    }
    void main()
    {
    	PNODE pHead=create_list();
    	insert_data(pHead);
    	show_list(pHead);
    	cout<<"lenth:"<<lenth<<endl;
    	myFun(pHead);
    }

这个总体来说这个比较简单。很容易实现。只是我的这种是笨办法。因为我找不出来啥高级的方法。

对于更好的实验模拟，我们可以加入随机数生成函数。这样模拟操作就更逼真了。

我们可以这样实现：

在代码中去掉上面的两条宏定义语句，用这两条随机数生成函数代替就好

int M = rand()%5+1;//生成1到5之间的随机数  
int MAX = rand()%100+1; //生成1到100之间的随机数