數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告雙鏈表創(chuàng)建與演示設(shè)計

1、課 程 設(shè) 計 報 告 課程名稱課程名稱 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 課題名稱課題名稱 雙鏈表創(chuàng)建演示雙鏈表創(chuàng)建演示 專專 業(yè)業(yè) 計算機(jī)科學(xué)與技術(shù)計算機(jī)科學(xué)與技術(shù) 班班 級級 計算機(jī)計算機(jī) 0703 學(xué)學(xué) 號號 姓姓 名名 指導(dǎo)教師指導(dǎo)教師 2009 年年 11 月月 7 日日 課 程 設(shè) 計 任 務(wù) 書 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 雙鏈表創(chuàng)建演示 專業(yè)班級 學(xué)生姓名 張 理 學(xué) 號 指導(dǎo)老師 審 批 1 1 設(shè)設(shè)計計內(nèi)內(nèi)容容與與設(shè)設(shè)計計要要求求 1.11.1 設(shè)計內(nèi)容設(shè)計內(nèi)容 1.1.11.1.1 算術(shù)算術(shù) 2424 游戲演示游戲演示 由系統(tǒng)隨機(jī)生成 4 張撲克牌，用戶利用撲克牌的數(shù)字及運算符號“+”

2、 、 “” 、 “*” 、 “/”及括號“（”和“） ”從鍵盤上輸入一個計算表達(dá)式，系統(tǒng) 運行后得出計算結(jié)果，如果結(jié)果等于 24，則顯示“congratulation!” ，否則 顯示“incorrect!” 設(shè)計思路：從鍵盤輸入中綴表達(dá)式，然后將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá) 式，利用后綴表達(dá)式求值。 1.1.21.1.2 迷宮探索迷宮探索 隨機(jī)生成一個迷宮圖，迷宮大小為 n*n，n 預(yù)定義為常數(shù)，修改 n 的值可 以改變迷宮的大小。用白色表示可走的路，藍(lán)色表示墻壁不可以通過。系統(tǒng) 設(shè)計兩種運行方式：一種是系統(tǒng)自動探索（用遞歸方法實現(xiàn)） ；另一種是由人 工操作探索通路。 設(shè)計思路：程序首先要考慮迷

3、宮的表示，這是一個二維關(guān)系圖，所以可 選擇二維數(shù)組來存儲。數(shù)組元素只有兩種值 0 和 1，分別代表通路和墻壁。圖 形的顯示可以根據(jù)數(shù)組元素的值來確定。如果是人工探索，則依據(jù)按鍵來確 定探索物的位置坐標(biāo)，利用循環(huán)語句實現(xiàn)。如果是系統(tǒng)自動探索，可采用遞 歸算法實現(xiàn)。 1.1.31.1.3 二叉樹遍歷演示二叉樹遍歷演示 演示遍歷二叉樹的過程，所以首先建立二叉樹，并用圖形顯示出樹的形 狀。建立的過程是采用前序便利的方法來創(chuàng)建，設(shè)計兩種生成樹的方式：一 種是系統(tǒng)隨機(jī)生成，另一種是人工輸入?？紤]到屏幕界面的有限性，限定二 叉樹不超過 5 層，最多 26 個字符，輸入字符小數(shù)點“.”代表 null。初始樹

4、為某種顏色的結(jié)點，三種情況的遍歷采用填充另外一種醒目的顏色，來表示 當(dāng)前遍歷的結(jié)點，同時顯示該結(jié)點的訪問序號。同時在遍歷的過程中在遍歷 圖形的下方顯示出遍歷序列。 1.1.41.1.4 數(shù)組應(yīng)用數(shù)組應(yīng)用 按照行優(yōu)先順序?qū)⒂脩綦S機(jī)輸入的數(shù)據(jù)建成 2 維數(shù)組并以圖形方式逐步 顯示出來，然后再按照列優(yōu)先順序以圖形方式逐步輸出相應(yīng)數(shù)組。 1.1.51.1.5 拓?fù)渑判蜓菔就負(fù)渑判蜓菔?演示拓?fù)渑判虻倪^程。按照有向圖給出的次序關(guān)系，將圖中頂點排成一 個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意 的次序關(guān)系。要求每輸出一個頂點后就演示從圖中刪去此頂點以及所有以它 為尾的弧。 1.1.

