北理工数据结构实验一

1、数据结构与算法设计实验报告实验一学院： 班级： 学号： 姓名： 一、实验目的 1. 通过实验实践、巩固线性表的相关操作；2. 熟悉VC环境，加强编程、调试的练习；3. 用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作；4. 理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。二、实验内容 1、采用单向环表实现约瑟夫环。请按以下要求编程实现： 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，m。 从键盘输入整数s（1=s=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环

2、表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。三、程序设计 1、概要设计为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。（1）、单向环表的抽象数据类型定义为：ADT Joseph 数据对象：D=ai|aiElemSet,i=1,2,3,n,n0数据关系：R1= |aiD,i=1,2,n基本操作：create(&L,n) 操作结果：构造一个有n个结点的单向环表L。show(L) 初始条件：单向环表L已存在。操作结果：按顺序在屏幕上输出L的数据元素。Josephf( L,m,s,n) 初始条件

3、：单向环表L已存在， s0,n0，sdata = 1;h=L;for(int i=2;idata = i; /生成新节点，数据为节点编号h-next = p;h = p; /插入链表h-next = L; /形成循环链表void show(Linklist L,int m)/从第一个节点开始依次输出节点编号printf(The numbers of the list are: n); /提示用户Linklist h;h=L;for(int i=1;idata);h = h-next;printf(n);void Josephf(Linklist &L,int m,int s,int n)/实现

4、约瑟夫环Linklist h,q;h = L;q = L;while(h-data != s) /定位开始的节点h = h-next;while(q-next!=h) /定位在开始位置的上一个节点q = q-next;for(int j=1;j=m;j+)int i=1;while(inext;i+;printf(%d ,q-next-data); /依次输出报号为n的节点q-next = q-next-next; /删除已输出节点printf(n);（3）、主程序的代码实现：int main()int s,m,n;Linklist L;printf(请输入节点数m：n);scanf(%d,&

5、m);create(L,m); /建立循环链表show(L,m); /输出链表数据printf(请输入起始位置s：n);scanf(%d,&s);printf(请输入报的数n：n);scanf(%d,&n);Josephf(L,m,s,n); /输出所报数字return 0;四、程序调试分析 1. 引用标识符&不符合C语言语法，应使用C+;2. 为了实现循环链表，建立时应该不设头结点且第一个节点就存储编号数据；3. 删除节点时要定位到前一个指针，所以在定位开始位置后还要再定位到前一个指针；4. 输出时要注意增加“ ”（空格）和“n”（换行），使输出易于辨识。五、 用户使用说明 1. 本程序的运

6、行环境为DOS操作系统，执行文件为：实验一.exe，双击打开文件。2. 进入程序后，出现提示语句“请输入节点数m：”，用户根据提示输入节点数m,按Enter键，显示生成的链表，同时出现提示语句：“请输入起始位置s：”，用户输入起始位置s，按Enter键，出现提示语句“请输入报的数n：”，用户输入报的数，按Enter键，即可得到依次报号的结果。六、程序运行结果测试一： 测试二：七、程序清单#include stdio.h#include stdlib.htypedef int Status;typedef int ElemType;typedef struct LnodeElemType dat

7、a;struct Lnode *next;Lnode,*Linklist; /定义链表结点void create(Linklist &L,int m)/生成一个具有m个结点的单向环表，环表中的结点编号依次为1，2，mLinklist h,p;L=(Linklist)malloc(sizeof(Lnode);L-data = 1;h=L;for(int i=2;idata = i; /生成新节点，数据为节点编号h-next = p;h = p; /插入链表h-next = L; /形成循环链表void show(Linklist L,int m)/从第一个节点开始依次输出节点编号printf(T

8、he numbers of the list are: n); /提示用户Linklist h;h=L;for(int i=1;idata);h = h-next;printf(n);void Josephf(Linklist &L,int m,int s,int n)/实现约瑟夫环Linklist h,q;h = L;q = L;while(h-data != s) /定位开始的节点h = h-next;while(q-next!=h) /定位在开始位置的上一个节点q = q-next;for(int j=1;j=m;j+)int i=1;while(inext;i+;printf(%d ,

9、q-next-data); /依次输出报号为n的节点q-next = q-next-next; /删除已输出节点printf(n);int main()int s,m,n;Linklist L;printf(请输入节点数m：n);scanf(%d,&m);create(L,m);show(L,m);printf(请输入起始位置s：n);scanf(%d,&s);printf(请输入报的数n：n);scanf(%d,&n);Josephf(L,m,s,n);return 0;选做实验2、归并顺序表（选作）。请按以下要求编程实现： 从键盘输入两个升序排列的整数序列linka和linkb，每个序列以

10、输入0为结束标记。 将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。 对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。例如：linka输入为：10 20 30 40 50 0 linkb输入为：15 20 25 30 35 40 45 50 0 归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50 程序清单#include stdi

11、o.h#include stdlib.htypedef int ElemType;typedef struct LnodeElemType data;struct Lnode *next;Lnode,*Linklist; /定义链表结点,指针类型void create(Linklist &L)/生成从键盘输入的升序排列的整数序列链表Linklist h,p;int x = 1;L=(Linklist)malloc(sizeof(Lnode); /生成头指针h=L;while(x!=0)scanf(%d,&x);p = (Linklist)malloc(sizeof(Lnode);p-data

12、= x; /生成新节点，数据输入数字h-next = p;h = p; /插入链表h-next = NULL; void show(Linklist L)/依次输出链表中的元素Linklist h;h=L-next;while(h-next) /指针指向空指针时结束循环 printf(%d ,h-data);h = h-next;printf(n);void merge(Linklist &La,Linklist &Lb,Linklist &Lc)/将链表La和Lb归并为Lc，Lc仍然为升序排列Linklist ha,hb,hc,p;Lc=(Linklist)malloc(sizeof(Lno

13、de);/生成头指针hc=Lc;ha=La-next;hb=Lb-next;while(ha-next & hb-next) /插入La和Lb中较小的数,直到La或者Lb为空p = (Linklist)malloc(sizeof(Lnode);if(ha-datadata) p-data = ha-data; hc-next = p;hc = p; ha = ha-next;elsep-data = hb-data; hc-next = p;hc = p; hb = hb-next;if(ha-next)hc-next = ha;if(hb-next)hc-next = hb;/将没有插入完的

14、链表直接接在Lc后面void listdelete(Linklist &L)/删除Lc中重复的数字Linklist h;h=L;while(h-next-next) if(h-next-data = h-next-next-data)h-next = h-next-next; /如果相邻两数字相同，删除相同数字中前一个对应的节点else h=h-next; /如果相邻两数字不同，指针指向下一个节点void clear(Linklist &La,Linklist &Lb)/将La，Lb置空La-next-next=NULL; Lb-next-next=NULL; printf(置空后La中的元素为：n);show(La);printf(置空后Lb中的元素为：n);show(Lb);int main()int s,m,n;Linklist La,Lb,Lc;printf(请输入升序整数序列La：n);create(La);printf(La中的元素依次为：n);show(La);printf(请输入升序整数序列Lb：n);create(Lb);print