學(xué)習(xí)C++

1. 斐波納切數(shù)列

斐波那契數(shù)列是一種非常有意思的數(shù)列，由 00 和 11 開始，之后的斐波那契系數(shù)就由之前的兩數(shù)相加。用數(shù)學(xué)公式定義斐波那契數(shù)列則可以看成如下形式：
?Fn表示斐波那契數(shù)列的第n項，你能知道斐波那契數(shù)列中的任何一項嗎？

#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. 矩陣翻轉(zhuǎn)
曉萌最近在做一個翻轉(zhuǎn)圖片的應(yīng)用，你可能也知道，圖片其實(shí)是由一個個的點(diǎn)組成的。于是，曉萌想先做一個可以翻轉(zhuǎn)矩陣的程序，來解決他問題的核心部分。
輸入第一行包括由空格分開的整數(shù)M、N、T（0 < M < 200，0 < N < 200，T=0或1），其中M和N分別表示待處理矩陣的行數(shù)與列數(shù)，T為0時表示左右翻轉(zhuǎn)，為1時表示上下翻轉(zhuǎn)。
之后的M行，每行包括由空格分隔的N個整數(shù)，依次為輸入矩陣的每一行的數(shù)據(jù)。
輸出包括M行N列，每個數(shù)字之間用一個空格分隔，每一行行末均有一個空格，表示的是按照要求翻轉(zhuǎ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];
}
}
//左右翻轉(zhuǎn)
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){ //上下翻轉(zhuǎn)
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進(jìn)制數(shù)，oct是八進(jìn)制數(shù)，dec是十進(jìn)制，bin二進(jìn)制
cout << hex << a << " " << ~a << endl;
return 0;
}```

4. cstdio庫

#include <cstdio>引入C風(fēng)格的輸入和輸出，scanf和printf比cout和cin要高效。

5. 指針

一個指針是一個地址，是一個常量，而一個指針變量卻可以被賦予不同的指針值，是變量。定義指針的目的是通過指針去訪問內(nèi)存單元。
指針變量的賦值只能被賦予地址數(shù)據(jù)，錯誤賦值將無法通過編譯或者在運(yùn)行中出錯。變量的地址是系統(tǒng)分配，使用&進(jìn)行取地址，*是指針運(yùn)算符，間接訪問運(yùn)算符，通過指針變量存儲的地址來訪問變量。

#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;
}```
函數(shù)的形式參數(shù)是一個指針類型的變量，*表示指針變量的類型聲明，square函數(shù)中的指針指向了主函數(shù)中的變量，square函數(shù)中的指針值的運(yùn)算將改變主函數(shù)中變量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是目標(biāo)引用名，ra=1;等價于a=1，并且&只是在聲明的時候起標(biāo)識作用，不同于取地址。
聲明一個引用，不是新定義了一個變量，它本身不是一種數(shù)據(jù)類型。
不能建立引用的數(shù)組，無法建立一個由引用組成的集合，但是可以建立數(shù)組的引用。
下面是引用做函數(shù)參數(shù)的例子，同樣和指針一樣可以修改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. 內(nèi)存分區(qū)
計算機(jī)中的內(nèi)存在用于編程的時候，被人為的進(jìn)行了分區(qū)，分為棧區(qū)stack，堆區(qū)heap，全局區(qū)(靜態(tài)區(qū)Static)，文字常量區(qū)，程序代碼區(qū)。
函數(shù)的參數(shù)值，局部變量值都被存在了棧區(qū)，這部分的內(nèi)存是系統(tǒng)幫助來進(jìn)行管理的。
堆區(qū)的內(nèi)存，是由程序員來進(jìn)行分配和釋放的，使用堆內(nèi)存的原因是棧上內(nèi)存較少，不夠用，系統(tǒng)管理內(nèi)存的方式比較死板，不方便用。堆上的內(nèi)存，程序員手動分配后，如果不釋放就有可能出現(xiàn)內(nèi)存泄漏。
全局變量和靜態(tài)變量的存儲是在一塊的，初始化的全局變量和靜態(tài)變量在一塊區(qū)域，為初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域。程序結(jié)束后由系統(tǒng)釋放。
文字常量區(qū)用于儲存常量字符串的，程序結(jié)束后由系統(tǒng)釋放。
程序代碼區(qū)用于存放函數(shù)體的二進(jìn)制代碼。
`int *arr = new int[n];` new用于申請堆上空間的運(yùn)算符，申請空間的最開始位置首地址，用前面聲明的指針進(jìn)行指向，從而可以像用數(shù)組一樣用指針名使用這塊空間。

include<iostream>

using namespace std;
int main(){
int i,n;
cin>>n;
int *arr= new int[n];

//以下代碼對一個數(shù)組第一位進(jìn)行了賦值
arr[0]=1;

//以下代碼對一個長度為n的數(shù)組第二位開始依次做計算，并輸出最后一個值結(jié)果
for(i=1;i<n;i++){
    arr[i]=arr[i-1]+i;
}
cout<<arr[n-1];
//請在下一行釋放內(nèi)存空間
delete []arr;
    arr = NULL;
return 0;

}```
new來動態(tài)申請分配堆內(nèi)存
申請單個對象

int *p;
p = new int;
//或者申請的堆內(nèi)存中直接包含值
int *p;
p = new int(100);```
動態(tài)申請數(shù)組

