數(shù)據(jù)結(jié)構(gòu)討論小課堂和習(xí)題解答(共53頁)

1、討論小課堂 1數(shù)據(jù)結(jié)構(gòu)課程主要討論哪三個(gè)方面？1.2.存儲結(jié)構(gòu)3.數(shù)據(jù)操作1.算法和程序的區(qū)別是什么呢？【參考答案】：算法的含義與程序十分相似，但又有區(qū)別。一個(gè)程序不一定滿足有窮性。例如，操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會停止，即使沒有作業(yè)需要處理，它仍處于動(dòng)態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。另一方面，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語言來描述，則它就是一個(gè)程序。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相承的。解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。

2、反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來體現(xiàn)。要設(shè)計(jì)一個(gè)好的算法通常要考慮以下的要求。正確。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求?？勺x。一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。健壯。當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后果。高效。有效使用存儲空間和有較高的時(shí)間效率。2，你認(rèn)為應(yīng)該如何評估一個(gè)數(shù)據(jù)結(jié)構(gòu)或算法的有效性。【參考答案】：前提之一是算法的正確性；其二還必須考慮執(zhí)行算法所耗費(fèi)的時(shí)間和執(zhí)行算法所耗費(fèi)的空間（主要是只指輔助空間），以及算法是否易讀、易編碼和易于調(diào)試。3，討論數(shù)據(jù)結(jié)構(gòu)的重要性?！緟⒖即鸢浮浚喝缃裼?jì)算機(jī)的應(yīng)用已深入到社會生活 的各個(gè)領(lǐng)域，計(jì)算機(jī)處

3、理的對象由單純的數(shù)值 發(fā)展到字符、圖象、聲音等，表示這些對象的數(shù)據(jù)成分往往不是單一的，而是多成分且形成一定的結(jié)構(gòu)。因此,在程序設(shè)計(jì)中，除了應(yīng)精心設(shè)計(jì)算法外 ，還應(yīng)精心組織數(shù)據(jù)（包括原始數(shù)據(jù)、中間結(jié)果 、最終結(jié)果），使之形成一定的組織形式（數(shù)據(jù)結(jié)構(gòu) ），以便讓計(jì)算機(jī)盡可能高效率地處理。在實(shí)際程序設(shè)計(jì)的實(shí)踐中 ，數(shù)據(jù)結(jié)構(gòu)和算法是不同的但又是互相聯(lián)系的兩個(gè)方面。我們甚至還可以說 ，問題的算法往往取決于選定的數(shù)據(jù)結(jié)構(gòu) 。 所以N.Wirth 教授認(rèn)為 程序設(shè)計(jì)=算法+數(shù)據(jù)結(jié)構(gòu)。我們已經(jīng)初步地學(xué)習(xí)了高級語言（例如pascal）的程序設(shè),掌握了一些程序設(shè)計(jì)方法與技巧 。然而，這些方法與技巧對于現(xiàn)實(shí)的程序設(shè)

4、計(jì)工作來說 ，是遠(yuǎn)遠(yuǎn)不夠的。以下舉幾個(gè)例子加以說明 。例1 求真分?jǐn)?shù)117/29 的值，求到小數(shù)點(diǎn)后50位例2 求真分?jǐn)?shù) 7/27 的值，精確到小數(shù)點(diǎn)后50 位。1. 輸出 117 /29的值。2. a < 余數(shù)。b<293. aa * 10 。4. 輸出 a/b 的商。5. a<余數(shù)。6. 如未達(dá)要求，轉(zhuǎn) 3 ，否則結(jié)束。例3 從鍵盤輸入若干個(gè)數(shù) ，并將其排序輸出。相同的數(shù)，只輸出一個(gè)。本例似乎不難 ，可以采取的策略之一：用一個(gè)數(shù)組來存放輸入的數(shù)，然后排序輸出。策略之二：邊輸入邊排序。我們注意到：輸出只能是不同的數(shù) ，因而這是一個(gè)搜索加排序的問題。所以，不論采取那一種策略

