c語法和數據結構的基本知識?文章取材于博客園丨web前端社區，有部分修改，圖片來源于網絡，希望對大家有幫助，下面我們就來聊聊關于c語法和數據結構的基本知識?接下來我們就一起去了解一下吧!

c語法和數據結構的基本知識

文章取材于博客園丨web前端社區，有部分修改，圖片來源于網絡，希望對大家有幫助

從邏輯結構上來看，數組必須實現定于固定的長度，不能适應數據動态增減的情況，即數組的大小一旦定義就不能改變。當數據增加是，可能超過原先定義的元素的個數；當數據減少時，造成内存浪費；鍊表動态進行存儲分配，可以适應數據動态地增減的情況，且可以方便地插入、删除數據項。

從内存存儲的角度看；數組從棧中分配空間（用new則在堆上創建），對程序員方便快速，但是自由度小；鍊表從堆中分配空間，自由度大但是申請管理比較麻煩。

從訪問方式類看，數組在内存中是連續的存儲，因此可以利用下标索引進行訪問；鍊表是鍊式存儲結構，在訪問元素時候隻能夠通過線性方式由前到後順序的訪問，所以訪問效率比數組要低。

掌握所有常見的排序算法的手寫實現，以及複雜度相關細節知識。

選擇一個基準元素,通常選擇第一個元素或者最後一個元素,

通過一趟排序将待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值比基準值大。

此時基準元素在其排好序後的正确位置

然後分别對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。

3.1 時間複雜度來說

（1）平方階(O(n2))排序

各類簡單排序:直接插入、直接選擇和冒泡排序；

（2）線性對數階(O(nlog2n))排序

快速排序、堆排序和歸并排序；

（3）O(n1 §))排序,§是介于0和1之間的常數。

希爾排序

（4）線性階(O(n))排序

基數排序，此外還有桶、箱排序。

說明：

當原表有序或基本有序時，直接插入排序和冒泡排序将大大減少比較次數和移動記錄的次數，時間複雜度可降至O（n）；

而快速排序則相反，當原表基本有序時，将蛻化為冒泡排序，時間複雜度提高為O（n2）；

原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數排序的時間複雜度影響不大。

3.2 穩定性

排序算法的穩定性:若待排序的序列中，存在多個具有相同關鍵字的記錄，經過排序，這些記錄的相對次序保持不變，則稱該算法是穩定的；若經排序後，記錄的相對次序發生了改變，則稱該算法是不穩定的。

3.2.1 穩定的排序算法

冒泡排序、插入排序、歸并排序和基數排序

3.2.2 不是穩定的排序算法

選擇排序、快速排序、希爾排序、堆排序

3.3 選擇排序算法準則

一般而言，需要考慮的因素有以下幾點：

設待排序元素的個數為n.

（1）當n較大，則應采用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。

（2）當n較大，内存空間允許，且要求穩定性：歸并排序

（3）當n較小，可采用直接插入或直接選擇排序。

直接插入排序：當元素分布有序，直接插入排序将大大減少比較次數和移動記錄的次數。

直接選擇排序 ：元素分布有序，如果不要求穩定性，選擇直接選擇排序

（4）一般不使用或不直接使用傳統的冒泡排序。

（5）基數排序

它是一種穩定的排序算法，但有一定的局限性：

a.關鍵字可分解。

b.記錄的關鍵字位數較少，如果密集更好

c.如果是數字時，最好是無符号的

需要對HashTable的底層實現有深入的理解，知道哈希沖突的産生原因和解決方法。

哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。

1） 線性探測法

2） 平方探測法

3） 僞随機序列法

4） 拉鍊法

如果對數據庫有了解的話，該知識點需要深入理解。

根據B類樹的特點，構造一個多階的B類樹，然後在盡量多的在結點上存儲相關的信息，保證層數盡量的少，以便後面我們可以更快的找到信息，磁盤的I/O操作也少一些，而且B類樹是平衡樹，每個結點到葉子結點的高度都是相同，這也保證了每個查詢是穩定的。

B樹和B 樹的區别，以一個m階樹為例。

（1）關鍵字的數量不同；B 樹中分支結點有m個關鍵字，其葉子結點也有m個，其關鍵字隻是起到了一個索引的作用，但是B樹雖然也有m個子結點，但是其隻擁有m-1個關鍵字。

（2）存儲的位置不同；B 樹中的數據都存儲在葉子結點上，也就是其所有葉子結點的數據組合起來就是完整的數據，但是B樹的數據存儲在每一個結點中，并不僅僅存儲在葉子結點上。

（3）分支結點的構造不同；B 樹的分支結點僅僅存儲着關鍵字信息和兒子的指針（這裡的指針指的是磁盤塊的偏移量），也就是說内部結點僅僅包含着索引信息。

（4）查詢不同；B樹在找到具體的數值以後，則結束，而B 樹則需要通過索引找到葉子結點中的數據才結束，也就是說B 樹的搜索過程中走了一條從根結點到葉子結點的路徑。

想要在程序員生涯内有更高的成就的話，最最重要的是盡可能的提升自己的編程能力，并且，與其想着怎麼去提升，不如從現在開始動手動腦，如果對于C/C 感興趣的話，可以關注 私信小編【C/C 編程】有一些視頻希望可以幫助到你，學習不怕從零開始，就怕從不開始。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!