avatar
文章
22
标签
8
分类
1
首页
时间轴
标签
分类
关于
清单
Aemonair
首页
时间轴
标签
分类
关于
清单
数据结构C语言实现2.带控制信息的链表
|Study
阅读量:

引言

在上一篇博客数据结构1.单链表中，我们对链表相对数组的优缺点进行了比较。
而且，我们发现，链表是一种物理存储单元上非连续、非顺序的存储结构，所以，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
若是想要对链表中的其中一个元素进行操作，通常都需要p_node = p_node->next;的循环进行。

计算机科学领域的任何问题，都可以通过增加一个间接中间层来解决。
Any problems in computer science can be soved by another layer of indirection.

所以，我们在定义这个链表的时候，可以给链表加上一层控制信息。如下：

** 本文的所有源程序可以在single_control_list上得到。**

一、链表数据类型的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*链表数据类型定义*/

struct List_node;    //声明一个类型

//链表控制信息
typedef struct List
{
    struct List_node *head;    //指向链表头部
    struct List_node *tail;    //指向链表尾部
    int              count;    //链表节点数量
}List;

//链表节点信息
typedef struct List_node
{
    int               data;    //数据域
    struct List_node *next;    //指针域
}List_node;

这样我们可以看到，已经可以直接获取到链表节点个数以及指向尾部节点的指针。我们可以用来做什么呢？

二、链表的接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/********链表的接口********/

List      *init_list(void)                                 ;    //1.  链表的初始化
void      destroy_list(List **list)                        ;    //2.  链表的销毁
Boolean   push_front(List *list, int value)                ;    //3.1 头部插入
Boolean   push_back(List  *list, int value)                ;    //3.2 尾部插入
Boolean   pop_front(List *list)                            ;    //4.1 头部删除
Boolean   pop_back(List *list)                             ;    //4.2 尾部删除
List_node *find_node(List *list, int value)                ;    //5.1 链表的查找
List_node *find_revise_node(List *list, int num)           ;    //5.2 找到链表的倒数第num个节点
List_node *find_mid_node(List *list)                       ;    //5.3 找到链表的中间节点
void      modify_node(List *list, int value)               ;    //6.1 链表节点的修改
Boolean   insert_node(List *list, int index, int value)    ;    //6.2 链表节点的插入(下标)
void      delete_one_node(List *list, List_node *node)     ;    //6.3 在O（1）的时间复杂度删除节点
void      sort_list_ascend(List *list)                     ;    //7.1 升序
void      sort_list_descent(List *list)                    ;    //7.2 降序排列
void      show_list(List *list)                            ;    //8.1 显示链表信息
void      reverse_show_list(List *list)                    ;    //8.2 逆序输出链表信息
int       get_list_count(List *list)                       ;    //9.  得到链表节点数量
List      *merge_two_lists(List *list1, List *list2)       ;    //10.  合并两个有序链表
List      *merge_two_lists_recure(List *list1, List *list2);    //11.  合并两个有序链表（递归）
List      *reverse_list(List *list)                        ;    //12.  逆置一个链表
List      *list_dump(List *list)                           ;    //13.  链表的拷贝
Boolean   is_list_intersect(List *list1, List *list2)      ;    //14.  判断链表是否有交点
List_node *get_first_common_node(List *list1, List *list2) ;    //15.  得到第一个交点
Boolean   has_circle(List *list)                           ;    //16.  判断一个链表是否有环
List_node *find_circle_first_node(List *list)              ;    //17.  找到带环链表的环入口节点

我们将这些都放入ctl_list.h文件当中，包括链表的定义，链表的接口，一些用到的宏定义。

为了能够方便的进行程序的设计，我们仍旧采用包裹函数的方式对某些操作进行简化：

1
2
3
4
5
6
/*接口包裹函数定义*/

static void *Malloc(size_t size);
static List_node *Create_node(void); 
static void Swap(void *a, void *b, int length);
static void Rev_show_list(List_node *node);

我们常用到的操作函数定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*接口包裹函数实现*/

