數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(附代碼)-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)Word版

整理為word格式整理為word格式整理為word格式上海應(yīng)用技術(shù)學(xué)院課程設(shè)計(jì)報(bào)告課程名稱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》設(shè)計(jì)題目猴子選大王；建立二叉樹(shù)；各種排序；有序表的合并；成績(jī)管理系統(tǒng)；院系計(jì)算機(jī)科學(xué)與信息工程專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)姓名學(xué)號(hào)指導(dǎo)教師日期目的與要求鞏固和加深對(duì)常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的理解和掌握掌握基于數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)的基本方法掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)算法的基本技能掌握書(shū)寫(xiě)程序設(shè)計(jì)說(shuō)明文檔的能力提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)及高級(jí)語(yǔ)言解決非數(shù)值實(shí)際問(wèn)題的能力課程設(shè)計(jì)內(nèi)容說(shuō)明項(xiàng)目一對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述學(xué)生成績(jī)管理**任務(wù)：要求實(shí)現(xiàn)對(duì)學(xué)生資料的錄入、瀏覽、插入和刪除等功能。輸入：設(shè)學(xué)生成績(jī)以記錄形式存儲(chǔ)，每個(gè)學(xué)生記錄包含的信息有：學(xué)號(hào)和各門(mén)課程的成績(jī)，設(shè)學(xué)生成績(jī)至少3門(mén)以上。存儲(chǔ)結(jié)構(gòu)：采用線性鏈?zhǔn)浇Y(jié)構(gòu)。詳細(xì)設(shè)計(jì)LinkList*create()：輸入學(xué)生成績(jī)記錄函數(shù)；voidprint(LinkList*head)：顯示全部記錄函數(shù)LinkList*Delete(LinkList*head)：刪除記錄函數(shù)LinkList*Insert(LinkList*head)：插入記錄函數(shù)voidmenu_select()：菜單選擇voidScoreManage()：函數(shù)界面程序流程圖整理為word格式整理為word格式整理為word格式3．3．刪除學(xué)生記錄4．插入學(xué)生記錄1．輸入學(xué)生記錄輸入n（0<n<6）主界面2．輸出學(xué)生記錄退出學(xué)生成績(jī)管理系統(tǒng)5．退出判斷nn=5n=1、2、3、4程序模塊及其接口描述該程序可以分為以下幾個(gè)模塊：1、菜單選擇：voidmenu_select();提供五種可以選擇的操作，在main函數(shù)中通過(guò)switch語(yǔ)句調(diào)用菜單menu_select()函數(shù)，進(jìn)入不同的功能函數(shù)中完成相關(guān)操作。2、輸入功能：LinkList*create();通過(guò)一個(gè)for循環(huán)語(yǔ)句的控制，可以一次完成無(wú)數(shù)條記錄的輸入。并將其存入鏈表。整理為word格式整理為word格式整理為word格式3、輸出功能：voidprint(LinkList*head);通過(guò)一個(gè)while的循環(huán)控制語(yǔ)句，在指針p!=NULL時(shí)，完成全部學(xué)生記錄的顯示。知道不滿足循環(huán)語(yǔ)句，程序再次回到菜單選擇功能界面。4、刪除功能：LinkList*Delete(LinkList*head);按想要?jiǎng)h除的學(xué)生的學(xué)號(hào)首先進(jìn)行查找，通過(guò)指針?biāo)赶蚪Y(jié)點(diǎn)的下移來(lái)完成，如果找到該記錄，則完成前后結(jié)點(diǎn)的連接，同時(shí)對(duì)以查找到的結(jié)點(diǎn)進(jìn)行空間的釋放，最后完成對(duì)某個(gè)學(xué)生記錄進(jìn)行刪除，并重新存儲(chǔ)。5、插入功能：LinkList*Insert(LinkList*head)；輸入你想插入的位置，通過(guò)指針?biāo)赶蚪Y(jié)點(diǎn)的下移，找到該位置，將該新的學(xué)生記錄插入到該結(jié)點(diǎn)，并對(duì)該結(jié)點(diǎn)后面的指針下移。鏈表長(zhǎng)度加一，重新存儲(chǔ)。程序的輸入與輸出描述輸入：調(diào)用LinkList*create()函數(shù)，輸入學(xué)生的姓名、學(xué)號(hào)、三門(mén)功課的成績(jī)；輸出：調(diào)用voidprint(LinkList*head)函數(shù)，輸出學(xué)生的記錄。程序測(cè)試主菜單：整理為word格式整理為word格式整理為word格式成績(jī)管理系統(tǒng)的主界面：學(xué)生成績(jī)記錄的輸入：輸出學(xué)生成績(jī)記錄：整理為word格式整理為word格式整理為word格式學(xué)生成績(jī)記錄的刪除（刪除學(xué)號(hào)是1101的學(xué)生記錄）插入新的學(xué)生成績(jī)記錄（插入學(xué)號(hào)為1103的學(xué)生記錄）整理為word格式整理為word格式整理為word格式尚未解決的問(wèn)題或改進(jìn)方向尚未解決的問(wèn)題：該成績(jī)管理系統(tǒng)還存在不少缺陷，而且它提供的功能也是有限的，只能實(shí)現(xiàn)學(xué)生成績(jī)的輸入、輸出、刪除、插入。對(duì)于，學(xué)生成績(jī)記錄的文件保存以及按學(xué)號(hào)、姓名等的查詢也是缺少的。還有就是，對(duì)于多個(gè)學(xué)生成績(jī)的操作也是不夠的。改進(jìn)的方向：在時(shí)間許可的條件下，盡量的完善該系統(tǒng)的各種功能，同時(shí)也應(yīng)修改系統(tǒng)，讓它更為人性化、簡(jiǎn)單化，被廣大用戶所接受。對(duì)軟件的使用說(shuō)明該軟件是屬于比較低級(jí)的軟件，只是包含了課程設(shè)計(jì)的要求的幾個(gè)功能：輸入、輸出、刪除、插入。所以用戶在使用的過(guò)程中肯定會(huì)受到一定的局限性、不方便性，但由于時(shí)間的緣故，無(wú)法將軟件做到盡善盡美。項(xiàng)目二對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述各種排序任務(wù)：用程序?qū)崿F(xiàn)插入法排序、選擇法排序、起泡法改進(jìn)算法排序；利用插入排序、選擇法排序和冒泡法的改進(jìn)算法,將用戶隨機(jī)輸入的一列數(shù)按遞增的順序排好。輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列。功能描述整理為word格式整理為word格式整理為word格式該函數(shù)有以下幾個(gè)功能：對(duì)R[0..n-1]按遞增有序進(jìn)行直接插入排序?qū)[0..n-1]按遞增有序進(jìn)行冒泡排序?qū)[0..n-1]按遞增有序進(jìn)行直接選擇排序排序后的輸出5)調(diào)用所有排序，實(shí)現(xiàn)排序程序流程圖直接插入排序InsertSort()直接插入排序InsertSort()退出排序Sort（）直接選擇排序SelectSort()冒泡排序BubbleSort()詳細(xì)設(shè)計(jì)voidInsertSort(RecTypeR[],intn)：對(duì)R[0..n-1]按遞增有序進(jìn)行直接插入排序voidBubbleSort(RecTypeR[],intn)：對(duì)R[0..n-1]按遞增有序進(jìn)行冒泡排序voidSelectSort(RecTypeR[],intn)：對(duì)R[0..n-1]按遞增有序進(jìn)行直接選擇排序voiddisp(RecTypeR[],intn)：排序后的輸出voidSort()：調(diào)用所有排序，實(shí)現(xiàn)排序整理為word格式整理為word格式整理為word格式程序模塊及其接口描述該程序分為五個(gè)模塊:1.輸入功能：voidSort()建立一個(gè)數(shù)組存放用戶在鍵盤(pán)上輸入的關(guān)鍵字，在分別調(diào)用各種排序的函數(shù)，對(duì)關(guān)鍵字進(jìn)行排序。2.直接插入排序功能：voidInsertSort(RecTypeR[],intn)將后一個(gè)數(shù)與前一個(gè)數(shù)比較，將其插入到第一個(gè)比它大的大的數(shù)前面，其余數(shù)字往后移一個(gè)位置。每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。3.冒泡排序功能：voidBubbleSort(RecTypeR[],intn)在排序過(guò)程中，執(zhí)行完最后的排序后，雖然數(shù)據(jù)已全部排序完備，但程序無(wú)法判斷是否完成排序，為了解決這一不足，可設(shè)置一個(gè)標(biāo)志位exchange，將其初始值設(shè)置為非0，表示被排序的表是一個(gè)無(wú)序的表，每一次排序開(kāi)始前設(shè)置exchange值為0，在進(jìn)行數(shù)據(jù)交換時(shí)，修改exchange為非0。在新一輪排序開(kāi)始時(shí)，檢查此標(biāo)志，若此標(biāo)志為0，表示上一次沒(méi)有做過(guò)交換數(shù)據(jù)，則結(jié)束排序；否則進(jìn)行排序。4.直接選擇排序功能：voidSelectSort(RecTypeR[],intn)在無(wú)序區(qū)里找最小的數(shù)，第i小的數(shù)字放在第i個(gè)位置上，與原來(lái)第i個(gè)位置上的數(shù)字交換。5.輸出功能：voiddisp(RecTypeR[],intn)程序的輸入與輸出描述輸入：要求是10個(gè)為數(shù)字的關(guān)鍵字；輸出：排序后新的序列。程序測(cè)試輸入關(guān)鍵字，調(diào)用各種排序函數(shù)整理為word格式整理為word格式整理為word格式尚未解決的問(wèn)題或改進(jìn)方向改進(jìn)方向：雖然給出了它的各種排序的結(jié)果，但是沒(méi)有它的箱子過(guò)程，這是我的改進(jìn)的方向，希望能將每種排序的過(guò)程也能展示給用戶，來(lái)體現(xiàn)它們的不同。對(duì)軟件的使用說(shuō)明用戶只需根據(jù)提示，在鍵盤(pán)上輸入要排序的10個(gè)關(guān)鍵字。項(xiàng)目三對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述有序表的合并要求輸入有序表的數(shù)據(jù)，利用順序表和鏈表結(jié)構(gòu)分布完成兩個(gè)有序表合并功能，并輸出合并后的信息。功能描述該程序有如下幾個(gè)功能：初始化順序表初始化鏈表建立順序表尾插法建表輸出合并后的順序表輸出合并后的單鏈表合并順序表合并單鏈表整理為word格式整理為word格式整理為word格式調(diào)用以上的函數(shù)，實(shí)現(xiàn)有序表的合并概要設(shè)計(jì)或程序流程圖開(kāi)始開(kāi)始初始化鏈表初始化順序表初始化鏈表初始化順序表建立順序表尾插法建表建立順序表尾插法建表合并順序表合并單鏈表合并順序表合并單鏈表輸出輸出結(jié)束結(jié)束詳細(xì)設(shè)計(jì)voidInitList(SqList*&L)：初始化順序表voidInitList1(LinkList1*&L)：初始化鏈表voidCreateList(SqList*&L,ElemTypea[],intn)：建立順序表voidCreateListR(LinkList1*&L,ElemTypea[],intn)：尾插法建表voidDispList(SqList*L)：輸出合并后的順序表voidDispList1(LinkList1*L)：輸出合并后的單鏈表voidUnionList(SqList*LA,SqList*LB,SqList*&LC)：合并順序表voidUnionList1(LinkList1*LA,LinkList1*LB,LinkList1*&LC)：合并單鏈表voidUnion()：調(diào)用以上的函數(shù)，實(shí)現(xiàn)有序表的合并。程序模塊及其接口描述程序有以下幾個(gè)模塊：初始化、建立順序表初始化、建立鏈表整理為word格式整理為word格式整理為word格式輸出合并后的表合并表調(diào)試分析或程序測(cè)試有序表的合并：尚未解決的問(wèn)題或改進(jìn)方向不足：不能重復(fù)使用程序。對(duì)軟件的使用說(shuō)明用戶只需根據(jù)界面的提示，采用對(duì)應(yīng)的操作。4．項(xiàng)目四(1)對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述建立二叉樹(shù)，層序、先序、中序、后序遍歷（用遞歸或非遞歸的方法都可以）**任務(wù)：要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)、輸出中序遍歷序列的函數(shù)、輸出后序遍歷序列的函數(shù)；(2)功能描述建立二叉樹(shù)輸出二叉樹(shù)先序遍歷非遞歸算法：整理為word格式整理為word格式整理為word格式不為空時(shí)，訪問(wèn)根--左--右，采用遞歸的方法。中序遍歷非遞歸算法：不為空時(shí)，訪問(wèn)左--根--右，采用遞歸的方法。后序遍歷非遞歸算法：不為空時(shí)，訪問(wèn)左--右--根，采用遞歸的方法。層序遍歷：運(yùn)用隊(duì)列，隊(duì)列不空時(shí)，有左孩子將其入隊(duì)，有右孩子將其入隊(duì)，同時(shí)出隊(duì)。調(diào)用以上函數(shù)實(shí)現(xiàn)二叉樹(shù)的各種遍歷(3)概要設(shè)計(jì)或程序流程圖開(kāi)始開(kāi)始輸入二叉樹(shù)的按層結(jié)點(diǎn)值輸入二叉樹(shù)的按層結(jié)點(diǎn)值層次遍歷后序遍歷中序遍歷先序遍歷層次遍歷后序遍歷中序遍歷先序遍歷結(jié)束結(jié)束(4)詳細(xì)設(shè)計(jì)voidCreateBTNode(BTNode*&b,char*str)：建立二叉樹(shù)voidDispBTNode(BTNode*b)：輸出二叉樹(shù)voidPreOrder(BTNode*b)：先序遍歷非遞歸算法voidInOrder(BTNode*b)：中序遍歷非遞歸算法voidPostOrder(BTNode*b)：后序遍歷非遞歸算法voidLevelOrder(BTNode*b)：層序遍歷(5)程序模塊及其接口描述(6)程序的輸入與輸出描述輸入二叉樹(shù)的按層結(jié)點(diǎn)值；整理為word格式整理為word格式整理為word格式輸出二叉樹(shù)先序遍歷訪問(wèn)結(jié)點(diǎn)的順序；輸出二叉樹(shù)中序遍歷訪問(wèn)結(jié)點(diǎn)的順序；輸出二叉樹(shù)后序遍歷訪問(wèn)結(jié)點(diǎn)的順序；輸出二叉樹(shù)層次遍歷訪問(wèn)結(jié)點(diǎn)的順序；(7)調(diào)試分析或程序測(cè)試用戶從鍵盤(pán)上輸入要?jiǎng)?chuàng)建的二叉樹(shù)結(jié)點(diǎn)：(8)尚未解決的問(wèn)題或改進(jìn)方向改進(jìn)方向：希望能將系統(tǒng)改進(jìn)的更為人性化，讓界面更舒適，操作更簡(jiǎn)單。(9)對(duì)軟件的使用說(shuō)明用戶只需按照界面的提示，采取相應(yīng)的措施，到時(shí)界面會(huì)提醒用戶鍵盤(pán)輸入。5．項(xiàng)目五（1）對(duì)設(shè)計(jì)任務(wù)內(nèi)容的概述猴子選大王**任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3...m,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,nm,n為整數(shù)，n<m輸出形式：中文提示按照m個(gè)猴子，數(shù)n個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào)，建立一個(gè)函數(shù)來(lái)實(shí)現(xiàn)此功能整理為word格式整理為word格式整理為word格式（2）需求分析或功能描述為猴子編號(hào)out，編號(hào)out=pass（pass為密碼值），該猴子離圈，次數(shù)step++。剩下的猴子繼續(xù)次操作，直到次數(shù)step=猴子monkey時(shí)結(jié)束。（3）概要設(shè)計(jì)或程序流程圖開(kāi)始開(kāi)始輸入猴子的數(shù)量和密碼值輸入猴子的數(shù)量和密碼值編號(hào)=密碼值，猴子出列，次數(shù)自增編號(hào)=密碼值，猴子出列，次數(shù)自增NN次數(shù)=猴子數(shù)次數(shù)=猴子數(shù)YY結(jié)束結(jié)束（4）詳細(xì)設(shè)計(jì)或源代碼說(shuō)明為猴子編號(hào)out，編號(hào)out=pass（pass為密碼值），該猴子離圈，次數(shù)step++。剩下的猴子繼續(xù)次操作，直到次數(shù)step=猴子monkey時(shí)結(jié)束。函數(shù)intMonkey()實(shí)現(xiàn)了這一功能。（5）程序模塊及其接口描述運(yùn)用隊(duì)列（環(huán)形隊(duì)列），編號(hào)=密碼值入隊(duì)；為猴子編號(hào)out，編號(hào)out=pass（pass為密碼值），該猴子離圈，次數(shù)step++。剩下的猴子繼續(xù)次操作，直到次數(shù)step=猴子monkey時(shí)結(jié)束。函數(shù)intMonkey()實(shí)現(xiàn)了這一功能。整理為word格式整理為word格式整理為word格式（6）程序的輸入與輸出描述輸入數(shù)據(jù)：輸入m,nm,n為整數(shù)，n<m輸出形式：中文提示按照m個(gè)猴子，數(shù)n個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào)，建立一個(gè)函數(shù)來(lái)實(shí)現(xiàn)此功能。（7）調(diào)試分析或程序測(cè)試猴子數(shù)量8,密碼值9（猴子數(shù)>密碼值）（8）尚未解決的問(wèn)題或改進(jìn)方向不足：不能重復(fù)使用程序，如果數(shù)字大的話，輸出繁瑣。（9）對(duì)軟件的使用說(shuō)明用戶只需根據(jù)軟件界面的提示進(jìn)行相關(guān)操作。結(jié)論及體會(huì)本學(xué)期，我學(xué)會(huì)了常用數(shù)據(jù)結(jié)構(gòu)：數(shù)組（連續(xù)空間），棧（先進(jìn)后出），隊(duì)列（先進(jìn)先出），鏈表（指針），樹(shù)（前驅(qū)、后繼，根、葉子），圖（點(diǎn)、邊），堆（特殊的樹(shù)，根節(jié)點(diǎn)的值最大或最?。┻€有線性表存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)，常用的排序算法。在這一周里，自己用了C—Free做了一個(gè)程序，分別實(shí)現(xiàn)了學(xué)生成績(jī)管理系統(tǒng)、各種排序、有序表的合并、二叉樹(shù)的建立及遍歷以及猴子選大王，通過(guò)本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我學(xué)習(xí)了很多課上沒(méi)弄懂的動(dòng)西，鞏固了關(guān)于二叉樹(shù)、棧、鏈表等知識(shí)。整理為word格式整理為word格式整理為word格式在設(shè)計(jì)程序時(shí)，雖然很用心的做，但還是遇到種種難題，通過(guò)上網(wǎng)查找資料、圖書(shū)館查閱資料、問(wèn)老師的方式，最終還是解決多數(shù)，雖然最后的程序不是很完美，但是因?yàn)槭峭ㄟ^(guò)自己的努力完成的，還是感覺(jué)很滿意，也收獲很大東西。經(jīng)過(guò)了這次課程設(shè)計(jì)，現(xiàn)在已經(jīng)可以了解很多錯(cuò)誤在英文里的提示，這對(duì)我來(lái)說(shuō)是一個(gè)突破性的進(jìn)步，眼看著一個(gè)個(gè)錯(cuò)誤通過(guò)自己的努力在我眼前消失，覺(jué)得很是開(kāi)心。在這一段努力學(xué)習(xí)的過(guò)程中，我的編程設(shè)計(jì)有了明顯的提高，其實(shí)現(xiàn)在想起來(lái)，收獲還真是不少，雖然說(shuō)以前非常不懂這門(mén)語(yǔ)言，在它上面花費(fèi)了好多心血，覺(jué)得它很難，是需用花費(fèi)了大量的時(shí)間編寫(xiě)出來(lái)的?，F(xiàn)在真正的明白了一些代碼的應(yīng)用，每個(gè)程序都有一些共同點(diǎn)，通用的結(jié)構(gòu)，相似的格式。只要努力去學(xué)習(xí)，就會(huì)靈活的去應(yīng)用它?？傊ㄟ^(guò)這次的課程設(shè)計(jì)，我們收獲匪淺，首先由衷感謝老師提供這樣的一個(gè)機(jī)會(huì)鍛煉自己，感受到學(xué)來(lái)的知識(shí)不只是用來(lái)完成試卷的。一向習(xí)慣獨(dú)立思考的自己學(xué)會(huì)了積極的與別人交流，取長(zhǎng)補(bǔ)短，共同進(jìn)步。課程設(shè)計(jì)使自己發(fā)現(xiàn)考試不是最重要的，最重要的是能運(yùn)用所學(xué)的知識(shí)。在整個(gè)課程設(shè)計(jì)的學(xué)習(xí)過(guò)程中，不再是學(xué)到知識(shí)解題，而是在實(shí)際運(yùn)用時(shí)遇到什么學(xué)什么，重在把知識(shí)應(yīng)用于實(shí)際。附錄1：參考文獻(xiàn)[1]《數(shù)據(jù)結(jié)構(gòu)教程（第3版）》，李春葆，清華大學(xué)出版社，2010[2]《數(shù)據(jù)結(jié)構(gòu)》，楊劍，清華大學(xué)出版社，2011[3]《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》，嚴(yán)蔚敏吳偉民，清華大學(xué)出版社，1997[4]《DataStructuresUsingC數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，RKrishnamoorthy、GIndiraniKumaravel，清華大學(xué)出版社，2009-9[5]《C++數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)（美）RobertL.Kruse/AlexanderJ.Ryba著/錢(qián)麗萍譯》，清華大學(xué)出版社，2004[6]《計(jì)算機(jī)算法設(shè)計(jì)與分析（第2版）》，王曉東，電子工業(yè)出版社，2004附錄2：部分源代碼清單#include<stdio.h>#include<malloc.h>#include<string.h>#include<iostream>#include<stdlib.h>整理為word格式整理為word格式整理為word格式#defineLENsizeof(LinkList)#defineMaxSize50//************************************************************//成績(jī)管理系統(tǒng)typedefstructLNode /*定義單鏈表結(jié)點(diǎn)類型*/{ charname[10]; //姓名 charnum[10]; //學(xué)號(hào) intscore[3];structLNode*next;}LinkList;LinkList*init(){ returnNULL;/*返回空指針*/}LinkList*create(){ inti,s,k; intj=0; LinkList*head=NULL,*p;/*定義函數(shù).此函數(shù)帶回一個(gè)指向鏈表頭的指針*/ system("cls"); printf("\n請(qǐng)輸入您想輸入的學(xué)生個(gè)數(shù)："); scanf("%d",&k); for(j=0;j<k;j++) { p=(LinkList*)malloc(LEN);/*開(kāi)辟一個(gè)新的單元*/整理為word格式整理為word格式整理為word格式 if(p==NULL)/*如果指針p為空*/ { printf("\n輸出內(nèi)存溢出.");/*輸出內(nèi)存溢出*/ return(head);/*返回頭指針,下同*/ } printf("輸入學(xué)號(hào):"); scanf("%s",p->num); printf("輸入姓名:"); scanf("%s",p->name); printf("請(qǐng)分別輸入語(yǔ)文、數(shù)學(xué)、英語(yǔ)的分?jǐn)?shù)%dscores\n",3);/*開(kāi)始輸入*/ for(i=0;i<3;i++)/*3門(mén)課程循環(huán)3次*/ { do{ printf("score%d:",i+1); scanf("%d",&p->score[i]); if(p->score[i]<0||p->score[i]>100)/*確保成績(jī)?cè)?~100之間*/ printf("Dataerror,pleaseenteragain.\n"); }while(p->score[i]<0||p->score[i]>100); } p->next=head;/*將頭結(jié)點(diǎn)做為新輸入結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/ head=p;/*新輸入結(jié)點(diǎn)為新的頭結(jié)點(diǎn)*/ } return(head);}/*顯示全部記錄函數(shù)*/voidprint(LinkList*head)整理為word格式整理為word格式整理為word格式{ LinkList*p; system("cls"); p=head;/*初值為頭指針*/ printf("\n************************LinkList***************\n"); printf("-------------------------------------------------\n"); printf("|學(xué)號(hào)|姓名|語(yǔ)文|數(shù)學(xué)|英語(yǔ)|\n"); printf("-------------------------------------------------\n"); while(p!=NULL) { printf("|%4s|%-4s|%3d|%3d|%3d|\n", p->num,p->name,p->score[0],p->score[1],p->score[2]);p=p->next; } printf("-------------------------------------------------\n"); printf("***********************END***********************\n");}/*刪除記錄函數(shù)*/LinkList*Delete(LinkList*head){ LinkList*p1,*p2;/*p1為查找到要?jiǎng)h除的結(jié)點(diǎn)指針，p2為其前驅(qū)指針*/ charc,s[6];/*s[6]用來(lái)存放學(xué)號(hào),c用來(lái)輸入字母*/ system("cls"); printf("請(qǐng)輸入要?jiǎng)h除的學(xué)生的學(xué)號(hào):"); scanf("%s",s); p1=p2=head;/*給p1和p2賦初值頭指針*/ while(strcmp(p1->num,s)&&p1!=NULL)/*當(dāng)記錄的學(xué)號(hào)不是要找的，或指針不為空時(shí)*/整理為word格式整理為word格式整理為word格式 { p2=p1;/*將p1指針值賦給p2作為p1的前驅(qū)指針*/ p1=p1->next;/*將p1指針指向下一條記錄*/ } if(strcmp(p1->num,s)==0)/*學(xué)號(hào)找到了*/ { printf("***********************FOUND************************\n"); printf("-----------------------------------------------------------\n"); printf("|學(xué)號(hào)|姓名|語(yǔ)文|數(shù)學(xué)|英語(yǔ)|\n"); printf("-------------------------------------------------\n"); printf("|%4s|%4s|%3d|%3d|%3d|\n",p1->num,p1->name,p1->score[0],p1->score[1],p1->score[2]); printf("-----------------------------------------------------\n"); printf("**************************END**************************\n"); printf("您確定要?jiǎng)h除該學(xué)生的記錄嗎Y/N?");/*提示是否要?jiǎng)h除,輸入Y刪除,N則退出*/ for(;;) { scanf("%c",&c); if(c=='n'||c=='N')break;/*如果不刪除,則跳出本循環(huán)*/ if(c=='y'||c=='Y') { if(p1==head)/*若p1==head，說(shuō)明被刪結(jié)點(diǎn)是首結(jié)點(diǎn)*/ head=p1->next;/*把第二個(gè)結(jié)點(diǎn)地址賦予head*/ else整理為word格式整理為word格式整理為word格式 p2->next=p1->next; free(p1); /*否則將一下結(jié)點(diǎn)地址賦給前一結(jié)點(diǎn)地址*/ printf("\n學(xué)號(hào)為%s的學(xué)生記錄已被刪除.\n",s); break;/*刪除后就跳出循環(huán)*/ } } } else printf("\n找不到學(xué)號(hào)為%s的學(xué)生記錄.\n",s);/*找不到該結(jié)點(diǎn)*/ return(head);}//插入LinkList*Insert(LinkList*head){ intk; //在表中第k個(gè)位置插入 printf("請(qǐng)輸入插入的位置："); scanf("%d",&k); intj=0,i=0; LinkList*p1,*p2;/*p1為查找到要?jiǎng)h除的結(jié)點(diǎn)指針，p2為其前驅(qū)指針*/ charN[10],s[10];/*s[10]用來(lái)存放姓名,N[10]用來(lái)存放學(xué)號(hào)*/ intscore[3]; system("cls"); printf("輸入學(xué)號(hào):"); scanf("%s",N); printf("輸入姓名:"); scanf("%s",s); printf("請(qǐng)分別輸入語(yǔ)文、數(shù)學(xué)、英語(yǔ)的分?jǐn)?shù)%dscores\n",3);/*開(kāi)始輸入*/整理為word格式整理為word格式整理為word格式 for(i=0;i<3;i++)/*3門(mén)課程循環(huán)3次*/ { do{ printf("score%d:",i+1); scanf("%d",&score[i]); if(score[i]<0||score[i]>100)/*確保成績(jī)?cè)?~100之間*/ printf("Dataerror,pleaseenteragain.\n"); }while(score[i]<0||score[i]>100); } p1=head;/*給p1賦初值頭指針*/ while(j<k-1&&p1!=NULL) { j++; p1=p1->next;/*將p1指針指向下一條記錄*/ } if(p1==NULL)return0; else { p2=(LinkList*)malloc(sizeof(LinkList)); strcpy(p2->num,N); strcpy(p2->name,s); for(i=0;i<3;i++) p2->score[i]=score[i]; p2->next=p1->next; p1->next=p2; }}voidmenu_select()整理為word格式整理為word格式整理為word格式{ printf("\n\n\n"); printf("****************************************************\n"); printf("\tWelcometo\n"); printf("\tThestudentscoremanagesystem\n"); printf("**********************MENU**************************\n"); printf("\t\t1.輸入學(xué)生記錄\n");/*輸入學(xué)生成績(jī)記錄*/ printf("\t\t2.輸出學(xué)生記錄\n");/*顯示*/ printf("\t\t3.刪除學(xué)生記錄\n");/*刪除*/ printf("\t\t4.插入一個(gè)新的學(xué)生記錄\n");/*插入*/ printf("\t\t5.退出\n");/*退出*/ printf("****************************************************\n");}/*主函數(shù)界面*/voidScoreManage(){ LinkList*head,New; inti,n; head=init();/*鏈表初始化,使head的值為NULL*/ menu_select(); do{printf("\n\t\t輸入您的選擇(1~5):");scanf("%d",&n); }while(n<1||n>5); for(;;)/*循環(huán)無(wú)限次*/ { switch(n) { case1:head=create();break; case2:print(head);break; case3:head=Delete(head);break;整理為word格式整理為word格式整理為word格式 case4:head=Insert(head);break; case5:return;/*如菜單返回值為9則程序結(jié)束*/ } menu_select(); printf("\n\t\t\t輸入您的選擇(1~5):");scanf("%d",&n); }}//************************************************************//各種排序typedefintKeyType; /*定義關(guān)鍵字類型*/typedefcharInfoType[10];typedefstruct /*記錄類型*/{ KeyTypekey; /*關(guān)鍵字項(xiàng)*/ InfoTypedata; /*其他數(shù)據(jù)項(xiàng),類型為InfoType*/}RecType; /*排序的記錄類型定義*/voidInsertSort(RecTypeR[],intn)/*對(duì)R[0..n-1]按遞增有序進(jìn)行直接插入排序*/{ inti,j; RecTypetmp; for(i=1;i<n;i++) { tmp=R[i]; j=i-1;/*從右向左在有序區(qū)R[0..i-1]中找R[i]的插入位置*/整理為word格式整理為word格式整理為word格式 while(j>=0&&tmp.key<R[j].key) { R[j+1]=R[j];/*將關(guān)鍵字大于R[i].key的記錄后移*/ j--; } R[j+1]=tmp;/*在j+1處插入R[i]*/ }}voidBubbleSort(RecTypeR[],intn){ inti,j,exchange; RecTypetmp; for(i=0;i<n-1;i++) { exchange=0; for(j=n-1;j>i;j--) if(R[j].key<R[j-1].key) { tmp=R[j]; R[j]=R[j-1]; R[j-1]=tmp; exchange=1; } if(exchange==0)return; }}voidSelectSort(RecTypeR[],intn){ inti,j,k; RecTypetmp;整理為word格式整理為word格式整理為word格式 for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(R[j].key<R[k].key) k=j; if(k!=i) { tmp=R[i]; R[i]=R[k]; R[k]=tmp; } }}voiddisp(RecTypeR[],intn){ inti; for(i=0;i<n;i++) printf("%d",R[i].key);}voidSort(){ inti,n=10,k; RecTypeR[MaxSize]; KeyTypea[10]; printf("請(qǐng)輸入排序的關(guān)鍵字(10個(gè)數(shù)字)\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++)整理為word格式整理為word格式整理為word格式 R[i].key=a[i]; printf("\n\n直接插入排序:"); InsertSort(R,n); disp(R,n); printf("\n\n冒泡排序:"); BubbleSort(R,n); disp(R,n); printf("\n\n直接選擇排序:"); SelectSort(R,n); disp(R,n);}//************************************************************//建立二叉樹(shù)typedefcharElemType;typedefstructnode{ ElemTypedata; /*數(shù)據(jù)元素*/ structnode*lchild; /*指向左孩子結(jié)點(diǎn)*/ structnode*rchild; /*指向右孩子結(jié)點(diǎn)*/}BTNode;voidCreateBTNode(BTNode*&b,char*str){ BTNode*St[MaxSize],*p=NULL;整理為word格式整理為word格式整理為word格式 inttop=-1,k,j=0; charch; b=NULL; /*建立的二叉樹(shù)初始時(shí)為空*/ ch=str[j]; while(ch!='\0') /*str未掃描完時(shí)循環(huán)*/ { switch(ch) { case'(':top++;St[top]=p;k=1;break; /*為左孩子結(jié)點(diǎn)*/ case')':top--;break; case',':k=2;break; /*為孩子結(jié)點(diǎn)右結(jié)點(diǎn)*/ default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) /**p為二叉樹(shù)的根結(jié)點(diǎn)*/ b=p; else /*已建立二叉樹(shù)根結(jié)點(diǎn)*/ { switch(k) { case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }}整理為word格式整理為word格式整理為word格式voidDispBTNode(BTNode*b){ if(b!=NULL) { printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); /*有孩子結(jié)點(diǎn)時(shí)才輸出(*/ DispBTNode(b->lchild); /*遞歸處理左子樹(shù)*/ if(b->rchild!=NULL)printf(","); /*有右孩子結(jié)點(diǎn)時(shí)才輸出,*/ DispBTNode(b->rchild); /*遞歸處理右子樹(shù)*/ printf(")"); /*有孩子結(jié)點(diǎn)時(shí)才輸出)*/ } }}//先序遍歷非遞歸算法voidPreOrder(BTNode*b){ BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL){ top++; St[top]=b; while(top>-1) { p=St[top]; top--; printf("%c",p->data); if(p->rchild!=NULL)整理為word格式整理為word格式整理為word格式 { top++; St[top]=p->rchild; } if(p->lchild!=NULL) { top++; St[top]=p->lchild; } } printf("%c",b); printf("\n"); }}//中序遍歷非遞歸算法voidInOrder(BTNode*b){ BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL){ p=b; while(top>-1||p!=NULL) { while(p!=NULL) { top++; St[top]=p; p=p->lchild; }整理為word格式整理為word格式整理為word格式 if(top>-1) { p=St[top]; top--; printf("%c",p->data); p=p->rchild; } } printf("\n"); }}//后序遍歷非遞歸算法voidPostOrder(BTNode*b){ BTNode*St[MaxSize],*p; intflag,top=-1; if(b!=NULL) { do { while(b!=NULL) { top++; St[top]=b; b=b->lchild; } p=NULL; flag=1; while(top!=-1&&flag)整理為word格式整理為word格式整理為word格式 { b=St[top]; if(b->rchild==p) { printf("%c",b->data); top--; p=b; } else { b=b->rchild; flag=0; } } }while(top!=-1); printf("\n"); }}//層序遍歷voidLevelOrder(BTNode*b){ BTNode*p; BTNode*qu[MaxSize]; intfront,rear; front=rear=-1; rear++; qu[rear]=b; while(front!=rear) { front=(front+1)%MaxSize; p=qu[front];整理為word格式整理為word格式整理為word格式 printf("%c",p->data); if(p->lchild!=NULL) { rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%MaxSize; qu[rear]=p->rchild; } }}voidBTtree(){ BTNode*b; charstr[100]; printf("輸入你要建立二叉樹(shù)的結(jié)點(diǎn)："); scanf("%s",str); CreateBTNode(b,str); printf("\n\n建立二叉樹(shù)為："); DispBTNode(b); printf("\n\n二叉樹(shù)b的先序遍歷序列"); PreOrder(b); printf("\n\n二叉樹(shù)b的中序遍歷序列"); InOrder(b); printf("\n\n二叉樹(shù)b的后序遍歷序列"); PostOrder(b); printf("\n\n二叉樹(shù)b的層次遍歷序列"); LevelOrder(b); printf("\n\n");整理為word格式整理為word格式整理為word格式}//************************************************************//有序表的合并typedefcharElemType;typedefstruct{ ElemTypedata[MaxSize]; /*存放順序表元素*/ intlength; /*存放順序表的長(zhǎng)度*/}SqList; /*順序表的類型定義*/typedefstructLNode1 /*定義單鏈表結(jié)點(diǎn)類型*/{ ElemTypedata; structLNode1*next; /*指向后繼結(jié)點(diǎn)*/}LinkList1;voidInitList(SqList*&L){ L=(SqList*)malloc(sizeof(SqList)); /*分配存放線性表的空間*/ L->length=0;}voidInitList1(LinkList1*&L){ L=(LinkList1*)malloc(sizeof(LinkList1)); /*創(chuàng)建頭結(jié)點(diǎn)*/ L->next=NULL;}voidCreateList(SqList*&L,ElemTypea[],intn)/*建立順序表*/整理為word格式整理為word格式整理為word格式{ inti; for(i=0;i<n;i++) L->data[i]=a[i]; L->length=n;}voidCreateListR(LinkList1*&L,ElemTypea[],intn)/*尾插法建立單鏈表*/{ LinkList1*s,*r;inti; L=(LinkList1*)malloc(sizeof(LinkList1)); /*創(chuàng)建頭結(jié)點(diǎn)*/ L->next=NULL; r=L; /*r始終指向終端結(jié)點(diǎn),開(kāi)始時(shí)指向頭結(jié)點(diǎn)*/ for(i=0;i<n;i++) { s=(LinkList1*)malloc(sizeof(LinkList1));/*創(chuàng)建新結(jié)點(diǎn)*/ s->data=a[i]; r->next=s; /*將*s插入*r之后*/ r=s; } r->next=NULL; /*終端結(jié)點(diǎn)next域置為NULL*/}voidDispList(SqList*L){ inti; if(L->length==0)return; for(i=0;i<L->length;i++)整理為word格式整理為word格式整理為word格式 printf("%c",L->data[i]); printf("\n");}voidDispList1(LinkList1*L){ LinkList1*p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}//順序表存放有序表voidUnionList(SqList*LA,SqList*LB,SqList*&LC){ inti=0,j=0,k=0; /*i、j、k分別作為L(zhǎng)A、LB、LC的下標(biāo)*/ LC=(SqList*)malloc(sizeof(SqList)); LC->length=0; while(i<LA->length&&j<LB->length) { if(LA->data[i]<LB->data[j]) { LC->data[k]=LA->data[i]; i++;k++; } else /*LA->data[i]>LB->data[j]*/ { 整理為word格式整理為word格式整理為word格式 LC->data[k]=LB->data[j]; j++;k++; } } while(i<LA->length) /*LA尚未掃描完,將其余元素插入LC中*/ { LC->data[k]=LA->data[i]; i++;k++; } while(j<LB->length)/*LB尚未掃描完,將其余元素插入LC中*/ { LC->data[k]=LB->data[j]; j++;k++; } LC->length=k;}//單鏈表存放有序表voidUnionList1(LinkList1*LA,LinkList1*LB,LinkList1*&LC){ LinkList1*pa=LA->next,*pb=LB->next,*pc,*s; LC=(LinkList1*)malloc(sizeof(LinkList1)); /*創(chuàng)建LC的頭結(jié)點(diǎn)*/ pc=LC; /*pc始終指向LC的最后一個(gè)結(jié)點(diǎn)*/ while(pa!=NULL&&pb!=NULL) { if(pa->data<pb->data) { s=(LinkList1*)malloc(sizeof(LinkList1));/*復(fù)制*pa結(jié)點(diǎn)*/整理為word格式整理為word格式整理為word格式 s->data=pa->data; pc->next=s;pc=s; /*采用尾插法將*s插入到LC的最后*/ pa=pa->next; }else { s=(LinkList1*)malloc(sizeof(LinkList1));/*復(fù)制*pb結(jié)點(diǎn)*/ s->data=pa->data; pc->next=s;pc=s; /*采用尾插法將*s插入到LC的最后*/ pa=pa->next; } } while(pa!=NULL) { s=(LinkList1*)malloc(sizeof(LinkList1)); /*復(fù)制*pa結(jié)點(diǎn)*/ s->data=pa->data; pc->next=s;pc=s; /*采用尾插法將*s插入到LC的最后*/ pa=pa->next; } while(pb!=NULL) { s=(LinkList1*)malloc(sizeof(LinkList1)); /*復(fù)制*pa結(jié)點(diǎn)*/ s->data=pb->data; pc->next=s;pc=s; /*采用尾插法將*s插入到LC的最后*/ pb=pb->next; } pc->next=NULL;}voidUnion()整理為word格式整理為word格式整理為word格式{ SqList*L1,*L2,*L3; LinkList1*L4,*L5,*L6; ElemTypea[5]; ElemTypeb[5]; printf("a[]=:");scanf("%s",a); printf("b[]=:");scanf("%s",b); printf("順序表存放有序表的合并\n"); InitList(L1); InitList(L2); InitList(L3); CreateList(L1,a,3); printf("L1:");DispList(L1); CreateList(L2,b,4); printf("L2:");DispList(L2); printf("歸并\n"); UnionList(L1,L2,L3); printf("L3:");DispList(L3); printf("單鏈表存放有序表的合并\n"); InitList1(L4); InitList1(L5); InitList1(L6); CreateListR(L4,a,3); printf("L4:");DispList1(L4); Cr