天天看點
傳回

Linux核心思想連結清單的系列循環連結清單以及求解約瑟夫問題circule_link_list.h頭檔案circule_link_list.c函數體Joseph_question.c約瑟夫環問題求解測試程式代碼

歡迎加入QQ：498903810 一起交流、讨論知識，裡面有大佬，也有小白，天下碼農一家親，大家一起讨論進步。

注：測試程式代碼和約瑟夫環問題求解不能同時運作，但是運作時需要包含頭檔案和函數體

circule_link_list.h頭檔案 

檔案:circule_link_list.h
代碼:
#ifndef _CIRCULE_LINK_LIST_H
#define _CIRCULE_LINK_LIST_H

typedef void CirculeLinkList;
typedef void CirculeLinkListNode;

typedef struct TagCirculeLinkListNode
{
    struct TagCirculeLinkListNode * next;
}TagCirculeLinkListNode;

//建立一個循環連結清單
CirculeLinkList * LinkLIst_Creat();

//銷毀一個循環連結清單
void LinkList_Destory(CirculeLinkList * list);

//清理一個循環連結清單
void LinkList_Clear(CirculeLinkList * list);

//求連結清單長度
int LinkList_Length(CirculeLinkList * list);

//插入節點
int LinkList_Insert(CirculeLinkList * list, CirculeLinkListNode * node, int pos);

//擷取連結清單節點資訊
CirculeLinkListNode * LinkList_Get(CirculeLinkList * list, int pos);

//删除節點
CirculeLinkListNode * LinkList_Delete(CirculeLinkList * list, int pos);
//add--->新增遊标概念

//删除遊标指向的節點
CirculeLinkListNode * CirculeLinkList_Delete(CirculeLinkList * list, CirculeLinkListNode * node);

//重置遊标
CirculeLinkListNode * CirculeLinkList_Reset(CirculeLinkList * list);

//擷取遊标位置
CirculeLinkListNode * CirculeLinkList_Current(CirculeLinkList * list);

//遊标下移
CirculeLinkListNode * CirculeLinkList_Next(CirculeLinkList * list);

#endif

circule_link_list.c函數體 

檔案:circule_link_list.c
代碼:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include "circule_link_list.h"

typedef struct TagCircleLink
{
    TagCirculeLinkListNode head;
    TagCirculeLinkListNode * vernier;//vernier遊标
    int length;
}TagCircleLink;

//建立一個循環連結清單
CirculeLinkList * LinkLIst_Creat()
{
    TagCircleLink * begin;
    begin = (TagCircleLink *)malloc(sizeof(TagCircleLink));
    if (NULL == begin)
    {
        printf("(TagCircleLink *)malloc(sizeof(TagCircleLink)) error");
        return NULL;
    }
    begin->vernier = NULL;
    begin->length = ;
    begin->head.next = NULL;
    return (void *)begin;
}
//銷毀一個循環連結清單
void LinkList_Destory(CirculeLinkList * list)
{
    if (NULL != list)
    {
        free(list);
    }
}
//清理一個循環連結清單
void LinkList_Clear(CirculeLinkList * list)
{
    TagCircleLink * begin;
    begin = (TagCircleLink *)list;
    begin->head.next = NULL;
    begin->length = ;
    begin->vernier = NULL;
}
//求連結清單長度
int LinkList_Length(CirculeLinkList * list)
{
    TagCircleLink * begin;
    begin = (TagCircleLink *)list;
    return begin->length;
}
//插入節點
int LinkList_Insert(CirculeLinkList * list, CirculeLinkListNode * node, int pos)
{
    if (NULL == list || NULL == node || pos < )
    {
        return -;
    }
    TagCircleLink * begin = NULL;
    TagCirculeLinkListNode * insert = NULL, * tmp = NULL;

    begin = (TagCircleLink *)list;
    insert = (TagCirculeLinkListNode *)node;
    if (NULL == begin->head.next)//第一個插入的元素特殊處理
    {
        begin->head.next = insert;
        insert->next = insert;
        begin->vernier = insert;//遊标指向0号結點
        begin->length++;
        return ;
    }

    //如果插入的是零号位置特殊處理，插入零号位置相當于插入在最後一個位置，然後把頭結點後移一位,
    if (pos > begin->length)
    {
        pos = begin->length;
    }
    if ( == pos)
    {
        LinkList_Insert(list, node, begin->length);
        begin->head.next = insert;
        begin->vernier = insert;
        return ;
    }

    tmp = begin->head.next;
    for (int i = ; i < pos - ; i++)
    {
        tmp = tmp->next;
    }
    insert->next = tmp->next;
    tmp->next = insert;
    begin->length++;
    return ;
}
//擷取連結清單節點資訊
CirculeLinkListNode * LinkList_Get(CirculeLinkList * list, int pos)
{
    if (NULL == list  || pos < )
    {
        return NULL;
    }
    TagCircleLink * begin = NULL;
    TagCirculeLinkListNode * tmp = NULL;
    begin = (TagCircleLink *)list;
    tmp = begin->head.next;
    for (int i = ; i < pos; i++)
    {
        tmp = tmp->next;
    }
    return (void *)tmp;
}
//删除節點
CirculeLinkListNode * LinkList_Delete(CirculeLinkList * list, int pos)
{
    if (NULL == list || pos < )
    {
        return NULL;
    }
    TagCircleLink * begin = NULL;
    TagCirculeLinkListNode * tmp = NULL, * ret = NULL;
    begin = (TagCircleLink *)list;
    tmp = begin->head.next;
    if (pos >= begin->length)
    {
        return NULL;
    }
    if (begin->vernier == (TagCirculeLinkListNode *)LinkList_Get(list, pos))//如果删除的結點是遊标指向的位置，遊标下移
    {
        begin->vernier = begin->vernier->next;
    }
    if (begin->length ==  && pos == )//如果删除的最後一個結點
    {
        CirculeLinkListNode * ret = begin->head.next;
        begin->length--;
        begin->vernier = NULL;
        begin->head.next = NULL;
        return ret;
    }
    if ( == pos)//如果是删除的頭号結點特殊處理
    {
        begin->head.next = begin->head.next->next;//頭結點移到一号位置
        CirculeLinkListNode * sign = LinkList_Delete(list, begin->length - );//删除最後一個元素
        if (NULL != sign)
        {
            return sign;
        }
        else
            return NULL;
    }


    for (int i = ; i < pos - ; i++)//删除普通結點
    {
        tmp = tmp->next;
    }
    ret = tmp->next;
    tmp->next = tmp->next->next;
    begin->length--;
    return (void *)ret;
}

