第一篇:实验四 单链表及其应用(参考程序)
实验四 单链表的建立
一、实验目的
1.掌握线性表的链式存储结构——单链表的定义及C语言实现。2.掌握线性表在链式存储结构——单链表中的各种基本操作。
二、实验内容
1.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据分别按尾插入法和头插法来建立相应单链表。【知识要点】
为了便于实现各种运算,通常在单链表的第一个结点前增设一个附加结点,称为头结点,它的结构与表结点相同,其数据域可不存储信息,也可存储表长等附加信息,具体如下图。
【实验提示】
单链表的结点结构除数据域外,还含有一个指针域。用C语言描述结点结构如下:
typedef int datatype;
/* 线性表中存放整型元素 */ typedef struct LNode
/ * 结点类型定义 * /
{
datatype data;
/ * 数据域 * /
struct node *next;
/ * 指针域 * / }Linklist;
/* Linklist为单链表类型*/
注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc(),如给指针变量p分配一个结点的地址:
p=(strcut LNode *)malloc(sizeof(Linklist));该语句的功能是申请分配一个类型为Linklist的结点的地址空间,并将首地址存入指针变量p中(或p=new(struct LNode);即生成新结点)。当结点不需要时可以用标准函数free(p)释放结点存储空间,这时p为空值(NULL)。【程序提示】
#include
//补充实现表节点类型的定义; } Linklist;
Linklist * creatlist(){ int x;Linklist *head, *p;// head为单链表的头指针,p指向新建的结点
//补充实现单链表的建立;
return(head);
// 函数返回链表头指针head }
void output(Linklist *HeadL){ if(HeadL->next==NULL)printf(“空链表!n”);else { printf(“链表为:n”);Linklist *P;P=HeadL->next;while(P!=NULL){
printf(“%d->”,P->data);P=P->next;} printf(“n”);}
}
void main(void){ Linklist *List;List=creatlist();output(List);} 【参考程序】
1、尾插法
#include
Linklist * creatlist(){ int x;
Linklist *head, *p,*r;/* head为头指针 */
head=new(struct LNode);
head->data=0;
/* 表头结点数据域赋值 */
r=head;
/* 尾指针的初值为头结点head */
printf(“请随机输入互不相同的正整数以0作为结束符:n”);
scanf(“%d”, &x);
/* 读入第一个结点的值 */
while(x!=0)
/* 输入数据,以0为结束符 */ { p=new(struct LNode);/* 生成新结点 */
p->data=x;
/* 给新结点的数据域赋值 */
r->next=p;
/* 新结点插入到表尾*rear之后 */
r=p;
/* 将尾指针rear指向新的尾结点 */
head->data++;
/* 链表长度计数 */
scanf(“%d”, &x);
/* 输入下一个结点的数据 */
}
r->next=NULL;
/* 将链表最后一个结点rear指针域置空 */
return(head);/* 函数返回链表头指针head */ }
void output(Linklist *HeadL){
if(HeadL->next==NULL)printf(“空链表!n”);else {
printf(“链表为:n”);
Linklist *P;
P=HeadL->next;
while(P!=NULL)
{
printf(“%d->”,P->data);
P=P->next;
}
printf(“n”);}
} void main(void){
Linklist *List;List=creatlist();output(List);}
2、头插法
#include
Linklist * creatlist(){ int x;
Linklist *head, *p;/* head为头指针 */
head=new(struct LNode);
head->data=0;
/* 表头结点数据域赋值 */
head->next=NULL;
printf(“n请随机输入一组正整数以0结束输入:n”);
scanf(“%d”,&x);
/* 输入第一个结点数据值 */
while(x!=0)
/* 输入数据,以0为结束符 */
{ p=new(struct LNode);/* 生成新结点 */
p->data=x;/* 给新结点的数据域赋值 */
p->next=head->next;
/* 将新结点插入表头结点head之后 */
head->next=p;
head->data++;
/* 链表长度计数 */
scanf(“%d”,&x);
/* 输入下一个结点的值 */
}
return(head);/* 函数返回链表头指针head */ }
void output(Linklist *HeadL){
} void main(void){
Linklist *List;List=creatlist();output(List);}
方法二 void main(void){
} 2.在第一题的基础上,增加单链表的查找,插入,删除子程序。#include
typedef struct LNode{ int data;struct LNode *next;Linklist *head,*p;head=creatlist();printf(“output the list:n”);p=head->next;while(p){ } printf(“%d ”,p->data);p=p->next;} Linklist;
Linklist * creatlist(){ int x;
Linklist *head, *p;
/* head为头指针 */
head=new(struct LNode);
head->data=0;
/* 表头结点数据域赋值 */
head->next=NULL;
cout<<“n请随机输入一组正整数以0结束输入:n”;
cin>>x;/* 输入第一个结点数据值 */
while(x!=0)
/* 输入数据,以0为结束符 */
{ p=new(struct LNode);/* 生成新结点 */
p->data=x;/* 给新结点的数据域赋值 */
p->next=head->next;
/* 将新结点插入表头结点head之后 */
head->next=p;
head->data++;
/* 链表长度计数 */
cin>>x;
}
return(head);} void output(Linklist *HeadL){
if(HeadL->next==NULL)cout<<“空链表!n”;else {
cout<<“链表为:n”;
Linklist *P;
P=HeadL->next;
while(P!=NULL)
{
cout<
data<<“->”;/* 函数返回链表头指针head */ /* 输入下一个结点的值 */
P=P->next;
}
cout<<“n”;} } Linklist *no_search(Linklist *head, int i){
Linklist *p;int j;
p=head->next;
j=1;
/* 从首结点开始扫描 */
while((p!=NULL)&&(j
{ p=p->next;
/* 扫描下一个结点 */
j++;
}
if(i==j)return(p);
else return(NULL);
/* 若找不到,则返回空指针 */ } Linklist *data_insert(Linklist *head, Linklist *p, int x){
Linklist *s;
s =new(struct LNode);/* 建立新结点 */
s->data=x;
/* 将x值赋给s→data */
/* 统计已扫描结点的个数 */
s->next=p->next;/* 新结点s后继指向原p结点后继 */
p->next=s;
/* p结点的后继指向新结点s */
return(head);
/* 返回带头结点的单链表头指针*/ } Linklist *key_delete(Linklist *head, int x){
Linklist *p, *q;
/* p是被删除结点,q是p的前驱结点 */
p=head;
while((p!=NULL)&&(p->data!=x))
{
q=p;
p=p->next;
}
if(p!=NULL)
{
q->next=p->next;
/* 修改p前驱结点q指针域 */
/* 释放结点空间 */
/* 若该结点存在,则删除之 */
free(p);
return(head);
}
/* 函数返回链表头指针*/
else
{
cout<<“要删的结点不存在,请重输数据!n”;
return(NULL);
} }
void main(void){
Linklist *List,*chazhao;List=creatlist();output(List);chazhao=no_search(List,2);//查找第二个节点,并输出数据域信息 cout<<“n查找第二个节点,数据域信息为:n”;cout<
output(List);List=key_delete(List,50);//删除数据为50的节点 cout<<“n删除数据为50的节点:n”;
output(List);}
第二篇:单链表实验报告
《数据结构》实验报告二
分校:
学号:
日期:
班级:
姓名:
程序名: L2311.CPP
一、上机实验的问题和要求:
单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求:
1.从键盘输入20个整数,产生带表头的单链表,并输入结点值。
2.从键盘输入1个整数,在单链表中查找该结点。若找到,则显示“找到了”;否则,则显示“找不到”。
3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插入在对应位置上,输出单链表所有结点值,观察输出结果。4.从键盘输入1个整数,表示欲删除结点的位置,输出单链表所有结点值,观察输出结果。5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结点值,观察输出结果。
6.删除其中所有数据值为偶数的结点,输出单链表所有结点值,观察输出结果。
7.把单链表变成带表头结点的循环链表,输出循环单链表所有结点值,观察输出结果。8.(★)将单链表分解成两个单链表A和B,使A链表中含有原链表中序号为奇数的元素,而B链表中含有原链表中序号为偶数的元素,且保持原来的相对顺序,分别输出单链表A和单链表B的所有结点值,观察输出结果。
二、程序设计的基本思想,原理和算法描述:
(包括程序的结构,数据结构,输入/输出设计,符号名说明等)
三、源程序及注释:
四、运行输出结果:
五、调试和运行程序过程中产生的问题及采取的措施:
六、对算法的程序的讨论、分析,改进设想,其它经验教训:
七、对实验方式、组织、设备、题目的意见和建议:
第三篇:第三章 单文档应用程序
第三章 单文档应用程序
在本学习情境中主要学习:(1)单文档应用框架(2)文档与视图
3.1 MFC消息处理
3.1.1事件驱动程序设计
事件驱动程序设计是一种全新的程序设计方法,它不是由事件的顺序来控制,而是由事件的发生来控制,而这种事件的发生是随机的、不确定的,并没有预定的顺序,这样就允许程序的的用户用各种合理的顺序来安排程序的流程。对于需要用户交互的应用程序来说,事件驱动的程序设计有着过程驱动方法无法替代的优点。它是一种面向用户的程序设计方法,它在程序设计过程中除了完成所需功能之外,更多的考虑了用户可能的各种输入,并针对性的设计相应的处理程序。它是一种“被动”式程序设计方法,程序开始运行时,处于等待用户输入事件状态,然后取得事件并作出相应反应,处理完毕又返回并处于等待事件状态。它的框图如图1所示:
图1事件驱动程序模型
3.1.2 MFC的消息处理
在DOS应用程序下,可以通过getchar()、getch()等函数直接等待键盘输入,并直接向屏幕输出。而在Windows下,由于允许多个任务同时运行,应用程序的输入输出是由Windows来统一管理的。
Windows操作系统包括三个内核基本元件:GDI, KERNEL ,USER。其中GDI(图形设备接口)负责在屏幕上绘制像素、打印硬拷贝输出,绘制用户界面包括窗口、菜单、对话框等。系统内核KERNEL支持与操作系统密切相关的功能:如进程加载,文本切换、文件I/O,以及内存管理、线程管理等。USER为所有的用户界面对象提供支持,它用于接收和管理所有输入消息、系统消息并把它们发给相应的窗口的消息队列。消息队列是一个系统定义的内存块,用于临时存储消息;或是把消息直接发给窗口过程。每个窗口维护自己的消息队列,并从中取出消息,利用窗口函数进行处理。框图2如下:
图2 消息驱动模型
从消息的发送途径上看,消息分两种:队列消息和非队列消息。队列消息送到系统消息队列,然后到线程消息队列;非队列消息直接送给目的窗口过程。
Windows维护一个系统消息队列(System message queue),每个GUI线程有一个线程消息队列(Thread message queue)。
鼠标、键盘事件由鼠标或键盘驱动程序转换成输入消息并把消息放进系统消息队列,例如WM_MOUSEMOVE、WM_LBUTTONUP、WM_KEYDOWN、WM_CHAR等等。Windows每次从系统消息队列移走一个消息,确定它是送给哪个窗口的和这个窗口是由哪个线程创建的,然后,把它放进窗口创建线程的线程消息队列。线程消息队列接收送给该线程所创建窗口的消息。线程从消息队列取出消息,通过Windows把它送给适当的窗口过程来处理。
除了键盘、鼠标消息以外,队列消息还有WM_PAINT、WM_TIMER和WM_QUIT。这些队列消息以外的绝大多数消息是非队列消息。
通过消息映射,我们可以把消息和它的消息处理函数联系起来。VC++为我们提供了Class Wizard 来为用户添加一个消息映射关系,而用户只需编写该消息发生响应的函数即可。
从View菜单中选择“ClassWizard”命令,便可调出如图3所示的ClassWizard对话框,它一共分为五个选项卡,依次分别是消息映射、成员变量、自动化、ActiveX事件和类信息。最常用的是消息映射和成员变量两个选项卡,如果程序中使用了ActiveX控件,那么还需要使用ActiveX事件选项卡来添加事件处理函数,类信息选项卡可用来了解各个类的文件名、基类和资源等信息,自动化选项卡只有在编写OLE自动化服务器时才用得着。下面我们就来看看消息映射和成员变量两个选项卡的特点和用途。
消息映射选项卡主要用途是为选中的类添加消息处理函数。其中,Projects组合框用于选择Workspace中的一个工程,Class name组合框用于选择工程中的一个类。Objects IDs中列出了所选择的类的名称及属于它的一系列ID,对于CXXXView类来说,列出的ID基本上都是菜单命令,对于一个对话框类来说,列出的ID多数对应着对话框模板中的控件。
从Objects IDs选择不同的类名或ID后,右边的Messages列表框中的内容也会跟着改变,选中类名时,Messages列表框中会显示出所有该类能处理的标准Windows消息以及该类可以重载的成员函数,选中一个ID时,Messages列表框中会显示出这个ID对应的对象(菜单选项或控件)所能引发的命令消息和通知消息。在Messages列表框中选择一条消息(或一个可以重载的成员函数)后,如果该消息还没有相应的消息处理函数(或还未重载该成员函数),那么ClassWizard对话框右上角的Add Function按钮就会变为有效,提示我们可以添加一个消息处理函数(或重载该成员函数),按下Add Function按钮后,ClassWizard就会在所选的类中添加一个处理函数(为一个ID添加处理函数时,还会弹出一个对话框,要求输入函数名),并在Member funtions列表框中显示出刚添加的函数,在这个列表框中双击该函数名后,ClassWizard对话框将自动关闭,文本编辑器会定位在函数的实现代码处,这些代码及它在类定义中的声明都是由ClassWizard自动生成的。
图 3Class wizard 对话框
Member functions列表框并没有列出类的所有成员函数,而只是列出了消息处理函数和重载的成员函数,其中每个函数的左边都有一个小图标,如果小图标为“W”字样,表示该函数是一个消息处理函数,除了Add function按钮外,消息映射选项卡中还有三个按钮,其中Delete Function用来删除一个消息处理函数或重载的成员函数,但是此按钮只能删除函数在类定义中的声明,函数的实现代码还需要手工来删除;Edit Code按钮的用途相当于在Member functions中双击一个成员函数;Add Class按钮则可用于向工程中添加一个新的类。3.1.3 文档与视图
先利用Appwizard 来新建一个单文档工程。在SDI框架程序中,主要包含四个类:
主框架类:CMainFrame用于管理主程序窗口,从MFC 类的CFrameWnd派生。
应用类:CXXXApp负责初始化及程序结束前的整理工作,从MFC 类的CWinApp派生。
文档类:CXXXDoc负责存放程序数据和在磁盘上读写数据,从MFC 类的CDocment派生。
视图类:CXXXView负责数据的显示及处理用户的输入,从MFC类的CView派生。用户对话框类:CAboutDlg负责用户对话框的设置,从MFC类的CDialog类派生。
文档是存储的对象.文档类负责数据的维护,包括数据的读取、存储和修改,并将更改的数据通知相关视图,另外它还负责将数据存储到文件及从文件中读取数据。
文档是一种数据源,数据源有很多种,最常见的是磁盘文件,但它不必是一个磁盘文件,文档的数据源也可以来自串行口、网络或摄像机输入信号等。文档对象负责来自所有数据源的数据的管理。
视图类的作用是与用户交互。视图对象负责对保存在文挡对象中的数据以某种方式进行显示,并接受用户的输入,将这些输入交文挡类进行处理。
视图是数据的用户窗口,为用户提供了文档的可视的数据显示,它把文档的部分或全部内容在窗口中显示出来。视图还给用户提供了一个与文档中的数据交互的界面,它把用户的输入转化为对文档中数据的操作。每个文档都会有一个或多个视图显示,一个文档可以有多个不同的视图。比如,在Excel电子表格中,我们可以将数据以表格方式显示,也可以将数据以图表方式显示。一个视图既可以输出到窗口中,也可以输出到打印机上。
图 文档与视图关系
3.1.4 鼠标消息举例
我们先通过一个例子来说明如何用class wizard 来实现捕获鼠标消息,进行消息映射和定义消息处理函数.利用class wizard来设置消息选项。选择ClassName中的CXXXView,选择其中相对应的WM_LBUTTONDOWN,双击选中的消息,单击Edit Code 按纽,如图4所示,并增加相关代码,如图5所示。
图4 增加鼠标消息映射
图5 增加代码
图6 运行结果
3.1.4键盘消息举例
键盘的输入是从扫描码开始的,windows键盘驱动程序将这些扫描码转换成为与硬件无关的形式,即虚拟键码.WM_CHAR:此消息在键被按下时产生,通常用于处理非打印键中的按键消息.图7 在工程中增加相关变量
图8 增加变量Text
图9 初始化变量为空
图10 增加键盘的消息影射
图11 编写Onchar处理函数
图12 输出接收到的字符
图13 运行结果 为了能够实现输入字符的换行功能,在CXXXDoc类中增加一个用来计算行数的成员变量m_Line,如图14所示,并初始化变量m_Line,如图15所示。
图 增加成员变量
图15 初始化成员变量
为了保存字符串行的数据,定义一个字符串列表变量m_strList,如图16所示。
图16 定义字符串列表变量
修改CXXXView类中的OnChar函数,如下所示。
void CSDIView::OnChar(UINT nChar, UINT nRepCnt, UINT nFlags){ // TODO: Add your message handler code here and/or call default
CSDIDoc *pDoc=GetDocument();ASSERT_VALID(pDoc);
} if(nChar==VK_RETURN){ pDoc->m_Line++;pDoc->m_strList.AddTail(pDoc->Text);pDoc->Text.Empty();
Invalidate();} else {
pDoc->Text+=nChar;
CClientDC dc(this);
TEXTMETRIC tm;
dc.GetTextMetrics(&tm);
int nLineHeight=tm.tmHeight+tm.tmExternalLeading;
dc.TextOut(0,pDoc->m_Line*nLineHeight,pDoc->Text);} CView::OnChar(nChar, nRepCnt, nFlags);为了保证能够将CXXXDoc类中m_strList的数据输出出来,增加一个DrawText函数,如图17所示和图18所示。
图17 在CXXXDoc类中增加成员函数
图18 增加DrawText函数
实现CXXXDoc类中的DrawText函数,如下所示。void CSDIDoc::DrawText(CDC *pDC){
TEXTMETRIC tm;
CString str;int line=0;
pDC->GetTextMetrics(&tm);
int nLineHeight=tm.tmHeight+tm.tmExternalLeading;
POSITION pos=m_strList.GetHeadPosition();for(;pos!=NULL;m_strList.GetNext(pos)){
str=m_strList.GetAt(pos);
pDC->TextOut(0,line*nLineHeight,str);
line++;} } 修改CXXXView类中的OnDraw函数,如下所示。
void CSDIView::OnDraw(CDC* pDC){ CSDIDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);
pDoc->DrawText(pDC);
// TODO: add draw code for native data here }
第四篇:北邮数据结构实验报告 单链表
北京邮电大学 数据结构试验报告
实验名称: 实验一
线性表 学生姓名:
班
级:
班内序号:
学
号:
日
期: 2014年1月3日
实验目的
熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 实验内容
2.1题目1 根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表,并完成线性表的基本功能。
线性表存储结构(五选一):
1、带头结点的单链表
2、不带头结点的单链表
3、循环链表
4、双链表
5、静态链表
线性表的基本功能:
1、构造:使用头插法、尾插法两种方法
2、插入:要求建立的链表按照关键字从小到大有序
3、删除
4、查找
5、获取链表长度
6、销毁
7、其他:可自行定义
编写测试main()函数测试线性表的正确性。程序分析
3.1 存储结构 单链表的存储结构:
3.2 关键算法分析
一、关键算法 1.头插法
自然语言描述:a.在堆中建立新结点
b.将a[i]写入到新结点的数据域
c.修改新结点的指针域
d.修改头结点的指针域,将新结点加入链表中 代码描述: template
front = new Node
}
} s->next = front->next;front->next = s;时间复杂度:O(n)
2.尾插法
自然语言描述:a.在堆中建立新结点
b.将a[i]写入到新结点的数据域
c.将新结点加入到链表中
d.修改修改尾指针 代码描述: template
front = new Node
}
} s->data = a[i];s->next = r->next;r->next= s;r=s;时间复杂度:O(n)
3.析构函数
自然语言描述:a.新建立一个指针,指向头结点
b.移动a中建立的指针
c.逐个释放指针
代码描述: template
Node
} } delete front;4.按位查找函数
自然语言描述: a.初始化工作指针p和计数器j,p指向第一个结点,j=1
b.循环以下操作,直到p为空或者j等于1
b1:p指向下一个结点
b2:j加1
c.若p为空,说明第i个元素不存在,抛出异常
d.否则,说明p指向的元素就是所查找的元素,返回元素地址
代码描述: template
Node
if(j
} else break;p = p->next;j++;
} if(!p)throw“查找位置非法”;else
return p;} 时间复杂度:O(n)
5.按值查找函数
自然语言描述:a.初始化工作指针p和计数器j,p指向第一个结点,j=1
b.循环以下操作,找到这个元素或者p指向最后一个结点
b1.判断p指向的结点是不是要查找的值,如果是,返回j;
b2.否则p指向下一个结点,并且j的值加一
c.如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息
代码描述: template
Node
} return-1;if(p->data == x)return j;else { p = p->next;
j++;} } 时间复杂度:O(n)6.插入函数
自然语言描述: a.在堆中建立新结点
b.将要插入的结点的数据写入到新结点的数据域
c.修改新结点的指针域
d.修改前一个指针的指针域,使其指向新插入的结点的位置
代码描述: template
Node
} else throw“插入位置非法”;Node
自然语言描述:a.从第一个结点开始,查找要删除的位数i前一个位置i-1的结点
b.设q指向第i个元素
c.将q元素从链表中删除
d.保存q元素的数据
e.释放q元素 代码描述: template
T x=q->data;
} p->next = q->next;delete q;return x;
8.遍历打印函数
自然语言描述: a.判断该链表是否为空链表,如果是,报错
b.如果不是空链表,新建立一个temp指针
c.将temp指针指向头结点
d.打印temp指针的data域
e.逐个往后移动temp指针,直到temp指针的指向的指针的next域为空
代码描述: template
} Node
} cout<
自然语言描述: a.判断该链表是否为空链表,如果是,输出长度0
b.如果不是空链表,新建立一个temp指针,初始化整形数n为0
c.将temp指针指向头结点
d.判断temp指针指向的结点的next域是否为空,如果不是,n加一,否则return n
e.使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n 代码描述: template
} Node
} return i-1;p = p->next;i++;4 程序运行结果
4.1主函数流程图
4.2程序运行框图
实验心得
1.调试时出现的问题及解决的方法
在编写按值查找函数时,由于没有处理好指针类型的原因,导致指针无法正常返回,屡屡报错。最后意识到c++没有指针强制类型的转换机制,经过细致检查后才改正错误使得程序正常运行。2.心得体会
了解了单链表的基本的操作函数实现,对链式存储结构有了较好的认识 3.下一步的改进
可以增加完善报错机制,增强程序的健壮性
完整源代码
#include
template
};
template
};
//template
Node
template
}
template
}
template
} front = p;p = p->next;delete front;front = new Node } Node } Node } Node } cout< template } template } Node } return-1;if(p->data == x)return j;else { } p = p->next; j++;Node } if(!p)throw“查找位置非法”;else return p;if(j } else break;p = p->next;j++; template } template } template } void main(){ Node } return i-1;p = p->next;i++;Node } else throw“插入位置非法”;Node T x=q->data; } int n;cout<<“将要输入的链表长度为:”;cin>>n;int *b=new int[n];cout<<“输入链表中的元素:”;for(int k=0;k 求解Josephus问题实验总结 1实验题目: josephus问题可描述如下: 设有n个人围成一个环,现从第s个人开始报数,数到第m的人出列,然后从出列的下一个人从新开始报数,数到第m的人又出列,如此重复,直至所有人均出列为止。求这些人出列的顺序。 2实验目的: 熟练掌握线性表的顺序实现和链式实现的基本操作。 3实验方法: 通过运用已学的向量和循环单链表编写程序,并在电脑上运行,实现josephus问题的求解。4实验过程与结果: (1)输入n值为6,s值为3,m值为2,输入A[i]的值为1 2 3 4 5 6 输出结 果为:4 6 2 5 3 1 截图如下: (2) 1、输入n值为-1, s值为3,m值为2,显示:ERROR。截图如下: 2、输入n值为6, s值为0,m值为3,显示:ERROR。截图如下: 3、输入n值为6, s值为3,m值为0,显示:ERROR。截图如下 : 5试验体会与收获: (1)写程序是要随时注意缩进,使得程序层次清晰,便于寻找错误,同时也让别人看的更加方便。(2)构造循环单链表,要以单链表为单元指针指向把最后个单元与第一个即可(3)建立好循环单链表后,通过三个指针(p,q,tmp)的指示,来确定报数,出列人的位置,得以完成。具体过程如下:p指向head头指针,通过s次循环将p指向报数的起始位置s,用q记录p的位置,再经过m次循环另p指向出列者的位置,将其数值保存在一维数组中,并将其从链表中删除,p指向下一次起始位置,结束时返回数组A[j]。(4)删除节点时,注意要释放节点。 (5)构造函数时,一定要明确函数的类型,即返回行还是不返回型,以免出现不必要的错误。第五篇:求解Josephus问题实验总结(用C语言循环单链表实现)