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

1、數(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ù)

2、據(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ù)元素

3、之間存在的邏輯關(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確

4、定性3可行性4有輸入5有輸出設(shè)計(jì)算法時(shí)，通常還應(yīng)考慮滿足以下目標(biāo)：正確性，2.可讀性，3.健壯性4.高效率與低存儲(chǔ)量需求如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)I語(yǔ)=原操作（i）的執(zhí)行次數(shù)X原操作（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ǔ)量包括:輸入數(shù)據(jù)所占空間程序本身所占空間輔助變量所占空間第二章線性表重點(diǎn)內(nèi)容及要求：1、掌握線性表的順序存儲(chǔ)結(jié)構(gòu)，了解順序表的存儲(chǔ)特點(diǎn)（數(shù)據(jù)元素在內(nèi)存中依次順序存儲(chǔ)），優(yōu)點(diǎn)：

5、可隨機(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ū)定義如下：/存儲(chǔ)數(shù)據(jù)元素的一維數(shù)組；/線性表當(dāng)前長(zhǎng)度；/當(dāng)前分配數(shù)組容量；,intmaxsize）/初始化線性表typedefintElemTypetypedefstructElemType*elem;intlength;intlistsize;SqList;VoidI

6、nitSqList(SqListA.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ǔ)表示的線性

7、表長(zhǎng)度，可設(shè)置一個(gè)計(jì)數(shù)器3、了解有序線性表的特點(diǎn)（順序有序表、有序鏈表）。有序線性表：線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即a$a或aWii-1ia(i=2,3,n),則稱該線性表為有序表(OrderedList)i-14、學(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ù)雜度。排序：將一組“無(wú)序”的記錄序列按某一關(guān)鍵字調(diào)整為“有序”的記錄序列。若整個(gè)排序

