C++学习(计蒜客)
学习C++
1. 斐波纳切数列
斐波那契数列是一种非常有意思的数列，由 00 和 11 开始，之后的斐波那契系数就由之前的两数相加。用数学公式定义斐波那契数列则可以看成如下形式：
Fn表示斐波那契数列的第n项，你能知道斐波那契数列中的任何一项吗？
#include <iostream>
using namespace std;
int Fibonacci(int pos);
int main(){
int pos;
cin >> pos;
int value;
value = Fibonacci(pos);
cout << value << endl;
return 0;
}
int Fibonacci(int pos){
if (pos == 0){
return 0;
}else if (pos == 1){
return 1;
}
else{
return Fibonacci(pos - 1) + Fibonacci(pos - 2);
}
}```
###2. 矩阵翻转
晓萌最近在做一个翻转图片的应用，你可能也知道，图片其实是由一个个的点组成的。于是，晓萌想先做一个可以翻转矩阵的程序，来解决他问题的核心部分。
输入第一行包括由空格分开的整数M、N、T（0 < M < 200，0 < N < 200，T=0或1），其中M和N分别表示待处理矩阵的行数与列数，T为0时表示左右翻转，为1时表示上下翻转。
之后的M行，每行包括由空格分隔的N个整数，依次为输入矩阵的每一行的数据。
输出包括M行N列，每个数字之间用一个空格分隔，每一行行末均有一个空格，表示的是按照要求翻转后的矩阵。
include <iostream>
using namespace std;
int main(){
int row,col,lrud;
cin >> row >> col >> lrud;
int arr[row][col];
//i不能到5
for (int i=0; i<row; i++){
for(int j=0; j<col; j++){
cin >> arr[i][j];
}
}
//左右翻转
if (lrud == 0){
for (int i1=0; i1<row; i1++){
for (int j1=col-1; j1>=0; j1--){
cout << arr[i1][j1] << " ";
}
cout << endl;
}
}else if(lrud == 1){ //上下翻转
for (int i1=row-1; i1>=0; i1--){
for (int j1=0; j1<col; j1++){
cout << arr[i1][j1] << " ";
}
cout << endl;
}
}
}
###3. 位操作
include<iostream>
using namespace std;
int main(){
int a;
cin>>a;
//hex指输出16进制数，oct是八进制数，dec是十进制，bin二进制
cout << hex << a << " " << ~a << endl;
return 0;
}```
4. cstdio库
#include <cstdio>引入C风格的输入和输出，scanf和printf比cout和cin要高效。
5. 指针
一个指针是一个地址，是一个常量，而一个指针变量却可以被赋予不同的指针值，是变量。定义指针的目的是通过指针去访问内存单元。
指针变量的赋值只能被赋予地址数据，错误赋值将无法通过编译或者在运行中出错。变量的地址是系统分配，使用&进行取地址，*是指针运算符，间接访问运算符，通过指针变量存储的地址来访问变量。
#include<iostream>
using namespace std;
int main(){
int a = 0, b = 0, *p, *p1, *p2;
cin >> a >> b;
p1 = &a;
p2 = &b;
if (a<b){
p = p1;
p1 = p2;
p2 = p;
}
cout << "a=" << a << ",b=" << b << endl;
cout << "max=" << *p1 << ",min=" << *p2 << endl;
return 0;
}```
函数的形式参数是一个指针类型的变量，*表示指针变量的类型声明，square函数中的指针指向了主函数中的变量，square函数中的指针值的运算将改变主函数中变量num的值。
include<iostream>
using namespace std;
void square(int *n){
*n = *n * *n;
}
int main(){
int num = 2;
cout<<"The original number is "<<num<<endl;
square(&num);
cout<<"The new value of number is "<<num<<endl;
return 0;
}```
6. 引用
引用就是某一变量的一个别名，对引用的操作与对变量直接操作完全一样，定义引用的表示方法与定义指针类似，只是用&代替了*，例如int a,&ra=a，ra是目标引用名，ra=1;等价于a=1，并且&只是在声明的时候起标识作用，不同于取地址。
声明一个引用，不是新定义了一个变量，它本身不是一种数据类型。
不能建立引用的数组，无法建立一个由引用组成的集合，但是可以建立数组的引用。
下面是引用做函数参数的例子，同样和指针一样可以修改main中的变量值。
#include<iostream>
using namespace std;
void square(int &n){
n = n * n;
}
int main(){
int num = 2;
cout<<"The original number is "<<num<<endl;
square(num);
cout<<"The new value of number is "<<num<<endl;
return 0;
}```
###7. 内存分区
计算机中的内存在用于编程的时候，被人为的进行了分区，分为栈区stack，堆区heap，全局区(静态区Static)，文字常量区，程序代码区。
函数的参数值，局部变量值都被存在了栈区，这部分的内存是系统帮助来进行管理的。
堆区的内存，是由程序员来进行分配和释放的，使用堆内存的原因是栈上内存较少，不够用，系统管理内存的方式比较死板，不方便用。堆上的内存，程序员手动分配后，如果不释放就有可能出现内存泄漏。
全局变量和静态变量的存储是在一块的，初始化的全局变量和静态变量在一块区域，为初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
文字常量区用于储存常量字符串的，程序结束后由系统释放。
程序代码区用于存放函数体的二进制代码。
`int *arr = new int[n];` new用于申请堆上空间的运算符，申请空间的最开始位置首地址，用前面声明的指针进行指向，从而可以像用数组一样用指针名使用这块空间。
include<iostream>
using namespace std;
int main(){
int i,n;
cin>>n;
int *arr= new int[n];
//以下代码对一个数组第一位进行了赋值
arr[0]=1;
//以下代码对一个长度为n的数组第二位开始依次做计算，并输出最后一个值结果
for(i=1;i<n;i++){
arr[i]=arr[i-1]+i;
}
cout<<arr[n-1];
//请在下一行释放内存空间
delete []arr;
arr = NULL;
return 0;
}```
new来动态申请分配堆内存
申请单个对象
int *p;
p = new int;
//或者申请的堆内存中直接包含值
int *p;
p = new int(100);```
动态申请数组
int *p;
p = new int[n];```
圆括号是用来赋初值的，方括号是用来说明申请堆空间大小的。
内存释放
delete加指针名的形式进行释放，如果指针指向的空间是数组，那么需要在delete后加上[]进行标识。然后将arr指针数组指向NULL，使之成为空指针。
8. 链表
#include <iostream>
using namespace std;
struct List
{
int num;
List *next;
};
List *head;
void Insert(List *&head)
{
//在下面编写插入代码
List *node = NULL;
node = new List;
cin >> node->num;
node -> next = NULL;
List *q, *p;
//如果插入的值本身小于head的值，插入到最前面
if(node->num <= head->num){
node->next = head;
head = node;
return ;
}
p = head; //记录head指针
q = head->next; //记录指向head后面的
while(q!=NULL){
if(node->num > q->num){
//大于的话，判断下一个
p = q;
q = q->next;
}else{
break;
}
}
p->next = node;
node->next = q;
}
void deleteNode(List *&head)
{
//在下面编写删除代码
int num;
cin >> num;
List *p = NULL, *q = NULL;
p = head;
if(p->num == num){
head = p->next;
delete p;
return;
}
//如果删除的节点不是头节点
q = p->next;
while(q != NULL){
if(q->num == num){
p->next = q->next;
delete q;
return;
}
if(q->num > num){
return;
}
p = q;
q = q->next;
}
return ;
}
List *Create()
{
List *p = NULL;
List *q = NULL;
head = NULL;
for ( int i = 0; i < 3; i++ ) {
p = new List;
p->num = i * 2;
if ( head == NULL ) {
head = p;
}
else {
q->next = p;
}
q = p;
}
if ( head != NULL ) {
q->next = NULL;
}
return head;
}
void displayList(List *head)
{
while ( head != NULL ) {
cout << head->num;
head = head->next;
if ( head != NULL ) {
cout << "->";
}
}
cout << endl;
}
int main() {
Create();
Insert(head);
displayList(head);
return 0;
}```
###9. 单链表部分逆置
给定一个固定的单链表，输入两个数begin和end。将下标为begin到end之间的内容逆置。
给定的单链表为：0->2->4->6->8->10->12->14->16->18
测试数据确保begin和end不会超出单链表的长度范围，并且end>=begin
include <iostream>
using namespace std;
struct List
{
int num;
List *next;
};
List *head;
void reverse(int begin, int end, List *&head)
{
//在这个函数中编写你的代码
if(end <= begin || begin < 0 || end > 9){
return;
}
if(begin == 0){
List *p = head;
List *qian = p;
List *kai = p;
List *hou = NULL;
p = p->next;
for(int i=1;i<=end;i++){
hou = p;
p = p->next;
//开始转换
hou->next = qian;
qian = hou;
if(i == end){
kai->next = p;
head = hou;
}
}
}else{
//记录begin前面的指针，begin的指针，end处的，end后面的
//算法思想就是将链表指针逆过来
List *p = head;
//q 开始的前一个节点指针
List *q = NULL;
//qian 是两个节点进行逆序时第一个节点指针
//kai 是开始位置节点指针
//hou是逆序时候第二个节点指针
List *qian=NULL, *hou=NULL, *kai=NULL;
for(int i=0;i<=end;i++){
if(i == begin - 1){
q = p;
qian = p;
p = p -> next;
}else if (i >= begin){
if (i == begin){
kai = p;
}
hou = p;
p = p->next;
//这里进行两个节点之间的逆序
hou -> next = qian;
qian = hou;
if(i == end){
if(q == NULL){
head = hou;
}else{
//这里处理结束时候与链表其它位置交接的地方
q->next = hou;
kai->next = p;
}
}
}else{
p = p->next;
}
}
}
}
List *Create()
{
List *p = NULL;
List *q = NULL;
head = NULL;
for ( int i = 0; i < 10; i++ ) {
p = new List;
p->num = i * 2;
if ( head == NULL ) {
head = p;
}
else {
q->next = p;
}
q = p;
}
if ( head != NULL ) {
q->next = NULL;
}
return head;
}
void displayList(List *head)
{
while ( head != NULL ) {
cout << head->num;
head = head->next;
if ( head != NULL ) {
cout << "->";
}
}
cout << endl;
}
int main() {
Create();
int begin, end;
cin >> begin >> end;
reverse(begin, end, head);
displayList(head);
return 0;
}```
10. 单链表是否有环？
如果单链表里有重复的节点，则说明单链表中存在环
有一个链表，我们需要判断链表中是否存在环。有环则输出true，否则输出false。
输入有多行，每行为由空格分隔的两个整数m和n，m是当前结点的数据，n代表当前结点的指针域指向第n个结点。
n存在四种情形：
①为-1，代表该结点的指针域指向NULL，输入结束；
②指向该结点之前的结点，如第3个结点的指针域指向n = 2的结点；
③指向自己，如第3个结点的指针域指向n = 3的结点；
④指向其直接后继结点，如第3个结点的指针域指向n = 4的结点，不能指向n = 5的结点。
当输入为：
1 2
2 3
3 -1
时，代表：第1个结点的数据为1，指向第2个结点；第2个结点的数据为2，指向第3个结点；第3个结点的数据为3，指向NULL，输入结束。
下面是代码实现一个初步的算法，基本思想还是建立链表后，进行遍历，遍历过的节点置flag为1，如果以后遍历到flag==1的节点，那么就说明有环。
#include <iostream>
#include <vector>
using namespace std;
struct List{
int num;
int flag;
List *next;
};
//建立头指针
List *head = NULL;
int main(){
//建立输入动态数组
vector<int> data;
vector<int> pos;
vector<List *> point;
int m, n;
while(cin >> m >> n){
data.push_back(m);
pos.push_back(n);
}
for(int i=0;i<pos.size();i++){
List *node = NULL;
node = new List;
node->num = data[i];
node->flag = 0;
point.push_back(node);
}
head = point[0];
//建立链表
for(int j=0;j<pos.size();j++){
if(pos[j] != -1){
point[j]->next = point[pos[j]-1];
}else{
point[j]->next = NULL;
}
}
//遍历链表
int loop = 0;
List *p;
head->flag = 1;
cout << head->num << "->";
p = head->next;
while(p){
if(p->flag != 1){
cout << p->num << "->";
p->flag = 1;
}else{
loop = 1;
break;
}
p = p->next;
}
cout << endl;
if(loop == 1){
cout << "true" << endl;
}else{
cout << "false" << endl;
}
}```
###11. 面向对象Object Oriented Programming
首先是抽象特性，封装，继承，多态
C++对于类内的成员提供了三种访问权限，public，protected,private表示公有，保护和私有。
- public
表示其后定义的成员对程序所有部分可见，包括数据成员，成员函数以及类型。作为公有成员存在的大多是一些特定方式读取，修改数据成员的成员函数，类的接口。
- private
修饰成员时表示该成员仅在该类内可见，类外无法对这个成员进行访问。包括大部分变量，一些不需要类的使用者关注的用于具体运算过程的函数。
- protected
继承派生
通过对成员访问的控制，信息被封存在了一个可控的地方，可以设定一些安全的途径，获得和修改一些信息，这就是面向对象的一个特性，封装
include<iostream>
using namespace std;
class Student{
private:
int id;
int age;
public:
int getID(){return id;}
int getAge(){return age;}
//先进行声明,函数比较复杂，定义在类的外面
void setID(int newID);
void setAge(int newAge);
};
void Student::setID(int newID){
id = newID;
}
void Student::setAge(int newAge){
age = newAge<100?newAge:99;
}
int main(){
Student tom;
tom.setID(1);
tom.setAge(16);
cout<<tom.getID()<<" "<<tom.getAge();
return 0;
}```
