1、大 連 科 技 學 院數據結構畢業設計題 目 單鏈表的基本操作-建立和遍歷 學生成績管理系統-排列 排序問題-選擇排序,直接插入排序學生姓名 李易霖專業班級 計算機10-1指導教師 宋 麗 芳 職 稱 副教授 所在單位 信息科學系軟件教研室 系 主 任 王立娟 完成日期 2012年1月6日大連科技學院數據結構畢業設計成績考核表學生姓名李易霖專業班級計算機10-1學號1001020112題 目單鏈表的基本操作，學生成績管理系統，排序問題 考 核 項 目分值評分1出勤情況102完成原理分析103設計分析104完成代碼編寫與調試105獨立工作能力、綜合運用所學知識分析和解決問題能力及實際工作能力提高

2、的程度106回答問題207畢業設計報告格式規范性30合計100總評成績注：總評標準采用優良制：優秀（90分以上）、良好（80-90）、中等（70-80）、及格（60-70）、不及格（60分以下）指導教師簽字： 畢業設計任務書一、任務及要求1. 設計（研究）內容和要求研究內容：單鏈表的基本操作，學生成績管理系統，二叉樹的運算任務和要求：（1）學習數據結構基礎知識，掌握數據結構典型的算法的使用。（2）對指導教師下達的題目進行任務分析。（3）根據分析結果完成設計。（4）編程：在計算機上實現題目的代碼實現。（5）完成對程序的測試和調試。（6）提交畢業設計報告(約二十頁)，含程序代碼及運行結果。2. 原

3、始依據結合數據結構畢業中的基本理論和基本算法，正確分析出數據的邏輯結構，合理地選擇相應的存儲結構，并能設計出解決問題的有效算法。提高程序設計和調試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改。二、工作量2周（10個工作日）時間。三、計劃安排第1個工作日第2個工作日：查找相關資料、書籍，閱讀示例文檔，選擇題目。第3個工作日：題目分析，設計算法。第4個工作日-5個工作日: 功能模塊的劃分和設計。第6個工作日：實現具體數據結構和模塊。第7個工作日第8個工作日：程序設計與調試，編寫畢業設計報告。第9個工作日：上交畢業設計報告。第10個工

4、作日：軟件驗收、答辯，成績評定。指導教師簽字： 2011年12月26日目 錄題目一：單鏈表的基本操作11 需求分析11.1 問題描述11.2 實現要求12.概要設計12.1邏輯結構設計12.2功能結構設計22.3物理結構設計23 算法設計與實現33.1算法設計33.2算法實現與調試3題目二：線性表的應用學生成績管理41 需求分析41.1 問題描述41.2 實現要求42.概要設計42.1邏輯結構設計42.2功能結構設計52.3物理結構設計53 算法設計與實現63.1算法設計63.2算法實現與調試7題目三：排序問題81 需求分析81.1 問題描述81.2 實現要求82.概要設計82.1邏輯結構設計

5、82.2功能結構設計82.3物理結構設計93 算法設計與實現93.1算法設計93.2算法實現與調試11總 結13參考文獻14附錄 全部代碼15題目一15題目二22題目三30題目一：單鏈表的基本操作1 需求分析1.1 問題描述用學過的方法建立單鏈表,掌握單鏈表的建立、插入，查找、刪除、逆置等基本算法和操作。掌握指針類型的應用和結構體的具體操作，初步掌握采用自底向上，分模塊進行的程序的調試與測試。1.2 實現要求(1)建立單鏈表用尾插法建立帶頭結點的單鏈表h，從鍵盤輸入各整型數據元素，以“-1”作為輸入結束標志符。 (2) 遍歷單鏈表h依次輸出鏈表中各數據元素。 (3) 按序號查找查找單鏈表h中第

