有环链表的判断
本帖最后由 spy 于 2015-3-27 17:30 编辑#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node * next;
};
struct Node *CreateList();
void ListTraverse(struct Node *);
int IsEmpty(struct Node *);
int ListLength(struct Node *);
void GenerateLoopListTail(struct Node *, int);
//int HaveLoop(struct Node *, int);
int HaveLoop2(struct Node *);
void DestroyList(struct Node *, int);
void main()
{
struct Node *head = NULL;
int n, i, len=0, j=0;
char ch;
printf("\n");
printf("------------------------\n\n");
printf(" 1.初始化链表\n 2.创建有环链表(尾插法)\n 3.判断链表是否有环\n 0.退出\n\n 请选择您的操作: ");
scanf("%d", &n);
putchar('\n');
while(n)
{
switch(n)
{
case 1:
{
head = CreateList();
len = ListLength(head);
if(IsEmpty(head))
{
printf("链表为空,请初始化链表!\n\n");
break;
}
else
{
ListTraverse(head);
break;
}
}
case 2:
{
if(IsEmpty(head))
{
printf("链表为空,请初始化链表!\n\n");
break;
}
else
{
if(j)//j=0,则创建有环链表, 否则重新输入
{
while(1)
{
printf("当前已经是有环链表, 是重新建立链表还是放弃当前操作?(Y/N)\n");
fflush(stdin);
ch = getchar();
putchar('\n');
if('Y'==toupper(ch))
{
j = 0;
DestroyList(&head, len);
head = CreateList();
if(IsEmpty(head))
{
printf("链表为空,请初始化链表!\n\n");
goto SELECT;
}
else
{
ListTraverse(head);
goto SELECT;
}
}
else
if('N'==toupper(ch))
{
goto SELECT;
}
else
{
printf("error!\n");
}
}
}
printf("输入要形成环的结点位置\n");
scanf("%d", &i);
len = ListLength(head);
while(i<1 || i>len-1)
{
printf("无法形成环, 是重新输入还是放弃当前操作?(Y/N)\n");
fflush(stdin); //之前输入的回车符还存在缓冲区，需要清除后缓冲区才能正确接受当前的输入
ch = getchar();
if('N'==toupper(ch))
{
putchar('\n');
goto SELECT;
}
else
if('Y'==toupper(ch))
{
printf("输入要形成环的结点位置\n");
scanf("%d", &i);
}
else
{
printf("error!\n");
}
}
GenerateLoopListTail(head, i);
j++;
printf("有环链表已形成!\n\n");
}
break;
}
case 3:
{
if(IsEmpty(head))
{
printf("链表为空,请初始化链表!\n\n");
break;
}
else
{
//if(HaveLoop(head, len))
if(HaveLoop2(head))
{
printf("有环, 环的位置在第%d个结点\n\n", i);
}
else
{
printf("无环\n\n");
}
}
break;
}
default:
{
printf("您的输入有误, 请重新输入选择菜单!\n\n");
}
}
SELECT: printf("请选择您的操作: ");
scanf("%d", &n);
if(1==n && len!=0)
{
DestroyList(&head, len);
}
putchar('\n');
}
}
struct Node *CreateList()
{
int n=1, value;
struct Node * head=NULL;
struct Node * p, *q;
printf("输入结点的值, 输入0完成初始化\n");
scanf("%d", &value);
while(!value)
{
printf("至少需要输入一个元素, 重新输入还是放弃当前操作? (Y/N)\n");
fflush(stdin);
if('N'==toupper(getchar()))
{
putchar('\n');
return head;
}
else
{
printf("输入结点的值, 输入0完成初始化\n");
scanf("%d", &value);
}
}
head = (struct Node *)malloc(sizeof(struct Node));
p = head;
while(value)
{
q = (struct Node *)malloc(sizeof(struct Node));
q->data = value;
p->next = q;
p= q;
scanf("%d", &value);
}
q->next = NULL;
return head;
}
void ListTraverse(struct Node *head)
{
struct Node *p = head;
p = p->next;
printf("**********链表中的元素**********\n");
while(p)
{
printf("%5d", p->data);
p = p->next;
}
printf("\n\n");
}
int IsEmpty(struct Node *head)
{
if(NULL == head)
return 1;
else
return 0;
}
void GenerateLoopListTail(struct Node *head, int i)
{
struct Node *p = head, *q = NULL;
int j = 0;
while(p->next!=NULL)
{
while(++j<i)
{
p = p->next;
}
if(j==i)
{
q = p->next;
}
p = p->next;
}
p->next = q;
}
int ListLength(struct Node *head)
{
struct Node *p = head;
int i=0;
if(IsEmpty(head))
{
return 0;
}
while(p->next)
{
p = p->next;
i++;
}
return i;
}
/*int HaveLoop(struct Node *head, int len)
{
struct Node *p=head, *q;
int cur1=0, cur2;
while(cur1<=len+1)
{
cur2 = 0;
q = head;
while(cur2<cur1 && p!=q)
{
q = q->next;
cur2++;
}
if(p == q)
{
if(cur2!=cur1)
{
return 1;
}
else
{
if(cur2==len+1)
{
return 0;
}
}
}
p = p->next;
cur1++;
}
}
*/
//使用快慢指针, 效率较高
int HaveLoop2(struct Node *head)
{
struct Node *p, *q;
p = q = head;
do
{
p = p->next;
q = q->next->next;
}while( p!=q && !(q->next==NULL || q->next->next==NULL) );
if(p==q)
{
return 1;
}
else
{
return 0;
}
}
void DestroyList(struct Node **head, int len)
{
struct Node *p, *q;
int i=0;
p = q = (*head)->next;
while(++i<len)
{
q = p->next;
free(p);
p = q;
}
free(p);
free(*head);
} 谢谢分享！！ 看看。。
页:
[1]