求助关于循环链表约瑟夫环的问题
本帖最后由 白轼泽 于 2019-2-18 14:41 编辑刚学链表没多久，对于一些操作都不熟。自己做了一个约瑟夫环的代码，题目是这样的
题目描述
有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。
输入
初始人数n，有多组测试数据，对每一个测试数据，输出一个结果
输出
最后一人的初始编号
样例输入
3
4
5
10
样例输出
2
1
4
4
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}node;
typedef struct node *List;
struct node *Create(List head,int n)
{
List p1=NULL,p2=NULL;
int m;
for(m=1,p1=head;m<=n;m++)//尾插法，每个结点的data依次为1,2,...,n
{
p1=(List)malloc(sizeof(node));
p1->data=m;
p2->next=p1;
p2=p1;
}
p1->next=head->next;//for循环后，p1指向最后一个结点，通过此操作构成循环链表
free(head);//释放无用的头结点，使链表构成一个环
return p1->next;//返回第一个结点的位置
}
struct node *Delete(List l,int n)
{
List p,q;
p=l;//p从第一个结点开始
for(;n>1;n--)
{
q=p->next->next;//q为从p开始的第三个元素
p->next->next=q->next;//将从p开始的第二个结点与第四个结点衔接
p=q->next;//将p改为q后面的元素，即原来的从q开始的第四个元素
free(q);//从原来的p开始的删除第三个元素
}
return l;
}
int main()
{
int n;
List head,l;
while(scanf("%d",&n)!=EOF)
{
head=(List)malloc(sizeof(node));//创建带头结点的空链表
head->next=NULL;
l=Create(head,n);
//l=Delete(head,n);
printf("%d\n",l->data);
}
return 0;
}
但是执行程序之后，我输入一个数据，比如3，这个程序什么都没输出，而且还直接结束了
求助为什么是这样的？{:5_92:}
多谢各位了 本帖最后由 jackz007 于 2019-2-18 18:45 编辑
问题比较多，就不一一赘述，大概改了下，程序的结构基本维持原样，楼主不妨对照原代码比较一下看看。
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data ;
struct node * next ;
} node ;
typedef struct node * List ;
struct node * Create(int n)
{
List head , p1 = NULL , p2 = NULL ;
int m ;
p1 = (List)malloc(sizeof(node)) ; // 为首节点分配内存空间
p1 -> data = 1 ; // 为首节点 data 成员赋值
p1 -> next = p1 ; // 让首节点指针成员指向自己，形成自闭
head = p1 ; // 记录首节点
for(m = 2 ; m <= n ; m ++) {
p2 = (List)malloc(sizeof(node)) ; // p2 新建节点
p2 -> data = m ; // 为新节点 data 成员赋值
p2 -> next = head ; // 让新节点指针成员指向首节点，形成闭环
p1 -> next = p2 ; // 更新前一个节点的指针成员，使其指向新节点
p1 = p2 ; // 腾出新节点指针，准备插入新节点
}
return head ; //返回指向首结点的指针
}
struct node * Delete(List l , int n)
{
List p , q ;
int k ;
p = l ; //p从第一个结点开始
k = n ;
while(k > 2) {
q = p -> next -> next ; // q - 待删除节点
p -> next -> next = q -> next ; // 节点桥接，跨过被删除节点
p = q -> next ; // 下次从已删除掉节点的下一个节点开始计数
free(q) ; // 释放被删除节点所占用的内存空间
k -- ; // 节点计数减 1
}
return p -> next ;
}
main(void)
{
int n ;
List head , l ;
while(scanf("%d", & n) != EOF) {
l = Create(n) ;
l = Delete(l , n) ;
printf("%d\n" , l -> data) ;
}
}
本帖最后由 白轼泽 于 2019-2-19 18:48 编辑
jackz007 发表于 2019-2-18 16:05
问题比较多，就不一一赘述，大概改了下，程序的结构基本维持原样，楼主不妨对照原代码比较一下看看。
...
多谢指点了，不过我还想问一下，我是看着视频里的，把无用的头节点释放了，这一步出错了吗？还是说我的创建链表的函数出了问题？
另外我对你的删除部分的代码做了点优化List Delete(List l , int n)
{
List p , q;
p = l; //p从第一个结点开始
for(;n > 1;n --) //n是节点计数器，每次删除一个结点之后都减一
{
q = p -> next -> next; // q为从p开始的第三个元素，是待删除节点
p -> next -> next = q -> next;// 节点桥接，跨过被删除节点
p = q -> next; // 下次从已删除掉节点的下一个节点开始计数
free(q); // 释放被删除节点所占用的内存空间
}
return p;
}
页:
[1]