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

链表与数组

在编程语言中，数组数据结构（array data structure），简称数组（Array），是一种数据结构，是数据元素（elements）的集合。有限个相同类型的元素按顺序存储，用一个名字命名，然后用编号区分他们的变量的集合;这个名字称为数组名，编号称为下标。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不同与数组的是，并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储。

一、链表与数组的优缺点

首先让我们来介绍下链表与数组之间的优缺点:

// 数组的缺点：
//
//    1.一旦数组定义，则大小固定，无法进行修改（数组的大小）。
//    2.数组插入和删除的效率太低，时间复杂度O（n）。
//    
// 数组的优点：
//    
//    1.下标访问，速度快，时间复杂度是O（1）
//
//////////////////////////////////////////////////////////
//
// 链表：
//   
// 链表的优点：
//   
//    1.资源允许的情况下，规模可以不断的增长或减小。
//    2.删除和添加效率高，O（1）
//
// 链表的缺点：
//
//    链表的遍历过程效率比较低。

为什么会有这样的差异呢。
接下来我们一步步来看。

二、数据结构类型的定义

数组的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
//方法1
int array1[10] = {0};    

//方法2
int array2[] = {12, 23, 34, 45, 56, 67, 78};  

//方法3
int *array3 = NULL;
array3 = (int *)malloc(sizeof(int) * 100);   
if(array3 != NULL){
     fprintf(stderr, "the memory is full!\n");
     exit(1);
}

这里，我们的array1和array2都在定义时直接分配了栈上的内存空间;
而array3是一个int类型的指针，指向我们在堆上用malloc分配的4bytes ×100 = 400 bytes大小的空间。

我们的数组虽然在O(1)的时间复杂度访问下标进行数据存取查找，可是一般数组定义后，大小不能够进行动态变化，且插入删除效率过低，时间复杂度为O(n).
所以，为了弥补这些不足，我们又学习到了链表。

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，链表由相同结构的链表节点构成，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。可以关注链表节点的结构：

1
2
3
4
5
6
7
typedef struct List_node
{
    int               data;    //数据域
    struct List_node *next;    //指针域
}List_node;

typedef List_node *List_head;

  1. 链表节点的两个组成部分：
    我们可以看到链表节点主要分为两大部分:数据域和链域。
    数据域是我们最要存储的内容，而链域则代表着一种指针。

  2. 如何把两个节点进行连接：
    这个指针指向类型为链表节点，这样每一个节点就可以记录下下一个节点的位置，从而把原本毫不相干的链表节点串接起来。

dlist

一个链表节点定义;

1
2
3
4
5
6
7
8
9
typedef struct Node{
    //数据域
    char name[20];  //姓名
    char sex;       //m 男 w 女 性别
    char age;       //年龄
    char jobs[20];  //职业
    //链域
    struct Node *next;
}Node;

再申请一个链表节点;

1
2
3
4
5
Node node1 = {0};

Node *p_node = (Node *)malloc(sizeof(Node));

node1.next = p_node;

malloc 函数：
void *malloc(int size);
说明：malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。
man malloc可在bash中查看帮助文档。

三、链表的常见接口