5、，用數(shù)組這一種結(jié)構(gòu)不是最佳的結(jié)構(gòu)，因?yàn)樾屎艿汀Ｊ聦?shí)上，若用二叉樹作為存儲結(jié)構(gòu)，效率則會大大提高。例4 工作安排的可行性問題 。為了直觀了解工作環(huán)節(jié)之間的制約關(guān)系，通常用"有向圖"來表示這種安排。 習(xí)題11. 抽象數(shù)據(jù)類型的定義由哪幾部分組成？ 1.1【參考答案】：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作三部分。 2. 按數(shù)據(jù)元素之間的邏輯關(guān)系不同，數(shù)據(jù)結(jié)構(gòu)有哪幾類？ 1.2【參考答案】：線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合四類。 3. 你能舉出幾個(gè)你熟悉的"序列"的例子來嗎？ 1.3【參考答案】：如："0，1，2，9","A，B，C，Z

6、"。 4. 簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。5.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？1.5【參考答案】：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。6. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。1.6【參考答案】：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的。7. 有下列兩段描述：（1）void pro1( ) (2)void pro2( ) n=2; y=0; While(n%2=0) x=5/y; n=n+2;

7、 printf(“%d,%dn,x,y); printf(“%dn”,n); 這兩段描述均不能滿足算法的特征，試問它們違反了算法的那些特征？1.7【參考答案】：（1）是一個(gè)死循環(huán)，違反了算法的有窮性特征。（2）出現(xiàn)除零錯(cuò)誤，違反了算法的可行性特征。8. 分析并寫出下面的各語句組所代表的算法的時(shí)間復(fù)雜度。 (1) for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;【參考答案】：O（m*n）(2) k=0; for( i=1; i<=n; i+) for (j=i ; j<=n; j+) k+; 【參考答案】：O（n2） (3) i=1;

8、while(i<=n) i=i*3;【參考答案】：3 T(n)n即：T(n) log3n =O（log3n）所以：T(n)= O（log3n） (4) k=0; for( i=1; i<=n; i+) for (j=i ; j<=n; j+) for (k=j ; k<=n; k+) x += delta; 【參考答案】：O（n3）(5) for(i=0,j=n-1;i<j;i+,j- -)t=ai; ai= aj; ai=t;【參考答案】：基本語句共執(zhí)行了n/2次，T(n)=O（n）(6) x=0;for(i=1; i<n; i+) for (j=1; j

9、<=n-i; j+)x+;【參考答案】：因?yàn)閤+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）討論小課堂21. 在一個(gè)非遞減有序線性表中，插入一個(gè)值為X的元素，使插入后的線性表仍為非遞減有序。（注意：對比順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。）【參考答案】方法一：順序存儲結(jié)構(gòu)void insert(ElemType x) i=length-1; while(i>=0&&elemi>x) elemi+1=elemi; i-; elemi+1=x;length+;方法二：鏈?zhǔn)酱鎯Y(jié)構(gòu)void insert(ElemType x) NodeTyp

10、e *p,*q,*s; p=L;q=q->next; while(q!=NULL&&q->data<=x) p=q;q=q->next; s=new NodeType; s->data=x; p->next=s; s->next=q;2.觀察下面的算法，此算法完成如下功能：在非遞減有序表中刪除所有值為X的元素。問：如何改進(jìn)此算法，使得算法效率提高？ void Deletaz(ElemType x) int i=0,j; while (i<length&& elemi<x) i+; if(i=length) c

11、out<<”X不存在”<<endl; else while(elemi=x) for(j=I;j<length;j+) elemj=elemj+1; length-;【答案】void delete(ElemType x) int i=0,j,n; while(i<length&&elemi<x) i+; if(i=length) cout<<“no x”<<endl; else while(elemi=x) n+;i+; for(j=i;j<length-1;j+) elemj-n=elemj; lengt

12、h=length-n; 3試設(shè)計(jì)一個(gè)算法，將線性表中前 m 個(gè)元素和后 n 個(gè)元素進(jìn)行互換，即將線性表 (a1, , , am, b1, b2, , bn ) 改變成(b1, b2, , bn, a1, a2, , am ) 要求采用順序存儲結(jié)構(gòu)及鏈?zhǔn)酱鎯Y(jié)構(gòu)分別完成，并比較采用這兩種存儲結(jié)構(gòu)，其算法效率哪種存儲結(jié)構(gòu)更好？【答案】試設(shè)計(jì)一個(gè)算法，順序表中前 m 個(gè)元素和后 n 個(gè)元素進(jìn)行互換，即將線性表 (a1, a2, , am, b1, b2, , bn ) 改變成 (b1, b2, , bn, a1, a2, , am ) 。 算法 1：進(jìn)行三次“逆轉(zhuǎn)順序表”的操作。算法 2：從 b1開

