- 浏览: 153430 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
lyaqys:
lz实现的OptimisticExclusiveLock有点问 ...
java park/unpark 【java并发】基于JUC CAS原理,自己实现简单独占锁
判断两个一个链表是否存在循环(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;
}
#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;
}
发表评论
-
c语言链表实现学生管理
2013-10-28 14:13 901#include<stdio.h> #includ ... -
简单的linux -c http-client
2013-10-23 15:35 4726#include<stdio.h> #includ ... -
毗连“"aa"”和“"bb"”不能给出一个有效的预处理标识符,gcc编译错误表
2013-10-01 18:54 2995gcc bug : ##’ cannot appear at ... -
负数转化为整数
2013-10-01 12:02 1354负数转化为整数 int a = -1321313; 12 ... -
STDIN_FILENO的作用及与stdin 的区别
2013-09-08 14:48 906if(NULL == fgets(msg,100,stdi ... -
linux进程cpu资源分配命令nice,renice,taskset
2013-09-04 14:03 1163nice,renice 指定进程运行的优先级 taskset ... -
c++ 动态内存分配
2013-08-28 22:35 844先看一段代码: [cpp] view plaincopy ... -
文件结束符EOF,system("stty raw")
2013-08-14 10:47 1555>> 关于文件结束符EOF EOF 是 End O ... -
c 专家编程
2013-08-13 17:06 688总结: -2> int * a = NUL ... -
Linux中线程与CPU核的绑定
2013-08-09 15:15 2128最近在对项目进行性能 ... -
建议编译的时候加警告 atof
2013-08-07 20:46 708#include <stdlib.h> ... -
feodra 17 安装 chrome
2013-08-04 01:35 7671: 下载:http://www.google.cn/chro ... -
Sudo提权出现:xx用户不在 sudoers 文件中
2013-08-03 20:22 911Sudo提权出现:xx用户不在 sudoers 文件中 症状 ... -
c语言api
2013-07-31 21:06 676原型:extern int isalnum(int c); 用 ... -
c 语言无符号类型使用注意,类型升级
2013-07-30 14:37 624#define SS sizeof(int) 5 int ... -
select,epoll,poll比较
2013-07-28 17:13 683select,poll,epoll简介 se ... -
gcc编译程序时,可能会用到“-I”(大写i),“-L”(大写l),“-l”(小写l)等参数
2013-07-22 22:45 901我们用gcc编译程序时,可能会用到“-I”(大写i),“-L” ... -
Linux下如何将进程绑定在特定的CPU上运行
2013-07-22 10:52 988Linux下如何将进程绑定在特定的CPU上运行? 以root用 ... -
linux运维常用命令
2013-07-13 20:40 882推荐一个实用命令:awk '{x+=$2} END {prin ... -
linux 进程通信方式
2013-07-07 20:46 619# 管道( pipe ):管道是一种半双工的通信方式,数据只能 ...
相关推荐
在C语言中,一个链表节点通常包含两个部分:数据和指向下一个节点的指针。对于循环链表,我们需要让最后一个节点的指针指向第一个节点,所以我们还需要一个指针用来记录链表的头节点。 ```c typedef struct Node { ...
这通常涉及到找到两个链表的适当连接点。 9. **链表的长度**: 计算循环链表的长度不能简单地用计数器加一,因为可能会无限循环。一种解决方案是使用快慢指针,慢指针每次移动一个节点,快指针每次移动两个节点,...
在IT领域,特别是系统编程和数据结构中,链表是一种非常基础且重要的数据结构。本文将深入探讨C语言实现的双向链表和双向循环链表,以及如何将这些概念应用于Linux内核。双向链表与单向链表相比,具有更灵活的操作...
解决这个问题的一种常见方法是先分别遍历两个链表,将其中一个链表(假设为较短的链表)中的所有节点存储在一个哈希表(例如Python中的字典)中。这样做的目的是为了快速检查一个节点是否存在于另一个链表中,因为...
本题目要求实现的功能是:输入两个递增的链表,然后通过程序对这两个链表进行排序(虽然在实际应用中,递增的链表已经有序,这里排序步骤是为了确保链表有序),接着按照递增顺序合并这两个链表,最终输出合并后的...
循环链表是一种特殊的链表结构,其特点在于链表的最后一个节点的指针域不再指向空,而是指向前一个节点,这样整个链表形成一个闭合的环形结构。在循环链表中,由于没有明显的尾端,因此在进行算法操作时需要特别注意...
在编程领域,有序链表序列的合并是一个常见的问题,尤其在数据结构和算法的学习中占有重要地位。这个题目“PTA 两个有序链表序列的合并”主要涉及到链表的操作和合并策略,这对于理解和掌握链表操作有极大的帮助。...
C语言中,我们可以使用结构体来定义链表节点,包含两个部分:存储人的编号的数据域和指向下一个节点的指针。 C语言循环链表的实现涉及以下几个关键点: 1. 结构体定义:创建一个结构体,如`struct Node`,包含一个...
它通过分别遍历两个链表h1和h2,寻找h1中的节点是否出现在h2中。这种方法的时间复杂度是O(length(h1) * length(h2)),因为每次都需要遍历整个h2链表来检查是否存在匹配节点。但由于每次遍历都要遍历整个链表,所以...
针对题目要求,我们可以用Python、Java和C语言实现快慢指针算法来检测链表中是否存在环。 ##### 1. Python 实现 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next =...
在C语言中,这通常通过创建两个指针,一个指向当前子链表的尾部,另一个初始为头部,然后依次交换它们指向的节点,直到两个指针相遇。 2. 初始化一个临时指针,用于保存每次翻转后子链表的前一个节点。初始时,这个...
链表是一种基础且重要的数据结构,它在计算机科学和编程,尤其是C语言中扮演着核心角色。相较于数组,链表提供了更加灵活的数据存储方式。在本文中,我们将深入探讨链表的基本概念、类型、操作以及如何在C语言中实现...
单循环链表是一种常见的数据结构,它在计算机科学中被广泛用于存储和处理有序或无序的数据序列。链表与数组不同,不依赖于物理位置的连续性,而是通过节点间的引用连接彼此。本篇文章将深入探讨单循环链表的概念、...
循环链表是一种特殊的链式数据结构,其最后一个元素的指针指向了链表的第一个元素,形成一个闭合的环状结构。与线性链表不同,循环链表没有明显的起点和终点,使得在某些场景下遍历和操作更加方便。在C++编程中,不...
在C语言中,我们首先需要定义链表节点的结构体,通常包含两个部分:数据域(用于存储元素)和指针域(指向下一个节点)。对于循环链表,最后一个节点的指针会指向链表的第一个节点,形成一个闭合的环。 以下是一个...
在双循环链表中插入节点相对复杂,因为需要更新前后两个方向的连接。例如,在某个位置插入新节点时,需要改变新节点、前一个节点和后一个节点的指针。插入操作通常分为在头部插入、在尾部插入和在中间插入。在C++中...
### C语言链表编程实例知识点详解 #### 1. 链表基础 链表是由一系列节点组成的集合,每个节点由数据部分和指向下一个节点的指针构成。链表的节点结构体定义如下: ```c typedef struct LNode { int data; // ...
3. **检测是否相遇**:通过检查两个指针是否相遇来判断链表中是否存在环。如果两个指针在某一点相遇,则表示链表中有环;如果快指针到达了链表尾部,则表示链表为无环链表。 ### 实现代码分析 在给定的部分内容中...
与单向链表不同,双向循环链表的每个节点都有两个指针,一个指向其前一个节点,另一个指向其后一个节点。这种结构在实现队列、栈和其他高级数据结构时非常有用。 双向循环链表的主要优点在于它的灵活性。由于我们...