《數(shù)據(jù)結(jié)構(gòu)》知識(shí)點(diǎn)總結(jié)-數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概括參考

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概第一章 概論數(shù)據(jù)就就是指能夠被計(jì)算機(jī) 識(shí)別、存儲(chǔ)與加工處理得信息得載體。數(shù)據(jù)元素就是數(shù)據(jù)得 基本單位，可以由若干個(gè) 數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)就是具有獨(dú)立含義得 最小標(biāo)識(shí)單位數(shù)據(jù)結(jié)構(gòu)得定義：·邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。 ·線性結(jié)構(gòu)： 一對(duì)一關(guān)系。·線性結(jié)構(gòu)：多對(duì)多關(guān)系。存儲(chǔ)結(jié)構(gòu)：就是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言得實(shí)現(xiàn)。 ·順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ：如鏈表。索引存儲(chǔ)結(jié)構(gòu) ·稠密索引：每 個(gè)結(jié)點(diǎn)都有索引項(xiàng)。稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。散列存儲(chǔ)結(jié)構(gòu) ：如散列表。·數(shù)據(jù)運(yùn)算。·對(duì)數(shù)據(jù)得操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合?！こＳ玫糜校?檢索、插入、刪除、更新、排序 。數(shù)據(jù)類型：就是一個(gè)值得集合以及在這些值上定義得 一組操作得總稱?！そY(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，就是導(dǎo)出類型。抽象數(shù)據(jù)類型 ADT·就是抽象數(shù)據(jù)得組織與與之得操作。相當(dāng)于在概念層上描述問題?！?yōu)點(diǎn)就是將數(shù)據(jù)與操作封裝在一起實(shí)現(xiàn)了信息隱藏。程序設(shè)計(jì)得實(shí)質(zhì)就是對(duì)實(shí)際問題選擇一種好得數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好得算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。算法就是一個(gè)良定義得計(jì)算過程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法得好壞得因素： ·算法就是正確得；·執(zhí)行算法得時(shí)間；·執(zhí)行算法得存儲(chǔ)空間（主要就是輔助存儲(chǔ)空間） ；·算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度：就是某個(gè)算法得時(shí)間耗費(fèi)，它就是該算法所求解問題規(guī)模 n得函數(shù)。漸近時(shí)間復(fù)雜度：就是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度得數(shù)量級(jí)評(píng)價(jià)一個(gè)算法得時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就就是算法得漸近時(shí)間復(fù)雜度 。算法中語句得頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素得取值相關(guān)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階（1（n（（n、平方階O（2O（3、??k次方階O（kO（n?？臻g復(fù)雜度：就是某個(gè)算法得空間耗費(fèi)，它就是該算法所求解問題規(guī)模 n得函數(shù)算法得時(shí)間復(fù)雜度與空間復(fù)雜度合稱算法復(fù)雜度。第二章 線性表線性表就是由 0個(gè)數(shù)據(jù)元素組成得有限序列。n=0線性表上定義得基本運(yùn)算：·構(gòu)造空表： Initlist（L）·求表長：Listlength（L）·取結(jié)點(diǎn)：GetNode（Li）·查找：LocateNode（Lx）·插入：InsertList（L，x，i）·刪除：Delete（Li）順序表就是按線性表得邏輯結(jié)構(gòu)次序 依次存放在一組地址連續(xù)得存儲(chǔ)單元中。在存儲(chǔ)單元中得各元素得 物理位置與邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系就是一致得。地址計(jì)算： a（i）=LOCa（）+（1）d（首地址為 ）在順序表中實(shí)現(xiàn)得基本運(yùn)算：·插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為 2；平均時(shí)間復(fù)雜度均為 O（n?！h除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（ 1）/2；平均時(shí)間復(fù)雜度均為 O（n。線性表得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)得邏輯次序與物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間得邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值得同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)得地址信息（即 指針或鏈。這兩部分信息組成鏈表中得結(jié)點(diǎn)結(jié)構(gòu)一個(gè)單鏈表由頭指針得名字來命名。單鏈表運(yùn)算：·建立單鏈表·頭插法： s->next=head；；生成得順序與輸入順序相反。平均時(shí)間復(fù)雜度均為 O（n。·尾插法：head=rear=null；if（head=null）head=s；elser->next=s；r=s； 平均時(shí)間復(fù)雜度均為 O（n）·加頭結(jié)點(diǎn)得算法：對(duì)開始結(jié)點(diǎn)得操作無需特殊處理，統(tǒng)一了空表與非空表?！げ檎摇ぐ葱蛱?hào)：與查找位置有關(guān)，平均時(shí)間復(fù)雜度均為 。·按值：與輸入實(shí)例有關(guān)，平均時(shí)間復(fù)雜度均為 O（n?！げ迦脒\(yùn)算： e（L，1；s->next=p->next；s；平均時(shí)間復(fù)雜度均為 O（）·刪除運(yùn)算： e（L，1；r=p->next；t；free（r；平均時(shí)間復(fù)雜度均為 O（單循環(huán)鏈表就是一種首尾相接得單鏈表，終端結(jié)點(diǎn)得指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件就是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)就是查找頭指針與尾指針得時(shí)間都就是 O（1，不用遍歷整個(gè)鏈表。雙鏈表就就是雙向鏈表， 就就是在單鏈表得每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨得指針域 prior形成兩條不同方向得鏈。由頭指針 head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)鏈表。雙鏈表上得插入與刪除時(shí)間復(fù)雜度均為 O（1順序表與鏈表得比較： ·基于空間：·順序表得存儲(chǔ)空間就是靜態(tài)分配 ，存儲(chǔ)密度為 適于線性表事先確定其大小時(shí)采用?！ゆ湵淼么鎯?chǔ)空間就是動(dòng)態(tài)分配，存儲(chǔ)密度＜ 1；適于線性表長度變化大時(shí)采用?！せ跁r(shí)間：·順序表就是隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表得操作 主要就是查找時(shí) ，宜采用。·以插入與刪除操作為主得線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)?！と舨迦肱c刪除主要發(fā)生在表得 首尾兩端，則宜采用尾指針表示得單循環(huán)鏈表。第三章 棧與隊(duì)列棧（Stack）就是僅限制在表得一端進(jìn)行插入與刪除運(yùn)算得線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時(shí)為空棧。棧得修改就是按后進(jìn)先出得原則進(jìn)行得，我們又稱棧為 LIFO表（LastInFirstOut。通常棧有順序棧與鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧得基本運(yùn)算有六種： ·構(gòu)造空棧： InitStack（·判?？眨?StackEmpty（·判棧滿： StackFull（·進(jìn)棧： Push（S，x）·退棧： ·取棧頂元素： S）在順序棧中有“上溢”與“下溢”得現(xiàn)象。 “上溢”就是 棧頂指針指出棧得外面就是出錯(cuò)狀態(tài) ?！跋乱纭笨梢员硎緱榭諚＃虼擞脕碜鳛榭刂妻D(zhuǎn)移得條件。順序棧中得基本操作有六種： ·構(gòu)造空棧 ·判?？?·判棧滿 ·進(jìn)棧 ·退棧 ·取棧頂元素鏈棧則沒有上溢得限制， 因此進(jìn)棧不要判棧滿。 鏈棧不需要在頭部附加頭結(jié)點(diǎn)， 只要有鏈表得頭指針就可以了。鏈棧中得基本操作有五種： ·構(gòu)造空棧 ·判棧空 ·進(jìn)棧 ·退棧 ·取棧頂元素隊(duì)列（Queue）就是一種運(yùn)算受限得線性表，插入在表得一端進(jìn)行，而刪除在表得另一端進(jìn)行，允許刪除得一端稱為隊(duì)頭（front允許插入得一端稱為隊(duì)尾（ ，隊(duì)列得操作原則就是先進(jìn)先出得，又稱作 FIFO表（FirstInFirstOut）、隊(duì)列也有順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。隊(duì)列得基本運(yùn)算有六種： ·置空隊(duì)：InitQueue（·判隊(duì)空：QueueEmpty（Q）·判隊(duì)滿：QueueFull（Q）·入隊(duì)：EnQueue（x）·出隊(duì)：DeQueue（Q）·取隊(duì)頭元素： QueueFront（Q）順序隊(duì)列得“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列就是空得卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量得概念， 就是把向量空間形成一個(gè)頭尾相接得環(huán)形， 這時(shí)隊(duì)列稱循環(huán)隊(duì)列判定循環(huán)隊(duì)列就是空還就是滿，方法有三種：·一種就是另設(shè)一個(gè)布爾變量來判斷；·第二種就是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（ （rear+1）%m=front）？ 滿：空；·第三種就就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中得元素得總數(shù)。隊(duì)列得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列就就是一個(gè)操作受限得單鏈表。為了便于在表尾進(jìn)行插入（入隊(duì)）操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針與一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿與上溢得問題。在鏈隊(duì)列得出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。第四章 串串就是零個(gè)或多個(gè)字符組成得有限序列?！た沾壕褪侵搁L度為零得串，也就就是串中不包含任何 字符（結(jié)點(diǎn)）?！た瞻状褐复邪?一個(gè)或多個(gè)空格字符得串?！ぴ谝粋€(gè)串中任意個(gè)連續(xù)字符組成得子序列稱為該串得子串，包含子串得串就稱為主串。子串在主串中得序號(hào)就就是指子串在主串中首次出現(xiàn)得位置 ?！た沾褪侨我獯米哟我獯褪亲陨淼米哟?。串分為兩種： ·串常量在程序中只能引用不能改變·串變量得值可以改變。串得基本運(yùn)算有： ·求串長 strlen（char*s）·串復(fù)制 strcpy（char*to，char*from）·串聯(lián)接 strcat（char*to，char*from）·串比較 charcmp（char*s1，char*s2）·字符定位 strchr（char*s，charc）串就是特殊得線性表（結(jié)點(diǎn)就是字符） ，所以串得存儲(chǔ)結(jié)構(gòu)與線性表得存儲(chǔ)結(jié)構(gòu)類似。串得順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱順序串。順序串又可按存儲(chǔ)分配得不同分為：·靜態(tài)存儲(chǔ)分配：直接用定長得字符數(shù)組來定義。優(yōu)點(diǎn)就是涉及串長得操作速度 快，但不適合插入、鏈接操作?！?dòng)態(tài)存儲(chǔ)分配：就是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串得長度分配存儲(chǔ)單元。串得鏈?zhǔn)酱鎯?chǔ)就就是用 單鏈表得方式 存儲(chǔ)串值，串得這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表得差異只就它得 結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決“存儲(chǔ)密度”低得狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)得大小。順序串上子串定位得運(yùn)算：又稱串得“模式匹配”或“串匹配” ，就是在主串中查找出子串出現(xiàn)得位置。在匹配中，將主串稱為目標(biāo)（串） ，子串稱為模式（串）。這就是比較容易理解得，串匹配問題就就是找出給定模式串P在給定目標(biāo)串 T中首次出現(xiàn)得有效位移或者就是全部有效位移。最壞得情況下時(shí)間復(fù)雜度就是 O（n-m+1）假如m與n同階得話則它就是 O（2。鏈串上得子串定位運(yùn)算位移就是結(jié)點(diǎn)地址而不就是整數(shù)第五章 多維數(shù)組數(shù)組一般用順序存儲(chǔ)得方式表示。存儲(chǔ)得方式有： ·行優(yōu)先順序，也就就是把數(shù)組逐行依次排列。 PASCAL、C·列優(yōu)先順序，就就是把數(shù)組逐列依次排列。 FORTRAN地址得計(jì)算方法： ·按行優(yōu)先順序排列得數(shù)組： LOCa（ij）=LOCa（+（i-1）*n+（j-1） *d、·按列優(yōu)先順序排列得數(shù)組： LOCa（ij）=LOCa（+（j-1）*n+（i-1） *d、矩陣得壓縮存儲(chǔ)：為多個(gè)相同得非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。稀疏矩陣得概念：一個(gè)矩陣中若其非零元素得個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素得個(gè)數(shù)，則該矩陣稱為稀疏矩陣。特殊矩陣得類型： ·對(duì)稱矩陣：滿足 （j）=（i。元素總數(shù) （1）/2、I=max（i，j，J=min（ij，a（j）=LOC（sa[0]）+（I*（I+1）/2+J）d、·三角矩陣： ·上三角陣： k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*d、·下三角陣： k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d、·對(duì)角矩陣： k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d、稀疏矩陣得壓縮存儲(chǔ)方式用三元組表把非零元素得值與它所在得行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起， 用這些點(diǎn)組成得一個(gè)線性表來表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行得非零元素在三元組表中得起始位置，即帶行表得三元組表。第六章 樹樹就是n個(gè)結(jié)點(diǎn)得有限集合 ，非空時(shí)必須滿足：只有一個(gè)稱為根得結(jié)點(diǎn)；其余結(jié)點(diǎn)形成 m個(gè)不相交得子集，并稱根得子樹。根就是開始結(jié)點(diǎn)；結(jié)點(diǎn)得子樹數(shù)稱度；度為 0得結(jié)點(diǎn)稱葉子（終端結(jié)點(diǎn)） ；度不為 0得結(jié)點(diǎn)稱分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）；除根外得分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)；有序樹就是子樹有左，右之分得樹；無序樹就是子樹沒有左，右之分得樹；森林就是 m個(gè)互不相交得樹得集合樹得四種不同表示方法： ·樹形表示法；·嵌套集合表示法；·凹入表示法·廣義表表示法。二叉樹得定義：就是 n≥0個(gè)結(jié)點(diǎn)得有限集，它就是空集（ n=0）或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交得分別稱作個(gè)根得左子樹與右子樹得二叉樹組成。二叉樹不就是樹得特殊情形，與度數(shù)為 2得有序樹不同。二叉樹得 4個(gè)重要性質(zhì)： ·二叉樹上第 i層上得結(jié)點(diǎn)數(shù)目最多為 ^（1（i≥1；·深度為 k得二叉樹至多有（ k）-1個(gè)結(jié)點(diǎn)（k≥1；·在任意一棵二叉樹中，若終端結(jié)點(diǎn)得個(gè)數(shù)為 n0，度為2得結(jié)點(diǎn)數(shù)為 則n0=n2+1；·具有n個(gè)結(jié)點(diǎn)得完全二叉樹得深度為 int（log2n）+1、滿二叉樹就是一棵深度為 k結(jié)點(diǎn)數(shù)為（2^k）-1得二叉樹；完全二叉樹就是滿二叉樹在最下層自右向左去處部結(jié)點(diǎn)；二叉樹得順序存儲(chǔ)結(jié)構(gòu)就就是把二叉樹得所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)得存儲(chǔ)單元中。 （存儲(chǔ)前先將其畫完全二叉樹）樹得存儲(chǔ)結(jié)構(gòu)多用得就是鏈?zhǔn)酱鎯?chǔ)。 BinTNode得結(jié)構(gòu)為 lchild|data|rchild，把所有 BinTNode類型得結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)得 BinTree型頭指針就構(gòu)成了二叉樹得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就就是由根指針 root唯一定得。共有2n個(gè)指針域，n+1個(gè)空指針。根據(jù)訪問結(jié)點(diǎn)得次序不同可得三種遍歷： 先序遍歷（前序遍歷或先根遍歷） 中序遍歷（或中根遍歷）后序遍歷（后根遍歷）。時(shí)間復(fù)雜度為 O（。利用二叉鏈表中得 n+1個(gè)空指針域來存放指向某種遍歷次序下得前趨結(jié)點(diǎn)與后繼結(jié)點(diǎn)得指針， 這些附加得指針就為“線索”，加上線索得二叉鏈表就稱為線索鏈表。線索使得查找中序前趨與中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)得前序前趨與后序后繼并沒有什么作用。樹與森林及二叉樹得轉(zhuǎn)換就是唯一對(duì)應(yīng)得。轉(zhuǎn)換方法： ·樹變二叉樹：兄弟相連，保留長子得連線。·二叉樹變樹：結(jié)點(diǎn)得右孩子與其雙親連。·森林變二叉樹：樹變二叉樹，各個(gè)樹得根相連。樹得存儲(chǔ)結(jié)構(gòu)：·有雙親鏈表表示法：結(jié)點(diǎn) data|parent，對(duì)于求指定結(jié)點(diǎn)得雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)得孩子及后代?！ず⒆渔湵肀硎痉ǎ簽闃渲忻總€(gè)結(jié)點(diǎn) data|next設(shè)置一個(gè)孩子鏈表 firstchild，并將data|firstchild存放在一個(gè)向中。·雙親孩子鏈表表示法：將雙親鏈表與孩子鏈表結(jié)合。·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu) leftmostchild|data|rightsibing ，附加兩個(gè)分別指向該結(jié)點(diǎn)得最左孩子與右鄰弟得指針域。樹得前序遍歷與相對(duì)應(yīng)得二叉樹得前序遍歷一致；樹得后序遍歷與相對(duì)應(yīng)得二叉樹得中序遍歷一致。樹得帶權(quán)路徑長度就是樹中所有葉結(jié)點(diǎn)得帶權(quán)路徑長度之與。 樹得帶權(quán)路徑長度最小得二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹）。在葉子得權(quán)值相同得二叉樹中，完全二叉樹得路徑長度最短。哈夫曼樹有 n個(gè)葉結(jié)點(diǎn)，共有 2n-1個(gè)結(jié)點(diǎn)，沒有度為 1得結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。變長編碼技術(shù)可以使頻度高得字符編碼短，而頻度低得字符編碼長，但就是變長編碼可能使解碼產(chǎn)生二義性。如00、0001符編碼得前綴，這種碼稱為前綴碼（其實(shí)就是非前綴碼） 。哈夫曼樹得應(yīng)用最廣泛地就是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布得最優(yōu)前綴碼。哈夫曼編碼得構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼 右路徑上寫代碼 1，然后從上到到葉結(jié)點(diǎn)得相應(yīng)路徑上得代碼得序列就就是該結(jié)點(diǎn)得最優(yōu)前綴碼。第七章 圖圖得邏輯結(jié)構(gòu)特征就就是其結(jié)點(diǎn)（頂點(diǎn)）得前趨與后繼得個(gè)數(shù)都就是沒有限制得，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。圖GraphG=（V，V就是頂點(diǎn)得有窮非空集合， E就是頂點(diǎn)偶對(duì)得有窮集。有向圖Digraph：每條邊有方向；無向圖 Undigraph：每條邊沒有方向。有向完全圖：具有 n*（n-1）條邊得有向圖；無向完全圖：具有 n*（/2條邊得無向圖；有根圖：有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)得有向圖；簡(jiǎn)單路徑：就是經(jīng)過頂點(diǎn)不同得路徑；簡(jiǎn)單回路就是開始與終端重得簡(jiǎn)單路徑；網(wǎng)絡(luò)：就是帶權(quán)得圖。圖得存儲(chǔ)結(jié)構(gòu)：·鄰接矩陣表示法：用一個(gè) n階方陣來表示圖得結(jié)構(gòu)就是唯一得，適合稠密圖?！o向圖：鄰接矩陣就是對(duì)稱得。·有向圖：行就是出度，列就是入度。建立鄰接矩陣算法得時(shí)間就是 O（e，其時(shí)間復(fù)雜度為 O（2）·鄰接表表示法：用頂點(diǎn)表與鄰接表構(gòu)成不就是唯一得，適合稀疏圖?！ろ旤c(diǎn)表結(jié)構(gòu) vertex|firstedge，指針域存放鄰接表頭指針。·鄰接表：用頭指針確定。 ·無向圖稱邊表；·有向圖又分出邊表與逆鄰接表；·鄰接表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex|next，時(shí)間復(fù)雜度為 O（，空間復(fù)雜度為 O（。圖得遍歷： ·深度優(yōu)先遍歷：借助于鄰接矩陣得列。使用棧保存已訪問結(jié)點(diǎn)。·廣度優(yōu)先遍歷：借助于鄰接矩陣得行。使用隊(duì)列保存已訪問結(jié)點(diǎn)。生成樹得定義：若從圖得某個(gè)頂點(diǎn)出發(fā)，可以系統(tǒng)地訪問到圖中所有頂點(diǎn)，則遍歷時(shí)經(jīng)過得邊與圖得所有頂點(diǎn)構(gòu)成得子圖稱作該圖得生成樹。最小生成樹：圖得生成樹不唯一，從不同得頂點(diǎn)出發(fā)可得到不同得生成樹，把權(quán)值最小得生成樹稱為最小生成樹（MST。構(gòu)造最小生成樹得算法： ·Prim算法得時(shí)間復(fù)雜度為 O（n^2）與邊數(shù)無關(guān)適于稠密圖。Kruskal算法得時(shí)間復(fù)雜度為 O（e，主要取決于邊數(shù)，較適合于稀疏圖。最短路徑得算法：·a算法，時(shí)間復(fù)雜度為 O（2·類似于 m算法。拓?fù)渑判颍壕褪菍⒂邢驘o環(huán)圖 G中所有頂點(diǎn)排成一個(gè)線性序列， 若<uv>∈（G則在線性序列 u在v之前這種線性序列稱為拓?fù)湫蛄?。拓?fù)渑判蛞灿袃煞N方法：·無前趨得頂點(diǎn)優(yōu)先，每次輸出一個(gè)無前趨得結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊，最后得到得序列即拓?fù)湫蛄小！o后繼得結(jié)點(diǎn)優(yōu)先：每次輸出一個(gè)無后繼得結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊，最后得到得序列就是逆拓?fù)湫蛄小５诎苏?排序排序就是使文件中得記錄按關(guān)鍵字遞增（或遞減）次序排列起來?！せ静僮鳎罕容^關(guān)鍵字大??；改變指向記錄得指針或移動(dòng)記錄?！ご鎯?chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過排序后這些具有相同關(guān)鍵字得記錄之間得相對(duì)次序保持不變，則稱這種排序方法就是穩(wěn)定得，否則排序算法就是不穩(wěn)定得。排序過程中不涉及數(shù)據(jù)得內(nèi)、外存交換則稱之為“內(nèi)部排序” （內(nèi)排序），反之，若存在數(shù)據(jù)得內(nèi)外存交換，稱之為外排序。內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序與分配排序。評(píng)價(jià)排序算法好壞得標(biāo)準(zhǔn)主要有兩條：執(zhí)行時(shí)間與所需得輔助空間，另外算法得復(fù)雜程序也就是要考慮得一個(gè)因素。插入排序：·直接插入排序： ·逐個(gè)向前插入到合適位置。·哨兵（監(jiān)視哨）有兩個(gè)作用： ·作為臨變量存放 R[i]·就是在查找循環(huán)中用來監(jiān)視下標(biāo)變量 j就是否越界?！ぶ苯硬迦肱判蚓褪蔷偷氐梅€(wěn)定排序。 時(shí)間復(fù)雜度為 （2比較次數(shù)為（2（1）/2移動(dòng)次數(shù)為（4）（n-1）/2；·希爾排序： ·等間隔得數(shù)據(jù)比較并按要求順序排列，最后間隔為 、·希爾排序就是就地得不穩(wěn)定排序。時(shí)間復(fù)雜度為 （1、5，比較次數(shù)為（ 1、；移動(dòng)次數(shù)為（ 、6n^1、交換排序：·冒泡排序：·自下向上確定最輕得一個(gè)。 ·自上向下確定最重得一個(gè)。 ·自下向上確定最輕得一個(gè)后自上向下確定最重得一個(gè)?！っ芭菖判蚓褪蔷偷氐梅€(wěn)定排序。時(shí)間復(fù)雜度為 O（2，比較次數(shù)為 （1）/2；移動(dòng)次數(shù)為 （1）/2；·快速排序：·以第一個(gè)元素為參考基準(zhǔn)，設(shè)定、動(dòng)兩個(gè)指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成。·快速排序就是非就地得不穩(wěn)定排序。時(shí)間復(fù)雜度為 O（n，比較次數(shù)為 n（1）2選擇排序：·直接選擇排序： ·選擇最小得放在比較區(qū)前。·直接選擇排序就地得不穩(wěn)定排序。時(shí)間復(fù)雜度為 O（2。比較次數(shù)為 （1）/2；·堆排序 ·建堆：按層次將數(shù)據(jù)填入完全二叉樹，從 int（n/2）處向前逐個(gè)調(diào)整位置?！と缓髮涓c最后一個(gè)葉子交換值并斷開與樹得連接并重建堆，直到全斷開?！ざ雅判蚓褪蔷偷夭环€(wěn)定得排序，時(shí)間復(fù)雜度為 O（nlog2n不適宜于記錄數(shù)較少得文件歸并排序： ·先兩個(gè)一組排序，形成（ n+1）/2組，再將兩組并一組，直到剩下一組為止?！w并排序就是非就地穩(wěn)定排序，時(shí)間復(fù)雜度就是 O（nlog2n分配排序：·箱排序： ·按關(guān)鍵字得取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱?！は渑判虻闷骄鶗r(shí)間復(fù)雜度就是線性得 O（n?！せ鶖?shù)排序：·從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序。·基數(shù)排序就是非就穩(wěn)定得排序，時(shí)間復(fù)雜度就是 O（d*n+d*rd。各種排序方法得比較與選擇： ·待排序得記錄數(shù)目 n較大得要用時(shí)間復(fù)雜度為 O（nlog2n）得排序方法；·記錄得大小（規(guī)模） ；記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu)，而快速排序與堆排序在鏈表上難于實(shí)現(xiàn)；·關(guān)鍵字得結(jié)構(gòu)及其初始狀態(tài)； ·對(duì)穩(wěn)定性得要求；·語言工具得條件； ·存儲(chǔ)結(jié)構(gòu)； ·時(shí)間與輔助空間復(fù)雜度。第九章 查找查找得同時(shí)對(duì)表做修改操作（如插入或刪除）則相應(yīng)得表稱之為動(dòng)態(tài)查找表，否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣得標(biāo)準(zhǔn)就是在查找過程中對(duì)關(guān)鍵字需要執(zhí)行得平均比較次數(shù)（即平均查找長度 ASL線性表查找得方法： ·順序查找：逐個(gè)查找， ASL=（n+1）/2；·二分查找：取中點(diǎn) int（n/2）比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹表示。 ASL=（∑（每結(jié)點(diǎn)數(shù)*層數(shù)/N、·分塊查找。要求“分塊有序” ，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中得最大關(guān)鍵字及其位置建有序索引表。二叉排序樹（BST）定義就是：二叉排序樹就是空樹或者滿足如下性質(zhì)得二叉樹： ·若它得左子樹非空，則子樹上所有結(jié)點(diǎn)得值均小于根結(jié)點(diǎn)得值；·若它得右子樹非空，則右子樹上所有結(jié)點(diǎn)得值均大于根結(jié)點(diǎn)得值；·左、右子樹本身又就是一棵二叉排序樹。二叉排序樹得插入、建立、刪除得算法平均時(shí)間性能就是 nlog2n。二叉排序樹得刪除操作可分三種情況進(jìn)行處理： ·*P就是葉子，則直接刪除 *P，即將*P得雙親*parent中指向*P得指針域置空即可?！?P只有一個(gè)孩子 *child，此時(shí)只需將 *child與*p得雙親直接連接就可刪去 *p、·*p有兩個(gè)孩子，則先將 *p結(jié)點(diǎn)得中序后繼結(jié)點(diǎn)得數(shù)據(jù)到 *p，刪除中序后繼結(jié)點(diǎn)。關(guān)于B-樹（多路平衡查找樹） 。它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)得查找表，就是一種外查找算法。建得方式就是從下向上拱起。散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字得散列地址存儲(chǔ)到散列表得過程稱為散列。散列函數(shù)得選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單與均勻。常見得散列函數(shù)構(gòu)得造方法：·平方取中法： hash=int（ x^2）%100）·除余法：表長為 m，hash=x%m·相乘取整法： hash=int（m*（x*A-int（x*A）；A=0、618·隨機(jī)數(shù)法： hash=random（x。處理沖突得方法：·開放定址法： ·一般形式為 hi=（h（key）+di）%m1≤i≤m-1，開放定址法要求散列表得裝填因子α≤、·開放定址法類型： ·線性探查法： ）+i）%m；·二次探查法： +i^2）%m；·雙重散列法： x）+i*hash（y） %m；·拉鏈法： ·就是將所有關(guān)鍵字為同義詞得結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中?！だ湻ǖ脙?yōu)點(diǎn)： ·拉鏈法處理沖突簡(jiǎn)單，且無堆積現(xiàn)象；·鏈表上得結(jié)點(diǎn)空間就是動(dòng)態(tài)申請(qǐng)得適于無法確定表長得情況；·拉鏈法中α可以大于 1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省空間；·拉鏈法構(gòu)造得散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)?！だ湻ㄒ灿腥秉c(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中得指針域也要占用額外空間，還就是開放定址法省空間第十章 排序10、1 排序得基本概念10、2 插入排序10、3 選擇排序10、4 交換排序本章主要知識(shí)點(diǎn)排序得基本概念與衡量排序算法優(yōu)劣得標(biāo)準(zhǔn)，其中衡量標(biāo)準(zhǔn)有算法得時(shí)間復(fù)雜度、空間復(fù)雜度與穩(wěn)定性直接插入排序，希爾排序直接選擇排序，堆排序冒泡排序，快速排序10、11、排序就是對(duì)數(shù)據(jù)元素序列建立某種有序排列得過程。2、排序得目得：便于查找。3、關(guān)鍵字就是要排序得數(shù)據(jù)元素集合中得一個(gè)域，排序就是以關(guān)鍵字為基準(zhǔn)進(jìn)行得。關(guān)鍵字分主關(guān)鍵字與次關(guān)鍵字兩種。對(duì)要排序得數(shù)據(jù)元素集合來說，如果關(guān)鍵字滿足數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字得值也一定不同，這樣得關(guān)鍵字稱為主關(guān)鍵字。不滿足主關(guān)鍵字定義得關(guān)鍵字稱為次關(guān)鍵字。4、排序得種類：分為內(nèi)部排序與外部排序兩大類。若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。、排序算法好壞得衡量標(biāo)準(zhǔn)：時(shí)間復(fù)雜度—— 它主要就是分析記錄關(guān)鍵字得比較次數(shù)與記錄得移動(dòng)次數(shù)。穩(wěn)定性——若兩個(gè)記錄 A與B得關(guān)鍵字值相等，但排序后 A、B得先后次序保持不變，則稱這種排序算法就穩(wěn)定得。10、2插入排序插入排序得基本思想就是：每步將一個(gè)待排序得對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序得一組對(duì)象得適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都就是排好序得。常用得插入排序有：直接插入排序與希爾排序兩種。10、2、1直接插入排序1、其基本思想就是：順序地把待排序得數(shù)據(jù)元素按其關(guān)鍵字值得大小插入到已排序數(shù)據(jù)元素子集合得適當(dāng)位置例關(guān)鍵字序列 T=（13，6，3，9，27，5，請(qǐng)寫出直接插入排序得中間過程序列。初始關(guān)鍵字序列：【13】,6,3,31,9,27,5,11第一次排序： 【6,】,3,31,9,27,5,11第二次排序： 【3,6,13】,31,9,27,5,11第三次排序： 【3,6,13，31】,9,27,5,11第四次排序： 【3,6,9,13，】,27,5,11第五次排序： 【3,6,9,13，27,31】,5,11第六次排序： 【3,5,6,9,13，27,31】,11第七次排序： 【3,5,6,9,11，13，27,31】注：方括號(hào) [ ]中為已排序記錄得關(guān)鍵字，下劃橫線得 關(guān)鍵字表示它對(duì)應(yīng)得記錄后移一個(gè)位置。2、直接插入排序算法publicstaticvoidinsertSort(int[]a){inti,j,temp;intna、Length;for(i=0;i<n-1;i++){temp=a[i+1];j=i;while(j>-1&&temp<a[j]){a[j+1]=a[j];j--;}a[j+1]=temp;}}初始關(guān)鍵字序列：【13】,6,3,31,9,27,5,11第一次排序： 【6,】,3,31,9,27,5,11第二次排序： 【3,6,13】,31,9,27,5,113、直接插入排序算法分析時(shí)間效率：當(dāng)數(shù)據(jù)有序時(shí)，執(zhí)行效率最好，此時(shí)得時(shí)間復(fù)雜度為 O(n)；當(dāng)數(shù)據(jù)基本反序時(shí)，執(zhí)行效率最差，此得時(shí)間復(fù)雜度為 O(n2)。所以當(dāng)數(shù)據(jù)越接近有序，直接插入排序算法得性能越好?？臻g效率：僅占用 1個(gè)緩沖單元——O（1）算法得穩(wěn)定性：穩(wěn)定、2、2希爾（shell）排序 （又稱縮小增量排序）1、基本思想：把整個(gè)待排序得數(shù)據(jù)元素分成若干個(gè)小組，對(duì)同一小組內(nèi)得數(shù)據(jù)元素用直接插入法排序；小組得個(gè)數(shù)逐次縮小，當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)得排序后排序過程結(jié)束。 、技巧：小組得構(gòu)成不就是簡(jiǎn)單地 逐段分割而就是將相隔某個(gè)增量 d得記錄組成一個(gè)小組 ,讓增量d逐趟縮（例如依次取 1直到d＝1為止。3、優(yōu)點(diǎn)：讓關(guān)鍵字值小得元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。例：設(shè)待排序得序列中有 2個(gè)記錄，它們得關(guān)鍵字序列 T=(654，5，7，，，6，6，4，，2，3，請(qǐng)寫出希爾排序得具體實(shí)現(xiàn)過程。publicstaticvoidshellSort(int[]a,int[]d,intnumOfD){inti,j,k,m,span;inttemp;intn=a、Length;for(m=0;m<numOfDm++){ 共numOfD次循環(huán)span=d[m]; //取本次得增量值for(k=0;k<span;k++){ 共span個(gè)小for(i=k;i<n-span;i=i+span){temp=a[i+span];j=i;while(j>-1&&temp<a[j]){a[j+span]=a[j];j=j-span;}a[j+span]=temp;}}}}算法分析：開始時(shí) d得值較大，子序列中得對(duì)象較少，排序速度較快；隨著排序進(jìn)展， d值逐漸變小，子序列中象個(gè)數(shù)逐漸變多，由于前面工作得基礎(chǔ)，大多數(shù)記錄已基本有序，所以排序速度仍然很快。時(shí)間效率：O(n(log2n)2)空間效率：1）——因?yàn)閮H占用 1個(gè)緩沖單算法得穩(wěn)定性：不穩(wěn)定練習(xí)：、 欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中得關(guān)鍵碼按字母升序重排，則初始 d為4得希爾排序一趟得果就是？答： 原始序列： Q,H,C,Y,P,A,M,S,R,D,F, Xshell一趟后： P,A,C,S,Q,D,F,X,R,H,M,Y、以關(guān)鍵字序列（ 256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（取 d=5,3,1）算法得各趟排序結(jié)束時(shí)，關(guān)鍵字序列得狀態(tài)。解：原始序列 :256，751，937，863，742，694，076，438希爾排序第一趟 d=5256301694076438863742751129937第二趟d=3076301129256438694742751863937第三趟d=1 076 129 256 301 438 694 742 751 863 93710、3選擇排序選擇排序得基本思想就是：每次從待排序得數(shù)據(jù)元素集合中選取關(guān)鍵字最?。ɑ蜃畲螅┑脭?shù)據(jù)元素放到數(shù)據(jù)素集合得最前（或最后） ，數(shù)據(jù)元素集合不斷縮小，當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序結(jié)束。常用得選擇排序算法：（1）直接選擇排序（2）堆排序10、3、1直接選擇排序1、其基本思想每經(jīng)過一趟比較就找出一個(gè)最小值，與待排序列最前面得位置互換即可。（即從待排序得數(shù)據(jù)元素集合中選取關(guān)鍵字最小得數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中得第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置得數(shù)據(jù)元素集合中選取關(guān)鍵字最小得數(shù)據(jù)元素并將它與原始數(shù)據(jù)集合中得第二個(gè)據(jù)元素交換位置；如此重復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。 ）2、優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：每趟只能確定一個(gè)元素，表長為 n時(shí)需要 n-1趟例：關(guān)鍵字序列 T=（，5，9，*，6，8，請(qǐng)給出直接選擇排序得具體實(shí)現(xiàn)過程。原始序列： 21，49，25*，16，08第1趟 25，25*，16，21第2趟08，16,49，25*，25，21第3趟08，16,21，25*，25，49第4趟08，16,21，25*，25，49第5趟08，16,21，25*，25，49publicstaticvoidselectSort(int[]a){inti,j,small;inttemp;intn=a、Length;for(i=0;i<n-1;i++){smalli; //設(shè)第i個(gè)數(shù)據(jù)元素最小for(j=i+1;j<nj 尋找最小得數(shù)據(jù)元素if(a[j]<a[small])small=j; //記住最小元素得下if(small!=i){ //當(dāng)最小元素得下標(biāo)不為 i時(shí)交換位置temp=a[i];a[i]=a[small];a[small]=temp;}}}3、算法分析時(shí)間效率： O(n2)——雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多?？臻g效率：O（——沒有附加單元（僅用到 1個(gè)temp)算法得穩(wěn)定性：不穩(wěn)定4、穩(wěn)定得直接選擇排序算法例：關(guān)鍵字序列 T= （1，5，9，*，6，8，請(qǐng)給出穩(wěn)定得直接選擇排序得具體實(shí)現(xiàn)過程。原始序列： 21，49，25*，16，08第1趟08, 21, 25, 49, 25*,16第2趟16, 25，49，25*第3趟16, 25，49，25*第4趟16, 25，49，25*第5趟16, 25，25* ，publicstaticvoidselectSort2(int[]a){inti,j,small;inttemp;intn=a、Length;for(i=0;i<n-1;i++){small=i;for(j=i+1;jnj++){ //尋找最小得數(shù)據(jù)元素if(a[j]<a[small])smallj; //記住最小元素得下標(biāo)}if(small!=i){temp=a[small];for(j=small;jij--) //把該區(qū)段尚未排序元素依次后移a[j]=a[j-1];a[itemp; //插入找出得最小元素}}}8、3、2堆排序、 什么就是堆？ 、 怎樣建堆？ 、 怎樣堆排序？堆得定義：設(shè)有 n個(gè)數(shù)據(jù)元素得序列 k0，k1，?，kn-1，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。解釋：如果讓滿足以上條件得元素序列 （k０，k１，?，kn－１）順次排成一棵完全二叉樹，則此樹得特點(diǎn)就是：樹中所有結(jié)點(diǎn)得值均大于（或小于）其左右孩子，此樹得根結(jié)點(diǎn)（即堆頂）必最大（或最?。?。例：有序列 T1=（,,,,,7）與序列 T2=（,,,,,,5）判斷它們就是否 堆？、 怎樣建堆？步驟：從第一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整例：關(guān)鍵字序列 T=(21，5，，*，6，8，請(qǐng)建最大堆。解：為便于理解，先將原始序列畫成完全二叉樹得形式：這樣可以很清晰地從 (n-1-1)/2開始調(diào)整。publicstaticvoidcreateHeap(int[]a,intn,inth){inti,j,flag;inttemp;i=h;j=2*i1; //j為i結(jié)點(diǎn)得左孩子結(jié)點(diǎn)得下標(biāo)temp=a[i];flag=0;while(j<n&&flag!=1){//尋找左右孩子結(jié)點(diǎn)中得較大者 ,j為其下標(biāo)if(j<n-1&&a[j]<a[j+1])j++;if(tempa[j]) flag1; //標(biāo)記結(jié)束篩選條件else{ //否則把 a[j]上a[i]=a[j];i=j;j=2*i+1;}}a[i]=temp;}利用上述 函數(shù)，初始化創(chuàng)建最大堆得過程就就是從第一個(gè)非葉子結(jié)點(diǎn) a[i]開始，到根結(jié)點(diǎn)a[0]為止，循環(huán)調(diào)用 得過程。初始化創(chuàng)建最大堆算法如下：publicstaticvoidinitCreateHeap(int[a){intna、Length;for(inti=(n-1-1)/2;i>=0;i--)createHeap(a,n,i);}、 怎樣進(jìn)行整個(gè)序列得堆排序？*基于初始堆進(jìn)行堆排序得算法步驟：堆得第一個(gè)對(duì)象 a[0]具有最大得關(guān)鍵碼，將 a[0]與a[n-1]對(duì)調(diào)，把具有最大關(guān)鍵碼得對(duì)象交換到最后 ;再對(duì)前面得 n-1個(gè)對(duì)象，使用堆得調(diào)整算法， 重新建立堆（調(diào)整根結(jié)點(diǎn)使之滿足最大堆得定義） 結(jié)果具有次大關(guān)鍵碼得對(duì)象又上浮到堆頂，即 a[0]位置;再對(duì)調(diào)a[0]與a[n-2]，然后對(duì)前 n-2個(gè)對(duì)象重新調(diào)整， ?如此反復(fù)，最后得到全部排序好得對(duì)象序列例對(duì)剛才建好得最大堆進(jìn)行排序：publicstaticvoidheapSort(int[]a){inttemp;intn=a、Length;initCreateHeap(a); //初始化創(chuàng)建最大堆for(inti=n-1;i>0;i--){ //當(dāng)前最大堆個(gè)數(shù)每次遞減 1//把堆頂a[0]元素與當(dāng)前最大堆得最后一個(gè)元素交換temp=a[0];a[0]=a[i];a[i]=temp;createHeap(a,i,0); //調(diào)整根結(jié)點(diǎn)滿足最大堆}}、堆排序算法分析：時(shí)間效率：O(nlog2n)空間效率：O(1)。穩(wěn)定性： 不穩(wěn)定。練習(xí)1：以下序列就是堆得就是（ ）{75,65,30,15,25,45,20,10} B、{75,65,45,10,30,25,20,15}C、 {75,45,65,30,15,25,20,10} D、 {75,45,65,10,25,30,20,15}練習(xí)2：有一組數(shù)據(jù) {15,9,7,8,20,1,7*,4} ，建成得最小堆為（ 。A、{1,4,8,9,20,7,15,7*} B、{1,7,15,7*,4,8,20,9}C、{1,4,7,8,20,15,7*,9} D、以上都不對(duì)練習(xí)3：已知序列{503512908170897275462，寫出采用堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)得排序過程。排序好得序列為： 87，170，275，462，503，512，897，90810、4交換排序交換排序得基本思想就是：利用交換數(shù)據(jù)元素得位置進(jìn)行排序得方法。交換排序得主要算法有：冒泡排序快速排序10、4、1冒泡排序、基本思路：每趟不斷將記錄兩兩比較，并按 前小后大（或前大后?。┮?guī)則交換。2、優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其她元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。例：關(guān)鍵字序列 T=(21，5，，*，6，8，請(qǐng)按從小到大得順序，寫出冒泡排序得具體實(shí)現(xiàn)過程。初態(tài)：21，25，49，25*，16， 08第1趟25，25*，16，08，49第2趟25，08，25*，49第3趟16，08，25，25*49第4趟08，25，25*，49第5趟16，25，25*，49、冒泡排序算法publicstaticvoidbubbleSort(int[]a){inti,j,flag=1;inttemp;intn=a、Length;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}4、冒泡排序得算法分析時(shí)間效率：O（n2)—因?yàn)橐紤]最壞情況（數(shù)據(jù)元素全部逆序） ，當(dāng)然最好情況就是數(shù)據(jù)元素已全部排好序，此循環(huán)n-1次，時(shí)間復(fù)雜度為 O（n)空間效率：O（—只在交換時(shí)用到一個(gè)緩沖單元穩(wěn)定 性： 穩(wěn)定 —25與25*在排序前后得次序未改練習(xí)：關(guān)鍵字序列 T=(31，5，9，5，，8，請(qǐng)按從小到大得順序，寫出冒泡排序得具體實(shí)現(xiàn)過程初態(tài)：31，15，9，25，16， 28第1趟9，25，16，31第2趟9，15， 25，28，31第3趟9，15， 25， 31、基本思想：設(shè)數(shù)組 a中存放了 n個(gè)數(shù)據(jù)元素，low為數(shù)組得低端下標(biāo)， high為數(shù)組得高端下標(biāo)，從數(shù)組 a中任一個(gè)元素（通常取 a[low]）做為標(biāo)準(zhǔn)元素，以該標(biāo)準(zhǔn)元素調(diào)整數(shù)組 a中其她各個(gè)元素得位置，使排在標(biāo)準(zhǔn)元素前面得元素均小于標(biāo)準(zhǔn)元素，排在標(biāo)準(zhǔn)元素后面得均大于或等于標(biāo)準(zhǔn)元素。這樣一次排序過程結(jié)束后，一方面將標(biāo)準(zhǔn)元素放在了未來排好序得數(shù)組中該標(biāo)準(zhǔn)元素應(yīng)位于得位置上， 另一方面將數(shù)組中得元素以標(biāo)準(zhǔn)元素為中心分成了兩子數(shù)組，位于標(biāo)準(zhǔn)元素左邊子數(shù)組中得元素均小于標(biāo)準(zhǔn)元素，位于標(biāo)準(zhǔn)元素右邊子數(shù)組中得元素均大于等于或標(biāo)準(zhǔn)元素。對(duì)這兩個(gè)子數(shù)組中得元素分別再進(jìn)行方法類同得遞歸快速排序。算法得遞歸出口條件就是 low例、關(guān)鍵字序列T=(60，5，，7，，0，，6，請(qǐng)按從小到大得順序，寫出快速排序得具體實(shí)現(xiàn)過程。快速排序算法各次快速排序過程3、快速排序算法publicstaticvoidquickSort(int[]a,intlow,inthigh){inti,j;inttemp;i=low;j=high;tempa[low]; //while(ij){//在數(shù)組得右端掃描while(i<j&&temp<=a[j])j--;if(i<j){a[i]=a[j];i++;}if(i<j){a[j]=j--;

//在數(shù)組得左端掃描while(i<j&&a[i]<temp)i++;}}a[i]=temp;if(low<i)quickSort(alowi-1); //對(duì)左端子集合遞歸if(i<high)quickSort(aj+1high); //對(duì)右端子集合遞歸}4、快速排序算法分析：時(shí)間效率：一般情況下時(shí)間復(fù)雜度為 O(nlog2n)，最壞情況就是數(shù)據(jù)元素已全部正序或反序有序，此時(shí)每次標(biāo)準(zhǔn)素都把當(dāng)前數(shù)組分成一個(gè)大小比當(dāng)前數(shù)組小 1得子數(shù)組，此時(shí)時(shí)間復(fù)雜度為 O(n2)空間效率：O（log2n）穩(wěn)定 性： 不穩(wěn)定 —因?yàn)橛刑S式交換。練習(xí)：已知序列 {503,87,512,61,908,170,897,275,653,462}，給出采用快速排序?qū)υ撔蛄凶鞣沁f減排序時(shí)每趟得結(jié)果。第一趟【462 87 275 61 170】 503【897 908 653 】第二趟【170 87 275 61】 462 503 【512 】 897 【908】第三趟【61 87】 170 【275】 462 503 512【653】 897 908第四趟：61【87】 170 275 462 503 512 653 897 908最后排序結(jié)果： 61 87 170 275 462 503 512 653 897 9081、插入排序就是穩(wěn)定得，選擇排序就是不穩(wěn)定得。2、堆排序所需要附加空間數(shù)與待排序得記錄個(gè)數(shù)無關(guān)。、對(duì)有 n個(gè)記錄得集合進(jìn)行快速排序，所需時(shí)間確定于初始記錄得排列情況，在初始記錄無序得情況下最好。、直接插入排序在最好情況下得時(shí)間復(fù)雜度為（ A）A、O(n) B、O(nlog2n) C、 O(log2n) D、O(n2)、數(shù)據(jù)序列{8,9,10,4,5,6,20,1,2}只能就是（ C ）算法得兩趟排序后得結(jié)果。A、直接選擇排序 B、冒泡排序 C、直接插入排序 D、堆排序、用直接插入排序?qū)ο旅?4個(gè)序列進(jìn)行遞增排序，元素比較次數(shù)最少得就是（ C ）A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,40、 、以下排序算法中，（B ）不能保證每趟排序至少能將一個(gè)元素放到其最終位置上。A、 快速排序 B、希爾排序 、堆排序 D、冒泡排序、對(duì)關(guān)鍵字{28,16,32,12,60,2,5,72}序列進(jìn)行快速排序，第一趟從小到大一次劃分結(jié)果為（ B ）A、(2,5,12,16)26(60,32,72) B、(5,16,2,12)28(60,32,72)C、(2,16,12,5)28(60,32,72) D、(5,16,2,12)28(32,60,72)、若用冒泡排序?qū)﹃P(guān)鍵字序列 {18，16，14，12，8}進(jìn)行從小到大得排序，所需進(jìn)行得關(guān)鍵字比較總次數(shù)就是（ B 。A、10 B、15 C、21 D、3410、一組記錄得關(guān)鍵字為 {45，80，55，40，42，85}，則利用堆排序得方法建立得初始堆為（ B。A、{85，45，40，55} B、{85，55，42，45} C、{85，80，55，45，42，40} D、{85，55，42，45，40}第十章 文件文件就是性質(zhì)相同得記錄得集合。記錄就是文件中存取得基本單位，數(shù)據(jù)項(xiàng)就是文件可使用得最小單位，數(shù)據(jù)項(xiàng)有時(shí)稱字段或者屬性。文件 ·邏輯結(jié)構(gòu)就是一種線性結(jié)構(gòu)。·操作有：檢索與維護(hù)。并有實(shí)時(shí)與批量處理兩種處理方式文件 ·存儲(chǔ)結(jié)構(gòu)就是指文件在外存上得組織方式?！せ镜媒M織方式有：順序組織、索引組織、散列組織與鏈組織。·常用得文件組織方式：順序文件、索引文件、散列文件與多關(guān)鍵字文件。評(píng)價(jià)一個(gè)文件組織得效率，就是執(zhí)行文件操作所花費(fèi)得時(shí)間與文件組織所需得存儲(chǔ)空間。檢索功能得多寡與速度得快慢，就是衡量文件操作質(zhì)量得重要標(biāo)志。順序文件就是指按記錄進(jìn)入文件得先后順序存放、其邏輯順序與物理順序一致得文件。主關(guān)鍵字有序稱順序有序文件，否則稱順序無序文件。一切存儲(chǔ)在順序存儲(chǔ)器（如磁帶）上得文件都只能順序文件，只能按順序查找法存取。順序文件得插入、刪除與修改只能通過復(fù)制整個(gè)文件實(shí)現(xiàn)。索引文件得組織方式：通常就是在主文件之外建立一張索引表指明邏輯記錄與物理記錄之間一一對(duì)應(yīng)得關(guān)系，它與主文件一起構(gòu)成索引文件。索引非順序文件中得索引表為稠密索引。索引順序文件中得索引表為稀疏索引。若記錄很大使得索引表也很大時(shí)，可對(duì)索引表再建立索引，稱為查找表。就是一種靜態(tài)索引。索引順序文件常用得有兩種：·ISAM索引順序存取方法：就是專為磁盤存取文件設(shè)計(jì)得，采用靜態(tài)索引結(jié)構(gòu)?！SAM 虛擬存儲(chǔ)存取方法：采用 B+樹作為動(dòng)態(tài)索引結(jié)構(gòu)，由索引集、順序集、數(shù)據(jù)集組成散列文件就是利用散列存儲(chǔ)方式組織得文件，亦稱為直接存取文件。散列文件·優(yōu)點(diǎn)就是：文件隨機(jī)存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。·缺點(diǎn)就是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式限地簡(jiǎn)單詢問，需要重新組織文件。多重表文件：對(duì)需要查詢得次關(guān)鍵字建立相應(yīng)得索引，對(duì)相同次關(guān)鍵字得記錄建一個(gè)鏈表并將鏈表頭指針、長度、次關(guān)鍵字作為索引表得索引項(xiàng)。倒排表：次關(guān)鍵字索引表稱倒排表，主文件與倒排表構(gòu)成倒排文件。衛(wèi)生管理制度1 總則1.1 為了加強(qiáng)公司的環(huán)境衛(wèi)生管理，創(chuàng)造一個(gè)整潔、文明、溫馨的購物、辦公環(huán)境，根據(jù)《公共場(chǎng)所衛(wèi)生管理?xiàng)l例》的要求，特制定本制度。1.2 集團(tuán)公司的衛(wèi)生管理部門設(shè)在企管部，并負(fù)責(zé)將集團(tuán)公司的衛(wèi)生區(qū)域詳細(xì)劃分到各部室，各分公司所轄區(qū)域衛(wèi)生由分公司客服部負(fù)責(zé)劃分，確保無遺漏。2 衛(wèi)生標(biāo)準(zhǔn)2.1 室內(nèi)衛(wèi)生標(biāo)準(zhǔn)2.1.1 地面、墻面：無灰塵、無紙屑、無痰跡、無泡泡糖等粘合物、無積水，墻角無灰吊、無蜘蛛網(wǎng)。2.1.2 門、窗、玻璃、鏡子、柱子、電梯、樓梯、燈具等，做到明亮、無灰塵、無污跡、無粘合物，特別是玻璃，要求兩面明亮。2.1.3 柜臺(tái)、貨架：清潔干凈，貨架、柜臺(tái)底層及周圍無亂堆亂放現(xiàn)象、無灰塵、無粘合物，貨架頂部、背部和底部干凈，不存放雜物和私人物品。2.1.4 購物車（筐）、直接接觸食品的售貨工具（包括刀、叉等）：做到內(nèi)外潔凈，無污垢和粘合物等。購物車（筐）要求每天營業(yè)前簡(jiǎn)單清理，周五全面清理消毒；售貨工具要求每天消毒，并做好記錄。2.1.5 商品及包裝：商品及外包裝清潔無灰塵（外包裝破損的或破舊的不得陳列）。2.1.6 收款臺(tái)、服務(wù)臺(tái)、辦公櫥、存包柜：保持清潔、無灰塵，臺(tái)面和側(cè)面無灰塵、無灰吊和蜘蛛網(wǎng)。桌面上不得亂貼、亂畫、亂堆放物品，用具擺放有序且干凈，除當(dāng)班的購物小票收款聯(lián)外，其它單據(jù)不得存放在桌面上。2.1.7 垃圾桶：桶內(nèi)外干凈，要求營業(yè)時(shí)間隨時(shí)清理，不得溢出，每天下班前徹底清理，不得留有垃圾過夜。2.1.8 窗簾：定期進(jìn)行清理，要求干凈、無污漬。2.1.9 吊飾：屋頂?shù)牡躏椧鬅o灰塵、無蜘蛛網(wǎng)，短期內(nèi)不適用的吊飾及時(shí)清理徹底。2.1.10 內(nèi)、外倉庫：半年徹底清理一次，無垃圾、無積塵、無蜘蛛網(wǎng)等。2.1.11 室內(nèi)其他附屬物及工作用具均以整潔為準(zhǔn)，要求無灰塵、無粘合物等污垢。2.2 室外衛(wèi)生標(biāo)準(zhǔn)2.2.1 門前衛(wèi)生：地面每天班前清理，平時(shí)每一小時(shí)清理一次，每周四營業(yè)結(jié)束后有條件的用水沖洗地面（冬季可根據(jù)情況適當(dāng)清理），墻面干凈且無亂貼亂畫。2.2.2 院落衛(wèi)生：院內(nèi)地面衛(wèi)生全天保潔，果皮箱、消防器械、護(hù)欄及配電箱等設(shè)施每周清理干凈。垃圾池周邊衛(wèi)生清理徹底，不得有垃圾溢出。2.2.3 綠化區(qū)衛(wèi)生：做到無雜物、無紙屑、無塑料袋等垃圾。3 清理程序3.1 室內(nèi)和門前院落等區(qū)域衛(wèi)生：每天營業(yè)前提前10分鐘把所管轄區(qū)域內(nèi)衛(wèi)生清理完畢，營業(yè)期間隨時(shí)保潔。下班后5-10分鐘清理桌面及衛(wèi)生區(qū)域。3.2 綠化區(qū)衛(wèi)生：每周徹底清理一遍，隨時(shí)保持清潔無垃圾。4 管理考核4.1 實(shí)行百分制考核，每月一次（四個(gè)分公司由客服部分別考核、集團(tuán)職能部室由企管部統(tǒng)一考核）。不符合衛(wèi)生標(biāo)準(zhǔn)的，超市內(nèi)每處扣0.5分，超市外每處扣1分。4.2 集團(tuán)堅(jiān)持定期檢查和不定期抽查的方式監(jiān)督各分公司、部門的衛(wèi)生工作。每周五為衛(wèi)生檢查日，集團(tuán)檢查結(jié)果考核至各分公司，各分公司客服部的檢查結(jié)果考核至各部門。4.3 集團(tuán)公司每年不定期組織衛(wèi)生大檢查活動(dòng)，活動(dòng)期間的考核以通知為準(zhǔn)。數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概第一章 概論數(shù)據(jù)就就是指能夠被計(jì)算機(jī) 識(shí)別、存儲(chǔ)與加工處理得信息得載體。數(shù)據(jù)元素就是數(shù)據(jù)得 基本單位，可以由若干個(gè) 數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)就是具有獨(dú)立含義得 最小標(biāo)識(shí)單位數(shù)據(jù)結(jié)構(gòu)得定義：·邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。 ·線性結(jié)構(gòu)： 一對(duì)一關(guān)系?！ぞ€性結(jié)構(gòu)：多對(duì)多關(guān)系。存儲(chǔ)結(jié)構(gòu)：就是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言得實(shí)現(xiàn)。 ·順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ：如鏈表。索引存儲(chǔ)結(jié)構(gòu) ·稠密索引：每 個(gè)結(jié)點(diǎn)都有索引項(xiàng)。稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。散列存儲(chǔ)結(jié)構(gòu) ：如散列表?！?shù)據(jù)運(yùn)算?！?duì)數(shù)據(jù)得操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合?！こＳ玫糜校?檢索、插入、刪除、更新、排序 。數(shù)據(jù)類型：就是一個(gè)值得集合以及在這些值上定義得 一組操作得總稱?！そY(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，就是導(dǎo)出類型。抽象數(shù)據(jù)類型 ADT·就是抽象數(shù)據(jù)得組織與與之得操作。相當(dāng)于在概念層上描述問題?！?yōu)點(diǎn)就是將數(shù)據(jù)與操作封裝在一起實(shí)現(xiàn)了信息隱藏。程序設(shè)計(jì)得實(shí)質(zhì)就是對(duì)實(shí)際問題選擇一種好得數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好得算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。算法就是一個(gè)良定義得計(jì)算過程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法得好壞得因素： ·算法就是正確得；·執(zhí)行算法得時(shí)間；·執(zhí)行算法得存儲(chǔ)空間（主要就是輔助存儲(chǔ)空間） ；·算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度：就是某個(gè)算法得時(shí)間耗費(fèi)，它就是該算法所求解問題規(guī)模 n得函數(shù)。漸近時(shí)間復(fù)雜度：就是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度得數(shù)量級(jí)評(píng)價(jià)一個(gè)算法得時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就就是算法得漸近時(shí)間復(fù)雜度 。算法中語句得頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素得取值相關(guān)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階（1（n（（n、平方階O（2O（3、??k次方階O（kO（n。空間復(fù)雜度：就是某個(gè)算法得空間耗費(fèi)，它就是該算法所求解問題規(guī)模 n得函數(shù)算法得時(shí)間復(fù)雜度與空間復(fù)雜度合稱算法復(fù)雜度。第二章 線性表線性表就是由 0個(gè)數(shù)據(jù)元素組成得有限序列。n=0線性表上定義得基本運(yùn)算：·構(gòu)造空表： Initlist（L）·求表長：Listlength（L）·取結(jié)點(diǎn)：GetNode（Li）·查找：LocateNode（Lx）·插入：InsertList（L，x，i）·刪除：Delete（Li）順序表就是按線性表得邏輯結(jié)構(gòu)次序 依次存放在一組地址連續(xù)得存儲(chǔ)單元中。在存儲(chǔ)單元中得各元素得 物理位置與邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系就是一致得。地址計(jì)算： a（i）=LOCa（）+（1）d（首地址為 ）在順序表中實(shí)現(xiàn)得基本運(yùn)算：·插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為 2；平均時(shí)間復(fù)雜度均為 O（n?！h除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（ 1）/2；平均時(shí)間復(fù)雜度均為 O（n。線性表得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)得邏輯次序與物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間得邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值得同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)得地址信息（即 指針或鏈。這兩部分信息組成鏈表中得結(jié)點(diǎn)結(jié)構(gòu)一個(gè)單鏈表由頭指針得名字來命名。單鏈表運(yùn)算：·建立單鏈表·頭插法： s->next=head；；生成得順序與輸入順序相反。平均時(shí)間復(fù)雜度均為 O（n。·尾插法：head=rear=null；if（head=null）head=s；elser->next=s；r=s； 平均時(shí)間復(fù)雜度均為 O（n）·加頭結(jié)點(diǎn)得算法：對(duì)開始結(jié)點(diǎn)得操作無需特殊處理，統(tǒng)一了空表與非空表?！げ檎摇ぐ葱蛱?hào)：與查找位置有關(guān)，平均時(shí)間復(fù)雜度均為 。·按值：與輸入實(shí)例有關(guān)，平均時(shí)間復(fù)雜度均為 O（n。·插入運(yùn)算： e（L，1；s->next=p->next；s；平均時(shí)間復(fù)雜度均為 O（）·刪除運(yùn)算： e（L，1；r=p->next；t；free（r；平均時(shí)間復(fù)雜度均為 O（單循環(huán)鏈表就是一種首尾相接得單鏈表，終端結(jié)點(diǎn)得指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件就是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)就是查找頭指針與尾指針得時(shí)間都就是 O（1，不用遍歷整個(gè)鏈表。雙鏈表就就是雙向鏈表， 就就是在單鏈表得每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨得指針域 prior形成兩條不同方向得鏈。由頭指針 head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)鏈表。雙鏈表上得插入與刪除時(shí)間復(fù)雜度均為 O（1順序表與鏈表得比較： ·基于空間：·順序表得存儲(chǔ)空間就是靜態(tài)分配 ，存儲(chǔ)密度為 適于線性表事先確定其大小時(shí)采用?！ゆ湵淼么鎯?chǔ)空間就是動(dòng)態(tài)分配，存儲(chǔ)密度＜ 1；適于線性表長度變化大時(shí)采用?！せ跁r(shí)間：·順序表就是隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表得操作 主要就是查找時(shí) ，宜采用?！ひ圆迦肱c刪除操作為主得線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。·若插入與刪除主要發(fā)生在表得 首尾兩端，則宜采用尾指針表示得單循環(huán)鏈表。第三章 棧與隊(duì)列棧（Stack）就是僅限制在表得一端進(jìn)行插入與刪除運(yùn)算得線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時(shí)為空棧。棧得修改就是按后進(jìn)先出得原則進(jìn)行得，我們又稱棧為 LIFO表（LastInFirstOut。通常棧有順序棧與鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧得基本運(yùn)算有六種： ·構(gòu)造空棧： InitStack（·判?？眨?StackEmpty（·判棧滿： StackFull（·進(jìn)棧： Push（S，x）·退棧： ·取棧頂元素： S）在順序棧中有“上溢”與“下溢”得現(xiàn)象。 “上溢”就是 棧頂指針指出棧得外面就是出錯(cuò)狀態(tài) ?！跋乱纭笨梢员硎緱榭諚＃虼擞脕碜鳛榭刂妻D(zhuǎn)移得條件。順序棧中得基本操作有六種： ·構(gòu)造空棧 ·判?？?·判棧滿 ·進(jìn)棧 ·退棧 ·取棧頂元素鏈棧則沒有上溢得限制， 因此進(jìn)棧不要判棧滿。 鏈棧不需要在頭部附加頭結(jié)點(diǎn)， 只要有鏈表得頭指針就可以了。鏈棧中得基本操作有五種： ·構(gòu)造空棧 ·判棧空 ·進(jìn)棧 ·退棧 ·取棧頂元素隊(duì)列（Queue）就是一種運(yùn)算受限得線性表，插入在表得一端進(jìn)行，而刪除在表得另一端進(jìn)行，允許刪除得一端稱為隊(duì)頭（front允許插入得一端稱為隊(duì)尾（ ，隊(duì)列得操作原則就是先進(jìn)先出得，又稱作 FIFO表（FirstInFirstOut）、隊(duì)列也有順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。隊(duì)列得基本運(yùn)算有六種： ·置空隊(duì)：InitQueue（·判隊(duì)空：QueueEmpty（Q）·判隊(duì)滿：QueueFull（Q）·入隊(duì)：EnQueue（x）·出隊(duì)：DeQueue（Q）·取隊(duì)頭元素： QueueFront（Q）順序隊(duì)列得“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列就是空得卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量得概念， 就是把向量空間形成一個(gè)頭尾相接得環(huán)形， 這時(shí)隊(duì)列稱循環(huán)隊(duì)列判定循環(huán)隊(duì)列就是空還就是滿，方法有三種：·一種就是另設(shè)一個(gè)布爾變量來判斷；·第二種就是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（ （rear+1）%m=front）？ 滿：空；·第三種就就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中得元素得總數(shù)。隊(duì)列得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列就就是一個(gè)操作受限得單鏈表。為了便于在表尾進(jìn)行插入（入隊(duì)）操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針與一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿與上溢得問題。在鏈隊(duì)列得出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。第四章 串串就是零個(gè)或多個(gè)字符組成得有限序列?！た沾壕褪侵搁L度為零得串，也就就是串中不包含任何 字符（結(jié)點(diǎn)）?！た瞻状褐复邪?一個(gè)或多個(gè)空格字符得串?！ぴ谝粋€(gè)串中任意個(gè)連續(xù)字符組成得子序列稱為該串得子串，包含子串得串就稱為主串。子串在主串中得序號(hào)就就是指子串在主串中首次出現(xiàn)得位置 ?！た沾褪侨我獯米哟我獯褪亲陨淼米哟?。串分為兩種： ·串常量在程序中只能引用不能改變·串變量得值可以改變。串得基本運(yùn)算有： ·求串長 strlen（char*s）·串復(fù)制 strcpy（char*to，char*from）·串聯(lián)接 strcat（char*to，char*from）·串比較 charcmp（char*s1，char*s2）·字符定位 strchr（char*s，charc）串就是特殊得線性表（結(jié)點(diǎn)就是字符） ，所以串得存儲(chǔ)結(jié)構(gòu)與線性表得存儲(chǔ)結(jié)構(gòu)類似。串得順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱順序串。順序串又可按存儲(chǔ)分配得不同分為：·靜態(tài)存儲(chǔ)分配：直接用定長得字符數(shù)組來定義。優(yōu)點(diǎn)就是涉及串長得操作速度 快，但不適合插入、鏈接操作?！?dòng)態(tài)存儲(chǔ)分配：就是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串得長度分配存儲(chǔ)單元。串得鏈?zhǔn)酱鎯?chǔ)就就是用 單鏈表得方式 存儲(chǔ)串值，串得這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表得差異只就它得 結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決“存儲(chǔ)密度”低得狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)得大小。順序串上子串定位得運(yùn)算：又稱串得“模式匹配”或“串匹配” ，就是在主串中查找出子串出現(xiàn)得位置。在匹配中，將主串稱為目標(biāo)（串） ，子串稱為模式（串）。這就是比較容易理解得，串匹配問題就就是找出給定模式串P在給定目標(biāo)串 T中首次出現(xiàn)得有效位移或者就是全部有效位移。最壞得情況下時(shí)間復(fù)雜度就是 O（n-m+1）假如m與n同階得話則它就是 O（2。鏈串上得子串定位運(yùn)算位移就是結(jié)點(diǎn)地址而不就是整數(shù)第五章 多維數(shù)組數(shù)組一般用順序存儲(chǔ)得方式表示。存儲(chǔ)得方式有： ·行優(yōu)先順序，也就就是把數(shù)組逐行依次排列。 PASCAL、C·列優(yōu)先順序，就就是把數(shù)組逐列依次排列。 FORTRAN地址得計(jì)算方法： ·按行優(yōu)先順序排列得數(shù)組： LOCa（ij）=LOCa（+（i-1）*n+（j-1） *d、·按列優(yōu)先順序排列得數(shù)組： LOCa（ij）=LOCa（+（j-1）*n+（i-1） *d、矩陣得壓縮存儲(chǔ)：為多個(gè)相同得非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。稀疏矩陣得概念：一個(gè)矩陣中若其非零元素得個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素得個(gè)數(shù)，則該矩陣稱為稀疏矩陣。特殊矩陣得類型： ·對(duì)稱矩陣：滿足 （j）=（i。元素總數(shù) （1）/2、I=max（i，j，J=min（ij，a（j）=LOC（sa[0]）+（I*（I+1）/2+J）d、·三角矩陣： ·上三角陣： k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*d、·下三角陣： k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d、·對(duì)角矩陣： k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d、稀疏矩陣得壓縮存儲(chǔ)方式用三元組表把非零元素得值與它所在得行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起， 用這些點(diǎn)組成得一個(gè)線性表來表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行得非零元素在三元組表中得起始位置，即帶行表得三元組表。第六章 樹樹就是n個(gè)結(jié)點(diǎn)得有限集合 ，非空時(shí)必須滿足：只有一個(gè)稱為根得結(jié)點(diǎn)；其余結(jié)點(diǎn)形成 m個(gè)不相交得子集，并稱根得子樹。根就是開始結(jié)點(diǎn)；結(jié)點(diǎn)得子樹數(shù)稱度；度為 0得結(jié)點(diǎn)稱葉子（終端結(jié)點(diǎn)） ；度不為 0得結(jié)點(diǎn)稱分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）；除根外得分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)；有序樹就是子樹有左，右之分得樹；無序樹就是子樹沒有左，右之分得樹；森林就是 m個(gè)互不相交得樹得集合樹得四種不同表示方法： ·樹形表示法；·嵌套集合表示法；·凹入表示法·廣義表表示法。二叉樹得定義：就是 n≥0個(gè)結(jié)點(diǎn)得有限集，它就是空集（ n=0）或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交得分別稱作個(gè)根得左子樹與右子樹得二叉樹組成。二叉樹不就是樹得特殊情形，與度數(shù)為 2得有序樹不同。二叉樹得 4個(gè)重要性質(zhì)： ·二叉樹上第 i層上得結(jié)點(diǎn)數(shù)目最多為 ^（1（i≥1；·深度為 k得二叉樹至多有（ k）-1個(gè)結(jié)點(diǎn)（k≥1；·在任意一棵二叉樹中，若終端結(jié)點(diǎn)得個(gè)數(shù)為 n0，度為2得結(jié)點(diǎn)數(shù)為 則n0=n2+1；·具有n個(gè)結(jié)點(diǎn)得完全二叉樹得深度為 int（log2n）+1、滿二叉樹就是一棵深度為 k結(jié)點(diǎn)數(shù)為（2^k）-1得二叉樹；完全二叉樹就是滿二叉樹在最下層自右向左去處部結(jié)點(diǎn)；二叉樹得順序存儲(chǔ)結(jié)構(gòu)就就是把二叉樹得所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)得存儲(chǔ)單元中。 （存儲(chǔ)前先將其畫完全二叉樹）樹得存儲(chǔ)結(jié)構(gòu)多用得就是鏈?zhǔn)酱鎯?chǔ)。 BinTNode得結(jié)構(gòu)為 lchild|data|rchild，把所有 BinTNode類型得結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)得 BinTree型頭指針就構(gòu)成了二叉樹得鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就就是由根指針 root唯一定得。共有2n個(gè)指針域，n+1個(gè)空指針。根據(jù)訪問結(jié)點(diǎn)得次序不同可得三種遍歷： 先序遍歷（前序遍歷或先根遍歷） 中序遍歷（或中根遍歷）后序遍歷（后根遍歷）。時(shí)間復(fù)雜度為 O（。利用二叉鏈表中得 n+1個(gè)空指針域來存放指向某種遍歷次序下得前趨結(jié)點(diǎn)與后繼結(jié)點(diǎn)得指針， 這些附加得指針就為“線索”，加上線索得二叉鏈表就稱為線索鏈表。線索使得查找中序前趨與中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)得前序前趨與后序后繼并沒有什么作用。樹與森林及二叉樹得轉(zhuǎn)換就是唯一對(duì)應(yīng)得。轉(zhuǎn)換方法： ·樹變二叉樹：兄弟相連，保留長子得連線?！ざ鏄渥儤洌航Y(jié)點(diǎn)得右孩子與其雙親連。·森林變二叉樹：樹變二叉樹，各個(gè)樹得根相連。樹得存儲(chǔ)結(jié)構(gòu)：·有雙親鏈表表示法：結(jié)點(diǎn) data|parent，對(duì)于求指定結(jié)點(diǎn)得雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)得孩子及后代?！ず⒆渔湵肀硎痉ǎ簽闃渲忻總€(gè)結(jié)點(diǎn) data|next設(shè)置一個(gè)孩子鏈表 firstchild，并將data|firstchild存放在一個(gè)向中。·雙親孩子鏈表表示法：將雙親鏈表與孩子鏈表結(jié)合?！ず⒆有值苕湵肀硎痉ǎ航Y(jié)點(diǎn)結(jié)構(gòu) leftmostchild|data|rightsibing ，附加兩個(gè)分別指向該結(jié)點(diǎn)得最左孩子與右鄰弟得指針域。樹得前序遍歷與相對(duì)應(yīng)得二叉樹得前序遍歷一致；樹得后序遍歷與相對(duì)應(yīng)得二叉樹得中序遍歷一致。樹得帶權(quán)路徑長度就是樹中所有葉結(jié)點(diǎn)得帶權(quán)路徑長度之與。 樹得帶權(quán)路徑長度最小得二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹）。在葉子得權(quán)值相同得二叉樹中，完全二叉樹得路徑長度最短。哈夫曼樹有 n個(gè)葉結(jié)點(diǎn)，共有 2n-1個(gè)結(jié)點(diǎn)，沒有度為 1得結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。變長編碼技術(shù)可以使頻度高得字符編碼短，而頻度低得字符編碼長，但就是變長編碼可能使解碼產(chǎn)生二義性。如00、0001符編碼得前綴，這種碼稱為前綴碼（其實(shí)就是非前綴碼） 。哈夫曼樹得應(yīng)用最廣泛地就是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布得最優(yōu)前綴碼。哈夫曼編碼得構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼 右路徑上寫代碼 1，然后從上到到葉結(jié)點(diǎn)得相應(yīng)路徑上得代碼得序列就就是該結(jié)點(diǎn)得最優(yōu)前綴碼。第七章 圖圖得邏輯結(jié)構(gòu)特征就就是其結(jié)點(diǎn)（頂點(diǎn)）得前趨與后繼得個(gè)數(shù)都就是沒有限制得，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。圖GraphG=（V，V就是頂點(diǎn)得有窮非空集合， E就是頂點(diǎn)偶對(duì)得有窮集。有向圖Digraph：每條邊有方向；無向圖 Undigraph：每條邊沒有方向。有向完全圖：具有 n*（n-1）條邊得有向圖；無向完全圖：具有 n*（/2條邊得無向圖；有根圖：有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)得有向圖；簡(jiǎn)單路徑：就是經(jīng)過頂點(diǎn)不同得路徑；簡(jiǎn)單回路就是開始與終端重得簡(jiǎn)單路徑；網(wǎng)絡(luò)：就是帶權(quán)得圖。圖得存儲(chǔ)結(jié)構(gòu)：·鄰接矩陣表示法：用一個(gè) n階方陣來表示圖得結(jié)構(gòu)就是唯一得，適合稠密圖?！o向圖：鄰接矩陣就是對(duì)稱得。·有向圖：行就是出度，列就是入度。建立鄰接矩陣算法得時(shí)間就是 O（e，其時(shí)間復(fù)雜度為 O（2）·鄰接表表示法：用頂點(diǎn)表與鄰接表構(gòu)成不就是唯一得，適合稀疏圖