版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验一线性表姓名:谢焘班级:物联网工程192学号:1930110689实验时间:2020.10.5一、约瑟夫问题1.问题描述设有编号为1,2,...,n(n>0)的n个人围成一圈,从约定编号k(1≤k≤n)开始报数,报到m的人出圈,然后从他的下一位开始新一轮报数。如此反复下去,直至所有人出圈。当任意给定n和m时,设计算法求n个人出圈的次序。2.数据结构设计采用循环单链表,可建立如下的结构体:structNode{ intdata; Node*next;};3.功能划分及算法设计规定的主要功能有创建无头节点的循环单链表、节点的删除与输出。(1)创建无头节点的循环单链表(尾插法)p=newNode; p->next=p; p->data=1; for(inti=2;i<=n;i++) { s=newNode;//新建元素结点 s->data=i;//输入新建数据元素值 s->next=p->next;//新结点链入表尾 p->next=s; p=s; }(2)节点的删除与输出Node*Delete_Print(Node*p,Node*pre)//删除、输出函数{ Node*q; cout<<p->data<<"";//输出需要删除的节点的数值 while(p->next!=pre)//p定位到删除点的前驱 { p=p->next;// } { q=p->next;//暂存删除结点位置 p->next=q->next;//从链表中摘除删除结点 deleteq;//释放删除点 returnp->next; }}4.运行与测试(1)运行程序,提示输入n,m,k,如图所示:(2)分别输入7、5、1,结果如下:5.调试记录及收获调试过程中经常会遇到与预计的删除节点偏差1-2个节点的情况,主要原因是:(1)链表创建完成后指针P未归位(2)删除节点后指针P任然停留在原节点的前驱(3)循环操作时计数器重置数设置错误通过本次实验掌握并练习了循环单链表的创建与部分操作,进一步加深对单链表的认识,提高了实践操作水平。6.源程序#include<iostream.h>//cout,cinstructNode{ intdata; Node*next;};Node*Delete_Print(Node*p,Node*pre)//删除、输出函数{ Node*q; cout<<p->data<<"";//输出需要删除的节点的数值 while(p->next!=pre)//p定位到删除点的前驱 { p=p->next;// } { q=p->next;//暂存删除结点位置 p->next=q->next;//从链表中摘除删除结点 deleteq;//释放删除点 returnp->next; }}voidmain(){ Node*p,*s,*pre; intm,n,k; cout<<"请依次输入人数n,密码m,起报人数k"<<endl; cin>>n>>m>>k; //创建循环单链表(尾插法) p=newNode; p->next=p; p->data=1; for(inti=2;i<=n;i++) { s=newNode;//新建元素结点 s->data=i;//输入新建数据元素值 s->next=p->next;//新结点链入表尾 p->next=s; p=s; } //初始化 p=p->next; i=1; while(i<=k){ pre=p; p=p->next; i++; }//定位起报人 intcount=2; while(pre!=p){ if(count==m) { p=Delete_Print(p,p); count=1;//计数器重置 }else{ count++; pre=p; p=p->next; } } Delete_Print(p,p);//删除并输出最后一个节点}二、有序表合并1.问题描述把两个有序表归为一个有序表2.数据结构设计采用单链表存储两个有序表,合并后的表采用带头结点的单链表存储。structNode{ intdata;//数据域,存放表元素 Node*next;//指针域,指向下一个结点};3.算法设计规定的主要功能有创建有序顺序表的函数,实现归并功能的函数、显示表内容的函数。(1)创建单链表Node*CreateList(){ Node*Head; Head=newNode; Head->next=NULL; returnHead;}(2)键盘输入有序单链表voidCinList(Node*Head){ Node*p=Head,*s; intn; cout<<"请输入元素个数:"; cin>>n; cout<<"请按序输入有序表的元素:"<<endl; for(inti=1;i<=n;i++) { s=newNode;//新建元素结点 cin>>s->data;//输入新建数据元素值 s->next=p->next;//新结点链入表尾 p->next=s; p=s; }}(3)实现并归功能voidSort(Node*pa,Node*pb,Node*pc){//实现并归功能 Node*p; while(pa!=NULL&&pb!=NULL){ p=newNode; p->next=pc->next; pc->next=p; pc=p; if(pa->data<=pb->data) { pc->data=pa->data; pa=pa->next; } else { pc->data=pb->data; pb=pb->next; } } if(pa==NULL){ while(pb!=NULL){ p=newNode; p->next=pc->next; pc->next=p; pc=p; pc->data=pb->data; pb=pb->next; } } else{ while(pa!=NULL){ p=newNode; p->next=pc->next; pc->next=p; pc=p; pc->data=pa->data; pa=pa->next; } }}(4)输出显示表内容oidListDisplay(Node*Head){ //遍历显示链表 Node*p;//设置工作指针 p=Head->next;//从首元结点开始遍历 inti=1;//元素位序 while(p) { cout<<p->data<<"\t"; p=p->next; i++; } cout<<endl;}4.运行与测试运行程序,多次数据测试,部分结果如下:5.调试记录及收获调试过程中,需要注意生成新结点插入到表尾的操作顺序,否则会出现表内容为空等状况,且编译器无法发现异常,需要手动排查。通过本次的实验练习,掌握了有序表合并的操作,对于尾插法掌握得更加熟练,对于单链表有了更深的理解6.源程序#include<iostream.h>structNode{ intdata;//数据域,存放表元素 Node*next;//指针域,指向下一个结点};Node*CreateList(){ Node*Head; Head=newNode; Head->next=NULL; returnHead;}voidCinList(Node*Head){ Node*p=Head,*s; intn; cout<<"请输入元素个数:"; cin>>n; cout<<"请按序输入有序表的元素:"<<endl; for(inti=1;i<=n;i++) { s=newNode;//新建元素结点 cin>>s->data;//输入新建数据元素值 s->next=p->next;//新结点链入表尾 p->next=s; p=s; }}voidListDisplay(Node*Head){ //遍历显示链表 Node*p;//设置工作指针 p=Head->next;//从首元结点开始遍历 inti=1;//元素位序 while(p) { cout<<p->data<<"\t"; p=p->next; i++; } cout<<endl;}voidSort(Node*pa,Node*pb,Node*pc){//实现并归功能 Node*p; while(pa!=NULL&&pb!=NULL){ p=newNode; p->next=pc->next; pc->next=p; pc=p; if(pa->data<=pb->data) { pc->data=pa->data; pa=pa->next; } else { pc->data=pb->data; pb=pb->next; } } if(pa==NULL){ while(pb!=NULL){ p=newNode; p->next=pc->next; pc->next=p; pc=p; pc->data=pb->data; pb=pb->next; } } else{ while(pa!=NULL){ p=newNode; p->next=pc->next; pc->next=p; pc=p; pc->data=pa->data; pa=pa->next; } }}voidmain(void){ Node*LA,*LB,*LC,*pa,*pb,*pc; LA=CreateList();LB=CreateList(); cout<<"创建表1"<<endl;Ci
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年金融资产管理公司行业市场需求预测报告及未来五至十年创新突破与热点迁移
- 2026年特岗分章节模拟试题及答案
- 2026年反违章培训模拟试卷带答案
- 2026年土方班组安全培训模拟试题及答案
- 2026年城市更新与历史建筑保护考试带答案
- 2026年全国各地语文教材课文赏析模拟试题及参考答案
- 2026年理科自主招生模拟试题及参考答案
- 2026年中职类单招模拟试题带答案
- 2026年科目四模拟试题内容考法及参考答案
- 2026年教师安全培训模拟试题及参考答案
- 橡胶制品模具维护管理制度
- 2026年新教材统编版九年级上册语文期末复习:古诗词理解性默写 专项测试卷(含答案)
- YMO数学竞赛2024秋季七年级复赛真题试卷含答案解析可打印
- T8联考2027届高三10月检测训练英语试题(含答案详解)
- 武汉产业投资控股集团有限公司招聘笔试题库2026
- ISO 9001-2026 换版深度解读:36条条款逐条对比与企业换版行动指南
- 人教版五年级上册语文第七单元第22课《白鹭》第2课时教学课件(新教材)
- 26新五(上)语文课后生字词情景默写
- 关于学生思想政治教育问题的调研报告2026(3篇)
- 九年级物理上册《改变世界的热机》单元复习教学设计(教科版2024)
- 2026-2030中国甲醛市场前景预判与供需平衡状况监测研究报告
评论
0/150
提交评论