我们把可以对链表的操作是在.h文件中进行声明的，我们叫这样的声明为接口，如下是单链表的接口声明:

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
/* list.h */
/*
 * 带头节点的链表
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#define TRUE     (1)
#define FALSE    (0)

typedef unsigned char Boolean;

//定义链表节点类型
typedef struct List_node{
    int               data;    //数据域  //4
    struct List_node *next;    //指针域  //32位：4 //64位：8
}List_node;


typedef List_node   *List_head;   

//链表的接口
//  常见接口：
//     1.初始化
//     2.销毁
//     3.增加
//     4.删除
//     5.查找
//     6.修改
//     7.排序
//     8.显示
List_head init_list(void)                                        ;   //1. 链表的初始化
void      destroy_list(List_head *head)                          ;   //2. 链表的销毁
Boolean   push_front(List_head head, int value)                  ;   //3.1 头部添加
Boolean   push_back(List_head head, int value)                   ;   //3.2 尾部添加（效率低，从头找到尾才能添加）
Boolean   pop_front(List_head head)                              ;   //4.1 头部删除
Boolean   pop_back(List_head head)                               ;   //4.2 尾部删除（效率低）
Boolean   find_node(List_head head, int value, List_node **node) ;   //5. 链表的查找
void      modify_node(List_node *node, int value)                ;   //6.1 链表节点的修改
Boolean   insert_node(List_head head, int index, int value)      ;   //6.2 链表节点的插入(下标)
void      sort_list_ascend(List_head head)                       ;    //7.1 链表升序
void      sort_list_descend(List_head head)                      ;    //7.2 链表降序
void      show_list(List_head head)                              ;    //8.1 显示链表信息
int       get_list_length(List_head head)                        ;    //8.2 链表的长度

我们可以通过定义 包裹函数 来缩短程序。每个包裹函数完成实际的函数调用，检查返回值，并在发生错误时终止进程。
包裹函数其实就是封装函数，调用一个函数来实现这个功能。既然我们会经常用到一些函数并且还要进行错误处理，那么，我们可以将这些函数封装起来，也放入头文件.h当中。

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
//包裹函数
static void *Malloc(size_t size);
static List_node *create_node(void);
static void swap(void *a, void *b, int length);

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)
{
    //申请节点，并且对节点初始化（置为0）
    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);
}

四、链表接口的实现

为了能够使用这些我们所提供的接口，如同菜名需要菜谱一样，我们要能够实现这些操作，可以在list.c中进行实现。

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

//////////////////////////////////////////////////////////////////////////////////////
//接口实现
//////////////////////////////////////////////////////////////////////////////////////

List_head init_list(void)                                           //1. 链表的初始化
{
    List_head head = NULL;

    head = create_node();

    return head;
}

void      destroy_list(List_head *head)                             //2. 链表的销毁
{
    List_node *p = NULL;
    List_node *q = NULL;

    if(head == NULL || *head == NULL){
        return ;
    } 
   
    //从链表头节点开始，依次对节点进行删除
    p = *head;
    while(p != NULL){
        q = p;
        p = p->next;
        free(q); 
    }

    *head = NULL;
}

Boolean   push_front(List_head head, int value)                      //3.1 头部添加
{
    List_node *node = NULL;

    if(head == NULL){    //判断链表是否存在
        return FALSE;
    }

    //生成链表节点并且赋初值
    node = create_node();
    node->data = value;

    node->next = head->next;
    head->next = node;

    head->data++;  
    return TRUE;
}

Boolean   push_back(List_head head, int value)                      //3.2 尾部添加（效率低，从头找到尾才能添加）
{
    List_node *p_node = NULL;

    if(head == NULL){    //参数检测
        return FALSE;
    }  

    //查找尾部节点的位置
    p_node = head;
    while(p_node->next != NULL){
        p_node = p_node->next;
    }

    //把新生成的节点追加到链表末尾
    p_node->next = create_node();
    p_node->next->data = value;
    
    head->data++;
    return TRUE;    
}

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

    if(head == NULL || head->next == NULL){
        //链表不存在或者没有有效节点
        return FALSE;
    }

    p_node = head->next;
    head->next = p_node->next;
    free(p_node);
   
    head->data--;
    return TRUE;
}

Boolean   pop_back(List_head head)                                   //4.2 尾部删除（效率低）
{
    List_node *p_node = NULL;

    //参数检测
    if(head == NULL || head->next == NULL){
        return FALSE;
    }

    //从头结点开始查找倒数第二个节点
    p_node = head;

    while(p_node->next->next != NULL){
        p_node = p_node->next;
    }
    //删除最后一个节点，把倒数第二个置为最后一个节点
    free(p_node->next);
    p_node->next = NULL;
  
    head->data--;
    return TRUE;
}




Boolean   find_node(List_head head, int value, List_node **node)    //5. 链表的查找
{
    List_node *p_node = NULL;

    if(head == NULL){
        return FALSE;
    }

    //从第一个有效节点开始查找值为value的节点
    p_node = head->next;
    while(p_node != NULL){
        if(p_node->data == value){    //找到value所在节点
            if(node != NULL){
                *node = p_node;
            }
            return TRUE;
        }
        p_node = p_node->next;
    }
    return FALSE;
}

void      modify_node(List_node *node, int value)                    //6.1 链表节点的修改
{
    node->data = value;
}

Boolean   insert_node(List_head head, int index, int value)   //6.2 链表节点的插入
{
    List_node *node = NULL;
    List_node *p_node = NULL;
    int count = index;

    if(head == NULL || index < 0 || index > head->data){
       //链表不存在并且下标不符合规则
       return FALSE;
    }

    //创建新的节点
    node = create_node();
    node->data = value;

    //寻找插入的位置
    p_node = head;
    while(count--){   //找到被插入节点的前一个节点
       p_node = p_node->next;
    }

    //插入新的节点
    node->next = p_node->next;
    p_node->next = node;
    head->data++;
    return TRUE;
}

void      sort_list_ascend(List_head head)                           //7.1 链表升序
{
    List_node *p_node = NULL;
    List_node *q_node = NULL;

    if(head == NULL || head->data < 2){
        return ;
    }

    for(p_node = head->next; 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, (unsigned long)(&((List_node *)0)->next));
            }
        }
    }
}

void      sort_list_descend(List_head head)                          //7.2 链表降序
{
    List_node *p_node = NULL;
    List_node *q_node = NULL;

    if(head == NULL || head->data < 2){
        return ;
    }

    for(p_node = head->next; 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, sizeof(List_node) - sizeof(List_node *));
            }
        }
    }
}

void      show_list(List_head head)                                 //8.1 显示链表信息
{
    List_node *p_node = NULL;

    if(head == NULL){
        return ;
    }

    for(p_node = head->next; p_node != NULL; p_node = p_node->next){
        printf("%d  ", p_node->data);
    }
    printf("\n");
}

int       get_list_length(List_head head)    //8.2 链表的长度
{
    if(head == NULL){
        return -1;
    }
    return head->data;
}

设计完这个单链表的接口与实现之后，我们要对相应功能进行检测。
测试代码如下：

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
//主函数-各个函数的测试
int main(int argc, char ** argv)
{
    int i = 0;
    List_head head = NULL;
    head = init_list();
    List_node *node = create_node();
 
    printf("\n头部插入:\n"); 
    for(i = 0 ; i < seed ; i++ )
    {
        push_front(head,rand()%100);
    }
    show_list(head);                   
    
    printf("\n尾部插入:\n"); 
    for(i = 0 ; i < seed ; i++ )
    {
        push_back(head,rand()%100);
    }
    show_list(head);                   

    printf("\n头部删除:\n"); 
    pop_front(head);
    show_list(head);                 
  
    printf("\n尾部删除:\n"); 
    pop_back(head);
    show_list(head);                 
   
    printf("\n插入节点:\n"); 
    insert_node(head, 3, 100);
    show_list(head);                 
    
    find_node(head, 77,&node);

    printf("\n升序排序:\n");
    sort_list_ascend(head);
    show_list(head);                 

    printf("\n降序排序:\n");
    sort_list_descend(head);
    show_list(head); 
               
    printf("\n修改节点数据：\n");
    node = head->next->next; 
    modify_node(node, 777);
    show_list(head); 
    
    printf("\nthe length of this list :%d\n",get_list_length(head));
    
    destroy_list(&head);
    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
root@aemonair# ./my_head_list 
链表初始化成功！

头部插入:
当前链表如下：
93 15 77 86 83 

尾部插入:
当前链表如下：
93 15 77 86 83 35 86 92 49 21 

头部删除:
当前链表如下：
15 77 86 83 35 86 92 49 21 

尾部删除:
当前链表如下：
15 77 86 83 35 86 92 49 

插入节点:
当前链表如下：
15 77 86 100 83 35 86 92 49 

the node is found !

升序排序:
当前链表如下：
15 35 49 77 83 86 86 92 100 

降序排序:
当前链表如下：
100 92 86 86 83 77 49 35 15 

修改节点数据：
当前链表如下：
100 777 86 86 83 77 49 35 15 

the length of this list :9
链表销毁完毕！

测试程序2：

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

int main(int argc, char **argv)
{
    List_head head = init_list();   //链表的初始化
    int i = 0;
    int value = 0;
    List_node *find = NULL;

    for(i = 0; i < 10; ++i){    //尾部追加10个元素
        push_front(head, rand() % 100);
    }

    pop_front(head);

    pop_back(head);

    show_list(head);   //显示链表信息

    printf("the count of list:%d\n", get_list_length(head));
 
    printf("你要找哪个节点:？\n");
    scanf("%d", &value);

    find_node(head, value, &find);
    if(find == NULL){
        printf("the %d is not found!\n", value);
    }else{
        printf("found! the value is %d\n", find->data);
    }
    sort_list_ascend(head);
    show_list(head);   //显示链表信息

    sort_list_descend(head);
    show_list(head);   //显示链表信息

    destroy_list(&head);
    return 0;
}

总结：

以上，我们关于单链表的基本操作和基本接口的实现。
对于链表的指针域在交换两个的时候很容易出现问题，之后还会进行进一步的详解。

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