c++基礎(chǔ)概念有哪些

今天小編給大家分享一下c++基礎(chǔ)概念有哪些的相關(guān)知識點，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

第1節(jié)：數(shù)據(jù)結(jié)構(gòu)概述

數(shù)據(jù)結(jié)構(gòu)的主要任務(wù)是通過分析數(shù)據(jù)對象的結(jié)構(gòu)特征，包括邏輯結(jié)構(gòu)及數(shù)據(jù)對象之間的關(guān)系，然后把邏輯結(jié)構(gòu)表示成計算機課實現(xiàn)的物理結(jié)構(gòu)，從而便于計算機處理。

1.1 概念術(shù)語

（1）數(shù)據(jù)（Data）是能被計算機處理的符號或符號集合，含義廣泛，可理解為“原材料”。如字符、圖片、音視頻等。

（2）數(shù)據(jù)元素（data element）是數(shù)據(jù)的基本單位。例如一張學(xué)生統(tǒng)計表。

（3）數(shù)據(jù)項（data item）組成數(shù)據(jù)元素的最小單位。例如一張學(xué)生統(tǒng)計表，有編號、姓名、性別、籍貫等數(shù)據(jù)項。

（4）數(shù)據(jù)對象（data object）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如正整數(shù)N={1，2，3，····}。

（5）數(shù)據(jù)結(jié)構(gòu)（data structure）是數(shù)據(jù)的組織形式，數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素集合。

（6）數(shù)據(jù)類型（data type）是按照數(shù)據(jù)值的不同進(jìn)行劃分的可操作性。在C語言中還可以分為原子類型和結(jié)構(gòu)類型。原字類型是不可以再分解的基本類型，包括整型、實型、字符型等。結(jié)構(gòu)類型是由若干個類型組合而成，是可以再分解的。

1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)（logical structure）是指在數(shù)據(jù)中數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)元素之間存在不同的邏輯關(guān)系構(gòu)成了以下4種結(jié)構(gòu)類型。

（1）集合結(jié)構(gòu)：集合的數(shù)據(jù)元素沒有其他關(guān)系，僅僅是因為他們擠在一個被稱作“集合”的盒子里。

（2）線性結(jié)構(gòu)：線性的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是一對一的，并且是一種先后的次序，就像a-b-c-d-e-f-g·····被一根線穿連起來。

（3）樹形結(jié)構(gòu)：樹形的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是一對多的，這就像公司的部門級別，董事長-CEO\CTO-技術(shù)部\人事部\市場部.....。

（4）圖結(jié)構(gòu)：圖的數(shù)據(jù)元素結(jié)構(gòu)關(guān)系是多對多的。就是我們常見的各大城市的鐵路圖，一個城市有很多線路連接不同城市。

1.3 數(shù)據(jù)的存儲（物理）結(jié)構(gòu)

存儲結(jié)構(gòu)（storage structure）也稱為物理結(jié)構(gòu)（physical structure），指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式。

數(shù)據(jù)的存儲結(jié)構(gòu)一般可以反映數(shù)據(jù)元素之間的邏輯關(guān)系。分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

（1）順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在一組存儲地址連續(xù)的存儲單元里，其數(shù)據(jù)元素間的邏輯關(guān)系和物理關(guān)系是一致的。

（2）鏈?zhǔn)酱鎯Y(jié)果：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，數(shù)據(jù)元素的存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

小結(jié)：

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的，在學(xué)習(xí)數(shù)據(jù)的過程中會發(fā)現(xiàn)，任何一個算法的設(shè)計取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。

1.4 抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（abstract data type，ADT）是描述具有某種邏輯關(guān)系的數(shù)據(jù)模型，并對在數(shù)學(xué)模型上進(jìn)行的一組操作。

抽象數(shù)據(jù)類型描述的是一組邏輯上的特性，與在計算機內(nèi)部表示無關(guān)，計算機中的整數(shù)數(shù)據(jù)類型是一個抽象數(shù)據(jù)類型，不同處理器可能實現(xiàn)方法不同，但其邏輯特性相同，即加、減、乘、除等運算是一致的。

“抽象”的意思是數(shù)據(jù)類型的數(shù)學(xué)抽象特性而不是指它們的實現(xiàn)方法。

