




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告 題 目 雙向鏈表 學(xué) 院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級 學(xué) 號 學(xué)生姓名 指導(dǎo)教師 編寫日期 2010-7-16 目錄1. 問題分析.31.1基本要求.31.2分析過程.32. 數(shù)據(jù)結(jié)構(gòu)描述.33. 算法設(shè)計(jì).43.1算法1:雙向鏈表的建立.43.2算法2:雙向鏈表的查找43.3算法3:雙向鏈表的插入.53.4算法4:雙向鏈表的刪除.54. 程序清單65. 程序運(yùn)行結(jié)果106. 總結(jié)11l 1.問題分析1.1【基本要求】:建立雙向鏈表,并進(jìn)行插入,查找,刪除等操作。1.2【分析過程】:先通過創(chuàng)建函數(shù)建立雙向鏈表,由文本文件提供數(shù)據(jù)??梢哉{(diào)用查找函數(shù),查找與e值相同
2、的結(jié)點(diǎn)是否存在;也可以通過插入函數(shù),在第i個(gè)結(jié)點(diǎn)前插入值為e的結(jié)點(diǎn),并且調(diào)節(jié)指針的變化;也可以調(diào)用刪除函數(shù),刪除第i個(gè)結(jié)點(diǎn),調(diào)節(jié)好指針,最后通過保存函數(shù)保留數(shù)據(jù)到文本文件中。l 2.數(shù)據(jù)結(jié)構(gòu)描述#include#includeusing namespace std;typedef struct dulnode int data; struct dulnode *prior; struct dulnode *next; dulnode,*dulinklist;l 3.算法設(shè)計(jì)3.1算法1:創(chuàng)建雙向鏈表status create_dul(dulinklist &l) /*利用尾插法建立頭帶頭結(jié)點(diǎn)的
3、雙向鏈表 */ l=(dulinklist)malloc(sizeof(dulnode); /* 生成頭結(jié)點(diǎn) */ l-prior=null; l-next=null; /* 頭結(jié)點(diǎn)的指針域初始值為空 */ l-data=-1; q=l; /* 尾指針初始指向頭結(jié)點(diǎn) */ file* fp; /* 定義文件指針的形式 */ if(fp=fopen(f:test1.txt,r+)=null) /* 打開文本文件 */ printf(cannot open file!n); exit(0); int n; fscanf(fp,%d,&n); for(i=0;idata); /* 在文件讀取結(jié)點(diǎn)的數(shù)
4、據(jù) */ p-next=null; /* 新結(jié)點(diǎn)指針域?yàn)榭?*/ p-prior=q; q-next=p; /* 尾結(jié)點(diǎn)指針域指向新結(jié)點(diǎn) */ q=p; /* q指針后移,始終指向尾指針 */ fclose(fp); /* 關(guān)閉文本文件 */3.2算法2:雙向鏈表的查找stadus locateelem_dul(dulinklist l,elemtype e) /* 查找雙線鏈表中第一個(gè)值為e的結(jié)點(diǎn)位置*/ p=l-next; /* p指向第一個(gè)結(jié)點(diǎn) */ j=1; /* j表示結(jié)點(diǎn)位置 */ while(p-data!=e)&p) p=p-next; +j; /* 尋找第一個(gè)值為e的結(jié)點(diǎn)位置
5、 */ if(!p) return -1; else return 1;3.3算法3:雙向鏈表的插入status listinsert_dul(dulinklist &l,int i,elemtype e) /* 在雙向鏈表l中的第i個(gè)位置之前插入新結(jié)點(diǎn)s */ p=l; /* p指向頭結(jié)點(diǎn) */ j=0; /* j表示結(jié)點(diǎn)位置 */ while(p&(jnext; +j; /* 尋找第i-1個(gè)結(jié)點(diǎn)位置 */ if(!p|ji-1) return error; /* 在l中確定插入位置,p=null或ji-1時(shí),即插入位置不合法 */ if(!(s=(dulinklist)malloc(siz
6、eof(dulnode) return error; /* 動(dòng)態(tài)生成新結(jié)點(diǎn)失敗,則返回錯(cuò)誤 */ s-data=e; /* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值 */ s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; /* 在雙向鏈表中插入新結(jié)點(diǎn)時(shí)指針的變化 */ return 0;3.4算法4:雙向鏈表的刪除status listdelete_dul(dulinklist &l,int i,elemtype &e) /* 在雙向鏈表l中,刪除第i個(gè)結(jié)點(diǎn) */ p=l-next; /* p指向第一個(gè)結(jié)點(diǎn) */ int j=1; /* j表示結(jié)點(diǎn)位置 */
7、while(p&(jnext; +j; /* 尋找第i個(gè)結(jié)點(diǎn) */ if(!p|ji) return error; /* 在l中確定第i個(gè)元素的位置指針p,p=null,即第i個(gè)元素不存在 */ e=p-data; /* 把指針p的數(shù)據(jù)域的值賦給e */ p-prior-next=p-next; p-next-prior=p-prior; /* 在雙向鏈表中刪除結(jié)點(diǎn)時(shí)指針的變化 */ free(p); /* 把結(jié)點(diǎn)p刪掉 */ return 0;l 4.程序清單#include#includeusing namespace std;typedef struct dulnode int data
8、; /* 數(shù)據(jù)域 */ struct dulnode *prior; /* 指向前驅(qū)的指針域 */ struct dulnode *next; /* 指向后繼的指針域 */dulnode,*dulinklist;void create_dul(dulinklist &l) /*利用尾插法建立頭帶頭結(jié)點(diǎn)的雙向鏈表 */ dulinklist p,q; int i; l=(dulinklist)malloc(sizeof(dulnode); /* 生成頭結(jié)點(diǎn) */ l-prior=null; l-next=null; /* 頭結(jié)點(diǎn)的指針域初始值為空 */ l-data=-1; q=l; /* 尾指
9、針初始指向頭結(jié)點(diǎn) */ file* fp; /* 定義文件指針的形式 */ if(fp=fopen(h:test1.txt,r+)=null) /* 打開文本文件 */ printf(cannot open file!n); exit(0); int n; fscanf(fp,%d,&n); for(i=0;idata); /* 在文件讀取結(jié)點(diǎn)的數(shù)據(jù) */ p-next=null; /* 新結(jié)點(diǎn)指針域?yàn)榭?*/ p-prior=q; q-next=p; /* 尾結(jié)點(diǎn)指針域指向新結(jié)點(diǎn) */ q=p; /* q指針后移,始終指向尾指針 */ fclose(fp); /* 關(guān)閉文本文件 */duli
10、nklist listinsert_dul(dulinklist &l,int i,int e) /* 在雙向鏈表l中的第i個(gè)位置之前插入新結(jié)點(diǎn)s */ dulinklist p,s; p=l; /* p指向頭結(jié)點(diǎn) */ int j=0; /* j表示結(jié)點(diǎn)位置 */ while(p&(jnext; +j; /* 尋找第i-1個(gè)結(jié)點(diǎn)位置 */ if(!p|ji-1) return null; /* 在l中確定插入位置,p=null或ji-1時(shí),即插入位置不合法 */ if(!(s=(dulinklist)malloc(sizeof(dulnode) return null; /* 動(dòng)態(tài)生成新結(jié)點(diǎn)
11、失敗,則返回錯(cuò)誤 */ s-data=e; /* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值 */ s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; /* 在雙向鏈表中插入新結(jié)點(diǎn)時(shí)指針的變化 */ return 0;dulinklist listdelete_dul(dulinklist &l,int i,int &e) /* 在雙向鏈表l中,刪除第i個(gè)結(jié)點(diǎn) */ dulinklist p; p=l-next; /* p指向第一個(gè)結(jié)點(diǎn) */ int j=1; /* j表示結(jié)點(diǎn)位置 */ while(p&(jnext; +j; /* 尋找第i個(gè)結(jié)點(diǎn) */ if(!
12、p|ji) return null; /* 在l中確定第i個(gè)元素的位置指針p,p=null,即第i個(gè)元素不存在 */ e=p-data; /* 把指針p的數(shù)據(jù)域的值賦給e */ p-prior-next=p-next; p-next-prior=p-prior; /* 在雙向鏈表中刪除結(jié)點(diǎn)時(shí)指針的變化 */ free(p); /* 把結(jié)點(diǎn)p刪掉 */ return 0;int locateelem_dul(dulinklist l,int e) /* 查找雙線鏈表中第一個(gè)值為e的結(jié)點(diǎn)位置*/ dulinklist p; int j; p=l-next; /* p指向第一個(gè)結(jié)點(diǎn) */ j=1;
13、/* j表示結(jié)點(diǎn)位置 */ while(p-data!=e)&p) p=p-next; +j; /* 尋找第一個(gè)值為e的結(jié)點(diǎn)位置 */ if(!p) return -1; /* 返回第一個(gè)值為e的結(jié)點(diǎn)位置 */ else return 1;void print_dul(dulinklist l) /* 打印雙向鏈表l */ dulinklist p; p=l; /* p指向頭結(jié)點(diǎn) */ while(p) printf(% d,p-data); p=p-next; /* 把雙向鏈表中的數(shù)據(jù)都打印出來 */void save_dul(dulinklist l) file* fp; if(fp=fo
14、pen(h:test2.txt,w+)=null) printf(cannot open file!n); exit(0); while(l)fprintf(fp,%d ,l-data);l = l-next;void main() dulinklist l; int i,e,x; int pos;create_dul(l); /* 調(diào)用雙向鏈表建立函數(shù) */ print_dul(l); /* 調(diào)用雙向鏈表的打印函數(shù) */ while(1) printf(input x to choose (1.查找,2.插入,3.刪除,4.0ver ): n); scanf(%d,&x); switch(x
15、)case 1:printf(n please input the data you want to locate: n); scanf(%d,&e); /* 輸入要查找的值 */ pos=locateelem_dul(l,e); /* 調(diào)用雙向鏈表的查找函數(shù) */ if(pos=-1) printf(the data is not found! n); else printf(the data is found! n);break;case 2: printf(please input the position you want to insert: n); scanf(%d,&i); /*
16、 輸入要插入的位置 */ printf(please input the data you want to insert: n); scanf(%d,&e); /* 輸入新結(jié)點(diǎn)的數(shù)據(jù) */ listinsert_dul(l,i,e); /* 調(diào)用雙向鏈表的插入函數(shù) */ print_dul(l); break; /* 調(diào)用雙向鏈表的打印函數(shù) */ case 3: printf(n please input the position you want to delete: n); scanf(%d,&i); /* 輸入要?jiǎng)h除結(jié)點(diǎn)的位置 */ listdelete_dul(l,i,e); /* 調(diào)用雙向鏈表的刪除函數(shù) */ print_dul(l);break; /* 調(diào)用雙向鏈表的打印函數(shù) */ case 4: save_dul(l); exit(0); l 5.程序運(yùn)行結(jié)果l 6.總結(jié): 通過此次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì),我對程序的編程,編譯,執(zhí)行等有了更深的認(rèn)識。理解到思路對于一個(gè)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年秋季新人教版8年級上冊物理全冊教學(xué)課件
- 雅思四個(gè)月復(fù)習(xí)計(jì)劃
- 最佳森林管理計(jì)劃
- 2025至2030年中國天然深海魚油數(shù)據(jù)監(jiān)測研究報(bào)告
- 2025至2030年中國嘴棒成型膠數(shù)據(jù)監(jiān)測研究報(bào)告
- 2025至2030年中國雙門多功能槍支保險(xiǎn)柜數(shù)據(jù)監(jiān)測研究報(bào)告
- 2025至2030年中國單孔雙柄臺盆龍頭數(shù)據(jù)監(jiān)測研究報(bào)告
- 兒童醫(yī)療遠(yuǎn)程醫(yī)療服務(wù)行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 成匹編帶、裝飾帶企業(yè)數(shù)字化轉(zhuǎn)型與智慧升級戰(zhàn)略研究報(bào)告
- 風(fēng)能風(fēng)電企業(yè)數(shù)字化轉(zhuǎn)型與智慧升級戰(zhàn)略研究報(bào)告
- 【寒假開學(xué)第一課】AI時(shí)代做自己的哪吒
- 《教育強(qiáng)國建設(shè)規(guī)劃綱要(2024-2035年)》全文
- 《真希望你也喜歡自己》房琪-讀書分享
- 2024年山東省高考生物試卷真題(含答案解析)
- 2024-2025學(xué)年全國中學(xué)生天文知識競賽考試題庫(含答案)
- 小學(xué)科學(xué)湘科版六年級下冊全冊同步練習(xí)含答案
- 思維第一:全面提升學(xué)習(xí)力
- 最新版結(jié)婚函調(diào)報(bào)告表.doc
- 紙張克重、厚度對照表
- 主斜井架空乘人裝置安裝安全技術(shù)措施方案
- 《鐵路橋梁檢定評估工作規(guī)則》鐵運(yùn)2004第42號
評論
0/150
提交評論