13、始，從原地刪除之后插入到 a1 之前直至 bn。例如：具體實(shí)例： a, b, c, d, e, f, g ,1, 2，3，4，5改變成1, 2，3，4，5,a, b, c, d, e, f, g54gfedcba3213gfedcba54321ji算法 1：void invert( ElemType R，int s， int t ) /* 本算法將數(shù)組 R 中下標(biāo)自 s 到 t 的元素逆置， 即將（Rs, Rs+1, , Rt-1, Rt ） 改變?yōu)椋≧t, Rt-1, , Rs+1, Rs ）*/ void exchange ( SqList A; int m ) /*本算法實(shí)現(xiàn)順序表中前

14、m 個(gè)元素和后 n 個(gè)元素的互換*/ n = A.length m; invert( A.elem, 0, A.length ); invert( A.elem, 0, n-1 ); invert( A.elem, n, m+n-1 ); 算法 2:void exchange( SqList A, int m ) /* 實(shí)現(xiàn)順序表 A 中前 m 個(gè)元素和后 n 個(gè)元素互換*/for ( i=0; j = m; j<A.length; i+,j+ ) x = A.elemj;for ( k=j; k>i; k- ) A.elemj = A.elemj-1; A.elemi = x;算

15、法的時(shí)間復(fù)雜度:為: O(m´n)算法設(shè)計(jì): 將 (b1, b2, , bn )從鏈表的當(dāng)前位置上刪除之后再插入 a1 到之前，并將 am設(shè)為表尾。a1a2amb1b2bnLtahbtbta->next=NULL;tb->next = L->next;L->next = hb;void exchange( SLink &L, int m ) / 互換鏈表中前 m 個(gè)和后 n 個(gè)結(jié)點(diǎn) ta = L; i = 0; while ( ta && i<m ) / 查詢結(jié)點(diǎn) amta = ta->next; i+; / whileif

16、 ( ta && ta->next ) / m < 表長 hb = ta->next; tb = hb; while (tb->next) tb = tb->next; / 查詢表尾 bn修改指針 算法的時(shí)間復(fù)雜度:為:O(ListLength(L)4討論線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系，以及不同存儲結(jié)構(gòu)的比較?！敬鸢浮看鎯Y(jié)構(gòu)分為：順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算

17、機(jī)存儲器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)： 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲結(jié)構(gòu) 順序表：可以實(shí)現(xiàn)隨機(jī)存?。篛(1) 插入和刪除時(shí)需要移動(dòng)元素：O(n) 需要預(yù)分配存儲空間; 適用于“不常進(jìn)行修改操作、表中元素相對穩(wěn)定”的場合。 鏈表：只能進(jìn)行順序存?。篛(n) 插入和刪除時(shí)只需修改指針：O(1) 不需要預(yù)分配存儲空間; 適用于“修改操作頻繁、事先無法估計(jì)最大表長”的場合。 應(yīng)用問題的算法時(shí)間復(fù)雜度的比較 例如，以線性表表示集合進(jìn)行運(yùn)算的時(shí)間復(fù)雜度為O(n2), 而以有序表表示集合進(jìn)行運(yùn)算的時(shí)間復(fù)雜度為O(n)習(xí) 題 21判斷下列概念的正確性(1) 線性表在物理存儲空間中也一定是連續(xù)

18、的。(2) 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。(3) 鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪去鏈表中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會自動(dòng)地將后繼的各個(gè)單元向前移動(dòng)。答：（1）（2）（3）都不正確。2. 有如下圖所示線性表，經(jīng)過daorder 算法處理后，線性表發(fā)生了什么變化？畫出處理后的線性表。 void daorder() int i, j, n ; ElemType x;n=length/2; for( i=0 ; i<n; i+ ) j=length-i-1; x=elemi; elemi=elemj; elemj=x; elem0 elem7 假設(shè)length=8 1 2 3 4 5 6 7

19、8 答：經(jīng)過daorder 算法處理后，線性表發(fā)生了逆置。處理后的線性表為：8 7 6 5 4 3 2 1 3試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。答：順序結(jié)構(gòu)存儲時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：一般情況下，存儲密度大，存儲空間利用率高。缺點(diǎn)：（1）在做插入和刪除操作時(shí)，需移動(dòng)大量元素；（2）由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴(kuò)充。鏈?zhǔn)浇Y(jié)構(gòu)存儲時(shí)，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。優(yōu)點(diǎn)：插入和刪除元素

