C++实现单链表的各种操作（数据结构）

链表又可以分为：单链表，双链表，循环链表和静态链表。

单链表的定义：线性表的链式存储又叫单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素。

---

头指针：把链表中第一个结点的存储位置叫做头指针。
头结点：在单链表的第一个结点前附设一个结点，称为头结点。
尾指针：尾指针是相对于头指针而言的，形式与头指针相同，内容指向链表的最后一个节点。

头指针与头结点的异同：

头指针

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
• 头指针具有标志作用，所以常用头指针冠以链表的名字。
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入和删除第一结点，其操作与其他结点的操作就统一了。
  头结点不一定是链表的必要元素。

C++实现如下：

/**
 * 单链表：带头节点(大多数情况下创建链表都是用这种方式)
 */

#include 
#include 

using namespace std;


/**
 * LNode是一个结构体类型，指向的是包含某个数据类型的数据域和指针域的结构体类型。
 * 
 * 而LinkList是LNode的指针类型，它占用一定内存空间，内存空间中的值是一个LNode类型结构体的地址。
 * 
 * 用typedef将结构体等价于类型名LNode，将结构体指针等价于LinkList
 */
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;


/**
 * 初始化单链表(带头结点)
 */
bool InitList(LinkList &L) {
    // 给头节点申请一块空间(数据域不存数据)，并将指针L指向头节点
    // 注意：这里的 L 是LinkList类型，分配内存的时候是 LNode 类型，
    // malloc()函数返回值是 void(*) 类型，所以要强转为LinkList
    L = (LinkList)malloc(sizeof(LNode));// 将L指向第一个结点(头结点)
    if(L == NULL) {
        return false;// 内存不足,分配失败
    }
    L->next = NULL;// 头节点之后暂时还没有节点
    return true;
}

/**
 * 判断单链表是否为空
 * @return true--链表为空; false--链表不为空
 */
bool Empty(LinkList L) {
    if(L->next == NULL) {
        return true;
    }
    return false;
}


/**
 * 按位置插入(带头结点)
 * 描述：先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新节点。
 * @param L: 头指针，永远指向头结点
 */
bool ListInsert(LinkList &L, int i, int e) {

    if(i < 1) return false; // 位置不合法

    // 找到i-1位置的结点
    LNode *p = L;
    int j = 0;
    while(p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if(p == NULL) return false; // i-1位置的结点为空，说明i不合法

    // 插入元素
    LNode *temp = (LNode *)malloc(sizeof(LNode));
    if(temp == NULL) return false;// 内存分配失败
    temp->data = e;
    temp->next = p->next;
    p->next = temp;

    return true;

}

/**
 * 按序号查找结点值
 * LNode * :强调返回的是一个结点
 * @param i: 链表序号
 */
LNode *GetElemByIndex(LinkList L, int i) {
    int j = 1; // 计数，初始为1
    LNode *p = L->next; // p指针指向第一个结点
    if(i == 0) return L; // 返回头节点 
    if(i < 1) return NULL;
    while(p && j < i) {
        p = p->next;
        j++;
    }
    return p; // 返回第i个结点的指针，若i大于表长，则会返回NULL
}

/**
 * 按值查找表结点
 * @param target: 目标值
 */
LNode * GetElemByVal(LinkList L, int target) {
    LNode *p = L->next; // p指针指向第一个结点
    while(p != NULL && p->data != target) {
        p = p->next;
    }
    return p; // 没找到则返回NULL，找到返回该结点
}

/**
 * 删除结点操作
 * 描述：先检查删除位置的合法性，然后查找表中第i-1个结点，即被删除结点的前驱结点，再将其删除。
 */
bool ListDel(LinkList &L, int i) {
    // 1.判断i的合法性
    if(i < 1) return false;

    int j = 0;
    LNode *p = L; // p指针指向头结点
    // 2.找到位置i-1的结点
    while(p!=NULL && j < i-1) {
        p = p->next;
        j++;
    }
    LNode *q = p->next; // 令q指针指向被删除的指针
    p->next = q->next;
    free(q); // 释放结点的存储空间
	return true;
}

/**
 * 求单链表的长度(带头结点)
 */
int GetLength(LinkList L) {
    int i = 0;
    LNode *cur = L; // 指向头结点
    while(cur->next != NULL) {
        i++;
        cur = cur->next;
    }
    return i;// 如果是空表，则会直接返回0
}

/**
 * 输出链表
 */
void PrintList(LinkList L) {
    if(L->next == NULL) {
        cout << "此链表为空!" << endl;
        return;
    }
    LNode *cur = L;
    cur = cur->next;
    cout << "输出链表: ";
    while(cur != NULL) {
        cout << cur->data << " ";
        cur = cur->next;
    }
    cout << endl;
}

// 头插法建立单链表
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));// 创建头结点
    L->next = NULL;// 初始为空链表
    while (cin.peek() != '\n') {
    	cin >> x;
        s = (LNode *)malloc(sizeof(LNode));// 创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;
    }
    return L;
    
}

// 尾插法建立单链表
LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));// 创建头结点
    LNode *s, *r = L;// r为表尾指针
    while (cin.peek() != '\n') {
    	cin >> x;
        s = (LNode *)malloc(sizeof(LNode));// 创建新结点
        s->data = x;
        r->next = s;
        r = s;// r指向新的表尾结点
    }
    r->next = NULL;// 尾结点指针置空
    return L;
}

int main() {

    LinkList L; // 声明一个指向单链表的指针
    List_TailInsert(L); // 尾插法创建链表
    PrintList(L); // 打印链表
    cout << "单链表的长度为："<< GetLength(L) <<endl;

    LNode *p = GetElemByVal(L, 33); // 查找链表中结点值为33的结点
    if(p == NULL) cout << "未找到目标值" << endl;
    else cout << "目标值为: " << p->data << endl;

    LNode *q = GetElemByIndex(L,2); // 查找位序为2的结点
    if(q == NULL || (q->data)==NULL) cout << "位序2处的结点不存在。" << endl;
    else cout << "位序2处的结点值为: " << q->data << endl;

    if(Empty(L) == true) cout << "链表为空。" << endl;
    else cout << "链表不为空。" << endl;

    ListInsert(L, 1, 100);// 在位置1处插入值为100的结点
    PrintList(L);
    ListDel(L, 3);// 删除位置3处的结点
    PrintList(L);

    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
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