雙鏈表課程設(shè)計(jì)

1、課 程 設(shè) 計(jì) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 雙鏈表創(chuàng)建演示 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級 計(jì)算機(jī)1202班 學(xué) 號 29 姓 名 陳潤同 指導(dǎo)教師 陳淑紅 李珍輝 李杰君 2014年 6 月 16 日湖南工程學(xué)院課 程 設(shè) 計(jì) 任 務(wù) 書課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 雙鏈表創(chuàng)建演示 專業(yè)班級 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名 陳潤同 學(xué) 號 29 指導(dǎo)老師 陳淑紅 李珍輝 李杰君 審 批 任務(wù)書下達(dá)日期 2014 年 6 月 16 日任務(wù)完成日期 2014年 6 月 29 日課程設(shè)計(jì)報(bào)告任務(wù)書1設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求1.1設(shè)計(jì)內(nèi)容1.1.1 算術(shù)24游戲演示由系統(tǒng)隨機(jī)生成4張撲克牌，用戶利用撲

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

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

4、問序號。同時(shí)在遍歷的過程中在遍歷圖形的下方顯示出遍歷序列。1.1.4 拓?fù)渑判蜓菔狙菔就負(fù)渑判虻倪^程。按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。要求每輸出一個(gè)頂點(diǎn)后就演示從圖中刪去此頂點(diǎn)以及所有以它為尾的弧。1.1.5 圖的遍歷演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖的結(jié)點(diǎn)數(shù)不能少于6個(gè)?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動輸入圖。報(bào)告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。1.1.6 雙鏈表創(chuàng)建演示建立一個(gè)遞增有序的雙鏈表。功能是隨機(jī)生成8個(gè)結(jié)點(diǎn)數(shù)據(jù)，每

5、生成一個(gè)結(jié)點(diǎn)則申請空間得到一個(gè)指針，將數(shù)據(jù)存放到指針?biāo)傅臄?shù)據(jù)域中，然后將結(jié)點(diǎn)插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點(diǎn)的插入位置，第二演示插入過程中指針的變化，第三步顯示插入后的鏈表結(jié)果。1.1.7公園導(dǎo)游圖給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點(diǎn)到另一景點(diǎn)的最短路徑。游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點(diǎn)，最后回到出口（出口就在入口旁邊）。要求用圖示展示最佳路徑。1.1.8 最小生成樹算法演示隨機(jī)生成一個(gè)網(wǎng)，并用圖形展示，然后依據(jù)Prim算法或Kruskal算法求該圖的最小生成樹，并用圖形展示相應(yīng)的過程步驟。1.2 選題方案所選題目根據(jù)

6、學(xué)號確定，學(xué)號模8加1，即（學(xué)號%8+1）。如你的學(xué)號為13，則所選題目號為：13%8+1（題目6）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。1.3設(shè)計(jì)要求1.3.1 課程設(shè)計(jì)報(bào)告規(guī)范（1）需求分析a. 程序的功能。b. 輸入輸出的要求。（2）概要設(shè)計(jì)a. 程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個(gè)模塊的功能。b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。（3）詳細(xì)設(shè)計(jì)a. 采用C語言定義相關(guān)的數(shù)據(jù)類型。b. 寫出各模塊的類C碼算法。c. 畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。（4）調(diào)試分析以及設(shè)計(jì)體會a

7、. 測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯(cuò)誤的輸入及輸出結(jié)果。b. 程序調(diào)試中遇到的問題以及解決問題的方法。c. 課程設(shè)計(jì)過程經(jīng)驗(yàn)教訓(xùn)、心得體會。（5）使用說明用戶使用手冊：說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。 （6）書寫格式a. 設(shè)計(jì)報(bào)告要求用A4紙打印成冊：b. 一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距為22。（7）附錄a. 源程序清單（帶注釋）1.3.2 考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個(gè)等級給出每位

8、同學(xué)的課程設(shè)計(jì)成績。具體考核標(biāo)準(zhǔn)包含以下幾個(gè)部分：（1）平時(shí)出勤 （占10%）（2）系統(tǒng)需求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及程序總體結(jié)構(gòu)合理與否（占10%）（3）程序能否完整、準(zhǔn)確地運(yùn)行，個(gè)人能否獨(dú)立、熟練地調(diào)試程序（占40%）（4）設(shè)計(jì)報(bào)告（占30%）注意：不得抄襲他人的報(bào)告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧＃?）獨(dú)立完成情況（占10%）。1.3.3 課程驗(yàn)收要求（1）運(yùn)行所設(shè)計(jì)的系統(tǒng)。（2）回答有關(guān)問題。（3）提交課程設(shè)計(jì)報(bào)告。（4）提交軟盤（源程序、設(shè)計(jì)報(bào)告文檔）。（5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。2 進(jìn)度安排第 17 周：星期一 8：0012：00 上課 星

