C語言的循環鏈表和約瑟夫環

相關推薦

C語言的循環鏈表和約瑟夫環

　　約瑟夫問題）是一個數學的應用問題，對于學習C語言四非常挺有幫助的，下面是小編為大家搜集整理出來的有關于C語言的循環鏈表和約瑟夫環，一起了解下吧!

　　循環鏈表的實現

　　單鏈表只有向后結點，當單鏈表的尾鏈表不指向NULL，而是指向頭結點時候，形成了一個環，成為單循環鏈表，簡稱循環鏈表。當它是空表，向后結點就只想了自己，這也是它與單鏈表的主要差異，判斷node->next是否等于head。

　　代碼實現分為四部分：

　　1. 初始化

　　2. 插入

　　3. 刪除

　　4. 定位尋找

　　代碼實現：

void ListInit(Node *pNode){
    int item;
    Node *temp,*target;
    cout<<"輸入0完成初始化"<<endl; cin="">>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<<"輸入您要插入的值:"<<endl; cin="">>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<i-1;++j) target="target-">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;
         temp; 
    }
    else{
        target = pNode;
        for(int j=1;j<i-1;++j) target="target-">next;
        temp = target->next;//要釋放的`node
        target->next = target->next->next;
         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;
}</i-1;++j)></i-1;++j)></endl;></endl;>

　　約瑟夫問題

　　約瑟夫環(約瑟夫問題)是一個數學的應用問題：已知n個人(以編號1，2，3…n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列;他的`下一個人又從1開始報數，數到m的那個人又出列;依此規律重復下去，直到圓桌周圍的人全部出列。這類問題用循環列表的思想剛好能解決。

　　注意：編寫代碼的時候，注意報數為m = 1的時候特殊情況

#include<iostream>
#include<cstdio>
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;
    }
     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<m-1;i++) 1="" m="3%2" start="start-">next;
            temp = start->next;
            start->next = start->next->next;
            start = start->next;
            cout<<temp->data<<" ";
             temp;
        }
    }
    else{
        for(int i=0;i<n-1;i++){ node="" start-="" temp="new">data<<" ";
            temp = start;
            start = start->next;
             temp;
        }
    }
    cout<<endl; last="" person="" start-="" the="">data<<endl; int="" pre="" return="">
         
    
</endl;></endl;></n-1;i++){></temp-></m-1;i++)></cstdio></iostream>

【C語言的循環鏈表和約瑟夫環】相關文章：

C語言用數組解決約瑟夫環問題09-01

c語言鏈表的用法10-20

C語言單向鏈表環測試并返回環起始節點的方法10-04

C語言for循環11-05

c語言鏈表的用法有哪些09-07

鏈表的C語言實現方法08-27

C語言鏈表逆序方法技巧08-21

C語言中while循環和do...while循環07-19

C#數據結構之循環鏈表的實例代碼10-22