1、討論小課堂11.算法和程序的區別是什么呢？【參考答案】：算法的含義與程序十分相似，但又有區別。一個程序不一定滿足 有窮性。例如，操作系統，只要整個系統不遭破壞，它將永遠不會停止，即使沒 有作業需要處理，它仍處于動態等待中。因此，操作系統不是一個算法。另一方 面，程序中的指令必須是機器可執行的， 而算法中的指令則無此限制。算法代表 了對問題的解，而程序則是算法在計算機上的特定的實現。一個算法若用程序設計語言來描述，則它就是一個程序。算法與數據結構是相輔相承的。解決某一特定類型問題的算法可以選定不同 的數據結構，而且選擇恰當與否直接影響算法的效率。 反之，一種數據結構的優 劣由各種算法的執行來體現

2、。要設計一個好的算法通常要考慮以下的要求。正確。算法的執行結果應當滿足預先規定的功能和性能要求?？勺x。一個算法應當思路清晰、層次分明、簡單明了、易讀易懂。健壯。當輸入不合法數據時，應能作適當處理，不至引起嚴重后果。高效。有效使用存儲空間和有較高的時間效率。2,你認為應該如何評估一個數據結構或算法的有效性?！緟⒖即鸢浮浚呵疤嶂皇撬惴ǖ恼_性；其二還必須考慮執行算法所耗費的時 問和執行算法所耗費的空間（主要是只指輔助空間），以及算法是否易讀、易編 碼和易于調試。3,討論數據結構的重要性?！緟⒖即鸢浮浚喝缃裼嬎銠C的應用已深入到社會生活 的各個領域，計算機處理的 對象由單純的數值 發展到字符、圖象、

3、聲音等，表示這些對象的數據成分往往 不是單一的，而是多成分且形成一定的結構。因此，在程序設計中，除了應精心設計算法外，還應精心組織數據（包括原始數據、中間結果 、最終結果）， 使之形成一定的組織形式（數據結構），以便讓計算機盡可能高效率地處理。在 實際程序設計的實踐中，數據結構和算法是不同的但又是互相聯系的兩個方面。 我們甚至還可以說，問題的算法往往取決于選定的數據結構。所以N.Wirth教授認為程序設計=算法+數據結構。我們已經初步地學習了高級語言（例如pascaD的程序設，掌握了一些程序設 計方法與技巧。然而，這些方法與技巧對于現實的程序設計工作來說 ，是遠遠 不夠的。以下舉幾個例子加以說

4、明 。例1求真分數117/29的值，求到小數點后50位例2求真分數7/27的值，精確到小數點后50位。1 .輸出117 /29的值。2 . a <余數。b<293 . aa * 10。4 .輸出a/b的商。5 . a<一余數。6 .如未達要求，轉3 ,否則結束。例3從鍵盤輸入若干個數，并將其排序輸出。相同的數，只輸出一個。本 例似乎不難，可以采取的策略之一：用一個數組來存放輸入的數，然后排序輸出。策略之二：邊輸入邊排序。我們注意到：輸出只能是不同的數 ，因而這是一個搜索加排序的問題。所 以，不論采取那一種策略，用數組這一種結構不是最佳的結構， 因為效率很低 事實上，若用二叉樹

5、作為存儲結構，效率則會大大提高。例4工作安排的可行性問題。為了直觀了解工作環節之間的制約關系，通 常用“有向圖”來表示這種安排。高等數學數據結構<高級語言習題11 .抽象數據類型的定義由哪幾部分組成?1.1 【參考答案】：數據對象、數據關系和基本操作三部分。2 .按數據元素之間的邏輯關系不同，數據結構有哪幾類？1.2【參考答案】：線性結構、樹型結構、圖狀結構和集合四類。3.你能舉出幾個你熟悉的"序列"的例子來嗎？1.3【參考答案】： 如："0, 1, 2,，9","A , B, C,，Z"。4 .簡述下列術語：數據、數據元素、數

