數(shù)據(jù)結(jié)構(gòu)課程設計雙向鏈表

1、數(shù)據(jù)結(jié)構(gòu)課程設計實驗報告 題 目 雙向鏈表 學 院 專 業(yè) 計算機科學與技術 班 級 學 號 學生姓名 指導教師 編寫日期 2010-7-16 目錄1. 問題分析.31.1基本要求.31.2分析過程.32. 數(shù)據(jù)結(jié)構(gòu)描述.33. 算法設計.43.1算法1：雙向鏈表的建立.43.2算法2：雙向鏈表的查找43.3算法3：雙向鏈表的插入.53.4算法4：雙向鏈表的刪除.54. 程序清單65. 程序運行結(jié)果106. 總結(jié)11l 1.問題分析1.1【基本要求】：建立雙向鏈表，并進行插入，查找，刪除等操作。1.2【分析過程】：先通過創(chuàng)建函數(shù)建立雙向鏈表，由文本文件提供數(shù)據(jù)?？梢哉{(diào)用查找函數(shù)，查找與e值相同

2、的結(jié)點是否存在；也可以通過插入函數(shù)，在第i個結(jié)點前插入值為e的結(jié)點，并且調(diào)節(jié)指針的變化；也可以調(diào)用刪除函數(shù)，刪除第i個結(jié)點，調(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.算法設計3.1算法1：創(chuàng)建雙向鏈表status create_dul(dulinklist &l) /*利用尾插法建立頭帶頭結(jié)點的

3、雙向鏈表 */ l=(dulinklist)malloc(sizeof(dulnode); /* 生成頭結(jié)點 */ l-prior=null; l-next=null; /* 頭結(jié)點的指針域初始值為空 */ l-data=-1; q=l; /* 尾指針初始指向頭結(jié)點 */ 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é)點的數(shù)

4、據(jù) */ p-next=null; /* 新結(jié)點指針域為空 */ p-prior=q; q-next=p; /* 尾結(jié)點指針域指向新結(jié)點 */ q=p; /* q指針后移，始終指向尾指針 */ fclose(fp); /* 關閉文本文件 */3.2算法2：雙向鏈表的查找stadus locateelem_dul(dulinklist l,elemtype e) /* 查找雙線鏈表中第一個值為e的結(jié)點位置*/ p=l-next; /* p指向第一個結(jié)點 */ j=1; /* j表示結(jié)點位置 */ while(p-data!=e)&p) p=p-next; +j; /* 尋找第一個值為e的結(jié)點位置

5、 */ if(!p) return -1; else return 1;3.3算法3：雙向鏈表的插入status listinsert_dul(dulinklist &l,int i,elemtype e) /* 在雙向鏈表l中的第i個位置之前插入新結(jié)點s */ p=l; /* p指向頭結(jié)點 */ j=0; /* j表示結(jié)點位置 */ while(p&(jnext; +j; /* 尋找第i-1個結(jié)點位置 */ if(!p|ji-1) return error; /* 在l中確定插入位置，p=null或ji-1時，即插入位置不合法 */ if(!(s=(dulinklist)malloc(siz

6、eof(dulnode) return error; /* 動態(tài)生成新結(jié)點失敗，則返回錯誤 */ s-data=e; /* 給新結(jié)點的數(shù)據(jù)域賦值 */ s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; /* 在雙向鏈表中插入新結(jié)點時指針的變化 */ return 0;3.4算法4：雙向鏈表的刪除status listdelete_dul(dulinklist &l,int i,elemtype &e) /* 在雙向鏈表l中，刪除第i個結(jié)點 */ p=l-next; /* p指向第一個結(jié)點 */ int j=1; /* j表示結(jié)點位置 */

7、while(p&(jnext; +j; /* 尋找第i個結(jié)點 */ if(!p|ji) return error; /* 在l中確定第i個元素的位置指針p，p=null，即第i個元素不存在 */ e=p-data; /* 把指針p的數(shù)據(jù)域的值賦給e */ p-prior-next=p-next; p-next-prior=p-prior; /* 在雙向鏈表中刪除結(jié)點時指針的變化 */ free(p); /* 把結(jié)點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é)點的雙向鏈表 */ dulinklist p,q; int i; l=(dulinklist)malloc(sizeof(dulnode); /* 生成頭結(jié)點 */ l-prior=null; l-next=null; /* 頭結(jié)點的指針域初始值為空 */ l-data=-1; q=l; /* 尾指

9、針初始指向頭結(jié)點 */ 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é)點的數(shù)據(jù) */ p-next=null; /* 新結(jié)點指針域為空 */ p-prior=q; q-next=p; /* 尾結(jié)點指針域指向新結(jié)點 */ q=p; /* q指針后移，始終指向尾指針 */ fclose(fp); /* 關閉文本文件 */duli

10、nklist listinsert_dul(dulinklist &l,int i,int e) /* 在雙向鏈表l中的第i個位置之前插入新結(jié)點s */ dulinklist p,s; p=l; /* p指向頭結(jié)點 */ int j=0; /* j表示結(jié)點位置 */ while(p&(jnext; +j; /* 尋找第i-1個結(jié)點位置 */ if(!p|ji-1) return null; /* 在l中確定插入位置，p=null或ji-1時，即插入位置不合法 */ if(!(s=(dulinklist)malloc(sizeof(dulnode) return null; /* 動態(tài)生成新結(jié)點

11、失敗，則返回錯誤 */ s-data=e; /* 給新結(jié)點的數(shù)據(jù)域賦值 */ s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; /* 在雙向鏈表中插入新結(jié)點時指針的變化 */ return 0;dulinklist listdelete_dul(dulinklist &l,int i,int &e) /* 在雙向鏈表l中，刪除第i個結(jié)點 */ dulinklist p; p=l-next; /* p指向第一個結(jié)點 */ int j=1; /* j表示結(jié)點位置 */ while(p&(jnext; +j; /* 尋找第i個結(jié)點 */ if(!

12、p|ji) return null; /* 在l中確定第i個元素的位置指針p，p=null，即第i個元素不存在 */ e=p-data; /* 把指針p的數(shù)據(jù)域的值賦給e */ p-prior-next=p-next; p-next-prior=p-prior; /* 在雙向鏈表中刪除結(jié)點時指針的變化 */ free(p); /* 把結(jié)點p刪掉 */ return 0;int locateelem_dul(dulinklist l,int e) /* 查找雙線鏈表中第一個值為e的結(jié)點位置*/ dulinklist p; int j; p=l-next; /* p指向第一個結(jié)點 */ j=1;

13、/* j表示結(jié)點位置 */ while(p-data!=e)&p) p=p-next; +j; /* 尋找第一個值為e的結(jié)點位置 */ if(!p) return -1; /* 返回第一個值為e的結(jié)點位置 */ else return 1;void print_dul(dulinklist l) /* 打印雙向鏈表l */ dulinklist p; p=l; /* p指向頭結(jié)點 */ 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é)點的數(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é)點的位置 */ listdelete_dul(l,i,e); /* 調(diào)用雙向鏈表的刪除函數(shù) */ print_dul(l);break; /* 調(diào)用雙向鏈表的打印函數(shù) */ case 4: save_dul(l); exit(0); l 5.程序運行結(jié)果l 6.總結(jié): 通過此次數(shù)據(jù)結(jié)構(gòu)的課程設計，我對程序的編程，編譯，執(zhí)行等有了更深的認識。理解到思路對