static void *Malloc(size_t size)
{
    void *result = malloc(size);
    if(result == NULL){
        fprintf(stderr, "the memory is full\n");
        exit(1);
    }
    return result;
}

static List_node *Create_node(void)    //创建链表节点
{
    List_node *node = (List_node *)Malloc(sizeof(List_node));
    bzero(node, sizeof(List_node));

    return node;
}

static void Swap(void *a, void *b, int length)
{
    void *temp = Malloc(length);
    memcpy(temp, a, length);
    memcpy(a, b, length);
    memcpy(b, temp, length);
    
    free(temp);
}

static void Rev_show_list(List_node *node)
{
   //要打印当前节点，先打印其后续节点
   if(node != NULL){
       rev_show_list(node->next);
       printf("%d ", node->data);    
   }
}

宏定义如下：

1
2
3
4
5
6
7
8
/*控制链表宏定义*/

#define TRUE               (1)
#define FALSE              (0)
#define ZERO               (0)
#define ONLY_ONE           (1)
#define TWO                (2)
#define get_data_size()    ((unsigned long)&(((List_node *)0)->next))

三、链表接口的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
//1.链表的初始化
//      | head | tail | count |
//          \      /      0
//           \    /
//            NULL
List      *init_list(void)                            
{
    List *list = (List *)Malloc(sizeof(List));
    
    bzero(list, sizeof(List));    //全部清零

    return list; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//2. 链表的销毁
//              list
//             /
//         list_head  
//          /
//      | head | tail | count |
//          \         \   n + 1
//             
//            \          \
//            node->node2->node3

void      destroy_list(List **list)                   
{
    if(list == NULL || *list == NULL){
        return ;
    }
   
    //  链表删除步骤：
    //  1.删除链表节点信息;
    while((*list)->count){   //头部删除链表节点
        pop_front(*list);
    }
    //  2.删除链表控制信息.
    free(*list);
    *list = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//3.1 头部插入
Boolean   push_front(List *list, int value)           
{
    List_node *node = NULL;
  
    if(list == NULL){ 
        return FALSE;
    }   

    //创建节点并赋值
    node = create_node();
    node->data = value;

    //   case1:
    //      | head | tail | count |
    //          \      /      1
    //           \    /
    //            node
    if(list->count == ZERO){
        list->tail = node;
    }else{
    //   case2:
    //      | head |              tail | count |
    //          \                 /       n + 1
    //           \               /
    //            node->node2->node3
        node->next = list->head;
    }
    list->head = node;
    list->count++;
    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//3.2 尾部插入
Boolean   push_back(List  *list, int value)           
{
    List_node *node = NULL;

    if(list == NULL){
        return FALSE;
    }
  
    node = create_node();
    node->data = value;

    //   case1:
    //      | head | tail | count |
    //          \      /      1
    //           \    /
    //            node
    if(list->count == ZERO){
       list->head = list->tail = node;
    }else{
        //   case2:
        //      | head |              tail | count |
        //          \                 /       n + 1
        //           \               /
        //            node1->node2->node
        list->tail->next = node;
        list->tail = node;
    }
    list->count++;
    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

//4.1 头部删除
Boolean   pop_front(List *list)                       
{
    List_node *p_node = NULL;

    if(list == NULL || list->count == ZERO){
        return FALSE;
    }

    //   case1:
    //      | head | tail | count |
    //          \      /      1->0
    //           \    /
    //            node
    
    //   case2:
    //      | head |              tail | count |
    //          \                 /       n-> n - 1
    //           \               /
    //            node1->node2->node3
    p_node = list->head;
    if(list->count == ONLY_ONE){
        list->head = list->tail = NULL; 
    }else{
        list->head = list->head->next;
    }
    free(p_node);
    list->count--;
    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//4.2 尾部删除
Boolean   pop_back(List *list)                        
{
    List_node *p_node = NULL;

    if(list == NULL || list->count == ZERO){ 
        return FALSE;
    }
   
    //   case1:
    //      | head | tail | count |
    //          \      /      1->0
    //           \    /
    //            node
    
    //   case2:
    //      | head |              tail | count |
    //          \                 /       n-> n - 1
    //           \               /
    //            node1->node2->node3
    p_node = list->head; 
    if(list->count == ONLY_ONE){    
        list->head = list->tail = NULL;
        free(p_node);
    }else{
        //判断倒数第二个？
        //   p_node->next == list->tail
        while(p_node->next != list->tail){
            p_node = p_node->next;
        }
        free(list->tail);
        list->tail = p_node;
        p_node->next = NULL;
    }
    list->count--;
    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//5.1 链表的查找
List_node *find_node(List *list, int value)
{
    if(list == NULL)
    {
        return NULL;
    }
    List_node *p = list->head;
    while(p != NULL)
    {
        if(p->data == value)
        {
            printf("found the value: %d\n", value);
            return p;
        }
        p = p->next;
    }
    printf("No found!");
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//5.2 找到链表的倒数第num个节点
List_node *find_revise_node(List *list, int num)   
{
    List_node *move = NULL;
    int move_count = 0;
    //move + num == count
    if(list == NULL || num <= 0 || num > list->count){
        return NULL;
    }    

    move = list->head;
    //移动的步长
    move_count = list->count - num;

    while(move_count--){
        move = move->next;
    }

    return move;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//5.3 找到链表的中间节点
    // 1.) 快慢指针：
    //
    //       f  每次移动2步， s 每次移动1步
    //       10  23  5  15  50  67  45  32  82
    //
    // 2.)   10 /  2 == 5
    //       10 >> 1 == 5
    //
    //       0000 1010   10
    //            10 >> 1
    //       0000 0101   5
List_node *find_mid_node(List *list)    
{
    List_node *move = NULL;
    int move_count = 0;

    if(list == NULL){
        return NULL;
    }

    move = list->head;
    move_count = list->count >> 1;

    while(move_count--){
        move = move->next;
    }

    return move;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//6.1 链表节点的修改
void modify_node(List *list, int index, int value)
{
    int count = index;
    List_node *p = list->head;
    
    if(list == NULL || index >= list->count || index < 0)
    {
        return ;

    while(count--)
    {
        p = p->next;
    }
    
    p->data = value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//6.2链表节点的插入
Boolean insert_node(List *list,int index, int value)
{
    if(list == NULL || index > list->count || index < 0)
    {
        return FALSE;
    }
    //在最后则尾部插入
    if(index == list->count)
    {
        return push_back(list, value);
    }
    //在最前则头部插入
    if(index == 0)
    {
        return push_front(list, value);
    }
    
    int count =  index -1;
    List_node *p_node = list->head;

    //创建新节点
    List_node *node = create_node();
    node->data = value;
    
	//寻找需插入的节点位置
    while(count--)
    {
        p_node = p_node->next;
    }

	//进行插入
    node->next = p_node->next;
    p_node->next = node;

    list->count++;
    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//6.3 在O（1）的时间复杂度删除节点
	//由于是单链表，无法获取到前一个节点的位置，
	//所以，我们在这里用后一个节点代替我们所需的节点。
void      delete_one_node(List *list, List_node *node)   
{
	if(list == NULL || node == NULL)
	{
	    return ;
	}
	//尾部删除
    if(node == list->tail)
    {
        pop_back(list);
        return ;
    }
    List_node *p = node->next;//保存下一个节点位置

    node->data = node->next->data; //这个节点作为后一个的替代
    node->next = node->next->next; //直接指向下一个节点的后面
    free(p);
    list->count--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//7.1 升序排列
 //我们在这里用到了一种新的办法求我们的结构体大小，定义在宏里：
 
 // ((unsigned long)&(((List_node *)0)->next))
 //    
 //                    (List_node *)0          //指向首地址在0的List_node的指针
 //                   ((List_node *)0)->next)  //取next则指向了它的下一个
 //                 &(((List_node *)0)->next)) //取地址，得到的是这个地址，由于首地址，则正好是大小
 // ((unsigned long)&(((List_node *)0)->next)) //unsigned long 类型转换，得到就是大小
 // sizeof(List_node) - sizeof(List_node *);
 
   //内存分配，结构体里内存对齐现象：
    // int               data;  // 0   1   2   3
    //                          // 4   5   6   7
    // struct List_Node *next;  // 8   9  10  11
    //                            12  13  14  15
    
void      sort_list_ascend(List *list)                
{
    List_node *p_node = NULL;
    List_node *q_node = NULL;
    unsigned long data_size = 0;

    if(list == NULL || list->count < TWO){
        return ;
    }


    data_size = get_data_size();    //求得数据区域得大小
    for(p_node = list->head; p_node->next; p_node = p_node->next){
        for(q_node = p_node->next; q_node ; q_node = q_node->next){
            if(p_node->data > q_node->data){ 
                swap(p_node, q_node, data_size);                
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//7.2 降序排列
  //和升序类似
void      sort_list_descend(List *list)               
{
    List_node *p_node = NULL;
    List_node *q_node = NULL;
    unsigned long data_size = 0;

    if(list == NULL || list->count < TWO){
        return ;
    }

    data_size = get_data_size();    //求得数据区域得大小
    for(p_node = list->head; p_node->next; p_node = p_node->next){
        for(q_node = p_node->next; q_node ; q_node = q_node->next){
            if(p_node->data < q_node->data){ 
                swap(p_node, q_node, data_size);                
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
//8.1 显示链表信息
void      show_list(List *list)                       
{
    List_node *p_node = NULL;

    if(list != NULL && list->count != ZERO){ 
        for(p_node = list->head; p_node; p_node = p_node->next){ 
            printf("%d ", p_node->data);
        }
        printf("\n");
    }
}
1
2
3
4
5
6
7
8
9
10
//8.2 逆序输出链表信息
void      reverse_show_list(List *list)    
{
    if(list == NULL || list->count == ZERO){
        return ;
    }  
    // .h中定义的递归（先递归再输出）
    Rev_show_list(list->head);
    printf("\n");
}
1
2
3
4
5
6
7
8
9
//9 得到链表节点数量
  //这是一个有控制信息的链表，有关于节点数量的变量
int       get_list_count(List *list)                  
{
    if(list == NULL){ 
        return -1;
    }
    return list->count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
///10 合并两个有序链表
    //l1    | head |              tail | count |
    //          \                 /       n-> n - 1
    //           \               /
    //            node1->node2->node3
    //
    //
    //l2    | head |              tail | count |
    //          \                 /       n-> n - 1
    //           \               /
    //            node1->node2->node3
    //
List      *merge_two_lists(List *list1, List *list2)    
{
    List *result = NULL;
    List_node *list1_move = NULL;   
    List_node *list2_move = NULL;   

    if(list1 == NULL || list2 == NULL){
        return result;
    }

    result = init_list();   //结果链表得初始化

    list1_move = list1->head;
    list2_move = list2->head;

    //如果两个链表都没有遍历完，进行比较
    while(list1_move != NULL && list2_move != NULL){
        if(list1_move->data <= list2_move->data){
            push_back(result, list1_move->data);
            list1_move = list1_move->next;
        }else{
            push_back(result, list2_move->data);
            list2_move = list2_move->next;
        }
    }

    //当两个链表中任何一个遍历结束，则把另外一个进行尾部添加
    while(list2_move != NULL){
        push_back(result, list2_move->data);
        list2_move = list2_move->next;
    }

    while(list1_move != NULL){
        push_back(result, list1_move->data);
        list1_move = list1_move->next;
    }

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

//11//合并两个有序链表（递归）
    //   
    //l1            node1->node2->node3
    //
    //     l->node1->node4...
    //    
    //l2            node4->node5->node6
    //
List      *merge_two_lists_recure(List *list1, List *list2)    
{
    List *node = NULL;
    List *l  = init_list();
    List *l1 = list1;
    List *l2 = list2;

    if(l1->count == 0)
    {
        return list2;
    }
    if(l2->count == 0)
    {
        return list1;
    }

    //若l1当前head满足较小情况，将l指向l1,让l1指向l1的下一个节点，进入递归比较l1->head->next形成的链表与l2再进行比较，返回的node链表是后面节点的新链表;
    if(l1->head->data < l2->head->data)
    {
        l->head = l1->head;
        l1->head = l1->head->next;
        l1->count --;
        node = merge_two_lists_recure(l1, l2);
    }
    else
    {
        l->head = l2->head;
        l2->head = l2->head->next;
        l2->count--;
        node = merge_two_lists_recure(l1, l2);
    }
    //完成递归后，l指向node组成的新链表;
    l->head->next = node->head;
    l->count = node->count +1;
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

//12 逆置一个链表
    //因为会改变结构，为了不失去对后面的节点的信息，使用了三个指针，交换前两个，不丢失第三个 。
    //
    //      | head |              tail | count |
    //          \                   \      n-> n - 1
    //           \                   \
    //            node1->node2->node3->node4
    //             |      |       |
    //             p      q       m
    //
    //            node1<-node2 node3->node4
    //             |      |       |      |
    //             p      q       m      |
    //                    p       q      m   
    //
    
List      *reverse_list(List *list)    
{
    List_node *p_node = NULL;
    List_node *q_node = NULL;
    List_node *m_node = NULL;

    if(list == NULL || list->count < TWO){
        return list;
    } 
    //两个节点
    if(list->count == TWO){
        list->tail->next = list->head;
        list->head->next = NULL;
    }else{    //三个节点
        p_node = list->head;
        q_node = p_node->next;
        m_node = q_node->next;
        p_node->next = NULL;
        do{
            q_node->next = p_node;   //让中间指针的next指向前一个
            p_node = q_node;    //指针整体向后搬移
            q_node = m_node;
            m_node = m_node->next;
        }while(m_node != NULL);
        q_node->next = p_node;
    }
    //交换头尾指针
    swap(&(list->head), &(list->tail), sizeof(List_node *));
    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
//13 链表的拷贝
  //使用了尾插法依次将元素插入
List      *list_dump(List *list)    
{
    List * new_list = init_list();
    List_node * node = list->head;
    for(node = list->head; node; node = node->next)
    {
        push_back(new_list, node->data);
    }
    return new_list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//14 判断链表是否有交点
  //若两个链表有交点，则尾节点一定是同一个。
  //
  //  l1-> => => =>
  //                \
  //                 \     
  //                 /  => => => => => =>
  //  l2-> => => => 
  //
Boolean   is_list_intersect(List *list1, List *list2)    
{
    if(list1 == NULL || list2 == NULL){
        return FALSE;
    }
//    
    if( list1->tail == list2->tail)
    {
        printf("intersect\n");
        return TRUE;
    }
    else
    {
        printf("nothing\n");
        return FALSE;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//15 得到第一个交点
  //             l1 =>
  //                    \     
  //                    /   => => => => => =>
  //     l2 => => => => 
  //     长度不等，先获得两个链表都离相遇点长度相等的地方开始依次比较。
List_node *get_first_common_node(List *list1, List *list2)    
{
    int list1_len = 0;
    int list2_len = 0;
    int distance = 0;
    List_node *p_node = NULL;
    List_node *q_node = NULL;
    

    if(!is_list_intersect(list1, list2)){    //判断两个链表是否有交点
        return NULL;
    }
   
    list1_len = list1->count;
    list2_len = list2->count;

    p_node = list1->head;
    q_node = list2->head;

    //判断较长链表并首先进行移动
    if(list1_len >= list2_len){
        distance = list1_len - list2_len;
        while(distance--){ 
            p_node = p_node->next;
        }
    }else{
        distance = list2_len - list1_len;
        while(distance--){
            q_node = q_node->next;
        }
    }

    //依次对对应节点进行判断是否相等，如果相等则是第一个相交节点
    while(p_node != q_node){
        p_node = p_node->next;
        q_node = q_node->next;
    }
   
    return p_node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//16 判断一个链表是否有环
  //
  //   - - - 、  
  //          \    - - - - 、
  //           \ /          |
  //            \          /
  //             ` - - - -
  //
Boolean has_circle(List *list)                                
{
    List_node *p = list->head;  //slow
    List_node *q = list->head;  //fast
    while(p != NULL && q != NULL && q->next !=NULL)
    {
        p = p->next;        //一次一步
        q = q->next->next;  //一次两步

        //如果有环，则一定会相遇
        if(p == q)
        {
            printf("we found circle!\n");
            return TRUE;
        }
    }
    printf("no circle!\n");
    return FALSE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//17 找到带环链表的环入口节点
  //
  //   - - - 、  
  //          \    - - - - 、
  //           \ /          |
  //            \          /
  //        入口点 ` - -*- -
  //                   \
  //                     相遇点
  //            |<-x->|
  //  |<---a--->|<-----r---->|
  //  |<----------L--------->|
  // 我们设整个链表长L，入口点与相遇点长x，起点到入口点长度为a;
  // 快指针走的长度是慢指针的2倍，由于快指针可能不止走了一圈;
  // 慢指针走了s步，即快指针走了2s步。
  //
  // ∵ 2s = s + nr ;
  // ∴ s = nr;
  //
  //   a + x = nr
  //   a + x = nr = (n-1)r + r =  (n-1)r + L -a
  //   a = (n-1)r + (L -a -x)
  //   链表从头到环入口点长度 = (n -1)环长 + 相遇点到环入口长度
  //   所以， 从链表头和相遇点各设一个一步长的指针，必定会在相遇点回合。
  //
List_node *find_circle_first_node(List *list)                  
{
    List_node * entry = NULL;
    if(!has_circle(list))
    {
        return NULL;
    }
    List_node *p = list->head;  //slow
    List_node *q = list->head;  //fast
    while(p != NULL && q != NULL && q->next !=NULL)
    {
        p = p->next;
        q = q->next->next;
        if(p == q)
        {
            break;    //相遇点p和q
        }
    }
    //p为相遇点开始
    q = list->head;   //q从链表头开始
    while(q != p)
    {
        p =p->next;
        q =q->next;
    }
    printf("we found the node is %d\n", q->data);
    return q;
}

四、测试功能

测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include "list.h"


int main()
{
    int i = 0;
    int num = 0;
    List *list = NULL;
    List *list1 = NULL;
    List *list2 = NULL;
    List_node * node = NULL;
    
    printf("1.init_list:\n");
    list = init_list();
    list1 = init_list();
    list2 = init_list();
    
    printf("3.1 list1 push_front :\n");
    for(i = 0; i < 6; i++)
    {
        push_front(list1, rand()%100);
    }

    show_list(list1);
    

    printf("3.2 list2 push_back:\n");
    for(i = 0; i < 4; i++)
    {
        push_back(list2, rand()%100);
    }
    show_list(list2);


    printf("4.1 list1 pop_front:\n");
    pop_front(list1);
    show_list(list1);

    printf("4.2 list2 pop_back:\n");
    pop_back(list2);
    show_list(list2);
    
    printf("7.1 sort_list1_ascend:\n");                   
    sort_list_ascend(list1);                  
    show_list(list1);
    
    printf("7.2 sort_list2_descend:\n");                   
    sort_list_descend(list2);                  
    show_list(list2);

    printf("12 reverse_list2:\n");
    reverse_list(list2);
    show_list(list2);
    
#if 0
    printf("10. list : merge_two_lists(list1, list2):\n");
    list = merge_two_lists(list1, list2);
    show_list(list);
#endif

#if 1
    printf("11. list : merge_two_lists_recure(list1, list2):\n");
    list = merge_two_lists_recure(list1, list2);
    show_list(list);
#endif
         
    printf("8.1 show_list(list);\n");      
    show_list(list);


    printf("8.2 reverse_show_list(list);\n");
    reverse_show_list(list);
#if 1 
    printf("find_node:\n");
    printf("which one?(value to find)\n"); 
    scanf("%d",&num);
    printf("found num of list is :%d \n",find_node(list, num)->data);
#endif

#if 1
    printf("find_revise_node:\n");     
    printf("which one index ?(reverse)\n"); 
    scanf("%d",&num);
    printf("reverse num of list is :%d \n",find_revise_node(list, num)->data);
#endif
    printf("5.3 find_mid_node(list):\n") ;
    printf("%d \n",find_mid_node(list)->data);

    printf("9. get_list_count:\n"); 
    printf("the count of list is :%d\n", get_list_count(list));

#if 1  
    printf("6.3 delete_one_node:");
    printf("which one?(to delete)\n"); 
    scanf("%d",&num);
    node = create_node();
    node = find_node(list,num);
    delete_one_node(list, node);
    show_list(list);
#endif

#if 1
    printf("6.1 modify_node :\n");
    modify_node(list, 1, 26);
    show_list(list);
#endif

#if 1
    printf("6.2 insert_node: \n");
    insert_node(list, 2, 18);
    show_list(list);
#endif 

#if 1
    printf("16. has_circle:\n");
    //list->head->next->next->next->next->next = list->head->next;

    if(has_circle(list))
    {
        printf("17 find_circle_first_node:\n");
        find_circle_first_node(list);
    }
#endif
    printf("13. list1:list_dump(list)\n");
    list1 = list_dump(list);
    printf("list1: ");
    show_list(list1);
    
    printf("14. is_list_intersect:\n");
    
    if(is_list_intersect(list1, list))
    {
        printf("the common node: %d\n",get_first_common_node(list1, list));
    }

    printf("2. destroy_list:\n");
    destroy_list(&list1);
    destroy_list(&list2);
    destroy_list(&list);
    return 0;
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
root@aemonair:/ctl_list# ./bin/list 
1.init_list:
3.1 list1 push_front :
35 93 15 77 86 83 
3.2 list2 push_back:
86 92 49 21 
4.1 list1 pop_front:
93 15 77 86 83 
4.2 list2 pop_back:
86 92 49 
7.1 sort_list1_ascend:
15 77 83 86 93 
7.2 sort_list2_descend:
92 86 49 
12 reverse_list2:
49 86 92 
11. list : merge_two_lists_recure(list1, list2):
15 49 77 83 86 86 92 93 
8.1 show_list(list);
15 49 77 83 86 86 92 93 
8.2 reverse_show_list(list);
93 92 86 86 83 77 49 15 
find_node:
which one?(value to find)
92
found the value: 92
found num of list is :92 
find_revise_node:
which one index ?(reverse)
2
reverse num of list is :92 
5.3 find_mid_node(list):
86 
9. get_list_count:
the count of list is :8
6.3 delete_one_node:which one?(to delete)
92
found the value: 92
15 49 77 83 86 86 93 
6.1 modify_node :
15 26 77 83 86 86 93 
6.2 insert_node: 
15 26 18 77 83 86 86 93 
16. has_circle:
no circle!
13. list1:list_dump(list)
list1: 15 26 18 77 83 86 86 93 
14. is_list_intersect:
nothing
2. destroy_list:

总结

至此。我们完成了对带控制信息链表的定义，实现，测试;
我们会发现加上控制信息之后，一些操作被封装起来，有可能更加便捷。
这是一种思路，一种方法。
以上解法也不一定是最简便快捷的，只是其中一种实现而已。
我们还将继续对数据结构进行进一步的探讨。

文章作者: Air
文章链接: http://aemonair.github.io/2016/05/31/Data_Structure_02_Single_Linked_List_With_Control/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Aemonair！
DataStructLinkedList
相关推荐
2020-04-29
数据结构C语言实现4.进一步封装的双向链表
2020-04-29
数据结构C语言实现1.单链表
2020-04-29
数据结构C语言实现5.通用栈
2020-04-29
数据结构C语言实现6.通用队列
2020-04-29
数据结构C语言实现3.双端链表
2020-04-29
数据结构C语言实现8.广义表
简