C++链表类

C++链表类的封装

1.C++

1.类与对象

对象：对象是我们生活中事物，有一定的属性和行为或者操作方式。
面向对象：是一种软件的开发方法，对象所指的是计算机操作系统中的某一个成分。在面向对象程序设计中，对象包含两个含义，其中一个是数据，另外一个是行为。
面向对象编程：C++是一种面向对象的语言，作为C语言的升级和扩充，C++完善了C语言中的不足，同时也在不断进行更新。面向对象编程的主要四线是把问题的各个部分分解成对象。面向对象程序设计中的概念主要包括：对象，类，数据抽象、继承、动态绑定、数据封装、多态性、消息传递。

2.类的定义和实例化

2.1类的一般语法：

class 类名：继承方式 基类,…{
访问控制限定符：
类名(形参表)：初始化列表{…}//构造函数
~类名（void）{…}//析构函数
返回类型 函数名（形参表）{…}//成员函数
数据类型 变量名；//成员变量
};

2.2访问控制限定符

1.public:公共的行为或属性，任何位置都可以访问使用
2.private:私有的行为或属性，只有类自己的成员函数才能访问，类的外部是不可以访问的，不写访问控制限定符，默认是私有成员
3.protected:受保护的成员，在派生类可访问
1
2
3

2.3构造函数

语法
class 类名{
        类名（形参表）{//负责初始化对象（初始化成员变量）}
}；
函数名字与类名相同，且无返回类型
构造函数在创建时自动被调用，不能像普通成员函数一样显式的调用
1
2
3
4
5
6

2.4对象的创建和销毁

1.在栈区创建单个对象：
类名 对象（构造实参表）；//无实参的话不需要加括号
如果只有一个构造实参也可以：类名 对象=构造实参；
类名 对象=类名（构造实参表）；//拷贝初始化
2.在栈区创建多个对象（对象数组）
类名 对象数组[元素个数]={类名（构造实参表），...}；
3.在堆区创建、销毁单个对象
创建：类名*对象指针=new 类名（构造实参表）
销毁：delete 对象指针
4.在堆区创建、销毁对象数组
创建：类名*对象指针=new类名[元素个数】{类名（构造实参表）}
销毁：delete[] 对象指针；
1
2
3
4
5
6
7
8
9
10
11
12

2.链表

1.定义

   链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
1

2.特点

 链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：  一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域
1

3.构成

链表节点分为两个域
     数据域：存放各种实际的数据，如：num、score等
     指针域：存放下一节点的首地址，如：next等.
1
2
3

4.操作

 基本操作包括增加，删除，修改，查询。
1

3.实现

1.创建（头插法）

void LinkList::HeadPushList(int x)
{
	if (data == 0)
	{
		LinkList* p = new LinkList(x);
		next = p;
		data++;
	}
	else
	{
		LinkList* p = new LinkList(x);
		p->next = next;
		next = p;
		data++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.插入

void LinkList::RandInsertList(int n, int x)
{
	if (n == 1)
	{
		HeadPushList(x);
	}
	else if (n > 1 && n <= data)
	{
		LinkList* p = new LinkList(x);
		LinkList* temp = next;
		int count = n - 2;
		while (count--)
		{
			temp = temp->next;
		}
		p->next = temp->next;
		temp->next = p;
		data++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.删除

int LinkList::RandDeleteList(int n)
{
	int x;
	if (data == 0)
		return NULL;
	if (n == 1)
	{
		x = HeadPopList();
	}
	else if (n == data)
	{
		x = TailPopList();
	}
	else if (n > 1 && n < data)
	{
		int cnt = n - 2;
		LinkList* p = next;
		while (cnt--)
			p = p->next;
		LinkList* p1 = p->next;
		x = p1->data;
		p->next = p1->next;
		delete p1;
		data--;
	}
	else
	{
		cout << "删除位置错误！";
		return NULL;
	}
	cout << "删除成功！" << endl;
	return x;
}
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

4.查询

int LinkList::DataSearchList(int n)
{
	if (EmptyList() || (!(n > 0 && n <= data)))
		return false;
	
	LinkList* p = next;
	int index = n - 1;
	while (index--)
		p = p->next;
	return p->data;
1
2
3
4
5
6
7
8
9
10

5.修改

bool LinkList::LocateChangeList(int n, int x)
{
	if (EmptyList()||(!(n > 0 && n <= data)))
		return false;
	int index = n - 1;
	LinkList* p = next;	
	while (index--)
		p = p->next;
	p->data = x;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

4.总结

C++中的链表操作方式跟C一样，但是在C++中更习惯将数据结构封装成类进行操作，通过成员函数对类里面的成员进行访问和操作。