5、61.1.6 圖的遍歷圖的遍歷 演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。 要求圖的結(jié)點數(shù)不能少于 6 個?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動 輸入圖。報告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一 步改進(jìn)圖的效果。 1.1.71.1.7 八皇后問題演示八皇后問題演示 在 8*8 的棋盤上擺放 8 個皇后，使他們不在同一條對角線上和不在一行 和列上。 解決 8 皇后時，在安放第 i 行皇后時，需要在列的方向從 1 到 n 試探(j =1, n)：首先在第 j 列安放一個皇后，如果在列、主對角線、次 對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第 j 列安放的皇

6、后。如果沒有 出現(xiàn)攻擊，在第 j 列安放的皇后不動，遞歸安放第 i+1 行皇后。 該課題要求 求解可能的方案及方案數(shù)并逐步演示擺放皇后的過程。 1.1.81.1.8 雙鏈表創(chuàng)建演示雙鏈表創(chuàng)建演示 建立一個遞增有序遞增有序的雙鏈表。功能是隨機(jī)生成 8 個結(jié)點數(shù)據(jù)，每生成一 個結(jié)點則申請空間得到一個指針，將數(shù)據(jù)存放到指針?biāo)傅臄?shù)據(jù)域中，然后 將結(jié)點插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點的插入 位置，第二不演示插入過程中指針的變化，第三步顯示插入后的鏈表結(jié)果。 1.1.91.1.9 公園導(dǎo)游圖公園導(dǎo)游圖 給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點到另一 景點的最短路徑。

7、游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重 復(fù)地游覽各景點，最后回到出口（出口就在入口旁邊） 。要求用圖示展示最佳 路徑。 1.21.2 選題方案：選題方案： 所選題目根據(jù)學(xué)號確定，學(xué)號模 9 加 1，即（學(xué)號%9+1） 。如你的學(xué)號為 12，則所選題目號為：12%9+1（題目 4） 。注意，所有的課題都要求用圖形 方式演示步驟和結(jié)果。有興趣的同學(xué)可以自己針對數(shù)據(jù)結(jié)構(gòu)課程中所講算法 來設(shè)計一個演示過程的算法，但要預(yù)先告知老師，經(jīng)過審批，方可確定課題。 1.31.3 設(shè)計要求：設(shè)計要求： 1.3.11.3.1 課程設(shè)計報告規(guī)范課程設(shè)計報告規(guī)范 （1）需求分析 a. 程序的功能。 b. 輸

8、入輸出的要求。 （2）概要設(shè)計 a. 程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每 個模塊的功能。 b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什 么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。 （3）詳細(xì)設(shè)計 a. 采用 c 語言定義相關(guān)的數(shù)據(jù)類型。 b. 寫出各模塊的類 c 碼算法。 c. 畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。 （4）調(diào)試分析以及設(shè)計體會 a. 測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié) 果和含有錯誤的輸入及輸出結(jié)果。 b. 程序調(diào)試中遇到的問題以及解決問題的方法。 c. 課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。 （5）使用說明

9、 用戶使用手冊：說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。 （6）書寫格式 a. 設(shè)計報告要求用 a4 紙打印成冊： b. 一級標(biāo)題用 3 號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距 為 22。 （7）附錄 a.源程序清單（帶注釋） 1.3.21.3.2 考核方式考核方式 指導(dǎo)老師負(fù)責(zé)驗收程序的運行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實際動手能力、創(chuàng) 新精神和設(shè)計報告等進(jìn)行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級 給出每位同學(xué)的課程設(shè)計成績。具體考核標(biāo)準(zhǔn)包含以下幾個部分： （1）平時出勤 （占 10%） （2）系統(tǒng)需求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否