int *p;
p = new int[n];```
圓括號是用來賦初值的，方括號是用來說明申請堆空間大小的。
內(nèi)存釋放
delete加指針名的形式進(jìn)行釋放，如果指針指向的空間是數(shù)組，那么需要在delete后加上[]進(jìn)行標(biāo)識。然后將arr指針數(shù)組指向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;
    }
    //如果刪除的節(jié)點(diǎn)不是頭節(jié)點(diǎn)
    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. 單鏈表部分逆置
給定一個固定的單鏈表，輸入兩個數(shù)begin和end。將下標(biāo)為begin到end之間的內(nèi)容逆置。

給定的單鏈表為：0->2->4->6->8->10->12->14->16->18

測試數(shù)據(jù)確保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)
{
//在這個函數(shù)中編寫你的代碼
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;
//開始轉(zhuǎn)換
hou->next = qian;
qian = hou;
if(i == end){
kai->next = p;
head = hou;
}
}
}else{
//記錄begin前面的指針，begin的指針，end處的，end后面的
//算法思想就是將鏈表指針逆過來
List *p = head;
//q 開始的前一個節(jié)點(diǎn)指針
List *q = NULL;
//qian 是兩個節(jié)點(diǎn)進(jìn)行逆序時第一個節(jié)點(diǎn)指針
//kai 是開始位置節(jié)點(diǎn)指針
//hou是逆序時候第二個節(jié)點(diǎn)指針
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;
//這里進(jìn)行兩個節(jié)點(diǎn)之間的逆序
hou -> next = qian;
qian = hou;
if(i == end){
if(q == NULL){
head = hou;
}else{
//這里處理結(jié)束時候與鏈表其它位置交接的地方
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. 單鏈表是否有環(huán)？

如果單鏈表里有重復(fù)的節(jié)點(diǎn)，則說明單鏈表中存在環(huán)
有一個鏈表，我們需要判斷鏈表中是否存在環(huán)。有環(huán)則輸出true，否則輸出false。

輸入有多行，每行為由空格分隔的兩個整數(shù)m和n，m是當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，n代表當(dāng)前結(jié)點(diǎn)的指針域指向第n個結(jié)點(diǎn)。

n存在四種情形：
①為-1，代表該結(jié)點(diǎn)的指針域指向NULL，輸入結(jié)束；
②指向該結(jié)點(diǎn)之前的結(jié)點(diǎn)，如第3個結(jié)點(diǎn)的指針域指向n = 2的結(jié)點(diǎn)；
③指向自己，如第3個結(jié)點(diǎn)的指針域指向n = 3的結(jié)點(diǎn)；
④指向其直接后繼結(jié)點(diǎn)，如第3個結(jié)點(diǎn)的指針域指向n = 4的結(jié)點(diǎn)，不能指向n = 5的結(jié)點(diǎn)。

當(dāng)輸入為：
1 2
2 3
3 -1
時，代表：第1個結(jié)點(diǎn)的數(shù)據(jù)為1，指向第2個結(jié)點(diǎn)；第2個結(jié)點(diǎn)的數(shù)據(jù)為2，指向第3個結(jié)點(diǎn)；第3個結(jié)點(diǎn)的數(shù)據(jù)為3，指向NULL，輸入結(jié)束。
下面是代碼實(shí)現(xiàn)一個初步的算法，基本思想還是建立鏈表后，進(jìn)行遍歷，遍歷過的節(jié)點(diǎn)置flag為1，如果以后遍歷到flag==1的節(jié)點(diǎn)，那么就說明有環(huán)。

#include <iostream>
#include <vector>
using namespace std;

struct List{
    int num;
    int flag;
    List *next;
};

//建立頭指針
List *head = NULL;

int main(){
    //建立輸入動態(tài)數(shù)組
    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. 面向?qū)ο驩bject Oriented Programming
首先是抽象特性，封裝，繼承，多態(tài)
C++對于類內(nèi)的成員提供了三種訪問權(quán)限，public，protected,private表示公有，保護(hù)和私有。
  - public
表示其后定義的成員對程序所有部分可見，包括數(shù)據(jù)成員，成員函數(shù)以及類型。作為公有成員存在的大多是一些特定方式讀取，修改數(shù)據(jù)成員的成員函數(shù)，類的接口。
  - private
修飾成員時表示該成員僅在該類內(nèi)可見，類外無法對這個成員進(jìn)行訪問。包括大部分變量，一些不需要類的使用者關(guān)注的用于具體運(yùn)算過程的函數(shù)。
  - protected
繼承派生

  通過對成員訪問的控制，信息被封存在了一個可控的地方，可以設(shè)定一些安全的途徑，獲得和修改一些信息，這就是面向?qū)ο蟮囊粋€特性，封裝

include<iostream>

using namespace std;
class Student{
private:
int id;
int age;
public:
int getID(){return id;}
int getAge(){return age;}
//先進(jìn)行聲明,函數(shù)比較復(fù)雜，定義在類的外面
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;
}```