用循环链表实现约瑟夫环

2018-07-02T21:13:55

删除数问题

在计算机上先输入两个正整数N和K,其中N为将要输入的正整数的个数,K为步长。请编写一个程序,首先用循环链接表储存这N个正整数。然后,首先删除第一个正整数,接着删除循环链表从当前删除节点开始步长走K个的正整数,依次类推,直至表空为止。如下所示,N=10,K=3,输入的10个正整数为1,2,3,4,5,6,7,8,9,10。则被删除的次序为:1,4,7,10,5,9,6,3,8,2。

#include<stdio.h>

#include<stdlib.h>

typedef int ElemType;

//声明循环链表结构体

typedef struct LNode

{

    ElemType data;//数据域

    struct LNode *next;//结构体指针

}LNode;//结点类型



//创建结点

LNode *Create_node(int LNum)

{

    LNode *Lp;//创建结点指针

    Lp=(LNode *)malloc(sizeof(LNode));//分配动态储存空间

    Lp->data=LNum;//*Lp指向data,把data的值传给LNum

    Lp->next=NULL;//*Lp指向下一个元素结点为空,确定*Lp是头结点指针

    return Lp;//返回头结点指针

}



//创建循环链表
/**
 *
 * @param pHead 头指针
 * @param LSum  正整数的个数
 * @return pHead
 */

LNode *Create_LinkList(LNode *pHead, int LSum)

{

    int k;

    LNode *p, *temp;//创建两个指针

    for(k=1;k<=LSum;k++)//遍历整个链表

    {

        p=Create_node(k);

        //如果链表为空,创建链表第一个结点,其next指针指向自身

        if(pHead==NULL)

        {

            temp=p; //把p的值传给temp

            pHead=p; //把p的值传给pHead

            temp->next=pHead; //让*temp指向的下一个位置为pHead

        }

            //否则,执行插入节点操作

        else

        {

            p->next=temp->next;//将p的next指向头结点

            temp->next=p;//完成结点插入

            temp=p; //把p的值再传给temp,继续循环,一个一个插入

        }

    }

    //测试是否生成循环链表成功

    p=pHead;

    k=1;//初始化k的值

    while(p->next!=pHead)//用循环输出链表中的元素

    {

        printf("第%d个数为:%d\n",k,p->data);

        p=p->next;//指针移向下一个位置

        k++;

    }

    printf("第%d个数为:%d\n\n",k,p->data);//确保最后一个元素能显示出来

    return pHead;//返回头指针

}



//执行出列操作
/**
 *
 * @param pHead 头指针
 * @param LNum 整数个数
 * @param LDel  步长
 */

void Delete_LinkList(LNode *pHead,int LNum, int LDel)

{

    int i, count = 1;//count为计数器

    LNode *p, *temp;

    p=pHead;

    //LStart为开始位置,即第一个整数的前一个位置

    int LStart = LNum - LDel + 1;

    //找到开始的那个数字所在的位置的后一个位置

    for(i=1;i<=LStart;i++)

        p=p->next;

    //只剩1个结点时终止循环

    while(p->next!=p)

    {

        //找到要出列的数字的位置

        for(i=1;i<LDel;i++)

        {

            temp=p;

            p=p->next;

        }

        //执行出列操作

        temp->next=p->next;//让*temp指向*p后面的结点

        printf("第%d个被删除的数为:%d\n",count,p->data);

        free(p);//释放*p

        count++;

        //出列者的下一个数字作为新的第一个

        p = temp->next;

    }

    printf("第%d个被删除的数为:%d\n",count,p->data);

    free(p);

    //所有数字均出列,头结点释放后赋空值

    pHead=NULL;

}

/*主函数*/

int main()

{

    int n,k;

    LNode *pHead=NULL, *p;//执行初始化操作

    printf("请输入正整数的个数:\n");

    scanf("%d",&n);

    printf("请输入步长:\n");

    scanf("%d",&k);

    p = Create_LinkList(pHead,n);//调用创建链表函数

    Delete_LinkList(p,n,k);//调用删除链表函数

    return 0;

}

 

当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »
因本文不是用Markdown格式的编辑器书写的,转换的页面可能不符合MIP标准。