10、（占 10%） （3）程序能否完整、準(zhǔn)確地運行，個人能否獨立、熟練地調(diào)試程序（占 40%） （4）設(shè)計報告（占 30%） 注意：不得抄襲他人的報告（或給他人抄襲） ，一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?（5）獨立完成情況（占 10%） 。 1.3.31.3.3 課程驗收要求課程驗收要求 （1）運行所設(shè)計的系統(tǒng)。 （2）回答有關(guān)問題。 （3）提交課程設(shè)計報告。 （4）提交軟盤（源程序、設(shè)計報告文檔） 。 （5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。 2 2 進(jìn)度安排進(jìn)度安排 2.12.1 計算機(jī)計算機(jī) 0701/07020701/0702 班：班： 第 7 周：星期一 8：0012：00 上課

11、 星期一 14：0016：00 上課 星期五 18：0022：00 上機(jī) 第 8 周：星期六 14：0018：00 上機(jī) 星期日 8：0012：00 上機(jī) 星期日 18：0022：00 上課 第 9 周：星期六 8：0012：00 上機(jī) 星期日 14：0018：00 上機(jī) 2.22.2 計算機(jī)計算機(jī) 07030703 班：班： 第 7 周：星期一 8：0012：00 上課 星期一 14：0016：00 上課 星期六 8：0012：00 上機(jī) 星期日 14：0018：00 上機(jī) 第 8 周：星期六 8：0012：00 上機(jī) 星期日 14：0018：00 上機(jī) 第 9 周：星期六 14：0018：

12、00 上機(jī) 星期日 18：0022：00 上機(jī) 目目 錄錄 一、一、需求分析需求分析 .- 1 - 1.1.程序功能說明程序功能說明 .- 1 - 2.2.輸入輸出輸入輸出 .- 1 - 二、二、概要設(shè)計概要設(shè)計 .- 2 - 1.1.程序模塊程序模塊 本程序由于僅需實現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主本程序由于僅需實現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主 要由三部分模塊函數(shù)組成，即構(gòu)建生成雙鏈表，演示指針變化，結(jié)果輸出。要由三部分模塊函數(shù)組成，即構(gòu)建生成雙鏈表，演示指針變化，結(jié)果輸出。.- 2 - 2.2.課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu) 本課題所

13、用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表，所用到的本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表，所用到的 數(shù)據(jù)結(jié)構(gòu)如下數(shù)據(jù)結(jié)構(gòu)如下.- 2 - 2.1 雙鏈表存儲結(jié)構(gòu).- 2 - 2.2 雙鏈表結(jié)點的插入.- 2 - 2.3 雙鏈表結(jié)點的刪除.- 3 - 三、三、詳細(xì)設(shè)計詳細(xì)設(shè)計 .- 4 - 1.采用采用 c 語言定義相關(guān)的數(shù)據(jù)類型語言定義相關(guān)的數(shù)據(jù)類型.- 4 - 1.1 雙鏈表結(jié)點定義.- 4 - 2.寫出各模塊的類寫出各模塊的類 c 碼算法碼算法.- 4 - 2.1 建立并插入雙鏈表的類 c 算法.- 4 - 2.2 指針變化演示類 c 算法.- 5 - 3.3 輸出已排序雙鏈表類 c 代碼.- 5 -

14、3.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。.- 6 - 四、四、調(diào)試分析以及設(shè)計體會調(diào)試分析以及設(shè)計體會.- 6 - 1程序調(diào)試中遇到的問題以及解決問題的方法。程序調(diào)試中遇到的問題以及解決問題的方法。.- 6 - 2課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。.- 7 - 五、五、使用說明使用說明 .- 7 - 六、六、附錄附錄.- 10 - 源程序清單源程序清單.- 10 - 參考文獻(xiàn)參考文獻(xiàn) .- 15 - 一、一、 需求分析需求分析 1.1. 程序功能說明 鏈表是線性表的鏈?zhǔn)奖硎?，由于它不要求邏輯上相鄰的元素在物理位置上?/p>

