使用循环链表实现约瑟夫问题——关于free（）的思考

122 阅读 0 评论 81 点赞

我是靠谱客的博主心灵美宝贝，最近开发中收集的这篇文章主要介绍使用循环链表实现约瑟夫问题——关于free（）的思考，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题介绍：

M个人围成一圈，从第一个开始报数，第N个将被杀掉，最后剩下一个，其余人都将被杀掉。例如M=6，N=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。

这里使用循环链表数据结构实现，代码如下：

 1 #include<stdlib.h>

#include<stdio.h>
 2 #define new(type) (type*)malloc(sizeof(type))
 3 typedef struct _LinkNode{
 4
int number;
 5
struct _LinkNode *next;
 6 }LinkNode;
 7 Josephus(LinkNode* head,int m,int n){
 8
int i,j;
 9
LinkNode* temp = head;
10
LinkNode* pre = head;
11
for(i = 0; i < m-1;i ++){
12
for(j = 0; j < n-1; j++){
13
pre = temp;
14
temp = temp->next;
15 
}
16
printf("Out:%dn",temp->number);
17
pre->next = temp->next;
18 
free(temp);
19
temp = pre->next;
20 
}
21 }
22 int main(){
23
int m,n,i;
24
printf("Input the number and the gapn");
25
while(scanf("%d,%d",&m,&n) != 2){
26
printf("Wrong input!n");
27
printf("Format: m,nn");
28
while(getchar() != 'n');
29 
}
30
LinkNode *head = new(LinkNode);
31
head->number = 1;
32
head->next = NULL;
33
LinkNode *temp = head;
34
for(i = 2; i <= m; i++){
35
LinkNode *ptr = new(LinkNode);
36
ptr->number = i;
37
if(i != m)
38
ptr->next = NULL;
39
else ptr->next = head;
40
temp->next = ptr;
41
temp = temp->next;
42 
}
43 
Josephus(head,m,n);
44 }

关于scanf（）的问题，之前谈到过，这里不多说了，注意的就是输入不对的时候，需要先清除缓存。

另外需要谈到的是关于free（）的问题。

在网上查阅资料，看到有说连续两次free（）会出现错误，我去尝试了一下，没有报错。

测试案例如下：

1 #include<stdlib.h>

#include<stdio.h>
2 int main(){
3
char *p = malloc(sizeof(char));
4
*p = 'a';
5 
free(p);
6 
free(p);
7
printf("Twice free() is Rightn");
8
return 0;
9 }

测试结果如下：

根据自己的理解，free（）操作只是释放了指针所指的相应的内存空间，指针并没有任何的影响，仍然可以继续操作。

测试案例如下：

 1 #include<stdlib.h>

#include<stdio.h>
 2 int main(){
 3
char *p = malloc(sizeof(char));
 4
*p = 'a';
 5
printf("befor free(), *p=%cn",*p);
 6 
free(p);
 7
printf("after free(), *p=%cn",*p);
 8
*p = 'a';
 9
printf("assign again, *p=%cn",*p);
10
return 0;
11 }