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
#pragma once
#include<iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};

class LinkList
{
private:
Node* head;
public:
LinkList();
LinkList(int array[],int n);
void ShowAll();
void HeadAfterInert(int e);
Node* SearchNode(int e);

void InsertAfterNode(Node *node,int e); // 指定结点后插入数据

void RemoveAfterNode(Node* node);// 删除指定节点的后继节点
void RemoveNode(Node* node);// 删除指定节点
void RemoveHeadAfterNode(); // 删除头节点后的第一个节点

// 求两个链表的交集
LinkList Intersection( LinkList hb);
};

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

// 初始化一个头节点,该节点不用于存储数据
LinkList::LinkList()
{
head = new Node();
head->next = NULL;
}
LinkList::LinkList(int array[],int n)
{
head = new Node();
head->next = NULL;
for (int i = 0; i < n; i++)
{
HeadAfterInert(array[i]);
}
}

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

// 在头节点后插入
void LinkList::HeadAfterInert(int e)
{
Node* p = new Node();
p->data = e;
p->next = head->next;
head->next = p;
}

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

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

// 删除指定结点
void LinkList::RemoveNode(Node *node)
{
if (node == NULL)
return;
Node* p = head;
while (p->next!=NULL)
{
if (p->next == node)
{
RemoveAfterNode(p);// 此时p结点为 待 删除节点的前驱结点
break;
}
p = p->next;
}
}

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

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


LinkList LinkList::Intersection(LinkList hb)
{
LinkList link;

Node* p = head->next;

while (p!=NULL)
{
Node* temp = hb.head->next;
while (temp!=NULL)
{
if (p->data == temp->data)
link.HeadAfterInert(p->data);
temp = temp->next;
}
p = p->next;
}
return link;

}

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
33
34
35
36
37
38
39
#include<iostream>
using namespace std;
#include"LinkList.h"


int main()
{
int n = 4;
int arrayHa[] = { 1,4,5,8 };
int arrayHb[] = { 2,4,5,7 };

LinkList ha(arrayHa, n);
LinkList hb(arrayHb, n);

LinkList L = ha.Intersection(hb);

L.ShowAll();

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

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

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



//L.RemoveNode(p);// 删除指定结点
//L.ShowAll();

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

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