15、表是線性表的鏈?zhǔn)奖硎?，由于它不要求邏輯上相鄰的元素在物理位置?也相鄰，所以它沒有順序存儲結(jié)構(gòu)在做插入刪除操作時需要移動大量元素也相鄰，所以它沒有順序存儲結(jié)構(gòu)在做插入刪除操作時需要移動大量元素 的弱點。雙鏈表的結(jié)點中有兩個指針域，一個指向直接后繼，一個指向直的弱點。雙鏈表的結(jié)點中有兩個指針域，一個指向直接后繼，一個指向直 接前驅(qū)。所以雙鏈表創(chuàng)建演示就是建立一個遞增有序的雙鏈表。程序功能接前驅(qū)。所以雙鏈表創(chuàng)建演示就是建立一個遞增有序的雙鏈表。程序功能 是首先由程序隨機(jī)生成是首先由程序隨機(jī)生成 8 8 個結(jié)點數(shù)據(jù)，生成一個結(jié)點后則申請空間得到一個結(jié)點數(shù)據(jù)，生成一個結(jié)點后則申請空間得到一 個指針，將

16、數(shù)據(jù)存放到指針?biāo)傅臄?shù)據(jù)域中，再生成一個結(jié)點后先判斷此個指針，將數(shù)據(jù)存放到指針?biāo)傅臄?shù)據(jù)域中，再生成一個結(jié)點后先判斷此 結(jié)點的數(shù)值和已生成結(jié)點的大小，由于要求建立遞增有序的雙鏈表，所以結(jié)點的數(shù)值和已生成結(jié)點的大小，由于要求建立遞增有序的雙鏈表，所以 把結(jié)點插入到比其大的所有結(jié)點中的最小結(jié)點之前和比其小的所有結(jié)點中把結(jié)點插入到比其大的所有結(jié)點中的最小結(jié)點之前和比其小的所有結(jié)點中 最大結(jié)點的之后，并在插入過程中顯示指針變化，最后輸出排好序的雙鏈最大結(jié)點的之后，并在插入過程中顯示指針變化，最后輸出排好序的雙鏈 表。表。 2.2. 輸入輸出 由于本程序為演示程序，結(jié)點也由程序隨機(jī)生成，所以在輸入方面不

17、需實由于本程序為演示程序，結(jié)點也由程序隨機(jī)生成，所以在輸入方面不需實 現(xiàn)功能，只需用戶控制程序操作。輸出方面主要是在屏幕顯示插入結(jié)點的現(xiàn)功能，只需用戶控制程序操作。輸出方面主要是在屏幕顯示插入結(jié)點的 結(jié)果和顯示指針變化的功能，具體輸出過程為輸出首先生成的結(jié)點，然后結(jié)果和顯示指針變化的功能，具體輸出過程為輸出首先生成的結(jié)點，然后 顯示對已生成結(jié)點的排序，再演示出指針變化，指針以彎折的箭頭表示，顯示對已生成結(jié)點的排序，再演示出指針變化，指針以彎折的箭頭表示， 最后輸出排序后的鏈表，直箭頭表示雙鏈表的前驅(qū)后驅(qū)。最后輸出排序后的鏈表，直箭頭表示雙鏈表的前驅(qū)后驅(qū)。 二、 概要設(shè)計計 1.1. 程序模塊

18、本程序由于僅需實現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主要由本程序由于僅需實現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主要由 三部分模塊函數(shù)組成，即構(gòu)建生成雙鏈表，演示指針變化，結(jié)果輸出。三部分模塊函數(shù)組成，即構(gòu)建生成雙鏈表，演示指針變化，結(jié)果輸出。 程序結(jié)構(gòu)圖： 2.2. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu) 本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表，所用到的數(shù)據(jù)結(jié)構(gòu)如下本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表，所用到的數(shù)據(jù)結(jié)構(gòu)如下 2.12.1 雙鏈表存儲結(jié)構(gòu)雙鏈表存儲結(jié)構(gòu) typedef struct dulnode elemtype data; struct dulnode *prior; st