9、期二 14：0018：00 上機(jī)星期三 14：0018：00 上機(jī) 星期四 14：0018：00 上機(jī)第 18 周：星期一14：0018：00 上機(jī) 星期二 14：0018：00 上機(jī) 星期四 14：0018：00 上機(jī) 附：課程設(shè)計(jì)報(bào)告裝訂順序：封面、任務(wù)書、目錄、正文、評分、附件（A4大小的圖紙及程序清單）。 正文的格式:一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗, 三級標(biāo)題用小四號宋體加粗，正文用小四號宋體;行距為22。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫出模塊圖）；三、主要功能的實(shí)現(xiàn)（至少要有一個(gè)主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有程序

10、的原代碼，要求對程序?qū)懗霰匾淖⑨專?。正文總字?jǐn)?shù)要求在5000字以上（不含程序原代碼）。III目錄課程設(shè)計(jì)任務(wù)書I1設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求I2 進(jìn)度安排IV課程設(shè)計(jì)報(bào)告11.需求分析1 1.1 程序的功能1 1.2 輸入輸出的要求12.概要設(shè)計(jì)1 2.1 主要程序功能模塊圖1 2.2 抽象數(shù)據(jù)類型（ADT）23詳細(xì)設(shè)計(jì)3 3.1 C語言定義的相關(guān)數(shù)據(jù)類型3 3.2 主要模塊的偽碼算法33.2.1 建立并插入雙鏈表的類C算法33.2.2指針變化演示類C算法43.2.3 輸出已排序雙鏈表類C代碼5 3.3 畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程63.3.1 各函數(shù)的調(diào)用關(guān)系圖.63.3.2 主函數(shù)ma

11、in的流程圖.73.3.3 輸出鏈表函數(shù)PrLink的流程圖.73.3.4 插入指針變化函數(shù)DrawChange的流程圖.74.調(diào)試分析以及設(shè)計(jì)體會11 4.1測試數(shù)據(jù)11 4.2調(diào)試分析11 4.3程序調(diào)試中遇到的問題以及解決問題的方法15 4.4課程設(shè)計(jì)過程經(jīng)驗(yàn)教訓(xùn)、心得體會17.使用說明18.參考文獻(xiàn)187.附件19課程設(shè)計(jì)報(bào)告1. 需求分析1.1 程序的功能建立一個(gè)遞增有序的雙鏈表。功能是隨機(jī)生成8個(gè)結(jié)點(diǎn)數(shù)據(jù)，每生成一個(gè)結(jié)點(diǎn)則申請空間得到一個(gè)指針，將數(shù)據(jù)存放到指針?biāo)傅臄?shù)據(jù)域中，然后將結(jié)點(diǎn)插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點(diǎn)的插入位置，第二步則演示插入過程中指針的變化

12、，第三步顯示插入后的雙鏈表結(jié)果。1.2 輸入輸出的要求在菜單中輸入數(shù)據(jù)為任意鍵，輸入數(shù)據(jù)是由隨機(jī)函數(shù)隨機(jī)產(chǎn)生的，輸出函數(shù)用圖形文本顯示,主要是在屏幕顯示指針變化的情況和結(jié)點(diǎn)插入后的結(jié)果，具體輸出過程為輸出首先生成的結(jié)點(diǎn)，然后顯示對已生成結(jié)點(diǎn)的排序，再演示出指針變化，指針以彎折的箭頭表示，最后輸出排序后的鏈表，直箭頭表示雙鏈表的前驅(qū)后繼。2. 概要設(shè)計(jì)2.1 主要程序功能模塊圖 本程序由于僅需實(shí)現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主要由三部分模塊函數(shù)組成，即創(chuàng)建雙鏈表,鏈表插入的指針變化，輸出鏈表。創(chuàng)建鏈表指針變化輸出鏈表主函數(shù)main() 圖2.1主要程序功能模塊圖2.2 抽象數(shù)據(jù)類型（

