栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > 资讯 > 高等教育 > 考研政策

zhongfu信息c语言笔试之约瑟夫算法

zhongfu信息c语言笔试之约瑟夫算法

接着上面说,说这是最后一个算法题目,这是最后一个题目,也是最复杂的题目,题目如下:

4、算法题目,转圈数M数,最后出局的是哪个数。(题目就是这样非常的简洁,其实就约瑟夫算法)

#include <stdio.h>#include <stdlib.h>typedef struct Link{int data;struct Link *next;} LinkList;LinkList * createLink(int n){printf("enter function createLinkn");LinkList *head, *rear, *new;head = rear = (LinkList *)malloc(sizeof(LinkList));int i = 0;for(i = 0; i< n; i++){new = (LinkList *)malloc(sizeof(LinkList));new->data = i+1;new->next = NULL;rear->next = new;rear = new;}rear->next = head->next;printf("exit function createLinkn");return rear;}LinkList* getJosephus(LinkList* rear, int m){printf("enter function getJosephusn");LinkList *newHead, *newRear, *newLinkList;LinkList *tempList;newHead = newRear = (LinkList *)malloc(sizeof(LinkList));//LinkList *oldHead = rear->next;int i = 0;while(rear != rear->next){//原链表走m-1节点for(i = 0; i < m-1; i++){rear = rear->next;}//原链表删除第m个节点tempList = rear->next;rear->next = tempList->next;tempList->next = NULL;//新链表加入删除的第m个节点newRear->next = tempList;newRear = tempList;}//新链表加入原链表剩下的最后一个节点newRear->next = rear;newRear = rear;newRear->next = newHead->next;printf("exit function getJosephusn");return newRear;}void printJosephus(LinkList* newRear){printf("enter function printJosephusn");//temp2先获取头节点LinkList *temp2 = newRear->next;do{printf("temp2->data=%d,", temp2->data);temp2 = temp2->next;}while(temp2 != newRear->next);//上面如果是头节点则结束循环printf("n");printf("exit function printJosephusn");}int main(){//1/创建5个节点的链表LinkList *oldLinkList = createLink(5);//打印当前链表的情况printJosephus(oldLinkList);//2/进行m循环,也就是约瑟夫循环LinkList *newLinkList = getJosephus(oldLinkList, 3);//打印约瑟夫循环的输出列表printJosephus(newLinkList);}

运行情况如下:

root@mkx:~/learn/Josephus# gcc josephus.c -o josephusroot@mkx:~/learn/Josephus# ./josephusenter function createLinkexit function createLinkenter function printJosephustemp2->data=1,temp2->data=2,temp2->data=3,temp2->data=4,temp2->data=5,exit function printJosephusenter function getJosephusexit function getJosephusenter function printJosephustemp2->data=3,temp2->data=1,temp2->data=5,temp2->data=2,temp2->data=4,exit function printJosephusroot@mkx:~/learn/Josephus#

5个数,用手画一下,就可以知道,结果是对的。

这道题目,其实就是著名的约瑟夫算法,循环链表实现,是非常经典的实现方法,这里用了循环链表,比如非循环列表多了一个尾节点,这是需要注意的地方:

下面用图就可以非常形象地表现出来:

其关键就是head与rear两个指针,其操作对这两个指针进行操作就可以了。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/news/1535000.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号