数据结构学习笔记-10

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0


typedef int Status;
typedef int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node, *LinkList;


Status InitList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));

    if(!(*L))
    {
        return ERROR;
    }

    (*L)->next = NULL;

    return OK;
}

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    int i;

    srand(time(0));/*初始化随机数种子*/

    *L = (LinkList)malloc(sizeof(Node));

    r = *L;/*r 指向尾部结点*/

    for(i=0; i<n; i++)
    {
        p = (Node *)malloc(sizeof(Node));
        p->data = rand()%100 + 1;
        r->next = p;
        r = p;
    }

    r->next = (*L)->next->next->next;
}

//比较步数的方法
int HasLoop1(LinkList L)
{
    LinkList cur1 = L;
    int pos1 = 0;

    while(cur1)
    {
        LinkList cur2 = L;
        int pos2 = 0;
        while(cur2)
        {
            if(cur2 == cur1)
            {
                if(pos1 == pos2)
                {
                    break;
                }
                else
                {
                    printf("Loop is at     position %d n", pos2);
                    return 1;
                }
            }

            cur2 = cur2->next;
            pos2++;
        }

        cur1 = cur1->next;
        pos1++;
    }
    return 0;
}

//快慢指针的方法
int HasLoop2(LinkList L)
{
    int step1 = 1;
    int step2 = 2;

    LinkList p = L;
    LinkList q = L;

    while(p!=NULL && q!=NULL && q->next!=NULL)
    {
        p = p->next;
        if(q->next != NULL)
            q = q->next->next;

        printf("p:%d, q:%d n", p->data, q->data);

        if(p == q)
            return 1;
    }
    return 0;
}

int main()
{
    LinkList L;
    int i = InitList(&L);

    CreateListTail(&L, 6);

    HasLoop1(L);

    HasLoop2(L);

    return 0;

}