20、時(shí)很方便，使用靈活。缺點(diǎn)：存儲密度小，存儲空間利用率低。4試寫出一個(gè)計(jì)算鏈表中結(jié)點(diǎn)個(gè)數(shù)的算法，其中指針指向該鏈表的第一個(gè)結(jié)點(diǎn)。答：int linklist_num(linklist L,Lnode *p) int n=0;While(p)n+;p=p->next;Return n:5試設(shè)計(jì)實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)的算法。 (a)為刪除前，(b)為刪除后。1015181510H(a) 刪除前181510H(b) 刪除后答：void Deletaz(Linklist L) Lnode *p,*q,*r,*s; P=l->next;while (p) q=p;r=q->n

21、ext;while(r)if(r->data!=p->data)q=r;r=r->next;elses=r->next;q->next=s;free(r);r=s; P=p->next; 6. 有一個(gè)線性表(a1,a2,.,an)，它存儲在有附加表頭結(jié)點(diǎn)的單鏈表中，寫一個(gè)算法，求出該線性表中值為x的元素的序號。如果x不存在，則輸出序號為零。答：int linklist_x(linklist L,datatype x)int i=0;Lnode *p;P=L->next;While(p&&p->dada!=x)i+;p=p->

22、next;If(!p)return 0;Else return I;7寫一個(gè)算法將一單鏈表逆置。要求操作在原鏈表上進(jìn)行。答：void reverse (LinkList L) p=L->next; L->next=NULL; while (p) q=p->next; p->next=L->next; L->next=p; p=q; 8在一個(gè)非遞減有序線性表中，插入一個(gè)值為X的元素，使插入后的線性表仍為非遞減有序。分別用向量和單鏈表編寫算法。答：void insert_x(Linklist L,Datatype x)/*在遞增有序的單鏈表L中插入值為x的元素，

23、使得插入后L仍然有序*/Lnode *p,*q,*r;P=L;q=p->next;While(q&&q->dada<=x)p=q;q=q->next;R=(Lnode *)malloc(Lnode);r->dada=x;r->next=q;p->next=r;9寫一算法將值為B的結(jié)點(diǎn)插在鏈表中值為a的結(jié)點(diǎn)之后。如果值為a的結(jié)點(diǎn)不存在，則插在表尾。答: void Insert_LinkList( LinkList L, DataType a, DataType B) /* 在值為a 的結(jié)點(diǎn)后插入值為B的結(jié)點(diǎn)，表中若無a則B接在表尾 */

