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

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

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

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

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

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

6、ype struct dulnode elemtype data; struct dulnode *prior;struct dulnode *next; dulnode,*dulinklist;2.2輸入輸出由于本程序為演示程序，需用戶控制程序操作。輸出方面主要是顯示：經(jīng)指針移動所變化后得到的另一組新的元素。輸入方面：運用雙向循環(huán)鏈表，這樣子較優(yōu)與普通的雙向鏈表，省去一個表尾的指針，使查詢代碼更加清晰，程序也更加簡介。.3.程序流程圖3.1創(chuàng)建雙向鏈表如圖3.1所示 建立一個雙鏈表最后以0判斷是否結(jié)束接收數(shù)據(jù)。start建立一個雙向鏈表有p和s兩個指針來接收元素是否以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所示 查找元素，判斷位置是否合法，若合法進行查找運算。start引用dulinklist接收查找的元素位置雙鏈表中有此元素否是進行查找運算輸出數(shù)據(jù) return ok stop圖3.2 雙鏈表查找運算流程圖3.3插入新的元素如圖2.3所示 查找元素，判斷位置是否合法，若合法進行查插入運算。start引用dulinklist引用dulinklist接收插入元素以及位次雙鏈表中有合

8、適的位置否 否是進行插入運算 輸出數(shù)據(jù)return okstop圖3.3 雙鏈表插入運算流程圖3.4刪除一個元素如圖3.4所示刪除元素，判斷位置是否合法，若合法進行查刪除運算。start接收刪除的位次及元素雙向鏈表中有對應(yīng)的值 否 進行刪除運算是輸出數(shù)據(jù)return ok; stop圖3.4 雙鏈表刪除運算流程圖4概要設(shè)計4.1 程序模塊本程序?qū)崿F(xiàn)雙鏈表的創(chuàng)建、查找、插入、刪除、顯示、菜單為主的六個函數(shù)組成。大致分為：雙鏈表創(chuàng)建演示主程序，雙鏈表創(chuàng)建指針變化演示，結(jié)果輸出，三大模塊。4.2 課題涉及的數(shù)據(jù)結(jié)構(gòu)本課題所用到的數(shù)據(jù)結(jié)構(gòu)主要是雙向鏈表4.2.1 雙鏈表結(jié)點的插入 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é)點的刪除 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è)計體會 程序調(diào)試中遇到的問題以及解決問題的方法。主要是在結(jié)點插入判斷方面有難度，一開始不能準(zhǔn)確的進行結(jié)點的判斷和插入，然后就是插入結(jié)點的過程中位置不對，后面在網(wǎng)上找到了一段演示代碼，通過研究這段代碼解決了這個問題。還有就是在顯示指針變化方面有問題，經(jīng)過查詢資料，解決結(jié)點插入方面的問題，用畫箭頭的方式來表現(xiàn)指針的變化。在運行程序時發(fā)現(xiàn)程序不能對不合法的位置進行判斷，最后通過修改加上一個計數(shù)的變量解決了這個問題。6源程序代碼#include#include#include#define list_init_size 100 /線性表存儲空

11、間的初始分配量#define listincrement 10 /線性表存儲空間的增配量#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(請輸入元素(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沒有這個元素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); /*運行前清屏*/ 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(請輸入查找的元素：); 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(請輸入插入元素); 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.程序運行結(jié)果 本程序是演示程序，根據(jù)提示輸入數(shù)據(jù)，也可以在等待所有過程結(jié)束后再退出。7.1創(chuàng)建雙鏈表如圖7.1所示 用戶進入菜單開始操作程序 圖7.1 菜單7.2 輸入元素如圖7.2所示 用戶輸入元素最后以0結(jié)束 圖7.2 在雙鏈表中輸入元素7.3 查找一個不屬于鏈表的值如圖7.3

19、所示 用戶輸出一個不合法的位置 圖7.3 不合法的查找7.4 正確的查找如圖7.4所示 用戶輸入正確的位置并且輸出正確的結(jié)果 圖7.4 查找成功7.5不合法的插入一個數(shù) 如圖7.5所示 用戶輸入一個不合法的插入位次圖7.5 不合法的插入7.6正確的插入一個數(shù) 如圖7.6所示 用戶輸入一個正確的位次并且輸出正確的結(jié)果 圖7.6 插入成功7.7刪除不合法的位次如圖7.7所示 用戶輸入一個不合法的刪除位次圖7.7不合法的刪除7.8刪除位次如圖7.8所示 用戶輸入正確的刪除位次并且刪除所選元素 圖7.8 刪除成功總結(jié)在進行本次課程設(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)在編程感覺完全不同了。在編寫一個程序之前，