资源描述：
《数据结构和算法设计-数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构实验报告学院：自动化学院班级：06120902学号：20091617姓名：简剑171．单向环表实现约瑟夫环……1~42．表达式求值……5~113．二叉树实现与遍历……12~144．Sorting……15~1617单向环表实现约瑟夫环1、单向环表实现约瑟夫环一、实验目的（1）进一步认识线性表，并上机实现线性链表。（2）学会从算法到具体程序的转换，并注意区别程序算法与具体程序的不同。（3）本实验用C语言，熟悉C语言的各种操作，并学会调试程序。二、实验内容请按以下要求编程实现：①从键盘输入整数m，通过crea
2、te函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。三、实验步骤输出数据删除节点①明确实验要求，依照书上的类C语言转化编写C语言程序；②程序按：定义
3、链表ð建立环链表ð预判错误（容错）ð完成约瑟夫输出编写，主要分成main()、Create(intm)、Delete(Linkp)三个函数#includetypedefstructLnode{intdata;structLnode*NextL;}LNODE,*Link;//定义链表的一个节点类型LNODE，以及指向该结构类型的指针类型Linktypedefstruct{Linkhead,tail;intlen;}LinkList;LinkListL;//定义一个全局链表Lmain(){Link
4、p;intm,s,n,i,count;voidCreate(int,Link);//对Create()函数的声明，17单向环表实现约瑟夫环LinkDelete(Link);//对Delete(Link)函数的声明，并且该函数的返回值为Link类e:scanf("%d%d%d",&m,&s,&n);if((m>0)*(n>0)*(s>0))//判断m,n,s是否是大于零的整数{Create(m);//生成一个环链表p=L.head->NextL;//定义一个指向首节点的指针for(i=1;;i++){if(i==
5、s)break;elsep=p->NextL;}//从i=1开始，知道找到i=s的节点B:for(i=1;i<=n;i++){if(p==NULL)break;if(i==n){printf("%d",p->data);p=Delete(p);gotoB;}elsep=p->NextL;}}//循环输出约瑟夫问题所求数据else{printf("Pleaseenterintnumberswhichallarebiggerthan0.");gotoe;}//容错处理system("pause");}//mai
6、n()VoidCreate(intm){inti;L.len=0;Linkp,q;if(!(p=(Link)malloc(sizeof(LNODE))))exit(0);//生成头指针及简单的容错处理L.head=p;if(!(p=(Link)malloc(sizeof(LNODE))))exit(0);L.head->NextL=p;for(i=1;i<=m;i++){if(i!=m){p->data=i;q=p;if(!p=(Link)malloc(sizeof(LNODE)))exit(0);q->Nex
7、tL=p;L.tail=p;}//从i=1开始一次对各节点的数据赋值else{p->data=i;p->NextL=L.head->NextL;}//当生成最后一个节点后，将其指向第一个节点形成环链L.len++;}}//VoidCreate17单向环表实现约瑟夫环LinkDelete(Linkp){Linkq;q=p;while(q->NextL!=p)q=q->NextL;//每次从p节点开始找到前一个的节点,不是从头结点开始if(q->NextL==q){free(q);L.len=L.tail=NULL
8、;returnNULL;}//链表中只剩下一个节点时,直接返回NULLelse{q->NextL=q->NextL->NextL;if(p==L.head->NextL)L.head->NextL=p->NextL;if(p==L.tail)L.tail=p->NextL;free(p);//释放p节点L.len--;returnq->NextL;}}//LinkDelete分块（分函