24、LinkList p,q,s ; s=( LinkList)malloc(sizeof(struct node); s->data=B; s->next=NULL; q=L; p=L->next; while( p!=NULL && p->data!=a ) q=p; p=p->next; if(p)s->next=p->next;p->next=s;else s->next=q->next;q->next=s; 10試用循環(huán)鏈表為存儲結(jié)構(gòu)，寫一個(gè)約瑟夫(Josephu)問題的算法。約瑟夫問題是：有N個(gè)人圍成一圈

25、，從第i個(gè)人開始從1報(bào)數(shù)，數(shù)到m時(shí)，此人就出列。下一個(gè)人重新從1開始報(bào)數(shù)，再數(shù)到m時(shí)，以一個(gè)人出列。直到所有的人全部出列。按出列的先后得到一個(gè)新的序列。例如，N=5， i=1, m=3 時(shí)新的序列應(yīng)為：3, 1, 5, 2, 4。答：typedef struct node /* 結(jié)點(diǎn)的結(jié)構(gòu)定義 */ int num; /* 編號子域 */ struct node *next; /* 指針域 */ JOS;void outs(JOS *h, int m) int i; JOS *q=h, *p; printf(“n “); while (q->next!=q) for(i=1;i<m

26、;i+) p=q; q=q->next; /* 報(bào)數(shù)到第m個(gè)人 */ printf(“%6d”,q->num); /* 輸出第m個(gè)人的編號 */ p->next=q->next; free(q); /* 第m個(gè)人出列 */ q=p->next; printf(“%6d n”,q->num); /* 輸出最后一個(gè)結(jié)點(diǎn)的編號值 */ free(q); /* outs */11. 設(shè)有兩個(gè)單鏈表A、B，其中元素遞增有序，編寫算法將A、B歸并成一個(gè)按元素值遞減（允許有相同值）有序的鏈表C，要求用A、B中的原結(jié)點(diǎn)形成，不能重新申請結(jié)點(diǎn)。答：void unit(Link

27、list A,Linklist B,Linklist C)Lnode *p,*q,*r,*s;P=A->next;q=>next;C=A;r=C;While(p&&q)if(p->dada<=q->dada)r=p;p=p->next;Elses=q;q=q->next;s->next=r->next;r->next=s;r=s;If(!p)r->next=q;free(B)討論小課堂 3【參考內(nèi)容】1. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5

28、 4 2 6;請說明為什么不能實(shí)現(xiàn)或如何才能得到。2. 設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？棧可以用單鏈表實(shí)現(xiàn)嗎？【答案】1、輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。 得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。2、不能得到序列2，5，3，4，6。棧

29、可以用單鏈表實(shí)現(xiàn)，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設(shè)頭結(jié)點(diǎn)。3. 簡述順序存儲隊(duì)列的“假溢出”現(xiàn)象的避免方法及怎樣判定隊(duì)列滿和空的條件。【答案】：3、設(shè)順序存儲隊(duì)列用一維數(shù)組qm表示，其中m為隊(duì)列中元素個(gè)數(shù)，隊(duì)列中元素在向量中的下標(biāo)從0到m-1。設(shè)隊(duì)頭指針為front，隊(duì)尾指針是rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。當(dāng)front等于-1時(shí)隊(duì)空，rear等于m-1時(shí)為隊(duì)滿。由于隊(duì)列的性質(zhì)（“刪除”在隊(duì)頭而“插入”在隊(duì)尾），所以當(dāng)隊(duì)尾指針rear等于m-1時(shí)，若front不等于-1，則隊(duì)列中仍有空閑單元，所以隊(duì)列并不是真滿。這時(shí)若再有入隊(duì)操作，會造成假

30、“溢出”。其解決辦法有二，一是將隊(duì)列元素向前“平移”（占用0至rear-front-1）；二是將隊(duì)列看成首尾相連，即循環(huán)隊(duì)列（0.m-1）。在循環(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ì)滿。4.假設(shè)有如下圖所示的列車調(diào)度系統(tǒng)，約定兩側(cè)鐵道均為單向行駛，入口處有N節(jié)硬席或軟席車廂（程序中可分別用

31、H和S表示）等待調(diào)度，試編寫算法，輸出對這N節(jié)車廂進(jìn)行調(diào)度的操作序列，要求所有的軟席車廂被調(diào)整到硬席車廂之前。v 【參考答案】：v void trains(char *elem) v int i,k; v k=0; v for(i=0;i<length;i+) v if(elemi=S) /軟席車廂Sv push(); v pop(); v v else v push(); v k+ v while(k>0)pop();k-; v 5.對于一個(gè)具有N個(gè)單元（N>>2）的循環(huán)隊(duì)列，若從進(jìn)入第一個(gè)元素開始每隔T1個(gè)時(shí)間單位進(jìn)入下一個(gè)元素，同時(shí)從進(jìn)入第一個(gè)元素開始，每隔T2（

32、T2>T1）個(gè)時(shí)間單位處理完一個(gè)元素并令其出隊(duì)，試編寫一個(gè)算法，求出在第幾個(gè)元素進(jìn)隊(duì)時(shí)將發(fā)生溢出。v 【分析】v 時(shí)刻t: 0 1 2 3 4 5 6 7 8 9 v 個(gè)數(shù)： 1 1 2 1 2 2 3-2 2 3 2v 放?。?+ + - + + - + -v 時(shí)刻t: 10 11 12 13v 個(gè)數(shù)： 3 3 4-3 v 放?。?+ + - vv N=2 v 先放后?。?6時(shí)刻，放了4次，3個(gè)為溢出v 放取同時(shí)： 8時(shí)刻，放了5次，3個(gè)為溢出如果同一時(shí)刻先放后?。? int main( )   int  y=1,i=0, n, m, front

33、=0,rear=1; cin>>n; cin>>t1;cin>>t2; m=n+2; if (t1>=t2) cout<<"error!"   else    while(rear+1)%m!=front)      i+;       if (i%t1=0) rear=(rear+1 )%m; y+;       

34、; if (i%t1=0&&(rear+1)%m=front) break;        if (i%t2=0) front=(front+1 )%m;                 cout<<i<<" "cout<<y;       

