2018年計算機考點精講講義數(shù)據(jù)結(jié)構(gòu)

1、網(wǎng)絡(luò)課堂系列計算機目錄緒論50.1 基本概念50.2 算法和算法的衡量5習題6第一章 線性表81.1 線性表的定義81.2 線性表的實現(xiàn)81.2.1 線性表的順序1.2.2 線性表的鏈式結(jié)構(gòu)8結(jié)構(gòu)10習題15第二章 棧、隊列和數(shù)組202.1 棧202.1.1 棧的定義202.1.2 棧的實現(xiàn)和運算實現(xiàn)202.1.3 棧的應(yīng)用舉例212.2 隊列242.2.1 隊列的定義及基本運算242.2.2 隊列的實現(xiàn)及運算實現(xiàn)242.3 特殊矩陣的壓縮. 262.3.1 數(shù)組262.3.2 特殊矩陣27習題29第三章 樹與二. 323.1 樹的概念323.2 二. 323.2.1 定義與性質(zhì)323.2.2

2、 二3.2.3 二的. 34的遍歷353.2.4 線索二. 383.3森林413.3.1 樹的結(jié)構(gòu)413.3.2 森林和二的轉(zhuǎn)換423.3.3森林的遍歷423.4（Huffman）編碼43習題44第四章 圖462網(wǎng)絡(luò)課堂系列計算機4.1 圖的概念464.2 圖的及基本操作474.2.1 鄰接矩陣474.2.2 鄰接表484.3 圖的遍歷494.3.1 深度優(yōu)先搜索494.3.2 廣度優(yōu)先搜索504.4 圖的基本應(yīng)用514.4.1 最小生成樹514.4.2 最短路徑524.4.3 拓撲排序544.4.4 關(guān)鍵路徑55習題56第五章 查找585.1 查找的基本概念585.2 順序查找法585.3

3、折半查找法595.4 動態(tài)查找. 605.4.1 二叉排序樹605.4.2 平衡二. 625.4.3B 樹及其基本操作、B+樹的基本概念655.5 散列表665.5.1 散列表與散列方法665.5.2 常用的散列函數(shù)665.5.3 處理的方法675.5.4 散列表的查找685.5.5 散列表的查找分析68習題69第六章 排序716.1 排序的基本概念716.2排序716.2.1 直接6.2.2 折半排序71排序726.3 冒泡排序726.4 簡單選擇排序736.5排序736.6 快速排序746.7 堆排序766.8 二路歸并排序773網(wǎng)絡(luò)課堂系列計算機6.9 基數(shù)排序786.10 各種內(nèi)部排序

4、算法的比較79習題804網(wǎng)絡(luò)課堂系列計算機數(shù)據(jù)結(jié)構(gòu)緒論0.1 基本概念1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structure （D，R），其中，D 是數(shù)據(jù)元素的有限集，R 是D的有限集。2、邏輯結(jié)構(gòu)：是指數(shù)據(jù)之間的相互關(guān)系。通常分為四類結(jié)構(gòu)：（1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。（2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元間存在一對一的關(guān)系。間存在一對多的關(guān)系。間存在多對多的關(guān)系。（3）結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元（4）圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元3、結(jié)構(gòu)：是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，又稱為數(shù)據(jù)的物理結(jié)構(gòu)。通常由四種基本的方法

5、實現(xiàn)：（1）順序方式。數(shù)據(jù)元素順序存放，每個結(jié)點只含一個元素。、刪除）效率較差。位置反映數(shù)據(jù)元素間的邏輯關(guān)系。密度大。但有些操作（如（2）鏈式方式。每個結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求空間連續(xù)，便于動態(tài)操作（如、刪除等），但（3）索引空間開銷大（用于指針），另外不能折半查找等。方式。除數(shù)據(jù)元素在一組地址連續(xù)的內(nèi)存空間外，還需建立一個索引表，索引表中索引指示結(jié)點的位置（下標）或區(qū)間端點（下標）。（4）散列方式。通過散列函數(shù)和解決的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的地址。其特點是存取速度

6、快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。0.2 算法和算法的衡量1、算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。算法具有下列特性：有窮性確定性可行性輸入輸出。算法和程序十分相似，但又有區(qū)別。程序不一定具有有窮性，的指令必須是可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。2、算法的時間復(fù)雜度：以基本運算的原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中基本運算次數(shù) T(n)是問題規(guī)模 n（輸入量的多少，稱之為問題規(guī)模）的某個函數(shù)