8、過程不需要訪問外存便能完成,則稱此類排序問題為內(nèi)部排序；反之則為外部排序。選擇排序：從記錄的無(wú)序子序列中“選擇”關(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;/*則交換最值和

9、當(dāng)前序列的第一個(gè)數(shù)*/插入排序：插入排序是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)。代碼如下：voidInsertSort(SqList&L)/對(duì)順序表L作插入排序for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)L.r0=L.ri;/復(fù)制為哨兵for(j=i-1;L.r0.key1)/i1表明上一趟曾進(jìn)行過記錄的交換lastExchangeIndex=1;for(j=1;ji;j+)if(L.rj+1.keyrrJi2i+1第四章棧和隊(duì)列重點(diǎn)內(nèi)容及要求：1、掌握棧和隊(duì)列的結(jié)構(gòu)特點(diǎn)及基本操作（入棧、出棧/入隊(duì)、出隊(duì)）棧（

10、后進(jìn)先出），隊(duì)列（先進(jìn)先出）構(gòu)造空棧：voidInitStack_Sq(SqStack&S)/構(gòu)造一個(gè)空棧SS.elem=newSElemTypemaxsize;S.top=-1;S.stacksize=maxsize;S.incrementsize=incresize;棧：(入棧)voidPush_Sq(SqStack&S,SElemTypee)if(S.top=S.stacksize-1)incrementStacksize(S);/如果順序棧的空間已滿，應(yīng)為棧擴(kuò)容S.elem+S.top=e;/在棧頂插入數(shù)據(jù)元素棧：(入棧)boolPop_Sq(SqStack&S,SElemType&e

11、)/若棧不空，則刪除S的棧頂元素，/用e返回其值，并返回TRUE；/否則返回FALSE。if(S.top=-1)returnFALSE;e=S.elemS.top-;returnTRUE;2、對(duì)于順序棧，熟悉棧空和棧滿的條件；對(duì)于鏈棧，掌握其?？盏臈l件。#includeusingnamespacestd;#defineINITSIZE100#defineRESIZE20typedefstructint*base;int*top;intstacksize;Sqstack;intInitstack(SqstackS)S.base=(int*)malloc(INITSIZE*sizeof(int);

12、if(!S.base)returnfalse;S.top=S.base;S.stacksize=INITSIZE;returntrue;intClearstack(Sqstack&S)free(S.base);S.base=(int*)malloc(INITSIZE*sizeof(int);S.top=S.base;returntrue;intStackempty(SqstackS)if(S.base=S.top)returntrue;elsereturnfalse;intPush(Sqstack&S,inte)if(S.top-S.base=S.stacksize)S.base=(int*)

13、realloc(S.base,(RESIZE+INITSIZE)*sizeof(int);if(!S.base)returnfalse;S.top=S.base+S.stacksize;S.stacksize+=RESIZE;*S.top+=e;returntrue;intPop(Sqstack&S,int&e)if(S.base=S.top)returnfalse;e=*-S.top;returntrue;intmain()SqstackS;intt,e;Initstack(S);cint;/需要輸入元素的個(gè)數(shù)while(t-)cine;Push(S,e);/進(jìn)棧while(S.top!=S

14、.base)Pop(S,e);coutetop;while(p)q=p;p=p-next;free(q);S-count=0;returnOK;3、掌握棧的典型應(yīng)用背包問題求解的基本方法。背包問題假設(shè)有n件體積分別為w1,w2,wn的物品和一個(gè)能裝載體積為T的背包.能否從n件物品中選擇若干件恰好裝滿背包,即wi1+wi2+wik=T,則背包問題有解；否則無(wú)解.以W(1,8,4,3,5,2),T=10為例(1,4,3,2),(1,4,5),(8,2)和(3,5,2)是其解。利用回溯的算法思想求解背包問題T=10I1+4+3+2=10從背包中取岀物品再繼續(xù)搜索的策略稱之為回溯，其規(guī)則是后進(jìn)先出=即

15、背包算法如下1以棧的操作完成求解口voidknapsack(intw,intT,intn)/T在算法中是剩余的容積，初值為背包的體積InitStack(S);k=0;dowhile(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;/初始化intQueueEmpty(LiQueue*q)if(q-rear=NULL)return1;elsereturn0;/判空voidenQueue(L

16、iQueue*&q,ElemTypee)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ì)intdeQueue(LiQueue*&q,ElemType&e)QNode*t;if(qrear二二NULL)returnO;t二qfront;if(qfront二二qrear)qfront二q-rear二NULL;elseqfront二qfrontnext;e二tdata;free(t);return1;/出

17、隊(duì)intdeQueue(LiQueue*&q,ElemType&e)QNode*t;if(qrear二二NULL)returnO;t二qfront;if(qfront二二qrear)qfront二q-rear二NULL;elseqfront二qfrontnext;e二tdata;break;free(t);return1;/取隊(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

18、=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（n$0）其中，ai屬于字符集，n為串的長(zhǎng)度，當(dāng)n=0時(shí)串為空串存儲(chǔ)特點(diǎn)串的實(shí)際長(zhǎng)

19、度可在這個(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ù)組”的線性表數(shù)組的順序表亦和實(shí)現(xiàn)類型特點(diǎn)：只有引用型操作沒有加工型操作數(shù)組是多維的結(jié)構(gòu)*而存睹空間是一個(gè)一維的結(jié)構(gòu)二3、有兩種順序映象的方式：了解矩陣壓縮存儲(chǔ)的目的、原理及基本思路和方法。矩陣壓縮存儲(chǔ)的目的零值元素占了很大空間；計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇

20、除法，還需判別除數(shù)是否為零。原理及基本思路和方法盡可能少存或不存零值元素；盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；操作方便。即：能盡可能快地找到與下標(biāo)值(i,j)對(duì)應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。彳有兩類稀疏矩陣:特殊矩陣非零元在矩陣中的分布有一定規(guī)則例如:三角矩陣對(duì)角矩陣隨機(jī)稀疏矩陣非零元在矩陣中隨機(jī)出現(xiàn)4、了解隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法（三元組順序表、十字鏈表）。三元組順序表原稀疏矩陣TOC o 1-5 h z_01400-510-70003600280三元組表示的稀疏矩陣節(jié)省了空間，便于實(shí)現(xiàn)矩陣運(yùn)算嗎？十字鏈表三元組表示的稀疏矩陣第六章二叉樹重點(diǎn)內(nèi)容及要求：1、掌握二叉樹的定義

21、、特點(diǎn)及相關(guān)概念。對(duì)比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)I第一個(gè)數(shù)據(jù)元素（無(wú)前驅(qū)）最后一個(gè)數(shù)據(jù)元素（無(wú)后繼）其它數(shù)據(jù)元素（一個(gè)前驅(qū)、一個(gè)后繼）根結(jié)點(diǎn)（無(wú)前驅(qū)）多個(gè)葉子結(jié)點(diǎn)（無(wú)后繼）其它數(shù)據(jù)元素（一個(gè)前驅(qū)、_多個(gè)證）_51線性結(jié)構(gòu)樹型結(jié)構(gòu)i基本術(shù)語(yǔ)結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支結(jié)點(diǎn)的度:分支的個(gè)數(shù)樹的度:樹中所有結(jié)點(diǎn)的度的最大值葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn)分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)結(jié)點(diǎn)的層次：假設(shè)根結(jié)點(diǎn)的層次為1,第I層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次二叉樹的定義二叉樹是n（n$0）個(gè)元素的有限集，它或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二

22、叉樹組成。2、了解二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)特點(diǎn)，掌握二叉樹的順序存儲(chǔ)結(jié)構(gòu)主要用于完全二叉樹。二叉樹的性質(zhì)：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（iM1）。深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（kM1）。對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為L(zhǎng)Iog2nJ+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)是二叉樹的根，無(wú)雙親,否則，編號(hào)為L(zhǎng)i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；若2in,則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)