35、60; return 0;習(xí)題31.假定有編號為A、B、C、D的四輛列車，自右向左順序開進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺，如圖3.16所示?？梢酝ㄟ^棧來編組然后開出站臺。請寫出列車開出站臺的順序有幾種？寫出每一種可能的序列。如果有n輛列車進(jìn)行編組呢？如何編程？注：每一輛列車由站臺向左開出時(shí)，均可進(jìn)棧、出棧開出站臺，但不允許出棧后回退。圖3.16 火車編組棧2.已知棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，初始時(shí)為空，試畫出a,b,c,d四個(gè)元素依次進(jìn)棧以后棧的狀態(tài)，然后再畫出此時(shí)的棧頂元素出棧后的狀態(tài)。3.寫出鏈表?xiàng)５娜ｍ斣睾椭脳？盏乃惴ā?.寫出計(jì)算表達(dá)式3+4/25*8-6時(shí)，操作數(shù)棧和運(yùn)算符棧的變化情況表。5.對于給

36、定的十進(jìn)制正整數(shù)N，轉(zhuǎn)換成對應(yīng)的八進(jìn)制正整數(shù)。（1）寫出遞歸算法。 （2）寫出非遞歸算法。6.已知n為大于等于零的整數(shù)，試寫出計(jì)算下列遞歸函數(shù)f(n)的遞歸和非遞歸算法。 f(n)=7. 假設(shè)如題3.1所述火車調(diào)度站的入口處有n節(jié)硬席或軟席車廂（分別以H和S表示）等待調(diào)度。試編寫算法，輸出對這n節(jié)車廂進(jìn)行調(diào)度的操作（即入?；虺鰲２僮鳎┬蛄?，以使所有的軟席車廂都被調(diào)整到硬席車廂之前。8.課文中規(guī)定：無論是循環(huán)隊(duì)列還是鏈表隊(duì)列，隊(duì)頭指針總是指向隊(duì)頭元素的前一位置，隊(duì)尾指針指向隊(duì)尾元素。（1）試畫出有個(gè)元素、B的循環(huán)隊(duì)列圖，及將這2個(gè)元素出隊(duì)后隊(duì)列的狀態(tài)圖。 注：假設(shè)MAXSIZE=6，front=

37、5，完成本題要求的圖示。若erar=5，情況如何？（2）試畫出有個(gè)元素C、D的鏈表隊(duì)列圖，及將這2個(gè)元素出隊(duì)后鏈表隊(duì)列的狀態(tài)圖。9.對于一個(gè)具有m個(gè)單元的循環(huán)隊(duì)列，寫出求隊(duì)列中元素個(gè)數(shù)的公式。10.對于一個(gè)具有n個(gè)單元(n>>2)的循環(huán)隊(duì)列,若從進(jìn)入第一個(gè)元素開始，每隔t1個(gè)時(shí)間單位進(jìn)入下一個(gè)元素，同時(shí)從進(jìn)入第一個(gè)元素開始，每隔t2(t2t1)個(gè)時(shí)間單位處理完一個(gè)元素并令其出隊(duì)，試編寫一個(gè)算法，求出在第幾個(gè)元素進(jìn)隊(duì)時(shí)將發(fā)生溢出。11.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫出相應(yīng)的置空隊(duì)列，入隊(duì)列和出隊(duì)列的算法。12.二項(xiàng)式(a

38、+ b)i展開后，其系數(shù)構(gòu)成楊輝三角形。利用隊(duì)列寫出打印楊輝三角形前n行的程序。即逐行打印二項(xiàng)展開式(a + b)i 的系數(shù)。圖3.17是指數(shù)i從1到6的(a + b)i的展開式系數(shù)所構(gòu)成的楊輝三角形。討論小課堂4重點(diǎn)掌握串的匹配運(yùn)算及應(yīng)用，可結(jié)合實(shí)際的題目進(jìn)行討論來加深對串的一些運(yùn)算的理解和掌握。1. 輸入一個(gè)字符串，內(nèi)有數(shù)字和非數(shù)字字符，如：ak123x456 17960?302gef4563，將其中連續(xù)的數(shù)字作為一個(gè)整體，依次存放到一數(shù)組中，例如123放入,456放入，。編程統(tǒng)計(jì)其共有多少個(gè)整數(shù)，并輸出這些數(shù)?！緟⒖即鸢浮吭谝粋€(gè)字符串內(nèi)，統(tǒng)計(jì)含多少整數(shù)的問題，核心是如何將數(shù)從字符串中分離

