數(shù)據(jù)結(jié)構(gòu)實驗

數(shù)據(jù)結(jié)構(gòu)實驗第一頁，共三十九頁，編輯于2023年，星期三實驗一C語言復習教學目的與要求

本實驗的目的是幫助大家復習C語言的使用方法，特別是指針、結(jié)構(gòu)體的內(nèi)容，同時也為以后的各個實驗做準備

教學的重點與難點

指針、結(jié)構(gòu)體、數(shù)組三種數(shù)據(jù)類型的混合使用第二頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容指針指向數(shù)組后，數(shù)組元素的訪問有哪些形式？在下列類型定義后，表達式a[3].num的邏輯含義是什么？類型是什么？ structstudent {longnum； floatscore； structstudent*next； }a[5]；答:3號元素的num數(shù)據(jù)域long類型第三頁，共三十九頁，編輯于2023年，星期三例題#defineNULL0structstudent{longnum；floatscore；structstudent*next；}；main(){structstudenta,b,c,*head,*p；a.num=99101；a.score=89.5；b.num=99103；b.score=90；c.num=99107；c.score=85；//a、b、c變量賦值head=&a；a.next=&b；//a的后續(xù)為bb.next=&c；c.next=NULL；p=head；do{printf（“%ld%5.1f\n”,p->num,p->score

）；/*輸出學號和成績*/

p=p->next；}while(

)；}答：p!=NULL第四頁，共三十九頁，編輯于2023年，星期三9、設(shè)計一個可進行復數(shù)運算的演示程序。要求：實現(xiàn)下列六種基本運算：1）由輸入的實部和虛部生成一個復數(shù)；2）兩個復數(shù)求和；3）兩個復數(shù)求差；4）兩個復數(shù)求積；5）從已知復數(shù)中分離出實部；6）從已知復數(shù)中分離出虛部。運算結(jié)果以相應(yīng)的復數(shù)或?qū)崝?shù)的表示形式顯示。10、設(shè)計一個可進行有理數(shù)運算的演示程序。要求：實現(xiàn)兩個有理數(shù)相加、相減、相乘以及求分子或求分母的運算。實驗內(nèi)容及要求第五頁，共三十九頁，編輯于2023年，星期三有10個學生，每個學生的數(shù)據(jù)包括學號、姓名、3門課的成績，從鍵盤輸入10個學生數(shù)據(jù)，要求打印出3門課總平均成績，以及最高分的學生的數(shù)據(jù)。要求：用input函數(shù)輸入10個學生數(shù)據(jù)，用average函數(shù)求總平均分；用max函數(shù)找出最高分的學生數(shù)據(jù)；總平均分和最高分學生的數(shù)據(jù)都在主函數(shù)中輸出。實驗內(nèi)容及要求第六頁，共三十九頁，編輯于2023年，星期三討論指出下列程序段的錯誤：structstudent{longnum；floatscore；structstudent*next；}a,b,c,*p；a.next=&b;b.next=&c;p=a;while(p){printf(“%ld%5.2f”,p->num,p->score);P++;}答：增加：c.next=NULL;p=a;=>P=&a;P++;=>P=p->next;第七頁，共三十九頁，編輯于2023年，星期三第二講線性表教學目的與要求掌握數(shù)據(jù)結(jié)構(gòu)中表的基本概念。熟練掌握線性表的基本操作，插入、刪除、查找等運算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的實現(xiàn)。熟練掌握鏈表的各種操作和應(yīng)用。教學的重點與難點線性表的基本操作在鏈接存儲結(jié)構(gòu)上的實現(xiàn)。第八頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容完成下列程序，指出main的結(jié)構(gòu)#include<stdio.h>#defineMaxLen50typedefintelemtype；structdatatype{elemtype*elem;intlength;}typedefstructdatatypesqlist；第九頁，共三十九頁，編輯于2023年，星期三voidcreate(sqlist*a){inti,n；a->elem=(elemtype*)malloc(MaxLen*sizeof(elemtype));printf（“創(chuàng)建一個順序表\n”）；printf（“輸入元素個數(shù)：”）；scanf（“%d",&a->length)；for(i=0；i<a->length；i++){printf（“輸入第%d個元素值：”,i）；scanf（“%d",a->elem+i)；}}第十頁，共三十九頁，編輯于2023年，星期三voidinvert(sqlist*a){intm=a->length/2,I；elemtypetemp；for(I=0；I<m；I++){temp=

