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

1、<p>　　課 程 設(shè) 計 報 告</p><p>　　課程名稱 數(shù)據(jù)結(jié)構(gòu) </p><p>　　課題名稱 雙鏈表創(chuàng)建演示 </p><p>　　專 業(yè) 計算機科學與技術(shù) </p><p>　　班 級 計算機0703

2、 </p><p>　　學 號 </p><p>　　姓 名 </p><p>　　指導教師 </p><p>　　2009 年 11 月 7 日</p><p>　　課 程 設(shè) 計 任 務(wù) 書<

3、/p><p>　　課程名稱 數(shù)據(jù)結(jié)構(gòu) </p><p>　　課 題 雙鏈表創(chuàng)建演示</p><p>　　專業(yè)班級 </p><p>　　學生姓名 張 理 </p><p>　　學 號 </p><p>　　指導

4、老師 </p><p>　　審 批 </p><p>　　1設(shè)計內(nèi)容與設(shè)計要求</p><p><b>　　1.1設(shè)計內(nèi)容</b></p><p>　　1.1.1 算術(shù)24游戲演示</p><p>　　由系統(tǒng)隨機生成4張撲克牌，用

5、戶利用撲克牌的數(shù)字及運算符號“+”、“—”、“*”、“/”及括號“（”和“）”從鍵盤上輸入一個計算表達式，系統(tǒng)運行后得出計算結(jié)果，如果結(jié)果等于24，則顯示“Congratulation!”，否則顯示“Incorrect!”</p><p>　　設(shè)計思路：從鍵盤輸入中綴表達式，然后將中綴表達式轉(zhuǎn)換為后綴表達式，利用后綴表達式求值。</p><p>　　1.1.2 迷宮探索</p>

6、<p>　　隨機生成一個迷宮圖，迷宮大小為N*N，N預(yù)定義為常數(shù)，修改N的值可以改變迷宮的大小。用白色表示可走的路，藍色表示墻壁不可以通過。系統(tǒng)設(shè)計兩種運行方式：一種是系統(tǒng)自動探索（用遞歸方法實現(xiàn)）；另一種是由人工操作探索通路。</p><p>　　設(shè)計思路：程序首先要考慮迷宮的表示，這是一個二維關(guān)系圖，所以可選擇二維數(shù)組來存儲。數(shù)組元素只有兩種值0和1，分別代表通路和墻壁。圖形的顯示可以根據(jù)數(shù)組元

7、素的值來確定。如果是人工探索，則依據(jù)按鍵來確定探索物的位置坐標，利用循環(huán)語句實現(xiàn)。如果是系統(tǒng)自動探索，可采用遞歸算法實現(xiàn)。</p><p>　　1.1.3 二叉樹遍歷演示</p><p>　　演示遍歷二叉樹的過程，所以首先建立二叉樹，并用圖形顯示出樹的形狀。建立的過程是采用前序便利的方法來創(chuàng)建，設(shè)計兩種生成樹的方式：一種是系統(tǒng)隨機生成，另一種是人工輸入?？紤]到屏幕界面的有限性，限定二叉樹不

8、超過5層，最多26個字符，輸入字符小數(shù)點“.”代表NULL。初始樹為某種顏色的結(jié)點，三種情況的遍歷采用填充另外一種醒目的顏色，來表示當前遍歷的結(jié)點，同時顯示該結(jié)點的訪問序號。同時在遍歷的過程中在遍歷圖形的下方顯示出遍歷序列。</p><p>　　1.1.4 數(shù)組應(yīng)用</p><p>　　按照行優(yōu)先順序?qū)⒂脩綦S機輸入的數(shù)據(jù)建成2維數(shù)組并以圖形方式逐步顯示出來，然后再按照列優(yōu)先順序以圖形方式逐

9、步輸出相應(yīng)數(shù)組。</p><p>　　1.1.5 拓撲排序演示</p><p>　　演示拓撲排序的過程。按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。要求每輸出一個頂點后就演示從圖中刪去此頂點以及所有以它為尾的弧。</p><p>　　1.1.6 圖的遍歷</p><p&g