23、點(diǎn)；(3)若2計(jì)1n,則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。兩類特殊的二叉樹:滿二叉樹：指的是深度為氐且含有才個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的程個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為至料的結(jié)點(diǎn)對(duì)應(yīng)。3、掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。root鏈表c語(yǔ)言的類型描述如下:結(jié)點(diǎn)結(jié)構(gòu)：lchilddataIrchildtypedefstructBiTNode/結(jié)點(diǎn)結(jié)構(gòu)BiTNode,*BiTree;結(jié)點(diǎn)結(jié)構(gòu):2TElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指針lchilddatarchildACA4、了解二叉樹遍歷的基本方法（先根次序、

24、中根次序及后根次序遍歷二叉樹）。先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法纟同（根）序的遍歷算法1先（根）序的遍歷算法:中（根）序的遍歷算法:后（根）序的遍歷算法:若二叉樹為空樹，則空操作；否則,（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹;（3）先序遍歷右子樹。宇二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；j（2）訪問根結(jié)點(diǎn)；/就中序遍歷右子樹。何骨二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；滬2）后序遍歷右子樹；俺存歐湎：I訪問根結(jié)點(diǎn)。謨365、了解堆排序的基本方法、了樹和森林.排序樹特點(diǎn)以及如何構(gòu)造一棵哈夫曼樹。二叉樹遍歷的輸出順序示例演示是in(mO)棵互不相

25、交的樹的集合任何一棵非空樹是一個(gè)二元組Tree=(rootjF)其中：mot被稱為根結(jié)點(diǎn)、F被稱為子樹森林樹和森林的存儲(chǔ)結(jié)構(gòu)1雙親表示法2.孩子鏈表表示法3樹的二叉鏈表（孩子-兄弟）1.雙親表示法:B；E)(Fdataparentr=0d=6C語(yǔ)言的類型描述：defineMAXTREESIZE100結(jié)點(diǎn)結(jié)構(gòu):dataparenttypedefstructPTNodeElemdata;intparent;/雙親位置域PTNode;樹結(jié)構(gòu):typedefstructPTNodenodesMAXTREESIZE;intt,n;/根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)PTree;2.孩子鏈表表亦法datafirstc