13、ADT）ADT DList 數(shù)據(jù)對象：D=ai | ai1,100，i=0,8 數(shù)據(jù)關(guān)系：R=<ai-1, ai > | ai-1, aiD, i=0,8 基本操作： Init(void)操作結(jié)果：完成圖形的初始化。Close(void)初始條件:圖形初始化完成。操作結(jié)果：關(guān)閉圖形。InitList(void)操作結(jié)果：創(chuàng)建雙鏈表。PrLink(linky p,int n)初始條件：鏈表已存在。操作結(jié)果：插入后輸出鏈表。DrawChange(int data,int i,int n)初始條件：鏈表已存在。操作結(jié)果：鏈表插入時(shí)的指針變化。ListInsert (DLinkList &

14、amp;L, int i, ElemType e)初始條件：鏈表已存在，1iListLength(L)+1。操作結(jié)果：在L中的第i個(gè)位置之前插入新數(shù)據(jù)元素e,L的長度加1。ListDelete (DLinkList &L, int i, ElemType &e)初始條件：鏈表已存在且非空，1iListLength(L)。操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1。ListLength(DLinkList &L)初始條件：鏈表已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)。LocateELem (DLinkList &L, ElemType e, co

15、mpare()初始條件：鏈表已存在,compare()是數(shù)據(jù)元素判定函數(shù)。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位 序。若這樣的數(shù)據(jù)元素不存在，則返回值為0 ListEmpty(DListLink &L)初始條件：鏈表已存在。操作結(jié)果：若L為空表，則返回TRUE,否則返回FALSE。ClearList(DLinkList &L)初始條件：鏈表已存在。操作結(jié)果：將L重置為空表。DestroyList（DLinkList &L）初始條件：鏈表已存在。操作結(jié)果：銷毀L。 ADT DList3詳細(xì)設(shè)計(jì)3.1 C語言定義的相關(guān)數(shù)據(jù)類型typedef s

16、truct Link /*雙鏈表結(jié)點(diǎn)定義*/ int data; struct Link *next; struct Link *prior; int num; /*給鏈表加序號,為了演示時(shí)計(jì)算正確位置*/linkx,*linky;3.2 主要模塊的偽碼算法3.2.1 建立并插入雙鏈表的類C算法 void InitList(void) srand(unsigned)time(NULL); 將產(chǎn)生的隨機(jī)數(shù)字轉(zhuǎn)換成字符串并輸出； PrLink(head,n); /*顯示只有頭節(jié)點(diǎn)的鏈表*/ n+; while(n!=8) s->data=rand()%100+1; if(s->data

17、<=head->data) /*小于頭結(jié)點(diǎn)，插在頭*/ q=head->next; q->num+; /*節(jié)點(diǎn)數(shù)加1；*/ 顯示具體插入過程； else /其他情況/ if(p=NULL) /*這個(gè)數(shù)是當(dāng)前最大的數(shù)，插在尾部*/ 顯示插入的具體過程； else /*隨即產(chǎn)生的數(shù)排在表中*/ while(s!=NULL) s->num+;s=s->next; 顯示插入的具體過程； 3.2.2指針變化演示類C算法void DrawChange(int data,int i,int n) 判斷插入結(jié)點(diǎn)的位置： if(i!=-1) 不是插在頭，畫新結(jié)點(diǎn)的前驅(qū)指針線；

18、 if(i!=n-1)不是插在尾，畫新結(jié)點(diǎn)的后繼指針線；去除插入位置的后繼指針線；if(i!=-1)不是插在頭，畫新結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的后繼指針線；去除插入位置的前驅(qū)指針線；if(i!=n-1) 不是插在尾，畫新結(jié)點(diǎn)后繼結(jié)點(diǎn)的前驅(qū)指針線；if(i!=n-1&&i!=-1) 既不是頭指針也不是尾指針時(shí)： 畫前驅(qū)指針線； 畫后繼指針線； 擦掉所畫的指針線；3.2.3 輸出已排序雙鏈表類C代碼 void PrLink(linky p,int n) while(p!=NULL) 輸出隨機(jī)產(chǎn)生的數(shù)據(jù)；if(p->prior!=NULL) 畫前驅(qū)指針； if(p->next!=NUL

19、L) 畫后繼指針； p=p->next; 3.3 畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程3.3.1各函數(shù)的調(diào)用關(guān)系圖本次課程設(shè)計(jì)由六個(gè)基本函數(shù)模塊組成，依次為主函數(shù)mian(void)，圖形驅(qū)動函數(shù)Init(void)，圖形關(guān)閉函數(shù)Close(void)，雙鏈表的創(chuàng)建函數(shù)InitList(void)，雙鏈表的指針變化演示函數(shù)DrawChange(int data,int i,int n)以及雙鏈表的輸出顯示函數(shù)PrLink(linky p,int n)。他們之間的函數(shù)調(diào)用關(guān)系為：由主函數(shù)mian(void)首先調(diào)用圖形驅(qū)動函數(shù)Init(void)，以驅(qū)動圖形界面的建立；接著主函數(shù)mian

20、(void)會調(diào)用雙鏈表的創(chuàng)建函數(shù)InitList(void)，利用該函數(shù)，我們會得到由8個(gè)隨機(jī)數(shù)據(jù)結(jié)點(diǎn)生成的一個(gè)雙鏈表，其建立的過程是一個(gè)一個(gè)的結(jié)點(diǎn)依次產(chǎn)生，而后對當(dāng)前雙鏈表進(jìn)行遍歷，找到新生成的數(shù)據(jù)結(jié)點(diǎn)所需要插入的位置，然后調(diào)用雙鏈表的指針變化演示函數(shù)DrawChange(int data,int i,int n)，對其插入過程進(jìn)行顯示，然后調(diào)用雙鏈表的輸出顯示函數(shù)PrLink(linky p,int n)，對每次插入后的雙鏈表進(jìn)行輸出顯示；待完成8個(gè)數(shù)據(jù)結(jié)點(diǎn)的插入與演示之后，程序返回主函數(shù)mian(void)當(dāng)中，由主函數(shù)mian(void)調(diào)用圖形關(guān)閉函數(shù)Close(void)，整個(gè)程

21、序運(yùn)行結(jié)束。如圖3.1所示。 main(void)Init(void)InitList(void)Close(void)PrLink(linky p,int n)DrawChange(int data,int i,int n) 圖3.1 各函數(shù)的調(diào)用關(guān)系圖3.3.2主函數(shù)main（void）主要思路：由主函數(shù)mian(void)首先調(diào)用圖形驅(qū)動函數(shù)Init(void)，以驅(qū)動圖形界面的建立；接著主函數(shù)mian(void)會調(diào)用雙鏈表的創(chuàng)建函數(shù)InitList(void)，利用該函數(shù)，我們會得到由8個(gè)隨機(jī)數(shù)據(jù)結(jié)點(diǎn)生成的一個(gè)雙鏈表，其建立的過程是一個(gè)一個(gè)的結(jié)點(diǎn)依次產(chǎn)生，而后對當(dāng)前雙鏈表進(jìn)行遍歷，找

22、到新生成的數(shù)據(jù)結(jié)點(diǎn)所需要插入的位置，然后調(diào)用雙鏈表的指針變化演示函數(shù)DrawChange(int data,int i,int n)。其調(diào)用過程需要根據(jù)s->data與head->data的大小來判斷，如果s->data<=head->data，表示所要插入的結(jié)點(diǎn)數(shù)據(jù)小于雙鏈表的頭結(jié)點(diǎn)數(shù)據(jù)，這時(shí)，程序?qū)⒄{(diào)用調(diào)用函數(shù)DrawChange(s->data,-1,n)，對其進(jìn)行頭部插入操作；如果s->data>head->data并且p!=NULL,表示所要插入的數(shù)據(jù)結(jié)點(diǎn)既不在雙鏈表的頭部也不在雙鏈表的尾部，而是要在雙鏈表的中間對其進(jìn)行插入操作，

23、這時(shí)，程序?qū)⒄{(diào)用函數(shù)DrawChange(s->data,n-1,n)，對其進(jìn)行雙鏈表的中間插入操作；如果s->data<=head->data并且p=NULL，表示所要插入新的結(jié)點(diǎn)數(shù)據(jù)大于雙鏈表的尾部結(jié)點(diǎn)數(shù)據(jù)，這時(shí)，程序?qū){(diào)用函數(shù)DrawChange(s->data,q->num,n)，對其進(jìn)行雙鏈表的尾部插入操作。然后調(diào)用雙鏈表的輸出顯示函數(shù)PrLink(linky p,int n)，對每次插入后的雙鏈表進(jìn)行輸出顯示，；待完成8個(gè)數(shù)據(jù)結(jié)點(diǎn)的插入與演示之后，程序返回主函數(shù)mian(void)當(dāng)中，由主函數(shù)mian(void)調(diào)用圖形關(guān)閉函數(shù)Close(v

24、oid)，整個(gè)程序運(yùn)行結(jié)束。如圖3.2所示。3.3.3輸出鏈表函數(shù)PrLink（linky p,int n）主要思路：p開始時(shí)指向頭結(jié)點(diǎn)，如果p!=NULL，表示當(dāng)前存在數(shù)據(jù)結(jié)點(diǎn)，這時(shí)就需要對其進(jìn)行輸出，如果p->prior!=NULL，表示當(dāng)前結(jié)點(diǎn)存在左指針，這時(shí)就需要畫出他的左指針線，如果p->next!=NULL，表示當(dāng)前結(jié)點(diǎn)存在右指針，這時(shí)就需要畫出他的右指針線，之后p=p->next，表示指針移向雙鏈表的下一個(gè)位置，直到p=NULL為之，此時(shí)表示雙鏈表已沒有下一個(gè)數(shù)據(jù)結(jié)點(diǎn)，所有的數(shù)據(jù)結(jié)點(diǎn)已經(jīng)完全輸出。如圖3.3所示。3.3.4插入指針變化函數(shù)DrawChange（i

25、nt data,int i,int n）主要思路：該函數(shù)是畫鏈表插入的具體過程，其中data是所要插入的數(shù)據(jù)，i為插入結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)序號，n為當(dāng)前雙鏈表中的所有結(jié)點(diǎn)個(gè)數(shù)。先將所要插入結(jié)點(diǎn)的前驅(qū)和后繼的指針線加上，在這里需要用到EasyX中的畫線函數(shù)line（），然后刪除新結(jié)點(diǎn)所要插入位置的后繼指針線，這里需要用到EasyX中的畫矩形函數(shù)bar()，使其來覆蓋原圖形中的線條圖形，以達(dá)到刪除指針的功能。之后對前驅(qū)指針的操作也如此進(jìn)行。然后便是要擦掉插入過程的指針線，同樣也用bar（）函數(shù)操作。如圖3.4所示。用函數(shù)InitList(void)調(diào)用函數(shù)PrLink(p,n)s- > data