//add--->新增遊标概念
//删除遊标指向的節點
CirculeLinkListNode * CirculeLinkList_Delete(CirculeLinkList * list, CirculeLinkListNode * node)
{
    //node是要删除的位置
    if (NULL == list || NULL == node)
    {
        return NULL;
    }
    int i = ;
    TagCirculeLinkListNode * del = (TagCirculeLinkListNode *)node, * tmp = NULL;
    TagCircleLink * begin = (TagCircleLink *)list;
    tmp = begin->head.next;
    for (i = ; i <= begin->length; i++)//找到要删除的結點的位置
    {
        if (i == begin->length)
        {
            return NULL;
        }
        if (del == tmp)
        {
            break;
        }
        tmp = tmp->next;
    }
    tmp = (TagCirculeLinkListNode *)LinkList_Delete(list, i);//移動結點
    if (tmp != NULL)
    {
        return tmp;
    }
    else
        return NULL;

}
//重置遊标
CirculeLinkListNode * CirculeLinkList_Reset(CirculeLinkList * list)
{
    if (NULL == list)
    {
        return NULL;
    }
    TagCircleLink * begin = NULL;
    begin = (TagCircleLink *)list;

    begin->vernier = begin->head.next;
    return (CirculeLinkListNode *)begin->vernier;
}
//擷取遊标位置
CirculeLinkListNode * CirculeLinkList_Current(CirculeLinkList * list)
{
    if (NULL == list)
    {
        return NULL;
    }
    TagCircleLink * begin = (TagCircleLink *)list;
    return (CirculeLinkListNode *)begin->vernier;

}
//遊标下移
CirculeLinkListNode * CirculeLinkList_Next(CirculeLinkList * list)
{
    if (NULL == list)
    {
        return NULL;
    }
    TagCircleLink * begin = (TagCircleLink *)list;
    (TagCirculeLinkListNode *)begin->vernier;
    begin->vernier = begin->vernier->next;
    return (CirculeLinkListNode *)begin->vernier;
}

Joseph_question.c約瑟夫環問題求解 

檔案:Joseph_question.c
代碼:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include "circule_link_list.h"

typedef struct Teacher
{
    TagCirculeLinkListNode * next;
    int age;
    char name[];
}Teacher;

int main()
{
    Teacher t1;
    Teacher t2;
    Teacher t3;
    Teacher t4;
    Teacher t5;
    Teacher t6;
    Teacher t7;
    Teacher t8;
    Teacher t9;
    t1.age = ;
    t2.age = ;
    t3.age = ;
    t4.age = ;
    t5.age = ;
    t6.age = ;
    t7.age = ;
    t8.age = ;
    t9.age = ;

    CirculeLinkList * list;
    Teacher * tmp;
    CirculeLinkList * ret = NULL;
    //建立連結清單
    list = LinkLIst_Creat();

    //插入元素
    LinkList_Insert(list, (CirculeLinkListNode *)&t1, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t2, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t3, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t4, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t5, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t6, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t7, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t8, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t9, );

    //周遊元素
    for (int i = ; i < LinkList_Length(list); i++)
    {
        Teacher *tmp = NULL;
        ret = LinkList_Get(list, i);
        tmp = (Teacher *)ret;
        printf("age = %d\n", tmp->age);
    }

    printf("約瑟夫問題求解\n");
    for (int i = ; i < LinkList_Length(list);)
    {
        for (int j = ; j < ; j++)
        {
            CirculeLinkList_Next(list);
        }
        ret = CirculeLinkList_Delete(list, CirculeLinkList_Current(list));
        if (ret != NULL)
        {
            tmp = (Teacher *)ret;
            printf("age = %d\n", tmp->age);
        }
        else
        {
            printf("error\n");
        }
    }
    system("pause");
    return ;
}

