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