【轻知识】循环链表、双向链表、双向循环链表、约瑟夫环

写完链表之后，这些就简单多了。额，这么说，也不对，万一迷糊了。就会耗很多时间想。

循环链表

#include<stdio.h>
#include<stdlib.h>

typedef struct Node {
    int data;
    struct Node* pNext;
} NODE,*PNODE;

PNODE create_list();
void traverse_list(PNODE);
PNODE reverse_list(PNODE);
int check_circle(PNODE pHead);
PNODE create_circle_list();
int main() {
    PNODE pHead = create_list();
    traverse_list(pHead);
    return 0;
}
PNODE create_list() {
    //1.首先mallc 一个地址
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL) {
        printf("malloc error");
    }
    int len;
    printf("please input len:");
    scanf("%d", &len);
    printf("len=%d\n", len);
    PNODE tempNode = pHead;
    int i;
    for(i = 0;i < len;i++) {
        //分配节点
        PNODE newNode = (PNODE)malloc(sizeof(NODE));
        if (newNode == NULL) {
            printf("malloc error");
        }
        printf("please input value:");
        int val;
        scanf("%d", &val);
        newNode->data = val;
        newNode->pNext = NULL;
        tempNode->pNext = newNode;
        tempNode = newNode;
        if ((len-1) == i) { // 既然是循环链表,最后一个指向第一个结点
            newNode->pNext = pHead->pNext;
        }
    }
    return pHead;
}
void traverse_list(PNODE pHead) {
    PNODE t = pHead->pNext;
    while(t != pHead->pNext) {
    //while(t != NULL) {
        printf("data=%d\n", t->data);
        t = t->pNext;
    }
    return ;
}

双向链表

#include<stdio.h>
#include<stdlib.h>

typedef struct Node {
    int data;
    struct Node* pNext;
    struct Node* pFront;
} NODE,*PNODE;

PNODE create_list();
void traverse_list(PNODE);
PNODE reverse_list(PNODE);
int check_circle(PNODE pHead);
PNODE create_circle_list();
int main() {
    PNODE pHead = create_list();
    traverse_list(pHead);
    return 0;
}
PNODE create_list() {
    //1.首先mallc 一个地址
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL) {
        printf("malloc error");
    }
    int len;
    printf("please input len:");
    scanf("%d", &len);
    printf("len=%d\n", len);
    PNODE tempNode = pHead;
    int i;
    for(i = 0;i < len;i++) {
        //分配节点
        PNODE newNode = (PNODE)malloc(sizeof(NODE));
        if (newNode == NULL) {
            printf("malloc error");
        }
        printf("please input value:");
        int val;
        scanf("%d", &val);
        newNode->data = val;
        newNode->pNext = NULL;
        tempNode->pNext = newNode;
        newNode->pFront  = tempNode;
        tempNode = newNode;
        //if ((len-1) == i) { // 既然是双向链表,最后一个指向第一个结点
        //  newNode->pNext = pHead->pNext;
        //}
    }
    return pHead;
}
void traverse_list(PNODE pHead) {
    PNODE t = pHead->pNext;
    while(t != NULL) {
        printf("front_data%d\n", t->pFront->data);
        printf("next_data=%d\n", t->data);
        printf("split line-------\n");
        t = t->pNext;
    }
    return ;
}

双向循环链表

#include<stdio.h>
#include<stdlib.h>

typedef struct Node {
    int data;
    struct Node* pNext;
    struct Node* pFront;
} NODE,*PNODE;

