程序设计课程设计报告

1、程序设计课程设计报告程序设计课程设计报告设计人：电气QU42李艳平(11150038)日期：2021-11-29指导教师：桂超设计题目：链表操作一、设计任务1、创立一个单链表,并返回头结点的地址head2、编写函数circulachain,将上述单链表改为单循环链表3、编写函数addnode,在数据为x的结点之后插入数据为y的结点4、编写函数delenode,删除单链表中数据为x的结点5、解决约瑟夫问题：有n个人,围坐一圈,对他们从1开始编号,即1,2,3,n,如果从某一个人开始报数,他报数1,按顺时针进行,紧挨的人报数2,再往下的人跟着报3,一直报到k,凡报到k的人出歹U,再往下,继续从1开

2、始报数,2,3,一直报到k,凡报到k的人出列.试输出该问题中顺序出列的人的名字.二、功能描述创立单链表函数:chain*crechain(char*ch)创立单循环链表函数:chain*circulchain(char*ch)销毁链表：voidDestroy(chain*head)显示链表中每个结点的数据:voidShow(chain*head)插入结点函数：voidAddNode(chain*head,charx,chary)删除结点函数：voidDeleNode(chain*head,charx)三、程序实现1、单链表的根本操作:#include<iostream>usingn

3、amespacestd;structchain(chardata;chain*next;);chain*crechain(char*ch)创立单链表(inti;chain*head=NULL,*P=NULL,*q=NULL;for(i=0;chi!=,(T;i+)(p=newchain;p->data=chi;if(head=NULL)(head=p;)else(q->next=p;)q=P；)q->next=NULL;return(head);)voidAddNode(chain*head,charx,chary)/*插入结点*/chain*r,*s;if(head=NUL

4、L)cout«''链表为空!n«endl;else(r=head;while(r!=NULL)(if(r->data!=x)(r=r->next;)elsebreak;)if(r=NULL)coutcc没有数据为x的节点!<<endl;else(s=newchain;s->data=y;s->next=r->next;r->next=s;voidDeleNode(chain*head,charx)/*删除结点*/(chain*p=head,*s;if(head=NULL)cout«''

5、链表为空!n«endl;if(head->data=x)(head=p->next;deletep;)else(while(p->next!=NULL)(if(p->next->data!=x)p=p->next;elses=p->next;p->next=s->next;deletes;break;)voidShow(chain*head)输出链表(chain*p;p=head;while(p!=NULL)(cout«p->data;p=p->next;)cout«HnH;voidDestroy(

6、chain*head)销毁链表chain*p;while(head!=NULL)(p=head;head=p->next;deletep;)intmain()(chain*head;head=crechain(Habcdn);Show(head);AddNode(head,T);Show(head);DeleNode(headJc');Show(head);Destroy(head);return0;)2、单循环链表：chain*circulchain(char*ch)(inti;chain*head=NULL,*P=NULL,NULL,*r;for(i=0;chi!=AO1;i

7、+)(p=newchain;p->data=chi;if(head=NULL)(head=p;)else(q->next=p;)q=p;)q->next=head;return(head);)3、约瑟夫问题：#include<iostream>usingnamespacestd;structJoseph(charch;Joseph*next;);Joseph*head,tail;/Joseph结构指针,全局变voidcreate(intn)给每个结点数据赋值(inti;Joseph*p,*q;p=(Joseph*)malloc(sizeof(Joseph);p-&

8、gt;ch='A'p->next=NULL;head=p;q=p;for(i=1;i<n;i+)p=(Joseph*)malloc(sizeof(Joseph);p->ch='A'+i;q->next=p;q=P；点p->next=NULL;)tail=q;tail->next=head;)将p结点加到链表尾部让q指向链表尾部结链表尾部指向空voidDisplay(intm)依次输出出列的人的名字(intx=0;Joseph*p,*q;q=tail;dop赋值为q相邻的p=q->next;下一个结点X+;if(x%m=0)(coutvv出列的人为"vvp>chvvendl;q->next=p->next;deletep;p=NULL;)elseq=p;/q指向相邻的下一结点P)while(q!=q->next);剩余结点数不为1,那么继续循环head=q;)intmain()intn,m;head=NULL;