北理工数据结构实验一

数据结构与算法设计实验报告实验一学院： 班级： 学号： 姓名： 一、实验目的 1. 通过实验实践、巩固线性表的相关操作；2. 熟悉 VC环境，加强编程、调试的练习；3. 用 C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作；4. 理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。二、实验内容 1、采用单向环表实现约瑟夫环。请按以下要求编程实现： 从键盘输入整数 m，通过 create函数生成一个具有 m个结点的单向环表。环表中的结点编号依次为 1，2，m。 从键盘输入整数 s（1|aiD,i=1,2,n基本操作：create(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 h = L;q = L;while(h-data != s) /定位开始的节点h = h-next;while(q-next!=h) /定位在开始位置的上一个节点q = q-next;for(int j=1;jnext;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“,create(L,m); /建立循环链表show(L,m); /输出链表数据printf(“请输入起始位置 s：n“);scanf(“%d“,printf(“请输入报的数 n：n“);scanf(“%d“,Josephf(L,m,s,n); /输出所报数字return 0;四、程序调试分析 1. 引用标识符2. 为了实现循环链表，建立时应该不设头结点且第一个节点就存储编号数据；3. 删除节点时要定位到前一个指针，所以在定位开始位置后还要再定位到前一个指针；4. 输出时要注意增加“ ” （空格）和“n” （换行） ，使输出易于辨识。五、 用户使用说明 1. 本程序的运行环境为 DOS操作系统，执行文件为：实验一.exe，双击打开文件。2. 进入程序后，出现提示语句“请输入节点数 m：” ，用户根据提示输入节点数 m,按Enter键，显示生成的链表，同时出现提示语句：“请输入起始位置 s：” ，用户输入起始位置 s，按 Enter键，出现提示语句“请输入报的数 n：” ，用户输入报的数，按Enter键，即可得到依次报号的结果。六、程序运行结果测试一：测试二：七、程序清单#include “stdio.h“#include “stdlib.h“typedef int Status;typedef int ElemType;typedef struct LnodeElemType data;struct Lnode *next;Lnode,*Linklist; /定义链表结点void create(Linklist 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(“The numbers of the list are: n“); /提示用户Linklist h;h=L;for(int i=1;idata);h = h-next;printf(“n“);void Josephf(Linklist h = L;q = L;while(h-data != s) /定位开始的节点h = h-next;while(q-next!=h) /定位在开始位置的上一个节点q = q-next;for(int j=1;jnext;i+;printf(“%d “,q-next-data); /依次输出报号为 n的节点q-next = q-next-next; /删除已输出节点printf(“n“);int main()int s,m,n;Linklist L;printf(“请输入节点数 m：n“);scanf(“%d“,create(L,m);show(L,m);printf(“请输入起始位置 s：n“);scanf(“%d“,printf(“请输入报的数 n：n“);scanf(“%d“,Josephf(L,m,s,n);return 0;选做实验2、归并顺序表（选作） 。请按以下要求编程实现： 从键盘输入两个升序排列的整数序列 linka和 linkb，每个序列以输入 0为结束标记。 将链表 linka和 linkb归并为 linkc，linkc 仍然为升序排列。归并完成后，linka和 linkb为空表。输出 linkc。 对 linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。例如：linka 输入为：10 20 30 40 50 0linkb输入为：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 “stdio.h“#include “stdlib.h“typedef int ElemType;typedef struct LnodeElemType data;struct Lnode *next;Lnode,*Linklist; /定义链表结点,指针类型void create(Linklist int x = 1;L=(Linklist)malloc(sizeof(Lnode); /生成头指针h=L;while(x!=0)scanf(“%d“,p = (Linklist)malloc(sizeof(Lnode);p-data = 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 Lc=(Linklist)malloc(sizeof(Lnode);/生成头指针hc=Lc;ha=La-next;hb=Lb-next;while(ha-next 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;/将没有插入完的链表直接接在 Lc后面void listdelete(Linklist 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 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);printf(“Lb中的元素依次为：n“);show(Lb);if