企业版循环单链表

//头文件:CircleLinkList.h
 1 #pragma once
 2 
 3 #include<stdlib.h>
 4 #include<stdio.h>
 5 //小链表结点
 6 typedef struct CIRCLELINKNODE
 7 {
 8     struct CIRCLELINKNODE* next;
 9 }CircleLinkNode;
10 //链表结点
11 typedef struct CIRCLELINKLIST
12 {
13     CircleLinkNode head;
14     int size;
15 }CircleLinkList; 
16 
17 //比较回调
18 typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);
19 //打印回调
20 typedef void(*PRINTNODE)(CircleLinkNode*);
21 //初始化
22 CircleLinkList* Init_CircleLinkList();
23 //插入
24 void Insert_CircleLinkList(CircleLinkList* list, int pos, CircleLinkNode* value);
25 //获取第一个元素
26 CircleLinkNode* Front_CircleLinkList(CircleLinkList* list);
27 //获取最后一个元素
28 CircleLinkNode* Back_CircleLinkList(CircleLinkList* list);
29 //根据位置删除
30 void RemovePos_CircleLinkList(CircleLinkList* list, int pos);
31 //根据值删除
32 void RemoveValue_CircleLinkList(CircleLinkList* list, CircleLinkNode* value,COMPARENODE compare);
33 //获得链表长度
34 int Length_CircleLinkList(CircleLinkList* list);
35 //释放
36 void Free_CircleLinkList(CircleLinkList* list);
37 //查找
38 int Find_CircleLinkList(CircleLinkList* list, CircleLinkNode* value, COMPARENODE compare);
39 //判断是否为空
40 bool IsEmpty_Find_CircleLinkList(CircleLinkList* list);
41 //打印
42 void Print_CircleLinkList(CircleLinkList* list, PRINTNODE print);

 //头文件的实现CircleLinkList.cpp

  1#include "CircleLinkList.h"
  2 //初始化
  3 CircleLinkList* Init_CircleLinkList()
  4 {
  5     CircleLinkList* list = (CircleLinkList*)malloc(sizeof(CircleLinkList));
  6     if (list == NULL)
  7     {
  8         exit(1);
  9     }
 10     list->head.next = &(list->head);//头结点指向自己
 11     list->size = 0;
 12 
 13     return list;
 14 }
 15 //插入
 16 void Insert_CircleLinkList(CircleLinkList* list, int pos, CircleLinkNode* value)
 17 {
 18     if (list == NULL)
 19     {
 20         exit(1);
 21     }
 22 
 23     if (value == NULL)
 24     {
 25         exit(1);
 26     }
 27 
 28     if (pos < 0 || pos > list->size)
 29     {
 30         pos = list->size;
 31     }
 32 
 33     //辅助指针变量借助指针找到查找位置的前一个结点
 34     CircleLinkNode* pCurrent = &(list->head);
 35     for(int i = 0; i < list->size; i++)
 36     {
 37         pCurrent = pCurrent->next;
 38     }
 39 
 40     //插入
 41     value->next = pCurrent->next;
 42     pCurrent->next = value;
 43 
 44     list->size++;
 45 }
 46 //获取第一个元素
 47 CircleLinkNode* Front_CircleLinkList(CircleLinkList* list)
 48 {
 49     if (list == NULL)
 50     {
 51         exit(1);
 52     }
 53 
 54     return list->head.next;
 55 }
 56 //获取最后一个元素
 57 CircleLinkNode* Back_CircleLinkList(CircleLinkList* list)
 58 {
 59     if (list == NULL)
 60     {
 61         exit(1);
 62     }
 63 
 64     //辅助指针变量借助指针找到查找位置的前一个结点
 65     CircleLinkNode* pCurrent = &(list->head);
 66     for(int i = 0;i <list->size;++i)
 67     {
 68         pCurrent = pCurrent->next;
 69     }
 70 
 71     return pCurrent;
 72 }
 73 //根据位置删除
 74 void RemovePos_CircleLinkList(CircleLinkList* list, int pos)
 75 {
 76     if (list == NULL)
 77     {
 78         exit(1);
 79     }
 80 
 81     if (pos < 0 || pos >= list->size)
 82     {
 83         exit(1);
 84     }
 85 
 86     //辅助指针变量找位置前一个结点
 87     CircleLinkNode* pCurrent = &(list->head);
 88     for (int i = 0; i < pos; ++i)
 89     {
 90         pCurrent = pCurrent->next;
 91     }
 92 
 93     //删除
 94     CircleLinkNode* p = pCurrent->next;
 95     pCurrent->next = p->next;
 96     list->size--;
 97 }
 98 //根据值删除
 99 void RemoveValue_CircleLinkList(CircleLinkList* list, CircleLinkNode* value, COMPARENODE compare)