10、t;　　演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖的結(jié)點數(shù)不能少于6個?？梢杂上到y(tǒng)隨機生成圖，也可以由用戶手動輸入圖。報告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學可以進一步改進圖的效果。</p><p>　　1.1.7 八皇后問題演示</p><p>　　在8*8的棋盤上擺放8個皇后，使他們不在同一條對角線上和不在一行和列上。  解決8皇后時，在

11、安放第i行皇后時，需要在列的方向從1到n試探(j =1,…, n)：首先在第j列安放一個皇后，如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動，遞歸安放第i+1行皇后。 該課題要求求解可能的方案及方案數(shù)并逐步演示擺放皇后的過程。</p><p>　　1.1.8 雙鏈表創(chuàng)建演示</p><p>　　建立一個遞增有序的雙鏈

12、表。功能是隨機生成8個結(jié)點數(shù)據(jù)，每生成一個結(jié)點則申請空間得到一個指針，將數(shù)據(jù)存放到指針所指的數(shù)據(jù)域中，然后將結(jié)點插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點的插入位置，第二不演示插入過程中指針的變化，第三步顯示插入后的鏈表結(jié)果。</p><p>　　1.1.9 公園導游圖</p><p>　　給出一張某公園的導游圖，游客通過終端詢問可知：從某一景點到另一景點的最短路徑。游客從公園

13、大門進入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點，最后回到出口（出口就在入口旁邊）。要求用圖示展示最佳路徑。</p><p><b>　　1.2 選題方案：</b></p><p>　　所選題目根據(jù)學號確定，學號模9加1，即（學號%9+1）。如你的學號為12，則所選題目號為：12%9+1＝（題目4）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。有興趣的同學可

14、以自己針對數(shù)據(jù)結(jié)構(gòu)課程中所講算法來設(shè)計一個演示過程的算法，但要預(yù)先告知老師，經(jīng)過審批，方可確定課題。</p><p><b>　　1.3設(shè)計要求：</b></p><p>　　1.3.1 課程設(shè)計報告規(guī)范</p><p><b>　?。?）需求分析</b></p><p><b>　　程序

15、的功能。</b></p><p><b>　　輸入輸出的要求。</b></p><p><b>　　（2）概要設(shè)計</b></p><p>　　程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個模塊的功能。</p><p>　　課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)

16、據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。</p><p><b>　?。?）詳細設(shè)計</b></p><p>　　采用C語言定義相關(guān)的數(shù)據(jù)類型。</p><p>　　寫出各模塊的類C碼算法。</p><p>　　畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。</p><p>　?。?）調(diào)試分

17、析以及設(shè)計體會</p><p>　　測試數(shù)據(jù)：準備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果。</p><p>　　程序調(diào)試中遇到的問題以及解決問題的方法。</p><p>　　課程設(shè)計過程經(jīng)驗教訓、心得體會。</p><p><b>　?。?）使用說明</b></p>&

18、lt;p>　　用戶使用手冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。</p><p><b>　?。?）書寫格式</b></p><p>　　設(shè)計報告要求用A4紙打印成冊：</p><p>　　一級標題用3號黑體,二級標題用四號宋體加粗,正文用小四號宋體;行距為22。</p><p><b>

19、　　（7）附錄</b></p><p>　　源程序清單（帶注釋）</p><p>　　1.3.2 考核方式</p><p>　　指導老師負責驗收程序的運行結(jié)果，并結(jié)合學生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設(shè)計報告等進行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學的課程設(shè)計成績。具體考核標準包含以下幾個部分：</p>&

20、lt;p>　?。?）平時出勤 （占10%）</p><p>　?。?）系統(tǒng)需求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否（占10%）</p><p>　?。?）程序能否完整、準確地運行，個人能否獨立、熟練地調(diào)試程序（占40%）</p><p>　?。?）設(shè)計報告（占30%）</p><p>　　注意：不得抄襲他人的報告（或給他人

21、抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?lt;/p><p>　?。?）獨立完成情況（占10%）。</p><p>　　1.3.3 課程驗收要求</p><p>　?。?）運行所設(shè)計的系統(tǒng)。</p><p>　　（2）回答有關(guān)問題。</p><p>　　（3）提交課程設(shè)計報告。</p><p>　　（4）提交

