1、數據結構課程設計報告學號2014-2015學年 第一學期1208210146數據結構課程設計報告題目：鏈表結構的相關函數庫的設計專業：計算機科學與技術班級：12級計科（3）班姓名：指導教師：成績：計算機與信息工程系2014 年 12月 15 日目錄1 問題分析和任務定義11.1 任務定義11.2 面臨的問題，進行分析解決，模塊之間的聯系。12概要設計和數據結構的選擇22.1 數據結構的選擇22.2 結構圖22.3 函數實現的具體算法舉例33 課程設計思路63.1 設計函數庫64 測試結果及其分析74.1 初始化74.2 逆序輸入元素84.3 單鏈表的長度84.4 遍歷輸出單鏈表84.5檢索查找

2、94.6輸入插入元素的值和位置94.7刪除元素105 小結10參考文獻10附錄：程序源代碼11數據結構課程設計報告1 問題分析和任務定義1.1 任務定義 設計出鏈表結構的相關函數庫，以便在程序設計中調用。進行鏈表中元素的輸入、查找、插入、刪除等操作的課程設計。要求： （1）所設計的數據結構應盡可能節省存儲空間。（2）程序的運行時間應盡可能少。 從題目看出所設計的程序應能達到的功能，設計好的程序要滿足以上兩點。在數據輸入方面可以根據鏈表的特點即存儲空間的連續，從創建鏈表到插入，刪除，查找元素以及輸出一系列的步驟，連貫而下。算法的實現依賴于所采用的存儲結構，所以選擇什么樣的存儲方式在課程設計中尤為

3、重要，這也是本程序好壞的一個評定。 1.2 面臨的問題，進行分析解決，模塊之間的聯系。（1）在內存中開辟一塊連續的內存空間，進行分析解決（2）利用物理位置的相鄰來表示變量，達到預期效果，很好的完成任務。查找元素以及輸出一系列的步驟，連貫而下。（3）使用鏈表的數據結構來滿足盡可能節省存儲空間的要求，達到要求，從創建鏈表到插入，刪除，查找元素以及輸出一系列的步驟，連貫而下。（4）輸出界面設計與各個模塊的聯系，設計出鏈表結構的相關函數庫，以便在程序設計中調用，進行鏈表中元素的分析。02概要設計和數據結構的選擇2.1 數據結構的選擇本程序選擇的數據結構是線性表中的鏈式結構（單鏈表），原因如下：單鏈表的

4、定義：（1）單鏈表是線性表的鏈接存儲表示。其各個數據元素可以相繼存儲，也可以不相繼存儲，不過它為每個數據元素附加了一個鏈接指針，并形成的一個結點。（2） 單鏈表的每一個結點分為兩個部分：data和link。（3） 鏈表的第一個結點的地址可以通過鏈表的頭指針first找到，其他結點的地址則在前趨結點的link域中，鏈表的最后一個結點沒有后繼，在結點的link域中放一個空指針NULL。（4）頭指針first為空的單鏈表為空表，該鏈表一個結點也沒有，相對地，頭指針first不為空且首元結點存在的單鏈表為非空表，表中至少有一個結點。2.2 結構圖創建單鏈表輸入數據插入數據刪除數據查找數據輸出數據計算表

5、長圖 1 結構圖2.3 函數實現的具體算法舉例（1）插入函數/* 在帶頭結點的單鏈線性表L中第i個位置之前插入元素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） 刪除函數int Delete_List(LinkList L,int i,ElemType *e) /* 在帶頭結點的單鏈線性表L中，刪除第i個元素,并由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）查找元素/* 當按位置查找

7、元素，第i個元素存在時,其值賦給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("鏈表不存在或參數i錯"); return 0; *e=p->data; /* 取第i個元素 */ 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 課程設計思路一般的說，其過程如下： A. 分析鏈表特點 B. 分析鏈表功能以及操作 C. 設計函數庫 D. 制定調試計劃:初步調試計劃 E. 編寫主函數，方便后面的測試 F. 制定完整的程序測試計劃 G. 書寫文檔，系統說明 H. 復查和審核：從技術的角度審查，從管理的角度審查3.1 設計函數庫設計函數庫不能隨心所欲，想編寫什么函數就編寫什么函數，而是要根據分析鏈表所得結果，從分析結果入手，由分析我們知道鏈表可以進行的操作有：輸入、輸出、插入一個元素、刪除一個元素、查找一個元素、取出一個元素。根據這些操作分別寫出函數：int Insert_List(); /*插入元素*/in

