`

判断两个一个链表是否存在循环(C专家编程中的问题)

阅读更多
判断两个一个链表是否存在循环(C专家编程中的问题)
#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
/**//*目的:检测指定的链表中是否存在循环*/
/**//*算法概要:同时指定p1,p2指向头节点,p1步长为1向后移,p2步长为2向后移*/
/**//*如果p1或p2指向NULL,说明不存在循环*/
/**//*如果存在循环,则p2经过循环必然会追上p1*/
/**//*算法的效率不是很高,但是却很简洁*/
/**//*author:dirtysalt,date:05.7.17,time:6:10*/
typedef struct list
{
struct list *next;
}list;
list *head=NULL,*tail=NULL;
void new_list()
{
tail=(list*)malloc(sizeof(list));
tail->next=NULL;
head=tail;
}
void add_item()
{
list *item;
item=(list*)malloc(sizeof(list));
item->next=head;
head=item;
}
void free_list()
{
list *tmp;
while(head!=tail)
{
  tmp=head;
  head=head->next;
  free(tmp);
}
free(head);
}
void make_loop()
{
tail->next=head;
}
int check_list_loop()
/**//*return value 1:loop*/
/**//*0:!loop*/
{
list *p1=head,*p2=head;
while(((p1=p1->next)!=NULL)&&((p2=p2->next)!=NULL)&&((p2=p2->next)!=NULL))
  {
   if(p1==p2)
    return 1;
  }
  return 0;
}
int main(int argc, char *argv[])
{
int i;
new_list();
for(i=0;i<10;i++)
  add_item();
if(check_list_loop()==1)
  printf("List Loop\n ");
else
  printf("List Non-Loop\n ");
make_loop();
if(check_list_loop()==1)
  printf("List Loop \n");
else
  printf("List Non-Loop\n ");
free_list();
return 0;
}
分享到:
评论

相关推荐

    Linux操作系统中通用双向循环链表的实现分析.pdf

    list-head是一个结构类型,其中包含两个指针域:next指向本结点在双向循环链表中的后继结点,prey指向前驱结点。在具体使用时,通常使用带头结点(头结点又称为占位结点,其直接后继为第一个有效结点,本文称之为...

    逆置数组实现和链表实现(C语言实现) 数组和链表.pdf

    首先,需要定义一个链表结点结构体`ListNode`,然后定义一个创建链表函数`Create_Linklist`,该函数将创建一个链表并且输入链表中的数据。接着,定义一个链表逆置函数`Reverse_Linklist`,该函数将链表中的结点按照...

    C 语言编程常见问题解答.chm

    6.10 怎样判判断两个字符串是否相同? 第7章 指针和内存分配 7.1 什么是间接引用(indirection)? 7.2 最多可以使用几层指针? 7.3 什么是空指针? 7.4 什么时候使用空指针? 7.5 什么是void指针? 7.6...

    数据结构和算法必知必会的50个代码实现.zip

    实现两个有序的链表合并为一个有序链表 实现求链表的中间结点 栈 用数组实现一个顺序栈 用链表实现一个链式栈 编程模拟实现一个浏览器的前进、后退功能 队列 用数组实现一个顺序队列 用链表实现一个链式队列 ...

    链表和数组的区别各有什么优缺点 数组和链表.pdf

    循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。 链表和数组都是重要的数据结构,它们在编程中扮演着重要的角色。链表可以动态生成节点并添加到已有的链表后面,链表灵活,可以在中间任意位置添加...

    动态数组链表数据结构.docx

    双链表中,每个元素有两个指针,一个指向下一个元素,另一个指向上一个元素;循环链表中,最后一个元素的指针指向第一个元素,形成一个环状结构。 通用链表 通用链表是一种可以存储任何类型数据的链表,它可以存储...

    数据结构--数组、单链表和双链表介绍以及双向链表 数组和链表.pdf

    双向链表是一种链表的变种,和单链表一样,也是由节点组成,但是每个数据结点中都有两个指针,分别指向直接后继和直接前驱。双向链表的特点是: * 节点的链接方向是双向的 * 相对于单链表来说,双向链表可以很方便...

    线性链表的实现及操作.doc

    单链表的每个节点只有一个后继指针,而循环链表的每个节点都有两个指针,一个指向下一个节点,另一个指向上一个节点。 在本文档中,我们将使用单链表来实现线性链表。每个节点都包含一个整数数据域和一个指针域,...

    50个必会的数据结构及算法实现源码

    问题:实现两个有序的链表合并为一个有序链表 问题:实现求链表的中间结点 栈 问题:用数组实现一个顺序栈 问题:用链表实现一个链式栈 队列 问题:用数组实现一个顺序队列 问题:用链表实现一个链式队列 ...

    华为C语言面试题.doc

    该算法的思想是使用两个指针,一个快指针和一个慢指针,快指针每次移动两步,慢指针每次移动一步,如果链表中有环,那么快指针一定会追上慢指针。 在给定的代码中,`bool CircleInList(Link* pHead)` 函数使用了该...

    数据结构实习报告一(链表求交集).doc

    1. 设计单链表类、链表的结点类、链表的迭代器类,以及单链表的创建、插入、删除、查找、判断是否空等函数。 2. 实现比较单链表所存元素是否相等的函数。 3. 实现求交集并存储交集单链表的函数。 三、设计 下面是...

    华为C语言面试题_嵌入式-常用知识&面试题库_大厂面试真题.doc

    在链表中,判断是否存在环是非常重要的。该问题的解决方法是使用双指针技术。我们可以定义两个指针,pTemp1和pTemp,初始时都指向链表的头节点。然后,我们可以让pTemp1每次移动一步,而pTemp每次移动两步。如果链表...

    C语言编程要点

    6.10. 怎样判断两个字符串是否相同? 105 第7章 指针和内存分配 106 7.1. 什么是间接引用(indirection)? 107 7.2. 最多可以使用几层指针? 108 7.3. 什么是空指针? 110 7.4. 什么时候使用空指针? 110 7.5. 什么是void...

    数据结构和算法必知必会的50个代码实现

    ## 链表* 实现单链表、循环链表、双向链表,支持增删操作* 实现单链表反转* 实现两个有序的链表合并为一个有序链表* 实现求链表的中间结点 ## 栈* 用数组实现一个顺序栈* 用链表实现一个链式栈* 编程模拟实现一个...

    c语言经典案例

    实例205 合并两个链表 296 实例206 单链表节点逆置 298 实例207 应用栈实现进制转换 300 实例208 用栈实现行编辑程序 303 实例209 用栈设置密码 306 实例210 括号匹配检测 310 实例211 用栈及递归计算多项式 313 ...

    C++经典面试题1.pdf

    在这个例子中,我们可以看到如何使用两个指针来判断链表是否有环。我们可以使用一个慢指针和一个快指针,慢指针每次移动一步,快指针每次移动两步。如果链表有环,那么快指针一定会追上慢指针;否则,快指针将到达...

    problems:在 JavaScript 中解决的编程问题

    问题 在 JavaScript 中解决的编程问题数组字符串链表返回循环链表循环开始处的节点检查链表是否是普通的检查链表是循环还是有循环查找单向链表的第 k 个最后一个元素修改一个链表,使得所有小于 x 的节点出现在所有...

    C语言程序设计标准教程

    为了解决这个问题,C语言中给出了另一种构造数据类型——“结构”。 它相当于其它高级语言中的记录。  “结构”是一种构造类型,它是由若干“成员”组成的。 每一个成员可以是一个基本数据类型或者又是一个构造...

    全国计算机等级考试二级C语言上机考试题库及答案.pdf

    在这份考试题库中,我们可以看到各种类型的C语言编程题目,其中包括函数实现、数组操作、链表操作、文件输入输出等等。下面我们将对每一道题目的知识点进行解析: 第1套: 1. 题目中要求使用结构体来存储学生信息...

    算法导论(part1)

    ·动态规划的两个应用(第15.1节和第15.5节)。 ·利用随机化和线性规划技术的近似算法(第35.4节)。 ·为了使更多的算法可以更早地在书中出现,第1版中有关数学背景知识的三章内容从第一部分移到了附录中,即现在...

Global site tag (gtag.js) - Google Analytics