39、出來。從左到右掃描字符串，初次碰到數(shù)字字符時(shí)，作為一個(gè)整數(shù)的開始。然后進(jìn)行拼數(shù)，即將連續(xù)出現(xiàn)的數(shù)字字符拼成一個(gè)整數(shù)，直到碰到非數(shù)字字符為止，一個(gè)整數(shù)拼完，存入數(shù)組，再準(zhǔn)備下一整數(shù)，如此下去，直至整個(gè)字符串掃描到結(jié)束。算法如下：int CountInt（）/* 從鍵盤輸入字符串，連續(xù)的數(shù)字字符算作一個(gè)整數(shù)，統(tǒng)計(jì)其中整數(shù)的個(gè)數(shù)。*/int i=0，a； /* 整數(shù)存儲到數(shù)組a，i記整數(shù)個(gè)數(shù)*/ char ch;scanf(%d,&ch)；/* 從左到右讀入字符串*/while（ch!=#） /*#是字符串結(jié)束標(biāo)記*/if（ch）>=48 && (ch)<=57）

40、/* 是數(shù)字字符*/num=； /*數(shù)初始化*/while（ch）>=48 && (ch)<=57 && ch!=#）/* 拼數(shù)*/num=num10+ch-；scanf(%d,&ch)； ai=num；i+；if（ch!=#）scanf(%d,&ch)；/* 若拼數(shù)中輸入了#，則不再輸入*/ while（ch！#） /* 結(jié)束*/Printf(”共有%d”,I,”個(gè)整數(shù)，它們是：”)；for（j=；j<i；j+）printf(“%d”;aj;” “)； if（j+1）10=0）printf(“n”); /*每10個(gè)數(shù)輸出在一行

41、上*/* 算法結(jié)束*/假定字符串中的數(shù)均不超過32767，否則，需用長整型數(shù)組及變量。2. 以順序存儲結(jié)構(gòu)表示串，設(shè)計(jì)算法。求串S中出現(xiàn)的第一個(gè)最長重復(fù)子串及其位置并分析算法的時(shí)間復(fù)雜度。例如：若S=“abceebccadddddaaadd!”， 則最長重復(fù)子串為“ddddd”。位置是9?！緟⒖即鸢浮吭O(shè)以字符數(shù)組s表示串，重復(fù)子串的含義是由一個(gè)或多個(gè)連續(xù)相等的字符組成的子串，其長度用max表示，初始長度為0，將每個(gè)局部重復(fù)子串的長度與max相比，若比max大，則需要更新max，并用index記住其開始位置。算法如下：int LongestString(char s,int n)/*串用一維數(shù)組

42、s存儲，長度為n，本算法求最長重復(fù)子串，返回其長度。*/int index=0,max=0; /*index記最長的串在s串中的開始位置，max記其長度*/ int length=1,i=0,start=0; /*length記局部重復(fù)子串長度，i為字符數(shù)組下標(biāo)*/ while(i<n-1) if(si=si+1) i+; length+; else /*上一個(gè)重復(fù)子串結(jié)束*/if(max<length) max=length; index=start; /*當(dāng)前重復(fù)子串長度大，則更新max*/i+;start=i;length=1; /*初始化下一重復(fù)子串的起始位置和長度*/Pr

43、intf(“最長重復(fù)子串的長度為:%d“;max;”在串中的位置:%d”;index);return(max);/*算法結(jié)束*/算法中用i<n-1來控制循環(huán)次數(shù)，因C數(shù)組下標(biāo)從0 開始，故長度為n的串，其最后一個(gè)字符下標(biāo)是n-1，當(dāng)i最大為n-2時(shí)，條件語句中si+1正好是sn-1，即最后一個(gè)字符。子串長度的初值數(shù)為1，表示一個(gè)字符自然等于其身。算法的時(shí)間復(fù)雜度為O(n)，每個(gè)字符與其后繼比較一次。習(xí)題4習(xí)題41填空（1）在計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是采用 顯式 ，第二種是 隱式 。（2）一個(gè)字符串相等的充要條件是 長度 和 對應(yīng)字符都相等 。（3）串是指 有限個(gè)

44、字符組成 的序列；空串是指 長度 的串；空格串是指 一個(gè)或多個(gè)空格組成 的串。（4）設(shè)s=“IAMATEACHER”,其長度是_14_。（5）若n為主串長，m為子串長，則串的古典匹配算法最壞的情況下需要比較字符的總次數(shù)為 （m*n） 。2空串和空格串有何區(qū)別？字符串中的空格符有何意義？空串在串的處理中有何作用？答：空串時(shí)長度為0的字符串；空格串是一個(gè)或多個(gè)字符組成的字符串。字符串中的空格符充當(dāng)界符的作用?？沾诖奶幚碇锌勺鳛槿我獯淖哟?。3設(shè)計(jì)一算法，將兩個(gè)字符串連接起來，要求不能利用strcat（）函數(shù)。答：Typedef struct char *ch; /*串?dāng)?shù)組*/ int leng

