C++数据结构---单链表_c++单链表

C++数据结构—单链表

基础知识

单链表是线性表的一种，是指用链式存储结构表示线性关系，使逻辑上相邻的元素在结构上也相邻。
线性关系是指除了首元元素和尾元元素，任何结点都只有一个一个前驱和一个后继，首元没有前驱尾元没有后继。
链式存储结构不同与顺序存储结构其存储空间不是一片连续的存储单元，每个空间除了存储数据信息，还要存储数据的逻辑关系。所以用一个结点来表示，每个结点包含数据域和指针域，数据域用于存储元素本身，指针域定义了一个指针，用于指向元素的下一个结点（指向后继），从而形成链式结构。
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。

首元结点是指链表中存储第一个数据元素a1 的结点。如图 2.8 或图 2.9所示的
结点"ZHAO" 。
头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的喊＇ 数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当骼赐 数据元素为整数型时，头结点的数据域中可存放该线性表的长度。
头指针 是指向链表中第一个结点的指针 。若链表设有头结点，则头指针所
指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首
元结点。

链表的操作：初始化、取值、查找、插入、删除、创建
链表在c++中可以直接调用STL里封装号的头文件list

#include<list>
1

C++自己定义实现单链表

1. List.h

#pragma once
#ifndef LIST
#define LIST

//定义结点
struct Node
{
	int data;
	Node *next;
};
/*定义结点也可使用
class IntSLLNode {
public:
	
	IntSLLNode() {
		next = 0;
	}
	IntSLLNode(int el, IntSLLNode *ptr = 0) {
		info = el;
		next = ptr;	
	}
	int info;
	IntSLLNode *next;
};*/


class List {
public:
	List() {
		head = new Node;
		head->data = 0;
		head->next = NULL;
		Length = 0;
	}//构造函数，初始化头结点
	~List();//析构函数
	void ClearList();//清空链表
	bool isEmpty();//判断是否为空
	int lengTh();//链表长度，可以存放在头指针
	int GetElem(int i);//获取第i个结点的元素
	void insertList(int i,int el);//在第i个结点插入el
	int deleteNode(int i);//删除第i个结点
	void addToHead(int n); //初始时从头给链表插入n个元素
	void addToTail(int n);//初始时从尾部给链表插入n个元素
	void printList();//遍历列表
	
	
private:
	Node* head;
	int Length;
	
};
#endif // !LIST

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

2.intList.cpp

# include<iostream>

#include"list.h"

using namespace std;

//析构函数
List::~List() {
	ClearList();
	delete head;
	head = NULL;
}
//清空列表，删除头结点以后的元素
void List::ClearList() {
	while(head->next!=NULL)
		deleteNode(1);
	Length = 0;
}
bool List::isEmpty() {
	if (Length == 0)
		return true;
	else
		return false;

}
int List::lengTh() {
	return Length;
}

int List::GetElem(int i) {
	Node* p;
	int j = 1;
	p = head->next;
	if (i<0 || i>Length)
		return false;
	for (j; j < i; j++) 
		p = p->next;
	return p->data;
}

void List::insertList(int i,int el) {
	
	int j = 1;
	if (i<0 || i>Length+1)
		cout << "插入失败";
	if (i == 1)
	{
		Node* p;
		p = new Node;
		p->data = el;
		p->next = head->next;
		head->next = p;
		Length += 1;
	}
	else if (i == Length + 1) {
		Node* m;
		Node* n;
		n = head->next;
		m = new Node;
		m->data = el;
		for (j; j < Length; j++)
			n = n->next;
		n->next = m;
		m->next = NULL;
		Length += 1;
	}
	else {
		Node *p;
		p = head->next;
		for (j; j < i - 1; j++) {
			p = p->next;
		}
		Node* s;
		s = new Node;
		s->data = el;
		s->next = p->next;
		p->next = s;
		Length += 1;
	}
	
}

int List::deleteNode(int i) {
	int j = 1;
	int el=0;
	if (i<0 || i>Length)
		cout << "不存在点";

	else if (i == 1) {
		Node* p;
		p = head->next;
		el = p->data;
		head->next = p->next;
		delete p;
		Length -= 1;
	}
	else if (i == Length) {
		Node* m;
		Node* n;
		n = head->next;
		for (j; j < Length-1; j++)
			n = n->next;
		m= n->next;
		n->next = NULL;
		el = m->data;
		delete m;
		Length -= 1;
	}
	else {
		Node* q;
		q = head->next;
		
		for (j; j < i - 1; j++) {
			q = q->next;
		}//p指向i-1
		Node* s;
		s = q->next;
		el = s->data;
		q->next = s->next;
		delete s;
		Length -= 1;
	}
	
	return el;
}
void List::addToHead(int n) {
	for (int i = 0; i < n; i++) {
		Node* p;
		p = new Node;
		cin >> p->data;
		p->next = head->next;
		head->next = p;
		Length += 1;
	}
}

void List::addToTail(int n) {
	Node* p;
	Node* r;//尾指针
	r = head;
	for (int i = 0; i < n; i++) {
		p = new Node;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
		Length += 1;
	}
}
void List::printList()
{
	Node* p;
	p = head->next;
	cout << "遍历结果\n";
	while (p!= NULL) {
		cout << p->data << endl;
		p = p->next;
	}
}
int main()
{
	List al;
	al.addToTail(5);
	al.printList();
	cout << "链表长度：" << al.lengTh() << endl;
	int a=1, b=3;
	al.insertList(a,b);
	al.printList();
	cout << "链表长度：" << al.lengTh() << endl;
	al.deleteNode(3);
	al.printList();
	cout << "链表长度：" << al.lengTh() << endl;
	int m, n;// m代表位置，n代表值
	cin >> m;
	cout <<"m位置的值为:"<< al.GetElem(m)<<endl;
	al.ClearList();
	al.printList();
	cout << "链表长度：" << al.lengTh() << endl;

}


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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182