26、<=head- > datap=NULL調(diào)用函數(shù)DrawChange(s->data,n-1,n)調(diào)用函數(shù)DrawChange(s->data,-1,n)調(diào)用函數(shù)DrawChange(s->data,q->num,n)調(diào)用函數(shù)PrLink(head,n)調(diào)用函數(shù)Close(void)調(diào)用函數(shù)Init(void)開始結(jié)束 N Y Y NY 圖3.2 主函數(shù)的流程圖 開始函數(shù)PrLink(p,n) p!=NULLp->prior=NULL 畫左指針線p->next=NULL 畫右指針線 結(jié)束 Y NN 圖3.3 輸出鏈表函數(shù)PrLink()的流程圖

27、開始 i!=-1bar結(jié)點(diǎn)的前驅(qū)指針線bar結(jié)點(diǎn)的前驅(qū)指針線 i!=n-1line新結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的后繼指針線line新結(jié)點(diǎn)的前驅(qū)指針線bar結(jié)點(diǎn)的后繼指針線 i!=n-1line新結(jié)點(diǎn)后繼結(jié)點(diǎn)的前驅(qū)指針線 (i!=n-1&&i!=-1）line前驅(qū)和后繼指針線bar插入過程的指針線 結(jié)束 圖3.4 插入指針變化函數(shù)流程圖4.調(diào)試分析以及設(shè)計(jì)體會4.1測試數(shù)據(jù)：測試數(shù)據(jù)是由隨機(jī)函數(shù)srand(unsigned)time(NULL)生成的介于1100之間的整數(shù)。4.2調(diào)試分析：進(jìn)入程序界面，程序會彈出對話框，由用戶進(jìn)行選擇操作數(shù)字，數(shù)字1表示進(jìn)入程序，數(shù)字2表示退出程序。具體程序代

28、碼為：InputBox(s, 10, "Please make choice: 1 Enter 2 Exit")；如圖4.1所示： 圖4.1 程序初始界面對話框在對話框中輸入數(shù)字1后，進(jìn)入程序運(yùn)行界面，可以看到第一行的提示，按任意鍵繼續(xù)；第二行是數(shù)據(jù)結(jié)點(diǎn)，并且已經(jīng)產(chǎn)生第一個(gè)隨機(jī)數(shù)據(jù)；第三行是雙鏈表的插入演示過程。具體程序代碼為：outtextxy(50,10,"Press any key to continue"); outtextxy(50,40,"NodeData:"); outtextxy(50,60,"DoubleL

29、inks:");如圖4.2所示： 圖4.2 進(jìn)入程序運(yùn)行界面操作將繼續(xù)進(jìn)行，這時(shí)出現(xiàn)第三個(gè)數(shù)據(jù)結(jié)點(diǎn)62，結(jié)點(diǎn)62要插在46和91這兩個(gè)數(shù)據(jù)結(jié)點(diǎn)的中間。其過程是，先將62結(jié)點(diǎn)的前驅(qū)與后繼指針線分別指向數(shù)據(jù)結(jié)點(diǎn)46和數(shù)據(jù)結(jié)點(diǎn)91；然后將數(shù)據(jù)結(jié)點(diǎn)46的后繼指針指向數(shù)據(jù)結(jié)點(diǎn)62，同時(shí)刪除46指向91的指針。如圖4.3所示： 圖4.3 結(jié)點(diǎn)在鏈表中間插入1操作繼續(xù)進(jìn)行，將結(jié)點(diǎn)62的后繼指針指向結(jié)點(diǎn)91，同時(shí)去掉它的結(jié)點(diǎn)91到46的前驅(qū)指針。以上過程的具體程序代碼為：s->next=q->next;s->prior=q;q->next->prior=s;q->

30、next=s;如圖4.4所示： 圖4.4 結(jié)點(diǎn)在鏈表中間插入2操作繼續(xù)進(jìn)行，結(jié)點(diǎn)的插入操作完成，形成一條新的雙鏈表。具體程序代碼為： while(p!=NULL) p=p->next;如圖4.5所示: 圖4.5 雙鏈表的顯示操作繼續(xù)進(jìn)行，出現(xiàn)新結(jié)點(diǎn)100，其按照順序需插在雙鏈表的最后。首先要將新結(jié)點(diǎn)100的前驅(qū)結(jié)點(diǎn)的指向結(jié)點(diǎn)91。如圖4.6所示： 圖4.6 新結(jié)點(diǎn)在雙鏈表尾部插入1操作繼續(xù)進(jìn)行，結(jié)點(diǎn)91的后繼指針指向新結(jié)點(diǎn)100。以上過程的具體代碼為s->prior=q;s->next=NULL;q->next=s;如圖4.7所示: 圖4.7 新結(jié)點(diǎn)在雙鏈表尾部插入2

31、繼續(xù)操作的執(zhí)行，當(dāng)八個(gè)數(shù)據(jù)都插入雙鏈表后，形成一條從小到大的雙鏈表，如圖4.8所示： 圖4.8 雙鏈表演示程序完成按任意鍵后退出操作的執(zhí)行。4.3程序調(diào)試中遇到的問題以及解決問題的方法在編寫結(jié)點(diǎn)插入雙鏈表中的指針變化演示函數(shù)DrawChange時(shí)，一開始所要?jiǎng)h除指針的位置總是找不到正確的位置。我的解決方法是，請教老師和同學(xué)，經(jīng)過仔細(xì)的檢查，發(fā)現(xiàn)原來是對所要插入結(jié)點(diǎn)的前驅(qū)指針和后繼指針的刪除順序出現(xiàn)了錯(cuò)誤，經(jīng)過一番修改之后，新結(jié)點(diǎn)便可以正確的插入到雙鏈表中了。如圖4.9所示。在編寫雙鏈表的顯示函數(shù)PrLink時(shí)，程序有時(shí)不能將當(dāng)前工作狀態(tài)下的所有結(jié)點(diǎn)顯示出來。我的解決方法是，請教老師，在老師的建

32、議下，我為程序創(chuàng)建雙鏈表時(shí)的創(chuàng)建函數(shù)InitList加上了頭指針結(jié)點(diǎn)，之后經(jīng)過修改，程序便可以正常的輸出所有數(shù)據(jù)結(jié)點(diǎn)了。如圖4.10所示。 圖 4.9 指針線無法正確的刪除 圖 4.10 雙鏈表無法正確顯示4.4課程設(shè)計(jì)過程經(jīng)驗(yàn)教訓(xùn)、心得體會在本次課程設(shè)計(jì)中，我的課題是完成雙鏈表創(chuàng)建演示的程序設(shè)計(jì)。這也是我第一次利用EasyX軟件在VC6.0的軟件平臺上做圖形演示程序，對此，我感到既新鮮又有一點(diǎn)擔(dān)心，新鮮的是我以前從沒考慮過在VC6.0上也可以做出一系列的圖形，例如，畫圓形，畫矩形，畫線條等，這使我覺得很新鮮，激發(fā)了我的好奇性與渴望以最好的程序界面來完成課程設(shè)計(jì)的課題；擔(dān)心的是畢竟我對C語言的

33、圖形編程不是很熟悉，在課程設(shè)計(jì)的第一周心里很是擔(dān)心，甚至想過用Turboc的軟件平臺來進(jìn)行答辯，但后來經(jīng)過老師和同學(xué)的熱心幫助，以及自己的認(rèn)真調(diào)試，我最終在VC6.0的軟件平臺上成功的將程序調(diào)試了出來。本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)不同于以往C語言的課程設(shè)計(jì)，給我最大的感受就是，以往的C語言編程，我只需要考慮該課程設(shè)計(jì)需要實(shí)現(xiàn)多少個(gè)功能，功能對應(yīng)幾個(gè)函數(shù)模塊以及這幾個(gè)函數(shù)模塊之間是怎樣的調(diào)用關(guān)系便可，之后便是對各個(gè)功能函數(shù)的具體實(shí)現(xiàn)，只要做到這些思索，程序的設(shè)計(jì)基本上就完成了；但本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)不單單只是按照C語言的課程設(shè)計(jì)方法來編程就可以完成的，它需要我對程序有更加深入與細(xì)致的了解，當(dāng)然對圖形