22、軟盤（源程序、設(shè)計報告文檔）。</p><p>　　（5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。</p><p><b>　　2 進度安排</b></p><p>　　2.1 計算機0701/0702班：</p><p>　　第 7 周：星期一 8：00——12：00 上課 星期一 14：00——

23、16：00 上課</p><p>　　星期五 18：00——22：00 上機</p><p>　　第 8 周：星期六 14：00——18：00 上機 星期日 8：00——12：00 上機</p><p>　　星期日 18：00——22：00 上課</p><p>　　第 9 周：星期六 8：00——12：00 上機 星

24、期日 14：00——18：00 上機</p><p>　　2.2 計算機0703班：</p><p>　　第 7 周：星期一 8：00——12：00 上課 星期一 14：00——16：00 上課</p><p>　　星期六 8：00——12：00 上機 星期日 14：00——18：00 上機</p><p>　

25、　第 8 周：星期六 8：00——12：00 上機 星期日 14：00——18：00 上機</p><p>　　第 9 周：星期六 14：00——18：00 上機 星期日 18：00——22：00 上機</p><p><b>　　目 錄</b></p><p>　　一、需求分析- 1 -</p><

26、;p>　　1.程序功能說明 - 1 -</p><p>　　2.輸入輸出- 1 -</p><p>　　二、概要設(shè)計- 2 -</p><p>　　1.程序模塊 本程序由于僅需實現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主要由三部分模塊函數(shù)組成，即構(gòu)建生成雙鏈表，演示指針變化，結(jié)果輸出。- 2 -</p&g

27、t;<p>　　2.課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu) 本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表，所用到的數(shù)據(jù)結(jié)構(gòu)如下- 2 -</p><p>　　2.1雙鏈表存儲結(jié)構(gòu)- 2 -</p><p>　　2.2雙鏈表結(jié)點的插入- 2 -</p><p>　　2.3雙鏈表結(jié)點的刪除- 3 -</p><p>　　

28、三、詳細設(shè)計- 4 -</p><p>　　1.采用C語言定義相關(guān)的數(shù)據(jù)類型- 4 -</p><p>　　1.1雙鏈表結(jié)點定義- 4 -</p><p>　　2.寫出各模塊的類C碼算法- 4 -</p><p>　　2.1 建立并插入雙鏈表的類C算法- 4 -</p><p>　　2.2 指針變化

29、演示類C算法- 5 -</p><p>　　3.3 輸出已排序雙鏈表類C代碼- 5 -</p><p>　　3.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。- 6 -</p><p>　　四、調(diào)試分析以及設(shè)計體會- 6 -</p><p>　　1．程序調(diào)試中遇到的問題以及解決問題的方法。- 6 -</p><

30、p>　　2．課程設(shè)計過程經(jīng)驗教訓、心得體會。- 7 -</p><p>　　五、使用說明- 7 -</p><p>　　六、附錄- 10 -</p><p>　　源程序清單- 10 -</p><p>　　參考文獻- 15 -</p><p><b>　　需求分析</b><

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

32、此結(jié)點的數(shù)值和已生成結(jié)點的大小，由于要求建立遞增有序的雙鏈表，所以把結(jié)點插入到比其大的所有結(jié)點中的最小結(jié)點之前和比其小的所有結(jié)點中最大結(jié)點的之后，并在插入過程中顯示指針變化，最后輸出排好序的雙鏈表。</p><p>　　輸入輸出由于本程序為演示程序，結(jié)點也由程序隨機生成，所以在輸入方面不需實現(xiàn)功能，只需用戶控制程序操作。輸出方面主要是在屏幕顯示插入結(jié)點的結(jié)果和顯示指針變化的功能，