10、t Delete_List(); /*刪除元素*/int GetElem_List(); /*查找元素*/int Disp_List(); /*顯示元素*/ int Length_List();/*求表長*/4 測試結果及其分析4.1 初始化圖2 初始化4.2 逆序輸入元素圖3 逆序輸入元素4.3 單鏈表的長度 圖4 計算長度4.4 遍歷輸出單鏈表圖 5遍歷4.5檢索查找 圖 6查找4.6輸入插入元素的值和位置圖 7插入4.7刪除元素圖 8 插入5 小結通過這次課設，我學會了如何把數據結構的知識應用到實踐當中，同時也進一步加深了對c/c+語言語法的應用，以及深刻的掌握了數據結構和c/c+語言的

11、結合運用。 在編程過程中，遇到了許多問題，在一次次的運行錯誤后，問題被一步步改正，也從中學到了許多知識。雖然我的程序還不夠完善，還需加以改進以實現更多的功能，但是我會盡我最大的努力去完成它，我相信我會努力去把程序做的更加完美。參考文獻 1王昆侖,李紅等編著. 數據結構與算法. 北京:中國鐵道出版社,2007. 2蘇仕華等編著. 數據結構課程設計. 北京：機械工業出版社 ,2005. 3蘇仕華編著. 數據結構與算法解析.合肥:中國科學技術大學出版社,2004. 4郭嵩山等著國際大學生程序設計競賽例題解北京:電子工業出版社,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;/*初始化單鏈表，即產生一個帶頭結點的空表，創建成功則返回空表的頭指針*/LinkList Init_List(void) LinkList L; L=(LinkList) malloc(sizeof(LNode); if(

13、L) L->next=NULL; /產生空表，頭結點的next域為空 return L; /*按逆序產生一個長度為n鏈表，參數為初始化的空鏈表，及線性表長度n*/*每個元素依次插入在頭結點后*/int Create_List(LinkList L,int n) int i; LinkList s; /*s變量用于保存新結點地址*/ printf("生成有%d個元素的線性表:n",n); for(i=n;i>0;i-) printf("請輸入線性表中第 %d 個元素:n",i); /*逆序輸入元素*/ s=(LinkList)malloc(si

14、zeof(LNode); if(!s) printf("創建結點不成功n"); return 0; scanf("%d",&s->data); s->next=L->next; L->next=s; return 1;/* 求單鏈表表長， 返回L中數據元素個數 */ int Length_List(LinkList L) int i=0; LinkList p=L->next; while(p) i+; p=p->next; return i; /* 當按位置查找元素，第i個元素存在時,其值賦給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("鏈表不存在或參數i錯"); return 0; *e=p->data; /* 取第i個元素 */ return 1; /* 按元素查找，查找鏈表中是否存在值為e的元素，存在，則返回L中第一個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; /* 在帶頭結點的單鏈線性表L中第i個位置之前插入元素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) /* 在帶頭結點的單鏈線性表L中，刪除第i個元素,并由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; /*顯示選擇提示信息函數*/void ShowSelect() printf("n請選擇要執行的操作：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變量表示用戶的選擇項*/ShowSelect();scanf("%d",&select);while(select!=0)switch(select)case 1: PL=Init_List(); break; case 2: printf("請輸入線性表中元素個數：n");scanf("%d",&le