數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫的設(shè)計(jì)

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