前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【c++】多态&&虚函数&&抽象类&&继承中的虚函数表详解

【c++】多态&&虚函数&&抽象类&&继承中的虚函数表详解

作者头像
用户10925563
发布于 2024-06-04 06:09:47
发布于 2024-06-04 06:09:47
43300
代码可运行
举报
文章被收录于专栏:c/c++&&linuxc/c++&&linux
运行总次数:0
代码可运行

1. 多态的概念

1.1 概念

多态的概念:通俗来说,就是多种形态,具体点就是去完成某个行为,当不同的对象去完成时会产生出不同的状态

举个栗子:比如买票这个行为,当普通人买票时,是全价买票;学生买票时,是半价买票;军人买票时是优先买票

再举个栗子: 最近为了争夺在线支付市场,支付宝年底经常会做诱人的扫红包-支付-给奖励金的活动。那么大家想想为什么有人扫的红包又大又新鲜8块、10块...,而有人扫的红包都是1毛,5 毛....

其实这背后也是一个多态行为。支付宝首先会分析你的账户数据,比如你是新用户、比如你没有经常支付宝支付等等,那么你需要被鼓励使用支付宝,那么就你扫码金额 =random()%99;比如你经常使用支付宝支付或者支付宝账户中常年没钱,那么就不需要太鼓励你去使用支付宝,那么就你扫码金额 = random()%1;总结一下:同样是扫码动作,不同的用户扫得到的不一样的红包,这也是一种多态行为。ps:支付宝红包问题纯属瞎编,大家仅供娱乐

2. 多态的定义及实现

2.1 多态的构成条件

多态是在不同继承关系的类对象,去调用同一函数,产生了不同的行为。比如Student继承了Person。Person对象买票全价,Student对象买票半价。

那么在继承中要构成多态还有两个条件

  1. 必须通过基类的指针或者引用调用虚函数
  2. 被调用的函数必须是虚函数,且派生类必须对基类的虚函数进行重写

2.2 虚函数

虚函数:即被virtual修饰的类成员函数称为虚函数

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Person {
public:
	virtual void BuyTicket() { cout << "买票-全价" << endl; }
};

2.3 虚函数的重写

虚函数的重写(覆盖):派生类中有一个跟基类完全相同的虚函数(即派生类虚函数与基类虚函数的返回值类型、函数名字、参数列表完全相同),称子类的虚函数重写了基类的虚函数

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Person {
public:
	virtual void BuyTicket() { cout << "买票-全价" << endl; }
};
class Student : public Person {
public:
	virtual void BuyTicket() { cout << "买票-半价" << endl; }
	/*注意:在重写基类虚函数时,派生类的虚函数在不加virtual关键字时,虽然也可以构成重写(因
	为继承后基类的虚函数被继承下来了在派生类依旧保持虚函数属性),但是该种写法不是很规范,不建议
	这样使用*/
	/*void BuyTicket() { cout << "买票-半价" << endl; }*/
};
void Func(Person& p) 
{ p.BuyTicket(); }
int main()
{
	Person ps;
	Student st;
	Func(ps);
	Func(st);
	return 0;
}
2.3.1 虚函数重写的两个例外:
2.3.1.2 协变

(基类与派生类虚函数返回值类型不同)

派生类重写基类虚函数时,与基类虚函数返回值类型不同。即基类虚函数返回基类对象的指针或者引用,派生类虚函数返回派生类对象的指针或者引用时,称为协变。(了解)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class A {};
class B : public A {};
class Person {
public:
	virtual A* f() { return new A; }
};
class Student : public Person {
public:
	virtual B* f() { return new B; }
};
2.3.1.2 析构函数的重写

(基类与派生类析构函数的名字不同)

