【正文】 要求：好友的信息包含名字和生日兩個(gè)數(shù)據(jù)項(xiàng)，其中好友的名字為主鍵，用漢語拼音形式存放；哈希函數(shù)采?。汉糜衙种兴衅匆糇帜窤SCII碼值的和 MOD 11(除以1取余)；采取線性探測再散列的方式處理沖突。實(shí)驗(yàn)六 有序表的查找一、實(shí)驗(yàn)?zāi)康睦斫飧鞣N查找方法的基本思想熟悉有序表查找方法的算法實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容 已知一有序的序列{1,3,5,7,9}，采用折半法分別查找3和6。創(chuàng)建二叉樹； 輸出：深度：5前序序列：+a*bcd/ef中序序列：a+b*cde/f后序序列：abcd*+ef/T:d / e ft=nil輸入：216。/e216。c216。測試數(shù)據(jù)：輸入序列：+a216。熟悉求二叉樹深度等遞歸算法的設(shè)計(jì)與實(shí)現(xiàn)。要求：1)參與運(yùn)算的操作數(shù)為10以內(nèi)的數(shù)值。二、實(shí)驗(yàn)內(nèi)容 問題描述：利用棧實(shí)現(xiàn)十進(jìn)制數(shù)n轉(zhuǎn)化為d進(jìn)制數(shù) 要求：1)輸入一個(gè)n和d，打印輸出d進(jìn)制數(shù)序列。}printf(“n”)。if(p==NULL){printf(“niln”)。scanf(“%d”,amp。pdata=data。q=L。L){ int data。若表中已經(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。掌握單鏈表的定義、創(chuàng)建、插入、刪除、遍歷等基本操作的實(shí)現(xiàn)。2 關(guān)于指針的使用：用malloc方式分別申請兩個(gè)指針，并實(shí)現(xiàn)兩個(gè)指針內(nèi)容的比較大小操作。）的概念及使用方法，為理解數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)內(nèi)容以及算法書寫奠定基礎(chǔ)。每個(gè)實(shí)驗(yàn)題目采取了統(tǒng)一的格式，由問題描述、基本要求、測試數(shù)據(jù)、實(shí)現(xiàn)提示等部分組成。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計(jì)所需的技術(shù)，為整個(gè)專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些典型問題，通過分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。 貫穿全書的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)和難點(diǎn)； 本課程系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對其進(jìn)行了性能分析和比較，內(nèi)容非常豐富。五、選做題、思考題快速排序算法的非遞歸實(shí)現(xiàn)。根據(jù)要求，編寫程序準(zhǔn)備上機(jī)調(diào)試。五、選做題、思考題1．如何實(shí)現(xiàn)對城市信息進(jìn)行編輯（如：添加或刪除）的功能。二、預(yù)習(xí)要求學(xué)習(xí)了解圖的存儲(chǔ)結(jié)構(gòu)，掌握求最短路徑的兩種算法。在主函數(shù)中設(shè)計(jì)一個(gè)簡單的菜單，分別調(diào)試上述算法。二、預(yù)習(xí)要求二叉樹的三種遍歷方法。采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。二、預(yù)習(xí)要求看懂書上的算法，深入理解棧的特性和存儲(chǔ)結(jié)構(gòu)，以便在實(shí)際問題背景下靈活運(yùn)用。四、選做題、思考題如何用帶表頭結(jié)點(diǎn)的單鏈表作為多項(xiàng)式的存儲(chǔ)表示，實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加。三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)單鏈表的就地逆置。三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)一個(gè)簡單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有：利用單鏈表建立學(xué)生基本信息表瀏覽每個(gè)學(xué)生的信息根據(jù)學(xué)號查詢某個(gè)學(xué)生的基本信息添加學(xué)生信息到單鏈表中刪除一個(gè)學(xué)生的信息四、實(shí)現(xiàn)提示設(shè)計(jì)結(jié)點(diǎn)的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號、姓名、年齡、性別；要求設(shè)計(jì)一個(gè)簡單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個(gè)函數(shù)實(shí)現(xiàn)上述的一個(gè)功能。實(shí) 驗(yàn) 環(huán) 境本實(shí)驗(yàn)在386以上的微機(jī)上進(jìn)行。遵守以下紀(jì)律：（1）在實(shí)驗(yàn)室不得做和實(shí)驗(yàn)無關(guān)的事情。預(yù)習(xí)要求如下：（1）認(rèn)真閱讀指導(dǎo)書，進(jìn)行必要的設(shè)計(jì)與計(jì)算。printf(“n”)。printf(“n”)。/*建立二叉樹*/BiTree CreateBiTree(BiTree amp。typedef char ElemType。,并通過調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。Q)。} } 可參考如下代碼： include “” define MaxSize 100 typedef int ElemType。x=pdata。qrear=s。for(i=1。/*初始化并建立鏈隊(duì)列函數(shù)*/ void creat(Lqueue *q){ h=(Qnodetype*)malloc(sizeof(Qnodetype))。}Qnodetype。int N。} /*置空順序棧函數(shù)*/ void setEmpty(SqStack *p){ ptop=1。} /*棧頂1*/ /*獲取棧頂元素函數(shù)*/ ElemType GetTop(SqStack *p){ x=pstack[ptop]。/*申請空間*/} /*入棧函數(shù)*/ void Push(SqStack *p,ElemType x){if(ptoptop=ptop+1。(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 (1)初始化并建立鏈隊(duì)列(2.)入鏈隊(duì)列(3)出鏈隊(duì)列(4)遍歷鏈隊(duì)列四、實(shí)現(xiàn)提示1./*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/ typedef struct { ElemType stack[MAXNUM]。五、思考與提高，應(yīng)如何建立順序表。注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。用C語言描述結(jié)點(diǎn)結(jié)構(gòu)如下：typedef int elemtype。/* 順序表的長度 */ }sequenlist。因此，可用C語言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68。——單鏈表中的各種基本操作。(R[i].score六、實(shí)驗(yàn)總結(jié)與思考。R[max]=R[i]。printf(“n請輸入學(xué)生成績: n”)。五、實(shí)驗(yàn)提示define n 30 typedef struct student { char name[8]。實(shí)驗(yàn)四排序（設(shè)計(jì)性實(shí)驗(yàn)）一、實(shí)驗(yàn)?zāi)康?，并掌握用高級語言實(shí)現(xiàn)排序算法的方法； ，并能加以靈活應(yīng)用； 。i,amp。/*求雙親結(jié)點(diǎn)的編號j*/if(i % 2 == 0)s[j]lchild = q。qlchild = NULL。 x!= 39。i,amp。int j,i,x。} 三元順序表的轉(zhuǎn)置 方法：(1)將矩陣行列互換，(2)重排矩陣六、實(shí)驗(yàn)總結(jié)與思考？？實(shí)驗(yàn)三樹與二叉樹（設(shè)計(jì)性實(shí)驗(yàn)）一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)內(nèi)容 三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦四、實(shí)驗(yàn)步驟，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。aa249。它上面的元素之和為((1+(i1))(i1)/2，左邊的元素為(j1)所以這個(gè)元素存儲(chǔ)的位置為k=i(i1)/2+j1。235。234。A=aaa234。=234。三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦四、實(shí)驗(yàn)步驟。六、實(shí)驗(yàn)總結(jié)與思考，應(yīng)如何建立順序表。注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。用C語言描述結(jié)點(diǎn)結(jié)構(gòu)如下：typedef int elemtype。/*順序表的長度 */ }sequenlist。因此，可用C語言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68?！獑捂湵碇械母鞣N基本操作。對C語言程序不熟悉的同學(xué)，上機(jī)時(shí)最好帶上C語言程序設(shè)計(jì)的教材，以備查閱。心得：軟件設(shè)計(jì)與實(shí)現(xiàn)過程中的經(jīng)驗(yàn)與體會(huì)，進(jìn)一步改進(jìn)的設(shè)想。需求分析：以無歧義的陳述說明程序設(shè)計(jì)的任務(wù)、約束條件、輸入輸出要求、對功能的規(guī)定及模型。硬件要求：在多媒體教室講解及演示。實(shí)現(xiàn)簡單的先序遍歷，中序遍歷和后序遍歷算法。各實(shí)驗(yàn)單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個(gè)實(shí)驗(yàn)題常常涉及到幾部分教學(xué)內(nèi)容。，以便為應(yīng)用設(shè)計(jì)的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。、編譯、調(diào)試程序。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法分析、設(shè)計(jì)能力及良好的程序設(shè)計(jì)習(xí)慣。typedef RecType SeqList[n+1]。define n 10typedef int KeyType。即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。如：void CreateBinTree(BinTree amp。//左右孩子指針 } BinTNode。并實(shí)現(xiàn)哈夫曼編碼。具體實(shí)現(xiàn)要求：(1)基于先序遍歷的構(gòu)造算法：輸入是二叉樹的先序序列，但必須在其中加入虛結(jié)點(diǎn)以示空指針的位置。、刪除結(jié)點(diǎn)的方法。建議課時(shí)安排如下：課外 2學(xué)時(shí)，課內(nèi)2學(xué)時(shí)【實(shí)驗(yàn)提示】：(1)以順序表為存儲(chǔ)結(jié)構(gòu)：可以用簡單的數(shù)組