19、ruct dulnode *next; dulnode, *dulinklist; 2.22.2 雙鏈表結(jié)點的插入雙鏈表結(jié)點的插入 status listinsert_dul(dulinklist if(!(s=(dulinklist)malloc(sizeof(dulnode) return error; s-data=e; 雙鏈表創(chuàng)建演示主程 序 雙鏈表創(chuàng)建指針變化演示結(jié)果輸出 s-prior=p-prior; p-piror-next=s; s-next=p; p-prior=s; return ok; 2.32.3 雙鏈表結(jié)點的刪除雙鏈表結(jié)點的刪除 status listdelete_

20、dul(dulinklist e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return ok; 三、三、 詳細(xì)設(shè)計詳細(xì)設(shè)計 1. 采用 c 語言定義相關(guān)的數(shù)據(jù)類型 1.11.1 雙鏈表結(jié)點定義雙鏈表結(jié)點定義 typedef struct link int data; struct link *right; struct link *left; int num; linkx,*linky; 2. 寫出各模塊的類 c 碼算法 2.12.1 建立并插入雙鏈表建立并插入雙鏈表的類的類 c c 算法算法 void initl

21、ist(void) randomize(); 將產(chǎn)生的隨機(jī)數(shù)字轉(zhuǎn)換成字符串并輸出； sleep(1); prlink(head,n); /*顯示只有頭節(jié)點的鏈表*/ n+; while(n!=8) s-data=random(100); if(s-datadata) /*小于頭結(jié)點，插在頭*/ q=head-right; q-num+; /*節(jié)點數(shù)加 1；*/ 顯示具體插入過程； else /其他情況/ if(p=null) /*這個數(shù)是當(dāng)前最大的數(shù)，插在尾部*/ 顯示插入的具體過程； else /*隨即產(chǎn)生的數(shù)排在表中*/ while(s!=null) s-num+;s=s-right; 顯

22、示插入的具體過程； 2.22.2指針變化演示類指針變化演示類 c c 算法算法 void drawchange(int data,int i,int n) 判斷插入結(jié)點的位置： if(i!=-1) 當(dāng)前指針是頭指針，畫前驅(qū)、后繼指針； if(i!=n-1) 當(dāng)前指針是尾指針，畫前驅(qū)、后驅(qū)指針； if(i!=n-1 3.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。 進(jìn)入 y y y n 具體 inintlist(void)函數(shù)的流程圖： 調(diào)用 prlink(head,n) closr(void) 調(diào)用 drawchange(s-data,q-num,n) 調(diào)用 drawchange(s-data,

23、n-1,n) 調(diào)用 drawchange(s-data,t,n) 調(diào)用 prink(p ,n) 調(diào)用 inintlist(void) s- datadata p=null 四、四、 調(diào)試分析以及設(shè)計體會調(diào)試分析以及設(shè)計體會 1程序調(diào)試中遇到的問題以及解決問題的方法。 主要是在結(jié)點插入判斷方面有難度，一開始不能準(zhǔn)確的進(jìn)行結(jié)點的判斷和插 入，然后就是插入結(jié)點的過程中位置不對，不是遞增有序的，后面在網(wǎng)上找 到了一段演示代碼，通過研究這段代碼解決了這個問題。還有就是在顯示指 針變化方面有問題，經(jīng)過查詢資料，解決結(jié)點插入方面的問題，用畫箭頭的 方式來表現(xiàn)指針的變化。 2課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。

24、在進(jìn)行本次課程設(shè)計的實驗操作中，由于自己的基礎(chǔ)知識不是很好，出現(xiàn)了一 些問題：在編程方面不熟，所以寫出的代碼總是出錯；數(shù)據(jù)結(jié)構(gòu)課程以前也沒 有好好學(xué)過，造成在構(gòu)建程序數(shù)據(jù)結(jié)構(gòu)時出現(xiàn)由于概念模糊而寫錯功能的問題。 但是在老師和同學(xué)們的幫助下，再通過查閱資料，最后終于寫出了可以正確運 行結(jié)果的代碼，所以要感謝給我?guī)椭睦蠋熀屯瑢W(xué)。以前用 c 編程，只是注重 如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術(shù)，只是憑單純的意 識和簡單的語句來堆砌出一段程序。感覺有點像張飛打仗，有勇無謀，只要能 完成任務(wù)就行。但現(xiàn)在編程感覺完全不同了。在編寫一個程序之前，自己能夠 綜合考慮各種因素，首先選取自己需要

25、的數(shù)據(jù)結(jié)構(gòu)，是樹還是圖或是別的什么？ 然后選定一種或幾種存儲結(jié)構(gòu)來具體的決定后面的函數(shù)的主要風(fēng)格。最后在編 寫每一個函數(shù)之前，可以仔細(xì)斟酌比對，挑選出最適合當(dāng)前狀況的算法。這樣， 即使在完整的程序還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。這樣 無形中就提高了自己編寫的程序的質(zhì)量。 通過這次課程設(shè)計，使我意識到作為一個計算機(jī)系的學(xué)生，正確掌握一門程序 語言和數(shù)據(jù)結(jié)構(gòu)的重要性，想要在程序設(shè)計上面作出成績，必須要有扎實的編 程語言基礎(chǔ)和良好的數(shù)據(jù)結(jié)構(gòu)算法知識，我決定在余下的在校時間里，認(rèn)認(rèn)真 真學(xué)一門語言，并去詳細(xì)了解程序的算法設(shè)計。 五、五、 使用說明使用說明 本程序是演示程序，在運行后按任

26、意鍵即執(zhí)行演示過程，可直觀的看到程序運 行時雙鏈表指針的變化情況，為方便觀察結(jié)果，在程序運行的時候，按一下執(zhí) 行一步，也可以通過按 q 鍵來退出程序，也可以在等待所有過程結(jié)束后再退出。 1進(jìn)入程序后界面： 2隨機(jī)產(chǎn)生結(jié)點，圖中已產(chǎn)生 2 個結(jié)點，由于 57 大于 1，所以沒有右指 針 3指針變化情況 4完成一個鏈表創(chuàng)建，下一結(jié)點插入中 5所有步驟完成后程序顯示界面，可清晰看到排序后的雙鏈表結(jié)果 六、六、 附錄附錄 源程序清單 #include stdlib.h #include graphics.h typedef struct link/*雙鏈表結(jié)點定義*/ int data; struct

27、 link *right; struct link *left; int num;/*給鏈表加序號,為了演示時計算正確位置*/ linkx,*linky; void init(void);/*圖形驅(qū)動*/ void close(void);/*圖形關(guān)閉*/ void initlist(void);/*建立雙鏈表,邊建立邊插入*/ void prlink(linky p,int n);/*每次插入后輸出鏈表*/ void drawchange(int data,int i,int n);/*畫鏈表插入的指針變化*/ void main(void) init();/*圖形關(guān)閉*/ initlist

28、();/*建立鏈表*/ close();/*圖形關(guān)閉*/ exit(0); void initlist(void) /*建立雙向鏈表,邊建立邊插入*/ linky head,p,q,s; int n=0; char str5; randomize();/*隨機(jī)數(shù)發(fā)生機(jī)*/ setcolor(blue); outtextxy(200,20,perss any key to start); setcolor(red); outtextxy(400,30,press q to quit); getch(); head=s=(linky)malloc(sizeof(linkx); s-data=ran

29、dom(100);/*隨機(jī)生成 100 以內(nèi)的數(shù)字*/ s-num=n; sprintf(str,%d,s-data);/*將數(shù)字轉(zhuǎn)換成字符串并輸出*/ settextstyle(4,0,1); setcolor(white); outtextxy(50,50,nodedata:); outtextxy(50,70,doublelinks:); setcolor(10); outtextxy(155+n*35,50,str);/*顯示數(shù)據(jù)*/ getch(); s-right=null; s-left=null; prlink(head,n);/*每次插入新數(shù)字后都顯示當(dāng)前鏈表*/ n+; w

30、hile(n!=8) s=(linky)malloc(sizeof(linkx); s-data=random(100); s-num=n; sprintf(str,%d,s-data);/*將數(shù)字轉(zhuǎn)換成字符串并輸出*/ setcolor(10); outtextxy(155+n*35,50,str); getch(); p=head;/*每生成一個結(jié)點，將該結(jié)點插入到有序雙鏈表中*/ if(s-datadata)/*小于頭結(jié)點，插在頭*/ drawchange(s-data,-1,n);/*顯示插入的具體過程*/ s-right=head; s-left=null; s-num=0; hea

31、d-left=s; head=s; q=head-right;/*后面所有數(shù)的序號都加 1，相當(dāng)于數(shù)據(jù)后移*/ while(q!=null) q-num+; q=q-right; else/*其他情況*/ while(s-datap-data p=p-right; if(p=null)/*這個數(shù)是當(dāng)前最大的數(shù)，插在尾部*/ drawchange(s-data,n-1,n);/*顯示插入的具體過程*/ q-right=s; s-right=null; s-left=q; s-num=n; else /*結(jié)點插入位置位于兩數(shù)之間*/ q-right-left=s; s-right=q-right;

32、 s-left=q; q-right=s; s-num=q-num+1; drawchange(s-data,q-num,n);/*顯示插入的具體過程*/ /*后面所有數(shù)的序號都加 1*/ s=s-right; while(s!=null) s-num+; s=s-right; prlink(head,n);/*每次插入新數(shù)據(jù)后都顯示新鏈表*/ n+; /*畫鏈表插入的具體過程，data 是要插入的數(shù)據(jù)，i 為插入結(jié)點前驅(qū)結(jié)點序號，n 為當(dāng)前結(jié)點個數(shù)， 先將前驅(qū)結(jié)點和后繼之間的指針線擦除，顯示新結(jié)點插入過程，插入后擦除插入過程，恢復(fù)刪除的 前驅(qū)結(jié)點的指針線*/ void drawchange(

33、int data,int i,int n) char str5; setfillstyle(solid_fill,black); setcolor(red);/*插入鏈表的新數(shù)據(jù)用紅色顯示*/ sprintf(str,%d,data); outtextxy(55+70*i+35,100+n*50,str);/*輸出插入的位置*/ bar(50+70*i+35,100+(n-1)*50-20,50+70*i+65,100+(n-1)*50+20); /*去除插入結(jié)點位置原結(jié)點間的指針線*/ setcolor(yellow); if(i!=-1) /*不是插在頭，新結(jié)點的前驅(qū)指針線*/ line(

34、50+70*i+34,100+n*50,50+70*i+30,100+n*50); line(50+70*i+30,100+n*50,50+70*i+30,100+n*50-25); line(50+70*i+30,100+n*50-25,50+70*i+27,100+n*50-22); line(50+70*i+30,100+n*50-25,50+70*i+33,100+n*50-22); getch(); if(i!=n-1)/*不是插在尾，新結(jié)點的后繼指針線*/ line(50+70*i+61,100+n*50,50+70*i+65,100+n*50); line(50+70*i+65,

35、100+n*50,50+70*i+65,100+n*50-25); line(50+70*i+65,100+n*50-25,50+70*i+62,100+n*50-22); line(50+70*i+65,100+n*50-25,50+70*i+68,100+n*50-22); getch(); setcolor(6); if(i!=-1)/*不是插在頭，新結(jié)點前驅(qū)結(jié)點的后繼指針線*/ line(50+70*i+20,100+n*50-25,50+70*i+20,110+n*50); line(50+70*i+20,110+n*50,50+70*i+34,110+n*50); line(50+70*i+34,110+n*50,50+70*i+31,110+n*50-3); line(50+70*i+34,110+n*50,50+70*i+31,110+n*50+3); getch(); if(i!=n-1) /*不是插在尾，新結(jié)點后繼結(jié)點的前驅(qū)指針線*/ line(50+70*i+75,100+n*50-25,50+70*i+75,110+n*50); line(50+70*i+75,110+n*50,50+70*i+61,110+n*50); line(50+70*i+61,110+n*50,50+70*i+64,110+n*50-3); line(50+7