单链表

发表于 | 分类于 | | 浏览 次
字数统计: 1,657 字 | 阅读时长 ≈ 9 分钟

前一篇文章《线性表及其实现》介绍了线性表的顺序存储实现和链式存储实现。本文继续介绍线性表，主要介绍线性表的链式存储结构之一的单链表。
主要包含如下内容:

  • 单链表
  • 单链表的C语言实现
  • 练习题：两个有序链表序列的合并

单链表

前一篇文章《线性表及其实现》里面介绍的线性表的链式存储实现，采用的其实不带头结点的单链表。需要注意带头结点的链表和不带头结点的单链表之间的一些区别。
可以通过本文的练习题目来体会二者区别。
（提示：该题目中的链表是带头结点的）

单链表的C语言实现

不带头结点的单链表实现参考《线性表及其实现》

带头结点的具体实现github：

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int ElemType;
typedef struct NodeList
{
    int element;
    struct NodeList *next;
}Node;


//初始化带头结点的单链表 

void InitList(Node **pNode)
{
    *pNode = (Node *)malloc(sizeof(Node));
    if(NULL == *pNode)
    {
        printf("%s executed, malloc failed, failed to init List.\n", __FUNCTION__);
        return;
    }

    (*pNode)->next = NULL;
    printf("%s executed succesfully, init List finished.\n", __FUNCTION__);
    return;
}


void CreateList(Node *pNode)
{
    //Node *p = (Node *)malloc(sizeof(Node));//notice if malloc is success
    //p->next = NULL;
    Node *tmp = pNode;

    int n;
    scanf("%d", &n);
    if(n > 0)
    {
        for(int i=0; i<n; i++)
        {
            Node *newNode = (Node *)malloc(sizeof(Node));
            newNode->next = NULL;
            scanf("%d", &(newNode->element));
            tmp->next = newNode;
            tmp = tmp->next;
        }
    }
    return;
}

void PrintList(Node *pNode)
{
    Node *p = pNode->next;
    while(p)
    {
        printf("%d ", p->element);
        p = p->next;
    }

    printf("\n Function %s executed, print list successfully.\n", __FUNCTION__);
    return;
}


void ClearList(Node *pNode)
{
    Node *p = pNode->next;
    while(p)
    {
        pNode->next = p->next;
        free(p);
        p = pNode->next;
    }

    printf("Function %s executed, clear list successfully.\n", __FUNCTION__);
    return;
}

int SizeList(Node *pNode)
{
    int i = 0;
    Node *p = pNode->next;
    while(p)
    {
        i++;
        p = p->next;
    }

    printf("Function %s executed, list size is %d.\n", __FUNCTION__, i);
    return i;
}

//返回单链表中第pos个结点中的元素，若返回-1，表示没有找到
int FindElement(Node *pNode, int pos)
{
    int i = 1;
    Node *p = pNode->next;
    while(p)
    {
        if(pos == i)
        {
            printf("Funtion %s executed，the value in pos=%d is %d\n", __FUNCTION__, pos, p->element);
            return p->element;
        }

        i++;
        p = p->next;
    }

    printf("Funtion %s executed，the value in pos=%d is not found.\n", __FUNCTION__, pos);
    return -1;
}


Node *ModifyElem(Node *pNode, int pos, int x)
{
    int i = 1;
    Node *p = pNode->next;
    while(p)
    {
        if(pos == i)
        {
            p->element = x;
            printf("Function %s executed, now the value pos=%d is %d.\n", __FUNCTION__, pos, x);
            return pNode;
        }
        i++;
        p = p->next;
    }

    printf("Function %s executed failed, maybe the list is NULL or the pos is invalid.\n", __FUNCTION__);

    return pNode;
}

//表头插入一个节点
Node *InsertHead(Node *pNode, int x)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->element = x;
    p->next = pNode->next;
    pNode->next = p;

    printf("Function %s executed, insert %d in head successfully.\n", __FUNCTION__, x);
    return pNode;
}

//表尾插入一个节点
Node *InsertTail(Node *pNode, int x)
{
    Node *p = pNode->next;
    Node *pInsert = (Node *)malloc(sizeof(Node));
    pInsert->element = x;
    pInsert->next = NULL;

    while(p->next != NULL) //思考这里为啥不是p != NULL
    {
        p = p->next;
    }

    p->next = pInsert;
    printf("Function %s executed, insert %d in tail successfully.\n", __FUNCTION__, x);

    return pNode;
}


int main(void)
{
    Node *pList;
    InitList(&pList);

    CreateList(pList);

    PrintList(pList);

    SizeList(pList);

    FindElement(pList, 3);

    ModifyElem(pList, 2, 11);

    PrintList(pList);

    InsertHead(pList, 2333);
    PrintList(pList);
    SizeList(pList);

    InsertTail(pList, 8888);
    PrintList(pList);
    SizeList(pList);

    ClearList(pList);
    PrintList(pList);

    return 0;
}

两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：

List Merge( List L1, List L2 );

其中List结构定义如下：

1
2
3
4
5
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};

typedef PtrToNode List; / 定义单链表类型 /

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的链表头指针。

裁判测试程序样例：

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
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

3
1 3 5
5
2 4 6 8 10

输出样例：

1 2 3 4 5 6 8 10
NULL
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
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
#include <stdio.h>
#include <stdlib.h>


typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node
{
    ElementType Data;
    PtrToNode Next;
};

typedef PtrToNode List;

List Read();
void Print(List);

List Merge(List L1, List L2);


int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);

    return 0;
}


List Read()
{
    List p = (List)malloc(sizeof(struct Node));
    p->Next = NULL;
    List tmp = p;

    int n;
    scanf("%d", &n);
    if(n > 0)
    {
        for(int i=0; i<n; i++)
        {
            List new_node = (List)malloc(sizeof(struct Node));
            new_node->Next = NULL;
            scanf("%d", &(new_node->Data));
            tmp->Next = new_node;
            tmp = tmp->Next;
        }
    }

    return p;
}

void Print(List L)
{
    List p = L->Next;
    if(p)
    {
        while(p)
        {
            printf("%d ", p->Data);
            p = p->Next;
        }
    }
    else
    {
        printf("NULL");
    }

    printf("\n");
    return;
}

List Merge(List L1, List L2)
{
    List p1 = L1->Next;
    List p2 = L2->Next;
    List p = (List)malloc(sizeof(struct Node));
    p->Next = NULL;
    List tmp = p;

    while(p1 && p2)
    {
        if(p1->Data < p2->Data)
        {
            tmp->Next = p1;
            tmp = tmp->Next;
            p1 = p1->Next;
        }
        else
        {
            tmp->Next = p2;
            tmp = tmp->Next;
            p2 = p2->Next;
        }
    }

    while(p1)
    {
        tmp->Next = p1;
        tmp = tmp->Next;
        p1 = p1->Next;
    }

    while(p2)
    {
        tmp->Next = p2;
        tmp = tmp->Next;
        p2 = p2->Next;
    }

    tmp->Next = NULL;
    L1->Next = NULL;
    L2->Next =NULL;

    return p;
}

参考资料

[浙江大学PTA]

[浙江大学数据结构公开课]

C语言实现单链表（带头结点）的基本操作

如果你觉得本文对你有帮助，欢迎打赏