34、界面的顯示與操作也要有必要的了解，所以，我在圖書館中查閱了一些關(guān)于圖形界面處理方法的圖書資料。在本次程序設(shè)計(jì)的過程中，遇到問題是在所難免的，但我并沒有逃避問題，我積極的請教老師和同學(xué)，在老師和同學(xué)的幫助下，我成功的解決了問題，調(diào)試出了程序。在此，我要衷心的感謝陳老師以及幫助我的同學(xué)。通過本次為期兩周的課程設(shè)計(jì)，加深了我對數(shù)據(jù)結(jié)構(gòu)知識尤其是雙鏈表插入部分內(nèi)容的理解與記憶，提高了我的動手操作能力，使我有機(jī)會將數(shù)據(jù)結(jié)構(gòu)的理論知識與實(shí)踐操作可以結(jié)合起來，做到靈活運(yùn)用所學(xué)的知識。同時(shí)，我也了解了一款在處理圖形界面很有效率的軟件，那就是EasyX，這款軟件使VC6.0較好的處理圖形界面成為了現(xiàn)實(shí)。 最后我

35、意識到作為一個(gè)計(jì)算機(jī)系的學(xué)生，正確掌握一門程序語言和數(shù)據(jù)結(jié)構(gòu)的重要性，想要在程序設(shè)計(jì)上面做出成績，必須要有扎實(shí)的編程語言基礎(chǔ)和良好的數(shù)據(jù)結(jié)構(gòu)算法知識，同時(shí)我也認(rèn)識到，單靠自己的力量來死扣程序是很沒有效率的，因?yàn)槟銜谝粋€(gè)死區(qū)里不停的打轉(zhuǎn)，但當(dāng)你請教他人的時(shí)候，很多的時(shí)候你會豁然開朗，對問題有了清晰的解決方案，所以，我們要學(xué)會善于請教他人。.使用說明本程序是演示程序，在運(yùn)行后按任意鍵即執(zhí)行演示過程，可直觀的看到程序運(yùn)行時(shí)雙鏈表指針的變化情況，等待所有過程結(jié)束后出現(xiàn)一個(gè)笑臉圖形然后再退出。當(dāng)進(jìn)入程序界面后，按任意鍵出現(xiàn)數(shù)據(jù)結(jié)點(diǎn)，當(dāng)插入新結(jié)點(diǎn)的時(shí)候，按任意鍵可以顯示指針變化的全過程，直到雙鏈表滿8個(gè)

