C++单链表-不带头节点

LinkList.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
29
30
31
32
33
34
#pragma once
#include<iostream>
using namespace std;
#include<string>
#include <fstream>

struct Node
{
int data;
Node* next;
};

class LinkList
{
private:
Node* head;
public:
LinkList();
LinkList(string fname);// 通过文件初始化链表,尾插法,传入文件路径
LinkList(int array[],int n);
void ShowAll();
void HeadAfterInert(int e);
Node* SearchNode(int e);


void InsertAfterNode(Node *node,int e); // 指定结点后插入数据
void RemoveNode(Node *node);
void RemoveAfterNode(Node* node);// 删除指定节点的后继节点
void RemoveHeadAfterNode(); // 删除头指针后的第一个节点

void SearchRemove(int e);// 查找删除

};

LinkList.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
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
#include "LinkList.h"

LinkList::LinkList()
{
// 表示空链表
head = NULL; // 这里的head表示 头指针; 而不是 头结点指针 ( 不带头结点 )
}
LinkList::LinkList(string fname)
{
head = NULL;
ifstream fin(fname);
int n;
fin >> n;
Node* tail = NULL;
for (int i = 0; i < n; i++)
{
int data;
fin >> data;

Node* p = new Node();
p->data = data;
p->next = NULL;

if (head == NULL)
head = p;
else
tail->next = p;
tail = p;
}

fin.close();
}
LinkList::LinkList(int array[],int n)
{
head = NULL;
for (int i = 0; i < n; i++)
{
HeadAfterInert(array[i]);
}
}

void LinkList::ShowAll()
{
Node* p = head;
while (p!=NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}

// 在链表头进行后插操作
void LinkList::HeadAfterInert(int e)
{
Node* p = new Node();
p->data = e;
if (head == NULL) // 不带头结点的单链表,如果当前链表为空,则需要特殊关注
{
p->next = NULL;
head = p;
return;
}

p->next = head;
head = p;
}

Node* LinkList::SearchNode(int e)
{
Node* p = head;
while (p != NULL)
{
if (p->data == e)
return p;
p = p->next;
}
return NULL;
}

// 删除指定结点的后继结点
void LinkList::RemoveAfterNode(Node* node)
{
Node* p = node;
if (p->next != NULL)
{
Node* d = p->next;
p->next = d->next;
delete(d);
}
}

// 删除 头指针后 的第一个节点
void LinkList::RemoveHeadAfterNode()
{
Node* p = head->next;
head->next = p->next;
delete(p);
}

// 指定节点后插入
void LinkList::InsertAfterNode(Node* node, int e)
{
Node* p = new Node();
p->data = e;
p->next = node->next;
node->next = p;
}

// 删除指定结点
void LinkList::RemoveNode(Node *node)
{
Node* prev = NULL, * p = head;

if (p == NULL)
return;

while (p!=NULL)
{
if (p == node)
break;
prev = p; // 每次prev记录的是上一个结点
p = p->next;
}
if (prev != NULL)
prev->next = p->next;
else
head = p->next; // 如果prev为NULL,则第一个结点就是需要删除的结点
delete(p);
}

// 查找删除
void LinkList::SearchRemove(int e)
{
Node * p = SearchNode(e);
RemoveNode(p);
}

main.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
#include<iostream>
using namespace std;
#include"LinkList.h"

int main()
{
//int array[] = { 1,2,3,4,5,6,7,8,9,10 };
//int n = 10;
LinkList L("data.txt");
L.ShowAll();

Node *p = L.SearchNode(9); // 按值查找结点
cout << p->data << endl;

L.RemoveAfterNode(p);// 删除该结点的后继结点,存在的情况下
L.ShowAll();


L.RemoveNode(p);
L.ShowAll();

p = L.SearchNode(4);
L.InsertAfterNode(p, 200); // 在指定结点后插入数据
L.ShowAll();

L.SearchRemove(200);
L.ShowAll();
cout << "***********************" << endl;


return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!