如果基类的析构函数为虚函数,此时派生类析构函数只要定义,无论是否加virtual关键字,都与基类的析构函数构成重写,虽然基类与派生类析构函数名字不同。虽然函数名不相同,看起来违背了重写的规则,其实不然,这里可以理解为编译器对析构函数的名称做了特殊处理,编译后析构函数的名称统一处理成destructor。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Person {
public:
	virtual ~Person() { cout << "~Person()" << endl; }
};
class Student : public Person {
public:
	virtual ~Student() { cout << "~Student()" << endl; }
};
// 只有派生类Student的析构函数重写了Person的析构函数,下面的delete对象调用析构函
//数,才能构成多态,才能保证p1和p2指向的对象正确的调用析构函数。
int main()
{
	Person* p1 = new Person;
	Person* p2 = new Student; 
	delete p1;
	delete p2;
	return 0;
}

2.4 C++11 override 和 final

从上面可以看出,C++对函数重写的要求比较严格,但是有些情况下由于疏忽,可能会导致函数名字母次序写反而无法构成重载,而这种错误在编译期间是不会报出的,只有在程序运行时没有得到预期结果才来debug会得不偿失,因此:C++11提供了override和final两个关键字,可以帮助用户检测是否重写

2.4.1 final

修饰虚函数,表示该虚函数不能再被重写

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Car
{
public:
	virtual void Drive() final {}
};
class Benz :public Car
{
public:
	virtual void Drive() { cout << "Benz-舒适" << endl; }
};
2.4.2 override

检查派生类虚函数是否重写了基类某个虚函数,如果没有重写编译报错

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Car {
public:
	virtual void Drive() {}
};
class Benz :public Car {
public:
	virtual void Drive() override { cout << "Benz-舒适" << endl; }
};

2.5 重载、覆盖(重写)、隐藏(重定义)的对比

3. 抽象类

3.1 概念

在虚函数的后面写上 =0 ,则这个函数为纯虚函数。包含纯虚函数的类叫做抽象类(也叫接口类),抽象类不能实例化出对象。派生类继承后也不能实例化出对象,只有重写纯虚函数,派生类才能实例化出对象。纯虚函数规范了派生类必须重写,另外纯虚函数更体现出了接口继承

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Car
{
public:
	virtual void Drive() = 0;
};
class Benz :public Car
{
public:
	virtual void Drive()
	{
		cout << "Benz-舒适" << endl;
	}
};
class BMW :public Car
{
public:
	virtual void Drive()
	{
		cout << "BMW-操控" << endl;
	}
};
void Test()
{
	Car* pBenz = new Benz;
	pBenz->Drive();
	Car* pBMW = new BMW;
	pBMW->Drive();
}

3.2 接口继承和实现继承

普通函数的继承是一种实现继承,派生类继承了基类函数,可以使用函数,继承的是函数的实现。虚函数的继承是一种接口继承,派生类继承的是基类虚函数的接口,目的是为了重写,达成多态,继承的是接口。所以如果不实现多态,不要把函数定义成虚函数

4. 多态的原理

4.1 虚函数表

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 这里常考一道笔试题:sizeof(Base)是多少?
class Base
{
public:
	virtual void Func1()
	{
		cout << "Func1()" << endl;
	}
private:
	int _b = 1;
};

通过观察测试我们发现b对象是8bytes,除了_b成员,还多一个__vfptr放在对象的前面(注意有些平台可能会放到对象的最后面,这个跟平台有关),对象中的这个指针我们叫做虚函数表指针(v代表virtual,f代表function)。一个含有虚函数的类中都至少都有一个虚函数表指针,因为虚函数的地址要被放到虚函数表中,虚函数表也简称虚表。那么派生类中这个表放了些什么呢

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 针对上面的代码我们做出以下改造
// 1.我们增加一个派生类Derive去继承Base
// 2.Derive中重写Func1
// 3.Base再增加一个虚函数Func2和一个普通函数Func3
class Base
{
public:
	virtual void Func1()
	{
		cout << "Base::Func1()" << endl;
	}
	virtual void Func2()
	{
		cout << "Base::Func2()" << endl;
	}
	void Func3()
	{
		cout << "Base::Func3()" << endl;
	}
private:
	int _b = 1;
};
class Derive : public Base
{
public:
	virtual void Func1()
	{
		cout << "Derive::Func1()" << endl;
	}
private:
	int _d = 2;
};
int main()
{
	Base b;
	Derive d;
	return 0;
}

