鱼C论坛

 找回密码
 立即注册

鱼C作业-判断链表是否有环

已有 614 次阅读2013-3-15 12:58 |个人分类:鱼C-作业

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

/****************************************************/
/*链表声明*/
/****************************************************/
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
 ElementType Element;
 Position Next;
};

/****************************************************/
/*创建有环链表*/
/****************************************************/
List Create_LoopLinkList(int n)
{
 Position Head;                       //头节点

 Head = (Position)malloc(sizeof(Node));
 if(Head == NULL)
 {
  printf("动态内存分配失败,程序结束!\n");
  exit(-1);
 }

 Position Tail = Head;
 Tail->Next = NULL;
 
    srand((unsigned)time(NULL));             //根据系统时钟产生随机种子
 for(int i = 0;i < n;i++)
 {
  Position New = (Position)malloc(sizeof(Node));
  if(New == NULL)
  {
   printf("动态内存分配失败,程序结束!\n");
   exit(-1);
  }

     New->Element = rand()%100;
  Tail->Next = New;
  Tail = New;
  Tail->Next = NULL;
 }
   
 if(n != 0)
 Tail->Next = Head->Next->Next->Next;

 return Head;
}

/****************************************************/
/*创建无环链表*/
/****************************************************/
List Create_LinkList(int n)
{
 Position Head = (Position)malloc(sizeof(Node));
 if(Head == NULL)
 {
  printf("动态内存分配失败,程序结束!!\n");
  exit(-1);
 }

 Position Tail = Head;
 Tail->Next = NULL;

   srand((unsigned)time(NULL));

   for(int i=1;i<=n;i++)
   {
       Position New = (Position)malloc(sizeof(Node));
    if(New == NULL)
    {
    printf("动态内存分配失败,程序结束!!\n");
    exit(-1);
    }
        New->Element = rand()%100;
      Tail->Next = New;
    New->Next = NULL;
    Tail = New;
   }
   return Head;
}

/****************************************************/
/*判断循环链表是否有环*/
/****************************************************/
void IsLoop(List L)
{
     Position q,p;

  p = q = L;
   
  while(p != NULL && q != NULL && q->Next != NULL)        //不是空表且有环
  {
   p = p->Next;
   q = q->Next->Next;
   printf("p:%d  q:%d\n",p->Element ,q->Element );
   if(p == q)                                                                  //Node结构体相等是指Element和Next相等,或者他们的指针相等
   {
    printf("链表有环!!\n");
    printf("p:%d  q:%d\n",p->Element ,q->Element );
    exit(0);
   }
  }
  printf("可能是空表或者没有环!!\n");
}

/****************************************************/
/*主函数*/
/****************************************************/
int main()
{
 Position Point;
    int n;
 int num;

    printf("请输入链表的长度n=");
 scanf("%d",&n);

 printf("请输入要创建的项目:0:创建有环链表     1:创建无环链表\n");
 scanf("%d",&num);

    switch(num)
 {
 case 0:
           Point = Create_LoopLinkList(n);           //有环链表
     IsLoop(Point);
      break;

 case 1:
          Point = Create_LinkList( n);                     //无环链表
   IsLoop(Point);
       break;

    default:
  printf("请输入0或者1!!!\n");
  break;
 }
  //Traverse_LinkList(Point);
   
 return 0;
}

 

 

刚刚学习的,程序有问题的提出来,不喜欢勿喷啊!!!


路过

鸡蛋

鲜花

握手

雷人

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 立即注册

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-23 23:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部