PNODE create_list();
void traverse_list(PNODE);
PNODE reverse_list(PNODE);
int check_circle(PNODE pHead);
void traverse_list2(PNODE pHead);
PNODE create_circle_list();
int main() {
    PNODE pHead = create_list();
    //traverse_list(pHead);
    traverse_list2(pHead);
    return 0;
}
PNODE create_list() {
    //1.首先mallc 一个地址
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL) {
        printf("malloc error");
    }
    int len;
    printf("please input len:");
    scanf("%d", &len);
    printf("len=%d\n", len);
    PNODE tempNode = pHead;
    PNODE oneNode = NULL;
    int i;
    for(i = 0;i < len;i++) {
        //分配节点
        PNODE newNode = (PNODE)malloc(sizeof(NODE));
        if (newNode == NULL) {
            printf("malloc error");
        }
        printf("please input value:");
        int val;
        scanf("%d", &val);
        newNode->data = val;
        newNode->pNext = NULL;
        tempNode->pNext = newNode;
        newNode->pFront  = tempNode;
        tempNode = newNode;
        //if (i == 0) {
        //  oneNode = newNode;;
        //}
        if ((len-1) == i) { // 既然是双向链表,最后一个指向第一个结点
            newNode->pNext = pHead->pNext;
            pHead->pNext->pFront = newNode;
        }
    }
    return pHead;
}
void traverse_list(PNODE pHead) {
    PNODE tt= pHead->pNext;
    PNODE t = NULL;
    //while(t != NULL) {
    while(t != pHead->pNext && (t=tt)) {
        printf("front_data%d\n", t->pFront->data);
        printf("next_data=%d\n", t->data);
        printf("split line-------\n");
        tt = tt->pNext;
        t = tt;
        sleep(1);
    }
    return ;
}
void traverse_list2(PNODE pHead) {
    PNODE t = pHead->pNext;
    //while(t != NULL) {
    int flag = 0;
    while(t != pHead->pNext ||  (flag==0)) {
        flag = 1;
        printf("front_data%d\n", t->pFront->data);
        printf("next_data=%d\n", t->data);
        printf("split line-------\n");
        t = t->pNext;
        sleep(1);
    }
    return ;
}

约瑟夫环

#include<stdio.h>
#include<stdlib.h>

typedef struct Node {
    int data;
    struct Node* pNext;
} NODE,*PNODE;

PNODE create_list();
int josephus(PNODE, int ,int);
int main() {
    PNODE pHead = create_list();
    int k,num;
    printf("please input k pos\n");
    scanf("%d",&k);
    printf("please input num\n");
    scanf("%d", &num);
    josephus(pHead, k, num);
    return 0;
}
PNODE create_list() {
    //1.首先mallc 一个地址
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL) {
        printf("malloc error");
    }
    int len;
    printf("please input len:");
    scanf("%d", &len);
    printf("len=%d\n", len);
    PNODE tempNode = pHead;
    int i;
    for(i = 0;i < len;i++) {
        //分配节点
        PNODE newNode = (PNODE)malloc(sizeof(NODE));
        if (newNode == NULL) {
            printf("malloc error");
        }
        printf("please input value:");
        int val;
        scanf("%d", &val);
        newNode->data = val;
        newNode->pNext = NULL;
        tempNode->pNext = newNode;
        tempNode = newNode;
        if ((len-1) == i) { // 既然是双向链表,最后一个指向第一个结点
            newNode->pNext = pHead->pNext;
        }
    }
    return pHead;
}
int josephus(PNODE pHead, int k, int m) {
    PNODE t = pHead->pNext;
//  while(t != pHead->pNext) {
    int count = 0;
    PNODE tempNode = NULL;
    PNODE frontNode = pHead;
    int flag = 0;
    while(t != NULL) {
        tempNode = t->pNext;
        //printf("data=%d\n", t->data);
        if (t->data == k && flag == 0) {
            count++;
            k = 0;
            flag = 1;
        }
        if (count == m) {
            printf("out %d\n", t->data);
            //1.出局
            if (t == t->pNext) {
                pHead->pNext = NULL;
                return 1;
            } else {
                frontNode->pNext = t->pNext;
            }
            free(t);
            //2.count 重置
            count = 0;
        }
        if (flag == 1) {
            count++;
        }
        frontNode = t;
        t = tempNode;
        //sleep(1);
    }
    return 0;
}