抽象數(shù)據(jù)類型體現(xiàn)了程序設(shè)計中的問題分解、抽象、信息隱藏等特性，可以把現(xiàn)實中的大問題分解為多個規(guī)模小且容易處理的小問題，然后建立起一個能被計算機處理的數(shù)據(jù)，并把每個功能模塊的實現(xiàn)細(xì)節(jié)作為一個獨立的單元，從而使具體實現(xiàn)過程隱藏起來。
就類似建一棟房子，分成若干個小任務(wù)，如地皮規(guī)劃、圖紙設(shè)計、施工、裝修等，整個過程與抽象數(shù)據(jù)類型中的問題分解類似。而搬磚人不需要了解圖紙設(shè)計如何，設(shè)計圖紙人員不需要了解施工的地基、砌墻的具體細(xì)節(jié)，裝修工人不用關(guān)心圖紙和搬磚過程，這就是抽象類型中的信息隱藏。

抽象數(shù)據(jù)類型的概念可能讓初學(xué)者不太容易理解。例如線性表的抽象數(shù)據(jù)類型的描述數(shù)據(jù)對象集合：線性表的數(shù)據(jù)對象集合為{a1,a2,a3,····,an},每個元素的類型均為DataType。其中，除了第一個元素a1外，每一個元素有且只有一個直接前驅(qū)元素；除了最后一個元素an外，每一個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一的。

1.5 算法

算法（algorithm）是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為有限的操作序列。

在數(shù)據(jù)類型建立起來之后，就要對這些數(shù)據(jù)類型進(jìn)行操作，建立起運算的集合即程序。運算的建立、方法好壞直接決定著計算機程序原型效率的高低。

（1）數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系

兩者基友聯(lián)系又有區(qū)別。聯(lián)系是程序=算法+數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是算法實現(xiàn)的基礎(chǔ)，算法總是要依賴某種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的。

算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。區(qū)別是數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基本上解決實際問題。

算法是編程思想，數(shù)據(jù)結(jié)構(gòu)則是這些思想的基礎(chǔ)。

（2）算法的五大特性

有窮性，是指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不是出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。

確定性，是指算法執(zhí)行的每一步驟在一定條件下只有一條執(zhí)行路徑，也就是相同輸入只能有一個唯一的輸出結(jié)果。

可行性，是指算法每一步驟都必須可行，能夠通過有限的執(zhí)行次數(shù)完成。

輸入，是指算法具有零個或多個輸入。

輸出，是指算法至少有一個或多個輸出。

1.6 時間復(fù)雜度

在進(jìn)行算法分析時，語句總是執(zhí)行次數(shù) T(n) 是關(guān)于問題規(guī)模 n 的函數(shù)。進(jìn)而分析次數(shù)T(n)隨規(guī)模n的變化情況并確定T(n)的數(shù)量級。算法的時間復(fù)雜度就是算法的時間度量，記作T(n) = O（f（n））。它表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f（n）的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱為時間復(fù)雜度。其中，f（n）是問題規(guī)模n的某個函數(shù)。

