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
#pragma once
#include<iostream>
using namespace std;

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

class LinkList
{
private:
Node* head;
public:
LinkList();
LinkList(int array[],int n);
void InsertAfterHead(int e);
void ShowAll();
Node* SearchNode(int e); // 按值查找,返回结点
void InsertAfterNode(Node *node,int e); // 在指定结点后进行后插操作
void InsertBeforeNode(Node* node, 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
#include "LinkList.h"

LinkList::LinkList()
{
head = new Node(); // 创建一个头结点,不用来存储使用
}

LinkList::LinkList(int array[], int n)
{
head = new Node();
for (int i = 0; i < n; i++)
InsertAfterHead(array[i]);
}



// 头结点之后插入
void LinkList::InsertAfterHead(int e)
{

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

if (head->next != NULL) // 如果为空,表示此时为 空 双链表
head->next->front = p;


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

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

// 按值查找,返回结点
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::InsertAfterNode(Node* node, int e)
{
Node* p = new Node();
p->data = e;
p->next = node->next;
if (node->next != NULL) // 如果node->next为NULL,表示node结点为最后一个结点
node->next->front = p;

p->front = node;
node->next = p;
}


// 在指定结点前进行 前插操作
void LinkList::InsertBeforeNode(Node* node, int e)
{
Node* p = new Node();
p->data = e;
p->front = node->front;

node->front->next = p;

p->next = node;
node->front = 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
#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(array, n);
L.ShowAll();

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


p = L.SearchNode(4);
L.InsertAfterNode(p, 100); // 在中间节点后插操作
L.InsertBeforeNode(p, 200); // 在中间节点前插操作
L.ShowAll();

p = L.SearchNode(1);
L.InsertAfterNode(p, 300);// 在最后一个节点进行后插操作
L.ShowAll();

p = L.SearchNode(10);// 在第一个节点进行前插操作
L.InsertBeforeNode(p, 400);
L.ShowAll();

return 0;
}

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