45、th; /*串長*/HString;int StrConcat(HString *S, HString T) char *temp;temp=(char *)malloc(S->length);if(temp=NULL)return(0);for(int i=0;i<S->length;i+)tempi=S->chi;/* 先把串S放入臨時(shí)串temp中*/free(S->ch);S->ch=(char*)malloc(S->length+T.length); /* 為S分配新的空間*/for(int i=0;i< S->length;i+)

46、S->chi=tempi;for(int j=0;j< T.length;j+)S->chi+j=T.chj;return(1);.4設(shè)計(jì)一算法，將字符串S中從pos位置開始共num 個(gè)字符構(gòu)成的子串用字符串X來代替(X的長度可以不同于num)。答：Typedef struct char *ch; /*串?dāng)?shù)組*/ int length; /*串長*/HString;void Strrepl (HString *S, int pos, int num,HString X) if (pos < 1 | pos > S->length+1) printf(&quo

47、t;n 位置錯(cuò)誤!");return; /*位置不合法*/ char S1S->length ; /* S1 作為輔助串空間用于暫存 S */ if (X.length) /*X 非空，則為S重新分配空間并替換X*/char *p=S->ch; i=0;while (i < S.length)S1i+ = *(p+i); /* 暫存串S*/if(pos+num>S->length)S->ch = new charpos + X.length ;Else S-> ch = new charS->length-num + X.length

48、; /* 為S重新分配串值存儲空間*/for ( i=0, k=0; i<pos-1; i+)S->chk+ = S1i; /*保留插入位置之前的子串*/j = 0;while (j<X.length) S->chk+ = X.chj+; /* 替換X*/while ( i<S->length)S->chk+ = S1i+; /* 復(fù)制替換部分后的子串*/S->length+=T.length; /* 置串 S 的長度*/ /* if */ /* Strrepl*/5試設(shè)計(jì)一個(gè)算法，測試一個(gè)串t的值是否為回文（即從左面讀起與從右面讀起內(nèi)容一樣）。

49、答：int isSym(char *str,int length)  /*判斷一個(gè)字符串是否為回文,0是，-1不是for(int i=0;i<length/2;i+)        if(stri != strlength-i-1)                        re

50、turn -1;                return 0;6編寫一個(gè)算法，統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度。答：#include   <stdio.h>     int   main()           int   charcount256;     int   i;    

51、char   ch;     /*初始化*/    for(i=0;i<256;i+)     charcounti   =   0;     while(ch   =   getchar()   !=   'n')     charcount   (int)ch     +;     /*輸出*/     for(i=0;i<2

52、56;i+)     if(   charcounti)   printf("%c   -   %dn",   i,   charcounti);     return   0;     7設(shè)s=”00001000010100001”, t =”0001”,說明其在樸素模式匹配算法中的匹配過程。答： i=3第一趟匹配 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(1)0 0 0 1 j=3 i=5 第二趟匹配0 0 0 0

53、1 0 0 0 0 1 0 1 0 0 0 0 1(2) 0 0 0 1 j=4 8設(shè)計(jì)一個(gè)算法Replace(w,x), 將當(dāng)前字符串所有子串w用另一個(gè)字符串x來替換。字符串w和x的長度可以不同。答：參考習(xí)題4和匹配算法。討論小課堂5參考內(nèi)容1設(shè)m×n階稀疏矩陣A有t個(gè)非零元素，其三元組表表示為LTMA1.(t+1),1.3，試問：非零元素的個(gè)數(shù)t達(dá)到什么程度時(shí)用LTMA表示A才有意義？【參考答案】：稀疏矩陣A有t個(gè)非零元素，加上行數(shù)mu、列數(shù)nu和非零元素個(gè)數(shù)tu，共占用三元組表LTMA的3(t+1)個(gè)存儲單元，用二維數(shù)組存儲時(shí)占用m×n個(gè)單元，只有當(dāng)3(t+1)< m×n時(shí)，用LTMA表示A才有意義。解不等式得t< m×n/3-1。2特殊矩陣和稀疏矩陣哪一種壓縮存儲后