數據結(jie)構基(ji)礎知(zhi)識大全(quan)（學霸筆記）
時間：2018-08-09 來源：未知
一、學習知識點：
1、順序表(biao)、鏈(lian)表(biao)
2、順序棧(zhan)、鏈棧(zhan)
3、順序隊列、鏈(lian)式(shi)隊列
4、樹
5、圖&哈希表(biao)
二、學習內(nei)容
1、
(1)順序表：簡記(ji)：立個flag標記(ji)最后有效元素的(de)位(wei)置。特點：查找快，刪、增慢。插入(ru)的(de)元素從(cong)前面逐(zhu)個插入(ru)。
(2)鏈(lian)表：頭插、尾插。單(dan)向(xiang)或雙(shuang)向(xiang)循環鏈(lian)表要注意頭結點與尾節點的連接
在(zai)鏈(lian)表(biao)(biao)操(cao)作中(zhong)(zhong)經(jing)常出現段錯誤(wu)的(de)原因：當(dang)用指(zhi)針(zhen)進行(xing)地址操(cao)作時(shi)由于(yu)指(zhi)針(zhen)是(shi)個(ge)變(bian)量，可(ke)以表(biao)(biao)示(shi)某個(ge)地址也可(ke)表(biao)(biao)示(shi)NULL，因為操(cao)作時(shi)對指(zhi)針(zhen)變(bian)量進行(xing)的(de)賦值操(cao)作可(ke)能(neng)會導致指(zhi)針(zhen)被(bei)賦予NULL,再對此時(shi)的(de)指(zhi)針(zhen)進行(xing)地址偏移操(cao)作就會產生段錯誤(wu)。另(ling)一個(ge)需要注意的(de)問題：指(zhi)針(zhen)不(bu)僅要關注被(bei)賦予的(de)是(shi)不(bu)是(shi)地址，大小是(shi)否匹配(pei)，在(zai)鏈(lian)表(biao)(biao)操(cao)作中(zhong)(zhong)還要關注操(cao)作對象
2、
(1) 順序棧：也是立個int 型 flag,像(xiang)操作數(shu)組一樣 -1為空，N-1時為滿，flag自(zi)增時放數(shu)據，刪除時先(xian)把數(shu)據取出(chu)記錄，flag自(zi)減(jian)
(2) 鏈(lian)棧：一、只(zhi)有鏈(lian)表(biao) 先把頭(tou)(tou)結(jie)點(dian)的下(xia)(xia)家(jia)初始為(wei)(wei)空，然后(hou)采取頭(tou)(tou)插法，只(zhi)是頭(tou)(tou)結(jie)點(dian)的下(xia)(xia)家(jia)為(wei)(wei)空時棧空，之(zhi)后(hou)頭(tou)(tou)結(jie)點(dian)一直(zhi)往棧頂升(sheng)。刪(shan)除(chu)：先用個指針(zhen)把頭(tou)(tou)結(jie)點(dian)的下(xia)(xia)家(jia)記(ji)錄下(xia)(xia)來，再把頭(tou)(tou)結(jie)點(dian)的下(xia)(xia)家(jia)的信息(xi)記(ji)錄下(xia)(xia)來，然后(hou)頭(tou)(tou)結(jie)點(dian)與頭(tou)(tou)結(jie)點(dian)下(xia)(xia)家(jia)的下(xia)(xia)家(jia)連接(jie)上后(hou)就(jiu)可刪(shan)除(chu)了
3、
(1) 順序隊(dui)列(lie)：立兩個flag(頭和(he)尾(wei))，頭尾(wei)相(xiang)等時為(wei)空，尾(wei)加1對數組長度取模等于頭滿(man)
(2) 鏈式隊(dui)列(lie)：用(yong)(yong)(yong)鏈表操(cao)作(zuo)，一(yi)個(ge)結(jie)構(gou)體(ti)記(ji)錄信息和(he)下家(jia)，另一(yi)個(ge)結(jie)構(gou)體(ti)為節(jie)點(dian)(dian)類(lei)型(xing)的(de)(de)(de)(de)指(zhi)針(zhen)分別用(yong)(yong)(yong)于(yu)指(zhi)向(xiang)頭和(he)尾節(jie)點(dian)(dian)，此(ci)隊(dui)列(lie)只有(you)空(kong)(kong)(kong)沒有(you)滿的(de)(de)(de)(de)情況。申請空(kong)(kong)(kong)間(jian)的(de)(de)(de)(de)時(shi)候先為有(you)兩個(ge)節(jie)點(dian)(dian)類(lei)型(xing)的(de)(de)(de)(de)指(zhi)針(zhen)的(de)(de)(de)(de)結(jie)構(gou)體(ti)申請，然后(hou)通過指(zhi)針(zhen)解引用(yong)(yong)(yong)申請一(yi)個(ge)節(jie)點(dian)(dian)類(lei)型(xing)的(de)(de)(de)(de)空(kong)(kong)(kong)間(jian)，用(yong)(yong)(yong)這兩個(ge)指(zhi)針(zhen)接收地址，接著將指(zhi)向(xiang)頭結(jie)點(dian)(dian)的(de)(de)(de)(de)指(zhi)針(zhen)的(de)(de)(de)(de)下家(jia)初(chu)始化為NULL，其實就是初(chu)始化鏈表，當頭節(jie)點(dian)(dian)的(de)(de)(de)(de)下家(jia)為空(kong)(kong)(kong)時(shi)隊(dui)列(lie)為空(kong)(kong)(kong)。
4、
(1)樹(shu)的創建和前序(根 左 右(you))、中序(左 根 右(you))都采用遞(di)歸的方法(fa)
(2)樹的層次遍歷：用鏈式隊列(lie)操作，主要是將樹的某個(ge)節點的數據和(he)左右子節點封(feng)裝成一個(ge)數據，再讓(rang)其(qi)充(chong)當鏈表操作中的數據元素的位置。
(3)非(fei)遞(di)歸先(xian)序(xu)遍(bian)歷樹(shu)：用(yong)鏈棧操作 做(zuo)法與樹(shu)的(de)層次遍(bian)歷相同。
(4)完全二叉樹：也(ye)采用遞(di)歸的(de)方式創(chuang)建(jian)，在創(chuang)建(jian)的(de)時(shi)候傳兩(liang)個(ge)參數(shu)，一個(ge)是節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)總數(shu)，一個(ge)是傳進去的(de)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)號(節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)內(nei)的(de)數(shu)據等于節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)號時(shi))，然后利用節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)的(de)左子(zi)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)為(wei)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)的(de)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)號*2，右(you)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)為(wei)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)的(de)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)號*2+1判斷(duan)條件(jian)，滿足(zu)左右(you)子(zi)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)都小于等于最(zui)大(da)節(jie)(jie)點(dian)(dian)(dian)(dian)(dian)號則(ze)遞(di)歸創(chuang)建(jian)，不(bu)滿足(zu)則(ze)返回空(kong)。
5、
圖(tu)(tu)分為有向(xiang)圖(tu)(tu)和無(wu)向(xiang)圖(tu)(tu)，有向(xiang)圖(tu)(tu)是(shi)單向(xiang)的(de)，無(wu)向(xiang)圖(tu)(tu)是(shi)雙向(xiang)的(de)。圖(tu)(tu)的(de)算(suan)法有深度優(you)先算(suan)法(相(xiang)當于樹(shu)的(de)前序遍歷)、廣度優(you)先算(suan)法(相(xiang)當于樹(shu)的(de)層次遍歷)
哈希表(biao) 用鏈表(biao)操(cao)作 一個存放普通數(shu)據數(shu)組(zu)(zu) 一個節點類型數(shu)組(zu)(zu)：初始化(hua)數(shu)組(zu)(zu)成員(yuan)數(shu)據為0，指(zhi)針next為空，這(zhe)個節點類型的(de)(de)數(shu)組(zu)(zu)相(xiang)當(dang)于(yu)一排并排的(de)(de)頭結點，位置由數(shu)組(zu)(zu)下標(biao)標(biao)示。然(ran)后將(jiang)數(shu)組(zu)(zu)中的(de)(de)數(shu)據對(dui)數(shu)組(zu)(zu)長度取(qu)模(mo)計算數(shu)據存放下標(biao)，后面就是鏈表(biao)的(de)(de)操(cao)作。
三、經(jing)驗(yan)小(xiao)結
例：球鐘問(wen)題(ti) 將這個問(wen)題(ti)的(de)(de)各種(zhong)(zhong)可重復(fu)單一(yi)功(gong)(gong)能(neng)(neng)封(feng)裝成函(han)數(shu)(shu)，后期(qi)調(diao)用(yong)(yong)即可，在(zai)main函(han)數(shu)(shu)中寫(xie)邏(luo)輯調(diao)用(yong)(yong)即可。這種(zhong)(zhong)做法類(lei)似于文件(jian)io操(cao)作，別(bie)人(ren)提供的(de)(de)庫函(han)數(shu)(shu)就是實現某一(yi)可重復(fu)單一(yi)功(gong)(gong)能(neng)(neng)，將要的(de)(de)任務在(zai)main中寫(xie)邏(luo)輯，遇到相應的(de)(de)要做的(de)(de)功(gong)(gong)能(neng)(neng)直接調(diao)用(yong)(yong)即可。
編(bian)寫代碼時常犯錯誤：
頭(tou)文件(jian)忘(wang)記打(帶(dai)有退出狀態(tai))
全局(ju)變量一般不在(zai)頭文件中定義，在(zai)頭文件中定義頭文件的話就不能將頭文件初始化(hua)為(wei)0，數組要加(jia)static
一(yi)個(ge)程序本(ben)質上都是(shi)由(you) bss段(duan)(duan)、data段(duan)(duan)、text段(duan)(duan)三個(ge)組成的。在采(cai)用(yong)段(duan)(duan)式內(nei)存管理的架(jia)構中(比如intel的80x86系統(tong))，bss段(duan)(duan)(Block Started by Symbol segment)通常是(shi)指用(yong)來存放程序中未初始化(hua)的全(quan)局變量(liang)的一(yi)塊內(nei)存區域，一(yi)般在初始化(hua)時bss 段(duan)(duan)部分將(jiang)會清零(ling)。bss段(duan)(duan)屬于靜態(tai)內(nei)存分配，即程序一(yi)開始就(jiu)將(jiang)其清零(ling)了。
比如，在(zai)C語言之類的(de)程序(xu)編譯完成之后，已(yi)初始化的(de)全局(ju)變量保存在(zai).data 段中，未初始化的(de)全局(ju)變量保存在(zai).bss 段中。
全(quan)局變量，靜態變量默認初(chu)始化
數組(zu)的初始(shi)化(hua)只(zhi)能在定義時用，特別要注意結構體指針內(nei)有(you)數組(zu)，為其malloc申請空(kong)間時
未定義錯誤;
指針(zhen)的定義 例：int *a,*b;(a,b都是指針(zhen))
int *a,b;(a是(shi)指針，b不是(shi))在定(ding)義指針時，將
*與(yu)變量當做(zuo)一(yi)個整體來看以表示是(shi)一(yi)個指針變量;
將結構體成員沒有解引用或引用就(jiu)直接使用造成未定(ding)義錯誤
C語(yu)法錯誤：例(li)(li)如(ru)：指(zhi)(zhi)針(zhen)(zhen) 按照c的(de)規則，靜態的(de)指(zhi)(zhi)針(zhen)(zhen)賦值(zhi)(zhi)操(cao)作(zuo)或偏移操(cao)作(zuo)是沒有錯誤的(de)，但在(zai)程(cheng)(cheng)序中，常用變量(liang)來代替(ti)值(zhi)(zhi)，而(er)一(yi)(yi)個(ge)程(cheng)(cheng)序中的(de)變量(liang)經常會變，例(li)(li)當指(zhi)(zhi)針(zhen)(zhen)的(de)值(zhi)(zhi)在(zai)某一(yi)(yi)刻被賦空(kong)值(zhi)(zhi)又對這個(ge)指(zhi)(zhi)針(zhen)(zhen)進行(xing)(xing)偏移操(cao)作(zuo)或其他不應有的(de)操(cao)作(zuo)就會出現斷錯誤，也屬于c語(yu)法錯誤，在(zai)編(bian)程(cheng)(cheng)中要關注編(bian)寫(xie)時指(zhi)(zhi)針(zhen)(zhen)變量(liang)對應的(de)地址，大(da)小(xiao)，對象以(yi)及程(cheng)(cheng)序運行(xing)(xing)后變量(liang)的(de)值(zhi)(zhi)發(fa)生(sheng)的(de)變化(hua)，以(yi)及發(fa)生(sheng)了變化(hua)后對其進行(xing)(xing)的(de)操(cao)作(zuo)
鏈(lian)接(jie)錯誤：忘記鏈(lian)接(jie)庫
在編程時對一個(ge)變(bian)(bian)量(liang)(liang)的(de)關(guan)注的(de)：1.變(bian)(bian)量(liang)(liang)類(lei)型，普(pu)通類(lei)型，結構體類(lei)型，指針類(lei)型，數組，變(bian)(bian)量(liang)(liang)的(de)值會發生(sheng)變(bian)(bian)化，對發生(sheng)變(bian)(bian)化后的(de)變(bian)(bian)量(liang)(liang)進行的(de)操作可(ke)能(neng)造成的(de)結果(guo)
對(dui)不同(tong)類型的變量的使(shi)用要符(fu)合語法
數據類型是對取(qu)值范圍和運(yun)算方式的限定
隊(dui)列和棧本質都是線性(xing)表
頭文件(jian)：函(han)數(shu)聲(sheng)明，函(han)數(shu)實現(xian)，結構體定(ding)義
不能對表達式和(he)常量賦值
結構體指(zhi)針：->
結構體：.
順序(xu)表(biao)：數組是存儲數據的(de)容器，為這個容器定義一些
增刪(shan)查(cha)改的運算，把這個(ge)集合稱為順序(xu)表(biao)
段錯誤：空指針，非法指針
$?(返回(hui)上(shang)一(yi)條shell指令執行(xing)的結(jie)果(guo))
exit()終止進程 頭文件
return 讓(rang)當(dang)前函(han)數(shu)返回
main函(han)數return 后面也有一個exit
char * p;
%p ,p 打印(yin)p的值
printf()語句是從(cong)右(you)往左執行的
順(shun)序表(biao)查(cha)找快，插(cha)入刪除(chu)慢，鏈(lian)表(biao)相反
要關注指針指向的對象。
可以百度關于鏈(lian)表的面試(shi)題。
棧本(ben)質上(shang)是一個實現后進先出的線性表
