數據結構基礎知識大全（學霸筆記）
時間：2018-08-09 來源：未知
一、學習知識點：
1、順序表、鏈表
2、順序棧、鏈棧
3、順序隊列、鏈式隊列
4、樹
5、圖&哈希表
二、學習內容
1、
(1)順序表：簡記：立個flag標記最后有效元素的位置。特點：查找快，刪、增慢。插入的元素從前面逐個插入。
(2)鏈表：頭插、尾插。單向或雙向循環鏈表要注意頭結點與尾節點的連接
在鏈表操作中經常出現段錯誤的原因：當用指針進行地址操作時由于指針是個變量，可以表示某個地址也可表示NULL，因為操作時對指針變量進行的賦值操作可能會導致指針被賦予NULL,再對此時的指針進行地址偏移操作就會產生段錯誤。另一個需要注意的問題：指針不僅要關注被賦予的是不是地址，大小是否匹配，在鏈表操作中還要關注操作對象
2、
(1) 順序棧：也是立個int 型 flag,像操作數組一樣 -1為空，N-1時為滿，flag自增時放數據，刪除時先把數據取出記錄，flag自減
(2) 鏈棧：一、只有鏈表 先把頭結點的下家初始為空，然后采取頭插法，只是頭結點的下家為空時棧空，之后頭結點一直往棧頂升。刪除：先用個指針把頭結點的下家記錄下來，再把頭結點的下家的信息記錄下來，然后頭結點與頭結點下家的下家連接上后就可刪除了
3、
(1) 順序隊列：立兩個flag(頭和尾)，頭尾相等時為空，尾加1對數組長度取模等于頭滿
(2) 鏈式隊列：用鏈表操作，一個結構體記錄信息和下家，另一個結構體為節點類型的指針分別用于指向頭和尾節點，此隊列只有空沒有滿的情況。申請空間的時候先為有兩個節點類型的指針的結構體申請，然后通過指針解引用申請一個節點類型的空間，用這兩個指針接收地址，接著將指向頭結點的指針的下家初始化為NULL，其實就是初始化鏈表，當頭節點的下家為空時隊列為空。
4、
(1)樹的創建和前序(根 左 右)、中序(左 根 右)都采用遞歸的方法
(2)樹的層次遍歷：用鏈式隊列操作，主要是將樹的某個節點的數據和左右子節點封裝成一個數據，再讓其充當鏈表操作中的數據元素的位置。
(3)非遞歸先序遍歷樹：用鏈棧操作 做法與樹的層次遍歷相同。
(4)完全二叉樹：也采用遞歸的方式創建，在創建的時候傳兩個參數，一個是節點總數，一個是傳進去的節點號(節點內的數據等于節點號時)，然后利用節點的左子節點為節點的節點號*2，右節點為節點的節點號*2+1判斷條件，滿足左右子節點都小于等于最大節點號則遞歸創建，不滿足則返回空。
5、
圖分為有向圖和無向圖，有向圖是單向的，無向圖是雙向的。圖的算法有深度優先算法(相當于樹的前序遍歷)、廣度優先算法(相當于樹的層次遍歷)
哈希表 用鏈表操作 一個存放普通數據數組 一個節點類型數組：初始化數組成員數據為0，指針next為空，這個節點類型的數組相當于一排并排的頭結點，位置由數組下標標示。然后將數組中的數據對數組長度取模計算數據存放下標，后面就是鏈表的操作。
三、經驗小結
例：球鐘問題 將這個問題的各種可重復單一功能封裝成函數，后期調用即可，在main函數中寫邏輯調用即可。這種做法類似于文件io操作，別人提供的庫函數就是實現某一可重復單一功能，將要的任務在main中寫邏輯，遇到相應的要做的功能直接調用即可。
編寫代碼時常犯錯誤：
頭文件忘記打(帶有退出狀態)
全局變量一般不在頭文件中定義，在頭文件中定義頭文件的話就不能將頭文件初始化為0，數組要加static
一個程序本質上都是由 bss段、data段、text段三個組成的。在采用段式內存管理的架構中(比如intel的80x86系統)，bss段(Block Started by Symbol segment)通常是指用來存放程序中未初始化的全局變量的一塊內存區域，一般在初始化時bss 段部分將會清零。bss段屬于靜態內存分配，即程序一開始就將其清零了。
比如，在C語言之類的程序編譯完成之后，已初始化的全局變量保存在.data 段中，未初始化的全局變量保存在.bss 段中。
全局變量，靜態變量默認初始化
數組的初始化只能在定義時用，特別要注意結構體指針內有數組，為其malloc申請空間時
未定義錯誤;
指針的定義 例：int *a,*b;(a,b都是指針)
int *a,b;(a是指針，b不是)在定義指針時，將
*與變量當做一個整體來看以表示是一個指針變量;
將結構體成員沒有解引用或引用就直接使用造成未定義錯誤
C語法錯誤：例如：指針 按照c的規則，靜態的指針賦值操作或偏移操作是沒有錯誤的，但在程序中，常用變量來代替值，而一個程序中的變量經常會變，例當指針的值在某一刻被賦空值又對這個指針進行偏移操作或其他不應有的操作就會出現斷錯誤，也屬于c語法錯誤，在編程中要關注編寫時指針變量對應的地址，大小，對象以及程序運行后變量的值發生的變化，以及發生了變化后對其進行的操作
鏈接錯誤：忘記鏈接庫
在編程時對一個變量的關注的：1.變量類型，普通類型，結構體類型，指針類型，數組，變量的值會發生變化，對發生變化后的變量進行的操作可能造成的結果
對不同類型的變量的使用要符合語法
數據類型是對取值范圍和運算方式的限定
隊列和棧本質都是線性表
頭文件：函數聲明，函數實現，結構體定義
不能對表達式和常量賦值
結構體指針：->
結構體：.
順序表：數組是存儲數據的容器，為這個容器定義一些
增刪查改的運算，把這個集合稱為順序表
段錯誤：空指針，非法指針
$?(返回上一條shell指令執行的結果)
exit()終止進程 頭文件
return 讓當前函數返回
main函數return 后面也有一個exit
char * p;
%p ,p 打印p的值
printf()語句是從右往左執行的
順序表查找快，插入刪除慢，鏈表相反
要關注指針指向的對象。
可以百度關于鏈表的面試題。
棧本質上是一個實現后進先出的線性表