36、結(jié)點(diǎn)的時(shí)候，按任意鍵輸出笑臉，再按任意鍵退出。.參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)，北京：清華大學(xué)出版社，201342李春葆數(shù)據(jù)結(jié)構(gòu)教程，北京：清華大學(xué)出版社，201313李春葆上機(jī)實(shí)驗(yàn)指導(dǎo)，北京：清華大學(xué)出版社，201314譚浩強(qiáng). C程序設(shè)計(jì)，北京：清華大學(xué)出版社，201065 6 7.附件#include "stdio.h"#include "time.h"#include "stdlib.h"#include "graphics.h"#include "conio.h"typedef st

37、ruct Link/*雙鏈表結(jié)點(diǎn)定義*/int data;struct Link *prior;struct Link *next;int num;/*給鏈表加序號,為了演示時(shí)計(jì)算正確位置*/linkx,*linky;void Init(void);/*圖形驅(qū)動*/void Close(void);/*圖形關(guān)閉*/void InitList(void);/*建立雙鏈表,邊建立邊插入數(shù)據(jù)結(jié)點(diǎn)*/void PrLink(linky p,int n);/*每次插入后輸出鏈表*/void DrawChange(int data,int i,int n);/*畫鏈表插入的指針變化*/void main(

38、void)int i; char s5; Init();/*圖形驅(qū)動*/ InputBox(s, 10, "Please make choice: 1 Enter 2 Exit"); sscanf(s,"%d",&i); if(i=1)InitList();/*建立雙鏈表*/Close();else Close();/*圖形關(guān)閉*/ exit(0);void InitList(void)/*建立雙鏈表,邊建立邊插入數(shù)據(jù)結(jié)點(diǎn)*/linky head,p,q,s;int n=0;char str5; srand(unsigned)time(NULL)

