数据结构——循环链表-白红宇的个人博客

数据结构——循环链表

发布日期：2021-05-07 23:08:09 浏览次数：20 分类：精选文章

本文共 1647 字，大约阅读时间需要 5 分钟。

对于循环链表，我是通过一道例题来学习的：

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（以编号1，2，3，…，n分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。

当然，我们可以用数学知识来求解，通过找规律什么的应该是可以解的，但是我觉得咱写代码的应该对自己好点，比较头发不好保养，还是让计算机来解决这个问题吧~

我们可以很明确的知道这里我们需要用到循环来解决问题。那么循环链表就可以在这里出场了：循环链表其实很好理解，就是将之前的链表头尾相连。其他的地方和循环链表几乎一模一样~

接下来就是将这个题目的代码整理出来给大家了：

#include
   
    #include
    
     typedef struct node{   	int number;	struct node *next;}person;/*初始化循环列表*/person *initLink(int n){   	person *head = (person *)malloc(sizeof(person));	head->number = 1;	head->next = NULL;	person *cyclic = head;	/*head作为头指针，不能移动，不然咱也就找不到这个链表了，	所以这个时候我们申请一个新的cyclic来往下遍历创建新的结点*/ 	int i;	for(i = 2; i <= n; i++){   		/*用body创立新的结点*/ 		person *body = (person *)malloc(sizeof(person));  		body->number = i; 		body->next = NULL;		cyclic->next = body;//将前后的结点连接起来 		cyclic = cyclic->next;	}	cyclic->next = head;	return head;} void findAddKillK(person *head, int k, int m){   	person *tail = head;	/*找到链表的结尾*/	while(tail->next != head){   		tail = tail->next;	}	/*用p来找到我们的起点*/	person *p = head;	while( p->number != k){   		tail = p;		p = p->next;	} 		/*找到我们需要删除的结点*/ 	while(p->next != p){   		int i;		for( i = 1; i < m; i++){   			tail = p;			p = p->next;		} //此时的p指向我们需要删除的结点 		tail->next = p->next; //将p的前一个结点连向它的后一个结点 		printf("出列表的人为%d", p->number);		free(p); //释放空间 		p = tail->next;	}	printf("出列表的人为%d", p->number);	free(p); //最后将自己给释放 }int main(){   	int n,m,k;	printf("圆桌上共有：" );	scanf("%d", &n); 	person * head = initLink(n);	printf("从第k人开始报数：");	scanf("%d", &k); 	printf("数到m个人出列：");	scanf("%d", &m); 	findAddKillK(head, k, m);}

我是不会说我犯错居然把取地址符曾经漏了，找不到错差点崩溃的~

上一篇：顺序结构——顺序栈

下一篇：数据结构——静态链表

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章