1、 數據結構（2）部分六、串及其應用簡單行編輯程序問題描述：文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數據空間（內存）的作法既不經濟，也不總能實現。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內存，稱為活區。試按照這種方法實現一個簡單的行編輯程序。設文件每行不超過320個字符，很少超過80個字符。基本要求：實現以下4條基本編輯命令：（1）行插入。格式：i行號回車文本。回車后將文本插入活區中第行號行之后。（2）行刪除。格式：d行號1空格行號2

2、回車。刪除活區中第行號1行（到第行號2行）。例如：“d10/”和“d1014/”。（3）活區切換。格式：n回車。將活區寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區。（4）活區顯示。格式：p回車。逐頁地（每頁20行）顯示活區內容，每顯示一頁之后請用戶決定是否繼續顯示以后各頁（如果存在）。印出的每一行要前置行號和一個空格符，行號固定占4位，增量為1。各條命令中的行號均須在活區中各行行號范圍之內，只有插入命令的行號可以等于活區第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數非法。測試數據：自行設定，注意測試將活區刪空等特殊情況。實現提示：（1）設活區的大小用行數ActiveMaxL

3、en（可設為100）來描述。考慮到文本文件行長通常為正態分布，且峰值在60到70之間，用320XActiveMaxLen大小的字符數組實現存儲將造成大量浪費。可以以標準行塊為單位為各行分配存儲，每個標準行塊可含81個字符。這些行塊可以組成一個數組，也可以利用動態鏈表連接起來。一行文字可能占多個行塊。行尾可用一個特殊的ASCII字符（如（012）8）標識。此外，還應記住活區起始行號。行插入將引起隨后各行行號的順序下推。（2）初始化函數包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過ActiveMaxLen-x的值可以自定，例

4、如20。（3）在執行行插入命令的過程中，每接收到一行時都要檢查活區大小是否已達ActiveMaxLen.如果是，則為了在插入這一行之后仍保持活區大小不超過ActiveMaxLen,應將插入點之前的活區部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將新插入的這一行輸出。（4）若輸入文件尚未讀完，活區切換命令可將原活區中最后幾行留在活區頂部，以保持閱讀連續性；否則，它意味著結束編輯或開始編輯另一個文件。（5）可令前三條命令執行后自動調用活區顯示。七、圖及其應用1.最小生成樹問題問題描述：若要在n個城市之間建設通信網絡，只需要架設n-1條線路即可。如何以最低的經濟代價建設這個通信網，是一

5、個網的最小生成樹問題。基本要求：（1）利用普里姆或克魯期卡爾算法求網的最小生成樹。（2）以文本形式輸出生成樹中各條邊以及他們的權值。測試數據：按教材中的例子，自己相應設計。實現提示：通信線路一旦建立，必然是雙向的。因此，構造最小生成樹的網一定是無向網。設圖的頂點數不超過30個，并為簡單起見，網中邊的權值設成小于100的整數，可利用C語言提供的隨機數函數產生。圖的存儲結構的選取應和所作操作相適應。為了便于選擇權值最小的邊，此題的存儲結構既不選用鄰接矩陣的數組表示法，也不選用鄰接表，而是以存儲邊（帶權）的數組表示圖。2圖遍歷的演示問題描述：很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。試寫一個

6、程序，演示在連通的無向圖上訪問全部結點的操作。基本要求：以鄰接表為存儲結構，實現連通無向圖的深度優先和廣度優先遍歷。以用戶指定的結點為起點，分別輸出每種遍歷下的結點訪問序列和相應生成樹的邊集。測試數據：按教科書上的例子改編。實現提示：設圖的結點不超過30個，每個結點用一個編號表示（如果一個圖有n個結點，則它們的編號分別為1,2,，n）。通過輸入圖的全部邊輸入一個圖，每個邊為一個數對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點順序不能顛倒。選作內容：（1）借助于棧類型（自己定義和實現），用非遞歸算法實現深度優先遍歷。（2）以鄰接表為存儲結構，建立深度優先生成樹和廣度優先生成樹

7、，再按凹入表或樹形打印生成樹。（3）因圖的路徑遍歷要比結點編歷具有更為廣泛的應用。再寫一個路徑遍歷算法，求出從某給定點到另一點且中途不過某特定點的所有簡單路徑及其里程。 S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base)exit(1);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;charpop(SqStack&S,char&e)if(S.top=S.base)returnfalse;e=*-S.top

8、;returne;voidClearStack(SqStack&S)S.top=S.base;voidDestroyStack(SqStack&S)free(S.base);S.top=S.base;boolStackEmpty(SqStack&S)if(S.top=S.base)returntrue;returnfalse;/*voidPrintStack(SqStack&S)chare;while(!StackEmpty(S)pop(S,e);printf(%d,e);*/voidmain()charch,e;SqStackS,D;InitStack(S);InitStack(D);ch=getchar();while(ch!=EOF)while(ch!=EOF&ch!=n)switch(ch)case#:pop(S,e);break;case:ClearStack(S);break;default:push(S,ch);break;ch=getchar();while(