數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點

第一章*掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)的定義，四類基本結(jié)構(gòu)。?數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。（數(shù)據(jù)（Data）:是客觀事物的符號表示。在計算機科學(xué)中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。）?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成。（數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。?數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。?數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。?四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。*數(shù)據(jù)結(jié)構(gòu)的邏輯表示與物理存儲->邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)?“數(shù)據(jù)結(jié)構(gòu)”定義中的“關(guān)系”指數(shù)據(jù)間的邏輯關(guān)系，故也稱數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。?數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為物理結(jié)構(gòu)。又稱存儲結(jié)構(gòu)。有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)?抽象數(shù)據(jù)類型定義（ADT）：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。*掌握算法的定義及特性，算法設(shè)計的要求?算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列五個重要特性。?算法的五個特性：有窮性：一個算法必須總是（對任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成；確定性：算法中每一條指令必須有確切的含義，讀者理解時不會產(chǎn)生二義性。有任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出?？尚行裕阂粋€算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。輸入：一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象的集合。輸出：一個算法有一個或多個的輸出。這些輸出是同輸入有著某些特定關(guān)系的量。?算法設(shè)計的要求1、正確性2、可讀性3、健壯性4、效率與低存儲量需求?效率指的是算法執(zhí)行時間。對于解決同一問題的多個算法，執(zhí)行時間短的算法效率高。?存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。?兩者都與問題的規(guī)模有關(guān)。*掌握算法的漸近時間復(fù)雜度和空間復(fù)雜度的意義與作用及計算方法?語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。?學(xué)會計算語句重復(fù)執(zhí)行的次數(shù)。?重點掌握算法的5個特性（有窮性，確定性，可行性，輸入，輸出），算法好壞衡量標(biāo)準(zhǔn)（好的算法要滿足正確性，可讀性，健壯性，效率與地存儲需求），給出一個算法，分析時間復(fù)雜度（表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同），語句頻度（指的是該語句重復(fù)執(zhí)行的次數(shù)）AW-—*第——早?線性表（LinearList）:由n（n弐）個數(shù)據(jù)元素（結(jié)點）a1,a2， ...an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：(al,a2,...an)其中ai是屬于某一個數(shù)據(jù)對象的數(shù)據(jù)元素。?線性表的邏輯特征是：1?線性表中所有元素的性質(zhì)是相同的，即具有相同數(shù)據(jù)類型。2?在非空的線性表，有且僅有一個開始結(jié)點al,它沒有直接前趨，而僅有一個直接后繼a2；3.有且僅有一個終端結(jié)點an,它沒有直接后繼，而僅有一個直接前趨an-1；4?其余的內(nèi)部結(jié)點ai(2旨旨1-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。?線性表的運算：基本運算：1?存?。捍嫒』蚋卤碇心硞€數(shù)據(jù)元素。2?插入：在表的兩個確定的元素之間插入一個新元素。3?刪除：刪除表中某個數(shù)據(jù)元素。4?查找：查找表中滿足某種條件的數(shù)據(jù)元素。如找出某個數(shù)據(jù)項具有給定值的數(shù)據(jù)元素。復(fù)雜運算：5?合并：把兩個線性表合并成一個線性表。6?分解：把一個線性表拆分成多個線性表。7?排序：按一個或多個數(shù)據(jù)項值的遞增或遞減次序重新排列表中數(shù)據(jù)元素。?最基本的運算有：查找、插入和刪除。?順序表一把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里這組連續(xù)的存儲單元稱為向量。假設(shè)線性表的每個元素需占用L個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1):LOC(ai+1)=L0C(a1)+L*i線性表的第i個數(shù)據(jù)元素ai的存儲位置為：LOC(ai)=LOC(a1)+(i-1)*L通常稱LOC(a1)為線性表的開始地址。?順序存儲結(jié)構(gòu)的特點：表中邏輯上相鄰的數(shù)據(jù)元素存儲在相鄰的存儲位置。即以數(shù)據(jù)元素在計算機內(nèi)“物理位置相鄰”來表示表中數(shù)據(jù)元素間的邏輯關(guān)系。要訪問第i個數(shù)據(jù)元素，就可以直接計算出ai的存儲位置LOC(ai)因此，是一種隨機存取的存儲結(jié)構(gòu)。?適合很少進(jìn)行插入和刪除，但要求以最快的速度存取表中元素的情況。?掌握順序表的存儲結(jié)構(gòu)表示和定義。?順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。?順序表：把用順序存儲結(jié)構(gòu)存放的線性表稱為順序表(C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。#defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;這是靜態(tài)分配存儲空間的定義。采用靜態(tài)分配時的構(gòu)造空線性表算法defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;StatusInitList(Sqlist*L){/*按靜態(tài)分配空間方式，構(gòu)造空線性表L*/L->length=O;returnOK;}模擬主程序：main(){SqlistL;InitList(&L);}在C中也可以用動態(tài)分配的一維數(shù)組，描述如下：defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefintDataType;typedefstruct{DataType*data;intlength;intlistsize;}Sqlist;采用動態(tài)分配時的構(gòu)造空線性表算法defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefintDataType;typedefstruct{DataType*data;intlength;intlistsize;}Sqlist;StatusInitList(Sqlist*L){/*按動態(tài)分配空間方式，構(gòu)造空線性表L*/L->listsize=LIST_INIT_SIZE;/*存儲容量*/L->data=(DataType*)malloc(LIST_INIT_SIZE*sizeof(DataType));/*申請空間*/if(L->data==NULL){printf(“OVERFLOW!”)； /*存儲空間申請失敗*/returnERROR;}L->length=0;returnOK;})*掌握順序表的插入(向后移動數(shù)據(jù))，刪除算法(向前移動數(shù)據(jù))，查找運算。1、 插入：線性表的插入運算是指在表的第i(l旨旨1+1)個位置上，插入一個新結(jié)點X。算法2.4VoidInsertList(Sqlist&L,DataTypex,inti){//在順序線性表L中第i個位置之前插入新的元素xintj;if(i<1IIi>l.length+1)printf(“Positionerror");returnERROR;if(l.length>=ListSize){printf(“overflow”);exit(overflow);}for(j=l.length-1;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x;l.length++;}備注：L為固定長度的順序線性表。2、 刪除：線性表的刪除運算是指將表的第i(1旨旨1)結(jié)點刪除，使長度為n的線性表:(a1,...ai-1,ai,ai+1...,an)變成長度為n-1的線性表(a1,...ai-1,ai+1,an)算法2.5VoiddeleteList(Sqlist&1,inti){//在順序線性表L中刪除第i個位置的元素xintj;if(i<1IIi>l.length)printf(“Positionerror");returnERROR;for(j=i;jv=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}*線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的順序表示的特點是用物理位置上的鄰接關(guān)系來表示結(jié)點間的邏輯關(guān)系，這一特點使我們可以隨機存取表中的任一結(jié)點，但它也使得插入和刪除操作會移動大量的結(jié)點?為避免大量結(jié)點的移動，我們介紹線性表的另一種存儲方式:鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為鏈表(LinkedList)。*分單鏈表，雙鏈表，循環(huán)單鏈表，循環(huán)雙鏈表*掌握各種鏈表的特點，適用范圍。*掌握基本運算，如何改變指針完成運算。*如單鏈表，雙鏈表，循環(huán)鏈表各種鏈表的結(jié)構(gòu)圖，類C的數(shù)據(jù)結(jié)構(gòu)定義，做各種運算時如何改變指針第三章#棧的定義及基本運算：*棧(Stack)是限制在表的一端進(jìn)行插入和刪除運算的線性表*插入、刪除的這一端為棧頂(Top).另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。*棧的操作特點：棧的操作后進(jìn)先出，稱為后進(jìn)先出表(LIFO)*棧的主要運算：插入和刪除*插入一個新元素(在棧頂))叫進(jìn)棧(壓入)push(&s,e)；刪除一個棧頂元素叫退棧(彈出)pop(&s,e)*棧的其他運算：有棧的初始化(設(shè)置一個空棧)判定某個棧是否為空棧(判空》讀取棧頂元素等*順序棧:利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時附設(shè)指針top指示棧頂元素在順序棧中的位置。*可用數(shù)組來實現(xiàn)順序棧。*設(shè)定一個整型變量top表示棧頂位置，稱棧頂指針。*約定：top指向?qū)嶋H棧頂下面一個空位置，即新數(shù)據(jù)將要插入的位置。順序棧的類型定義如下：#defineStackSize100;typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}SeqStack;設(shè)S是SeqStack類型的變量。則s.top=0表示空棧(?？諚l件)，s.top>=StackSize表示棧滿(棧滿條件)*若用s.top、s.base分別表示棧頂和棧底指針，則?？?，棧滿條件：?？諚l件：s.top=s.base； 棧滿條件：s.top-s.base>=s.stacksize*棧的基本運算如下：進(jìn)棧：當(dāng)某一數(shù)據(jù)x進(jìn)棧，先判斷棧是否已滿，否，置s.data[s.top]=x,s.top加1退棧：當(dāng)棧頂元素退棧時，先判斷棧是否已空，否，s.top減1,取y=s.data[s.top]#棧的應(yīng)用*數(shù)制轉(zhuǎn)換(要求掌握)括號匹配的檢驗(以下四個了解即可)行編輯程序；迷宮求解；表達(dá)式求值；棧和遞歸的實現(xiàn)：要求能夠會編寫遞歸程序。#隊列*隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。*允許刪除的一端稱為隊頭(front). 允許插入的一端稱為隊尾(rear)。*隊列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡稱FIFO表。*主要運算：插入一個新元素，稱入隊刪除一個新元素，稱出隊*其它運算：判斷隊列是否為空判斷隊列是否為已滿設(shè)置空隊列 銷毀隊列清空隊列 求隊列長度取隊頭元素*一個隊列需要兩個分別指示隊頭和隊尾的指針。設(shè)front為頭指針，始終指向隊頭；rear為尾指針，指向隊尾；當(dāng)front=rear為隊空。*由于有順序表和鏈表，相應(yīng)就有順序隊列和鏈隊列。*鏈隊列：用鏈表表示的隊列簡稱為鏈隊列。設(shè)有一表頭結(jié)點,front始終指向表頭結(jié)點；rear指向含隊尾元素的結(jié)點；*隊空條件：當(dāng)front=rear為隊空。*隊滿條件：由于存儲空間是用時申請的，一般不能滿，除非計算機中空間沒有了*鏈隊列的類型定義：typedefstructqueuenode{datatypedata;structqueuenode*next;}queuenode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;*入隊操作：申請空結(jié)點，給新結(jié)點賦值（數(shù)據(jù)域和指針域）；將原尾指針指向新結(jié)點，建立連接；移動尾指針到新結(jié)點。*出隊操作：判斷隊列是否為空；否，取隊首元素，指針后移，釋放隊首指針。*注意：在出隊算法中，一般只需修改隊頭指針。但當(dāng)原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。*順序隊列：實現(xiàn)：用一維數(shù)組實現(xiàn)data[M]*設(shè)front為隊頭指針，指向?qū)嶋H隊頭的前一個位置；rear為隊尾指針，指向?qū)嶋H隊尾元素所在位置。*初始狀態(tài)：front=rear=-1*設(shè)定front=rear時隊列為空；rear=MAXQSIZE-1隊列滿了，再不能入隊，則稱“上溢”（假上溢）*出隊操作：隊頭指針增1,判是否為空，否，取此位置的