注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Aspirer's blog

停止维护,新博客地址:http://aspirer.wang/

 
 
 

日志

 
 

循环链表  

2009-08-13 21:24:08|  分类: 学习心得 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

循环链表 - aspirer - Aspirers blog

已知N个人(分别以编号1…N表示)围坐在一张圆桌周围,从编号为beg的人开始报数,数到dis的那个人出列;他的下一个人又开始从1报数,数到dis的那个人出列,以此重复下去,直到N个人全部出列。

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct node *Node;

struct node
{
 int data;
 Node next;
};

Node creatCleList(int n)
{
 Node head = NULL;
 Node curr;
 Node tmp;
 int i = 1;

 if (n < 1)
 {
  return NULL;
 }


 tmp = new (struct node)();
 tmp->data = i;
 head = tmp;
 curr = head;

 for (i = 2; i <= n; ++i)
 {
  tmp = new (struct node)();
  tmp->data = i;
  curr->next = tmp;
  curr = curr->next;
 }
 curr->next = head;

 return head;
}

void freeCleList(Node head)
{
 Node trail = head;
 Node tmp;
 if (NULL == head)
 {
  return;
 }
 if (NULL == head->next)
 {
  delete []head;
  return;
 }
 head = head->next;
 while (head != trail)
 {
  tmp = head;
  cout << head->data << " was released." << endl;
  head = head->next;
  delete []tmp;
 }
 cout << head->data << " was released." << endl;
 delete []head;
}

void removeCleList(Node head, const int beg, const int dis)
{
 Node prev, tmp;
 int i = 1;
 prev = head;
 if (NULL == head)
 {
  cerr << "empty circle list." << endl;
  exit(1);
 }
 while (head->data != beg)
 {
  prev = head;
  head = head->next;
 }

 if (head == prev)
 {
  tmp = head;
  while (tmp->next != head)
  {
   tmp = tmp->next;
  }
  prev = tmp;
 }
 
 while (head != prev)
 {
  for (i = 1; i <= dis; ++i)
  {
   if (dis == i)
   {
    tmp = head;
    head = head->next;
    prev->next = head;    
    cout << tmp->data << " was removed." << endl;
    delete []tmp;    
   }
   else
   {
    prev = head;
    head = head->next;
   }
  }
 }

 cout << head->data << " was removed." << endl;
 delete []head;

}

int main()
{
 int n, beg, dis;
 Node head;
 cout << "input n, beg, dis." << endl;
 cin >> n >> beg >> dis;
 fflush(stdin);
 while (beg > n)
 {
  cerr << "beg can't bigger than n, pls input a new one." << endl;
  cin >> beg;
  fflush(stdin);
 }
 head = creatCleList(n);

 removeCleList(head, beg, dis);

 //freeCleList(head);
 return 0;
}

  评论这张
 
阅读(354)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018