33、具體輸出過程為輸出首先生成的結(jié)點，然后顯示對已生成結(jié)點的排序，再演示出指針變化，指針以彎折的箭頭表示，最后輸出排序后的鏈表，直箭頭表示雙鏈表的前驅(qū)后驅(qū)。</p><p><b>　　概要設(shè)計</b></p><p>　　程序模塊本程序由于僅需實現(xiàn)雙鏈表的創(chuàng)建演示，所以程序結(jié)構(gòu)比較簡單，主要由三部分模塊函數(shù)組成，即構(gòu)建生成雙鏈表，演示指

34、針變化，結(jié)果輸出。</p><p><b>　　程序結(jié)構(gòu)圖：</b></p><p>　　課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表，所用到的數(shù)據(jù)結(jié)構(gòu)如下</p><p>　　2.1雙鏈表存儲結(jié)構(gòu)</p><p>　　typedef struct DuLNode{</p&

35、gt;<p>　　ElemType data;</p><p>　　struct DuLNode *prior;</p><p>　　struct DuLNode *next;</p><p>　　}DuLNode, *DuLinkList;</p><p>　　2.2雙鏈表結(jié)點的插入</p><p>　

36、　Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){</p><p>　　if(!(p=GetElemp_DuL(L,i)))</p><p>　　return ERROR;</p><p>　　if(!(s=(DuLinklist)malloc(sizeof(DuLNode))))</p&

37、gt;<p>　　return ERROR;</p><p>　　s->data=e;</p><p>　　s->prior=p->prior; </p><p>　　p->piror-next=s;</p><p>　　s->next=p;</p><p>　　p->

38、prior=s;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　2.3雙鏈表結(jié)點的刪除</p><p>　　Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)｛</p>&l

39、t;p>　　if(!(p=GetElemP_DuL(L,i)))</p><p>　　return ERROR;</p><p>　　e=p->data;</p><p>　　p->prior->next=p->next;</p><p>　　p->next->prior=p->prior;&l

40、t;/p><p>　　free(p); return OK;</p><p><b>　　詳細設(shè)計</b></p><p>　　1.采用C語言定義相關(guān)的數(shù)據(jù)類型</p><p>　　1.1雙鏈表結(jié)點定義</p><p>　　typedef struct Link</p><p&g

41、t;<b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct Link *right;</p><p>　　struct Link *left;</p><p><b>　　int num;</b></p>

42、<p>　　}linkx,*linky;</p><p>　　2.寫出各模塊的類C碼算法</p><p>　　2.1 建立并插入雙鏈表的類C算法 </p><p>　　void InitList(void){ </p><p>　　randomize(); </p><p>　　將產(chǎn)生的隨機數(shù)字

43、轉(zhuǎn)換成字符串并輸出；</p><p><b>　　sleep(1);</b></p><p>　　PrLink(head,n); /*顯示只有頭節(jié)點的鏈表*/</p><p><b>　　n++; </b></p><p>　　while(n!=8){ </p><

44、p>　　s->data=random(100);</p><p>　　if(s->data<=head->data) /*小于頭結(jié)點，插在頭*/</p><p><b>　　{ </b></p><p>　　q=head->right; q->num++;} /*節(jié)點數(shù)加1；*/</p

45、><p><b>　　顯示具體插入過程；</b></p><p>　　else /其他情況/</p><p>　　if(p==NULL) /*這個數(shù)是當前最大的數(shù)，插在尾部*/</p><p>　　顯示插入的具體過程；</p><p>　　else /*隨即產(chǎn)生的數(shù)排在表中*/{

46、 </p><p>　　while(s!=NULL)</p><p>　　{ s->num++;s=s->right;}</p><p><b>　　}</b></p><p>　　顯示插入的具體過程；</p><p><b>　　}</b></p>

47、<p><b>　　}</b></p><p>　　2.2指針變化演示類C算法</p><p>　　void DrawChange(int data,int i,int n){ </p><p>　　判斷插入結(jié)點的位置：</p><p>　　if(i!=-1) </p><p>

48、;<b>　　{</b></p><p>　　當前指針是頭指針，畫前驅(qū)、后繼指針；</p><p><b>　　}</b></p><p>　　if(i!=n-1)</p><p><b>　　{</b></p><p>　　當前指針是尾指針，畫前驅(qū)、后

49、驅(qū)指針；</p><p><b>　　}</b></p><p>　　if(i!=n-1&&i!=-1)</p><p><b>　　{</b></p><p>　　不是頭指針也不是尾指針時：</p><p><b>　　畫前驅(qū)指針；</b&g

50、t;</p><p><b>　　畫后繼指針；</b></p><p><b>　　}</b></p><p><b>　　擦掉所畫的指針線；</b></p><p><b>　　}</b></p><p>　　3.3輸出已排序

