




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告學(xué)號(hào)2014-2015學(xué)年 第一學(xué)期1208210146數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目:鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫的設(shè)計(jì)專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)班級(jí):12級(jí)計(jì)科(3)班姓名:指導(dǎo)教師:成績:計(jì)算機(jī)與信息工程系2014 年 12月 15 日目錄1 問題分析和任務(wù)定義11.1 任務(wù)定義11.2 面臨的問題,進(jìn)行分析解決,模塊之間的聯(lián)系。12概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)的選擇22.1 數(shù)據(jù)結(jié)構(gòu)的選擇22.2 結(jié)構(gòu)圖22.3 函數(shù)實(shí)現(xiàn)的具體算法舉例33 課程設(shè)計(jì)思路63.1 設(shè)計(jì)函數(shù)庫64 測試結(jié)果及其分析74.1 初始化74.2 逆序輸入元素84.3 單鏈表的長度84.4 遍歷輸出單鏈表84.5檢索查找
2、94.6輸入插入元素的值和位置94.7刪除元素105 小結(jié)10參考文獻(xiàn)10附錄:程序源代碼11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告1 問題分析和任務(wù)定義1.1 任務(wù)定義 設(shè)計(jì)出鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,以便在程序設(shè)計(jì)中調(diào)用。進(jìn)行鏈表中元素的輸入、查找、插入、刪除等操作的課程設(shè)計(jì)。要求: (1)所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間。(2)程序的運(yùn)行時(shí)間應(yīng)盡可能少。 從題目看出所設(shè)計(jì)的程序應(yīng)能達(dá)到的功能,設(shè)計(jì)好的程序要滿足以上兩點(diǎn)。在數(shù)據(jù)輸入方面可以根據(jù)鏈表的特點(diǎn)即存儲(chǔ)空間的連續(xù),從創(chuàng)建鏈表到插入,刪除,查找元素以及輸出一系列的步驟,連貫而下。算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu),所以選擇什么樣的存儲(chǔ)方式在課程設(shè)計(jì)中尤為
3、重要,這也是本程序好壞的一個(gè)評(píng)定。 1.2 面臨的問題,進(jìn)行分析解決,模塊之間的聯(lián)系。(1)在內(nèi)存中開辟一塊連續(xù)的內(nèi)存空間,進(jìn)行分析解決(2)利用物理位置的相鄰來表示變量,達(dá)到預(yù)期效果,很好的完成任務(wù)。查找元素以及輸出一系列的步驟,連貫而下。(3)使用鏈表的數(shù)據(jù)結(jié)構(gòu)來滿足盡可能節(jié)省存儲(chǔ)空間的要求,達(dá)到要求,從創(chuàng)建鏈表到插入,刪除,查找元素以及輸出一系列的步驟,連貫而下。(4)輸出界面設(shè)計(jì)與各個(gè)模塊的聯(lián)系,設(shè)計(jì)出鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,以便在程序設(shè)計(jì)中調(diào)用,進(jìn)行鏈表中元素的分析。02概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)的選擇2.1 數(shù)據(jù)結(jié)構(gòu)的選擇本程序選擇的數(shù)據(jù)結(jié)構(gòu)是線性表中的鏈?zhǔn)浇Y(jié)構(gòu)(單鏈表),原因如下:單鏈表的
4、定義:(1)單鏈表是線性表的鏈接存儲(chǔ)表示。其各個(gè)數(shù)據(jù)元素可以相繼存儲(chǔ),也可以不相繼存儲(chǔ),不過它為每個(gè)數(shù)據(jù)元素附加了一個(gè)鏈接指針,并形成的一個(gè)結(jié)點(diǎn)。(2) 單鏈表的每一個(gè)結(jié)點(diǎn)分為兩個(gè)部分:data和link。(3) 鏈表的第一個(gè)結(jié)點(diǎn)的地址可以通過鏈表的頭指針first找到,其他結(jié)點(diǎn)的地址則在前趨結(jié)點(diǎn)的link域中,鏈表的最后一個(gè)結(jié)點(diǎn)沒有后繼,在結(jié)點(diǎn)的link域中放一個(gè)空指針NULL。(4)頭指針first為空的單鏈表為空表,該鏈表一個(gè)結(jié)點(diǎn)也沒有,相對(duì)地,頭指針first不為空且首元結(jié)點(diǎn)存在的單鏈表為非空表,表中至少有一個(gè)結(jié)點(diǎn)。2.2 結(jié)構(gòu)圖創(chuàng)建單鏈表輸入數(shù)據(jù)插入數(shù)據(jù)刪除數(shù)據(jù)查找數(shù)據(jù)輸出數(shù)據(jù)計(jì)算表
5、長圖 1 結(jié)構(gòu)圖2.3 函數(shù)實(shí)現(xiàn)的具體算法舉例(1)插入函數(shù)/* 在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e */int Insert_List(LinkList L,int i,ElemType e) int j=0; LinkList p=L,s; while(p&&j<i-1) p=p->next; j+; if(!p|j>i-1) return ERROR; s=(LinkList)malloc(sizeof(struct LNode); s->data=e; s->next=p->next; p->next=s; re
6、turn OK; (2) 刪除函數(shù)int Delete_List(LinkList L,int i,ElemType *e) /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中,刪除第i個(gè)元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p->next&&j<i-1) p=p->next; j+; if(!p->next|j>i-1) return 0; q=p->next; p->next=q->next; *e=q->data; free(q); return 1; (3)查找元素/* 當(dāng)按位置查找
7、元素,第i個(gè)元素存在時(shí),其值賦給e并返回1,否則返回0 */ int GetElem_List(LinkList L,int i,ElemType *e) int j=0; LinkList p=L; while(p&&j<i) p=p->next; j+; if(!p|j>i) printf("鏈表不存在或參數(shù)i錯(cuò)"); return 0; *e=p->data; /* 取第i個(gè)元素 */ return 1; (5)顯示單鏈表int Disp_List(LinkList L)/*顯示單鏈表*/ LinkList p=L->ne
8、xt; if(p=Null) printf("單鏈表為空表"); else printf("輸出單鏈表:n"); while(p!=Null) printf("%d",p->data); printf("->"); p=p->next; printf("n"); return 1; (6)求單鏈表表長int Length_List(LinkList L) int i=0; LinkList p=L->next; while(p) i+; p=p->next; ret
9、urn i; 3 課程設(shè)計(jì)思路一般的說,其過程如下: A. 分析鏈表特點(diǎn) B. 分析鏈表功能以及操作 C. 設(shè)計(jì)函數(shù)庫 D. 制定調(diào)試計(jì)劃:初步調(diào)試計(jì)劃 E. 編寫主函數(shù),方便后面的測試 F. 制定完整的程序測試計(jì)劃 G. 書寫文檔,系統(tǒng)說明 H. 復(fù)查和審核:從技術(shù)的角度審查,從管理的角度審查3.1 設(shè)計(jì)函數(shù)庫設(shè)計(jì)函數(shù)庫不能隨心所欲,想編寫什么函數(shù)就編寫什么函數(shù),而是要根據(jù)分析鏈表所得結(jié)果,從分析結(jié)果入手,由分析我們知道鏈表可以進(jìn)行的操作有:輸入、輸出、插入一個(gè)元素、刪除一個(gè)元素、查找一個(gè)元素、取出一個(gè)元素。根據(jù)這些操作分別寫出函數(shù):int Insert_List(); /*插入元素*/in
10、t Delete_List(); /*刪除元素*/int GetElem_List(); /*查找元素*/int Disp_List(); /*顯示元素*/ int Length_List();/*求表長*/4 測試結(jié)果及其分析4.1 初始化圖2 初始化4.2 逆序輸入元素圖3 逆序輸入元素4.3 單鏈表的長度 圖4 計(jì)算長度4.4 遍歷輸出單鏈表圖 5遍歷4.5檢索查找 圖 6查找4.6輸入插入元素的值和位置圖 7插入4.7刪除元素圖 8 插入5 小結(jié)通過這次課設(shè),我學(xué)會(huì)了如何把數(shù)據(jù)結(jié)構(gòu)的知識(shí)應(yīng)用到實(shí)踐當(dāng)中,同時(shí)也進(jìn)一步加深了對(duì)c/c+語言語法的應(yīng)用,以及深刻的掌握了數(shù)據(jù)結(jié)構(gòu)和c/c+語言的
11、結(jié)合運(yùn)用。 在編程過程中,遇到了許多問題,在一次次的運(yùn)行錯(cuò)誤后,問題被一步步改正,也從中學(xué)到了許多知識(shí)。雖然我的程序還不夠完善,還需加以改進(jìn)以實(shí)現(xiàn)更多的功能,但是我會(huì)盡我最大的努力去完成它,我相信我會(huì)努力去把程序做的更加完美。參考文獻(xiàn) 1王昆侖,李紅等編著. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京:中國鐵道出版社,2007. 2蘇仕華等編著. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì). 北京:機(jī)械工業(yè)出版社 ,2005. 3蘇仕華編著. 數(shù)據(jù)結(jié)構(gòu)與算法解析.合肥:中國科學(xué)技術(shù)大學(xué)出版社,2004. 4郭嵩山等著國際大學(xué)生程序設(shè)計(jì)競賽例題解北京:電子工業(yè)出版社,2008.附錄:程序源代碼#include<stdlib.h>
12、#include<stdio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define Null 0typedef int ElemType; typedef struct LNode ElemType data; struct LNode *next; LNode ,*LinkList;/*初始化單鏈表,即產(chǎn)生一個(gè)帶頭結(jié)點(diǎn)的空表,創(chuàng)建成功則返回空表的頭指針*/LinkList Init_List(void) LinkList L; L=(LinkList) malloc(sizeof(LNode); if(
13、L) L->next=NULL; /產(chǎn)生空表,頭結(jié)點(diǎn)的next域?yàn)榭?return L; /*按逆序產(chǎn)生一個(gè)長度為n鏈表,參數(shù)為初始化的空鏈表,及線性表長度n*/*每個(gè)元素依次插入在頭結(jié)點(diǎn)后*/int Create_List(LinkList L,int n) int i; LinkList s; /*s變量用于保存新結(jié)點(diǎn)地址*/ printf("生成有%d個(gè)元素的線性表:n",n); for(i=n;i>0;i-) printf("請(qǐng)輸入線性表中第 %d 個(gè)元素:n",i); /*逆序輸入元素*/ s=(LinkList)malloc(si
14、zeof(LNode); if(!s) printf("創(chuàng)建結(jié)點(diǎn)不成功n"); return 0; scanf("%d",&s->data); s->next=L->next; L->next=s; return 1;/* 求單鏈表表長, 返回L中數(shù)據(jù)元素個(gè)數(shù) */ int Length_List(LinkList L) int i=0; LinkList p=L->next; while(p) i+; p=p->next; return i; /* 當(dāng)按位置查找元素,第i個(gè)元素存在時(shí),其值賦給e并返回1,否則
15、返回0 */ int GetElem_List(LinkList L,int i,ElemType *e) int j=0; LinkList p=L; while(p&&j<i) p=p->next; j+; if(!p|j>i) printf("鏈表不存在或參數(shù)i錯(cuò)"); return 0; *e=p->data; /* 取第i個(gè)元素 */ return 1; /* 按元素查找,查找鏈表中是否存在值為e的元素,存在,則返回L中第一個(gè)e元素的位序,若不存在,則返回值為0 */ int Locate_List(LinkList L,E
16、lemType e) int i=0; LinkList p=L; while(p&&p->data!=e) p=p->next; i+; if(p) return i; else return 0; /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e */int Insert_List(LinkList L,int i,ElemType e) int j=0; LinkList p=L,s; while(p&&j<i-1) p=p->next; j+; if(!p|j>i-1) return ERROR; s=(LinkLi
17、st)malloc(sizeof(struct LNode); s->data=e; s->next=p->next; p->next=s; return OK; int Delete_List(LinkList L,int i,ElemType *e) /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中,刪除第i個(gè)元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p->next&&j<i-1) p=p->next; j+; if(!p->next|j>i-1) return 0; q=p->ne
18、xt; p->next=q->next; *e=q->data; free(q); return 1; int Disp_List(LinkList L)/*顯示單鏈表*/ LinkList p=L->next; if(p=Null) printf("單鏈表為空表"); else printf("輸出單鏈表:n"); while(p!=Null) printf("%d",p->data); printf("->"); p=p->next; printf("n&qu
19、ot;); return 1; /*顯示選擇提示信息函數(shù)*/void ShowSelect() printf("n請(qǐng)選擇要執(zhí)行的操作:n"); printf("-n"); printf(" 1-初始化n"); printf(" 2-逆序輸入元素n"); printf(" 3-求單鏈表長度n"); printf(" 4-遍歷輸出單鏈表n"); printf(" 5-在單鏈表中檢索查找n"); printf(" 6-向單鏈表中插入元素n")
20、; printf(" 7-從單鏈表中刪除元素n"); printf(" 0- 退出n"); printf("-n"); printf("please input number 07 nn");int main(void)LinkList PL=NULL;int i,x,flag; int len; /*表示單鏈表長*/ int select; /*select變量表示用戶的選擇項(xiàng)*/ShowSelect();scanf("%d",&select);while(select!=0)switch(select)case 1: PL=Init_List(); break; case 2: printf("請(qǐng)輸入線性表中元素個(gè)數(shù):n");scanf("%d",&le
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 學(xué)校垃圾廢棄管理制度
- 醫(yī)院護(hù)士設(shè)備管理制度
- 醫(yī)院科室資金管理制度
- 做好臨時(shí)用電管理制度
- 噴淋設(shè)施安全管理制度
- 兒童培訓(xùn)宿舍管理制度
- 公司內(nèi)部糾紛管理制度
- 化工企業(yè)手機(jī)管理制度
- 小型企業(yè)財(cái)務(wù)管理制度
- 咸寧員工食堂管理制度
- 起重機(jī)服務(wù)協(xié)議合同協(xié)議
- 生物化學(xué)教學(xué)研究知識(shí)圖譜可視化分析
- 小學(xué)老師心理健康教育培訓(xùn)
- 正規(guī)監(jiān)控合同協(xié)議
- 高中生物2015-2024年10年高考真題專題分類匯編-專題6光合作用考點(diǎn)1捕獲光能的色素與結(jié)構(gòu)
- 廣東高考:化學(xué)必考知識(shí)點(diǎn)歸納
- 江蘇卷-2025屆高考地理4月模擬預(yù)測卷(解析版)
- 透射電鏡基本操作解答
- GB 19762-2025離心泵能效限定值及能效等級(jí)
- 大數(shù)據(jù)專業(yè)英語教程 課件 Unit 1 B Applications of Big Data
- 五臟排毒課件
評(píng)論
0/150
提交評(píng)論