6、i個元素并輸出該元素。(4) 插入在單鏈表h的第i個元素位置上插入x數據元素 并遍歷單鏈表h(5) 刪除刪除單鏈表h的第i個數據元素，并返回第i個元素同時遍歷單鏈表h(6）求表長求單鏈表的表長并輸出表長(7) 逆置單鏈表逆置帶頭結點的單鏈表h，逆置后的單鏈表利用原表中的結點空間，不重新申請空間，逆置后進行遍歷。(8) 將一個元素插入到有序表中使表仍然有序帶頭結點的單鏈表中的數據元素是整型數且有序。將x插入到順序表的適當位置上，保持表的有序性,將兩個遞增的有序表歸并成一個遞減的有序表，利用原表空間，不能重新申請空間2.概要設計2.1邏輯結構設計邏輯結構: 線性結構二元組圖式 G=(D,S) D=

7、(q,a,z,w,s,x) S=r R=,2.2功能結構設計 圖1功能設計圖本人在該小組中主要負責完成建立和遍歷模塊的功能實現2.3物理結構設計物理結構(1) 鏈式存儲示意圖如下： 圖2鏈式存儲示意圖 (2) c語言描述如下： #include /*denition of datatype*/( T ypedef char datatype; typedef struct node datatype data; struct node *next; linklist;3 算法設計與實現3.1算法設計1.用于定義單鏈表的存儲結構的函數 LinkList()。2.用帶頭結點的尾插法創建鏈表的函數

8、createList()。3.用于查找第i位元素的函數 get ()。4.用于遍歷單鏈表的函數 visit()。5.用于獲得表長的函數lengthList()。6.用于在第i位元素后插入新元素的函數 insert ()。7.用于刪除第i位元素的函數 delete ()。8.用于逆置單鏈表的函數 reverse ()。9.用于在程序開始輸出歡迎和提示信息的函數 start()。10.用于在程序結束時輸出提示信息的函數 end()。11.用于調用上述函數的主函數main()，主函數中對各函數的調用次序及方法為：定義了必要的變量后，先使用system()函數設置操作臺背景色；再調用程序開始時的輸出函

9、數start()；然后調用創建單鏈表的函數createList()并用相應類型的變量接 收它返回的頭結點地址；然后詢問是否遍歷（詢問步驟下同），需要的話將剛接收的頭結點地址作為參數調用遍歷函數visit()；遍歷后傳遞頭結點的地址調用查找函數get ()，該函數具有判斷查找位置合法性的功能；查找操作結束后傳遞頭結點地址給inser ()調用它（插入操作帶有判斷插入位置是否合法的功能，故還要調用lengthList()獲得表長作為插入函數的另一個參數）插入操作完成后將再次調用遍歷函數visit()顯示插入結果；結束插入后將頭結點地址作為參數調用刪除函數delete ()，刪除成功后將調用遍歷函數

10、顯示刪除后的結果（插入函數也具有判斷位置合法性的功能）；最后是調用逆置函數reverse ()，同樣是以頭結點為參數。3.2算法實現與調試（1）建立單鏈表： 123456 圖3建立單鏈表（2）遍歷單鏈表 圖4遍歷單鏈表題目二：線性表的應用學生成績管理1 需求分析1.1 問題描述編寫一個簡單的學生信息管理程序，能實現對學生信息的簡單管理。編寫一個簡單的學生信息管理程序，能實現對學生信息的簡單管理。1.2 實現要求 （1）創建成績鏈表，學生數據包含學生的學號、姓名和成績。 （2）可以在指定學號學生前插入學生成績數據。 （3）可以刪除指定學號的學生數據。 （4）可以計算學生的總數。 （5）可以按學號

11、和姓名查找學生。 （6）可以顯示所有學生的成績。 （7）可以把學生成績按從高到低的順序排列。2.概要設計2.1邏輯結構設計邏輯結構，線性結構二元組圖式如下: G=(D,S) D=(q,a,z,w,s,x) S=r R=, 圖5二元組圖式2.2功能結構設計開 始菜單選擇錄入？排列？插入？連接鏈表刪除？倒置？遍歷？按號查找按名查找成績成績成績成績成績成績成績成績成績結 束是否是是是是是是是是否否否否否否圖6功能結構設計圖本人在該小組中主要負責完成排列功能實現2.3物理結構設計 物理結構:鏈式存儲， c語言描述如下：#include #include #include #include typede

12、f struct Student int score; char sno5,sname8;Student;typedef struct Node Student studentInfo; struct Node * next;LinkList;3 算法設計與實現3.1算法設計1. 定義學生數據類型 stu。2. 定義結點存儲類型 LinkList。3. 函數聲明部分。4. 學生信息的輸入函數 input()。5. 用帶頭結點的尾插法建立單鏈表來存儲學生信息的函數createTailList()。6. 遍歷單鏈表顯示出學生數據的函數 showList()，此函數由羅聰同學編寫。7. 按學號查找學

13、生信息的函數getElem()，此函數由賈利洋同學編寫。8. 顯示單個學生信息的函數showElem()，此函數由羅聰同學編寫。9. 按姓名查找學生信息的函數locateElem()，此函數由賈利洋同學編寫。10. 求學生總人數（即表長）的函數lengthList()，此函數由華政同學編寫。11. 在指定學號前插入學生數據的函數insertElem()，此函數由孟繁章同學編寫。12. 刪除指定學號學生信息的函數deleteElem()，此函數由華政同學編寫。13. 用直接插入法按分數從高到底排序的函數SIS()。此函數由本人編寫。14. 程序開始時的顯示函數 start()。15. 程序結束時

14、的顯示函數 end()。16. 調用上述各函數的主函數 main()，調用順序及方法是：首先定義必要的變量；調用程序開始時的顯示函數start()；選擇后循環語句嵌套選擇語句；接著是循環語句中嵌套選擇語句和判斷語句，根據用戶的選擇，賦予適當的參數來調用各個功能函數；結束時調用程序結束時的顯示函數end()。3.2算法實現與調試（1）開始的菜單圖7開始界面(2)當前學生成績從高到低排序 圖8排序題目三：排序問題1 需求分析1.1 問題描述排序是數據處理中最常見，最基本的操作。在解決很多實際問題是，都離不開排序。排序還是另一種基本操作查找操作的基礎，排序可以提高查找的效率。因此，學習和 研究排序方

15、法是計算機程序人員課題之一。 1.2 實現要求 利用直接插入和選擇排序的方法對一組無序的序列進行排序，使其能正確的按順序輸出2.概要設計2.1邏輯結構設計選擇排序：在要排序的一組數中，選出最小的一個數與第一個位置的數交換，然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。直接插入排序：將一個待排序記錄按照排序碼的大小插入到一個有序序列的適當位置，使得插入后的序列仍然有序，直到所有的記錄全部插入到有序序列中。2.2功能結構設計圖9功能結構設計圖 關鍵碼序列為（42，20，17，27，13，8，17*，48），用直接插入排序算法進行排序。排序過程如圖所示

16、。 2.3物理結構設計選擇排序 第i趟排序開始時，當前有序區和無序區分別為R1.i-1和R(1in-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 Rk，將它與無序區的第1個記錄R交換，使R1.i和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。 這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。 直接插入排序用函數實現直接插入排序，并輸出每趟排序的結果.輸入格式第一行：鍵盤輸入待排序關鍵的個數n第二行：輸入n個待排序關鍵字，用空格分隔數據輸出格式每行輸出一趟排序結果，數據之間用一個空格分隔輸入樣例105 4 8 0 9 3 2 6 7 1輸出樣例4

17、 5 8 0 9 3 2 6 7 14 5 8 0 9 3 2 6 7 10 4 5 8 9 3 2 6 7 10 4 5 8 9 3 2 6 7 10 3 4 5 8 9 2 6 7 10 2 3 4 5 8 9 6 7 10 2 3 4 5 6 8 9 7 10 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 93 算法設計與實現3.1算法設計功能：選擇排序輸入：數組名稱（也就是數組首地址）、數組中元素個數*/void select_sort(int *x, int n)int i, j, min, t;for (i=0; in-1; i+) /*要選擇的次數：0n-

18、2共n-1次*/ min = i; /*假設當前下標為i的數最小，比較后再調整*/ for (j=i+1; jn; j+)/*循環找出最小的數的下標是哪個*/ if (*(x+j) *(x+min) min = j; /*如果后面的數比前面的小，則記下它的下標*/ if (min != i) /*如果min在循環中改變了，就需要交換數據*/ t = *(x+i); *(x+i) = *(x+min); *(x+min) = t; 功能：直接插入排序輸入：數組名稱（也就是數組首地址）、數組中元素個數*/void insert_sort(int *x, int n)int i, j, t;for

19、(i=1; i=0 & t*(x+j); j-) /*注意：j=i-1，j-，這里就是下標為i的數，在它前面有序列中找插入位置。*/ *(x+j+1) = *(x+ j ); /*如果滿足條件就往后挪。最壞的情況就是t比下標為0的數都小，它要放在最前面，j=-1，退出循環*/ *(x+j+1) = t; /*找到下標為i的數的放置位置*/3.2算法實現與調試1直接插入排序（1）第一行：鍵盤輸入待排序關鍵的個數n圖10輸入界面 ( 2 )第二行：輸入n個待排序關鍵字，用空格分隔數據 圖11排序演示圖（3）每行輸出一趟排序結果，數據之間用一個空格分隔2直接選擇排序（1）輸入幾個字符串，直到輸入！結

20、束 圖12輸入數字（2）分別以升序和降序排列字符串數組。圖13排序結果總 結通過這次兩周的數據結構畢業設計，我學會了許多知識并且提高了自己的動收能力與團隊合作能力，在完成這次畢業設計的過程中，我認真查找資料。和隊友配合，共同努力完成了這次畢業設計。本次畢業設計的主題分為三個，分別為單鏈表的基本操作，學生成績管理系統 排序問題，通過上機實踐，我對這些知識有了更進一步的了解，通過這次畢業設計，我的專業知識也豐富了許多。在程序調試階段，一個小小的錯誤就會讓程序無法運行，我在這個過程中認真查找錯誤，最后通過我的不懈努力終于把程序調試成功了。這次畢業設計的過程讓我學會了很多，成長了很多，同時也讓我看到了

21、自己身上的不足，許多看似簡單的問題在自己操作的時候發現并不那么簡單。以后我要繼續努力學習專業知識，提高自己的動手能力，不斷的豐富自己，完善自己。 參考文獻1 趙波,霍利等編著數據結構實用教程(C語言版)清華大學出版社，200992 唐策善，李龍澍，黃劉生數據結構用C語言描述M 北京：高等教育出版社19993 嚴蔚敏, 吳偉民著.據結構(C語言版)，清華大學出版，19994 陳一華等編.數據結構-使用C 語言，電子科技大學出版社, 19985 譚浩強.C語言程序設計（第二版）.北京：高等教育出版社，20026標準C語言程序設計及應用 周純杰 ,劉正林等 編著 華中科技大學 7C語言畢業設計案例精

22、編 姜靈芝,余健 編著 清華大學出版社附錄 全部代碼題目一 #include #include #include /*denition of datatype*/typedef int datatype; typedef struct nodedatatype data;struct node *next;linklist;/*function of create*/linklist *create()int x;linklist *head,*s,*r; head = (linklist*)malloc(sizeof(linklist); r=head;scanf(%d,&x);while(

23、x!=-1) s = (linklist*)malloc(sizeof(linklist); s-data=x; r-next = s; r = s; scanf(%d,&x); r-next = NULL; return head;/*function of visit*/void visit(linklist *head)linklist *p;p=head-next;while(p) printf( %d,p-data); p=p-next;printf(n);void main()linklist *h1,*q,*h2;int i,b=1;int x;int in,de,ins;dat

24、atype *e;while(b)int a;printf(nn);printf( -菜單-n);printf( -n); printf( (1)創建(帶頭尾插) (2)遍歷 (3)查找n);printf( (4)插入(無序) (5)刪除 (6)求表長n);printf( (7)逆置 (8)插入(有序) (9)歸并n); printf( (10)退出 n);printf( -);printf(n請輸入功能選項: );scanf(%d,&a);switch(a)case 1:printf(Creat linklist h1:n);h1=create();break;case 2:printf(v

25、isit LinkList h1:n);visit(h1);break; case 3:printf(please input the station of locate:);scanf(%d,&i); q=get(h1,i); if (q) printf(%d,q-data); else printf(location is error); printf(n);break;case 4:printf(please input the station and data of insert:);scanf(%d,%d,&i,&x); in=insert(h1,i,x); printf(n);if

26、 (in=0) printf(location is error); else visit(h1); printf(n);break; case 5:printf(please input the staion of delete:);scanf(%d,&i); e=(datatype *) malloc(sizeof(datatype); de=delete(h1,i,e); if (de=0) printf(location is error); else visit(h1); printf(the dele is %d,*e); printf(n);break;case 6:printf

27、(n the table long: %d n,lengthList(h1);break;case 7:reverse(h1);visit(h1);break; case 8:printf(please input the data of insertSort:);scanf(%d,&x);ins=insertSort(h1,x);printf(n);visit(h1);printf(n);break; case 9:h1=create();visit(h1);h2=create();visit(h2);visit(meger(h1,h2);break;case 10:printf(n退出n)

28、;b=0;break;題目二#include#include#include #include typedef struct Student /*學生類型定義*/ int score; /*成績*/ char sno5,sname8; /*學號,姓名*/ Student; typedef struct Node /*結點類型定義*/ Student studentInfo; /*學生信息*/ struct Node *next; /*指向后繼元素的指針域*/ LinkList; void insertSort(LinkList *L) /*用直接插入排序思想把學生的成績按從高到低排序， 結果保

29、存在新有序鏈表中，原鏈表不變*/ LinkList *L1,*p; /*L1有序鏈表的表頭，p插入位置前結點*/ LinkList *q,*s; /*q欲插入L1中的結點*/ int len; len=lengthList (L) ; L1=( LinkList *)malloc(sizeof (LinkList); /*建立頭結點，申請結點存儲空間*/ if (L-next) /*鏈表L非空*/ /*生成有序鏈表的第一個結點*/ s=( LinkList *)malloc(sizeof (LinkList); /*建立結點，申請結點存儲空間*/ strcpy(s-studentInfo .s

30、no ,L-next-studentInfo.sno); strcpy(s-studentInfo .sname,L-next-studentInfo.sname); s-studentInfo .score =L-next-studentInfo.score; s-next =NULL; L1-next=s; /*只有原單鏈表的第一個結點的有序鏈表L1*/ q=L-next-next; /*原單鏈表的第二個結點，q即要插入有序鏈表L1中的結點*/ else printf(nthe student link list is empty!n); return; while(q) /*鏈表L中有結

31、點*/ p=L1 ; /*從鏈表L1的第一個結點開始比較*/ while(p-next) & (p-next-studentInfo.score=q-studentInfo.score) p=p-next ; /*查找插入位置前結點*/ /*生成欲插入有序鏈表中的結點*/ s=( LinkList *)malloc(sizeof (LinkList); /*建立結點，申請結點存儲空間*/ strcpy(s-studentInfo .sno ,q-studentInfo.sno); strcpy(s-studentInfo .sname ,q-studentInfo.sname); s-stud

32、entInfo .score =q-studentInfo.score; if(!p-next) /*p是有序鏈表的最后一個結點*/ s-next =NULL ; p-next =s; else s-next =p-next ; p-next =s; q=q-next; /*下一個欲插入有序鏈表的結點*/ /*while(!q)*/ displayAll(L1); /*顯示生成的有序鏈表*/void main() LinkList *L; char ch5; char sname8; int b=1; printf(=nn); printf( 帶頭結點的學生成績管理程序nn); printf(

33、=nn); while(b) int a; printf(nn); printf( 創建（帶頭尾插） 指定學號前插入 按學號刪除n ); printf(計算學生總數 按學號查找 按姓名查找n); printf( 顯示所有學生 成績排序 退出n); printf(n請輸入功能選項：); scanf(%d,&a); switch(a) case 1: L=CreateTailList(); break; case 2: printf(n輸入欲在哪個學號前插入數據:); scanf(%s,ch); insertElem(L, ch); break; case 3: printf(n輸入欲刪除學生的學

34、號:); scanf(%s,ch); deleteElem(L, ch); break; case 4: printf( n學生總數為： %d n,lengthList (L) ); break; case 5: printf(n輸入欲查找學生的學號:); scanf(%s,ch); locateElemByno(L, ch) ;break; case 6: printf(n輸入欲查找學生的姓名:); scanf(%s,sname); locateElemByname(L, sname);break; case 7: displayAll(L); break; case 8: insertSort(L); break; case 9: printf(n已退出n); b=0;b