通过观察和测试,我们发现了以下几点问题:

  1. 派生类对象d中也有一个虚表指针,d对象由两部分构成,一部分是父类继承下来的成员,虚表指针也就是存在部分的另一部分是自己的成员
  2. 基类b对象和派生类d对象虚表是不一样的,这里我们发现Func1完成了重写,所以d的虚表中存的是重写的Derive::Func1,所以虚函数的重写也叫作覆盖,覆盖就是指虚表中虚函数的覆盖。重写是语法的叫法,覆盖是原理层的叫法
  3. 另外Func2继承下来后是虚函数,所以放进了虚表,Func3也继承下来了,但是不是虚函数,所以不会放进虚表
  4. 虚函数表本质是一个存虚函数指针的指针数组,一般情况这个数组最后面放了一个nullptr
  5. 总结一下派生类的虚表生成:a.先将基类中的虚表内容拷贝一份到派生类虚表中 b.如果派生类重写了基类中某个虚函数,用派生类自己的虚函数覆盖虚表中基类的虚函数 c.派生类自己新增加的虚函数按其在派生类中的声明次序增加到派生类虚表的最后
  6. 这里还有一个童鞋们很容易混淆的问题:虚函数存在哪的?虚表存在哪的? 答:虚函数存在虚表,虚表存在对象中。注意上面的回答的错的。但是很多童鞋都是这样深以为然的。注意虚表存的是虚函数指针,不是虚函数,虚函数和普通函数一样的,都是存在代码段的,只是他的指针又存到了虚表中。另外对象中存的不是虚表,存的是虚表指针

4.2 多态的原理

上面分析了这个半天了那么多态的原理到底是什么?还记得这里Func函数传Person调用的Person::BuyTicket,传Student调用的是Student::BuyTicket

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Person {
public:
	virtual void BuyTicket() { cout << "买票-全价" << endl; }
};
class Student : public Person {
public:
	virtual void BuyTicket() { cout << "买票-半价" << endl; }
};
void Func(Person& p)
{
	p.BuyTicket();
}
int main()
{
	Person Mike;
	Func(Mike);
	Student Johnson;
	Func(Johnson);
	return 0;
}
  1. 观察下图的红色箭头我们看到,p是指向mike对象时,p->BuyTicket在mike的虚表中找到虚函数是Person::BuyTicket
  2. 观察下图的蓝色箭头我们看到,p是指向johnson对象时,p->BuyTicket在johson的虚表中 找到虚函数是Student::BuyTicket
  3. 这样就实现出了不同对象去完成同一行为时,展现出不同的形态
  4. 反过来思考我们要达到多态,有两个条件,一个是虚函数覆盖,一个是对象的指针或引用调用虚函数
  5. 再通过下面的汇编代码分析看出满足多态以后的函数调用,不是在编译时确定的,是运行起来以后到对象的中取找的。不满足多态的函数调用时编译时确认好的
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void Func(Person* p)
{
	p->BuyTicket();
}
int main()
{
	Person mike;
	Func(&mike);
	mike.BuyTicket();

	return 0;
}
// 以下汇编代码中跟这个问题不相关的都被去掉了
void Func(Person* p)
{
	...
		p->BuyTicket();
		// p中存的是mike对象的指针,将p移动到eax中
		001940DE  mov         eax, dword ptr[p]
		// [eax]就是取eax值指向的内容,这里相当于把mike对象头4个字节(虚表指针)移动到了edx
		001940E1  mov         edx, dword ptr[eax]
		// [edx]就是取edx值指向的内容,这里相当于把虚表中的头4字节存的虚函数指针移动到了eax
		00B823EE  mov         eax, dword ptr[edx]
		// call eax中存虚函数的指针。这里可以看出满足多态的调用,不是在编译时确定的,是运行起来
		以后到对象的中取找的。
		001940EA  call        eax
		00头1940EC  cmp         esi, esp
}
int main()
{
	...
		// 首先BuyTicket虽然是虚函数,但是mike是对象,不满足多态的条件,所以这里是普通函数的调
		用转换成地址时,是在编译时已经从符号表确认了函数的地址,直接call 地址
		mike.BuyTicket();
		00195182  lea         ecx, [mike]
		00195185  call        Person::BuyTicket(01914F6h)
		...
}