;*(a->elem+i)=

;

=temp;}}(1)*(a->elem+i)(2)*(a->elem+a->length-1-i)(3))*(a->elem+a->length-1-i)第十一頁，共三十九頁，編輯于2023年，星期三Voiddisp(sqlist*a){intI;for(i=0;i<n;i++)printf(“%5d:%d\n”,i+1,*(a->elem+i));}第十二頁，共三十九頁，編輯于2023年，星期三voidmain(){sqlistb,*a；a=&b;;create(a)；disp(a)；invert(a)；disp(a)；}第十三頁，共三十九頁，編輯于2023年，星期三實驗內(nèi)容及要求4、7、13必做，其余老師選做幾題4、鍵盤輸入學生信息（包括學號和成績），學號為0作為結(jié)束標志，建立其對應(yīng)的線性表并輸出各結(jié)點中的數(shù)據(jù)。注：試以順序表和單鏈表兩種不同的存儲結(jié)構(gòu)實現(xiàn)。第十四頁，共三十九頁，編輯于2023年，星期三7、設(shè)計一個算法求A和B兩個單鏈表表示的集合的并集。提示：將A和B合并。9、用頭插法把單鏈表b中在單鏈表a中未出現(xiàn)的結(jié)點合并到單鏈表a中。第十五頁，共三十九頁，編輯于2023年，星期三實驗三棧和隊列教學目的與要求了解棧和隊列的特性，以便靈活應(yīng)用。熟練掌握棧和有關(guān)隊列的各種操作和應(yīng)用。

教學的重點與難點棧和有關(guān)隊列的各種操作和應(yīng)用

第十六頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容1、棧頂指針是棧頂元素的地址或是棧頂前一元素的地址,確定標準是什么?答:由程序員自己確定,在壓棧和彈棧操作時來實現(xiàn)2、在實際應(yīng)用中，是采用一般隊列還是循環(huán)隊列的依據(jù)是什么？答：實際應(yīng)用中，是否存在假溢出問題。第十七頁，共三十九頁，編輯于2023年，星期三實驗內(nèi)容及要求3、4必做，5選做3、設(shè)一個算術(shù)表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個算法判斷其中的括號是否匹配。4、到醫(yī)院看病的過程是，患者先排隊等候，排隊過程中主要重復兩件事：（1）病人到達診室時，將病歷交給護士，排到等候隊列中候診。（2）護士從等候隊列中取出下一個患者的病歷，該患者進入診室就診。第十八頁，共三十九頁，編輯于2023年，星期三5、設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達式求值的過程。基本要求：以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用教科書表3.1給出的算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值，并仿照教科書的例3_1演示在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。測試數(shù)據(jù)：3*（7-2）實驗內(nèi)容及要求第十九頁，共三十九頁，編輯于2023年，星期三實驗四串教學目的與要求掌握串的基本概念，存儲方法及主要運算。將串的運算應(yīng)用到文本編輯中。教學的重點與難點子串的操作第二十頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容串的順序存儲結(jié)構(gòu)包括哪兩種存儲方式？答：靜態(tài)分配和動態(tài)分配的順序存儲結(jié)構(gòu)。靜態(tài)分配：typedefstruct{charch[maxstrlen];

intlength}sstring;動態(tài)分配：typedefstruct{char*ch;intlength;}hsring;第二十一頁，共三十九頁，編輯于2023年，星期三實驗內(nèi)容及要求3、4必做，5選做3、采用順序結(jié)構(gòu)存儲串，編寫一個函數(shù)index(s1,s2),用于s2是否是s1的子串。若是，返回其在主串中的位置；否則返回-1。4、利用串的基本運算，編寫一個算法刪除串s1中所有s2子串。提示：本題利用3題的index()函數(shù)和刪除子串函數(shù)循環(huán)實現(xiàn)。第二十二頁，共三十九頁，編輯于2023年，星期三5、已知s=“(xyz)+*”,t=“(x+z)*y”。試利用連接、求子串和置換等操作，將s轉(zhuǎn)化為t。實驗內(nèi)容及要求第二十三頁，共三十九頁，編輯于2023年，星期三實驗五數(shù)組和廣義表教學目的與要求熟練掌握數(shù)組的存儲表示和實現(xiàn)。熟悉廣義表的存儲結(jié)構(gòu)的特性。教學的重點與難點

