c++基礎概念有哪些

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

第1節：數據結構概述

數據結構的主要任務是通過分析數據對象的結構特征，包括邏輯結構及數據對象之間的關系，然后把邏輯結構表示成計算機課實現的物理結構，從而便于計算機處理。

1.1 概念術語

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

（2）數據元素（data element）是數據的基本單位。例如一張學生統計表。

（3）數據項（data item）組成數據元素的最小單位。例如一張學生統計表，有編號、姓名、性別、籍貫等數據項。

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

（5）數據結構（data structure）是數據的組織形式，數據元素之間存在的一種或多種特定關系的數據元素集合。

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

1.2 數據的邏輯結構

邏輯結構（logical structure）是指在數據中數據元素之間的相互關系。數據元素之間存在不同的邏輯關系構成了以下4種結構類型。

（1）集合結構：集合的數據元素沒有其他關系，僅僅是因為他們擠在一個被稱作“集合”的盒子里。

（2）線性結構：線性的數據元素結構關系是一對一的，并且是一種先后的次序，就像a-b-c-d-e-f-g·····被一根線穿連起來。

（3）樹形結構：樹形的數據元素結構關系是一對多的，這就像公司的部門級別，董事長-CEO\CTO-技術部\人事部\市場部.....。

（4）圖結構：圖的數據元素結構關系是多對多的。就是我們常見的各大城市的鐵路圖，一個城市有很多線路連接不同城市。

1.3 數據的存儲（物理）結構

存儲結構（storage structure）也稱為物理結構（physical structure），指的是數據的邏輯結構在計算機中的存儲形式。

數據的存儲結構一般可以反映數據元素之間的邏輯關系。分為順序存儲結構和鏈式存儲結構。

（1）順序存儲結構：是把數據元素存放在一組存儲地址連續的存儲單元里，其數據元素間的邏輯關系和物理關系是一致的。

（2）鏈式存儲結果：是把數據元素存放在任意的存儲單元里，這組存儲單元可以是連續的，也可以是不連續的，數據元素的存儲關系并不能反映其邏輯關系，因此需要借助指針來表示數據元素之間的邏輯關系。

小結：

數據的邏輯結構和物理結構是密切相關的，在學習數據的過程中會發現，任何一個算法的設計取決于選定的數據邏輯結構，而算法的實現依賴于所采用的存儲結構。

1.4 抽象數據類型

抽象數據類型（abstract data type，ADT）是描述具有某種邏輯關系的數據模型，并對在數學模型上進行的一組操作。

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

“抽象”的意思是數據類型的數學抽象特性而不是指它們的實現方法。

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

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

1.5 算法

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

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

（1）數據結構和算法的關系

兩者基友聯系又有區別。聯系是程序=算法+數據結構。數據結構是算法實現的基礎，算法總是要依賴某種數據結構來實現的。

算法的操作對象是數據結構。區別是數據結構關注的是數據的邏輯結構、存儲結構及其基本操作，而算法更多的是關注如何在數據結構的基本上解決實際問題。

算法是編程思想，數據結構則是這些思想的基礎。

（2）算法的五大特性

有窮性，是指算法在執行有限的步驟之后，自動結束而不是出現無限循環，并且每一個步驟在可接受的時間內完成。

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

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

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

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

1.6 時間復雜度

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

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

例如：

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

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

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

1.7 空間復雜度

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

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

第2節：C語言基礎

C語言作為數據結構的算法描述語言，廣泛應用于系統軟件和應用軟件的開發。在真正開發學習數據結構知識之前，先復習一下C語言基礎，為數據結構的學習掃清障礙。本節主要針對重點和難點部分詳細講解，包括開發環境、函數與遞歸、指針、參數傳遞、動態內存分配及結構體、聯合體。

2.1 開發環境

C語言常見的開發環境有很多種，如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程序集成開發環境。界面簡單、上手容易、使用方便，通過一個簡單的主界面可以很容易編輯、編譯和鏈接程序，也是初學者廣發使用的開發工具。

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

2.2 遞歸與非遞歸（重點）

在數據結構與算法實踐過程中，經常會遇到利用遞歸實現算法的情況。遞歸是一種分而治之、將復雜問題轉換成簡單問題的求解方法。使用遞歸可以使編寫的程序簡潔、結構清晰，程序的正確性很容易證明，不需要了解遞歸調用的具體細節。

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

例1：利用遞歸求n! ：有兩種情況，當n=0遞歸結束，返回值為1 ；當n !=0時，繼續遞歸。

//遞歸求n！函數實現

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

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

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）迭代與遞歸

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

（3）指針

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

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

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

2.3 參數傳遞

（1）傳值調用：分為實際參數和形式參數。例如：

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

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

（2）傳指針地址參數：略

2.4 結構體和聯合體

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

//結構體類型
struct teacher{
    //數據項
    int no;
    char name[20];
    char sex[4];
    char headship[8];
    char degree[6];
    long int phone;
}

與結構體一樣，聯合體也是一種派生的數據類型。但是與結構體不同的是，聯合體的成員共享同一個存儲空間。定義聯合體一般形式如下所示。

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

2.5 鏈表

在C語言中，處理已知數據可以使用數組。如果事先并不知道要處理的數據的個數，則需要使用鏈表結構。鏈表需要動態分配內存，鏈表的長度隨時可以發生變化。鏈表有一個指針類型的成員指向自身，該指針指向與結構體一樣的類型。例如如下語句：

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

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

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

2.6 內存的分配與釋放

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

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

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