課程設(shè)計(jì)雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說(shuō)明書(shū)雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn) 學(xué)生姓名張?chǎng)螌W(xué)號(hào)1021024077班級(jí)信管103成績(jī)指導(dǎo)教師李婧數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2012年3月2日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書(shū)題目雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn)學(xué)生姓名張?chǎng)螌W(xué)號(hào)1021024077指導(dǎo)教師評(píng)語(yǔ)及成績(jī)指導(dǎo)教師簽名： 年 月 日答辯評(píng)語(yǔ)及成績(jī)答辯教師簽名： 年 月 日教研室意見(jiàn)：總成績(jī)： 室主任簽名：年 月 日課程設(shè)計(jì)任務(wù)書(shū)20112012學(xué)年第二學(xué)期專業(yè)： 信息管理與信息系統(tǒng) 學(xué)號(hào)： 1021024077 姓名： 張?chǎng)?課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè) 計(jì) 題 目： 雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn) 完 成

2、期 限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 設(shè)計(jì)要求、設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁(yè)）：設(shè)計(jì)內(nèi)容：雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn)，雙鏈表具有雙向鏈接的特點(diǎn)，克服了單鏈表的單向性。要求通過(guò)結(jié)構(gòu)體類型建立空的雙鏈表，在此基礎(chǔ)上調(diào)用函數(shù)實(shí)現(xiàn)雙鏈表的建立、插入、查找和刪除等基本操作。設(shè)計(jì)要求：1.遵循結(jié)構(gòu)化程序設(shè)計(jì)思想，采用c/c+實(shí)現(xiàn)。 2.界面友好，操作簡(jiǎn)便，容錯(cuò)性好。 指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 年 月 日摘要本課題主要討論在鏈?zhǔn)浇Y(jié)構(gòu)中建立雙向鏈表。雙向鏈表有兩個(gè)指針域，其一指向直接前趨，另一指向直接后繼。并合理利用插

3、入、查找、刪除運(yùn)算。和單鏈的循環(huán)表類似，雙鏈表也可以有相應(yīng)的循環(huán)表。用一個(gè)表頭單元將雙鏈表首尾相接，即將表頭單元中的head指針指向表尾，并將表尾單元的next指針指向表頭單元。關(guān)鍵詞：雙向鏈表；鏈?zhǔn)浇Y(jié)構(gòu)；直接前趨；直接后繼目 錄1.課題描述12需求分析22.1程序功能說(shuō)明22.2輸入輸出23.程序流程圖33.1創(chuàng)建雙向鏈表33.2按位次查找43.3插入新的元素53.4刪除一個(gè)元素64概要設(shè)計(jì)74.1 程序模塊74.2 課題涉及的數(shù)據(jù)結(jié)構(gòu)74.2.1 雙鏈表結(jié)點(diǎn)的插入74.2.2 雙鏈表結(jié)點(diǎn)的刪除75. 調(diào)試分析以及設(shè)計(jì)體會(huì)86源程序代碼97.程序運(yùn)行結(jié)果147.1創(chuàng)建雙鏈表147.2 輸入元

4、素157.3 查找一個(gè)不屬于鏈表的值167.4 正確的查找177.5不合法的插入一個(gè)數(shù)187.6正確的插入一個(gè)數(shù)197.7刪除不合法的位次207.8刪除位次21總結(jié)22參考文獻(xiàn)231.課題描述雙（向）鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接前趨的指針域prior。雙鏈表有以下特點(diǎn)：雙鏈表由頭指針head惟一確定的。 帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。 將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)，為雙（向）循環(huán)鏈表。2需求分析2.1程序功能說(shuō)明鏈表是線性表的鏈?zhǔn)奖硎荆捎谒灰筮壿嬌舷噜彽脑卦谖锢砦恢蒙弦蚕噜?，所以它沒(méi)有順序存儲(chǔ)結(jié)構(gòu)在做插入刪除操作時(shí)需要移動(dòng)