39、;/*隨機(jī)數(shù)發(fā)生機(jī)*/head=s=(linky)malloc(sizeof (linkx);s->data=rand()%100+1;/*隨機(jī)生成100以內(nèi)的數(shù)字*/ s->num=n;sprintf(str,"%d",s->data);/*將數(shù)字轉(zhuǎn)換成字符串并輸出*/ setfont(16,0,"宋體");/* 設(shè)置當(dāng)前字體為高 16 像素的“宋體”*/ setcolor(BLUE);outtextxy(50,10,"Press any key to continue"); outtextxy(50,40,&qu

40、ot;NodeData:"); outtextxy(50,60,"DoubleLinks:"); setcolor(RED);outtextxy(155+n*35,40,str);/*顯示數(shù)據(jù)*/ getch(); s->prior=NULL; s->next=NULL;PrLink(head,n);/*每次插入新數(shù)字后都顯示當(dāng)前鏈表*/ n+; while(n!=8)s=(linky)malloc(sizeof(linkx);s->data=rand()%100+1;/*隨機(jī)生成1到100以內(nèi)的數(shù)字*/s->num=n;sprintf(s

41、tr,"%d",s->data);/*將數(shù)字轉(zhuǎn)換成字符串并輸出*/setcolor(RED);outtextxy(155+n*35,40,str);getch();p=head;/*每生成一個(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)插入到有序雙鏈表中*/if(s->data<=head->data)/*小于頭結(jié)點(diǎn)，插在頭*/DrawChange(s->data,-1,n);/*顯示插入的具體過程*/s->next=head;s->prior=NULL;s->num=0;head->prior=s;head=s;q=head->next;/*

42、后面所有數(shù)的序號都加1，相當(dāng)于數(shù)據(jù)后移*/while(q!=NULL)q->num+;q=q->next;else/*其他情況*/while(p!=NULL&&s->data>p->data) q=p; p=p->next;if(p=NULL)/*這個(gè)數(shù)是當(dāng)前最大的數(shù)，插在尾部*/DrawChange(s->data,n-1,n);/*顯示插入的具體過程*/s->prior=q;s->next=NULL;q->next=s;s->num=n;else /*結(jié)點(diǎn)插入位置位于兩數(shù)之間，q之后插入*/s->nex

43、t=q->next;s->prior=q;q->next->prior=s;q->next=s;s->num=q->num+1;DrawChange(s->data,q->num,n);/*顯示插入的具體過程*/s=s->next;while(s!=NULL)/*后面所有數(shù)的序號都加1*/s->num+;s=s->next;PrLink(head,n);/*每次插入新數(shù)據(jù)后都顯示新鏈表*/n+;/*畫鏈表插入的具體過程，data是要插入的數(shù)據(jù)，i為插入結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)序號，n為當(dāng)前結(jié)點(diǎn)個(gè)數(shù)，先將前驅(qū)結(jié)點(diǎn)和后繼之間的指針線擦除，

44、顯示新結(jié)點(diǎn)插入過程，插入后擦除插入過程，恢復(fù)刪除的前驅(qū)結(jié)點(diǎn)的指針線*/void DrawChange(int data,int i,int n) char str5; setcolor(BLACK);/*插入鏈表的新數(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); setcolor(BLUE); if(i!=-1) /*不是插在頭，新結(jié)點(diǎn)的前驅(qū)

45、指針線*/ line(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é)點(diǎn)的后繼指針線*/ line(50+70*i+61,100+n*50,50+70*i+65,100+n*50); line(

46、50+70*i+65,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(RED); bar(50+70*i+35,100+(n-1)*50+5,50+70*i+65,100+(n-1)*50+20);/*去除插入位置的后繼指針線*/ if(i!=-1)/*不是插在頭，新結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的后繼指針線*/ 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+