基本概念

2019-11-10 17:08:21

字體：大中小

來源：轉載

供稿：網友

一、指針操作C語言支持兩種數據集合：結構和數組。作為函數參數的指針；按引用調用傳遞參數；int f1(int a[]); <==> int f1(int *a); (等價)泛型指針（void*）二、遞歸》基本遞歸一種強大的方法，允許一個問題以其自身越來越小的形式來定義自己。在計算機可學領域中，我們通過使用遞歸函數來解決帶有遞歸性質的問題，也就是用函數調用自身?！肺策f歸遞歸的一種形式，這里編譯器會為此產生優化的代碼。大多數現代的編譯器能夠識別尾遞歸。為此，只要條件允許我們應該利用這個特性。A、在基礎遞歸中，函數的調用類似于這種遞歸調用有點象棧的先進后出，后進先出。棧包含函數調用的信息。當C程序中調用了一個函數時，棧中會分配一塊空間來保存與這個調用相關的信息。每一個調用都被當做是活躍的。棧上的那塊存儲空間成為活躍記錄，或者稱為棧幀。棧幀由5個區域組成：輸入參數、返回值空間、計算表達式時用到的臨時存儲空間、函數調用時保存的狀態信息以及輸出參數。B、尾遞歸如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。四、鏈表五、堆棧棧和隊列a、棧的一個顯著特征是它按照后進先出（LIFO）的方式存儲和刪除元素。類似于鏈表，可以通過鏈表特殊情況來處理（頭進頭出）；b、隊列也是用鏈表來處理，六、哈希表桶的概念。1、哈希表支持一種最有效的檢索方法：散列。從根本上來說，一個哈希表包含一個數組，通過特殊的索引值（鍵）來訪問數組中的元素。哈希表的主要思想是通過一個哈希函數，在所有可能的鍵與槽位之間建立一張映射表。哈希函數每次接受一個鍵將返回與鍵相對的哈希編碼或哈希值。鍵的數據類型可能多種多樣，但哈希值的類型只能是整形。2、有鏈式哈希表、開地址哈希表等等。鏈式哈希表：將數據存儲在“桶”（bucket）中的哈希表。每個“桶”都是一個鏈表，且鏈表的容量能夠隨著沖突的增加而增大。開地址哈希表：將數據存儲在表本身中，而不是“桶”中的哈希表。它通過各種探查方法來避免沖突問題。3、哈希表的應用數據庫系統、符號表、標簽緩沖區、數據字典、關聯數組等等。數據庫系統主要用來優化兩種數據訪問方法：順序訪問和隨機訪問。哈希表是高效的隨機訪問方法的一個重要組成部分，因為它能在固定時間內定位數據。七、樹樹的應用包括霍夫曼編碼、用戶界面、數據庫系統、表達式處理、人工智能、事件調度、優先級隊列等等。樹的周游算法一般有四種：先序遍歷(前序遍歷)、中序遍歷、后序遍歷和層級遍歷。先序遍歷：首先訪問它的根結點，然后是左子結點，最后是右子結點。由于按照從左到右的方式依次遍歷各個子樹，因此以相同的方式將左子結點和右子結點當做新的子樹的根。先序遍歷是按照深度優先的方式遍歷結點的。中序遍歷：首先訪問左子結點，然后是根結點，最后是右子結點。由于按照從左到右的方式依次遍歷各個子樹，因此相同的方式將左子結點和右子結點當做新的子樹的跟。后續遍歷：首先訪問左子結點，然后是右子結點，最后是根結點。由于按照從左到右的方式依次遍歷各個子樹，因此以相同的方式將左子結點和右子結點當做新的子樹的跟。層級遍歷：首先方位數的根，然后依次向下層處理，按照從左到有的順序訪問每層的結點。層級遍歷運用了廣度優先的策略。八、堆和優先隊列九、圖圖由兩種類型的元素組成：頂點和邊。頂點代表對象，邊則建立起對象之間的關系或關聯。圖包含邊(u,v), 則稱頂點v與定點u鄰接。（注意是后者v與前者u鄰接）。如果一幅圖中的每一個頂點都與其他頂點相鄰接，則稱這幅圖是完全圖。關聯是頂點與邊之間的關系。在有向圖中，邊(u,v)從頂點u開始關聯到v。在有向圖中，頂點的入度（in-degree）指的是以該頂點為終點的邊的數目。而頂點的出度（out-degree）指的是從該頂點為起點的邊的數目。在無向圖中，邊(u,v)與頂點u和v相關聯，而頂點的度就是與該頂點相關聯的邊的數目。搜索方法a、廣度優先搜索廣度優先搜索在進一步探索圖中的頂點之前優先訪問當前頂點的所有鄰接結點。這種查找方法在很多應用中都非常有用，包括找出最小生成樹以及最短路徑問題。b、深度優先搜索深度優先搜索在搜索過程中每當訪問到某個頂點后，需要遞歸地訪問此頂點的所有未訪問過的相鄰頂點。因而，這種搜索將盡可能深地持續探索，直到無法繼續為止。這種策略使得深度優先搜索在很多應用中非常有用，包括環檢測以及拓撲排序。

上一篇：leetcode1. Two Sum

下一篇：Spring MVC：基于注解的MVC（下）