4.3 动态绑定与静态绑定

  1. 静态绑定又称为前期绑定(早绑定),在程序编译期间确定了程序的行为也称为静态多态,比如:函数重载
  2. 动态绑定又称后期绑定(晚绑定),是在程序运行期间,根据具体拿到的类型确定程序的具体行为,调用具体的函数,也称为动态多态

5. 单继承和多继承关系中的虚函数表

5.1 单继承中的虚函数表

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Base {
public:
	virtual void func1() { cout << "Base::func1" << endl; }
	virtual void func2() { cout << "Base::func2" << endl; }
private:
	int a;
};
class Derive :public Base {
public:
	virtual void func1() { cout << "Derive::func1" << endl; }
	virtual void func3() { cout << "Derive::func3" << endl; }
	virtual void func4() { cout << "Derive::func4" << endl; }
private:
	int b;
};

观察下图中的监视窗口中我们发现看不见func3和func4。这里是编译器的监视窗口故意隐藏了这两个函数,也可以认为是他的一个小bug。那么我们如何查看d的虚表呢?下面我们使用代码打印 出虚表中的函数

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
typedef void(*VFPTR) ();
void PrintVTable(VFPTR vTable[])
{
	// 依次取虚表中的虚函数指针打印并调用。调用就可以看出存的是哪个函数
	cout << " 虚表地址>" << vTable << endl;
	for (int i = 0; vTable[i] != nullptr; ++i)
	{
		printf(" 第%d个虚函数地址 :0X%x,->", i, vTable[i]);
		VFPTR f = vTable[i];
		f();
	}
	cout << endl;
}
int main()
{
	Base b;
	Derive d;
	// 思路:取出b、d对象的头4bytes,就是虚表的指针,前面我们说了虚函数表本质是一个存虚函数
	// 指针的指针数组,这个数组最后面放了一个nullptr
		// 1.先取b的地址,强转成一个int*的指针
		// 2.再解引用取值,就取到了b对象头4bytes的值,这个值就是指向虚表的指针
		// 3.再强转成VFPTR*,因为虚表就是一个存VFPTR类型(虚函数指针类型)的数组。
		// 4.虚表指针传递给PrintVTable进行打印虚表
		// 5.需要说明的是这个打印虚表的代码经常会崩溃,因为编译器有时对虚表的处理不干净,虚表最
		// 后面没有放nullptr,导致越界,这是编译器的问题。我们只需要点目录栏的 - 生成 - 清理解决方案,再
		// 编译就好了。
		VFPTR * vTableb = (VFPTR*)(*(int*)&b);
	PrintVTable(vTableb);
	VFPTR* vTabled = (VFPTR*)(*(int*)&d);
	PrintVTable(vTabled);
	return 0;
}

5.2 多继承中的虚函数表

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Base1 {
public:
	virtual void func1() { cout << "Base1::func1" << endl; }
	virtual void func2() { cout << "Base1::func2" << endl; }
private:
	int b1;
};
class Base2 {
public:
	virtual void func1() { cout << "Base2::func1" << endl; }
	virtual void func2() { cout << "Base2::func2" << endl; }
private:int b2;
};
class Derive : public Base1, public Base2 {
public:
	virtual void func1() { cout << "Derive::func1" << endl; }
	virtual void func3() { cout << "Derive::func3" << endl; }
private:
	int d1;
};
typedef void(*VFPTR) ();
void PrintVTable(VFPTR vTable[])
{
	cout << " 虚表地址>" << vTable << endl;
	for (int i = 0; vTable[i] != nullptr; ++i)
	{
		printf(" 第%d个虚函数地址 :0X%x,->", i, vTable[i]);
		VFPTR f = vTable[i];
		f();
	}
	cout << endl;
}
int main()
{
	Derive d;
	VFPTR* vTableb1 = (VFPTR*)(*(int*)&d);
	PrintVTable(vTableb1);
	VFPTR* vTableb2 = (VFPTR*)(*(int*)((char*)&d + sizeof(Base1)));
	PrintVTable(vTableb2);
	return 0;
}

