數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)知識(shí)點(diǎn).doc

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)知識(shí)點(diǎn)試題類型：本課程為考試科目（閉卷筆試），試題類型包括：概念填空題（10 %），是非判斷題（10 %），單項(xiàng)選擇題（40 %），算法填空題（10%），算法應(yīng)用題（20 %)，算法設(shè)計(jì)題（10 %）。第一章 緒論重點(diǎn)內(nèi)容及要求：1、 了解與數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念（集合、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、關(guān)鍵字、元素之間的關(guān)系等）。數(shù)據(jù)： 所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合。是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素：是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體來考慮和處理。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，數(shù)據(jù)元素可以是一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合關(guān)鍵碼：也叫關(guān)鍵字（Key），是數(shù)據(jù)元素中能起標(biāo)識(shí)作用的數(shù)據(jù)項(xiàng)。其中能起到唯一標(biāo)識(shí)作用的關(guān)鍵碼稱為主關(guān)鍵碼（簡(jiǎn)稱主碼）；否則稱為次關(guān)鍵碼。通常，一個(gè)數(shù)據(jù)元素只有一個(gè)主碼，但可以有多個(gè)次碼。關(guān)系：指一個(gè)數(shù)據(jù)集合中數(shù)據(jù)元素之間的某種相關(guān)性。數(shù)據(jù)結(jié)構(gòu)：帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合。這里的結(jié)構(gòu)指元素之間存在的關(guān)系。數(shù)據(jù)類型：是一個(gè)值的集合和定義在此集合上的一組操作的總稱。2、 掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、數(shù)據(jù)的邏輯結(jié)構(gòu)（四種）和物理結(jié)構(gòu)（數(shù)據(jù)元素的表示與關(guān)系的表示、兩類存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩個(gè)層次。數(shù)據(jù)的邏輯結(jié)構(gòu)：是對(duì)數(shù)據(jù)元素之間存在的邏輯關(guān)系的一種抽象的描述，可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示邏輯結(jié)構(gòu)有四種：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)、集合結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)：是其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示或?qū)崿F(xiàn)，因此又稱其為存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：利用數(shù)據(jù)元素在存儲(chǔ)器中相對(duì)位置之間的某種特定的關(guān)系來表示數(shù)據(jù)元素之間的邏輯關(guān)系；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：除數(shù)據(jù)元素本身外，采用附加的“指針”表示數(shù)據(jù)元素之間的邏輯關(guān)系。3、 了解算法分析的基本方法，掌握算法時(shí)間復(fù)雜度相關(guān)的概念。算法：是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列或處理問題的策略一個(gè)算法必須滿足以下五個(gè)重要特性：1有窮性 2確定性 3可行性4有輸入 5有輸出設(shè)計(jì)算法時(shí)，通常還應(yīng)考慮滿足以下目標(biāo)： 1.正確性，2.可讀性， 3.健壯性 4.高效率與低存儲(chǔ)量需求如何估算 算法的時(shí)間復(fù)雜度？算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間 = 原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間與 原操作執(zhí)行次數(shù)之和成正比 算法的空間復(fù)雜度定義為:S(n) = O(g(n)表示隨著問題規(guī)模 n 的增大,算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與 g(n) 的增長(zhǎng)率相同。算法的存儲(chǔ)量包括:1. 輸入數(shù)據(jù)所占空間2. 程序本身所占空間3. 輔助變量所占空間第二章 線性表重點(diǎn)內(nèi)容及要求：1、 掌握線性表的順序存儲(chǔ)結(jié)構(gòu)，了解順序表的存儲(chǔ)特點(diǎn)（數(shù)據(jù)元素在內(nèi)存中依次順序存儲(chǔ)），優(yōu)點(diǎn)：可隨機(jī)存取訪問；缺點(diǎn)：結(jié)點(diǎn)的插入/刪除操作不方便。線性表：是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，也是構(gòu)造其它各類復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。一個(gè)數(shù)據(jù)元素的有序（次序）集。它有順序和鏈?zhǔn)絻煞N存儲(chǔ)表示方法。 線性表必有：1集合中必存在唯一的一個(gè)“第一元素”2集合中必存在唯一的一個(gè) “最后元素”3除最后元素在外，均有 唯一的后繼；4除第一元素之外，均有 唯一的前驅(qū)定義如下：typedef int ElemType;typedef struct ElemType*elem; /存儲(chǔ)數(shù)據(jù)元素的一維數(shù)組； int length; /線性表當(dāng)前長(zhǎng)度； int listsize; /當(dāng)前分配數(shù)組容量；SqList;Void InitSqList(SqList A,int maxsize)/初始化線性表 A.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!A.elem) exit(0); A.length = 0; A.listsize = LIST_INIT_SIZE; return ; 2、 了解線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，重點(diǎn)掌握帶頭結(jié)點(diǎn)的單鏈表的基本操作（結(jié)點(diǎn)的插入與刪除運(yùn)算），了解單向循環(huán)鏈表和雙向鏈表存儲(chǔ)表示方法。單鏈表：用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。以元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置) = 結(jié)點(diǎn) (表示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象)單鏈表是一種順序存取的結(jié)構(gòu)，求以此為存儲(chǔ)表示的線性表長(zhǎng)度，可設(shè)置一個(gè)計(jì)數(shù)器3、了解有序線性表的特點(diǎn)（順序有序表、有序鏈表）。有序線性表：線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，則稱該線性表為有序表(Ordered List)4、學(xué)會(huì)對(duì)線性表設(shè)計(jì)相關(guān)的算法進(jìn)行相應(yīng)的處理。第三章 排序重點(diǎn)內(nèi)容及要求：1、掌握對(duì)順序表數(shù)據(jù)記錄進(jìn)行排序的基本思路和常規(guī)操作（比較、移動(dòng)），了解排序算法的穩(wěn)定性問題。2、掌握簡(jiǎn)單選擇排序、直接插入排序、冒泡排序算法，了解各種排序算法的特點(diǎn)及時(shí)間復(fù)雜度。排序：將一組“無序”的記錄序列按某一關(guān)鍵字調(diào)整為“有序”的記錄序列。若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；反之則為外部排序。 選擇排序：從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度基本代碼如下for(i=0;in-1;i+)/*外循環(huán)控制趟數(shù)，n個(gè)數(shù)選n-1趟*/k=i;/*假設(shè)當(dāng)前趟的第一個(gè)數(shù)為最值,記在k中 */for(j=i+1;jn;j+)/*從下一個(gè)數(shù)到最后一個(gè)數(shù)之間找最值*/if(akaj)/*若其后有比最值更大的*/k=j;/*則將其下標(biāo)記在k中*/if(k!=i)/*若k不為最初的i值，說明在其后找到比其更大的數(shù)*/t=ak;ak=ai;ai=t;/*則交換最值和當(dāng)前序列的第一個(gè)數(shù)*/插入排序：插入排序是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)。代碼如下：void InsertSort ( SqList &L) / 對(duì)順序表L作插入排序 for ( i=2; i=L.length; +i ) if ( L.ri.key L.ri-1.key ) L.r0 = L.ri; / 復(fù)制為哨兵 for ( j=i-1; L.r0.key 1) / i1 表明上一趟曾進(jìn)行過記錄的交換 lastExchangeIndex = 1; for (j = 1; j i; j+) if (L.rj+1.key L.rj.key) W=L.rj；L.rj =L.rj+1；L.rj+1 = W； / 互換記錄 lastExchangeIndex = j; i = lastExchangeIndex; / 一趟排序中無序序列中最后一個(gè)記錄的位置 3、 了解什么是堆？堆是滿足下列性質(zhì)的數(shù)列r1, r2, ，rn：(小頂堆) (大頂堆) 第四章 棧和隊(duì)列重點(diǎn)內(nèi)容及要求：1、掌握棧和隊(duì)列的結(jié)構(gòu)特點(diǎn)及基本操作（入棧、出棧/入隊(duì)、出隊(duì)）。棧（后進(jìn)先出），隊(duì)列（先進(jìn)先出）構(gòu)造空棧：void InitStack_Sq (SqStack &S) / 構(gòu)造一個(gè)空棧S S.elem = new SElemTypemaxsize; S.top =-1; S.stacksize = maxsize; S.incrementsize=incresize; 棧：（入棧）void Push_Sq(SqStack &S, SElemType e) if (S.top = S.stacksize-1) incrementStacksize (S); / 如果順序棧的空間已滿，應(yīng)為棧擴(kuò)容 S.elem+S. top = e; / 在棧頂插入數(shù)據(jù)元素棧：（入棧）bool Pop_Sq (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用e返回其值，并返回TRUE； / 否則返回FALSE。 if (S.top = -1) return FALSE; e = S.elemS.top- -; return TRUE;2、對(duì)于順序棧，熟悉棧空和棧滿的條件；對(duì)于鏈棧，掌握其棧空的條件。#include using namespace std;#define INITSIZE 100#define RESIZE 20typedef struct int *base; int *top; int stacksize;Sqstack;int Initstack(Sqstack S) S.base=(int *)malloc(INITSIZE*sizeof(int); if(!S.base) return false; S.top=S.base; S.stacksize=INITSIZE; return true;int Clearstack(Sqstack &S) free(S.base); S.base=(int *)malloc(INITSIZE*sizeof(int); S.top=S.base; return true;int Stackempty(Sqstack S) if(S.base=S.top) return true; else return false;int Push(Sqstack &S,int e) if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(RESIZE+INITSIZE)*sizeof(int); if(!S.base) return false; S.top=S.base+S.stacksize; S.stacksize+=RESIZE; *S.top+=e; return true;int Pop(Sqstack &S,int &e) if(S.base=S.top) return false; e=*-S.top; return true; int main() Sqstack S; int t,e; Initstack(S); cint; /需要輸入元素的個(gè)數(shù) while(t-) cine; Push(S,e); /進(jìn)棧 while(S.top!=S.base) Pop(S,e); coutetop; while(p) q=p; p=p-next; free(q); S-count=0; return OK;3、掌握棧的典型應(yīng)用背包問題求解的基本方法。背包問題假設(shè)有n件體積分別為w1,w2,wn的物品和一個(gè)能裝載體積為T的背包.能否從n件物品中選擇若干件恰好裝滿背包, 即 wi1+wi2+wik = T,則背包問題有解； 否則無解. 以W(1,8,4,3,5,2), T=10為例 (1,4,3,2 ), (1,4,5 ), (8,2)和(3,5, 2)是其解。算法如下void knapsack(int w, int T, int n) / T在算法中是剩余的容積，初值為背包的體積 InitStack(S); k=0; do while (T0 & k=0) / 第k件物品可以進(jìn)棧 Push(S, k); T =wk; k+; if (T=0) StackTraverse(S); / 輸出一個(gè)解 Pop (S, k); T+ =wk; / 退出棧頂物品 k+; while (!StackEmpty(S) | kfront=q-rear-NULL; /初始化 int QueueEmpty(LiQueue *q) if(q-rear=NULL)return 1;else return 0; /判空 void enQueue( LiQueue *&q,ElemType e) QNode *s;s=(QNode *)malloc(sizeof(QNode);s-data=e;s-next=NULL;if(q-rear=NULL)q-front=q-rear=s;elseq-rear-next=s;q-rear=s; /入隊(duì) int deQueue( LiQueue *&q,ElemType &e) QNode *t;if(q-rear=NULL)return0;t=q-front;if(q-front=q-rear)q-front=q-rear=NULL;elseq-front=q-front-next;e=t-data;free(t);return 1; /出隊(duì) int deQueue( LiQueue *&q,ElemType &e) QNode *t;if(q-rear=NULL)return0;t=q-front;if(q-front=q-rear)q-front=q-rear=NULL;elseq-front=q-front-next;e=t-data;break;free(t);return 1; /取隊(duì)頭5、對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的循環(huán)隊(duì)列，掌握隊(duì)列為空、隊(duì)列滿的條件，及隊(duì)列的基本操作。循環(huán)隊(duì)列判斷空滿有兩種方法： 1.另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列空滿；2.少用一個(gè)元素空間，當(dāng)隊(duì)頭指針在隊(duì)尾指針下一位時(shí)，隊(duì)列為滿，當(dāng)隊(duì)頭指針與隊(duì)尾指針相同是隊(duì)列為空。在循環(huán)隊(duì)列下，仍定義front=rear時(shí)為隊(duì)空，而判斷隊(duì)滿則用兩種辦法，一是用“犧牲一個(gè)單元”，即rear+1=front（準(zhǔn)確記是（rear+1）%m=front，m是隊(duì)列容量）時(shí)為隊(duì)滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記tag，tag等于0情況下，若刪除時(shí)導(dǎo)致front=rear為隊(duì)空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊(duì)滿。第五章 串和數(shù)組重點(diǎn)內(nèi)容及要求：1、掌握字符串類型的定義及存儲(chǔ)表示方法。一般情況之下用char定義，串（String ），或稱字符串是由零個(gè)或多個(gè)字符組成的有限序列。記作：S = a0a1aian-1 （n0）其中，ai屬于字符集， n為串的長(zhǎng)度，當(dāng)n=0 時(shí)串為空串存儲(chǔ)特點(diǎn)串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過予定義長(zhǎng)度的串值則被舍去，稱之為“截?cái)唷?按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為 “字符序列的復(fù)制”2、掌握數(shù)組的定義和存儲(chǔ)結(jié)構(gòu)，熟悉二維數(shù)組中數(shù)據(jù)元素按行存儲(chǔ)的基本方法，會(huì)計(jì)算元素的存儲(chǔ)地址。數(shù)組的定義和存儲(chǔ)結(jié)構(gòu)數(shù)組是線性表的一種擴(kuò)充，一維數(shù)組即為線性表，二維數(shù)組定義為“其數(shù)組元素為一維數(shù)組”的線性表3、了解矩陣壓縮存儲(chǔ)的目的、原理及基本思路和方法。矩陣壓縮存儲(chǔ)的目的1) 零值元素占了很大空間;2) 計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。原理及基本思路和方法1) 盡可能少存或不存零值元素；2) 盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；3) 操作方便。 即： 能盡可能快地找到與下標(biāo)值(i, j)對(duì)應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。4、了解隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法（三元組順序表、十字鏈表）。三元組順序表十字鏈表第六章 二叉樹重點(diǎn)內(nèi)容及要求：1、掌握二叉樹的定義、特點(diǎn)及相關(guān)概念。結(jié)點(diǎn)的層次:假設(shè)根結(jié)點(diǎn)的層次為1,第l 層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次二叉樹的定義 二叉樹是n（n0）個(gè)元素的有限集，它或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。2、了解二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)特點(diǎn)，掌握二叉樹的順序存儲(chǔ)結(jié)構(gòu)主要用于完全二叉樹。二叉樹的性質(zhì)：1. 在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn) (i1) 。2. 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）。3. 對(duì)任何一棵二叉樹，若它含有n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：n0 = n2+1。4. 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1 。若對(duì)含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為 i 的結(jié)點(diǎn)： (1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，編號(hào)為 i/2 的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；(2) 若 2in，則該結(jié)點(diǎn)無左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；(3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。3、掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。4、了解二叉樹遍歷的基本方法（先根次序、中根次序及后根次序遍歷二叉樹）。5、了解堆排序的基本方法、了解二叉排序樹的基本特點(diǎn)以及如何構(gòu)造一棵哈夫曼樹。樹和森林樹和森林的存儲(chǔ)結(jié)構(gòu) 第七章 圖重點(diǎn)內(nèi)容及要求：1、了解圖的基本概念和相關(guān)術(shù)語。圖是較樹結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)圖Graph是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，記作Graph = (V , E )。 其中，圖的頂點(diǎn)為數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，弧的集合E是定義在頂點(diǎn)集合V上的一個(gè)關(guān)系。有序?qū)?表示從 v 到 w 的一條弧，并稱 v 為弧頭，w 為弧尾。 謂詞 P(v,w) 定義了弧 的意義或信息由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖2、了解圖的存儲(chǔ)結(jié)構(gòu)特點(diǎn)（鄰接矩陣、鄰接表存儲(chǔ)結(jié)構(gòu)）。鄰接矩陣： 鄰接表存儲(chǔ) 3、了解圖的遍歷方法（深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS）。深度優(yōu)先搜索DFS連通圖的深度優(yōu)先搜索遍歷從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。void DFS(Graph G, int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for (w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) ) if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用DFS / DFS非連通圖的深度優(yōu)先搜索遍歷首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。void DFSTraverse(Graph G ) / 對(duì)圖 G 作深度優(yōu)先遍歷 for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS廣度優(yōu)先搜索BFS從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。void BFSTraverse(Graph G, int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 / BFSTraverse以深度優(yōu)先搜索 DFS 和廣度優(yōu)先搜索 BFS 的算法為框架, 可以派生出很多有實(shí)用價(jià)值的應(yīng)用。1. 求一條從頂點(diǎn) i 到頂點(diǎn) s 的簡(jiǎn)單路徑；2. 求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑；3. 求迷宮的最短路徑。4、了解連通網(wǎng)的最小生成樹和單源最短路徑算法。連通網(wǎng)的最小生成樹構(gòu)造網(wǎng)的一棵最小生成樹, 即:在 e 條帶權(quán)的邊中選取 n-1 條邊(不構(gòu)成回路), 使“權(quán)值之和”為最小用（普里姆算法）或（克魯斯卡爾算法）解決；普里姆算法的基本思想:取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根，之后往生成樹上添加新的頂點(diǎn) w。在添加的頂點(diǎn) w 和已經(jīng)在生成樹上的頂點(diǎn)v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v 和 w 之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n-1 個(gè)頂點(diǎn)為止。 克魯斯卡爾算法的基本思想：考慮問題的出發(fā)點(diǎn): 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使 SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。 單源最短路徑算法求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到頂點(diǎn)v的最短路徑是所有最短路徑中長(zhǎng)度最短者。 第八章 查找表重點(diǎn)內(nèi)容及要求：1、掌握線性表的查找算法（順序查找、折半查找、分塊查找）。查找表：靜態(tài)查找表、動(dòng)態(tài)查找表靜態(tài)查找表：順序查找、折半查找、分塊查找動(dòng)態(tài)查找表：二叉查找樹、二叉平衡樹、鏈樹（數(shù)字查找樹）順序查找：以順序表或線性鏈表表示靜態(tài)查找表實(shí)現(xiàn)的算法：int Search_Seq (SSTable ST, KeyType kval) / 在順序表ST中順序查找其關(guān)鍵字等于kval的數(shù)據(jù)元素。 若找到，則函數(shù)值為該元素在表中的位置，否則為0。 ST.elem0.key = kval; / 設(shè)置哨兵 for (i=ST.length; ST.elemi.key != kval; -i); / 從后往前查找 return i; / 找不到時(shí)，i為0其中“for (i=ST.length; ST.elemi.key != kval; -i);”還可以寫成“for (i=0; iST.length; i+)if(ST.elemi.key = kval) Cout”輸出結(jié)果：” ST.elemi.key endl;Return (i=0);”折半查找（二分查找）：若以有序表表示靜態(tài)查找表，則查找過程可以按“折半” 進(jìn)行。實(shí)現(xiàn)的算法：int Search_Bin ( SSTable ST, KeyTyp