26、hildtypedefstructCTNodeintchild;structCTNode*next;*ChildPtr;C語(yǔ)言的類型描述:雙親結(jié)點(diǎn)結(jié)構(gòu)datafirstchildchUdnext孩子結(jié)點(diǎn)結(jié)構(gòu):typedefstructElemdata;ChildPtrfirstchild;孩子鏈的頭指針CTBox;樹結(jié)構(gòu)：typedefstructCTBoxnodesMAX_TREE_SIZE;(intn,r;結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置CTree;3.樹的二叉鏈表（孩子-兄弟）存儲(chǔ)表示法C語(yǔ)言的類型描述：結(jié)點(diǎn)結(jié)構(gòu)：|firstchilddatanextsiblingtypedefstructCSNo

27、deElemdata;structCSNode興firstchild,*口extsibling;CSNode,*CSTree;第七章圖重點(diǎn)內(nèi)容及要求：1、了解圖的基本概念和相關(guān)術(shù)語(yǔ)。圖是較樹結(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ū),w表示從v到w的一條弧，并稱v為弧頭,w為弧尾。謂詞P(v,w)定義了弧v,w的意義或信息由于“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖T名詞和術(shù)語(yǔ)網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑

28、、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹，生成森林2、了解圖的存儲(chǔ)結(jié)構(gòu)特點(diǎn)(鄰接矩陣、鄰接表存儲(chǔ)結(jié)構(gòu))。鄰接矩陣：有向圖的鄰接矩陣為非對(duì)稱矩陣00100typedefstructArcCell/弧的定義VRTypeadj;/VRType是頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或0表亦相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType*infb;該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUM圖的結(jié)構(gòu)定義（鄰接矩陣）typedefstructVertexType/頂點(diǎn)信息vexsMAX_VERTEX_NUM;AdjMatrixarcs;/弧的

29、信息intvexnum?arcnum;/頂點(diǎn)數(shù)，弧數(shù)GraphKindkind;/圖的種類標(biāo)志MGraph;鄰接表存儲(chǔ):、圖的鄰接表存儲(chǔ)表不表結(jié)點(diǎn)之間無(wú)順序要求，由建圖時(shí)輸入的31a|信息次序決定有向圖的逆鄰接表在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。有向圖的鄰接表可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。OA2B3CDE3、了解圖的遍歷方法(深度優(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)都被訪問到。voi

30、dDFS(GraphG,intv)/從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisitedv=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)。voidDFSTraverse(GraphG)/對(duì)圖G作深度優(yōu)先遍歷for(v=0;vG.vexnum;+v)v

31、isitedv=FALSE;/訪問標(biāo)志數(shù)組初始化for(v=0;vw1；V-w2；V-w8的路徑長(zhǎng)度為1；V-w7,V-w3,V-w5的路徑長(zhǎng)度為2；V-w6,V-w4從圖中的某個(gè)頂點(diǎn)VO出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。voidBFSTraverse(GraphG,intv)for(v=O;vG.vexnum;+v)visitedv=FALSE;/初始化訪問標(biāo)志InitQueue(Q);/置空的輔助隊(duì)列Qfor(v=O;vG.vexnum;+v)if(!visited

32、v)/v尚未訪問/BFSTraverse以深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS的算法為框架,可以派生出很多有實(shí)用價(jià)值的應(yīng)用。求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑；求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑；求迷宮的最短路徑。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之間

33、的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n-1個(gè)頂點(diǎn)為止。廠二情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U和尚未落在生成樹上的頂點(diǎn)集VU,則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊.1918827例如?所得生成樹權(quán)值和=14+8+3+5+16+21=67克魯斯卡爾算法的基本思想：考慮問題的出發(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ù)，

34、直至加上n-1條邊為止。普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)適應(yīng)范圍稠密圖稀疏圖72比較兩種算法單源最短路徑算法求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑從源點(diǎn)到頂點(diǎn)v的最短路徑是所有最短路徑中長(zhǎng)度最短者。f路徑長(zhǎng)度最短的最短路徑的特點(diǎn)：在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):它只可能有兩種情況：或者是直接從源點(diǎn)到fFL條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)（只含一條弧）；或者是從源點(diǎn)經(jīng)過頂點(diǎn)V,再到達(dá)該頂點(diǎn)（由兩條弧組成）；或者是從源點(diǎn)經(jīng)過頂點(diǎn)V2,再到達(dá)該頂點(diǎn)。其余最短路徑的特點(diǎn)：它或者是直接從

35、源點(diǎn)到該點(diǎn)（只含一條?。?；該點(diǎn)（只含一條?。?；或者是從源點(diǎn)經(jīng)過頂點(diǎn)V,再到達(dá)該頂點(diǎn)（由兩條弧組成）。或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。求最短路徑的迪杰斯特拉算法：設(shè)置輔助數(shù)組DiSt,其中每個(gè)分量Distk表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑匚一般情況下，Distk=源點(diǎn)到頂點(diǎn)k的弧上的權(quán)值或者=源點(diǎn)到其它頂點(diǎn)的路徑長(zhǎng)度+其它頂點(diǎn)到頂點(diǎn)k的弧上的權(quán)值。1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。rinG.arcsvO伙V0和k之間存在弧Distlk=1INFINITYV0和k之間不存在弧其中的最小值即為最短路徑的長(zhǎng)度2）修改其它各頂點(diǎn)的Ds/

36、岡值。假設(shè)求得最短路徑的頂點(diǎn)為u,若Distii+G.arcsukDistk，則將Distk改為Distu+G.arcsu幻。帀第八章查找表重點(diǎn)內(nèi)容及要求：1、掌握線性表的查找算法（順序查找、折半查找、分塊查找）。查找表：靜態(tài)查找表、動(dòng)態(tài)查找表靜態(tài)查找表：順序查找、折半查找、分塊查找動(dòng)態(tài)查找表：二叉查找樹、二叉平衡樹、鏈樹（數(shù)字查找樹）順序查找：以順序表或線性鏈表表示靜態(tài)查找表實(shí)現(xiàn)的算法：intSearch_Seq（SSTableST,KeyTypekval）/在順序表ST中順序查找其關(guān)鍵字等于kval的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0。ST.elem0.key=kval;/設(shè)