算法的時間復(fù)雜度是衡量一個算法好壞的重要指標(biāo)。一般情況下，隨著規(guī)模n的增大，次數(shù)T(n)的增長較慢的算法為最優(yōu)算法。常見時間復(fù)雜度從小到大依次排列：O(1) < O(log2n) < O(n) < O(n2）<O(n3) ····<O(n!)

例如：

(a) 1; // 時間復(fù)雜度為O(1)

(b) for(i =1 ; i<=n ;i++){ x= x+1;} // 時間復(fù)雜度為O(n)，稱為線性階

(c) for(i =1 ; i<=n ; i++）{for(j=1;j<=n;j++){ x=x+1 } } // 時間復(fù)雜度為O(n2),稱為平方階

1.7 空間復(fù)雜度

空間復(fù)雜度（space complexity）作為算法所需存儲空間的量度，記做S(n) = O (f(n))。其中，n為問題的規(guī)模；f（n）為語句關(guān)于n的所占存儲空間的函數(shù)。

一般情況下，一個程序在機器上運行時，除了需要存儲程序本身的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要存儲對數(shù)據(jù)操作的存儲單位。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，這樣只需要分析該算法在實現(xiàn)時所需的輔助單元即可。若算法執(zhí)行時所需的輔助空間相對于輸入數(shù)據(jù)量而言是個常量，則稱此算法為原地工作，空間復(fù)雜度為O(1)。

第2節(jié)：C語言基礎(chǔ)

C語言作為數(shù)據(jù)結(jié)構(gòu)的算法描述語言，廣泛應(yīng)用于系統(tǒng)軟件和應(yīng)用軟件的開發(fā)。在真正開發(fā)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識之前，先復(fù)習(xí)一下C語言基礎(chǔ)，為數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)掃清障礙。本節(jié)主要針對重點和難點部分詳細(xì)講解，包括開發(fā)環(huán)境、函數(shù)與遞歸、指針、參數(shù)傳遞、動態(tài)內(nèi)存分配及結(jié)構(gòu)體、聯(lián)合體。

2.1 開發(fā)環(huán)境

C語言常見的開發(fā)環(huán)境有很多種，如LCC、Turbo C2.0、Visual C++、Borland C++，本章主要介紹使用最多的Turbo C 2.0和Visual C++ 6.0。

（1）Turbo C 2.0 ：1989年，美國Borland公司推出,簡稱TC。它集編輯、編譯、連接和運行一體的C程序集成開發(fā)環(huán)境。界面簡單、上手容易、使用方便，通過一個簡單的主界面可以很容易編輯、編譯和鏈接程序，也是初學(xué)者廣發(fā)使用的開發(fā)工具。

（2）Visual C++6.0：是強大的C/C++軟件開發(fā)工具，使用非常廣泛，已經(jīng)成為首選的開發(fā)工具。利用它可以開發(fā)Windows SDK、MFC等應(yīng)用程序。

2.2 遞歸與非遞歸（重點）

在數(shù)據(jù)結(jié)構(gòu)與算法實踐過程中，經(jīng)常會遇到利用遞歸實現(xiàn)算法的情況。遞歸是一種分而治之、將復(fù)雜問題轉(zhuǎn)換成簡單問題的求解方法。使用遞歸可以使編寫的程序簡潔、結(jié)構(gòu)清晰，程序的正確性很容易證明，不需要了解遞歸調(diào)用的具體細(xì)節(jié)。

（1）函數(shù)的遞歸：就是函數(shù)自己調(diào)用自己，即一個函數(shù)在調(diào)用其他函數(shù)的過程中，又出現(xiàn)對自身的調(diào)用，這種函數(shù)稱為遞歸函數(shù)。函數(shù)的遞歸調(diào)用就是自己調(diào)用自己，可以直接調(diào)用自己也可以間接調(diào)用。其中，在函數(shù)中直接調(diào)用自己稱為函數(shù)的直接遞歸調(diào)用；如果函數(shù)f1調(diào)用了函數(shù)f2又再次調(diào)用了函數(shù)f1，這種調(diào)用的方式我們稱之為間接遞歸調(diào)用。

例1：利用遞歸求n! ：有兩種情況，當(dāng)n=0遞歸結(jié)束，返回值為1 ；當(dāng)n !=0時，繼續(xù)遞歸。

//遞歸求n！函數(shù)實現(xiàn)

int factorial (int  n) {
   if(n ==0 )
       return 1;
   else
       return n*factorial(n-1);
}

例2：已知有數(shù)組a[] ，要求利用遞歸實現(xiàn)求n個數(shù)中的最大值。

a[] ={0,···，n-1}；
int findMax(int a[] ,int n) {
    int  m ;
    if (n<=1)
        return a[0];
    else
    {
        m = findMax(a, n-1);
        return a[n-1] >= m ? a[n-1] : m ; //找到最大值
    }
}

（2）迭代與遞歸

迭代與遞歸是程序設(shè)計中最常用的兩種結(jié)構(gòu)。任何能使用遞歸解決的問題都能使用迭代的方法解決。迭代和遞歸的區(qū)別是，迭代使用的是循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)。大量的遞歸會耗費大量的時間和內(nèi)存，每次遞歸調(diào)用都會建立函數(shù)的一個備份，會占用大量的內(nèi)存空間。迭代則不需要反復(fù)調(diào)用函數(shù)和占用額外的內(nèi)存。對于較為簡單的遞歸問題，可以利用簡單的迭代將其轉(zhuǎn)化為非遞歸。而對于較為復(fù)雜的遞歸問題，需要通過利用數(shù)據(jù)結(jié)構(gòu)中的棧來消除遞歸。

（3）指針

是C語言中一個重要概念，也是最不容易掌握的內(nèi)容。指針常常用在函數(shù)的參數(shù)傳遞和動態(tài)內(nèi)存分配中。指針與數(shù)組相結(jié)合，使引用數(shù)組成分的形式更加多樣化，訪問數(shù)組元素的手段更加靈活；指針與結(jié)構(gòu)體結(jié)合，利用系統(tǒng)提供的動態(tài)存儲手段，能構(gòu)造出各種復(fù)雜的動態(tài)數(shù)據(jù)結(jié)構(gòu)；利用指針形參，使函數(shù)能實現(xiàn)傳遞地址形參和函數(shù)形參的要求。接下里會介紹指針變量的概念、指針與數(shù)組、函數(shù)指針與指針函數(shù)。

