[已解决]C语言数据结构-约瑟夫问题

qiao141486

1. #ifndef CIRCLELINKLIST
   
2. #define CIRCLELINKLIST
   
3. 
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. #define CIRCLELINKLIST_TRUE 1
   
7. #define CIRCLELINKLIST_FALSE 0
   
8. //链表小结点
   
9. typedef struct CIRCLELINKNODE{
   
10.         struct CIRCLELINKNODE * next;
    
11. 
    
12. }CircleLinkNode;
    
13. //链表结构体
    
14. typedef struct CIRCLELINKLIST{
    
15.         CircleLinkNode head;
    
16.         int size;//判断循环是否停止的标志
    
17. }CircleLinkList;
    
18. 
    
19. //编写针对链表结构体操作的API函数
    
20. 
    
21. //比较回调
    
22. typedef void(*PRINTLINKLIST)(CircleLinkNode *);
    
23. typedef int(*COMPARENODE)(CircleLinkNode *, CircleLinkNode *);
    
24. 
    
25. //初始化函数
    
26. CircleLinkList * Init_CircleLinkList();
    
27. //插入函数
    
28. void Insert_CircleLinkList(CircleLinkList * clist, int pos, CircleLinkNode* data);
    
29. //根据位置删除
    
30. void RemoveByPos_CircleLinkList(CircleLinkList * clist, int pos);
    
31. //根据值删除函数
    
32. void RemoveByValue_CircleLinkList(CircleLinkList * clist, CircleLinkNode * data, COMPARENODE compare);
    
33. //获取链表的长度
    
34. int Size_CircleLinkList(CircleLinkList * clist);
    
35. //判断是否为空
    
36. int IsEmpty_CircleLinkList(CircleLinkList * clist);
    
37. //返回第一个元素
    
38. CircleLinkNode *  Front_CircleLinkList(CircleLinkList * clist);
    
39. int Find_CircleLinkList(CircleLinkList * clist, CircleLinkNode * data, COMPARENODE compare);
    
40. //打印
    
41. void Print_CircleLinkList(CircleLinkList * clist, PRINTLINKLIST print);
    
42. //释放
    
43. void FreeSpace_CircleLinkList(CircleLinkList  * clist);
    
44. #endif

复制代码

1. #include "CircleLinkList.h"
   
2. 
   
3. //初始化函数
   
4. CircleLinkList * Init_CircleLinkList(){
   
5. 
   
6.         CircleLinkList *clist = (CircleLinkList *)malloc(sizeof(CircleLinkList));
   
7.         clist->head.next = &(clist->head);//指向自己
   
8.         clist->size = 0;
   
9.         return clist;
   
10. }
    
11. //插入函数
    
12. void Insert_CircleLinkList(CircleLinkList * clist, int pos, CircleLinkNode* data){
    
13.         if (clist == NULL)
    
14.         {
    
15.                 return;
    
16.         }
    
17.         if (data == NULL)
    
18.         {
    
19.                 return;
    
20.         }
    
21.         if (pos < 0 || pos >= clist->size)
    
22.         {
    
23.                 pos = clist->size;
    
24.         }
    
25.         //根据位置查找结点
    
26.         //辅助指针变量
    
27.         CircleLinkNode * pCurrent = &(clist->head);
    
28.         for (int i = 0; i < pos; i++)
    
29.         {
    
30.                 pCurrent = pCurrent->next;
    
31.         }
    
32.         data->next = pCurrent->next;
    
33.         pCurrent->next = data;
    
34. 
    
35.         clist->size++;
    
36. 
    
37. }
    
38. //根据位置删除
    
39. void RemoveByPos_CircleLinkList(CircleLinkList * clist, int pos){
    
40.         if (clist == NULL)
    
41.         {
    
42.                 return;
    
43.         }
    
44.         if (pos < 0 || pos >= clist->size){
    
45.                 return;
    
46.         }
    
47.         CircleLinkNode  * pCurrent = &(clist->head);
    
48.         for (int i = 0; i < pos; i++){
    
49.                 pCurrent = pCurrent->next;
    
50.         }
    
51.         //缓存当前结点的下一个结点
    
52.         CircleLinkNode * pNext = pCurrent->next;
    
53.         pCurrent->next = pNext->next;
    
54.         clist->size--;
    
55. 
    
56. }
    
57. //根据值删除函数
    
58. void RemoveByValue_CircleLinkList(CircleLinkList * clist, CircleLinkNode * data, COMPARENODE compare){
    
59.         if (clist == NULL){
    
60.                 return;
    
61.         }
    
62.         if (data == NULL){
    
63.                 return;
    
64.         }
    
65.         CircleLinkNode * pPrev = &(clist->head);
    
66.         CircleLinkNode * pCurrent = pPrev->next;
    
67.         int i = 0;
    
68.         for (i = 0; i < clist->size; i++){
    
69.                 if (compare(pCurrent, data) == CIRCLELINKLIST_TRUE)
    
70.                 {
    
71.                         pPrev->next = pCurrent->next;
    
72.                         break;
    
73. 
    
74.                 }
    
75.                 pPrev = pCurrent;
    
76.                 pCurrent = pPrev->next;
    
77.         }
    
78. 
    
79.         clist->size--;
    
80. 
    
81. }
    
