数据结构——单链表

发表于 | 分类于 | 评论数：

摘要：单链表的基本操作，由于太久没有复习数据结构了，导致该忘的都忘了，所以在这里记录重新学习数据结构的笔记，以备以后查看。

单链表

链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表节点定义

1
2
3
4
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode;

此处定义了一个单链表的结构体，里面包含数据以及下一个数据的单链表指针。

创建节点

1
2
3
4
5
LNode *create_LNode(ElemType data){
    LNode *ret = (LNode*)malloc(sizeof(LNode));
    ret->data = data; //C中将NULL作为空指针之用，C++用nullptr
    return ret;
}

此处可以直接传入数据进行创建节点，当创建头节点时可以用NULL进行数据传入；

头插法创建单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
int create_link_head(LNode *L,ElemType data[],int n){//传入头结点，数组，数组元素的个数
    LNode *p;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;
    L->next = NULL;
    for(i=0;i<n;i++){
        p = create_LNode(data[i]);
        p->next = L->next;
        L->next = p;
    }
    return L;
}

image-20200616173642497

tips：

因为是头插法，所以插入后的顺序是数组的倒序。

尾插法创建单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int create_link_tail(LNode *L,ElemType data[],int n){ //n为插入的个数
    LNode *p,*q;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;         //申请L为头节点
    q = L;
    for(i = 0; i< n ;i++){
        p = create_LNode(data[i]);
        q ->next = p;
        q = q->next;    //p = q;
    }
    q ->next = NULL;    //将最后一个节点指为NULL
    return L;
}

获取链表的长度

1
2
3
4
5
6
7
8
9
10
int get_length(LNode *L){
    int ret =0;
    if(L == NULL)
        return ret;
    while(L->next != NULL){
        ret++;
        L = L->next;
    }
    return ret;
}

获取链表中指定位置的节点指针

1
2
3
4
5
6
7
8
9
10
11
LNode *get_node(LNode *L,int p){ //p的范围是（1~N）不包含头结点
    LNode* ret;
    int count = 0;
    //ret = L->next;
    ret = L;
    while( ret != NULL && count< p){
        count++;
        ret = ret->next;
    }
    return ret;
}

获取单链表中data值第一次出现的节点指针

1
2
3
4
5
6
7
LNode *get_first_elem_node(LNode *L,ElemType data){
    LNode* ret = L->next;
    while(ret != NULL && ret->data != data){
        ret = ret->next;
    }
    return ret;
}

在指定的节点后插入节点

1
2
3
4
5
6
7
8
9
10
11
12
int insert_elem(LNode *L,int p,ElemType data){
    LNode *m = NULL;
    LNode *n = NULL;
    if(p<0 || L->next == NULL)
        return 0;
    m = get_node(L,p);
    n = (LNode*)malloc(sizeof(LNode));
    n->next = m->next;
    n->data = data;
    m->next = n;
    return 1;
}

删除节点

删除某个下标的节点,并返回被删除的节点的指针

1
2
3
4
5
6
7
8
9
10
LNode *delete_node(LNode *L,int p){
    LNode *ret = NULL;
    LNode *m = NULL;
    if(p < 1 || get_length(L)==0 ) //当删除的节点位置小于1或者长度为0时
        return 0;
    m = get_node(L,p-1);
    ret = m->next;
    m->next = m->next->next;
    return ret;
}

合并表