7、f(n)，記作：5網(wǎng)絡(luò)課堂系列計算機T(n) (f(n)也可表示 T(n) m(f(n)，其中 m 為常量。記號“O”讀作“大 O”，它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時間 T(n)的增長率和 f(n)的增長率相同。注意：有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。常見的漸進時間復(fù)雜度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!) O(nn)。3、算法的空間復(fù)雜度：是對一個算法在運行過程中臨時占用的分析除輸入和程序之外的輔助變量所占額外空間。空間大小的量度。只需要原地工作：若所需額外空間相對于輸入數(shù)據(jù)量來說是間復(fù)雜度為 O(1

8、)。習題，則稱此算法為原地工作，空1、以下算法的時間復(fù)雜度是（ void f (int n)int x=1; while (x<n)x=2*x;）。A.O(log2n)B. O(n)C. O(nlog2n)D. O(n2)分析：基本運算是語句 x=2*x，設(shè)其執(zhí)行時間為 T(n)，則有 2T(n)n， 即T(n)<log2 n=O(log2 n)。解答：A。2、 以下算法的時間復(fù)雜度是（void f (int n)int p=1,d=n,f=n; while (d>0)）。if (d%2= =1)f=f*f; d=d/2;p=p*f;A.O(log2n)B. O(n)C. O

9、(nlog2n)D. O(1)分析：算法中 while 循環(huán)的 if 條件中包含的 p=p*f 語句可以不考慮，因為它執(zhí)行的次數(shù)不超過 d=d/2 語句的執(zhí)行次數(shù)。基本運算是語句 d=d/2（或 f=f*f），設(shè)其執(zhí)行時間為 T(n)，則有 d=n/2T(n) >01，2T(n)n，即T(n)log2 n=O(log2 n)。解答：A。3.求出下列算法的時間復(fù)雜度。1) 比較同一簡單類型的兩個數(shù)據(jù) x1 和 x2 的大小，對于 x1>x2,x1=x2 和x1<x2 這三種不同情況分別返回>、=和<字符。char compare(SimpleType x1,Simp

10、leType x2) 6網(wǎng)絡(luò)課堂系列計算機if (x1>x2) return>else if (x1=x2) return =; else return<其時間復(fù)雜度為 O (1)。2) 將一個字符串中的所有字符按相反方向的次序重新放置。void Reverse(char *p) int n=strlen(p);for (int i=0; i<n/2; i+) char ch;ch=pi； pi=pn-i-1;pn-i-1=ch;其時間復(fù)雜度為 O (n)。3) 從二維整型數(shù)組 amn中查找出最大元素所在的行、列下標。void Find(int aMN,int m,in

11、t n,int M>=n 和 N>=n 的條件，Lin 和 Col 為Lin=0;Col=0;for (int i=0;i<m;i+)for (int j=0;j<n;j+)&Lin,int &Col) /M 和N 為全局常量，應(yīng)滿足形參，它是對應(yīng)實參的別名，其值由實參帶回if (aij>aLinCol) Lin=i;Col=j;其時間復(fù)雜度為 O (m*n)。4) void func(int n)int y = 0;while (y * y <=n)y +;其時間復(fù)雜度為 O (n1/2)。7網(wǎng)絡(luò)課堂系列計算機第一章 線性表1.1 線性表的

12、定義線性表是一種線性結(jié)構(gòu)，在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素的線性結(jié)構(gòu)，定義如下：線性表是具有相同數(shù)據(jù)類型的n(n0)個數(shù)據(jù)元素的有限序列，通常記為：(a1，a2， ai-1，ai，ai+1，an)其中n為表長， n0為空表。需要說明的是：ai為序號為 i 的數(shù)據(jù)元素（i=1,2,n），通常將它的數(shù)據(jù)類型抽象為ElemType，ElemType根據(jù)具體問題而定。1.2 線性表的實現(xiàn)1.2.1 線性表的順序1.順序表線性表的順序是指在內(nèi)存中用地址連續(xù)的一塊結(jié)構(gòu)空間順序存放線性表的各元素，用這種形式的線性表稱其為順序表。因為內(nèi)存中的地址空間是線性的，因此，用物