82. //获取链表的长度
    
83. int Size_CircleLinkList(CircleLinkList * clist){
    
84.         return clist->size;
    
85. }
    
86. //判断是否为空
    
87. int IsEmpty_CircleLinkList(CircleLinkList * clist){
    
88.         if (clist->size == 0)
    
89.         {
    
90.                 return CIRCLELINKLIST_TRUE;
    
91.         }
    
92.         return CIRCLELINKLIST_FALSE;
    
93. }
    
94. //返回第一个元素
    
95. CircleLinkNode *  Front_CircleLinkList(CircleLinkList * clist){
    
96. 
    
97.         return clist->head.next;
    
98. }
    
99. //查找
    
100. int Find_CircleLinkList(CircleLinkList * clist, CircleLinkNode * data, COMPARENODE compare){
     
101.         if (clist == NULL)
     
102.         {
     
103.                 return -1;
     
104.         }
     
105.         if (data == NULL)
     
106.         {
     
107.                 return -1;
     
108.         }
     
109. 
     
110.         CircleLinkNode * pCurrent = clist->head.next;
     
111. 
     
112.         int flag = -1;
     
113.         for (int i = 0; i < clist->size; i++)
     
114.         {
     
115.                 if (compare(pCurrent, data) == CIRCLELINKLIST_TRUE){
     
116.                         flag = i;
     
117.                         break;
     
118.                 }
     
119.                 pCurrent = pCurrent->next;
     
120.         }
     
121. 
     
122.         return flag;
     
123. }
     
124. 
     
125. 
     
126. //打印
     
127. void Print_CircleLinkList(CircleLinkList * clist, PRINTLINKLIST print){
     
128.         if (clist == NULL){
     
129. 
     
130.                 return;
     
131.         }
     
132.         CircleLinkNode * pCurrent = clist->head.next;
     
133.         for (int i = 0; i < clist->size; i++){
     
134.                 if (pCurrent == &(clist->head))
     
135.                 {
     
136.                         pCurrent = pCurrent->next;
     
137.                         printf("-------------------------- \n");
     
138.                 }
     
139.                 print(pCurrent);
     
140.                 pCurrent = pCurrent->next;
     
141.         }
     
142. 
     
143. }
     
144. void FreeSpace_CircleLinkList(CircleLinkList  * clist)
     
145. {
     
146.         if (clist == NULL){
     
147. 
     
148.                 return;
     
149.         }
     
150.         free(clist);
     
151. 
     
152. }

复制代码

1. #define _CRT_CECURE_NO_WARNINGS
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. #include "CircleLinkList.h"
   
6. #define M 8
   
7. #define N 3
   
8. typedef struct MYNUM {
   
9.         CircleLinkNode node;
   
10.         int val;
    
11. }MyNum;
    
12. void MyPrint(CircleLinkList * data){
    
13.         MyNum* num = (MyNum*)data;
    
14.         printf("%d ", num->val);
    
15. }
    
16. int MyCompare(CircleLinkNode * data1, CircleLinkNode * data2){
    
17.             MyNum * num1 = (MyNum*)data1;
    
18.                 MyNum* num2 = (MyNum*)data2;
    
19.                 if (num1->val == num2->val){
    
20.                         CIRCLELINKLIST_TRUE;
    
21.                 }
    
22.                 CIRCLELINKLIST_FALSE;
    
23.                 return  0;
    
24. }
    
25. int main(void){
    
26. 
    
27.         CircleLinkList * clist = Init_CircleLinkList();
    
28. 
    
29.         MyNum num[M];
    
30.         for (int i = 0; i < 8; i++){
    
31. 
    
32.                 num[i].val = i + 1;
    
33.                 Insert_CircleLinkList(clist, i, (CircleLinkNode *)&num[i]);
    
34.         }
    
35.         Print_CircleLinkList(clist, MyPrint);
    
36.         printf("\n");
    
37.         //FreeSpace_CircleLinkList(clist);
    
38.         //辅助指针
    
39.         int index = 1;
    
40.         CircleLinkNode * pCurrent = clist->head.next;
    
41.         while (Size_CircleLinkList(clist) > 1){
    
42.                 if (index == N){
    
43.                 MyNum* temNum = (MyNum*)pCurrent;
    
44.                 printf("%d ", temNum->val);
    
45.                 //缓存待删除结点的下一个结点
    
46.                 CircleLinkNode * pNext = pCurrent->next;
    
47.                 //根据值去删除
    
48.                 RemoveByValue_CircleLinkList(clist, pCurrent, MyCompare);
    
49.                   pCurrent = pNext;
    
50.                   if (pCurrent == &(clist->head)){
    
51.                           pCurrent = pCurrent->next;
    
52.                   }
    
53.                   index = 1;
    
54.                 }
    
55.                 pCurrent = pCurrent->next;
    
56.                 if (pCurrent == &(clist->head)){
    
57.                         pCurrent = pCurrent->next;
    
58.                 }
    
59.                 index++;
    
60.         }
    
61.         if (Size_CircleLinkList(clist) == 1){
    
62.                 MyNum *tempNum = (MyNum*)Front_CircleLinkList(clist);
    
63.                 printf("%d ", tempNum->val);
    
64.         }
    
65.         else{
    
66.                 printf("出错了！");
    
67.         }
    
68.         printf("\n");
    
69.         FreeSpace_CircleLinkList(clist);
    
70.         getchar();
    
71.         getchar();
    
72.         return 0;
    
73. }

