html5模板下载,胶州网站优化价格,网站设计 广州,动漫制作专业学什么实验四 循环链表
一、实验目的与要求
1#xff09;熟悉循环链表的类型定义和基本操作#xff1b;
2#xff09;灵活应用循环链表解决具体应用问题。
二、实验内容
题目一#xff1a;有n个小孩围成一圈#xff0c;给他们从1开始依次编号#xff0c;从编号为1的小孩开…实验四 循环链表
一、实验目的与要求
1熟悉循环链表的类型定义和基本操作
2灵活应用循环链表解决具体应用问题。
二、实验内容
题目一有n个小孩围成一圈给他们从1开始依次编号从编号为1的小孩开始报数数到第m个小孩出列然后从出列的下一个小孩开始重新报数数到第m个小孩又出列……如此反复直到所有的小孩全部出列为止求整个出列序列例如当n6,m5 时的出列序列是5,4,6,2,3,1 . 题目二围绕着山顶有10个洞一只狐狸和一只兔子住在各自的洞里。狐狸想吃掉兔子。一天兔子对狐狸说“你想吃我有一个条件先把洞从110编上号你从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-no1;//建立no为1结点的单链表tailhead;for(i2;in;i){p(child*)malloc(sizeof(child));p-noi;//建立一个存放编号i的结点tail-nextp;tailp;//将p结点链到末尾}tail-nexthead;//构成一个首结点为head的循环单链表
}//求出列顺序约瑟夫问题
void joseph(int n,int m){//n-总数 m-出列数 int i,j; child *head,*p,*q;createlist(head,n);//初始化列表 //出列n个小孩for(i1;in;i){phead; j1;//从head结点开始报数报到第m-1个结点while(jm-1){j;//报数递增pp-next;//移到下一个结点}qp-next;//q指向第m个结点coutq-no ;//该结点出列p-nextq-next;free(q);//删除q结点出列结点 headp-next;//从下一个结点重新开始}
}int main(){int n,m;//n-总数 m-出列数cinnm;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-b1;p-a1;qp;//记录头结点 int i0;while(i9){//创建十个结点 p-next(node*)malloc(sizeof(node));pp-next;//移动到下一个新结点 p-bi2;//洞的序号p-a0;i;}p-nextq;//构建循环 pp-next;//回到头结点 //寻找安全洞并标记狐狸洞进100次洞 for(i0;i100;i){int j;int temp(i2)%10;//序号归类为1-10 for(j0;jtemp;j){pp-next;}p-a1;//标记狐狸洞 }//输出安全洞 for(i0;i10;i){if(p-a0){//非兔子洞已经进行标记 cout可能在第p-b个洞里面endl;}pp-next;//遍历移动到下一个结点 }return 0;
}题目二结果展示 2请分析你程序中每个功能模块的算法时间复杂度。
题目一 构建含有n个元素的循环链表。时间复杂度为O(n)。 本段代码由两层循环构成。内层循环通过从head结点开始报数报到第m-1个结点此时寻找到第m个结点利用第m-1个结点的后继结点并删除。外层循环在每剔除一个结点后再一次进行遍历。时间复杂度为O(n²)。 题目二 构建含有n个元素的循环链表a为安全洞的标记b为洞的序号。时间复杂度为O(n)。 本段代码由两层循环构成。内层循环通过题目所给的狐狸进洞的规律对其所有进入过的洞进行标记即a1便于后续锁定兔子安全洞的位置。外层循环为题目所给的狐狸进洞的总次数即100次进洞寻找兔子并继承上一次进洞的位置。时间复杂度为O(n²)。 通过之前化简进洞的序号本段代码利用遍历输出安全洞的位置即通过从开始的结点中遍历寻找a标记为0的结点序号并输出。时间复杂度为O(n)。 其他参考
#includeiostream
using namespace std;// 定义结构体
struct CLNode
{int num;CLNode *next;
};
// 初始化链表
void Initlist(CLNode *L){ //注意引用 Lnew CLNode;L-nextL;
}
// 创建链表元素
void Creatlist(CLNode *L,int n){CLNode *pL;for(int i1;in;i){CLNode *qnew CLNode;q-numi;q-nextL; //循环链表的指针指向 p-nextq;pq;}
}
// 输出链表元素
void Outlist(CLNode *L){CLNode *pL;cout输出小孩序号如下endl; while(p-next!L){pp-next;coutp-num ;}coutendl;
}
// 输出出列序列
void Output(CLNode *L,int m){CLNode *pL-next;CLNode *preL;//定义pre指针以便删除元素操作 for(int i1;im;){if(p-nextL){if(p-next-nextL)//循环结束条件 break;else{prepre-next-next;pp-next-next;}}else{prepre-next;pp-next;}i;if(im){coutp-num ;pre-nextp-next;CLNode *qp;pp-next;q-nextNULL;delete q;if(p!L) //注意条件 i1;elsei0; //注意避开头结点 }}
}
// 释放空间
void Destroylist(CLNode *L){delete L;//删除头结点
}int main(){CLNode *L; //定义头指针 Initlist(L); //初始化链表 int n,m;cout请输入小孩的总人数endl;cinn; Creatlist(L,n); //插入链表元素 Outlist(L); //输出链表元素 cout请输出出列序号endl;cinm;cout当nnmm时的出列序号为endl;Output(L,m); //根据序号输出依次链表元素 Destroylist(L);//释放空间
}#includeiostream
using namespace std;
// 定义结构体
struct CLNode
{int num;CLNode *next;
};
// 初始化链表
void Initlist(CLNode *L){ //注意引用 Lnew CLNode;L-nextL;
}
// 创建链表元素
void Creatlist(CLNode *L,int n){CLNode *pL;for(int i1;in;i){CLNode *qnew CLNode;q-numi;q-nextL; //循环链表的指针指向 p-nextq;pq;}
}
// 输出链表元素
void Outlist(CLNode *L){CLNode *pL;cout输出山洞序号如下endl; while(p-next!L){pp-next;coutp-num ;}coutendl;
}
// 寻找安全洞
void Safenum(CLNode *L){cout安全洞的编号可能为endl;CLNode *pL;int a[101]; //储存被循环到的链表元素 int i1;while(i100){ //使循环次数足够多 for(int j0;ji;j){if(p-nextL)pp-next-next;elsepp-next;}a[i-1]p-num;i;}for(int j1;j10;j){for(i0;i100;i){if(a[i]j)break;} if(i100)coutj ;}
}
// 释放空间
void Destroylist(CLNode *L){CLNode *pL-next;while(p!L){ //除了头结点的所有结点 CLNode *qp;pp-next;q-nextNULL;delete q;}delete p;//删除头结点
}int main(){CLNode *L; //定义头指针 Initlist(L); //初始化链表 Creatlist(L,10); //插入链表元素 Outlist(L); //输出链表元素 Safenum(L); //找到安全洞 Destroylist(L);//释放空间
}
