关于 用单链表循环结构解决约瑟夫循环

Mr.K

#include <stdio.h>
#include <malloc.h>
typedef int DataType;

typedef struct Node
{
        DataType data;
        struct Node *next;
}SLNode;

//初始化
void ListInitiate(SLNode **head)
{
        *head = (SLNode *)malloc(sizeof(SLNode));
        (*head)->next = *head;
}

//插入
int ListInsert(SLNode *head,int i,int x)
{
        SLNode *p,*q;
        int j;

        p = head;
        j = -1;
        while(p->next != head && j<i-1)
        {
                p = p->next;
                j++;
        }

        if(j != i-1)
        {
                printf("插入数据元素位置参数错");
                return 0;
        }

        q = (SLNode *)malloc(sizeof(SLNode));
        q->data = x;
       
        q->next = p->next;
        p->next = q;
        return 1;
}


//求当前元素数据个数
int ListLength(SLNode *head)
{
        SLNode *p = head;
        int size = 0;
        while(p->next != head)
        {
                p = p->next;
                size ++;
        }
        return size;//返回个数
}


//删除
int ListDelete(SLNode *head,int i,DataType *x)
{
        SLNode *p,*s;
        int j;
        p = head;
        j = -1;
        while(p->next != head && p->next->next != head && j<i-1)
        {
                p = p->next;
                j++;
        }

        if(j != i-1)
        {
                printf("删除元素位置参数错！");
                return 0;
        }

        s = p->next;
        *x = s->data;
        p->next = p->next->next;
        free(s);
        return 1;
}

//取数据元素
int ListGet(SLNode * head,int i,DataType *x)
{
        SLNode *p;
        int j;
        j = -1;
        p = head;
        while(p->next != head && j<i)
        {
                p = p->next;
                j++;
        }

        if(j != i)
        {
                printf("取数据元素位置参数错！");
                return 0;
        }

        *x = p->data;
        return 1;
}

//撤销单链表
void Destroy(SLNode **head)
{
        SLNode *p,*p1;
       
        p = *head;
        while(p != *head)
        {
                p1 = p;
                p = p->next;
                free(p1);
        }
        *head = NULL;
}
//从那个结点开始
SLNode * AtBegining(SLNode * head,int k)
{
        SLNode *p;
        int i;
        printf("（从1开始）开始报数序号k=  ");
        scanf("%d",&k);
        p = head;
       
        for(i = 0 ;i < k; i++)
        {
                p = p->next;
        }

        return(p);
}

//删除给定地址的元素
void DeletePoint(SLNode * head,SLNode * p,DataType *x)
{
        SLNode *q;
        q = p->next;
        *x = p->data;
        p->data = q->data;//这一步是关键
        p->next = p->next->next;
        free(q);

       
}
void main(void)
{
        SLNode *head,*p,*q;
        int i,j,k,n,x;
        ListInitiate(&head);//head本身就是个指针

        //插入8个从1开始的自然数
        for(i = 0 ;i < 8; i++)
        {
                ListInsert(head,i,i+1);
        }

        //初始化头结点
        head->data = NULL;
        //从那个结点开始
        p = AtBegining(head,k);
       
       
        //报出列的数字
        printf("报出列的数字n=  ");
        scanf("%d",&n);
        //p->next != head && p->next->next != head
        j=0;

        while(j<9)
        {
                if(p->data != NULL)//由于存在头结点，不存放数据元素
                {
                        for(i = 0;i < n-1;i ++)
                        {       
                                p = p->next;
                                if(p == head) p = p->next;//头结点的解决
                        }
                printf("%d  ",p->data);//当p->data = 8;
                DeletePoint(head,p,&x);//"p->data = 8"的p地址被删除，指向下一个单元的域值，但赋予的值是head->data;
                }
               
                else if(p->data == NULL)
                {       
                        DeletePoint(head,p,&x);
//                        q = p->next;
//                        p->data = q->data;
//                        p = p->next;//使P的地址霸占4原在的地址
                }
         
                j++;
        }
       
       
        Destroy(&head);
}

骑乌龟的帅蜗牛

这是学习的节奏啊！

gmh5225

楼主是同道中人吗

Mr.K

yyz219 发表于 2014-11-6 20:00
觉得很深奥

不会的，只要理顺了思路，在算法设计方面下多点功夫就容易多了