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

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

教學(xué)的重點(diǎn)與難點(diǎn)

指針、結(jié)構(gòu)體、數(shù)組三種數(shù)據(jù)類型的混合使用第二頁(yè)，共三十九頁(yè)，編輯于2023年，星期三實(shí)驗(yàn)預(yù)習(xí)檢查內(nèi)容指針指向數(shù)組后，數(shù)組元素的訪問(wèn)有哪些形式？在下列類型定義后，表達(dá)式a[3].num的邏輯含義是什么？類型是什么？ structstudent {longnum； floatscore； structstudent*next； }a[5]；答:3號(hào)元素的num數(shù)據(jù)域long類型第三頁(yè)，共三十九頁(yè)，編輯于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

）；/*輸出學(xué)號(hào)和成績(jī)*/

p=p->next；}while(

)；}答：p!=NULL第四頁(yè)，共三十九頁(yè)，編輯于2023年，星期三9、設(shè)計(jì)一個(gè)可進(jìn)行復(fù)數(shù)運(yùn)算的演示程序。要求：實(shí)現(xiàn)下列六種基本運(yùn)算：1）由輸入的實(shí)部和虛部生成一個(gè)復(fù)數(shù)；2）兩個(gè)復(fù)數(shù)求和；3）兩個(gè)復(fù)數(shù)求差；4）兩個(gè)復(fù)數(shù)求積；5）從已知復(fù)數(shù)中分離出實(shí)部；6）從已知復(fù)數(shù)中分離出虛部。運(yùn)算結(jié)果以相應(yīng)的復(fù)數(shù)或?qū)崝?shù)的表示形式顯示。10、設(shè)計(jì)一個(gè)可進(jìn)行有理數(shù)運(yùn)算的演示程序。要求：實(shí)現(xiàn)兩個(gè)有理數(shù)相加、相減、相乘以及求分子或求分母的運(yùn)算。實(shí)驗(yàn)內(nèi)容及要求第五頁(yè)，共三十九頁(yè)，編輯于2023年，星期三有10個(gè)學(xué)生，每個(gè)學(xué)生的數(shù)據(jù)包括學(xué)號(hào)、姓名、3門(mén)課的成績(jī)，從鍵盤(pán)輸入10個(gè)學(xué)生數(shù)據(jù)，要求打印出3門(mén)課總平均成績(jī)，以及最高分的學(xué)生的數(shù)據(jù)。要求：用input函數(shù)輸入10個(gè)學(xué)生數(shù)據(jù)，用average函數(shù)求總平均分；用max函數(shù)找出最高分的學(xué)生數(shù)據(jù)；總平均分和最高分學(xué)生的數(shù)據(jù)都在主函數(shù)中輸出。實(shí)驗(yàn)內(nèi)容及要求第六頁(yè)，共三十九頁(yè)，編輯于2023年，星期三討論指出下列程序段的錯(cuò)誤：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;第七頁(yè)，共三十九頁(yè)，編輯于2023年，星期三第二講線性表教學(xué)目的與要求掌握數(shù)據(jù)結(jié)構(gòu)中表的基本概念。熟練掌握線性表的基本操作，插入、刪除、查找等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。熟練掌握鏈表的各種操作和應(yīng)用。教學(xué)的重點(diǎn)與難點(diǎn)線性表的基本操作在鏈接存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。第八頁(yè)，共三十九頁(yè)，編輯于2023年，星期三實(shí)驗(yàn)預(yù)習(xí)檢查內(nèi)容完成下列程序，指出main的結(jié)構(gòu)#include<stdio.h>#defineMaxLen50typedefintelemtype；structdatatype{elemtype*elem;intlength;}typedefstructdatatypesqlist；第九頁(yè)，共三十九頁(yè)，編輯于2023年，星期三voidcreate(sqlist*a){inti,n；a->elem=(elemtype*)malloc(MaxLen*sizeof(elemtype));printf（“創(chuàng)建一個(gè)順序表\n”）；printf（“輸入元素個(gè)數(shù)：”）；scanf（“%d",&a->length)；for(i=0；i<a->length；i++){printf（“輸入第%d個(gè)元素值：”,i）；scanf（“%d",a->elem+i)；}}第十頁(yè)，共三十九頁(yè)，編輯于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)第十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期三Voiddisp(sqlist*a){intI;for(i=0;i<n;i++)printf(“%5d:%d\n”,i+1,*(a->elem+i));}第十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期三voidmain(){sqlistb,*a；a=&b;;create(a)；disp(a)；invert(a)；disp(a)；}第十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期三實(shí)驗(yàn)內(nèi)容及要求4、7、13必做，其余老師選做幾題4、鍵盤(pán)輸入學(xué)生信息（包括學(xué)號(hào)和成績(jī)），學(xué)號(hào)為0作為結(jié)束標(biāo)志，建立其對(duì)應(yīng)的線性表并輸出各結(jié)點(diǎn)中的數(shù)據(jù)。注：試以順序表和單鏈表兩種不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。第十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期三7、設(shè)計(jì)一個(gè)算法求A和B兩個(gè)單鏈表表示的集合的并集。提示：將A和B合并。9、用頭插法把單鏈表b中在單鏈表a中未出現(xiàn)的結(jié)點(diǎn)合并到單鏈表a中。第十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期三實(shí)驗(yàn)三棧和隊(duì)列教學(xué)目的與要求了解棧和隊(duì)列的特性，以便靈活應(yīng)用。熟練掌握棧和有關(guān)隊(duì)列的各種操作和應(yīng)用。

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

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

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

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

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

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

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