13、理上的相鄰實現(xiàn)數(shù)據(jù)元間的邏輯相鄰關(guān)系是既簡單又自然的。設(shè)a的地址為Loc(a)，每個數(shù)據(jù)元素占d個地址，則第i個數(shù)據(jù)元素的地址為：Loc(ai)=Loc(a)+(i-1)*d1in這就是說只要知道順序表首地址和每個數(shù)據(jù)元素所占地址單元的個數(shù)就可求出第i個數(shù)據(jù)元素的地址來，這也是順序表具有按數(shù)據(jù)元素的序號隨機存取的特點。線性表的動態(tài)分配順序結(jié)構(gòu)：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedefstruct ElemType*elem; intlength;intlistsize;SqList;2.順序表上基本運算的實現(xiàn)（1）順序表

14、的初始化/空間的初始分配量空間的分配增量/線性表的/當前長度空間基址/當前已分配的空間型的運算，因此，將L設(shè)為順序表的初始化即構(gòu)造一個空表，這對表是一個參數(shù)，首先動態(tài)分配空間，然后，將length置為0，表示表中沒有數(shù)據(jù)元素。int Init_SqList (SqList &L)L.elem = (ElemType* )malloc(LIST_INIT_SIZE * sizeof(ElemType);if (!L.elem) exit (OVERFLOW);L.length=0;/分配失敗8網(wǎng)絡(luò)課堂系列計算機L. listsize = LIST_INIT_SIZE;return OK;

15、/初始容量（2）運算線性表的是指在表的第i(i的取值范圍：1in+1)個位置上一個值為 x 的新元素，后使長為 n的表:(a1，a2，. ，ai-1，ai，ai+1，. ，an) 成為表長為 n+1 表:(a1，a2，.，ai-1，x，ai，ai+1，.，an ) 。順序表上完成這一運算則通過以下步驟進行： 將aian 順序向下移動，為新元素讓出位置；（注意數(shù)據(jù)的移動方向：從后往前依次后移一個元素） 將 x 置入空出的第i個位置； 修改表長。int Insert_SqList (SqList &L，int i，ElemType x)if (i < 1 | i > L.len

16、gth+1) return ERROR;/位置不合法if (L.length >= L.listsize) return OVERFLOW; / 當前/需注意的是，若是采用動態(tài)分配的順序表，當空間已滿,不能空間已位置也可增加分配q = &(L.elemi-1);for (p = &(L.elemL.length-1); p >= q; -p)*(p+1) = *p;*q = e;+L.length; return OK;/ q指示/位置及之后的元素右移e1順序表上的運算，時間主要消耗在了數(shù)據(jù)的移動上，在第i個位置上x ，從 ai 到an 都要向下移動一個位置，共需要

17、移動 ni1個元素。（3）刪除運算線性表的刪除運算是指將表中第 i （i 的取值范圍為 ：1 in）個元素從線性表中去掉，刪除后使長為 n 的線性表：(a1，a2，. ，ai-1，ai，ai+1，.，an)成為表長為 n1 的線性表：(a1，a2，. ，ai-1， ai+1，. ，an)。順序表上完成這一運算的步驟如下： 將ai+1an 順序向上移動；（注意數(shù)據(jù)的移動方向：從前往后依次前移一個元素） 修改表長。int Delete_SqList (SqList &L;int i) if (i < 1) | (i > L.length)return ERROR;/ 刪除位置不

18、合法p = &(L.elemi-1);/ p 為被刪除元素的位置9網(wǎng)絡(luò)課堂系列計算機e = *p;q = L.elem+L.length-1; for (+p; p <= q; +p)*(p-1) = *p;-L.length; return OK;/ 被刪除元素的值賦給 e/ 表尾元素的位置/ 被刪除元/ 表長減1后的元素左移順序表的刪除運算與運算相同，其時間主要消耗在了移動表中元素上，刪除第i個元都要向上移動一個位置，共移動了 n-i 個元素，素時，其后面的元素ai+1an順序表的、刪除需移動大量元素 O(n)；但在尾端、刪除效率高 O(1)。1.2.2 線性表的鏈式結(jié)構(gòu)1.

19、2.2.1 單鏈表1.鏈表表示鏈表是通過一組任意的單元來線性表中的數(shù)據(jù)元素的。為建立起數(shù)據(jù)元間的線性關(guān)系，對每個數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息 ai 之外，還需要和ai一起存放其后繼示。ai+1所在的單元的地址，這兩部分信息組成一個“結(jié)點”，結(jié)點的結(jié)構(gòu)如圖所單鏈表結(jié)點結(jié)構(gòu)其中，存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼地址的稱為指針域。因此n個元素的線性表通過每個結(jié)點的指針域了一個“鏈”，稱之為鏈表。因為每個結(jié)點中只有一個指向后繼的指針，所以稱其為單鏈表。線性表的單鏈表結(jié)構(gòu)C語言描述下：typedef struct LNodeElemTypedata;/ 數(shù)據(jù)域/ 指針域struct

20、 LNodeLNode，*LinkList; LinkList L；*next;/ L 為單鏈表的頭指針通常用“頭指針”來標識一個單鏈表，如單鏈表L、單鏈表H等，是指某鏈表的第一個結(jié)點的地址放在了指針變量 L、H 中， 頭指針為“NULL”則表示一個空表。2.單鏈表上基本運算的實現(xiàn)(1)建立單鏈表10datanext網(wǎng)絡(luò)課堂系列計算機 頭插法在鏈表的頭部結(jié)點建立單鏈表鏈表與順序表不同，它是一種動態(tài)管理的結(jié)構(gòu)，鏈表中的每個結(jié)點占用的空間不是預(yù)先分配，而是運根據(jù)需求而生成的，因此建立單鏈表從空表開始，每讀入一個數(shù)據(jù)元素則申請一個結(jié)點，然后插在鏈表的頭部。LinkListCreateListF (

21、)LinkList L=NULL； /空表LNode *s;int x; scanf(%d,&x);while (x!=flag) /設(shè)數(shù)據(jù)元素的類型為ints=(LNode *)malloc(sizeof(LNode); s->data=x;s->next=L;L=s;scanf (%d,&x);return L; 尾插法在單鏈表的尾部結(jié)點建立單鏈表頭建立單鏈表簡單，但讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾的方法。因為每次是將新結(jié)點到鏈表的尾部，所以需加入一個指針 r 用來始終指向鏈表中的尾結(jié)點，以便能夠?qū)⑿陆Y(jié)點到鏈表的尾部。

22、初始狀態(tài)，頭指針L=NULL，尾指針 r=NULL; 按線性表中元素的順序依次讀入數(shù)據(jù)元素，到 r 所指結(jié)點的后面，然后 r 指向新結(jié)點（注意不是結(jié)束標志時，申請結(jié)點，將新結(jié)點第一個結(jié)點有所不同）。LinkListCreateListR1 ( ) LinkList L=NULL;LNode*s,*r=NULL;int x; scanf(%d,&x);while (x!=flag) /設(shè)數(shù)據(jù)元素的類型為ints=(LNode *)malloc(sizeof(LNode);s->data=x;if(L=NULL)elser->next=s; r=s;L=s;/第一個結(jié)點的處理/

23、其它結(jié)點的處理/r 指向新的尾結(jié)點scanf(%d,&x);if ( r!=NULL)r->next=NULL;/對于非空表，最后結(jié)點的指針域放空指針return L;11網(wǎng)絡(luò)課堂系列計算機在算法CreateListR1中，第一個結(jié)點的處理和其它結(jié)點是不同的，是第一個結(jié)點加入時鏈表為空，它沒有直接前驅(qū)結(jié)點，它的地址就是整個鏈表的指針，需要放在鏈表的頭指針變量中；而其它結(jié)點有直接前驅(qū)結(jié)點，其地址放入直接前驅(qū)結(jié)點的指針域。“第一個結(jié)點”的問題在很多操作中都會遇到，如在鏈表中結(jié)點時，將結(jié)點插在第一個位置和其它位置是不同的，在鏈表中刪除結(jié)點時，刪除第一個結(jié)點和其它結(jié)點的處理也是不同的，等

24、等。為了方便操作，有時在鏈表的頭部加入一個“頭結(jié)點”，頭結(jié)點的類型與數(shù)據(jù)結(jié)點一致， 標識鏈表的頭指針變量L中存放該結(jié)點的地址，這樣即使是空表，頭指針變量L也不為空了。頭結(jié)點的加入使得“第一個結(jié)點”的問題不再存在，也使得“空表”和“非空表”的處理成為一致。頭結(jié)點的加入完全是為了運算的方便，它的數(shù)據(jù)域無定義，指針域中存放的是第一個數(shù)據(jù)結(jié)點的地址，空表時為空。尾插法建立結(jié)點的單鏈表，將算法CreateListR1改寫成算法CreateListR2形式。LinkListCreateListR2( )LinkList L=(LNode *)malloc(sizeof(LNode);L->next=

25、NULL； LNode*s,*r=L; int x; scanf(%d,&x);while (x!=flag) /空表/設(shè)數(shù)據(jù)元素的類型為ints=(LNode *)malloc(sizeof(LNode); s->data=x;r->next=s;r=s;scanf(%d,&x);/r 指向新的尾結(jié)點r->next=NULL; return L;因此，頭結(jié)點的加入會帶來以下兩個優(yōu)點：第一個優(yōu)點：由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無需進行特殊處理；第二個優(yōu)點：無論鏈表是否為空，其頭指針是指

26、向頭結(jié)點在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。在以后的算法中不加說明則認為單鏈表是(2) 查找操作 按序號查找 Get_LinkList(L,i)結(jié)點的。從鏈表的第一個元素結(jié)點起，當前結(jié)點是否是第i個，若是，則返回該結(jié)點的指針，否則繼續(xù)后一個，表結(jié)束為止，沒有第個結(jié)點時返回空。LNode* Get_LinkList(LinkListL, inti); 12網(wǎng)絡(luò)課堂系列計算機LNode* p=L; intj=0;while (p->next !=NULL && j<i ) p=p->next;j+;if (j=i) retu

27、rn p; else return NULL;(3)運算 后插結(jié)點：設(shè)p指向單鏈表中某結(jié)點，s指向待的值為x的新結(jié)點，將*s到*p的后面，示意圖。p×s在*p之后*s操作如下：s->next=p->next;p->next=s;注意：兩個指針的操作順序不能交換。(4)刪除運算 刪除結(jié)點設(shè)p指向單鏈表中某結(jié)點，刪除*p。操作過程如圖。要實現(xiàn)對結(jié)點*p的刪除，首先要找到*p的前驅(qū)結(jié)點*q，然后完成指針的操作即可。pq×操作如下：q=L;while (q->next!=p)->next;q->next=p->next; free(p);/

28、找*p的直接前驅(qū)因為找*p前驅(qū)的時間復(fù)雜度為O(n)，所以該操作的時間復(fù)雜度為O(n)通過上面的基本操作我們得知：(1) 單鏈表上、刪除一個結(jié)點，必須知道其前驅(qū)結(jié)點。13網(wǎng)絡(luò)課堂系列計算機(2) 單鏈表不具有按序號隨機的特點，只能從頭指針開始一個個順序進行。1.2.2.2 循環(huán)鏈表對于單鏈表而言，最后一個結(jié)點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點相連，就了單循環(huán)鏈表。在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來為是否是頭指針而已，沒有其它較大的變化。指針是否為 NULL 變對于單鏈表只能從頭結(jié)點開始遍歷整個鏈表，而對于單循環(huán)鏈表則可以從表中任意結(jié)點開始遍

29、歷整個鏈表，不僅如此，有時對鏈表常做的操作是在表尾、表頭進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結(jié)點的指針 R 來標識，可以使得操作效率得以提高。1.2.2.3 雙向鏈表單鏈表的結(jié)點中只有一個指向其后繼結(jié)點的指針域 next，因此若已知某結(jié)點的指針為 p， 其后繼結(jié)點的指針則為 p->next ，而找其前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點的next 域進行，也就是說找后繼的時間性能是 O(1)，找前驅(qū)的時間性能是 O(n)，如果也希望找前驅(qū)的時間性能達到 O(1)，則只能付出空間的代價：每個結(jié)點再加一個指向前驅(qū)的指針域，結(jié)點的結(jié)構(gòu)為，用這種結(jié)點組成的鏈表稱為雙

30、向鏈表。線性表的雙向鏈表結(jié)構(gòu)C語言描述下：typedef structDuLNode ElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;和單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以結(jié)點。（1）雙向鏈表中結(jié)點的：設(shè) p 指向雙向鏈表中某結(jié)點，s 指向待的值為 x 的新結(jié)點，將*s到*p 的前面，示意圖如所示。p××s圖 雙向鏈表中的結(jié)點14priordatanext網(wǎng)絡(luò)課堂系列計算機操作如下：s->prior=p->prior; p->prior->next=s; s-&g

31、t;next=p;p->prior=s;指針操作的順序不是唯一的，但也不是任意的，操作必須要放到操作的前面完成，否則*p 的前驅(qū)結(jié)點的指針就丟掉了。（2）雙向鏈表中結(jié)點的刪除：設(shè) p 指向雙向鏈表中某結(jié)點，刪除*p。操作示意圖。p××雙向鏈表中刪除結(jié)點圖操作如下：p->prior->next=p->next;p->next->prior=p->prior; free(p);1.2.2.4 順序表和鏈表的比較總之，兩種結(jié)構(gòu)各有長短，選擇那一種由實際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序，而頻繁做刪除的即動態(tài)性較強的線性表

32、宜選擇鏈式。習題1、循環(huán)鏈表的主要優(yōu)點是（ ）A不再需要頭指針了。 B已知某個結(jié)點的位置后，能很容易找到它的直接前驅(qū)結(jié)點。C在進行刪除操作后，能保證鏈表不斷開。D從表中任一結(jié)點出發(fā)遍歷整個鏈表。2.若線性表最常用的運算是查找第i個元素及其前驅(qū)的值，則采用（ ）方式節(jié)省時間。A單鏈表C單循環(huán)鏈表B雙鏈表D順序表15順序表單鏈表以地址相鄰表示關(guān)系用指針表示關(guān)系隨機，取元素 O(1)順序，取元素 O(n)、刪除需要移動元素 O(n)、刪除不用移動元素 O(n)(用于查找位置)網(wǎng)絡(luò)課堂系列計算機3.若某線性表中最常用的操作是在最后一個元后一個元素和刪除第一個元素，則采用（ ）A單鏈表C雙鏈表方式最節(jié)省

33、運算時間。B. 僅有頭指針的單循環(huán)鏈表D. 僅有尾指針的單循環(huán)鏈表4.在具有n個結(jié)點的單鏈表中，實現(xiàn)（ ）的操作，其算法的時間復(fù)雜度都是O(n)。A遍歷鏈表和求鏈表的第i個結(jié)點B在地址為p的結(jié)點之后C刪除開始結(jié)點一個結(jié)點D刪除地址為p的結(jié)點的后繼結(jié)點5.在n個結(jié)點的順序表，算法的時間復(fù)雜度是O(1)的操作是（ ）。A.第i個結(jié)點(1in)和求第i個結(jié)點的直接前驅(qū)(2in)B在第i個結(jié)點后一個新結(jié)點(1in)C刪除第i個結(jié)點(1in) D將n個結(jié)點從大到小排序6.在非空循環(huán)雙鏈表中q所指的結(jié)點前p->next=q；p->prior=q->prior；q->prior=p；

34、（ ）；Aq->next=p；Bq->prior->next=p； Cp->prior->next=p； Dp->next->prior=p；一個由p所指結(jié)點的過程依次為：7、已知 A=(a1, a2, , am)，B=(b1, b2, , bn)均為順序表，試編寫一個比較A¸B大小的算法。int compare(SqList La, SqList Lb) i=0;while (i<La.Length && i<Lb.Length) if (La.elemi=Lb.elemi)i+; else if (La.ele

35、mi<Lb.elemi)return -1;else return 1;if ( i>La.length && i>Lb.Length)return 0;elseif (i>Lb.Length)elsereturn -1;return 1;8.刪除有序表中所有其值大于 mink 且小于maxk的數(shù)據(jù)元素。void delete(LinkList &L, int mink, int maxk) p=L->next;while (p && p->data<=mink) pre=p;p=p->next; /查找第

36、一個值>mink的結(jié)點16網(wǎng)絡(luò)課堂系列計算機if (p) while (p && p->data<maxk)p=p->next;/ 查找第一個值 maxk 的結(jié)點q=pre->next;pre->next=p;/ 修改指針while (q!=p) s=q->next;delete q;q=s; / / if / delete9.逆置線性鏈表void inverse(LinkList &L) / 逆置 結(jié)點的單鏈表 L p=L->next; L->next=NULL; while ( p) 結(jié)點空間su->nex

37、t;/ succ指向*p的后繼p->next=L->next; L->next=p;p = succ;/ *p在頭結(jié)點之后10.將兩個非遞減有序的有序表歸并為非遞增的有序鏈表（利用void union( LinkList& Lc, LinkList& La,LinkList& Lb) 結(jié)點）。/將非遞減的有序表 La 和Lb歸并為非遞增的有序表Lc,歸并之后，La和Lb表不再存在。上述三個表均為結(jié)點的單鏈表，Lc表中的結(jié)點即為原 La 或 Lb 表中的結(jié)點。Lc = new LNode;Lc->next = NULL; pa = La->n

38、ext;pb = Lb->next;while ( pa | pb ) if( !pa ) q = pb;pb = pb->next; else if( !pb ) q = pa;pa = pa->next; elseif (pa->data <= pb->data ) q = pa;pa = pa->next; else q = pb;pb = pb->next; / 初始化q->next = Lc->next;Lc->next = q;/delete La;delete Lb; / union/La 和 Lb的頭結(jié)點11.已

39、知A, B和C為三個有序鏈表，編寫算法從A表中刪除B表和C表中共有的數(shù)據(jù)元素。void Difference_L( LinkList &La, LinkList Lb,LinkList Lc ) / La, Lb 和 Lc 分別為三個非遞減有序的單鏈表的頭指針，從 La 表中刪除所有的既在 Lb表中出現(xiàn)，又在 Lc 表中出現(xiàn)的元素結(jié)點17網(wǎng)絡(luò)課堂系列計算機pre= pa;pa=La->next;pb=Lb->next;pc=Lc->next; while (pa && pb && pc) if (pa->data<pb-&g

40、t;data) pre=pa;pa=pa->next; else if (pb->data<pc->data)pb=pb->next;else if (pc->data<pa->data) pc=pc->next;else pre->next=pa->next;delete pa; pa=pre->next; / 刪除，注意沒有移動 pb 和 pc 才能實現(xiàn)刪除所有滿足條件的結(jié)點/ while/Difference12.在雙向循環(huán)鏈表的結(jié)點中，增加一個頻度的數(shù)據(jù)域 freq，編寫算法實現(xiàn)LOCATE(L,x)。p=L-&g

41、t;next; / L為雙向鏈表的頭指針while (p!=L && p->data!=x)p=p->next; / 搜索元素值為 x 的結(jié)點*p if (p=L)return NULL;q=p->prior;while (q!=L && q->freq<p->freq)將結(jié)點 *p 從當前位置上刪除;->prior; /搜索頻度不小于它的結(jié)點*q之后將結(jié)點 *preturn p;在結(jié)點 *q 之后;13.已知L為沒有頭結(jié)點的單鏈表中第一個結(jié)點的指針，每個結(jié)點數(shù)據(jù)域存放一個字符，該字符可能是英文字母字符或數(shù)字字符或其它字

42、符，編寫算法構(gòu)造三個以結(jié)點的單循環(huán)鏈表表示的線性表，使每個表中只含同一類字符。（要求用最少的時間和最少的空間）voidOneToThree（LinkedList &L， LinkedList & la， LinkedList & ld， LinkedList & lo） la=（LinkedList）malloc（sizeof（LNode）； ld=（LinkedList）malloc（sizeof（LNode）； lo=（LinkedList）malloc（sizeof（LNode）； la->next=la；ld->next=ld；lo->

43、next=lo；建立三個鏈表的頭結(jié)點，并置三個循環(huán)鏈表為空表while（L!=null）r=L; L=L->next;分解原鏈表。L指向待處理結(jié)點的后繼if（r->data>=a&& r->data<=z| r->data>=A&& r->data<=Z）r->next=la->next； la->next=r； else if（r->data>=0&& r->data<=9）r->next=ld->next；ld->next=r；處

44、理字母字符。處理數(shù)字字符else r->next=lo->next；lo->next=r； 處理其它符號。18網(wǎng)絡(luò)課堂系列計算機19網(wǎng)絡(luò)課堂系列計算機第二章 棧、隊列和數(shù)組2.1 棧2.1.1 棧的定義棧是限制在表的一端進行和刪除的線性表。、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當表中沒有元素為空棧。2.1.2 棧的實現(xiàn)和運算實現(xiàn)棧是運算受限的線性表，線性表的結(jié)構(gòu)對棧也是適用的，只是操作不同而已。利用順序方式實現(xiàn)的棧稱為順序棧。與線性表類似，棧的動態(tài)分配順序結(jié)構(gòu)如下：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10

45、typedefstruct/空間的初始分配量空間的分配增量SElemType*base; SElemType*top; intstacksize;SqStack;/在棧構(gòu)造之前和銷毀之后，base 的值為 NULL/棧頂指針/當前已分配的空間需要注意，在棧的動態(tài)分配順序始終在棧頂元素的下一個位置。結(jié)構(gòu)中，base 始終指向棧底元素，非空棧中的 top下面是順序棧上常用的基本操作的實現(xiàn)。（1）入棧：若棧不滿，則將 eint Push (SqStack &S, SElemType e) if (S.top-S.base>=S.stacksize)*S.top+ = e; return

46、 OK;棧頂。/棧滿，追加空間/top 始終在棧頂元素的下一個位置（2）出棧：若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，并返回 OK，否則返回ERROR。int Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR; e = *-S.top;return OK;出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常?？?0網(wǎng)絡(luò)課堂系列計算機常作為一種轉(zhuǎn)移的條件。2.1.3 棧的應(yīng)用舉例由于棧的“先進先出”特點，在很多實際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進行求解，下面通過幾個例子

47、進行說明。1數(shù)制轉(zhuǎn)換十進制數(shù) N 和其他 d 進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：N = (N div d)×d + N mod d(其中：div 為整除運算，mod 為求余運算） 例如：（1348)10 = (2504)8 ，其運算過程如下：NN div 8N mod 82120052212假設(shè)現(xiàn)要編制一個滿足下列要求的程序：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述計算過程是從低位到順序產(chǎn)生八進制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從到低位進行，恰好和計算過程相反。因此，若將計算過程中得到的八進制數(shù)的各

48、位順序進棧，則按出棧序列打印輸出的即為與輸入對應(yīng)的八進制數(shù)。算法思想：當 N>0 時重復(fù)（1），（2）（1） 若 N0，則將 N % r 壓入棧 s 中 ，執(zhí)行（2）;若 N=0，將棧 s 的內(nèi)容依次出棧， 算法結(jié)束。（2） 用 N / r 代替 N。void conversion () InitStack(S); scanf ("%d",N); while (N) Push(S, N % 8); N = N/8;/ 構(gòu)造空棧while (!StackEmpty(S) Pop(S,e);printf ( "%d", e );2.表求值表求值是程序設(shè)

49、計語言編譯中一個最基本的問題，它的實現(xiàn)也是需要棧的加入。下面的算法是由運算符優(yōu)先法對表求值。在此僅限于討論只含二目運算符的算術(shù)表。（1）中綴表求值：21網(wǎng)絡(luò)課堂系列計算機中綴表：每個二目運算符在兩個運算量的中間，假設(shè)所討論的算術(shù)運算符包括：+ 、- 、*、/、%、（乘方）和括號（）。設(shè)運算規(guī)則為：運算符的優(yōu)先級為：（）>>、/、%>+、-；有括號出現(xiàn)時先算括號內(nèi)的，后算括號外的，多層括號，由內(nèi)向乘方連續(xù)出現(xiàn)時先算最右面的。行；表作為一個滿足表語則的串，如表“3*2（4+2*2-*3）-5”,它的掃描表，當掃描到 3*2 時不能馬上計算，因為后面可能還有更的求值過程為：自高的運

50、算，正確的處理過程是：需要兩個棧：對象棧 s1 和運算符棧 s2。當自左至右掃描表達式的每一個字符時，若當前字符是運算對象，入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧，繼續(xù)向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運算量，從運算符棧出棧一個運算符進行運算，并將其運算結(jié)果入對象棧，繼續(xù)處理當前字符，直到“3*2（4+2*2-*3）-5”求值過程中兩個棧的狀態(tài)情況見圖遇到結(jié)束符。中綴表所示。表讀字符對象棧 s1算符棧 s2說明2233#3 入棧 s1*3#*入棧 s223，2#*2 入棧 s13，2#*入棧 s2(3，2#*(入棧 s243，2，4#*(4 入棧 s1+3，2，4#*(+入棧 s223，2