51、雙鏈表類C代碼</p><p>　　void PrLink(linky p,int n){ </p><p>　　while(p!=NULL){ </p><p>　　輸出隨機產(chǎn)生的數(shù)據(jù)；</p><p>　　if(p->left!=NULL) /*第一個節(jié)點不顯示前驅(qū)指針*/</p><p><b

52、>　　畫前驅(qū)指針；</b></p><p>　　if(p->right!=NULL)</p><p><b>　　畫后繼指針；</b></p><p>　　p=p->right;</p><p><b>　　}</b></p><p><b

53、>　　}</b></p><p>　　3.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。</p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b&g

54、t;　　N</b></p><p>　　具體Inintlist(void)函數(shù)的流程圖：</p><p>　　調(diào)試分析以及設(shè)計體會</p><p>　　程序調(diào)試中遇到的問題以及解決問題的方法。</p><p>　　主要是在結(jié)點插入判斷方面有難度，一開始不能準確的進行結(jié)點的判斷和插入，然后就是插入結(jié)點的過程中位置不對，不是遞增有序的

55、，后面在網(wǎng)上找到了一段演示代碼，通過研究這段代碼解決了這個問題。還有就是在顯示指針變化方面有問題，經(jīng)過查詢資料，解決結(jié)點插入方面的問題，用畫箭頭的方式來表現(xiàn)指針的變化。</p><p>　　2．課程設(shè)計過程經(jīng)驗教訓、心得體會。</p><p>　　在進行本次課程設(shè)計的實驗操作中，由于自己的基礎(chǔ)知識不是很好，出現(xiàn)了一些問題：在編程方面不熟，所以寫出的代碼總是出錯；數(shù)據(jù)結(jié)構(gòu)課程以前也沒有好好學

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

57、據(jù)結(jié)構(gòu)，是樹還是圖或是別的什么？然后選定一種或幾種存儲結(jié)構(gòu)來具體的決定后面的函數(shù)的主要風格。最后在編寫每一個函數(shù)之前，可以仔細斟酌比對，挑選出最適合當前狀況的算法。這樣，即使在完整的程序還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質(zhì)量。</p><p>　　通過這次課程設(shè)計，使我意識到作為一個計算機系的學生，正確掌握一門程序語言和數(shù)據(jù)結(jié)構(gòu)的重要性，想要在程序設(shè)計上面作出成績，

58、必須要有扎實的編程語言基礎(chǔ)和良好的數(shù)據(jù)結(jié)構(gòu)算法知識，我決定在余下的在校時間里，認認真真學一門語言，并去詳細了解程序的算法設(shè)計。</p><p><b>　　使用說明</b></p><p>　　本程序是演示程序，在運行后按任意鍵即執(zhí)行演示過程，可直觀的看到程序運行時雙鏈表指針的變化情況，為方便觀察結(jié)果，在程序運行的時候，按一下執(zhí)行一步，也可以通過按Q鍵來退出程序，也可

59、以在等待所有過程結(jié)束后再退出。</p><p>　　1．進入程序后界面：</p><p>　　2．隨機產(chǎn)生結(jié)點，圖中已產(chǎn)生2個結(jié)點，由于57大于1，所以沒有右指針</p><p><b>　　3．指針變化情況</b></p><p>　　4．完成一個鏈表創(chuàng)建，下一結(jié)點插入中</p><p>　　5

60、．所有步驟完成后程序顯示界面，可清晰看到排序后的雙鏈表結(jié)果</p><p><b>　　附錄</b></p><p><b>　　源程序清單</b></p><p>　　#include "stdlib.h"</p><p>　　#include "graphics.