5、大量元素的弱點(diǎn)。 雙鏈表的結(jié)點(diǎn)中有兩個(gè)指針域， 一個(gè)指向直接后繼， 一個(gè)指向直接前驅(qū)。本程序包括了的功能有：查找、插入、刪除。在單循環(huán)鏈表中，雖然從任一單元出發(fā)，可以找到其前驅(qū)單元，但需要o(n)時(shí)間。如果我們希望能快速確定表中任一個(gè)元素的前驅(qū)和后繼元素所在的單元，可以在鏈表的每個(gè)單元中設(shè)置兩個(gè)指針，一個(gè)指向后繼，另一個(gè)指向前驅(qū)，形成如圖2.1所示的雙向鏈表或簡(jiǎn)稱為雙鏈表。圖2.1雙鏈表示意圖由于在雙鏈表中可以直接確定一個(gè)單元的前驅(qū)單元和后繼單元，我們可以用一種更自然的方式表示元素的位置，即用指向雙鏈表中第i個(gè)單元而不是指向其前一個(gè)單元的指針來(lái)表示表的第i個(gè)位置。雙鏈表的單元類型定義如下： t

6、ype struct dulnode elemtype data; struct dulnode *prior;struct dulnode *next; dulnode,*dulinklist;2.2輸入輸出由于本程序?yàn)檠菔境绦?，需用戶控制程序操作。輸出方面主要是顯示：經(jīng)指針移動(dòng)所變化后得到的另一組新的元素。輸入方面：運(yùn)用雙向循環(huán)鏈表，這樣子較優(yōu)與普通的雙向鏈表，省去一個(gè)表尾的指針，使查詢代碼更加清晰，程序也更加簡(jiǎn)介。.3.程序流程圖3.1創(chuàng)建雙向鏈表如圖3.1所示 建立一個(gè)雙鏈表最后以0判斷是否結(jié)束接收數(shù)據(jù)。start建立一個(gè)雙向鏈表有p和s兩個(gè)指針來(lái)接收元素是否以0結(jié)束 是否 繼續(xù)接收數(shù)

7、據(jù) s-data=x; s-next=p-next; s-prior=p; p-next-prior=s; p-next=s; p=s; return ok stop圖3.1 創(chuàng)建雙鏈表流程圖 3.2按位次查找如圖2.2所示 查找元素，判斷位置是否合法，若合法進(jìn)行查找運(yùn)算。start引用dulinklist接收查找的元素位置雙鏈表中有此元素否是進(jìn)行查找運(yùn)算輸出數(shù)據(jù) return ok stop圖3.2 雙鏈表查找運(yùn)算流程圖3.3插入新的元素如圖2.3所示 查找元素，判斷位置是否合法，若合法進(jìn)行查插入運(yùn)算。start引用dulinklist引用dulinklist接收插入元素以及位次雙鏈表中有合

8、適的位置否 否是進(jìn)行插入運(yùn)算 輸出數(shù)據(jù)return okstop圖3.3 雙鏈表插入運(yùn)算流程圖3.4刪除一個(gè)元素如圖3.4所示刪除元素，判斷位置是否合法，若合法進(jìn)行查刪除運(yùn)算。start接收刪除的位次及元素雙向鏈表中有對(duì)應(yīng)的值 否 進(jìn)行刪除運(yùn)算是輸出數(shù)據(jù)return ok; stop圖3.4 雙鏈表刪除運(yùn)算流程圖4概要設(shè)計(jì)4.1 程序模塊本程序?qū)崿F(xiàn)雙鏈表的創(chuàng)建、查找、插入、刪除、顯示、菜單為主的六個(gè)函數(shù)組成。大致分為：雙鏈表創(chuàng)建演示主程序，雙鏈表創(chuàng)建指針變化演示，結(jié)果輸出，三大模塊。4.2 課題涉及的數(shù)據(jù)結(jié)構(gòu)本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表4.2.1 雙鏈表結(jié)點(diǎn)的插入 status lis

