单链表——单链表的定义及基本操作（初始化、头插法尾插法建表、查找、插入、删除、判空等）_带头结点的单链表的元素的创建、查找、插入、删除等基本操作

---

单链表的定义

  由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

  单链表的特点：

1. 单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。
2. 单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

 对于每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。
 单链表中结点类型的描述：

typedef struct LNode{ //定义单链表结点类型
	int data; //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next; //指针域
}LNode, *LinkList;
1
2
3
4

---

单链表上的操作

初始化

 通常会用头指针来标识一个单链表，头指针为NULL时表示一个空表。但是，为了操作方便，会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。如下图所示：

 头结点和头指针的区分：不管带不带头结点，头指针始终指向单链表的第一个结点，而头结点是带头结点的单链表中的第一个结点，结点内通常不存储信息。
 那么单链表的初始化操作就是申请一个头结点，将指针域置空。

void InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LinkList));
    L->next = NULL;
}
1
2
3
4

---

建立单链表

头插法建立单链表

 所谓头插法建立单链表是说将新结点插入到当前链表的表头，即头结点之后。如图所示：

 算法思想：首先初始化一个单链表，其头结点为空，然后循环插入新结点*s：将s的next指向头结点的下一个结点，然后将头结点的next指向s。

 实现代码：

//头插法建立单链表
LinkList HeadInsert(LinkList &L){
    InitList(L); //初始化
    int x;
    cin>>x;
    while(x!=9999){ //输入9999表示结束
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin>>x;
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 需要指出的是，头插法建立的单链表中结点的次序和输入数据的顺序不一致，是相反的。若希望两者的顺序是一致的，则可采用尾插法建立单链表。

尾插法建立单链表

 所谓尾插法建立单链表，就是将新结点插入到当前链表的表尾。如下图所示：

  算法思想：首先初始化一个单链表，然后声明一个尾指针r，让r始终指向当前链表的尾结点，循环向单链表的尾部插入新的结点*s，将尾指针r的next域指向新结点，再修改尾指针r指向新结点，也就是当前链表的尾结点。最后别忘记将尾结点的指针域置空。

 实现代码：

//尾插法建立单链表
LinkList TailInsert(LinkList &L){
    InitList(L);
    LNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999){
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        cin>>x;
    }
    r->next = NULL;
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

遍历单链表

 算法思想：声明一个指针p，从头结点指向的第一个结点开始，如果p不为空，那么就输出当前结点的值，并将p指向下一个结点，直到遍历到最后一个结点为止。

 实现代码：

//遍历操作
void PrintList(LinkList L){
    LNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}
1
2
3
4
5
6
7
8
9

---

求单链表的长度

 算法思想：声明一个指针p，p指向头结点指向的第一个结点，如果p指向的结点不为空，那么长度加一，将p指向下一个结点，直到遍历到最后一个结点为止。

 实现代码：

//求单链表的长度
int Length(LinkList L){
    LNode *p = L->next;
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}
1
2
3
4
5
6
7
8
9
10

---

查找操作

按值查找

 查找值x在单链表L中的结点指针。

 算法思想：从单链表的第一个结点开始，依次比较表中各个结点的数据域的值，若某结点数据域的值等于x，则返回该结点的指针；若整个单链表中没有这样的结点，则返回空。

 实现代码：

//按值查找：查找x在L中的位置
LNode *LocateElem(LinkList L, int x){
    LNode *p = L->next;
    while(p && p->data != x){
        p = p->next;
    }
    return p;
}
1
2
3
4
5
6
7
8

按位查找

 查找单链表L中第 i 个位置的结点指针。

 算法思想：从单链表的第一个结点开始，顺着指针域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点的指针域NULL。

 实现代码：

//按位查找：查找在单链表L中第i个位置的结点
LNode *GetElem(LinkList L, int i){
    int j=1;
    LNode *p = L->next;
    if(i==0)return L;
    if(i<1)return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}
1
2
3
4
5
6
7
8
9
10
11
12

---

插入操作

 这里所说的插入是将值为x的新结点插入到单链表L的第i个位置上。（不包括头结点）

 算法思想：从表头开始遍历，查找第 i-1个结点，即插入位置的前驱结点为p，然后令新结点s的指针域指向p的后继结点，再令结点p的指针域指向新结点*s。

 实现代码：

//将x插入到单链表L的第i个位置上
void Insert(LinkList &L, int i, int x){
    LNode *p = GetElem(L,i-1);
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
}
1
2
3
4
5
6
7
8

---

删除操作

 将单链表的第 i 个结点删除。

 算法思想：先检查删除位置的合法性，然后从头开始遍历，找到表中的第 i-1 个结点，即被删除结点的前驱结点*p，被删除结点为*q，修改*p的指针域，将其指向*q的下一个结点，最后再释放结点*q的存储空间。

 实现代码：

//删除操作:将单链表中的第i个结点删除
void Delete(LinkList &L, int i){
    if(i<1 || i>Length(L))
        cout<<"delete failed: index is wrong."<<endl;
        return;
    LNode *p = GetElem(L,i-1);
    LNode *q = p->next;
    p->next = q->next;
    free(q);
}
1
2
3
4
5
6
7
8
9
10

---

判空操作

 算法思想：要判断带头结点的单链表是否为空，只需要看头结点的指针域即可，如果头结点的指针域为空，即单链表中只有一个头结点，那么该单链表为空表。

 实现代码：

//判空操作
bool Empty(LinkList L){
    if(L->next == NULL){
        cout<<"L is null"<<endl;
        return true;
    }else{
        cout<<"L is not null"<<endl;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10

---

完整代码及实例

 完整代码：

#include<bits/stdc++.h>
using namespace std;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

//初始化
void InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LinkList));
    L->next = NULL;
}

//遍历操作
void PrintList(LinkList L){
    LNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

//求单链表的长度
int Length(LinkList L){
    LNode *p = L->next;
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}

//头插法建立单链表
LinkList HeadInsert(LinkList &L){
    InitList(L); //初始化
    int x;
    cin>>x;
    while(x!=9999){
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin>>x;
    }
    return L;
}

//尾插法建立单链表
LinkList TailInsert(LinkList &L){
    InitList(L);
    LNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999){
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        cin>>x;
    }
    r->next = NULL;
    return L;
}

//按值查找：查找x在L中的位置
LNode *LocateElem(LinkList L, int x){
    LNode *p = L->next;
    while(p && p->data != x){
        p = p->next;
    }
    return p;
}

//按位查找：查找在单链表L中第i个位置的结点
LNode *GetElem(LinkList L, int i){
    int j=1;
    LNode *p = L->next;
    if(i==0)return L;
    if(i<1)return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}

//将x插入到单链表L的第i个位置上
void Insert(LinkList &L, int i, int x){
    LNode *p = GetElem(L,i-1);
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
}

//删除操作:将单链表中的第i个结点删除
void Delete(LinkList &L, int i){
    if(i<1 || i>Length(L)){
        cout<<"delete failed: index is wrong."<<endl;
        return;
    }
    LNode *p = GetElem(L,i-1);
    LNode *q = p->next;
    p->next = q->next;
    free(q);
}


int main(){
    //初始化，尾插法建立单链表
    LinkList L = TailInsert(L);
    //插入：在第二个位置插入结点，数据域为888，并遍历单链表
    Insert(L,2,888);
    cout<<"在第二个位置插入888： ";
    PrintList(L);
    //删除：删除第四个结点
    Delete(L,4);
    cout<<"删除第四个结点后：";
    PrintList(L);
    //按位查找：查找第三个结点，并输出其数据域的值
    LNode *p = GetElem(L,3);
    cout<<"第三个结点的值为："<<p->data<<endl;
    //按值查找：查找数据域为2的结点的指针
    LNode *q = LocateElem(L,2);
    cout<<"数据为2的结点的下一个结点的值为："<<q->next->data<<endl;
    //输出单链表的长度
    cout<<"单链表的长度："<<Length(L)<<endl;
    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

 执行结果：