測試程式代碼 

程式測試代碼
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include "circule_link_list.h"

typedef struct Teacher
{
    TagCirculeLinkListNode * next;
    int age;
    char name[];
}Teacher;

int main()
{
    Teacher t1;
    Teacher t2;
    Teacher t3;
    Teacher t4;
    Teacher t5;
    t1.age = ;
    t2.age = ;
    t3.age = ;
    t4.age = ;
    t5.age = ;
    CirculeLinkList * list;
    CirculeLinkList * ret = NULL;
    //建立連結清單
    list = LinkLIst_Creat();

    //插入元素
    LinkList_Insert(list, (CirculeLinkListNode *)&t1, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t2, );
    LinkList_Insert(list, (CirculeLinkListNode *)&t3, );

    //CirculeLinkListNode * LinkList_Get(CirculeLinkList * list, int pos);
    //周遊元素
    for (int i = ; i < LinkList_Length(list); i++)
    {
        Teacher *tmp = NULL;
        ret = LinkList_Get(list, i);
        tmp = (Teacher *)ret;
        printf("age = %d\n", tmp->age);
    }

    删除元素 --- > 測試通過
    //for (int i = 0; i < LinkList_Length(list);)
    //{
    //  ret = LinkList_Delete(list, 0);
    //  if (ret == NULL)
    //  {
    //      printf("删除失敗!!!\n");
    //      break;
    //  }
    //  else
    //  {
    //      Teacher *tmp = NULL;
    //      tmp = (Teacher *)ret;
    //      printf("被删除的年齡是 age = %d\n", tmp->age);
    //  }
    //}

    //測試通過
    //ret = CirculeLinkList_Delete(list, (CirculeLinkListNode *)& t1);
    //if (ret == NULL)
    //{
    //  printf("失敗!!!\n");
    //}
    //else
    //{
    //  Teacher *tmp = NULL;
    //  tmp = (Teacher *)ret;
    //  printf("年齡是 age = %d\n", tmp->age);
    //}
    周遊元素
    //for (int i = 0; i < LinkList_Length(list); i++)
    //{
    //  Teacher *tmp = NULL;
    //  ret = LinkList_Get(list, i);
    //  tmp = (Teacher *)ret;
    //  printf("age = %d\n", tmp->age);
    //}

    //測試通過
    //ret = CirculeLinkList_Reset(list);
    //Teacher *tmp = NULL;
    //tmp = (Teacher *)ret;
    //printf("年齡是 age = %d\n", tmp->age);

    ret = CirculeLinkList_Next(list);
    Teacher *tmp = NULL;
    tmp = (Teacher *)ret;
    printf("年齡是 age = %d\n", tmp->age);

    /*
    //建立一個循環連結清單
    CirculeLinkList * LinkLIst_Creat();
    //銷毀一個循環連結清單
    void LinkList_Destory(CirculeLinkList * list);
    //清理一個循環連結清單
    void LinkList_Clear(CirculeLinkList * list);
    //求連結清單長度
    int LinkList_Length(CirculeLinkList * list);
    //插入節點
    int LinkList_Insert(CirculeLinkList * list, CirculeLinkListNode * node, int pos);
    //擷取連結清單節點資訊
    CirculeLinkListNode * LinkList_Get(CirculeLinkList * list, int pos);
    //删除節點
    CirculeLinkListNode * LinkList_Delete(CirculeLinkList * list, int pos);
    //add--->新增遊标概念
    //删除遊标指向的節點
    CirculeLinkListNode * CirculeLinkList_Delete(CirculeLinkList * list, CirculeLinkListNode * node);
    //重置遊标
    CirculeLinkListNode * CirculeLinkList_Reset(CirculeLinkList * list);
    //擷取遊标位置
    CirculeLinkListNode * CirculeLinkList_Current(CirculeLinkList * list);
    //遊标下移
    CirculeLinkListNode * CirculeLinkList_Next(CirculeLinkList * list);
    */
    system("pause");
    return ;
}
算法 c語言 約瑟夫環 循環連結清單
上一篇: 約瑟夫環 連結清單java_java連結清單實作約瑟夫環
下一篇: “金九銀十”你準備好了嗎？Android面試超全知識點合集，沖刺大廠高薪崗，輕松應對面試官的每一問

繼續閱讀