【正文】 表的定義：用數(shù)據(jù)元素的有限序列表示◆ 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 j++ )a[j1]=a[j]。 // 第一個結(jié)點值為字符apnext=(node*)malloc(m)。 //首先保存b的指針，靠它才能找到c；pnext=qnext。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種線性關(guān)系，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠指針來反映這種關(guān)系的。例：在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為 O（n）8. 順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點？ 順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。 V[0]=39?！?棧的定義及操作。 //隊尾指針 } LinkQueue。q, QElemType e){//向循環(huán)隊列 q 的隊尾加入一個元素 e if ( (+1) % QUEUE_MAXSIZE = = ) return ERROR 。，若約定隊首指針指向隊首元素的前一個位置。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。樹：由一個或多個(n≥0)結(jié)點組成的有限集合T，有且僅有一個結(jié)點稱為根（root），當(dāng)n1時，其余的結(jié)點分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。 回顧2：二叉樹怎樣還原為樹？ 要點：逆操作，把所有右孩子變?yōu)樾值埽?討論1：森林如何轉(zhuǎn)為二叉樹？ 法一：① 各森林先各自轉(zhuǎn)為二叉樹；② 依次連到前一個二叉樹的右子樹上?！?二叉樹遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實用的算法，如求二叉樹的高度、各結(jié)點的層次數(shù)、度為0、2的結(jié)點數(shù)?？臻g效率為O(n2)。限定各邊上的權(quán)值大于或等于0。3. 用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲3. 若對連通圖進行遍歷，得到的是生成樹 若對非連通圖進行遍歷，得到的是生成森林。特點：塊間有序，塊內(nèi)無序。有兩種解決方法：法1：令*p的左子樹為 *f的左子樹，*p的右子樹接為*s的右子樹； //即 fL=PL 。補充：？ 給定一個值K，在含有n個記錄的文件中進行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。1) 直接插入排序 在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。此方法具有鏈表排序和地址排序的特點表插入排序算法分析：① 無需移動記錄，只需修改指針值。選擇排序的基本思想是：每一趟在后面ni 個待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i 個記錄。優(yōu)點：減少比較次數(shù)，加快排序速度缺點：空間效率低3） 堆排序：設(shè)有n個元素的序列 k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。補充：？時間效率——排序速度（即排序所花費的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 個優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。2） 快速排序基本思想：從待排序列中任取一個元素 (例如取第一個) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。優(yōu)點：比較次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。 穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。有序表的平均查找長度不超過樹的深度。 //查找不成功，生成一個新結(jié)點s，插入到二叉排序樹葉子處case { t=NULL： t=s。缺點： ASL 太大，時間效率太低。 應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹的生成過程。 求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法 Kruskal算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。(數(shù)組)表示法① 建立一個頂點表和一個鄰接矩陣② 設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 [n][n]。(3) 在F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F中。一般從根結(jié)點開始存儲。 //否則屬于iS[0]情況，i先到尾就不正常} //Index_BP補充重點：？答：有區(qū)別。模式匹配算法補充重點：1. 為什么要設(shè)計堆棧？它有什么獨特用途？① 調(diào)用函數(shù)或子程序非它莫屬；② 遞歸運算的有力工具；③ 用于保護現(xiàn)場和恢復(fù)現(xiàn)場；④ 簡化了程序設(shè)計的問題。//內(nèi)存分配失敗，退出程序 ==0。 //元素 Struct QNode *next。 display( )。解：介紹3種存儲形式。(x)—— 計算變量x的長度（字節(jié)數(shù)）； malloc(m) — 開辟m字節(jié)長度的地址空間，并返回這段空間的首地址； free(p) —— 釋放指針p所指變量的存儲空間，即徹底刪除一個變量。 在二維數(shù)組中，我們既可以規(guī)定按行存儲，也 可以規(guī)定按列存儲。 j++。 //m=sizeof(node) 前面已求出p=head。 插入時的平均移動次數(shù)為：n(n+1)/2247。①正確性、②可讀性、③健壯性、④效率與低存儲量需求◆ 算法分析。數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實際意義。 核心語句: V[i]=x。}node。 p=pnext。 pprior = s ?！?數(shù)組（主要是二維）在以行序/列序為主的存儲中的地址計算方法?！? 順序表適宜于做查找這樣的靜態(tài)操作；◆ 鏈表宜于做插入、刪除這樣的動態(tài)操作。 }void display( ) //字母線性表的顯示，即讀表操作{ int i。 順序棧入棧函數(shù)PUSH（）status Push(ElemType e) { if(topM){上溢} else s[top++]=e。2. 順序隊順序隊類型定義：define QUEUEMAXSIZE 100 //最大隊列長度 typedef struct { QElemType *base。3） 出隊操作Status DeQueue ( SqQueue amp。第四章 串內(nèi)容提要 while ( i=S[0] amp。性質(zhì)2: 深度為k的二叉樹至多有2k1個結(jié)點（k0）。① 先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；先根遍歷第一棵樹的根結(jié)點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林?！?哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索 深度優(yōu)先搜索（遍歷）步驟：① 訪問起始點 v。 如果圖中任意一對頂點都是連通的, 則稱此圖是連通圖。 針對靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找 一、順序查找（線性查找） 技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。② 二叉排序樹的插入與刪除思路：查找不成功，生成一個新結(jié)點s，插入到二叉排序樹中；查找成功則返回。如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。ASL=∑ Pi. Ci，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序：① 查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；② 中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實現(xiàn)了排序運算）；③ 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除時只需修改指針而不需移動元素。 i =。5） 希爾（shell）排序基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。 i。僅在第二個for循環(huán)中交換記錄時用到一個臨時變量temp。優(yōu)點：對小文件效果不明顯，但對大文件有效。 if( i!=j ) r[i] 171。◆ 交換排序（冒泡排序、快速排序）。 j=i1 。平衡旋轉(zhuǎn)可以歸納為四類：學(xué)習(xí)重點：t) { //K為待查關(guān)鍵字，t為根結(jié)點指針 p=t。 for( i=。 ② 生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n1條邊。基本思想：——仿樹的先序遍歷過程。滿二叉樹是完全二叉樹的一個特例?！?二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。 性質(zhì)5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）。 j=T[0] ) //如果i,j二指針在正常長度范圍， { if (S[