再识数据结构之单链表

单链表的概念

单链表(singly linked list)是一种最简单的链表表示,也叫作线性链表,它用来表示线性表时,用指针表示节点之间的
逻辑关系。因此,单链表一个存储节点包含两个部分(域,field)

节点图示

其中data部分表示数据域,用于表示线性表一个节点的数据元素。link表示指针域,用于存放一个指针,该指针指示链表中
下一个节点的开始存储地址

存储示意图

单链表的特点是:可以无限扩充,线性表中数据元素的顺序与其在链表中的表示的物理顺序可能不会一致

单链表基本操作示例

  1. main.cpp
1
2
3
4
5
6
7
#include "singly_linked_list.h"

int main()
{
run();
return 0;
}
  1. singly_linked_list.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
    //
    // Created by Gamelife on 2017/3/29.
    //

    #ifndef DATA_STRUCT_SINGLY_LINKED_LIST_H
    #define DATA_STRUCT_SINGLY_LINKED_LIST_H

    struct link_list {
    int data;
    link_list * p;
    };

    // initialize singly link list
    link_list * init_link(int num = 10);

    // print link
    void print_link(const link_list *);

    // insert
    bool insert_ele(link_list * &, int data = 99, int pos = 0);

    // delete
    bool delete_ele(link_list * &, int position = 1);

    // module starter
    void run();

    #endif //DATA_STRUCT_SINGLY_LINKED_LIST_H
  2. singly_linked_list.cpp

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
// singly linked list
#include <iostream>

#include "singly_linked_list.h"

using namespace std;

link_list * init_link(int num)
{
link_list * first = NULL, * move_p = NULL;
for (int i = 0; i < num; i++) {
link_list * current = new link_list;
if (current != NULL) {
current->p = NULL;
current->data = i;
if (i == 0) {
first = move_p = current;
} else {
move_p->p = current;
move_p = current;
}
}
}
return first;
}

void print_link(const link_list * head)
{
const link_list * current = head;
while (current != NULL) {
cout << current->data << endl;
current = current->p;
}
}

bool insert_ele(link_list * &head, int data, int pos)
{
bool insert_result = true;
link_list * new_ele = new link_list;
new_ele->data = data;
new_ele->p = NULL;

if (head == NULL || pos == 0) {
new_ele->p = head;
head = new_ele;
} else {
link_list * current = head;
for(int k = 1; k < pos; k++) {
if(current == NULL) break;
else current = current->p;
}
if (current == NULL && head != NULL) {
cout << "无效的插入位置";
return false;
} else {
new_ele->p = current->p;
current->p = new_ele;
}
}
return insert_result;
}

bool delete_ele(link_list * &head, int pos)
{
link_list * del, * current;
if (pos <= 1) {
del = head;
head = head->p;
} else {
current = head;
for(int k = 1; k < pos; k++) {
if (current == NULL) break;
else current = current->p;
}
if (current == NULL || current->p == NULL) {
cerr << "无效的删除位置" << endl;
}
del = current->p;
current->p = del->p;
}
cout << "删除:" << del->data << endl;
delete del;
return true;
}

void run()
{
link_list * head = init_link();
print_link(head);
insert_ele(head);
print_link(head);
delete_ele(head, 3);
print_link(head);
}

编译运行

g++ main.cpp singly_linked_list.cpp -o main.out