约瑟夫环的点滴

发布于:2021-09-21 03:50:51

??????????? 最*在用双向循环链表做传说中的约瑟夫环,奇葩的做着做着就环进去了,不过通过这个学*,知道了关于双向循环链表的点滴,还有就是约瑟夫环的算法思想。




?????????? 首先是算法的思想,约瑟夫环俗话说就是一群人为一个圈,选一个代表去参加代表大会。我是这样理解的,首先给一个初始密码,让每个人拿着随机给定的密码牌(密码可能有相同的);到底怎魔玩呢?先从第一个人开始吧,他有选择的权利,以他为中心,可选择逆序也可以选择顺序查到下一个人作为下一次开始的起点,并记录他的passwd,这个passwd作为下一次查找的对象和当前对象中间隔的人数,依次循环,知道剩下最后一个人,他就是获胜者。




????????? 其次,我在实现的过程中用的是双向的循环链表,所用的结构体为


typedef struct circle
{
int num; //记录这个人的编号
int passwd; //记录这个人所持卡片的编号
int direct; //记录方向,为奇数逆序循环,为偶数顺序循环
struct cilcle *pre, *next;
}Circle, *Cir;


? ? ? ? ? 最让我纠结的是,当找到要被删除的人时,怎样搭建才能使它顺利删除?


cur->pre->next = cur->next;
cur->next->pre = cur->pre;
改变cur->next->pre 及cur->pre->next 的指向,最后free(cur);就OK啦~~




但是在程序的执行过程中,出现了一个问题free(cur);如果cur 为空的时候,free 函数并不会释放空指针,而在编辑的过程中,很多人会像我一样没有考虑到当cur 指向head 时,这个头结点本身就不存在数据域,所以free了以后就会出现乱码的情况。




解决的方法就是在建立循环链表时,不要让尾指针r->next = head; 而是r->next = head->next;? head->next->pre = r; 这样就行了,避免出现乱码的情况。。。



相关推荐

最新更新

猜你喜欢