设为首页 加入收藏

TOP

循环链表和约瑟夫环
2017-06-14 10:22:44 】 浏览:6023
Tags:循环 约瑟夫

循环链表和约瑟夫环

循环链表的实现

单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head。

代码实现分为四部分:

1. 初始化

2. 插入

3. 删除

4. 定位寻找

代码实现:

void ListInit(Node *pNode){
    int item;
    Node *temp,*target;
    cout<<"输入0完成初始化"<
  
   >item;
        if(!item)
            return ;
        if(!(pNode)){ //当空表的时候,head==NULL 
            pNode = new Node ;
            if(!(pNode))
                exit(0);//未成功申请 
            pNode->data = item;
            pNode->next = pNode;
        }
        else{
            //
            for(target = pNode;target->next!=pNode;target = target->next)
                ;
            temp = new Node;
            if(!(temp))
                exit(0);
            temp->data = item;
            temp->next = pNode;
            target->next = temp;
        }
    }
} 
void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置 
    Node *temp;
    Node *target;
    int item;
    cout<<"输入您要插入的值:"<
   
    >item; if(i==1){ temp = new Node; if(!temp) exit(0); temp->data = item; for(target=pNode;target->next != pNode;target = target->next) ; temp->next = pNode; target->next = temp; pNode = temp; } else{ target = pNode; for (int j=1;j
    
     next; temp = new Node; if(!temp) exit(0); temp->data = item; temp->next = target->next; target->next = temp; } } void ListDelete(Node *pNode,int i){ Node *target,*temp; if(i==1){ for(target=pNode;target->next!=pNode;target=target->next) ; temp = pNode;//保存一下要删除的首节点 ,一会便于释放 pNode = pNode->next; target->next = pNode; delete temp; } else{ target = pNode; for(int j=1;j
     
      next; temp = target->next;//要释放的node target->next = target->next->next; delete temp; } } int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置 Node *target; int i=1; for(target = pNode;target->data!=elem && target->next!= pNode;++i) target = target->next; if(target->next == pNode && target->data!=elem) return 0; else return i; }
     
    
   
  

约瑟夫问题

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。这类问题用循环列表的思想刚好能解决。

注意:编写代码的时候,注意报数为m = 1的时候特殊情况

#include
  
   
#include
   
     using namespace std; typedef struct Node{ int data; Node *next; }; Node *Create(int n){ Node *p = NULL, *head; head = new Node; if (!head) exit(0); p = head; // p是当前指针 int item=1; if(n){ int i=1; Node *temp; while(i<=n){ temp = new Node; if(!temp) exit(0); temp->data = i++; p->next = temp; p = temp; } p->next = head->next; } delete head; return p->next; } void Joseph(int n,int m){ //n为总人数,m为数到第m个的退出 m = n%m; Node *start = Create(n); if(m){//如果取余数后的m!=0,说明 m!=1 while(start->next!=start){ Node *temp = new Node; if(!temp) exit(0); for(int i=0;i
    
     next; temp = start->next; start->next = start->next->next; start = start->next; cout<
     
      data<<" "; delete temp; } } else{ for(int i=0;i
      
       data<<" "; temp = start; start = start->next; delete temp; } } cout<
       
        data<
         
        
       
      
     
    
   
  
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇怎么找到最长子串位置 下一篇C常用库函数实现

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目