9、tinsert_dul(dulinklist &;l, int i, elemtype e) if(!(s=(dulinklist)malloc(sizeof(dulnode) return error;s-data=e; s-prior=p-prior; p-piror-next=s; s-next=p; p-prior=s; return ok; 4.2.2 雙鏈表結(jié)點(diǎn)的刪除 status listdelete_dul(dulinklist&;l,int i,elemtype &;e) e=p-data; p-prior-next=p-next; p-next-prior=p-prior;

10、 free(p); return ok;5. 調(diào)試分析以及設(shè)計(jì)體會(huì) 程序調(diào)試中遇到的問(wèn)題以及解決問(wèn)題的方法。主要是在結(jié)點(diǎn)插入判斷方面有難度，一開(kāi)始不能準(zhǔn)確的進(jìn)行結(jié)點(diǎn)的判斷和插入，然后就是插入結(jié)點(diǎn)的過(guò)程中位置不對(duì)，后面在網(wǎng)上找到了一段演示代碼，通過(guò)研究這段代碼解決了這個(gè)問(wèn)題。還有就是在顯示指針變化方面有問(wèn)題，經(jīng)過(guò)查詢資料，解決結(jié)點(diǎn)插入方面的問(wèn)題，用畫(huà)箭頭的方式來(lái)表現(xiàn)指針的變化。在運(yùn)行程序時(shí)發(fā)現(xiàn)程序不能對(duì)不合法的位置進(jìn)行判斷，最后通過(guò)修改加上一個(gè)計(jì)數(shù)的變量解決了這個(gè)問(wèn)題。6源程序代碼#include#include#include#define list_init_size 100 /線性表存儲(chǔ)空

11、間的初始分配量#define listincrement 10 /線性表存儲(chǔ)空間的增配量#define ok 1#define error 0#define overflow -2typedef struct dulnodeint data;struct dulnode *prior, *next;int l;dulinklist;dulinklist *head;int putyuansu_dul(dulinklist &l) dulinklist *p,*s; int x; head=(dulinklist*)malloc(sizeof(dulinklist); head-data=-1;

12、 head-next=head; head-prior=head; p=head; l.l=0; printf(請(qǐng)輸入元素(0 結(jié)束)n); scanf(%d,&x); while(x!=0) s=(dulinklist*)malloc(sizeof(dulinklist); s-data=x; s-next=p-next; s-prior=p; p-next-prior=s; p-next=s; p=s; scanf(%d,&x); l.l+; return ok;void display_dul(dulinklist &l)dulinklist * p=head-next;while(p!

13、=head)printf(%d ,p-data);p=p-next;printf(n);int locate_dul(dulinklist &l,int e) /查找 dulinklist * p=head-next; int i=1;if(p=null) return error; while(p-data!=e& p-next!=head) /尋找值為x的元素 p=p-next; i+; if(p-data=e) printf(查找出的位次是：%d n,i); else printf(t沒(méi)有這個(gè)元素n); return ok;int listinsert_dul(dulinklist &l

14、,int i,int e) /插入 int j;j=0;dulinklist *p=head-next,*s;while(p-next!=head)&(jnext;j+;if(i0)&(j=i-1) s=(dulinklist*)malloc(sizeof(dulinklist);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s; display_dul(l);return ok;int listdelet_dul(dulinklist &l,int i) /刪除 int e,j=0; dulinklist *p=head-n

15、ext;while(p-next!=head)&(jnext;j+; if(i0)&(j=i)e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);display_dul(l);return ok;int menu_select() int a; dosystem(cls); /*運(yùn)行前清屏*/ printf(tt*查找、插入、刪除 system*n); /*菜單選擇*/ printf(tt | 1. 輸入元素 n); printf(tt | 2. 查找 n); printf(tt | 3. 插入 n); printf(tt | 4

16、. 刪除 n); printf(tt | 5. 顯示數(shù)據(jù) n); printf(tt | 6. quit n); printf(tttgive your choice(1-6):); scanf(%d,&a); while(a6); return (a);int main(int argc, char* argv) dulinklist l;for(;) switch(menu_select() int e,i; case 1:putyuansu_dul(l); system(pause); break; case 2:printf(請(qǐng)輸入查找的元素：); scanf(%d,&e); loca

17、te_dul(l,e); system(pause); break; case 3:printf(輸入插入的數(shù)的位次); scanf(%d,&i); if(il.l) printf(t輸入不合法t); system(pause); break; printf(請(qǐng)輸入插入元素); scanf(%d,&e); listinsert_dul(l,i,e); system(pause); break; case 4:printf(輸入刪除的位次); scanf(%d,&i); if(il.l) printf(t輸入不合法t); system(pause); break; listdelet_dul(l

18、,i); system(pause); break; case 5:display_dul(l); system(pause); case 6:printf(ttthave a good luck,bye-bye!n); printf(ttt); system(pause); exit(0); return 0;7.程序運(yùn)行結(jié)果 本程序是演示程序，根據(jù)提示輸入數(shù)據(jù)，也可以在等待所有過(guò)程結(jié)束后再退出。7.1創(chuàng)建雙鏈表如圖7.1所示 用戶進(jìn)入菜單開(kāi)始操作程序 圖7.1 菜單7.2 輸入元素如圖7.2所示 用戶輸入元素最后以0結(jié)束 圖7.2 在雙鏈表中輸入元素7.3 查找一個(gè)不屬于鏈表的值如圖7.3

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