61、h"</p><p>　　typedef struct Link/*雙鏈表結(jié)點定義*/</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct Link *right;</p><p>　　s

62、truct Link *left;</p><p>　　int num;/*給鏈表加序號,為了演示時計算正確位置*/</p><p>　　}linkx,*linky;</p><p>　　void Init(void);/*圖形驅(qū)動*/</p><p>　　void Close(void);/*圖形關(guān)閉*/</p><p&

63、gt;　　void InitList(void);/*建立雙鏈表,邊建立邊插入*/</p><p>　　void PrLink(linky p,int n);/*每次插入后輸出鏈表*/</p><p>　　void DrawChange(int data,int i,int n);/*畫鏈表插入的指針變化*/</p><p>　　void main(void)<

64、;/p><p><b>　　{</b></p><p>　　Init();/*圖形關(guān)閉*/</p><p>　　InitList();/*建立鏈表*/</p><p>　　Close();/*圖形關(guān)閉*/</p><p><b>　　exit(0);</b></p>

65、<p><b>　　}</b></p><p>　　void InitList(void) /*建立雙向鏈表,邊建立邊插入*/</p><p><b>　　{</b></p><p>　　linky head,p,q,s;</p><p><b>　　int n=0;</

66、b></p><p>　　char str[5];</p><p>　　randomize();/*隨機數(shù)發(fā)生機*/</p><p>　　setcolor(BLUE);</p><p>　　outtextxy(200,20,"PERSS ANY KEY TO START");</p><p>

67、　　setcolor(RED);</p><p>　　outtextxy(400,30,"Press Q to quit");</p><p><b>　　getch();</b></p><p>　　head=s=(linky)malloc(sizeof(linkx));</p><p>　　s-&

68、gt;data=random(100);/*隨機生成100以內(nèi)的數(shù)字*/</p><p><b>　　s->num=n;</b></p><p>　　sprintf(str,"%d",s->data);/*將數(shù)字轉(zhuǎn)換成字符串并輸出*/</p><p>　　settextstyle(4,0,1);</p>

69、;<p>　　setcolor(WHITE);</p><p>　　outtextxy(50,50,"NodeData:");</p><p>　　outtextxy(50,70,"DoubleLinks:");</p><p>　　setcolor(10);</p><p>　　outt

70、extxy(155+n*35,50,str);/*顯示數(shù)據(jù)*/</p><p><b>　　getch();</b></p><p>　　s->right=NULL;</p><p>　　s->left=NULL;</p><p>　　PrLink(head,n);/*每次插入新數(shù)字后都顯示當前鏈表*/<

71、;/p><p><b>　　n++;</b></p><p>　　while(n!=8)</p><p><b>　　{</b></p><p>　　s=(linky)malloc(sizeof(linkx));</p><p>　　s->data=random(100);

72、</p><p><b>　　s->num=n;</b></p><p>　　sprintf(str,"%d",s->data);/*將數(shù)字轉(zhuǎn)換成字符串并輸出*/</p><p>　　setcolor(10);</p><p>　　outtextxy(155+n*35,50,str);&l

73、t;/p><p><b>　　getch();</b></p><p>　　p=head;/*每生成一個結(jié)點，將該結(jié)點插入到有序雙鏈表中*/</p><p>　　if(s->data<=head->data)/*小于頭結(jié)點，插在頭*/</p><p><b>　　{</b></p

74、><p>　　DrawChange(s->data,-1,n);/*顯示插入的具體過程*/</p><p>　　s->right=head;</p><p>　　s->left=NULL;</p><p><b>　　s->num=0;</b></p><p>　　head-&

75、gt;left=s;</p><p><b>　　head=s;</b></p><p>　　q=head->right;/*后面所有數(shù)的序號都加1，相當于數(shù)據(jù)后移*/</p><p>　　while(q!=NULL)</p><p><b>　　{</b></p><p&

76、gt;<b>　　q->num++;</b></p><p>　　q=q->right;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else/*其他情況*/</p><p><b

77、>　　{</b></p><p>　　while(s->data>p->data&&p!=NULL)</p><p><b>　　{</b></p><p><b>　　q=p;</b></p><p>　　p=p->right;</p

78、><p><b>　　}</b></p><p>　　if(p==NULL)/*這個數(shù)是當前最大的數(shù)，插在尾部*/</p><p><b>　　{</b></p><p>　　DrawChange(s->data,n-1,n);/*顯示插入的具體過程*/</p><p>　

79、　q->right=s;</p><p>　　s->right=NULL;</p><p>　　s->left=q;</p><p><b>　　s->num=n;</b></p><p><b>　　}</b></p><p>　　else /*結(jié)

80、點插入位置位于兩數(shù)之間*/</p><p><b>　　{</b></p><p>　　q->right->left=s;</p><p>　　s->right=q->right;</p><p>　　s->left=q;</p><p>　　q->right=

81、s;</p><p>　　s->num=q->num+1;</p><p>　　DrawChange(s->data,q->num,n);/*顯示插入的具體過程*/</p><p>　　/*后面所有數(shù)的序號都加1*/</p><p>　　s=s->right;</p><p>　　whil

82、e(s!=NULL)</p><p><b>　　{</b></p><p><b>　　s->num++;</b></p><p>　　s=s->right;</p><p><b>　　}</b></p><p><b>　　}

83、</b></p><p><b>　　}</b></p><p>　　PrLink(head,n);/*每次插入新數(shù)據(jù)后都顯示新鏈表*/</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p>&

84、lt;b>　　}</b></p><p>　　/*畫鏈表插入的具體過程，data是要插入的數(shù)據(jù)，i為插入結(jié)點前驅(qū)結(jié)點序號，n為當前結(jié)點個數(shù)，先將前驅(qū)結(jié)點和后繼之間的指針線擦除，顯示新結(jié)點插入過程，插入后擦除插入過程，恢復(fù)刪除的前驅(qū)結(jié)點的指針線*/</p><p>　　void DrawChange(int data,int i,int n)</p><

85、p><b>　　{</b></p><p>　　char str[5];</p><p>　　setfillstyle(SOLID_FILL,BLACK);</p><p>　　setcolor(RED);/*插入鏈表的新數(shù)據(jù)用紅色顯示*/</p><p>　　sprintf(str,"%d",

86、data);</p><p>　　outtextxy(55+70*i+35,100+n*50,str);/*輸出插入的位置*/</p><p>　　bar(50+70*i+35,100+(n-1)*50-20,50+70*i+65,100+(n-1)*50+20);</p><p>　　/*去除插入結(jié)點位置原結(jié)點間的指針線*/</p><p>

87、;　　setcolor(YELLOW);</p><p>　　if(i!=-1) /*不是插在頭，新結(jié)點的前驅(qū)指針線*/</p><p><b>　　{</b></p><p>　　line(50+70*i+34,100+n*50,50+70*i+30,100+n*50);</p><p>　　line(50+70*i+

88、30,100+n*50,50+70*i+30,100+n*50-25);</p><p>　　line(50+70*i+30,100+n*50-25,50+70*i+27,100+n*50-22);</p><p>　　line(50+70*i+30,100+n*50-25,50+70*i+33,100+n*50-22);</p><p><b>　　ge

89、tch();</b></p><p><b>　　}</b></p><p>　　if(i!=n-1)/*不是插在尾，新結(jié)點的后繼指針線*/</p><p><b>　　{</b></p><p>　　line(50+70*i+61,100+n*50,50+70*i+65,100+n*5

90、0);</p><p>　　line(50+70*i+65,100+n*50,50+70*i+65,100+n*50-25);</p><p>　　line(50+70*i+65,100+n*50-25,50+70*i+62,100+n*50-22);</p><p>　　line(50+70*i+65,100+n*50-25,50+70*i+68,100+n*50

91、-22);</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p>　　setcolor(6);</p><p>　　if(i!=-1)/*不是插在頭，新結(jié)點前驅(qū)結(jié)點的后繼指針線*/</p><p><b>　　

92、{</b></p><p>　　line(50+70*i+20,100+n*50-25,50+70*i+20,110+n*50);</p><p>　　line(50+70*i+20,110+n*50,50+70*i+34,110+n*50);</p><p>　　line(50+70*i+34,110+n*50,50+70*i+31,110+n*50-

93、3);</p><p>　　line(50+70*i+34,110+n*50,50+70*i+31,110+n*50+3);</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p>　　if(i!=n-1) /*不是插在尾，新結(jié)點后繼結(jié)點的前驅(qū)指

94、針線*/</p><p><b>　　{</b></p><p>　　line(50+70*i+75,100+n*50-25,50+70*i+75,110+n*50);</p><p>　　line(50+70*i+75,110+n*50,50+70*i+61,110+n*50);</p><p>　　line(50+7

95、0*i+61,110+n*50,50+70*i+64,110+n*50-3);</p><p>　　line(50+70*i+61,110+n*50,50+70*i+64,110+n*50+3);</p><p><b>　　}</b></p><p><b>　　getch();</b></p><p

96、>　　setcolor(WHITE);</p><p>　　if(i!=n-1&&i!=-1)/*第一個節(jié)點和最后一個結(jié)點不恢復(fù)指針*/</p><p><b>　　{</b></p><p>　　line(50+70*i+35,100+(n-1)*50,50+70*i+65,100+(n-1)*50);/*畫前驅(qū)指針*/

97、</p><p>　　line(50+70*i+35,100+(n-1)*50,50+70*i+40,95+(n-1)*50);</p><p>　　line(50+70*i+35,110+(n-1)*50,50+70*i+65,110+(n-1)*50);/*畫右指針*/</p><p>　　line(50+70*i+65,110+(n-1)*50,50+70*i

98、+60,115+(n-1)*50);</p><p><b>　　}</b></p><p>　　bar(0,100+(n-1)*50+21,640,120+n*50);/*擦掉插入過程的指針線*/</p><p><b>　　}</b></p><p>　　void PrLink(linky p,

99、int n)/*每次插入后輸出鏈表*/</p><p><b>　　{</b></p><p>　　char str[5];</p><p>　　while(p!=NULL)/*不為空就輸出*/</p><p><b>　　{</b></p><p>　　sprintf(st

100、r,"%d",p->data);</p><p>　　setcolor(GREEN);</p><p>　　outtextxy(55+70*p->num,100+n*50,str); /*輸出數(shù)據(jù)*/</p><p>　　setcolor(WHITE);</p><p>　　if(p->left!=NUL

101、L)/*第一個節(jié)點不顯示左指針*/</p><p><b>　　{</b></p><p>　　line(50+70*(p->num-1)+35,100+n*50,50+70*(p->num-1)+65,</p><p>　　100+n*50);/*畫左指針*/</p><p>　　line(50+70*(p

102、->num-1)+35,100+n*50,50+70*(p->num-1)+</p><p>　　40,95+n*50);</p><p><b>　　}</b></p><p>　　if(p->right!=NULL)</p><p><b>　　{</b></p>

103、<p>　　line(50+70*p->num+35,110+n*50,50+70*p->num+65,110+n*50);/*畫右指針*/</p><p>　　line(50+70*p->num+65,110+n*50,50+70*p->num+60,115+n*50);</p><p><b>　　}</b></p>

104、<p>　　p=p->right;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Init(void)/*圖形驅(qū)動*/</p><p><b>　　{</b></p><p&

105、gt;　　int gd=DETECT,gm;</p><p>　　initgraph(&gd,&gm,"c:\\tc"); </p><p>　　cleardevice();</p><p><b>　　}</b></p><p>　　void Close(void)/*圖形關(guān)閉*

106、/</p><p><b>　　{</b></p><p><b>　　getch();</b></p><p>　　closegraph();</p><p><b>　　}</b></p><p><b>　　參考文獻</b>&

107、lt;/p><p>　　嚴蔚敏，吳偉民， 《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，北京：清華大學出版社，2005</p><p>　　嚴蔚敏，吳偉民， 《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，北京：清華大學出版社，2003</p><p>　　郭翠英 等 《C語言課程設(shè)計案例精編》，北京：水利水電出版社，2004</p><p>　　計算機與通信學院課程設(shè)