6、據對象、數據結構、存儲結構、數據類型和抽象數據類型。5 .數據結構和數據類型兩個概念之間有區別嗎？1.5【參考答案】：簡單地說，數據結構定義了一組按某些關系結合在一起的數組 元素。數據類型不僅定義了一組帶結構的數據元素，而且還在其上定義了 一組操 作。6.簡述線性結構與非線性結構的不同點1.6【參考答案】：線性結構反映結點間的邏輯關系是一對一的，非線性結構反映結點間的邏輯關系是多對多的。7 .有下列兩段描述：n=2;While(n%2=0)n=n+2;printf( %dn”,n);(1) void pro1( )(2)void pro2()y=0;x=5/y;printf( %d,%dn,x

7、,y)這兩段描述均不能滿足算法的特征，試問它們違反了算法的那些特征？1.7【參考答案】：(1)是一個死循環，違反了算法的有窮性特征。(2)出現除零錯誤，違反了算法的可行性特征。8 .分析并寫出下面的各語句組所代表的算法的時間復雜度。(1) for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0；【參考答案】：O (m*n) k=0;for( i=1; i<=n; i+) for (j=i ; j<=n; j+)k+;)【參考答案】：O (n2)(3) i=1;while(i<=n)i=i*3;【參考答案】：3T(n)&n 即：T

8、(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;【參考答案】：基本語句共執行了 n/2次，T(n)=O (n)(6) x=0;for(i=1; i<n; i+)for (j=1; j<=n-i; j+)x+;【參考答案】:因為x+共執行了 n-

9、1+n-2+1= n(n-1)/2,所以執行時間為O2(n2)-1)2藺f n n-1F5)二工 gi=辦二 jf+i i=i討論小課堂21 .在一個非遞減有序線性表中，插入一個值為 X的元素，使插入后的線性表仍為非遞減有序。(注意：對比順序存儲結構和鏈式存儲結構表示。)【參考答案】方法一：順序存儲結構void insert(ElemType x) i=length-1;while(i>=0&&elemi>x)elemi+1=elemi;i-;elemi+1=x;length+;方法二：鏈式存儲結構void insert(ElemType x) NodeType *

10、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 .觀察下面的算法，此算法完成如下功能：在非遞減有序表中刪除所有值為元素。問：如何改進此算法，使得算法效率提高？void Deletaz(ElemType x) int i=0,j;while (i<length&& elemi<x) i+;if(i=l ength) cout<<

11、”Wf在 " <<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;elsewhile(elemi=x)n+;i+;for(j=i;j<length-1;j+)elemj-n=elemj;length=length-n;

12、3 .試設計一個算法，將線性表中前m個元素和后n個元素進行互換，即將線性表(ai,，am，bi, b2,，bn ) 改變成(bi, b2,，bn, ai,吻 ，am )要求采用順序存儲結構及鏈式存儲結構分別完成，并比較采用這兩種存儲結構，其算法效率哪種存儲結構更好？【答案】試設計一個算法，順序表中前m個元素和后n個元素進行互換，即將線性表(ai,孫，am, bi, b2,，bn ) 改變成(b1, b2,，bn, ai, a2,，am )。算法i:進行三次“逆轉順序表”的操作。算法2：從bi開始，從原地刪除之后插入到ai之前直至bn。例如：具體實例： a, b, c, d, e, f, g ,

13、i, 2, 3, 4, 5改變成i, 2, 3, 4, 5,a, b,c, d, e, f, g i ij123abcdefg4512345abcdefg算法1:void invert( ElemType R口, int s, int t )/*本算法將數組 R中下標自s到t的元素逆置，即將(Rs, Rs+1,Rt-1, Rt ) 改變為(Rt, Rt-1,，Rs+1, Rs */void exchange ( SqList A; int m ) /*本算法實現順序表中前m個元素和后n個元素的互換*/n = A.length - m;invert( A.elem, 0, A.length );