合并两个元素递增的单链表到一个新的单链表且依然有序

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
LNode* merge_link(LNode* A,LNode* B,LNode* C){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;
    C = (LNode*)malloc(sizeof(LNode));
    C->data=NULL;
    r = C;
    while(p!=NULL && q!=NULL){
        if(p->data<=q->data){
            r->next=p;
            p=p->next;
            r=r->next;
        }
        else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    //下面的操作是另一个不为空的表剩下都归并到新的表的后面
    if(p==NULL)
        r->next = q;
    if(q==NULL)
        r->next = p;
    return C;
}

打印单链表

1
2
3
4
5
6
7
void print_link(LNode *L){
    while(L->next){
        L = L->next;
        printf("%3d",L->data);
    }
    printf("\n");
}

完整的函数（包含测试部分）

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
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode;

//初始化节点
LNode *create_LNode(ElemType data){
    LNode *ret = (LNode*)malloc(sizeof(LNode));
    ret->data = data; //C中将NULL作为空指针之用，C++用nullptr
    return ret;
}

//尾插法建立单链表
int create_link_tail(LNode *L,ElemType data[],int n){ //n为插入的个数
    LNode *p,*q;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;         //申请L为头节点
    q = L;
    for(i = 0; i< n ;i++){
        p = create_LNode(data[i]);
        q ->next = p;
        q = q->next;    //p = q;
    }
    q ->next = NULL;    //将最后一个节点指为NULL
    return L;
}
//头插法建立单链表
int create_link_head(LNode *L,ElemType data[],int n){
    LNode *p;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;
    L->next = NULL;
    for(i=0;i<n;i++){
        p = create_LNode(data[i]);
        p->next = L->next;
        L->next = p;
    }
    return L;
}

//获取单链表的长度
int get_length(LNode *L){
    int ret =0;
    if(L == NULL)
        return ret;
    while(L->next != NULL){
        ret++;
        L = L->next;
    }
    return ret;
}

//获取链表中指定位置的节点指针
LNode *get_node(LNode *L,int p){
    LNode* ret;
    int count = 0;
    //ret = L->next;
    ret = L;
    while( ret != NULL && count< p){
        count++;
        ret = ret->next;
    }
    return ret;
}

//获取单链表中data值第一次出现的节点指针
LNode *get_first_elem_node(LNode *L,ElemType data){
    LNode* ret = L->next;
    while(ret != NULL && ret->data != data){
        ret = ret->next;
    }
    return ret;
}

//在指定的节点后插入节点
int insert_elem(LNode *L,int p,ElemType data){
    LNode *m = NULL;
    LNode *n = NULL;
    if(p<0 || L->next == NULL)
        return 0;
    m = get_node(L,p);
    n = (LNode*)malloc(sizeof(LNode));
    n->next = m->next;
    n->data = data;
    m->next = n;
    return 1;
}

//删除某个下标的节点,并返回被删除的节点
LNode *delete_node(LNode *L,int p){
    LNode *ret = NULL;
    LNode *m = NULL;
    if(p < 1 || get_length(L)==0 ) //当删除的节点位置小于1或者长度为0时
        return 0;
    m = get_node(L,p-1);
    ret = m->next;
    m->next = m->next->next;
    return ret;
}

//合并两个元素递增的单链表到一个新的单链表且依然有序
LNode* merge_link(LNode* A,LNode* B,LNode* C){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;
    C = (LNode*)malloc(sizeof(LNode));
    C->data=NULL;
    r = C;
    while(p!=NULL && q!=NULL){
        if(p->data<=q->data){
            r->next=p;
            p=p->next;
            r=r->next;
        }
        else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    if(p==NULL)
        r->next = q;
    if(q==NULL)
        r->next = p;
    return C;
}

//打印单链表
void print_link(LNode *L){
    while(L->next){
        L = L->next;
        printf("%3d",L->data);
    }
    printf("\n");
}

int main()
{
    LNode *A,*B,*C;
    int i;
    LNode* LOCAL;
    int data1[5]={9,7,5,3,1};
    int data2[7]={2,4,6,8,10,12,14};
    A = create_link_head(A,data1,5);
    B = create_link_tail(B,data2,7);
    print_link(A);
    print_link(B);

    i = get_length(A);
    printf("\nA的长度为:%d\n\n",i);

    LOCAL = get_first_elem_node(A,3);
    printf("A的第一次出现元素3的指针为：%d\n",LOCAL);
    printf("验证LOCAL的data为：%d\n\n",LOCAL->data);

    LOCAL = NULL;
    LOCAL = get_node(A,2);
    printf("A的第2位的指针为：%d\n",LOCAL);
    printf("验证LOCAL的data为：%d\n\n",LOCAL->data);

    //在指定的节点后插入节点
    insert_elem(B,2,5);
    print_link(B);
    printf("\n");
    //删除节点
    LOCAL = NULL;
    LOCAL= delete_node(B,3);
    print_link(B);
    printf("验证被删除的LOCAL->data为：%d\n\n",LOCAL->data);
    //合并两个单链表
    C=merge_link(A,B,C);
    print_link(C);
    printf("\n");

    return 0;
}

tips:

在函数中创建的节点要传出才能使用噢

相关文章
-------　本文结束　　感谢您的阅读　-------