100 {
101     if (list == NULL)
102     {
103         exit(1);
104     }
105 
106     if (value == NULL)
107     {
108         exit(1);
109     }
110 
111     //辅助指针变量找位置前一个结点
112     CIRCLELINKNODE* pCurrent = &(list->head);
113     CIRCLELINKNODE* qCurrent = pCurrent->next;
114     for(int i = 0;i < list->size; ++i)
115     {
116         if (compare(qCurrent, value) == 0)
117         {
118             pCurrent->next = qCurrent->next;
119             list->size--;
120             break;
121         }
122         pCurrent = qCurrent;
123         qCurrent = pCurrent->next;
124     }    
125 }
126 //获得链表长度
127 int Length_CircleLinkList(CircleLinkList* list)
128 {
129     if (list == NULL)
130     {
131         exit(1);
132     }
133 
134     return list->size;
135 }
136 
137 //释放
138 void Free_CircleLinkList(CircleLinkList* list)
139 {
140     if (list == NULL)
141     {
142         exit(1);
143     }
144 
145     free(list);
146 }
147 //查找
148 int Find_CircleLinkList(CircleLinkList* list, CircleLinkNode* value, COMPARENODE compare)
149 {
150     if (list == NULL)
151     {
152         exit(1);
153     }
154 
155     if (value == NULL)
156     {
157         exit(1);
158     }
159 
160     CIRCLELINKNODE* pCurrent = list->head.next;
161     int flag = -1;
162     for (int i = 0; i < list->size; ++i)
163     {
164         if (compare(pCurrent, value) == 0)
165         {
166             flag = i;
167             break;
168         }
169         pCurrent = pCurrent->next;
170     }
171 
172     return flag;
173 }
174 
175 //判断是否为空
176 bool IsEmpty_Find_CircleLinkList(CircleLinkList* list)
177 {
178     if (list == NULL)
179     {
180         exit(1);
181     }
182 
183     return list->size == 0;
184 }
185 
186 //打印
187 void Print_CircleLinkList(CircleLinkList* list, PRINTNODE print)
188 {
189     if (list == NULL)
190     {
191         exit(1);
192     }
193 
194     //辅助指针变量
195     CircleLinkNode* pCurrent = list->head.next;
196     for (int i = 0; i < list->size; i++)
197     {
198         if (pCurrent == &(list->head))
199         {
200             pCurrent = pCurrent->next;
201             printf("---------------------
");
202         }
203         print(pCurrent);
204         pCurrent = pCurrent->next;
205     }
206 
207     
208 }

1、基本功能测试：

  1 #include"CircleLinkList.h"
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #include<stdio.h>
  5 //要添加到链表中的元素类型
  6 typedef struct PERSON
  7 {
  8     CircleLinkNode node;
  9     char name[65];
 10     int age;
 11     int score;
 12 }Person;
 13 
 14 void MyPrint(CircleLinkNode* value)
 15 {
 16     Person* p = (Person*)value;
 17     printf("Name : %s  Age : %d Score %d
", p->name, p->age, p->score);
 18 }
 19 
 20 int MyCompare(CircleLinkNode* value1, CircleLinkNode* value2)
 21 {
 22     Person* p1 = (Person*)value1;
 23     Person* p2 = (Person*)value2;
 24 
 25     if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age && p1->score == p2->score)
 26     {
 27         return 0;
 28     }
 29 
 30     return -1;
 31 }
 32 
 33 int main(int argc, const char* argv[])
 34 {
 35     //创建循环链表
 36     CircleLinkList* list = Init_CircleLinkList();
 37     //创建数据
 38     Person p1, p2, p3, p4, p5;
 39     strcpy_s(p1.name, "aaa");
 40     strcpy_s(p2.name, "bbb");
 41     strcpy_s(p3.name, "ccc");
 42     strcpy_s(p4.name, "ddd");
 43     strcpy_s(p5.name, "eee");
 44 
 45     p1.age = 20;
 46     p2.age = 30;
 47     p3.age = 40;
 48     p4.age = 50;
 49     p5.age = 60;
 50 
 51     p1.score = 55;
 52     p2.score = 66;
 53     p3.score = 77;
 54     p4.score = 88;
 55     p5.score = 99;
 56 
 57     //插入
 58     Insert_CircleLinkList(list, 0, (CircleLinkNode*)&p1);
 59     Insert_CircleLinkList(list, 0, (CircleLinkNode*)&p2);
 60     Insert_CircleLinkList(list, 0, (CircleLinkNode*)&p3);
 61     Insert_CircleLinkList(list, 0, (CircleLinkNode*)&p4);
 62     Insert_CircleLinkList(list, 0, (CircleLinkNode*)&p5);
 63     //打印数据
 64     Print_CircleLinkList(list, MyPrint);
 65     printf("------------------
");
 66     //返回第一个元素
 67     CircleLinkNode* value = Front_CircleLinkList(list);
 68     Person* p = (Person*)value;
 69     printf("第一个元素Name : %s  Age : %d Score %d
", p->name, p->age, p->score);
 70     printf("------------------
");
 71     //返回最后一个元素
 72     CircleLinkNode* value1 = Back_CircleLinkList(list);
 73     Person* g = (Person*)value1;
 74     printf("最后一个元素Name : %s  Age : %d Score %d
", g->name, g->age, g->score);
 75     printf("------------------
");
 76     //返回数据元素个数
 77     int length = Length_CircleLinkList(list);
 78     printf("数据元素个数：%d-----------------
", length);
 79     //链表是否为空
 80     bool ret = IsEmpty_Find_CircleLinkList(list);
 81     printf("链表是否为空：%d-----------------
", ret);
 82     //链表按值删除
 83     Person p7;
 84     strcpy_s(p7.name, "ccc");
 85     p7.age = 40;
 86     p7.score = 77;
 87     //RemoveValue_CircleLinkList(list, (CircleLinkNode*)&p7, MyCompare);
 88     //Print_CircleLinkList(list, MyPrint);
 89     printf("------------------
");
 90     //链表按位置删除
 91     RemovePos_CircleLinkList(list, 2);
 92     Print_CircleLinkList(list, MyPrint);
 93     printf("------------------
");
 94     //查找某值
 95     Person p8;
 96     strcpy_s(p8.name, "aaa");
 97     p8.age = 20;
 98     p8.score = 55;
 99     int i = Find_CircleLinkList(list, (CircleLinkNode*)&p8, MyCompare);
100     printf("%d", i);
101     Free_CircleLinkList(list);
102     system("pause");
103     return 0;
104 }

结果：

2、循环链表测试约瑟夫问题：

//#include"企业链表.h"
#include"CircleLinkList.h"
#include<string.h>
#include<stdlib.h>
#include<stdio.h>

#define M 8
#define N 3
//数据元素结构体
typedef struct PERSON
{
    CircleLinkNode node;
    int data;
}Person;

void MyPrint(CircleLinkNode* value)
{
    Person* p = (Person*)value;
    printf("data : %d  
", p->data);
}

int MyCompare(CircleLinkNode* value1, CircleLinkNode* value2)
{
    Person* p1 = (Person*)value1;
    Person* p2 = (Person*)value2;

    if ( p1->data == p2->data)
    {
        return 0;
    }

    return -1;
}

int main(int argc, const char* argv[])
{
    //创建循环链表
    CircleLinkList* list = Init_CircleLinkList();
    //创建数据
    Person num[M];
    for (int i = 0; i < M; ++i)
    {
        num[i].data = i + 1;
        Insert_CircleLinkList(list, i, (CircleLinkNode*)&num[i]);
    }
    
    //打印数据
    Print_CircleLinkList(list, MyPrint);
    printf("------------------
");
    
    //辅助指针变量
    CircleLinkNode* pCurrent = list->head.next;
    int index = 1;
    while (Length_CircleLinkList(list) > 1)
    {
        if (index == N)
        {
            Person* temp = (Person*)pCurrent;
            printf("value:%d
", temp->data);

            CircleLinkNode* p = pCurrent->next;
            RemoveValue_CircleLinkList(list, pCurrent, MyCompare);
            pCurrent = p;

            if (pCurrent == &(list->head))
            {
                pCurrent = pCurrent->next;
            }

            index = 1;
        }


        pCurrent = pCurrent->next;
        if (pCurrent == &(list->head))
        {
            pCurrent = pCurrent->next;
        }
        index++;
    }

    if (Length_CircleLinkList(list) == 1)
    {
        Person* tmp = (Person*)Front_CircleLinkList(list);
        printf("value:%d", tmp->data);
    }

    Free_CircleLinkList(list);
    system("pause");
    return 0;
}