【正文】 容。(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 (1)初始化并建立鏈隊(duì)列(2.)入鏈隊(duì)列(3)出鏈隊(duì)列(4)遍歷鏈隊(duì)列四、實(shí)現(xiàn)提示1./*定義順序棧的存儲結(jié)構(gòu)*/ typedef struct { ElemType stack[MAXNUM]。}SqStack。/*申請空間*/} /*入棧函數(shù)*/ void Push(SqStack *p,ElemType x){if(ptoptop=ptop+1。} /*數(shù)據(jù)入棧*/ } /*出棧函數(shù)*/ ElemType Pop(SqStack *p){x=pstack[ptop]。} /*棧頂1*/ /*獲取棧頂元素函數(shù)*/ ElemType GetTop(SqStack *p){ x=pstack[ptop]。i=0。} /*置空順序棧函數(shù)*/ void setEmpty(SqStack *p){ ptop=1。main(){SqStack S。int N。}2./*定義鏈隊(duì)列*/ typedef struct Qnode { ElemType data。}Qnodetype。Qnodetype *rear。/*初始化并建立鏈隊(duì)列函數(shù)*/ void creat(Lqueue *q){ h=(Qnodetype*)malloc(sizeof(Qnodetype))。qfront=h。for(i=1。snext=NULL。qrear=s。qfrontnext=pnext。x=pdata。} /*釋放空間*/ /*遍歷鏈隊(duì)列函數(shù)*/ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊(duì)尾*/ { printf(“%d”,pdata)。} } 可參考如下代碼： include “” define MaxSize 100 typedef int ElemType。ElemType e。Q)。}五、思考與提高？ 試寫一個算法，判別讀入的一個以‘’為結(jié)束符的字符序列是否是?回文?。,并通過調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。、中序遍歷與后序遍歷二叉樹。typedef char ElemType。struct BiTNode *lchild,*rchild。/*建立二叉樹*/BiTree CreateBiTree(BiTree amp。CreateBiTree(T)。printf(“n”)。printf(“n”)。printf(“n”)。}五、思考與提高編寫遞歸算法，計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。6 實(shí)驗(yàn)四 二叉樹8 實(shí)驗(yàn)六 內(nèi)部排序預(yù)習(xí)要求如下：（1）認(rèn)真閱讀指導(dǎo)書，進(jìn)行必要的設(shè)計與計算。（3）預(yù)先復(fù)習(xí)，并按要求編寫程序。遵守以下紀(jì)律：（1）在實(shí)驗(yàn)室不得做和實(shí)驗(yàn)無關(guān)的事情。（3）遵守紀(jì)律，不遲到。實(shí) 驗(yàn) 環(huán) 境本實(shí)驗(yàn)在386以上的微機(jī)上進(jìn)行。二、預(yù)習(xí)要求看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)一個簡單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有：利用單鏈表建立學(xué)生基本信息表瀏覽每個學(xué)生的信息根據(jù)學(xué)號查詢某個學(xué)生的基本信息添加學(xué)生信息到單鏈表中刪除一個學(xué)生的信息四、實(shí)現(xiàn)提示設(shè)計結(jié)點(diǎn)的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號、姓名、年齡、性別；要求設(shè)計一個簡單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個函數(shù)實(shí)現(xiàn)上述的一個功能。二、預(yù)習(xí)要求看懂書上的算法，深入理解鏈表的物理存儲模式和邏輯模式。三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)單鏈表的就地逆置。建立兩個非遞減有序單鏈表，然后合并成一個非遞增鏈表。四、選做題、思考題如何用帶表頭結(jié)點(diǎn)的單鏈表作為多項(xiàng)式的存儲表示，實(shí)現(xiàn)兩個多項(xiàng)式的相加。如何利用文件實(shí)現(xiàn)學(xué)生信息的存取。二、預(yù)習(xí)要求看懂書上的算法，深入理解棧的特性和存儲結(jié)構(gòu)，以便在實(shí)際問題背景下靈活運(yùn)用。三、實(shí)驗(yàn)內(nèi)容利用棧實(shí)現(xiàn)數(shù)據(jù)的分類，要求當(dāng)輸入為偶數(shù)時進(jìn)棧1，當(dāng)輸入為奇數(shù)時進(jìn)棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。采用順序存儲實(shí)現(xiàn)棧的初始化、入棧、出棧操作。編寫程序，利用棧實(shí)現(xiàn)表達(dá)式求值。二、預(yù)習(xí)要求二叉樹的三種遍歷方法。利用棧，編寫非遞歸算法，編程實(shí)現(xiàn)二叉樹的中序遍歷。在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。如何求二叉樹的高度。二、預(yù)習(xí)要求學(xué)習(xí)了解圖的存儲結(jié)構(gòu)，掌握求最短路徑的兩種算法。四、實(shí)現(xiàn)提示咨詢以用戶和計算機(jī)的對話方式進(jìn)行，由用戶輸入起始點(diǎn)和終點(diǎn)，輸出信息：最短路徑是多少？并指出所經(jīng)過的城市。五、選做題、思考題1．如何實(shí)現(xiàn)對城市信息進(jìn)行編輯（如：添加或刪除）的功能。實(shí)驗(yàn)六 內(nèi)部排序一、實(shí)驗(yàn)?zāi)康闹庇^感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)。根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。利用鏈?zhǔn)酱鎯Y(jié)構(gòu)，編寫程序，實(shí)現(xiàn)直接插入排序和冒泡排序。五、選做題、思考題快速排序算法的非遞歸實(shí)現(xiàn)。如何對本實(shí)驗(yàn)進(jìn)行時間、空間的復(fù)雜度分析。本課程系統(tǒng)地介紹了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲結(jié)構(gòu)和實(shí)現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對其進(jìn)行了性能分析和比較，內(nèi)容非常豐富。由于以下原因，使得掌握這門課程具有較大難度： 貫穿全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)和難點(diǎn)； 先修課程中所介紹的專業(yè)性知識不多，加大了學(xué)習(xí)難度。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計所需的技術(shù)，為整個專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運(yùn)用所學(xué)知識，上機(jī)解決一些典型問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。通過上機(jī)實(shí)踐，使學(xué)生在可能短的時間內(nèi)對數(shù)據(jù)結(jié)構(gòu)知識的實(shí)踐和應(yīng)用有一個比較全面和系統(tǒng)的認(rèn)識，達(dá)到理論與實(shí)踐相結(jié)合的目的。每個實(shí)驗(yàn)題目采取了統(tǒng)一的格式，由問題描述、基本要求、測試數(shù)據(jù)、實(shí)現(xiàn)提示等部分組成。下面帶*的題目為選做題目。）的概念及使用方法，為理解數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)內(nèi)容以及算法書寫奠定基礎(chǔ)。要求：在函數(shù)聲明中采用引用參數(shù)傳遞方式實(shí)現(xiàn)最大、最小值的返回。2 關(guān)于指針的使用：用malloc方式分別申請兩個指針，并實(shí)現(xiàn)兩個指針內(nèi)容的比較大小操作。測試：從主函數(shù)中輸入兩個數(shù)，調(diào)用該函數(shù)，打印輸出交換后的值。掌握單鏈表的定義、創(chuàng)建、插入、刪除、遍歷等基本操作的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容問題描述：已知遞增有序的單鏈表A，編寫算法實(shí)現(xiàn)向A中插入或刪除一個元素，并保持A的有序性。若表中已經(jīng)存在此元素，則不插入三、實(shí)現(xiàn)提示，需要下面的輔助函數(shù)：線性表的創(chuàng)建、線性表的遍歷，需依次實(shí)現(xiàn)：a)單鏈表結(jié)構(gòu)的定義b)單鏈表的創(chuàng)建（頭插法或尾插法建表）c)單鏈表的遍歷d)單鏈表的插入、刪除（采用順序查找方法，順頭指針往后，查找插入或刪除位置，再修改指針）//頭文件include “” //預(yù)定義常量 define NULL 0//單鏈表的定義typedef struct LNode{ int data。}LNode,*LinkList。L){ int data。L=(LinkList)malloc(sizeof(LNode))。q=L。data)。pdata=data。qnext=p。scanf(“%d”,amp。} }//單鏈表的遍歷void TranverseList(LinkList L){LinkList p。if(p==NULL){printf(“niln”)。}while(p!=NULL){printf(“%d ”,pdata)。}printf(“n”)。熟悉棧的應(yīng)用。二、實(shí)驗(yàn)內(nèi)容 問題描述：利用棧實(shí)現(xiàn)十進(jìn)制數(shù)n轉(zhuǎn)化為d進(jìn)制數(shù) 要求：1)輸入一個n和d，打印輸出d進(jìn)制數(shù)序列。此時，需要同時實(shí)現(xiàn)初始化空棧、入棧、出棧、判?？盏容o助功能。要求：1)參與運(yùn)算的操作數(shù)為10以內(nèi)的數(shù)值。實(shí)驗(yàn)四 二叉樹的遞歸算法一、實(shí)驗(yàn)?zāi)康恼莆斩鏄涞谋硎九c實(shí)現(xiàn)。熟悉求二叉樹深度等遞歸算法的設(shè)計與實(shí)現(xiàn)。要求：二叉樹分別采用順序或二叉鏈表存儲。測試數(shù)據(jù)：輸入序列：+a216。*b216。c216。d216。/e216。f216。創(chuàng)建二叉樹； 輸出：深度：5前序序列：+a*bcd/ef中序序列：a+b*cde/f后序序列：abcd*+ef/T:d / e ft=nil輸入：216。二、實(shí)驗(yàn)內(nèi)容問題描述：已知的描述校園景點(diǎn)的圖，實(shí)現(xiàn)對該圖的深度優(yōu)先和廣度優(yōu)先遍歷。實(shí)驗(yàn)六 有序表的查找一、實(shí)驗(yàn)?zāi)康睦斫飧鞣N查找方法的基本思想熟悉有序表查找方法的算法實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容 已知一有序的序列{1,3,5,7,9}，采用折半法分別查找3和6。實(shí)驗(yàn)七 哈希表一、實(shí)驗(yàn)?zāi)康睦斫夤１淼母拍詈突静僮?；熟悉哈希表的?chuàng)建、查找、插入的算法實(shí)現(xiàn)。要求：好友的信息包含名字和生日兩個數(shù)據(jù)項(xiàng)，其中好友的名字為主鍵，用漢語拼音形式存放；哈希函數(shù)采?。汉糜衙种兴衅匆糇帜窤SCII碼值的和 MOD 11(除以1取余)；采取線性探測再散列的方式處理沖突。