链表功能函数总结

发表于 | 分类于 | | 阅读次数:

最近在学习数据结构的内容，链表（LinkList）就是数据结构中最基本的一种数据类型，链表本身的构造特性也特别有意思，这里就构造了一个链表的功能函数，包含了链表的创建初始化、打印输出、计算长度、查找中间结点和清除链表等功能，在今后的学习中会不断扩充添加不同的功能！
函数运行如下图所示：

LinkList

功能函数

链表创建函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//声明链表创建函数（尾插法）
void ListCreat(LinkList *L, int n)
{
    LinkList *p, *r;
    int i;
    srand(time(0));
    p = L;
    for(i = 0; i < n; i++)
    {
        r = (LinkList *)malloc(sizeof(LinkList));
        p->data = rand() % 100 + 1;
        p->next = r;
        p = r;
    }
    p->next = NULL;
}

这里使用了尾插法对链表进行生成操作，使用rand()函数生成随机数对链表进行初始化。

链表打印函数

1
2
3
4
5
6
7
8
9
10
11
12
//打印链表函数
ListPrint(LinkList *L)
{
    LinkList *p;
    p = L;
    while(p->next != NULL)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

通过判定p->next是否为NULL为条件对链表进行遍历打印。

获取链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
//声明一个函数，获取链表长度
int ListLength(LinkList *L)
{
    LinkList *p;
    p = L;
    int count = 0;
    while(p->next != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

同上，通过判定p->next是否为NULL为条件对链表进行遍历计算链表的长度。

获取中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//声明一个函数，获取链表中间结点
int ListMid(LinkList *L)
{
    LinkList *cur, *mid;
    cur = mid = L;
    while(cur->next != NULL)
    {
        if(cur->next->next != NULL)
        {
            mid = mid->next;
            cur = cur->next->next;
        }
        else
        {
            cur = cur->next;
        }
    }
    return mid->data;
}

设置cur的步长为2，mid的步长为1，同时对链表进行遍历，以cur == NULL为结束条件，可以以较高的效率得到链表的中间结点。

链表清除

1
2
3
4
5
6
7
8
9
10
11
12
13
//声明链表清理函数
void ListClear(LinkList *L)
{
    LinkList *p;
    p = L;
    while(L->next != NULL)
    {
        L = p->next;
        free(p);
        p = L;
    }
    free(L);
}

使用free()函数对我们生成的链表空间进行遍历删除。

总体代码

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
#include <stdio.h>
#include <stdlib.h>
//声明链表结构体
typedef struct node
{
    int data;
    struct node *next;
}LinkList;
//声明链表创建函数（尾插法）
void ListCreat(LinkList *L, int n)
{
    LinkList *p, *r;
    int i;
    srand(time(0));
    p = L;
    for(i = 0; i < n; i++)
    {
        r = (LinkList *)malloc(sizeof(LinkList));
        p->data = rand() % 100 + 1;
        p->next = r;
        p = r;
    }
    p->next = NULL;
}
//打印链表函数
ListPrint(LinkList *L)
{
    LinkList *p;
    p = L;
    while(p->next != NULL)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}
//声明一个函数，获取链表长度
int ListLength(LinkList *L)
{
    LinkList *p;
    p = L;
    int count = 0;
    while(p->next != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}
//声明一个函数，获取链表中间结点
int ListMid(LinkList *L)
{
    LinkList *cur, *mid;
    cur = mid = L;
    while(cur->next != NULL)
    {
        if(cur->next->next != NULL)
        {
            mid = mid->next;
            cur = cur->next->next;
        }
        else
        {
            cur = cur->next;
        }
    }
    return mid->data;
}
//声明链表清理函数
void ListClear(LinkList *L)
{
    LinkList *p;
    p = L;
    while(L->next != NULL)
    {
        L = p->next;
        free(p);
        p = L;
    }
    free(L);
}
//主函数
int main()
{
    printf("1.生成链表\n");
    printf("2.打印链表\n");
    printf("3.获取链表长度\n");
    printf("4.获取中间结点\n");
    printf("5.清楚链表\n");
    printf("0.退出\n");
    LinkList *L;
    L = (LinkList *)malloc(sizeof(LinkList));
    int length = 10;
    char operator;
    while(1)
    {
        scanf("%c", &operator);
        switch(operator)
        {
            case '1':
                printf("**********生成链表***********\n");
                ListCreat(L, length);
                break;
            case '2':
                printf("**********打印链表**********\n");
                ListPrint(L);
                break;
            case '3':
                printf("********获取链表长度********\n");
                printf("The length of this ListCreat is: %d\n", ListLength(L));
                break;
            case '4':
                printf("********获取中间结点********\n");
                printf("The value of the middle node is: %d\n", ListMid(L));
                break;
            case '5':
                ListClear(L);
                printf("**********清楚完毕**********\n");
                break;
            case '0':
                printf("************退出************\n");
                return 0;
        }
    }
    return 0;
}
-------------本文结束感谢您的阅读-------------
0%