1. 说说C语言和C++的区别
● C++是面向对象的语言,而C是面向过程的语言
● C++引入运算符,取代了C中的mallocfree库函数
● C++引入引用的概念,而C中没有
● C++引入类的概念,而C中没有
● C++引入函数重载的特性,而C中没有
● C++有bool类型,C中没有
2. 说说 C++中 struct 和 class 的区别
● struct 一般用于描述一个数据结构集合,而 class 是对一个对象数据的封装;
● struct 中默认的访问控制权限是 public 的,而 class 中默认的访问控制权限是 private 的,例如:
struct A{ int iNum; // 默认访问控制权限是 public }class B{ int iNum; // 默认访问控制权限是 private }
● 在继承关系中,struct 默认是公有继承,而 class 是私有继承;
● class 关键字可以用于定义模板参数,就像 typename,而 struct 不能用于定义模板参数,例如:
template<typename T, typename Y> // 可以把typename 换成 classint Func(const T& t, const Y& y) { //TODO }
● C++ 中的 struct 是对 C 中的 struct 进行了扩充,它们在声明时的区别如下:
● 使用时的区别:C 中使用结构体需要加上 struct 关键字,或者对结构体使用 typedef 取别名,而 C++ 中可以省略 struct 关键字直接使用,例如:
struct Student{ int iAgeNum; string strName; }typedef struct Student Student2; //C中取别名struct Student stu1; // C 中正常使用Student2 stu2; // C 中通过取别名的使用Student stu3; // C++ 中使用
*3.include头文件的顺序以及双引号""和尖括号<>的区别和查找路径
记忆
头文件引用顺序,a.h声明了b.h定义的变量时,a.c中引用两头文件顺序()
“”是什么 <>是什么
“”查找顺序,<>查找顺序
(1)include头文件的引用顺序
如果在a.h中声明了一个在b.h中定义的变量,那么在a.c中引用两个头文件的时候,必须a.h在b.h之后,否则报错变量类型未声明
(2)双引用号和尖括号的区别
尖括号<>的头文件是系统文件,双引号“”的头文件是自定义文件。
编译的预处理阶段查找头文件的路径不一样
“”查找顺序:当前头文件目录->编译器设置的头文件路径(编译器可使用-I显式指定搜索路径)->系统变量CPLUS_ INCLUDE PATH/C_ INCLUDE PATH 指定的头文件路径 <>查找顺序: 编译器设置的头文件路径->系统变量CPLUS_ INCLUDE PATH/C_ INCLUDE PATH 指定的头文件路径
4.引用
C++中的引用:
引用是为对象起的别名,必须被初始化,与变量绑定到一起,且将一直绑定在一起。
引用引入了对象的一个同义词。定义引用的表示方法与定义指针相似,只是用&代替了*。引用(reference)是c++对c语言的重要扩充。引用就是某一变量(目标)的一个别名,对引用的操作与对变量直接操作完全一样。其格式为:类型 &引用变量名 = 已定义过的变量名。
引用的特点:
①一个变量可取多个别名。
②引用必须初始化。
③引用只能在初始化的时候引用一次 ,不能更改为转而引用其他变量。
(1)基础引用:
void TestReference1 (){ int a = 1; int& b = a;
cout<<"a:address->" <<&a<< endl; cout<<"b:address->" <<&b<< endl;
a = 2; b = 3; int& c = b;// 引用一个引用变量,别名的别名 c = 4;}
(2)const引用:
void TestReference2 (){ int d1 = 4; const int & d2 = d1; d1 = 5;//d1改变,d2的值也会改变。 //d2 = 6;//不能给常量(不能被修改的量)赋值。
const int d3 = 1; const int & d4 = d3; //int&d5 = d3; const int & d6 = 5;//常量具有常性,只有常引用可以引用常量
double d7 = 1.1; //int& d8 = d7;//d7是double类型,d8是int,d7赋值给 d8时要生成一个临时变量 //也就是说d8引用的是这个带有常性的临时变量,所以不能赋值。 const int& d9 = d7;}
(3)引用作参数:
1.【值传递】如果形参为非引用的传值方式,则生成局部临时变量接收实参的值void Swap (int left, int right) //值传递的方式无法实现交换,因为传参时对于参数left和right拷贝一临时副本,交换的是副本值,因为其是临时变量函数退出,变量销 { //毁,并不会影响外部left和right的值。 int temp = left; left = right ; right = temp ;}
2.【引用传递】如果形参为引用类型,则形参是实参的别名。void Swap (int& left, int& right)//使用引用的话,不做临时拷贝,&的使用说明此处只是原参数的另一个名字而已,所以修改时直接在原参数的基础上修改变量值。{ int temp = left; right = left ; left = temp ;}
3.【指针传递】void Swap (int* pLeft, int* pRight)//传入的是地址,因为地址是唯一的,所以指针通过地址的访问进而可修改其内容。{ int temp = *pLeft; *pLeft = *pRight; *pRight = temp;}
引用虽方便,使用须谨慎:
(1)&在这里不是求地址运算,而是起标识作用。
(2)类型标识符是指目标变量的类型。
(3)声明引用时,必须同时对其进行初始化。
(4)引用声明完毕后,相当于目标变量名有两个名称,即该目标原名称和引用名,且不能再把该引用名作为其他变量名的别名。
(5)对引用求地址,就是对目标变量求地址。即引用名是目标变量名的一个别名。引用在定义上是说引用不占据任何内存空间,但是编译器在一般将
其实现为const指针,即指向位置不可变的指针,所以引用实际上与一般指针同样占用内存。
(6)不能建立引用的数组。因为数组是一个由若干个元素所组成的集合,所以无法建立一个由引用组成的集合,但是可以建立数组的引用。
(7)引用常见的使用用途:作为函数的参数、函数的返回值。
总结:
-
不要返回一个临时变量的引用。
-
如果返回对象出了当前函数的作用域依旧存在,则最好使用引用返回,因为这样更高效。
- 引用和指针的区别和联系(笔试热点)
-
引用只能在定义时初始化一次,之后不能改变指向其它变量(从一而终);指针变量的值可变。
-
引用必须指向有效的变量,指针可以为空。
-
sizeof指针对象和引用对象的意义不一样。sizeof引用得到的是所指向的变量的大小,而sizeof指针是对象地址的大小。
-
指针和引用自增(++)自减(—)意义不一样。
-
相对而言,引用比指针更安全。
指针比引用更为灵活,但是其风险也很大。使用指针时一定要检查指针是否为空(NULL),且空间回收后指针最好置
零,以免野指针的发生造成内存泄漏等问题。
*5. 指针和引用的区别
记忆
引用概念 地址 空间 多级 运算 间接直接 初始化
● 指针:指针变量存储的内容为一个地址,引用是给一个已有对象起的别名也就是两个变量名字共用一个地址
● 指针是一个实体,需要分配内存空间;引用是变量别名,不需要分配内存空间
● 可以有多级指针,不能有多级引用
● 自增运算结果不一样
● 指针是间接访问,引用是直接访问
● 指针可以不用初始化,引用一定要先初始化并且引用不能初始化为NULL
*8. 简述C++从代码到可执行二进制文件的过程
记忆
过程名,每个过程的具体操作
● 一个C++程序从源码到执行文件,有四个过程,预编译、编译、汇编、链接。
● 预编译:展开所有头文件,宏替换,去掉注释,条件编译(对#ifend #endif判断)
● 编译:将代码转换为汇编代码
● 汇编:把汇编语言翻译成机器指令
○ 代码段:主要包含的是程序的指令,不可写,可读可执行
○ 数据段:存放程序中用到的各种全局变量或者静态数据。可读可写可执行。
● 链接:
○ 合并各个.obj文件,合并符号表,解析符号表判断是否重定义
○ 符号地址重定位
○ 生成.exe文件
*10. 什么是函数指针,如何定义函数指针,有什么使用场景
记忆
概念 定义方法 应用场景
● 函数指针就是指向函数的指针变量。每一个函数都有一个入口地址,该入口地址就是函数指针所指向的地址。
● 定义形式如下:
int func(int a); int (*f)(int a); f = &func;
● 函数指针的应用场景:回调(callback)。例如:在linux下创建线程的时候需要传入一个回调函数,还有在C++中的sort和priority_queue,如果自己实现比较器那么需要把比较器的函数入口当做参数传入。
*16. 宏函数
先说宏和函数的区别:
- 宏做的是简单的字符串替换(注意是字符串的替换,不是其他类型参数的替换),而函数的参数的传递,参数是有数据类型的,可以是各种各样的类型.
- 宏的参数替换是不经计算而直接处理的,而函数调用是将实参的值传递给形参,既然说是值,自然是计算得来的.
- 宏在编译之前进行,即先用宏体替换宏名,然后再编译的,而函数显然是编译之后,在执行时,才调用的.因此,宏占用的是编译的时间,而函数占用的是执行时的时间.
- 宏的参数是不占内存空间的,因为只是做字符串的替换,而函数调用时的参数传递则是具体变量之间的信息传递,形参作为函数的局部变量,显然是占用内存的.
- 函数的调用是需要付出一定的时空开销的,因为系统在调用函数时,要保留现场,然后转入被调用函数去执行,调用完,再返回主调函数,此时再恢复现场,
宏定义可以提高代码可移植性(改的地方少),可读性(代码量少),宏定义适合简短常用的函数。
//两种写法#define MAX( a, b) ( (a) > (b)? (a) : (b) )
#define MAX(a, b) ((a) > (b) \ ? (a) : (b))
//宏定义还可以实现函数不能实现的传参方式:传递数据类型#define MALLOC(n, type) ((type *) malloc((n)* sizeof(type)))
//宏定义调用int main(){ MAX(1,2); MALLOC(3,int); return0;}
17. 内联函数和宏函数的区别
野指针
不会的
1.extern c
2.友元函数
3.类有什么特点 3
4.多态 2
5.纯虚函数
6.多态怎么实现的 具体细节
7.初始化参数列表 顺序 const引用的参数必须在初始化参数列表中初始化
8.函数参数默认值 没定义时 缺省
9.内联函数
10.Malloc怎么实现的 堆2
11.new和malloc
12.自由存储区
13.const和指针
14.代码:链表 二叉树 排序 acm模式输入输出
查缺补漏
引用
概念 常引用 3
给变量起别名,没有常引用
- 引用变量创建必须初始化
- 引用变量不能赋值为空,必须指向一个已定义的对象
- 引用变量不可以改变指向
参数默认值
概念 定义默认值顺序 缺省顺序
参数形参处 可以定义缺省的参数值,当调用时不传递该位置的参数 就相当于 使用该默认值。参数默认值只能从后开始依次定义,不能有跨越的不定义默认值。
void run(int a, int b, int c = 10, int d = 20) {}//void run2(int a, int b=10, int c, int d=21, int f) {//}错误的写法,参数的默认值只能从后往前依次定义
类
类里有 访问权限
类里面有成员变量和成员方法(函数)
在内存中占有空间的就叫对象
类的默认访问权限是私有的 private只可以在类内访问
class people {private: int age = 1; int weight = 100;public://公有的 外界可以访问,可以通过对象访问 people (int age) { this->age = age; weight = 3; cout << "调用了构造函数"; } void fun() { cout << "我吃饭了" << endl; } void getAge() { cout << age << endl; }}int main() { //malloc 在堆区申请空间 //new首先在堆区创建了一块空间 然后会调用该对象的构造函数 people *p = new people(2);//在堆区创建了一个sizeof(people)大小的空间 //然后调用构造函数 类的大小只算成员变量和结构体对齐相同 people *q = new people(3); p->getAge();
return 0;}
?this指针
成员函数中,表示使用当前行为的对象就是this this是一个当前类类型的地址,指向了当前对象
构造函数
- 与类同名
- 没有返回值
- 如果没有实现构造函数,编译器会有一个默认的无参构造函数
- 如果自己实现了构造函数,编译器将不会生成默认构造函数
访问修饰符
private 只有当前类内才有权限访问这个成员 扩展友元函数
protect 本类和本类的子类
public 所有位置
成员和类的默认访问修饰符为private 扩展struct
?友元函数
类中可以声明一个友元类或友元函数,让这个友元类或友元函数可以访问本类的私有或受保护成员
单向,不可传递,不可继承
class Obj { int mem;//私有成员 friend class A;//声明了Obj类的一个友元类 friend void run();//声明了Obj类的一个友元全局函数};class A { void func() { Obj o; o.mem;//可以使用私有成员 }};void run() { Obj o; o.mem;}
创建对象
一共有三种方式
创建栈区对象
用类似定义变量的语法创建存在栈区的对象,出了作用域会自动析构,生命由系统自动管理
void run() { A a; //A a2();这么写符合声明函数的语法,声明了一个:返回值是A类型,函数名是a2,参数列表是无参的 A a3(25, 2);}
匿名构造对象
创建一个没有名字的临时对象,当本行代码结束时,对象被系统销毁
void run() { A();//创建匿名对象 A(2, 3);//用参数来创建匿名对象}
在堆区创建对象
堆区创建对象,对象的销毁由程序员控制,大的对象栈区放不下就必须在堆区创建
void run() { A* p = new A(); A* p2 = new A(int, int); A* p3 = new A[20];//创建数组 delete p; delete p2; delete[] p3;//析构数组时,不delete会报错,准确来讲是有析构函数的数组必须delete[] //总之,数组delete[]一定不会错}
二维数组
定义
vector<vector<int>> vec = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
操作
int row = vec.size();//行,一个一维数组占一行int col = vec[0].size();//列,第一个一维数组的元素个数
vec[0].push_back(11);//向第0行末尾加一个元素vector<int> p = {6, 6, 6};vec.push_back(p);//向二维数组中加入一行
//输出for (int i = 0; i < vec.size(); ++i) { for (int j = 0; i < vec[i].size(); ++j) { cout << vec[i][j] << " "; } cout << endl;}
实际上C++中没有二维数组,一维数组中放的一维数组就可以看成是二维数组,二维数组的行,看成一维数组中有几个元素(一维数组)
?构造函数与析构函数
注意:C++的一切操作都是在内存上的操作
C++利用构造函数和析构函数实现了对象所占内存的初始化和清空操作,对象的初始化操作和清除操作时强制执行构造函数和析构函数,如果我们没有自己实现构造函数和析构函数,编译器将会提供默认的构造函数和析构函数
- 构造函数是作用于对象初始化的,主要作用是在创建对象时为对象的成员变量赋值,构造函数由编译器自动调用,不需要手动调用。当我们使用 new 时,会先使用 malloc 申请一块堆区空间,然后调用构造函数为申请的空间赋值
- 析构函数作用于对象销毁工作,清空对象所占有的堆区内存
构造函数语法
- 没有返回值:类名 () {}
- 函数名和类名相同前面什么也不写
- 构造函数可以有参数,可以重载
- 创建对象时编译器会自动调用构造函数,不需要手动调用
- 如果实现了有参数的构造函数编译器不会实现默认的构造函数
析构函数语法
- 没有返回值:~类名 () {}
- 函数名称与类名相同但是前面要有~
- 析构函数不可以有参数,因此不可以发生重载
- 编译器在对象销毁前会自动调用析构函数,不需要手动调用
class people {private: int weight; int height; int age; string name; string bloodType;public: //构造函数 people() { cout << "调用了构造函数" << endl; } people(int weight) { this->weight = weight; cout << "体重为:" << endl; } people(int weight, int height, int age, string name, string bloodType) { this->weight = weight; this->height = height; this->age = age; this->name = name; this->bloodType = bloodType; cout << "姓名为:" << name << endl; cout << "体重为:" << weight << endl; cout << "年龄为:" << age << endl; } ~people() { cout << "调用了析构函数" << endl; }};int main() { //自定义类型只能用new不能用malloc //因为new会申请空间并且走构造函数,malloc只会申请空间 people p(1, 2, 3, "asd", "A");//在栈区创建的对象,编译器会自动释放 people *p1 = new people(99999);//在堆区创建的对象,需要手动释放,new会走malloc和构造函数 delete p1;//delete和new是搭配的 delete会走析构函数和free return 0;}
初始化参数列表
只能在构造函数里使用该语法,可以给所有成员设置初始化参数,const类型和引用类型必须在初始化参数列表中初始化,成员的构造顺序和在初始化参数列表中的顺序无关,与在类中的声明顺序有关
拷贝构造函数
拷贝构造函数是把对象以值的形式当作参数传入,利用传入的对象生成一个新的对象的实例,而赋值运算符是将对象的值复制给一个已经存在的实例,拷贝构造函数的功能是使用对象创建一个对象实例,也就是说使用对象初始化另一个新的对象,赋值运算符是将一个对象的值赋值给另一个已经存在的对象,调用的是拷贝构造函数还是赋值运算符,主要看是否有新的对象产生
使用场景
- 对象作为函数的返回值以值的方式从函数返回
- 对象作为函数参数,以值传递的方式穿给参数
- 使用一个对象给另一个对象初始化
class A {private: int n = 0; int *p = nullptr;//NULL 宏定义 0 nullptr 是空指针 void*public: A(int _size) { if (_size > 0) { n = _size; p = (int*)malloc(sizeof(int)* n); } } //如果不加引用在通过实参创建形参的过程中,还会调用拷贝构造函数 //还会有实参创建形参的过程导致无限循环该过程 A (const A &other) { this->n = other.n; this->p = other.p; cout << "调用了拷贝构造函数" << endl; }};int main() { A a(1); A b(a); A c(3); c = b;//会走赋值运算符,把对象赋值给一个已经存在的实例 cout << "-----------------" << endl; A d = c;//用对象初始化对象会走拷贝构造函数 return 0;}
深拷贝构造函数
对象中含有指针类型的成员变量时需要用深拷贝
构造,否则用浅拷贝构造
编译器默认的拷贝构造函数是浅拷贝
构造函数
如果对象中含有指针变量用了浅拷贝构造,那么会导致两个指针变量指向同一块地址空间,那么在对象释放时会导致一块空间释放两次
浅拷贝和深拷贝的区别在于两个指针变量指向的是一块空间还是指向不同的空间
。假设没有创建内存的操作就是浅拷贝,否则是深拷贝
class A {private: int n = 0; int *p = nullptr;//NULL宏定义0 nullptr是空指针void*public: A (int _size) { if (_size > 0) { n = _size; p = (int *)malloc(sizeof(int) *n); } } //如果不加引用在通过实参创建形参过程中,还会调用拷贝构造函数,还会有实参创建形参的过程导致无限循环该过程 A (const A &other) {//深拷贝 this->n = other.n; p = (int *)malloc(sizeof(int)* n); cout << "调用了拷贝构造函数" << endl; } ~A () { if (p != nullptr) { free(p); cout << "调用了析构函数释放了堆区空间" << endl; } }};int main() { A a(1); A b(a); return 0;}
浅拷贝构造函数
对象中含有指针类型的成员变量时需要用深拷贝构造,如果对象里面有指针变量,两个对象里面的指针变量指向同一块地址,在释放内存时会报错
class A {private: int n = 0; int *p = nullptr;//NULL宏定义0 nullptr是空指针void*public: A (int _size) { if (_size > 0) { n = _size; p = (int *)malloc(sizeof(int) *n); } } A (const A &other) {//浅拷贝 this->n = other.n; this->p = other.p; cout << "调用了拷贝构造函数" << endl; } ~A () { if (p != nullptr) { free(p); cout << "调用了析构函数释放了堆区空间" << endl; } }};int main() { A a(1); A b(a); return 0;}
NULL和nullptr
NULL宏定义0 nullptr是空指针void*
静态成员
类可以拥有静态成员,包括静态成员函数和静态成员变量
静态成员就类似于全局变量或全局函数,并且拥有访问修饰符,使用静态需要加类名作用域
静态成员变量必须类外初始化
相比之下静态成员函数没有什么限制 静态成员变量和静态成员函数不属于某个对象,属于类,可以直接通过类名加 :: 调用
静态成员函数只允许访问静态成员变量
class people {public: static int a; int b; static void fun() { a = 2;//静态成员函数只允许访问静态成员变量 }};int people::a = 1;//静态成员变量必须类外初始化
int main() { people::a; people::fun(); return 0;}
继承性
创建对象时,每个类都会先调用父类的构造,当父类构造完成后再构造子类
析构对象时,每个类都会先析构当前类,当前类析构函数调用完后再调用父类析构函数
如果父类没有无参构造,就需要手动指定调用构造传参数(使用初始化参数列表传参)
class father {public: int a; father(int a) { cout << "父类构造函数" << endl; } father(int a, int b) { cout << "父类构造函数" << endl; } void fun() { cout << "father fun" << endl; } ~father() { cout << "父类对象析构" << endl; }};class child:public father {public: int b; child():father(1) { cout << "子类构造函数" << endl; } ~child() { cout << "子类对象析构" << endl; }};
多继承
一个类有多个父类,不推荐如此使用,会导致难以控制,比如java或C#等其他面下那个语言中都不支持多继承
菱形继承
会导致D中有两份A的数据,多数情况下这都是多余的,并且可能导致二义性错误
虚继承
解决菱形继承中,父类被继承多次的问题,使用虚继承可以解决,虚继承时只会继承到一份
class grandFather {public: int a;};class father:virtual public grandFather {public:};class mather:virtual public grandFather {};class child:public father, public mather {public:};
多态性
记忆
静态多态 动态多态 概念
动态多态:重写:父类指针指向子类对象,父类指针动态的调用子类对象中的重写函数
class father {public: virtual void fun() {//虚函数 } father() { cout << "father的构造函数" << endl; } ~father() { cout << "father的析构函数" << endl; }};class child:public father { child() { cout << "child的构造函数" << endl; } ~child() { cout << "child的析构函数" << endl; }};int main() { father *f = new child(); delete f; return 0;}
虚函数
C++默认的成员函数不开启多态,只有将函数声明为virtual函数,该函数才可以被重写
class father {public: virtual void fun() {//虚函数 }}
虚析构
析构函数应该设置为虚函数,不然可能内存泄漏
当类之间具有继承关系时,在多态中应该将析构函数设置为虚函数,让析构函数具有多态,此时父类指针delete时才会准确的调用到子类的析构函数
class father {public: virtual void fun() {//虚函数 } father() { cout << "father的构造函数" << endl; } ~father() { cout << "father的析构函数" << endl; }};class child:public father {public: child() { cout << "child的构造函数" << endl; } ~child() { cout << "child的析构函数" << endl; }}
纯虚函数
如果父类中的一个虚函数其自身的实现无意义,此时可以将该虚函数定义为纯虚函数,拥有至少一个纯虚函数的类是纯虚类(抽象类),纯虚类不能直接创建对象,子类只有重写了所有纯虚函数后才能创建子类对象
class father {//抽象类(纯虚类)public: virtual void fun() = 0;//纯虚函数 father() { cout << "father的构造函数" << endl; } ~father() { cout << "father的析构函数" << endl; }};class child:public father {public: child() { cout << "child的构造函数" << endl; } void fun() { cout << "子类的fun" endl; } ~child() { cout << "child的析构函数" << endl; }};
覆盖(重写)
在父类和子类中返回值类型相同,函数名相同,参数类型相同的虚函数是覆盖,具体调用哪个函数看指针指向哪个类的对象
隐藏
在父类和子类中只有函数名相同就会发生隐藏,不要求返回值和参数相同,具体执行父类函数还是子类函数看是哪个类的对象指针调用的这个函数
//多态:父类指针指向子类对象:父类指针动态的调用子类对象里面的重写函数class duck {//纯虚类(抽象类) 作为基类 string country; string color; int weight;public: virtual void Swimming() = 0; void Lay_eggs() { cout << "下蛋嘿嘿嘿" << endl; }};class psyduck:public duck {//可达鸭public: virtual void Swimming() { cout << "可达鸭会玩铁男但是不会游泳" << endl; }; void Lay_eggs() { cout << "可达鸭下单嘿嘿嘿" << endl; }};class ugly_duckling:public duck {//丑小鸭public: virtual void Swimming() { cout << "会游泳但是不会打联盟" << endl; };};class Roasted_Duck:public duck {//烤鸭public: virtual void Swimming() { cout << "烤鸭不会游泳,但是香" << endl; };};int main() { //通过父类指针指向不同的子类对象,父类指针动态的去调用子类对象中重写的函数 ugly_duckling *d = new ugly_duckling(); d->Swimming(); d->Lay_eggs(); cout << endl;
Roasted_Duck *d1 = new Roasted_Duck(); d1->Swimming(); d1->Lay_eggs(); cout << endl;
psyduck *d2 = new psyduck(); d2->Swimming(); d2->Lay_eggs(); //函数隐藏,子类中只需要函数名和父类中的函数名相同就会发生函数隐藏 //函数隐藏具体执行父类中的同名函数还是子类中的同名函数,看调用这个函数的类型 return 0;}
优先级队列
概念
优先级队列,顾名思义,里面元素是有优先级的,自带排序功能
priority_queue 又称为优先队列,其底层是用堆
来进行实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。
当然,可以在任何时候往优先队列里面加入元素,而优先队列底层的数据结构堆(heap)会随时调整结构,使得每次的队首元素都是优先级最高的
和队列不同的是优先队列没有 front()函数与back()函数,而只能通过 top() 函数来访问队首元素(也称堆顶元素),也就是优先级最高的元素。
定义方法
例如:
priority_queue<int> que;
常用函数
#include<queue>//使用前要先添加头文件que.push(i);//把i放进优先级队列里que.pop();//弹出堆顶元素que.top();//获取堆顶元素但不弹出que.size();//优先级队列中元素个数que.empty();//判断优先级队列是否为空,如果为空返回1,不为空返回0
元素优先级设置
优先队列最为强大的是它的排序功能,如何定义队列的优先级是运用好优先队列的关键,下面分别介绍基本数据类型(例如:int char double)与结构体类型的优先级设置的方法。
1)基本数据类型的优先级设置
(即可以直接使用的数据类型),优先队列对他们的优先级设置一般是数字越大的优先级越高
,因此队首是优先级最大的那个(如果是 char
类型,则是字典序最大
的)。以 int 型为例下面两种是等价的:
priority_queue<int>q;//默认最大堆 即堆顶元素最大priority_queue<int,vector<int>,less<int> >q;//最大堆
可以发现第二种定义方式的尖括号内多出了两个参数:其中 vector
第三个参数 less
#include<iostream>#include<queue>using namespace std;int main(){ priority_queue<int,vector<int>,greater<int> > q; q.push(3); //入队 q.push(5); q.push(1); cout<<q.top()<<endl; //获取队首元素 return 0;}
?2)结构体的优先级设置
// 使用friend其排序与sort排序刚好相反struct node{ string name; int price; //friend bool operator<(const node &f1,const node &f2) //建议使用上面的引用来提高效率 friend bool operator<(node f1,node f2) { return f1.price<f2.price; }};priority_queue<node> q;// 不使用 friend 友元将它写在外面struct node{ string name; int price;};struct cmp{ bool operator() (node f1,node f2) { return f1.price>f2.price; } }priority_queue<node,vector<node>,cmp>;
首先对某一对象建立结构体,现在希望价格高的优先级高,就需要重载(overload)小于号“<”.重载是指对已有的运算符进行重新定义。
可以看到,node 结构体中增加了一个函数,其中“friend”为友元,后面的”bool operator<(node f1,node f2) ” 这里是对小于号进行了重载事实上也仅仅只能对小于号进行重载,重载大于号会编译错误,因为从数学上来讲只需要重载小于号即 f1>f2<==>f2<f1,而我们发现 return f1.price<f2.price ,重载后小于号还是小于号的作用,因此就可以直接定义 node 类型的优先队列,其内部就是以价格高的水果为优先级高,因此可以直接定义为:
priority_queue
priority_queue<int, vector<int>, greater<int>> que;//最小堆priority_queue<int> q;//默认优先级队列for (int i = 0; i < 5; ++i) { que.push(i);}que.pop();//弹出堆顶元素cout << que.top() << endl;//获取堆顶元素但不弹出que.size();//优先级队列中元素个数que.empty();//判断优先级队列是否为空,如果为空返回1 不为空返回0priority_queue<int, vector<int>, less<int>> que2;//最大堆que.push(6);que.push(1);que.push(8);que.push(2);que.push(7);cout << que.size() << endl;cout << "堆顶元素" << que.top() << endl;que.pop();cout << "移除堆顶元素后" << endl;cout << que.top << endl;cout << "优先级队列是否为空" << que.empty() << endl;
priority_queue的常见用途
priority_queue 可以解决一些贪心问题,也可以对 Dijkstra 算法进行优化。
需要要注意使用 top() 函数之前,必须用 empty() 判断优先队列是否为空。
栈和队列
栈定义方法及常用函数
stack<int> s;//定义 stack<数据类型> 名称;s.push();//入栈 将元素放到栈顶s.top();//获取栈顶元素s.pop();//弹出栈顶元素s.empty();//判断栈是否为空 为空返回1 不为空返回0s.size();//返回栈中元素个数
队列定义方法及常用函数
queue<string> q;//定义 queue<数据类型> 名称;q.push("Hello, World!");//队列先进先出 所以push是向队尾放元素q.pop();//弹出队首元素 即最前面那个q.size();//返回队列元素个数 返回类型为unsigned intq.empty();//判断是否为空 空返回1 不空返回0q.front();//返回队首元素q.back();//返回队尾元素
#include<stack>//栈 先进后出#include<queue>//队列 先进先出int main() { stack<int> stk;//栈里面放的元素类型是int stk.push(1); stk.push(2); stk.push(3); stk.push(4); stk.push(5); while (!stk.empty()) { cout << "栈顶元素" << stk.top() << endl; stk.pop(); } queue<int> que; for (int i = 0; i < 4; ++i) { que.push(i); } while (!que.empty()) { cout << "队列的首元素:" << que.front() << "队列的尾元素:" << que.back() << endl; que.pop(); } return 0;}
链表
它是动态的进行存储分配的一种结构,链表和数组比较,不用事先确定存储空间,而是根据需要开辟内存单元
链表分为数据域和指针域
- 数据域:存储数据,例如一个人的信息:姓名 年龄 班级
- 指针域:是一个指针变量,存储下一个节点的地址,使本来不连续的空间通过该指针链接到一起
上课学的代码
#pragma once//.h文件声明类中的函数,结构体变量等#include<iostream>#include<vector>using namesapce std;//结构体和类使一样的,只是默认访问权限不同struct Node {//链表的节点 int val;//数据域 Node* next;//指针域:存放下一个节点的地址 Node (int val) { this->val = val; next = nullptr; }};class List {private: Node *Head = nullptr;//头节点 链表中第一个节点帮助访问整个链表 Node *Tail = nullptr;//尾节点 链表中最后一个节点帮助插入节点public: List (vector<int> vec); Node *GetListHead(); void PrintList(); void DeleteNode(int val); void AddNode(int val, int newVal);//在节点值等于val的后面增加一个新节点 例如在2后买你加val值为0的节点};
结构体和类的访问权限
成员变量和成员函数在类中的默认访问权限为private,而在结构体中默认访问权限是public