數(shù)組的存儲表示和常用操作的實現(xiàn)

第二十四頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容數(shù)組與一般線性表的區(qū)別？答：數(shù)組結(jié)構(gòu)固定數(shù)據(jù)元素同構(gòu)為什么數(shù)組元素可以隨機訪問?答:可以通過地址計算公式來求得任意元素的地址第二十五頁，共三十九頁，編輯于2023年，星期三實驗內(nèi)容及要求3、6必做3、試設(shè)計一個算法，將A[0..n-1]中所有奇數(shù)移到偶數(shù)之前。要求不另增加存儲空間，且時間復雜度為O(n)。提示：i從左向右遍歷，指向A左邊的一個偶數(shù)，j從右向左遍歷，指向A右邊的一個奇數(shù)，然后將A[i]與A[j]交換。如此循環(huán)直到i大于等于j。第二十六頁，共三十九頁，編輯于2023年，星期三6、稀疏矩陣運算器基本要求：以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現(xiàn)兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結(jié)果的矩陣則以通常的陣列形式列出。實驗內(nèi)容及要求第二十七頁，共三十九頁，編輯于2023年，星期三實驗六樹教學目的與要求1.掌握二叉樹，二叉樹排序數(shù)的概念及存儲方法。2.掌握二叉樹的遍歷算法。3.熟練掌握編寫實現(xiàn)樹的各種運算的算法。教學的重點與難點二叉樹的遍歷操作及其應(yīng)用第二十八頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容1、下列程序段的功能是什么？2、二叉樹的遍歷常用哪些方式？答：1、建立排序樹2、先序、中序、后序、層次第二十九頁，共三十九頁，編輯于2023年，星期三實驗內(nèi)容及要求3、4必做3、編寫程序，實現(xiàn)按層次遍歷二叉樹。4、編寫程序，對二叉樹進行先序遍歷，并打印層號。第三十頁，共三十九頁，編輯于2023年，星期三實驗七圖教學目的與要求1.熟悉圖的各種存儲方法。2.掌握遍歷圖的遞歸和非遞歸的算法。3.理解圖的有關(guān)算法。教學的重點與難點圖的建立及圖的常用操作的實現(xiàn)第三十一頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容下列程序段的功能是什么？圖的存儲結(jié)構(gòu)是什么？答：1、建立圖2、此程序段中，圖的存儲結(jié)構(gòu)是鄰接表第三十二頁，共三十九頁，編輯于2023年，星期三實驗內(nèi)容及要求2、3必做2、編寫程序，實現(xiàn)無向圖的深度優(yōu)先搜索。3、有一個鄰接表存儲的圖G，分別設(shè)計實現(xiàn)以下要求的算法：求出圖中每個頂點的出度；計算圖中出度為0的頂點數(shù)。第三十三頁，共三十九頁，編輯于2023年，星期三實驗八查找教學目的與要求1.掌握順序查找，二分法查找和分塊查找的算法。2.能運用線性表的查找方法解決實際問題。教學的重點與難點順序查找、二分查找實現(xiàn)及應(yīng)用

第三十四頁，共三十九頁，編輯于2023年，星期三實驗預(yù)習檢查內(nèi)容順序查找、二分查找的對象有什么區(qū)別?答:順序查找的對象可以是有序或無序表;二分查找的對象必須是有序表.

順序查找、二分查找的對象的存儲結(jié)構(gòu)分別是什么?答:順序查找對象可以是順序表或鏈表