指針是一種變量，也稱之為指針變量，它的值不是整數(shù)、浮點數(shù)和字符，而是內(nèi)存地址。指針的值就是變量的地址，而變量又擁有一個具體的值。因此，可以理解為變量名直接引用了一個值，指針間接地引用了一個值。

指針可以與變量結(jié)合，也可以與數(shù)組結(jié)合使用。指針數(shù)組是一種存放一組變量的地址。數(shù)組指針是一個指針，表示該指針指向數(shù)組的指針。數(shù)組指針可以進(jìn)行自增或自減運算，但是數(shù)組名則不能進(jìn)行自增或自減運算，這是因為數(shù)組名是一個常量指針，它是一個常量，常量值是不能改變的。函數(shù)指針與指針函數(shù)同理。

2.3 參數(shù)傳遞

（1）傳值調(diào)用：分為實際參數(shù)和形式參數(shù)。例如：

int GCD（int m ,int n）;
 
void main(){
    int a,b,v,
    v = GCD(a,b);  //實際參數(shù)
}
 
int GCD(int m ,int n) { //形式參數(shù)
    int r;
    r = m;
    do {
        m=n;
        n=r;
        r=m&n;
      } while(r);
 
    return n;
}

上面的函數(shù)參數(shù)傳遞屬于參數(shù)的單向傳遞，即a和b可以把值傳遞給m和n，而不是可以把m和n傳遞給a和b。實際參數(shù)和形式參數(shù)的值的改變都不會互相收到影響。

（2）傳指針地址參數(shù)：略

2.4 結(jié)構(gòu)體和聯(lián)合體

也稱共用體，是自定義的數(shù)據(jù)類型，用于構(gòu)造非數(shù)值數(shù)據(jù)類型，在處理實際問題中應(yīng)用非常廣泛。數(shù)據(jù)結(jié)構(gòu)中的鏈表、隊列、樹、圖等結(jié)構(gòu)都需要用到結(jié)構(gòu)體。教師表結(jié)構(gòu)體如下所示。

//結(jié)構(gòu)體類型
struct teacher{
    //數(shù)據(jù)項
    int no;
    char name[20];
    char sex[4];
    char headship[8];
    char degree[6];
    long int phone;
}

與結(jié)構(gòu)體一樣，聯(lián)合體也是一種派生的數(shù)據(jù)類型。但是與結(jié)構(gòu)體不同的是，聯(lián)合體的成員共享同一個存儲空間。定義聯(lián)合體一般形式如下所示。

union 共用體名 {
    成員列表；
}
變量列表；
 
——————————————————————————
union data{
 
    int a ;
    float b;
    char c;
    double d;
}abc;
 
//或?qū)懗?
union data{
    int a;
    float b;
    char c;
    double d;
};
union data abc;

2.5 鏈表

在C語言中，處理已知數(shù)據(jù)可以使用數(shù)組。如果事先并不知道要處理的數(shù)據(jù)的個數(shù)，則需要使用鏈表結(jié)構(gòu)。鏈表需要動態(tài)分配內(nèi)存，鏈表的長度隨時可以發(fā)生變化。鏈表有一個指針類型的成員指向自身，該指針指向與結(jié)構(gòu)體一樣的類型。例如如下語句：

struct node{
    int data;
    struct data *next;
}

自引用結(jié)構(gòu)體類型為struct node，該結(jié)構(gòu)體類型有兩個成員：整數(shù)成員data，指針成員next。成員next是指向結(jié)構(gòu)體為struct node類型的指針。通過這種形式定義的結(jié)構(gòu)體通過next指針把兩個結(jié)構(gòu)體變量連在一起。這種自引用結(jié)構(gòu)體單元稱為結(jié)點，結(jié)點之間通過箭頭連接起來，構(gòu)成一張表，稱為鏈表。

鏈表中第一個結(jié)點的指針稱為頭指針且可以訪問鏈表的每一個結(jié)點。為了方便操作，在鏈表的第一個結(jié)點之前增加一個頭結(jié)點。

2.6 內(nèi)存的分配與釋放

（1）malloc函數(shù)主要作用是分配一塊長度為size的內(nèi)存空間。
void *malloc(unsigned int size); 其中，size就是要分配的內(nèi)存空間大小字節(jié)。使用時最好先檢查一下是否分配成功，否則返回null，可以保證程序的正確運行。使用完分配后的空間要利用free函數(shù)及時釋放。

（2）free函數(shù)主要作用是將內(nèi)存空間釋放。
void free (void *p); 其中，參數(shù)p指向要釋放的內(nèi)存空間。不能使用已經(jīng)被free函數(shù)釋放的內(nèi)存空間。

以上就是“c++基礎(chǔ)概念有哪些”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。