数据结构实验报告1

实验一线性表姓名：谢焘班级：物联网工程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