8000 add two demo, which is used to judge a linked list whether or not a l… · mikephp/basic_data_struct@c596fac · GitHub
[go: up one dir, main page]
Skip to content

Commit c596fac

Browse files
mikephpmikephp
committed
add two demo, which is used to judge a linked list whether or not a loop linked list
1 parent 239f8e7 commit c596fac

File tree

3 files changed

+208
-0
lines changed

3 files changed

+208
-0
lines changed

‎src/bison/Makefile

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
cc=gcc
2+
cflag=-g
3+
flex=flex
4+
yyac=bison
5+
target=cli
6+
.PHONY:all clean
7+
8+
all:$(target)
9+
10+
%.lex.c:%.l
11+
@echo $@ $^
12+
$(flex) $^
13+
%.tab.c:%.y
14+
@echo $@ $^
15+
$(yyac) -d -v $^
16+
17+
$(target):%.c %.h
18+
$(cc) $(cflag) $< -o $(target)
19+

‎src/data_struct/loop.c

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
4+
#define LEN 8
5+
typedef struct node* node_t;
6+
7+
struct node{
8+
char val;
9+
struct node *next;
10+
};
11+
12+
//method 1
13+
int has_loop(struct node *head);
14+
//method 2
15+
int has_loop2(node_t head);
16+
17+
int main()
18+
{
19+
//node_t* arr = (node_t*)malloc(sizeof(struct node)*LEN);
20+
node_t* arr = (node_t*)malloc(sizeof(struct node*)*LEN);
21+
arr[0] = (node_t)malloc(sizeof(struct node));
22+
int i;
23+
for(i = 1; i < LEN; i++)
24+
{
25+
arr[i] = (node_t)malloc(sizeof(struct node));
26+
arr[i - 1]->next = arr[i];
27+
}
28+
arr[LEN - 1]->next = NULL;
29+
30+
//you can add a loop here to test
31+
arr[6]->next = arr[0];
32+
if (has_loop(arr[0]))
33+
printf("method1: has loop.\n");
34+
else
35+
printf("method1: has no loop.\n");
36+
37+
if (has_loop2(arr[0]))
38+
printf("method2: has loop.\n");
39+
else
40+
printf("method2: has no loop.\n");
41+
42+
return 0;
43+
}
44+
45+
//if two pointer are equal, but they don't have the same steps, then has a loop
46+
int has_loop(node_t head)
47+
{
48+
node_t cur1 = head;
49+
int pos1 = 0;
50+
while(cur1){
51+
node_t cur2 = head;
52+
int pos2 = 0;
53+
pos1 ++;
54+
while(cur2){
55+
pos2 ++;
56+
if(cur2 == cur1){
57+
if(pos1 == pos2)
58+
break;
59+
else
60+
return 1;
61+
}
62+
cur2 = cur2->next;
63+
}
64+
cur1 = cur1->next;
65+
}
66+
return 0;
67+
}
68+
69+
//using step1 and step2 here
70+
//if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
71+
int has_loop2(node_t head)
72+
{
73+
node_t p = head;
74+
node_t q = head;
75+
while (p != NULL && q != NULL)
76+
{
77+
/*
78+
p = p->next;
79+
if (q->next != NULL)
80+
q = q->next->next;
81+
if (p == q)
82+
return 1;
83+
*/
84+
//correct it on 17/11/2012
85+
p = p->next;
86+
q = q->next;
87+
if (q != NULL)
88+
q = q->next;
89+
if (p != NULL && p == q)
90+
return 1;
91+
}
92+
return 0;
93+
}

‎src/data_struct/loop2.c

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
/*
2+
*
3+
* Author: mikephp
4+
* Created Time: 2015/12/1 22:28
5+
* Function: judge a linked list is or not a loop linked list
6+
*
7+
*/
8+
#include <stdio.h>
9+
#include <stdlib.h>
10+
11+
#define LEN 10
12+
13+
struct node{
14+
char val;
15+
struct node *next;
16+
};
17+
18+
typedef struct node* node_t;
19+
typedef struct node node_v;
20+
21+
//method 1
22+
int has_loop(struct node *head);
23+
//method 2
24+
int has_loop2(node_t head);
25+
26+
int main()
27+
{
28+
node_t arr[LEN];
29+
node_v nd[LEN];
30+
int i = 0;
31+
for (i = 0; i < LEN; i++){
32+
arr[i] = &nd[i];
33+
}
34+
35+
for(i = 1; i < LEN; i++)
36+
{
37+
arr[i - 1]->next = arr[i];
38+
}
39+
arr[LEN - 1]->next = NULL;
40+
41+
//you can add a loop here to test
42+
//arr[LEN - 2]->next = arr[LEN -3];
43+
if (has_loop(arr[0]))
44+
printf("method1: has loop.\n");
45+
else
46+
printf("method1: has no loop.\n");
47+
48+
if (has_loop2(arr[0]))
49+
printf("method2: has loop.\n");
50+
else
51+
printf("method2: has no loop.\n");
52+
53+
return 0;
54+
}
55+
56+
//if two pointer are equal, but they don't have the same steps, then has a loop
57+
int has_loop(node_t head)
58+
{
59+
node_t cur1 = head;
60+
int pos1 = 0;
61+
while(cur1){
62+
node_t cur2 = head;
63+
int pos2 = 0;
64+
pos1 ++;
65+
while(cur2){
66+
pos2 ++;
67+
if(cur2 == cur1){
68+
if(pos1 == pos2)
69+
break;
70+
else
71+
return 1;
72+
}
73+
cur2 = cur2->next;
74+
}
75+
cur1 = cur1->next;
76+
}
77+
return 0;
78+
}
79+
80+
//using step1 and step2 here
81+
//if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
82+
int has_loop2(node_t head)
83+
{
84+
node_t p = head;
85+
node_t q = head;
86+
while (p != NULL && q != NULL)
87+
{
88+
p = p->next;
89+
q = q->next;
90+
if (q != NULL)
91+
q = q->next;
92+
if (p != NULL && p == q)
93+
return 1;
94+
}
95+
return 0;
96+
}

0 commit comments

Comments
 (0)
0