复制代码

运行的结果不对，，我自己调试了调试，但找不到错误在哪，请教各位大佬同学

最佳答案

月排行榜 / 总排行榜

JLDawson

2020-4-29 11:45:52

qiao141486 发表于 2020-4-29 10:43
是我展示出来图片的代码，我黏贴复制上去的，我自己运行时，也没有出这些错误。吧CircleLinkList换成Circ ...

在while循环中把pCurrent的数值先打印一下，发现你的删除函数是有问题的。节点并没有将数据删除。

跳转到最佳答案楼层

JLDawson

第一个问题，楼主上传的代码是编译不过的，main.cpp中的Print_CircleLinkList(clist,MyPrint);会报错。
错误信息：
error C2664: “void Print_CircleLinkList(CircleLinkList *,PRINTLINKLIST)”: 无法将参数 2 从“void (__cdecl *)(CircleLinkList *)”转换为“PRINTLINKLIST”
查看代码后发现函数指针使用有问题。我们发现MyPrint的参数为CircleLinkList * ，而函数指针的参数类型为CircleLinkNode *。
其次MyPrint函数中，为什么要将CircleLinkList *强制转换为MYNUM*，然后再获取value？不可以直接使用printf("%d ", data->size);？
请问您所展示的图片是运行您展示的代码所运行出来的吗？

1. typedef void(*PRINTLINKLIST)(CircleLinkNode *);
   
2. 
   
3. //打印
   
4. void Print_CircleLinkList(CircleLinkList * clist, PRINTLINKLIST print);
   
5. 
   
6. //打印
   
7. void Print_CircleLinkList(CircleLinkList * clist, PRINTLINKLIST print) {
   
8.         if (clist == NULL) {
   
9. 
   
10.                 return;
    
11.         }
    
12.         CircleLinkNode * pCurrent = clist->head.next;
    
13.         for (int i = 0; i < clist->size; i++) {
    
14.                 if (pCurrent == &(clist->head))
    
15.                 {
    
16.                         pCurrent = pCurrent->next;
    
17.                         printf("-------------------------- \n");
    
18.                 }
    
19.                 print(pCurrent);
    
20.                 pCurrent = pCurrent->next;
    
21.         }
    
22. 
    
23. }
    
24. 
    
25. void MyPrint(CircleLinkList * data) {
    
26.         MyNum* num = (MyNum*)data;
    
27.         printf("%d ", num->val);
    
28. }
    
29. 
    
30. typedef struct MYNUM {
    
31.         CircleLinkNode node;
    
32.         int val;
    
33. }MyNum;
    
34. 
    
35. //链表结构体
    
36. typedef struct CIRCLELINKLIST {
    
37.         CircleLinkNode head;
    
38.         int size;//判断循环是否停止的标志
    
39. }CircleLinkList;
    
40. 
    

复制代码

qiao141486

JLDawson 发表于 2020-4-29 09:46
第一个问题，楼主上传的代码是编译不过的，main.cpp中的Print_CircleLinkList(clist,MyPrint);会报错。
错 ...

是我展示出来图片的代码，我黏贴复制上去的，我自己运行时，也没有出这些错误。

1. void MyPrint(CircleLinkNode * data){
   
2.         MyNum* num = (MyNum*)data;
   
3.         printf("%d ", num->val);
   
4. }

复制代码

吧CircleLinkList换成CircleLinkNode，因为循环列表中，数据是用结点串起来的，打印数据时就要把结点型数据转换成自己定义成的数据

JLDawson

qiao141486 发表于 2020-4-29 10:43
是我展示出来图片的代码，我黏贴复制上去的，我自己运行时，也没有出这些错误。吧CircleLinkList换成Circ ...

在while循环中把pCurrent的数值先打印一下，发现你的删除函数是有问题的。节点并没有将数据删除。

qiao141486

JLDawson 发表于 2020-4-29 11:45
在while循环中把pCurrent的数值先打印一下，发现你的删除函数是有问题的。节点并没有将数据删除。

谢谢这位大佬同学，我自己调试时似乎也感觉到了，就是不太确定