循环链表
<div id="cnblogs_post_body">单向循环链表：空表：L->next = L。
与单链表的联系：判断表尾的方法不同：单链表用p==NULL；循环链表用p==L。
双向循环链表：一个结点包含指向后继(next) 和指向前驱(prior) 两个指针，两个方向又分别构成循环链表。
双向循环链表的插入和删除：
1.p之后插入s
s->next = p->next;
p->next = s;
s->prior = p;
s->next->prior = s;
2.p之前插入s
s->prior= p->prior;
p->prior = s;
s->next = p;
s->prior->next = s;
3.删除p之后继s
s = p->next;
p->next = s->next;
p->next->prior = p;
4.删除p
p->prior->next= p->next;
p->next->prior= p->prior;
一道题目：循环链表解决Josephus环问题
题目：n个人围成一圈，从第一个开始顺序报数1，2，3，凡是报到3 者退出圈子，最后剩下的就是胜利者。
参考代码：
<div class="cnblogs_code">#include <iostream> using namespace std; typedef struct Node{ int data; struct Node *next;}Node,*List; List Creatlist(int n){ List head,p; int i; head=(Node*)malloc(sizeof(Node)); if(!head) { cout<<"memory allocation error!\n"; exit(1); } head->data=1; head->next=head; for(i=n;i>1;--i) { p=(Node*)malloc(sizeof(Node)); if(!p) { cout<<"memory allocation error!\n"; exit(1); } p->data=i; p->next=head->next; head->next=p; } return head;} void Output(List head){ List p=head; do { cout<<p->data<<" "; p=p->next; }while(p!=head); cout<<endl;} void Play(List head,int n,int m) //第一种方法 { List p,q; int c,k; p=head; c=1; k=n; while(k>1) { if(c==m-1) { q=p->next; p->next=q->next; cout<<q->data<<" "; free(q); c=0; --k; } else {c++; p=p->next;} } cout<<"The winner is "<<p->data; cout<<endl;} void Josephus(List h,int n,int m)//第二种方法 { Node* p=h,*pre=NULL; int i,j; for(i=0;i<n-1;++i) { for(j=1;j<m;++j) { pre=p; p=p->next; } cout<<"The out number is"<<p->data<<endl; pre->next=p->next; free(p); p=pre->next; } cout<<"The winner is "<<p->data<<endl;} int main(){ List head; int n,m; cout<<"Input the n and m :"; cin>>n>>m; head=Creatlist(n); Output(head); Josephus(head,n,m); return 0;}
页:
[1]