14、invert( A.elem, 0, n-1 );invert( A.elem, n, m+n-1 );算法2:void exchange( SqList A, int m ) /*實現順序表A中前m個元素和后n個元素互換*/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;算法的時間復雜度：為：O(m")算法設計:將（b1, b2,，bn處表的當前位置上刪除之后再插入al到之前，并將am設為表尾。ta->next=

15、NULL;tb->next = L->next;L->next = hb;void exchange( SLink &L, int m ) /互換鏈表中前 m個和后n個結點ta = L; i = 0;while ( ta && i<m ) / 查詢結點 amta = ta->next; i+; whileif ( ta && ta->next ) / m < 表長hb = ta->next; tb = hb;while (tb->next) tb = tb->next; / 查詢表尾 bn 修改

16、指針算法的時間復雜度：為:O(ListLength(L)4.討論線性表的邏輯結構和存儲結構的關系，以及不同存儲結構的比較【答案】存儲結構分為：順序存儲結構：借助元素在存儲器中的相對位置來表示數據元素間的邏輯關系鏈式存儲結構：借助指示元素存儲地址的指針表示數據元素間的邏輯關系數據的邏輯結構一只抽象反映數據元素的邏輯關系數據的存儲(物理)結構一數據的邏輯結構在計算機存儲器中的實現數據的邏輯結構與存儲結構密切相關：算法設計一邏輯結構算法實現一存儲結構順序表：可以實現隨機存?。?(1)插入和刪除時需要移動元素：0(n)需要預分配存儲空間；適用于不常進行修改操作、表中元素相對穩定”的場 合。鏈表：只能進

17、行順序存取：0(n)插入和刪除時只需修改指針：0(1)不需要預分配存儲空間；適用于修改操作頻繁、事先無法估計最大表長”的場合。應用問題的算法時間復雜度的比較例如，以線性表表示集合進行運算的時間復雜度為0 (n2),而以有序表表示集合進行運算的時間復雜度為 0 (n)習題21 .判斷下列概念的正確性(1)線性表在物理存儲空間中也一定是連續的。(2)鏈表的物理存儲結構具有同鏈表一樣的順序。(3)鏈表的刪除算法很簡單，因為當刪去鏈表中某個結點后，計算機會自動地將后繼的各個單元向前移動。答：(1) (2) (3)都不正確。2 .有如下圖所示線性表，經過daorder算法處理后，線性表發生了什么變化？畫

18、 出處理后的線性表。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假設 length=812345678答：經過daorder算法處理后，線性表發生了逆置。處理后的線性表為:876543213 .試比較順序存儲結構和鏈式存儲結構的優缺點。答：順序結構存儲時，相鄰數據元素的存放地址也相鄰，即邏輯結構和存儲結構是統 一的，要求內存中存儲單元的地址必須是連續的。優點：一般情況下，存儲密度大，

19、存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必 須預先分配較大的空間，往往使存儲空間不能得到充分利用；（ 3）表的容量難 以擴充。鏈式結構存儲時，相鄰數據元素可隨意存放，所占空間分為兩部分，一部分存放 結點值，另一部分存放表示結點間關系的指針。優點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。4 .試寫出一個計算鏈表中結點個數的算法，其中指針p指向該鏈表的第一個結 點。答：int linklist_num（linklist L,Lnode *p） int n=0;While（p）n+;p=p->next;Return

20、n:5 .試設計實現在單鏈表中刪去值相同的多余結點的算法。（a）為刪除前，（b）為刪除后。j MI * 15 |18 人(b)刪除后答：void Deletaz(Linklist L) Lnode *p,*q,*r,*s;P=l->next;while (p) q=p;r=q->next;while(r)if(r->data!=p->data)q=r尸r->next;elses=r->next;q->next=s;free(r);r=s;P=p->next;6 .有一個線性表(a1,a2,an)它存儲在有附加表頭結點的單鏈表中，寫一個算法， 求出

21、該線性表中值為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->next;If(!p)return 0;Else return I;7寫一個算法將一單鏈表逆置。要求操作在原鏈表上進行。答： void reverse (LinkList L) p=L->next;L->next=NULL;while (p) q=p->next;p->next=L-

22、>next;L->next=p;p=q;8在一個非遞減有序線性表中，插入一個值為X 的元素，使插入后的線性表仍為非遞減有序。分別用向量和單鏈表編寫算法。答： void insert_x(Linklist L,Datatype x)/*在遞增有序的單鏈表L中插入值為x的元素，使得插入后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=

23、r;9 .寫一算法將值為B的結點插在鏈表中值為a的結點之后。如果值為a的結點不存在，則插在表尾。答 : void Insert_LinkList( LinkList L, DataType a, DataType B)/* 在值為 a 的結點后插入值為B 的結點， 表中若無a 則B 接在表尾*/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

24、=p->next; if(p)s->next=p->next;p->next=s;else s->next=q->next;q->next=s;10 .試用循環鏈表為存儲結構，寫一個約瑟夫（Josephu）可題的算法。約瑟夫問題是： 有 N 個人圍成一圈，從第 i 個人開始從1 報數， 數到 m 時， 此人就出列。下一個人重新從1 開始報數，再數到m 時，以一個人出列。直到所有的人全部出列。按出列的先后得到一個新的序列。例如，N=5，i=1, m=3 時新的序列應為：3, 1, 5, 2, 4。答：typedef struct node/* 結點的結構

25、定義*/ 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;i+) p=q; q=q->next; printf( “ %6-d”>n,uqm);/*p->next=q->next; free(q); q=p->next;printf( “ %6nd” ,-q>num);free(q); /* outs */*/*/* 報數到第m

26、個人 */輸出第 m 個人的編號*/* 第 m 個人出列*/* 輸出最后一個結點的編號值*/11 .設有兩個單鏈表A、B,其中元素遞增有序，編寫算法將A、B歸并成一個按元素值遞減(允許有相同值)有序的鏈表 C,要求用A、B中的原結點形 成，不能重新申請結點。答： void unit(Linklist 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=

27、q->next;s->next=r->next;r->next=s;r=s;If(!p)r->next=q;free(B) 討論小課堂3【參考內容】1 .如果輸入序列為1 2 3 4 5 6,試問能否通過棧結構得到以下兩個序列：4 3 56 1 2和1 3 5 4 2 6;請說明為什么不能實現或如何才能得到。2 .設輸入序列為2, 3, 4, 5, 6,利用一個棧能得到序列 2, 5, 3, 4, 6嗎？ ?？梢杂脝捂湵韺崿F嗎？【答案】1、輸入序列為123456,不能得出435612,其理由是，輸出序列最后兩元素 是12,前面4個元素（ 4356）得到后，棧中元素

28、剩12,且2在棧頂，不可能棧 底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列1;然后2和3 入棧，3出棧，部分輸出序列變為：13;接著4和5入棧，5, 4和2依次出棧， 部分輸出序列變為13542;最后6入棧并退棧，得最終結果135426。2、不能得到序列2, 5, 3, 4, 6。棧可以用單鏈表實現，這就是鏈棧。由于 棧只在棧頂操作，所以鏈棧通常不設頭結點。3 .簡述順序存儲隊列的“假溢出”現象的避免方法及怎樣判定隊列滿和空的條 件。【答案】：3、設順序存儲隊列用一維數組qm表示，其中m為隊列中元素個數，隊列中元 素在向量中的下標從0到m-1。設隊頭

29、指針為front ,隊尾指針是rear ,約定front 指向隊頭元素的前一位置，rear指向隊尾元素。當front等于-1時隊空，rear 等于m-1時為隊滿。由于隊列的性質（“刪除”在隊頭而“插入”在隊尾），所以 當隊尾指針rear等于m-1時，若front不等于-1 ,則隊列中仍有空閑單元，所 以隊列并不是真滿。這時若再有入隊操作，會造成假“溢出”。其解決辦法有二， 一是將隊列元素向前“平移”（占用0至rear-front-1 ）；二是將隊列看成首尾 相連，即循環隊列（0.m-1 ）。在循環隊列下，仍定義front=rear時為隊空，而 判斷隊滿則用兩種辦法，一是用“犧牲一個單元”,即r

30、ear+1=front（準確記是（rear+1 ） %m=front, m是隊列容量）時為隊滿。另一種解法是“設標記”方法，如設標記tag , tag等于0情況下，若刪除時導致front=rear 為隊空；tag=1情 況下，若因插入導致front=rear則為隊滿。4 .假設有如下圖所示的列車調度系統，約定兩側鐵道均為單向行駛，入口處有N節硬席或軟席車廂（程序中可分別用 H和S表示）等待調度，試編寫算法，輸出 對這N節車廂進行調度的操作序列，要求所有的軟席車廂被調整到硬席車廂之 前?！緟⒖即鸢浮浚簐oid trains(char *elem) int i,k;k=0;for(i=0;i<

31、;length;i+) if(elemi= S ) 軟席車廂 S push()； pop()；elsepush()； k+while(k>0)pop();k-;5 .對于一個具有N個單元(N>>2的循環隊列，若從進入第一個元素開始每隔T1個時間單位進入下一個元素，同時從進入第一個元素開始，每隔T2 (T2>T1)求出在第幾個元素進個時間單位處理完一個元素并令其出隊， 試編寫一個算法, 隊時將發生溢出?！痉治觥繒r亥ij t:012個數：112放?。?時亥ij t: 1011個數：33放?。?+3 4561223-2-+ -12134-3+ -N=2先放后?。?6時刻，放了

32、 4次，3個為溢出放取同時： 8時刻，放了 5次，3個為溢出如果同一時刻先放后?。篿nt main( ) int y=1,i=0, n, m, front=0,rear=1;cin>>n; cin>>t1;cin>>t2; m=n+2;if (t1>=t2) cout<<"error!”;elsewhile(rear+1)%m!=front) i+;if (i%t1=0) rear=(rear+1 )%m; y+; if (i%t1=0&&(rear+1)%m=front) break;if (i%t2=0) fr

33、ont=(front+1 )%m; cout<<i<<" "cout<<y;return 0;習題31 .假定有編號為 A B G D的四輛列車，自右向左順序開進一個棧式結 構的站臺，如圖3.16所示?？梢酝ㄟ^棧來編組然后開出站臺。請寫出列車開 出站臺的順序有幾種？寫出每一種可能的序列。 如果有n輛列車進行編組呢? 如何編程？注：每一輛列車由站臺向左開出時，均可進棧、出棧開出站臺，但不允許 出棧后回退。A B C D圖3.16火車編組棧2 .已知棧采用鏈式存儲結構，初始時為空，試畫出 a,b,c,d四個元素依次 進棧以后棧的狀態，然后再畫

34、出此時的棧頂元素出棧后的狀態。3 .寫出鏈表棧的取棧頂元素和置?？盏乃惴?。4 .寫出計算表達式3+4/25*8-6時，操作數棧和運算符棧的變化情況表。5 .對于給定的十進制正整數 N,轉換成對應的八進制正整數。(1)寫出遞歸算法。(2)寫出非遞歸算法。6 .已知n為大于等于零的整數，試寫出計算下列遞歸函數f(n)的遞歸和非 遞歸算法。f(n)=n +1當n = 0時n* f (n/2)當n#0時7 .假設如題3.1所述火車調度立勺入口處有 n節硬席或軟席車廂(分別 以H和S表示)等待調度。試編寫算法，輸出對這n節車廂進行調度的操作(即 入?；虺鰲２僮?序列，以使所有的軟席車廂都被調整到硬席車廂

35、之前。8 .課文中規定：無論是循環隊列還是鏈表隊列，隊頭指針總是指向隊頭元 素的前一位置，隊尾指針指向隊尾元素。(1)試畫出有2個元素A、 B的循環隊列圖，及將這2個元素出隊后隊列 的狀態圖。注：假設 MAXSIZE=6 front=5 ,完成本題要求的圖示。若 erar=5 , 情況如何？(2)試畫出有2個元素C、D的鏈表隊列圖，及將這2個元素出隊后鏈表 隊列的狀態圖。9 .對于一個具有m個單元的循環隊列，寫出求隊列中元素個數的公式。10 .對于一個具有n個單元(n>>2)的循環隊列，若從進入第一個元素開始，每隔 t1 個時間單位進入下一個元素，同時從進入第一個元素開始，每隔 t

36、2(t2>t1)個時間單位處理完一個元素并令其出隊，試編寫一個算法，求出在第幾個元素進隊時將發生溢出。11 . 假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點(注意不設頭指針)，試編寫出相應的置空隊列，入隊列和出隊列的算法。12 . 二項式 (a + b) i 展開后，其系數構成楊輝三角形。利用隊列寫出打印楊輝三角形前n 行的程序。即逐行打印二項展開式(a + b) i 的系數。圖3.17是指數 i 從 1 到 6 的 (a + b) i 的展開式系數所構成的楊輝三角形。討論小課堂4重點掌握串的匹配運算及應用，可結合實際的題目進行討論來加深對串的一些運算的理解和掌握。

37、1 . 輸入一個字符串，內有數字和非數字字符，如： ak123x456 17960?302gef4563，將其中連續的數字作為一個整體，依次存放到一數組a中，例如 123放入a0 ,456放入a 1, 。編程統計其共有多少個整數，并輸出這些數?！緟⒖即鸢浮吭谝粋€字符串內，統計含多少整數的問題，核心是如何將數從字符串中分離出來。從左到右掃描字符串，初次碰到數字字符時，作為一個整數的開始。 然后進行拼數，即將連續出現的數字字符拼成一個整數，直到碰到非數字字符為止，一個整數拼完，存入數組，再準備下一整數，如此下去，直至整個字符串掃描到結束。算法如下：int CountInt()/* 從鍵盤輸入字符串

38、，連續的數字字符算作一個整數，統計其中整數的個數。*/int i=0, a口； /*整數存儲到數組a, i記整數個數*/char ch;scanf( d ,&ch/*從左到右讀入字符用*/while( ch!= #) /* #是字符串結束標記 */if( ( ch) >=48 && (ch)<=57 ) /* 是數字字符*/num= 0 ;/*數初始化*/while( ( ch) >=48 && (ch)<=57 && ch!= #) /* 拼數 */num=num* 10+ 'ch-'。'

39、；scanf( %d ,&ch)ai=num； i+；if (ch!= '#'scanf( " %d ,&chy*若拼數中輸入了 #'則不再輸入*/ while (ch!=拼 /* 結束*/Printf( 共有 ” %d” ,I, 個整數，它們是： ”) ；for (j= 0 ; j<i; j+)printf("%d 司;”“)if( ( j+1)10=0) printf( n“” ); */每 10個數輸出在一行上*/ /*算法結束*/假定字符串中白數均不超過 32767,否則，需用長整型數組及變量。2 .以順序存儲結構表示用

40、，設計算法。求用 S中出現的第一個最長重復子用及其位置并分析算法的時間復雜度。例如：若S= "abceebccadddddaaad。!”則最長重復子用為“ddddd'位置是9?！緟⒖即鸢浮吭O以字符數組s表示申，重復子用的含義是由一個或多個連續相等 的字符組成的子用，其長度用max表示，初始長度為0,將每個局部重復子用的 長度與max相比，若比max大，則需要更新max,并用index記住其開始位置。 算法如下：int LongestString(char s, int n)/*用用一維數組s存儲，長度為n,本算法求最長重復子用，返回其長度。*/int index=0,max=

41、0; /*index記最長的用在s用中的開始位置，max記其長 度*/int length=1,i=0,start=0; /*length記局部重復子用長度，i為字符數組下標 */while(i<n-1)if(si=si+1) i+; length+;else/*上一個重復子用結束*/if(max<length) max=length; index=start; /*當前重復子用長度大，則更新max*/i+;start=i;length=1;/*初始化下一重復子用的起始位置和長度*/Printf(最長重復子用的長度為：d "max;在用中白位置：d" ；inde

42、x);return (max);/*算法結束*/算法中用i<n-1來控制循環次數，因C數組下標從0開始，故長度為n的用， 其最后一個字符下標是n-1,當i最大為n-2時，條件語句中si+1正好是sn-1, 即最后一個字符。子用長度的初值數為 1,表示一個字符自然等于其身。算法的時間復雜度為O(n),每個字符與其后繼比較一次。習題4習題41.填空(1)在計算機軟件系統中，有兩種處理字符串長度的方法：一種是采用 顯式, 第二種是隱式 。(2)一個字符串相等的充要條件是長度 和對應字符都相(3)串是指 有限個字符組成的序列;空串是指 長度 的串;空格用是指一個或多個空格組成的由。(4)設 s=

43、 UAM A-TEACHSR,其長度是 _14。(5)若n為主用長，m為子用長，則用的卡典匹配算法最壞的情況下需要比 較字符的總次數為。(m*n)。2 .空用和空格用有何區別？字符串中的空格符有何意義？空用在用的處理中有 何作用？答：空用時長度為0的字符用；空格用是一個或多個字符組成的字符串。字符串中的空格符充當界符的作用。空用在用的處理中可作為任意用的子用。3 .設計一算法，將兩個字符串連接起來，要求不能利用 strcat ()函數。答：Typedef structchar *ch; /* 用數組 */ int length; /* 用長*/ HString;int StrConcat(HS

44、tring *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放入臨時申 temp 中*/free(S->ch);S->ch=(char*)malloc(S->length+T.length); /* 為 S 分配新的空間 */for(int i=0;i< S->length;i+)S->chi=tempi;for(int j=0

45、;j< T.length;j+)S->chi+j=T.chj; return(1);.4 .設計一算法，將字符串S中從pos位置開始共num個字符構成的子用用字符 用X來代替(X的長度可以不同于num)。Typedef structchar *ch; /* 用數組 */ int length;/* 用長*/HString;void Strrepl (HString *S, int pos, int num,HString X) if (pos < 1 | pos > S->length+1) printf("n位置錯誤!)return;/*位置不合法*/

46、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 ;/*為S重新分配用值存儲空間*/for ( i=0, k=0; i<p

47、os-1; i+)S->chk+ = S1i;j = 0;while (j<X.length)S->chk+ = X.chj+;while ( i<S->length)S->chk+ = S1i+;S->length+=T.length; /* if */ /* Strrepl*/*保留插入位置之前的子用*/*替換X*/*復制替換部分后的子用*/*置用S的長度*/5 .試設計一個算法，測試一個用t的值是否為回文(即從左面讀起與從右面讀 起內容一樣)。答：int isSym(char *str,int length) /*判斷一個字符串是否為回文,0是，

48、-1不是for(int i=0;i<length/2;i+) if(stri != strlength-i-1)return -1;return 0;6 .編寫一個算法，統計在輸入字符串中各個不同字符出現的頻度 答：#include <stdio.h>int main()int charcount256;int i;char ch;/*初始化*/for(i=0;i<256;i+)charcounti =0;while(ch = getchar() !='n')charcount (int)ch +;/*輸出*/for(i=0;i<256;i+)if

49、( charcounti) printf("%c - %dn", i, charcounti);return 0;7 .設s=" 00001000010100001 "，t= "說01在樸素模式匹配算法中的匹配過 程。第一趟匹配(1)第二趟匹配(2)I i=3 000010000101000010 0 0 11j=3|i=500001000010100001 0 0 0 1j=48.設計一個算法Replace(w,x),將當前字符串所有子用w用另一個字符串x來替 換。字符串w和x的長度可以不同。答：參考習題4和匹配算法。討論小課堂5參考內容1

50、.設mXn階稀疏矩陣A有t個非零元素，其三元組表表示為 LTMA1.(t+1),1.3,試問：非零元素的個數t達到什么程度時用LTMA表示A 才有意義？【參考答案】：稀疏夕!陣A有t個非零元素，加上行數 mu、列數nu和非零元素 個數tu,共占用三元組表LTMA的3(t+1)個存儲單元，用二維數組存儲時占用 m Xn個單元，只有當3(t+1)< mXn時，用LTMA表示A才有意義。解不等式得 t< m x n/3-1。2 .特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機存取的功能？為什么？ 【參考答案】：特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規律。 因此，可以對非零元素分配

51、單元(這里，對值相同元素只分配一個單元)，將非零 元素存儲在向量中，元素的下標i和j和該元素在向量中的下標有一定規律，可 以用簡單公式表示，仍具有隨機存取功能；而稀疏矩陣是指非零元素和矩陣容量 相比很小(t<<mxn),且分布沒有規律。用十字鏈表作存儲結構自然失去了隨機 存取的功能。即使用三元組表的順序存儲結構，存取下標為i和j的元素時，要掃描三元組表，下標不同的元素，存取時間也不同。最好情況下存取時間為 O(1), 最差情況下是O(n),因此也失去了隨機存取功能。3 .已知A為稀疏矩陣，試從空間和時間角度比較采用二維數組和三元組順序表 兩種不同的存儲結構，完成求矩陣元素之和，并分

52、析運算的優缺點?！緟⒖即鸢浮浚涸O稀疏矩陣A為m行n歹I，如果采用二維數組常規存儲，則其空 間復雜度為O(mxn)。因為要將所有的旬鎮元素累加起來， 需要使用一個兩層的 嵌套循環結構，所以其時間復雜度為O(mxn)。如果采用三元組順序表進行壓縮 存儲，假設稀疏矩陣中有t個非零元素，則其空間復雜度為 O(t),將所有的矩陣 元素累加起來只需要將三元組順序表掃描一遍， 其時間復雜度也為O(t)。當t<< m x n時，采用三元組順序表存儲可以獲得較好的時間及空間性能。4 .廣義表和線性表的區別與聯系?！緟⒖即鸢浮浚簭V義表是線性表的推廣，線性表是廣義表的特例。當廣義表中的 元素都是原子時，

53、即為線性表。習題51 .設矩陣A為2 0 0 40 0 3 0|0 3 0 0# 0 0 0_(1)若將A看作對稱矩陣，畫出對其進行壓縮存儲的存儲表示，并討論如何存取A中元素aj(0&i, j<4)。(2)若將A看作稀疏矩陣，畫出A的十字鏈表存儲結構?！緟⒖即鸢浮浚合聵?12345678g102000304000123412342 .已知廣義表A=(a), (b), c, (a), (d, e),解答下歹問題:(1)寫出表的長度和深度。(2)用求頭部和尾部的方式求出e?！緟⒖即鸢浮?1)表的長度為5，深度為4。(2)e=head(tail(head(head(head(tail(

54、tail(tail(tail(A)3 .設廣義表為 A=(a,b,(c,d),(e,(f,g),(h,j),則式 head(tail(head(tail(tail(A) 的值為什么？(華北計算機技術研究所2001 年考研題 )【參考答案】： (g)4 .設有5對角矩陣，A=(aij)20x20,按特殊矩陣壓縮存儲的方式將其5條對角線上的元素存于數組B-10:m中，計算元素A15,15的存儲位置。(東北大學1998年考研 題)【參考答案】：如果以行序為主，A15,15為第3+4+5X 12+3=70個，存儲位置為 70-10-1=59;如果按對角線順序， A15,15為第18+19+15=52個

55、，存儲位置為 52-10-1=41。5,若矩陣Amxn中的某個元素aij是第i行中的最小值，同時又是第j歹I中的最大值，則稱此元素為該矩陣中的一個馬鞍點。假設以二維數組存儲矩陣Amxn,試編寫求出矩陣中所有馬鞍點的算法，并分析所寫算法在最壞情況下的時間復雜度?！緟⒖即鸢浮浚涸诰仃囍兄鹦袑ふ以撔兄械淖钚≈?，然后對其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在的行號和列號輸出。void Andian(int A, int m, int n)/求解矩陣A 的所有馬鞍點 for(i=0; i<n; i+) d=Ai0;k=0;for(j=1; j<m; j+)if(Aij<d)d=Aij;k=j;for(j=0;j<n;j+)if(Ajk>d) break;if(j=n) cout<<” output Andian” <<I<<