观察下图可以看出:多继承派生类的未重写的虚函数放在第一个继承基类部分的虚函数表中

5.3 菱形继承、菱形虚拟继承

实际中我们不建议设计出菱形继承及菱形虚拟继承,一方面太复杂容易出问题,另一方面这样的模型,访问基类成员有一定得性能损耗。所以菱形继承、菱形虚拟继承我们的虚表我们就不看了,一般我们也不需要研究清楚,因为实际中很少用

C++ 虚函数表解析 | 酷 壳 - CoolShell

C++ 对象的内存布局 | 酷 壳 - CoolShell

5.4 菱形虚拟继承的构造

初始化的顺序一定和声明的顺序一致

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class A {
public:
	A(const char* s) { cout << s << endl; }
	~A() {}
};
class B :virtual public A
{
public:
	B(const char* s1, const char* s2) :A(s1) { cout << s2 << endl; }
};
class C :virtual public A
{
public:
	C(const char* s1, const char* s2) :A(s1) { cout << s2 << endl; }
};
class D :public B, public C
{
public:
	D(const char* s1, const char* s2, const char* s3, const char* s4) :B(s1, s2), C(s1, s3), A(s1)
	{
		cout << s4 << endl;
	}
};
int main() {
	D* p = new D("class A", "class B", "class C", "class D");
	delete p;
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-04-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
前端学习数据结构与算法系列(二):链表与数组的基础知识
由于数据是分散存储,查找数据时,只能从第一个数据开始,顺着指针的指向一一往下访问(顺序访问)。
一只图雀
2020/05/07
4090
《图解算法》第2章 选择排序
第2章 选择排序 数组是个重要的主题,一定要高度重视!很多算法仅在数据经过排序后才管用 内存工作原理 需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两
yeedomliu
2020/08/10
3860
数组和链表
假设我们要制作一个管理待办事项的应用,需要在计算机的内存中存储一系列的待办事项。这时候,该应用数组还是链表呢?
caoqi95
2019/03/27
5920
算法学习:数组 vs 链表
内存,尤其是随机存取存储器(RAM),是计算机中用于临时存储数据和程序指令的部分。与硬盘相比,内存访问速度快,但信息非持久保存。
空白诗
2024/06/14
1740
算法学习:数组 vs 链表
Android技能树 — 数组,链表,散列表基础小结
现在安卓面试,对于数据结构的问题也越来越多了,要求也越来越多,所以我对于数据结构只能慢慢补起来了。(灬ꈍ ꈍ灬)
青蛙要fly
2018/08/29
9500
Android技能树 — 数组,链表,散列表基础小结
数据结构与算法系列3之从内存角度分析数组与链表的区别
内存是计算机的重要部件之一。它是外存与CPU进行沟通的桥梁,计算机中所有程序的运行都在内存中进行。内存性能的强弱影响计算机整体发挥的水平。内存(Memory)也称内存储器和主存储器,它用于暂时存放CPU中的运算数据,与硬盘等外部存储器交换的数据。只要计算机开始运行,操作系统就会把需要运算的数据从内存调到CPU中进行运算。当运算完成,CPU将结果传送出来。内存的运行也决定计算机整体运行快慢的程度。内存条由内存芯片、电路板、金手指等部分组成。
一只胡说八道的猴子
2021/02/25
5370
数据结构与算法系列3之从内存角度分析数组与链表的区别
算法一看就懂之「 数组与链表 」
其实也不是真的用得少,只不过我们在使用的时候被很多高级语言和框架组件封装好了,真正需要自己去实现的地方比较少而已。但别人封装好了不代表我们就可以不关注了,数据结构作为程序员的内功心法,是非常值得我们多花时间去研究的,我这就翻开书复习复习:
奎哥
2019/08/16
4830
算法一看就懂之「 数组与链表 」
数据结构与算法系列2 线性表 链表的分类+使用java实现链表+链表源码详解
链表是一种物理存储单元上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表的链接次序实现的一系列节点组成,节点可以在运行时动态生成,每个节点包括两个部分,一个是村粗数据元素的数据域,一个是存储指针的指针域,相比于线性表顺序结构,操作复杂。由于不必须按照顺序存储,链表在插入的时候可以达到o(1)的复杂读,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
一只胡说八道的猴子
2020/09/27
6400
数据结构与算法系列2 线性表 链表的分类+使用java实现链表+链表源码详解
数据结构与算法(三)-线性表之静态链表
前言:前面介绍的线性表的顺序存储结构和链式存储结构中,都有对对象地引用或指向,也就是编程语言中有引用或者指针,那么在没有引用或指针的语言中,该怎么实现这个的数据结构呢?
2018/09/26
1.4K0
数据结构与算法(三)-线性表之静态链表
数据结构:数组、链表、栈、队列的理解
解释定义 数据结构: 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。再简单描述一下:数据结构就是描述对象间逻辑关系的学科。 如果还是不太清楚下面会举例说明的。 数据存储结构: 简单的讲就是数据在计算机中的存储方式。 常用的数据存储方式有两种:顺序存储,非顺序存储。顺序存储就是把数据存储在一块联系的存储介质(硬盘或内存等)中。反之就是非顺序存储咯。Java中的数组就是典型的顺序存储,链表就是非顺序存储。数组存储数据时会开辟出一块联系内存,按顺序存储。链表先不会开辟出一块内存来,而是只需要知道下一
纪莫
2018/04/19
1.8K0
数据结构:数组、链表、栈、队列的理解
疯狂java笔记之线性表
从数据的逻辑结构来分,数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来,应用程序中的数据大致哟如下四种基本的逻辑结构。
HelloJack
2018/08/28
6240
疯狂java笔记之线性表
数组和链表的区别浅析
链表是一种上一个元素的引用指向下一个元素的存储结构,链表通过指针来连接元素与元素;
全栈程序员站长
2022/07/02
4040
数组和链表的区别浅析
数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)
比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。
用户3045442
2018/09/11
7880
数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)
数据结构:数组和链表的区别(数组和链表的优缺点 & 数组和链表的适用场景)
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/147966.html原文链接:https://javaforall.cn
全栈程序员站长
2022/09/07
2.8K0
python算法与数据结构-单链表(38)
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
Se7eN_HOU
2019/07/02
4960
从PHP数组实现原理看线性表数据结构
线性表,全名为线性存储结构。使用线性表存储数据的方式可以这样理解,即“把所有数据用一根线串起来,再存储到物理空间中”。最简单的线性表就是数组了。虽然PHP的数组本身不是由基础的数据结构构成,但是其内部实现方式应用到了大部分的线性表数据结构。今天,借着学习线性表数据结构的机会,重新回顾PHP数组的内部实现原理。
写PHP的老王
2020/01/21
1.5K0
数组和链表的区别
数组: 数组是将元素在内存中连续存放,由于每个元素占用内存 相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其 中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少或不插入和删除元素,就应该用数组。 链表: 链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后
猿人谷
2018/01/17
4.9K0
数组和链表
在上面的例子中,数组 a 中有 5 个元素。 也就是说 ,a 的长度是 6 。我们可以使用 a [0] 来表示数组中的第一个元素。因此,a [0] = A 。类似地,a [1] = B,a [2] = C,依此类推。
硬件开源小站
2023/04/07
5430
数组和链表
数据结构与算法(二)-线性表之单链表顺序存储和链式存储
前言:前面已经介绍过数据结构和算法的基本概念,下面就开始总结一下数据结构中逻辑结构下的分支——线性结构线性表
2018/09/26
1.4K0
数据结构与算法(二)-线性表之单链表顺序存储和链式存储
小白学算法-数据结构和算法教程:什么链表以及操作
链表是一种线性数据结构,其中元素不存储在连续位置,而是使用指针链接。链表形成一系列相连的节点,每个节点存储数据和下一个节点的地址。
用户1418987
2023/10/26
1740
小白学算法-数据结构和算法教程:什么链表以及操作
推荐阅读
相关推荐
前端学习数据结构与算法系列(二):链表与数组的基础知识
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验