唐束科技學(xué)院GUANGDONG UNIVERSITY OF SCIENCE & TECHNOLOGY項(xiàng)目（課內(nèi)實(shí)訓(xùn)）指導(dǎo)書系別：計(jì)算機(jī)系專業(yè)：網(wǎng)絡(luò)工程課程：數(shù)據(jù)結(jié)構(gòu)制訂人：理艷榮審核人：制訂時間：2019年3月第一部分 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的目的、要求一、實(shí)驗(yàn)?zāi)康纳蠙C(jī)實(shí)踐是各位對本門課程所學(xué)知識的一種全面、綜合的能力訓(xùn)練，是與課 堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)環(huán)節(jié)，也是對課堂教學(xué)與實(shí) 踐教學(xué)效果的一種檢驗(yàn)。通常，實(shí)驗(yàn)題中的問題比平時的習(xí)題復(fù)雜得多， 也更接 近實(shí)際。實(shí)驗(yàn)著眼于原理與應(yīng)用的結(jié)合，使你們學(xué)會如何把書上學(xué)到的知識運(yùn)用 于解決實(shí)際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計(jì)工作所必需的基本技能；另一方面，能使書上的知識變 活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平 時的練習(xí)較偏重于如何編寫功能單一的 小”算法，而實(shí)驗(yàn)題是軟件設(shè)計(jì)的綜合訓(xùn) 練，包括問題分析（需求分析）、總體結(jié)構(gòu)設(shè)計(jì)和用戶界面設(shè)計(jì)（概要設(shè)計(jì)）、程 序設(shè)計(jì)基本技能和技巧等，即一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此 外，還有很重要的一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)厲的主考者。為了達(dá)到上述目的，第二部分安排了實(shí)驗(yàn)單元內(nèi)容，各單元的訓(xùn)練重點(diǎn)在于 基本的數(shù)據(jù)結(jié)構(gòu)，而不強(qiáng)調(diào)面面俱到。各實(shí)驗(yàn)單元與教科書的各章具有緊密的對 應(yīng)關(guān)系。二、要求：1做好每一次上機(jī)前的準(zhǔn)備以提高上機(jī)效率： 預(yù)先認(rèn)真閱讀相關(guān)實(shí)驗(yàn)內(nèi)容，做到心中有明確的目的要求和任務(wù)，要有備而來，應(yīng)該自己獨(dú)立的思考和設(shè)計(jì)你的算法和程序， 并爭取在規(guī)定的時間內(nèi)如 期完成上機(jī)工作任務(wù)。對于個別目前基礎(chǔ)較差的同學(xué)，實(shí)在是沒法完成任務(wù)的建 議你先參考其他同學(xué)的算法，勤學(xué)好問， 最終自己獨(dú)立完成，以增強(qiáng)你的感性認(rèn) 識，強(qiáng)化你的實(shí)踐基礎(chǔ)，提高你的實(shí)踐能力。 按照實(shí)驗(yàn)內(nèi)容規(guī)定的習(xí)題題目，事先在實(shí)驗(yàn)預(yù)習(xí)報告上編寫好源程序及 運(yùn)行程序所需的典型數(shù)據(jù)，并經(jīng)人工靜態(tài)檢查認(rèn)為無誤；手編程序應(yīng)書寫整齊，應(yīng)在每個題目之間留出一定的空間， 以備記錄上機(jī)調(diào)試情況和運(yùn)行結(jié)果等； 對程 序中自己有疑問的地方，應(yīng)作出記號，以便上機(jī)時給以注意。 將想要上機(jī)驗(yàn)證的問題草擬提綱；制定一個簡捷的程序調(diào)試計(jì)劃。2. 上機(jī)時輸入和調(diào)式自己所編寫的程序。對出錯信息”應(yīng)善于自己分析 判斷，并充分利用開發(fā)工具提供的錯誤信息和調(diào)試手段解決出現(xiàn)的問題， 及時修 改與完善算法、源程序， 隨時記錄有價值的內(nèi)容。 解決問題是學(xué)習(xí)調(diào)式程序的良 好機(jī)會。切不可不編程序或抄別人的程序去上機(jī)，應(yīng)從養(yǎng)成嚴(yán)謹(jǐn)?shù)目茖W(xué)作風(fēng)。3. 程序調(diào)試通過后，應(yīng)運(yùn)行程序并根據(jù)事先準(zhǔn)備的典型數(shù)據(jù)驗(yàn)證結(jié)果，在 運(yùn)行時要注意在輸入不同數(shù)據(jù)時所得到的不同結(jié)果。4. 為便于教師、助教檢查和以后復(fù)習(xí)，請不要刪除已通過的程序，包括有 問題待答疑的程序， 應(yīng)保存在自己的工作目錄內(nèi)。 源程序名應(yīng)能反映哪一次實(shí)驗(yàn) 的哪一個題目，女口 Lab1_1.c表示實(shí)驗(yàn)一的第1題，若有未完成調(diào)試的源 程序，可以作存盤保存處理，待課后繼續(xù)完成。5、幾乎每個實(shí)驗(yàn)都有超出數(shù)據(jù)結(jié)構(gòu)課程標(biāo)準(zhǔn)的內(nèi)容，是為有能力深入 學(xué)習(xí)或考研的同學(xué)準(zhǔn)備的，教師與學(xué)生可根據(jù)實(shí)際情況做取舍。三、考核或評價標(biāo)準(zhǔn)實(shí)訓(xùn)成績將主要根據(jù)學(xué)生對待實(shí)訓(xùn)的態(tài)度、 對關(guān)鍵知識點(diǎn)和編程技巧的掌握 程度、實(shí)訓(xùn)報告的內(nèi)容、 答辯情況等進(jìn)行綜合評定。 最后的成績將分優(yōu)秀、 良好、 中等、及格和不及格五個等級。具體評判標(biāo)準(zhǔn)如下：優(yōu)秀：實(shí)訓(xùn)認(rèn)真、刻苦，有鉆研精神，不無故缺席。熟練掌握了本實(shí)訓(xùn)的關(guān) 鍵知識點(diǎn)，具有良好的獨(dú)立思考問題和解決問題的能力，具備了較好的運(yùn)用 C 語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編制的程序運(yùn)行正確。實(shí)訓(xùn)記錄內(nèi)容豐富、 齊 全，答辯時能清晰明了地闡明問題，回答問題反映敏捷、思路清晰。優(yōu)秀的分?jǐn)?shù) 段為 100分90 分。良好：能認(rèn)真對待實(shí)訓(xùn)，不無故缺席。掌握了本實(shí)訓(xùn)的關(guān)鍵知識點(diǎn)，具備了較好的運(yùn)用 C 語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編寫的程序運(yùn)行正確。實(shí)訓(xùn)記 錄內(nèi)容齊全，答辯時能清晰明了地闡明問題，能正確回答全部問題。良好的分?jǐn)?shù) 段為89分一一80分。中等：能認(rèn)真對待實(shí)訓(xùn)，不無故缺席?；菊莆樟吮緦?shí)訓(xùn)的關(guān)鍵知識點(diǎn)，具 備了一定的運(yùn)用C語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編寫的程序運(yùn)行基本正確， 無致命錯誤。實(shí)訓(xùn)記錄內(nèi)容較齊全， 答辯時能正確回答大部分問題。中等的分?jǐn)?shù) 段為79分一一70分。及格：對待實(shí)訓(xùn)不夠認(rèn)真，有少量遲到、早退或無故缺席現(xiàn)象?；菊莆樟?本實(shí)訓(xùn)的主要內(nèi)容，具有了用運(yùn)用 C語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，但掌握 不全面、扎實(shí)，編寫的程序總體結(jié)構(gòu)符合要求，基本能正常運(yùn)行，但還存在少量 錯誤。實(shí)訓(xùn)記錄內(nèi)容基本齊全，答辯時能在教師提示下正確回答大部分問題。及 格分?jǐn)?shù)段為69分 60分。不及格：對待實(shí)訓(xùn)馬虎、敷衍，經(jīng)常遲到、早退或無故缺席。不能正確理解 本實(shí)訓(xùn)的主要內(nèi)容，不具備基本的運(yùn)用 C語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編 制的程序不能正常運(yùn)行，或是抄襲他人程序， 應(yīng)付答辯。答辯時即使經(jīng)教師提示 仍不能正確回答大部分問題。不及格分?jǐn)?shù)段小于 60分。第二部分 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)內(nèi)容預(yù)備實(shí)驗(yàn)C語言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識、實(shí)驗(yàn)?zāi)康?、復(fù)習(xí)c語言中函數(shù)、數(shù)組、指針、結(jié)構(gòu)體與共用體等的概念。2、熟悉利用C語言進(jìn)行程序設(shè)計(jì)的一般方法。3、為其它實(shí)驗(yàn)提供答題參考。環(huán)境中運(yùn)行即可。4、同學(xué)們可以把本小節(jié)程序直接復(fù)制到Microsoft Visual C+ 6.0二、實(shí)驗(yàn)預(yù)習(xí)說明以下C語言中的概念1、函數(shù)：略2、數(shù)組：略3、指針：略4、結(jié)構(gòu)體略5、共用體略、實(shí)驗(yàn)內(nèi)容和要求(一)、調(diào)試程序：輸出100以內(nèi)所有的素數(shù)(用函數(shù)實(shí)現(xiàn))#in clude<stdio.h>int isprime(i nt n)/*判斷一個數(shù)是否為素數(shù)*/int m;for(m=2;m*m<=n; m+)if(n%m=0) return 0;return 1;int i; prin tf("n");for(i=2;i<100;i+)if(isprime(i)=1) pri ntf("%4d",i); prin tf("n");return 0;運(yùn)行結(jié)果：（二）、調(diào)試程序：對一維數(shù)組中的元素進(jìn)行逆序排列。#in clude<stdio.h>#defi ne N 10 int mai n()int aN=0,1,2,3,4,5,6,7,8,9,i,temp;printf("nthe original Array is:n ");for(i=0;i<N;i+)prin tf("%4d",ai);for(i=0;i<N/2;i+)/*交換數(shù)組元素使之逆序*/temp=ai;ai=aN-i-1;aN-i-1=temp;prin tf("nthe cha nged Array is:n"); for(i=0;i<N;i+)prin tf("%4d",ai);prin tf("n");return 0;運(yùn)行結(jié)果：72 DhTEMPaaaDebugaaiaseKeH口 回 YwJthe original firray is:the changed Array is:9876543210Press mny Jcey to continuem( 三 )、 調(diào)試程序：在二維數(shù)組中，若某一位置上的元素在該行中最大，而在該列中最小， 則該元素即為該二維數(shù)組的一個鞍點(diǎn)。 要求從鍵盤上輸入一個二維數(shù)組， 當(dāng)鞍點(diǎn)存在時， 鞍點(diǎn)找出來。#include<stdio.h>#define M 3#define N 4int main()int aMN,i,j,k;printf("n 請輸入二維數(shù)組的數(shù)據(jù)： n"); for(i=0;i<M;i+)for(j=0;j<N;j+) scanf("%d",&aij);for(i=0;i<M;i+)/* 輸出矩陣 */for(j=0;j<N;j+)printf("%4d",aij);printf("n"); for(i=0;i<M;i+) k=0; for(j=1;j<N;j+)/*找出第 i 行的最大值 */if(aij>aik) k=j;for(j=0;j<M;j+)/*判斷第 i 行的最大值是否為該列的最小值 */if(ajk<aik)break;if(j=M)/*在第 i 行找到鞍點(diǎn) */printf("%d,%d,%dn",aik,i,k);printf("n"); return 0; 運(yùn)行結(jié)果：(四)、調(diào)試程序：利用指針輸出二維數(shù)組的元素。#in clude<stdio.h>int mai n()int a34=1,3,5,7,9,11,13,15,17,19,21,23;int *p;for(p=a0;p<a0+12;p+)if(p-a0)%4=0) pri ntf("n");prin tf("%4d",*p);prin tf("n");return 0;運(yùn)行結(jié)果：r* D:TEM PaDebu gaaa. exe". 4旦13579111315I 17192123Press any key to continue（五卜調(diào)試程序：設(shè)有一個教師與學(xué)生通用的表格，教師的數(shù)據(jù)有姓名、年齡、職業(yè)、教研室四項(xiàng)，學(xué)生有姓名、年齡、專業(yè)、班級四項(xiàng)，編程輸入人員的數(shù)據(jù)，再以表格輸出。#in clude <stdio.h>#defi ne N 10struct stude ntchar name8; /* 姓名 */int age;/*年齡 */char job; /*職業(yè)或?qū)I(yè)，用 s或t表示學(xué)生或教師*/union int class; /* 班級 */char office10; /*教研室 */depa;stuN;int mai n()int i; int n;printf("n請輸入人員數(shù)(<10人):");scan f("%d",&n);for(i=0;i<n;i+)/*輸入n個人員的信息*/printf("請輸入第 %d 人員的信息：(name age job class/office)n",i+1);scanf("%s %d %c",stui.name, &stui.age, &stui.job);if(stui.job='s')scan f("%d"，& stui.depa.class);elsescan f("%s",stui.depa.office);printf("n ameage job class/officen");for(i=0;i<n;i+)/*輸出 */if(stui.job='s')printf("%s %3d %3c %dn",stui.name, stui.age, stui.job, stui.depa.class); elseprintf("%s %3d %3c %sn",stui.name, stui.age, stui.job, stui.depa.office); 輸入的數(shù)據(jù)：Wan g,19,s,99061Li 36 t computer運(yùn)行結(jié)果:(六)、設(shè)某班級有M( 6)名學(xué)生，本學(xué)期共開設(shè) N (3)門課程，要求實(shí)現(xiàn)如下 程序(算法)。1輸入學(xué)生的學(xué)號、姓名和N門課程的成績(輸入提示和輸出顯示使用漢字 系統(tǒng))，輸出實(shí)驗(yàn)結(jié)果。2. 計(jì)算每個學(xué)生本學(xué)期N門課程的總分，輸出總分和N門課程成績排在前3 名學(xué)生的學(xué)號、姓名和成績。3. 按學(xué)生總分和N門課程成績關(guān)鍵字升序用選擇排序排列名次,總分相同者 同名次。/Seletsort.c#include "stdio.h"#include "string.h"#defi ne M 6#defi ne N 3void cha ngesort(struct stude nt a,i nt n ,i nt j);void prin t_score(struct stude nt a,i nt n ,i nt j);struct stude ntchar n ame10;int nu mber;int scoreN+1;/*scoreN 為 總分,score0-score2為學(xué)科成績 */stuM;mai n()int i,j,k;for (i=0;i<M;i+)/*輸入每個學(xué)生信息*/printf("請輸入第 %d 名學(xué)生分?jǐn)?shù)：",i+1);printf("n");printf("姓名:");scan f("%s",stui. name);printf("編號:");scan f("%4d",&stui. number);printf(" 數(shù)據(jù)結(jié)構(gòu) : "); scanf("%4d",&stui.score0);printf(" 離散數(shù)學(xué) : "); scanf("%4d",&stui.score1); printf(" 大學(xué)英語 : "); scanf("%4d",&stui.score2);for(i=0;i<M;i+)stui.scoreN=0;for(j=0;j<N;j+)stui.scoreN+=stui.scorej;changesort(stu,M,N);printf("/* 計(jì)算每個學(xué)生總分 */* 對總分進(jìn)行排序 */學(xué)生總分成績排序表 n");數(shù)據(jù)結(jié)構(gòu) 離散數(shù)學(xué) 大學(xué)英語 總printf(" 名次 學(xué)號 姓 名分 n");k=0;for(i=0;i<M+1;i+)if(i>0&&stui.scoreN!=stui-1.scoreN)k+;printf("%4d",k);printf(" %4d",stui-1.number);printf(" %s",stui-1.name);for(j=0;j<N+1;j+)printf(" %6d",stui-1.scorej);printf("n");changesort(stu,M,0); /* 對數(shù)據(jù)結(jié)構(gòu)成績進(jìn)行排序 */ print_score(stu,M,0); /*輸出數(shù)據(jù)結(jié)構(gòu)前 3 名同學(xué)成績 */ changesort(stu,M,1); /* 對離散數(shù)學(xué)成績進(jìn)行排序 */ print_score(stu,M,1); /*輸出離散數(shù)學(xué)前 3 名同學(xué)成績 */ changesort(stu,M,2); /* 對大學(xué)英語成績進(jìn)行排序 */ print_score(stu,M,2); /*輸出大學(xué)英語前 3 名同學(xué)成績 */ void cha ngesort(struct stude nt a,i nt n ,i nt j)int flag=1,i,m,k;struct stude nt temp;while(flag)Lflag=O;for(i=0;i<n-1;i+)/* 選擇排序法 */ k=i;for(m=i+1;m<n ;m+)if (am.scorej>ak.scorej) k=m;temp=ai; ai=ak; ak=temp; void prin t_score(struct stude nt a,i nt n ,i nt j) _int i,k;printf("選擇交換成績 %d排序表",j+1); prin tf("n");printf("名次學(xué)號 姓名分?jǐn)?shù)n"); k=1;for(i=0;k< N&&i< n;i+)if(i>0&&ai.scorej!=ai-1.scorej) k+;prin tf(" %4d",k);prin tf("%4d",ai. number);printf(" %s",ai. name);printf(" %6d",ai.scorej);prin tf("n");簡單選擇排序：請輸入第1 名學(xué)生分?jǐn)?shù)姓名史孟晨編號01數(shù)據(jù)結(jié)構(gòu)87離散數(shù)學(xué)90大學(xué)英語78請輸入第2 名學(xué)生分?jǐn)?shù)姓名袁欣編號02數(shù)據(jù)結(jié)構(gòu)78離散數(shù)學(xué)80大學(xué)英語92請輸入第3 名學(xué)生分?jǐn)?shù)姓名趙宇編號03數(shù)據(jù)結(jié)構(gòu)88離散數(shù)學(xué)76大學(xué)英語95請輸入第4 名學(xué)生分?jǐn)?shù)姓名滕芷編號04數(shù)據(jù)結(jié)構(gòu)79離散數(shù)學(xué)84大學(xué)英語88請輸入第5 名學(xué)生分?jǐn)?shù)姓名張一析編號05數(shù)據(jù)結(jié)構(gòu)78離散數(shù)學(xué)68大學(xué)英語91請輸入第6 名學(xué)生分?jǐn)?shù)姓名白曉彤編號06數(shù)據(jù)結(jié)構(gòu)88離散數(shù)學(xué)76大學(xué)英語90學(xué)生總分成績排序表名次 學(xué)號 姓 名 數(shù)據(jù)結(jié)構(gòu) 離散數(shù)學(xué) 大學(xué)英語 總 分13 趙宇88769525921 史孟晨87907825536 白曉彤88769025444 滕芷79848825152 袁欣78809225065 張一析786891237選擇交換 成績 1 排序表名次學(xué)號姓名分?jǐn)?shù)13趙宇8816白曉彤8821史孟晨8734滕芷79選擇交換成績2 排序表名次學(xué)號姓名分?jǐn)?shù)11史孟晨9024滕芷8432袁欣80選擇交換成績3 排序表名次學(xué)號姓名分?jǐn)?shù)13趙宇9522袁欣9235張一析91Press any key to continue 輸入的數(shù)據(jù)及運(yùn)行結(jié)果截屏：<Sb語 英 學(xué) 表大 D:TEMPaaaDebugaaa.exe"17 0 80 8 9 7(欣袁02788012 3塞-務(wù)嘗塞口備嘉塞口養(yǎng)毒塞oi毒畧口暮嘗塞務(wù)嘗 結(jié)數(shù)英入 結(jié)數(shù)英 IMS入 結(jié)數(shù)英入 結(jié)數(shù)英入號編B罔大恵編數(shù)罔大號編醫(yī)大團(tuán)編B崗大屢編醫(yī)大履編B曷大 數(shù)分生睜止 -6 5啟衆(zhòng) 4 9 4 8U長 5 8 8 1 6 8 6 07 9 4 0 7 8 8 n5 0 7 6 9 0 8 7 9 數(shù) 分名E總構(gòu) 生結(jié) 學(xué)據(jù)數(shù)J名次學(xué)號姓名瘧隸囑脾類學(xué)英語總分 " Q:TE IM Pa ajDebuqaaarexe"口86 07 9表12 3 4 5 6952085 4 75 5 32 2 10 25 52 20 6976 4 07 8 88 0 17 9 95 8 29 8 97 8 88 8 78 9 88 7 74 分8的878 9分8 7表 序名搟辰序看辰數(shù)915 2分9 9 表H- 3 2 5%交次3 筆 12 31丿彳扌/ Ji 丿彳 析M 琴 張養(yǎng)孟芷排孟芷廉丟“ 豐勲娜止欣T 1姓趙量滕2 H3姓爹張O 趙史SB譬書號'a號成 3 £ 1 4 成 14-25% %交次 交次112 3? 1 2迤名四、心得體會本學(xué)期開設(shè)的數(shù)據(jù)結(jié)構(gòu)課程已經(jīng)告一段落，現(xiàn)就學(xué)習(xí)體會進(jìn)行學(xué)習(xí)總 結(jié)。這是一門純屬于設(shè)計(jì)的科目，它需用把理論變?yōu)樯蠙C(jī)調(diào)試。剛開始學(xué)的時 候確實(shí)有很多地方很不理解，每次上課時老師都會給我們出不同的設(shè)計(jì)題目， 對 于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。老師會給我們需要編程的內(nèi)容一些講解， 順著老師的思路， 來完成自己的設(shè)計(jì)，我們可以開始運(yùn)行自己的程序。這門課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問題，最為突出的，書本上 的知識與老師的講解都比較容易理解，但是當(dāng)自己采用剛學(xué)的知識點(diǎn)編寫程序時 卻感到十分棘手，有時表現(xiàn)在想不到適合題意的算法，有時表現(xiàn)在算法想出來后， 只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫剛開始學(xué)的時候確實(shí)有很多地方我很不理解，每次上上機(jī)課時老師都會給 我們出不同的設(shè)計(jì)題目，對于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)， 撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。老師會給我們需要編程的 內(nèi)容一些講解，順著老師的思路，來完成自己的設(shè)計(jì)，我們可以開始運(yùn)行自己 的程序，可是好多處的錯誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯誤， 但是程序還是得繼續(xù)下去，我多次請教了老師和同學(xué)，逐漸能自己找出錯誤， 并加以改正。 TC 里檢查錯誤都是用英文來顯示出來的，經(jīng)過了這次課程設(shè)計(jì)， 現(xiàn)在已經(jīng)可以了解很多錯誤在英文里的提示，這對我來說是一個突破性的進(jìn) 步，眼看著一個個錯誤通過自己的努力在我眼前消失，覺得很是開心。此次的 程序設(shè)計(jì)能夠成功，是我和我的同學(xué)三個人共同努力作用的結(jié)果。在這一段努 力學(xué)習(xí)的過程中，我們的編程設(shè)計(jì)有了明顯的提高。其實(shí)現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它 上面花費(fèi)了好多心血，覺得它很難， 是需用花費(fèi)了大量的時間編寫出來的。 現(xiàn)在 真正的明白了一些代碼的應(yīng)用， 每個程序都有一些共同點(diǎn)，通用的結(jié)構(gòu)，相似的 格式。只要努力去學(xué)習(xí)，就會靈活的去應(yīng)用它。以上便是我對數(shù)據(jù)結(jié)構(gòu)這門課的學(xué)習(xí)總結(jié)，我會抓緊時間將沒有吃透 的知識點(diǎn)補(bǔ)齊 , 克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁 進(jìn)！實(shí)驗(yàn)一順序表與鏈表、實(shí)驗(yàn)?zāi)康?、掌握線性表中元素的前驅(qū)、后續(xù)的概念。2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。3、對線性表相應(yīng)算法的時間復(fù)雜度進(jìn)行分析。4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)（優(yōu)缺點(diǎn)） 。二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念（到主要參考教材上查找答案）1、線性表：2、順序表：3、鏈表：、實(shí)驗(yàn)內(nèi)容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#in clude<stdio.h>#in clude<malloc.h>#defi ne ERROR 0#defi ne OK 1#defi ne INIT_SIZE 5/*#defi ne INCREM 5/*typedef int ElemType; /* typedef struct SqlistElemType *slist; /* int len gth;/*int listsize; /*Sqlist;初始分配的順序表長度*/ 溢出時，順序表長度的增量*/定義表元素的類型*/存儲空間的基地址*/順序表的當(dāng)前長度*/當(dāng)前分配的存儲空間*/int InitList_sq(Sqlist *L); /*/int CreateList_sq(Sqlist *L,int n); /*/int ListInsert_sq(Sqlist *L,int i,ElemType e);/*/ int Prin tList_sq(Sqlist *L); /*輸出順序表的元素*/int ListDelete_sq(Sqlist *L,int i); /* int ListLocate(Sqlist *L,ElemType e); /*刪除第i個元素*/查找值為e的元素*/int In itList_sq(Sqlist *L)L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(!L->slist) return ERROR;L->length=0;L->listsize=INIT_SIZE;return OK;/*InitList*/int CreateList_sq(Sqlist *L,int n)ElemType e;int i;for(i=0;i<n;i+) printf("input data %d",i+1); scanf("%d",&e); if(!ListInsert_sq(L,i+1,e) return ERROR;return OK;/*CreateList*/* 輸出順序表中的元素 */int PrintList_sq(Sqlist *L)int i;for(i=1;i<=L->length;i+) printf("%5d",L->slisti-1);return OK;/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e)int k; if(i<1|i>L->length+1) return ERROR;if(L->length>=L->listsize)L->slist=(ElemType*)realloc(L->slist, (INIT_SIZE+INCREM)*sizeof(ElemType); if(!L->slist)return ERROR; L->listsize+=INCREM;for(k=L->length-1;k>=i-1;k-) L->slistk+1= L->slistk;L->slisti-1=e;L->length+;return OK;/*ListInsert*/ /* 在順序表中刪除第 i 個元素 */int ListDelete_sq(Sqlist *L,int i)/* 在順序表中查找指定值元素，返回其序號 */int ListLocate(Sqlist *L,ElemType e)int main()Sqlist sl;int n,m,k;printf("please input n:"); /* 輸入順序表的元素個數(shù) */ scanf("%d",&n);if(n>0)printf("n1-Create Sqlist:n");InitList_sq(&sl);CreateList_sq(&sl,n);printf("n2-Print Sqlist:n");PrintList_sq(&sl);printf("nplease input insert location and data:(location,data)n"); scanf("%d,%d",&m,&k);ListInsert_sq(&sl,m,k); printf("n3-Print Sqlist:n");PrintList_sq(&sl); printf("n");elseprintf("ERROR");return 0; 運(yùn)行結(jié)果(運(yùn)行結(jié)果截屏粘貼到這里)算法分析(參照教材上的“算法分析”部分填寫本部分內(nèi)容，2、為第 1 題補(bǔ)充刪除和查找功能函數(shù)，并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。 刪除算法代碼：運(yùn)行結(jié)果算法分析查找算法代碼：運(yùn)行結(jié)果算法分析3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#in clude<stdio.h>#in clude<malloc.h>#defi ne ERROR 0#defi ne OK 1定義表元素的類型*/ 線性表的單鏈表存儲*/typedef int ElemType; /* typedef struct LNode /*ElemType data; struct LNode *n ext;LNode,*Li nkList;LinkList CreateList(int n); /* void PrintList(LinkList L); /* int GetElem(LinkList L,int i,ElemType *e); /*/輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/*/LinkList CreateList(int n)LNode *p,*q,*head;int i;head=(L in kList)malloc(sizeof(LNode); p=head;for(i=0;i< n; i+)q=(L in kList)malloc(sizeof(LNode); data %i:",i+1);scan f("%d"，& q->data);/*q-> next=NULL;/*p_>n ext=q;/*p=q;retur n head;/*CreateList*/head-> next=NULL;prin tf("i nput輸入元素值*/結(jié)點(diǎn)指針域置空*/新結(jié)點(diǎn)連在表末尾*/void Prin tList(L in kList L)LNode *p;p=L->next; /*p指向單鏈表的第1個元素*/while(p!=NULL)prin tf("%5d",p->data);p=p->n ext;/*Pri ntList*/int GetElem(LinkList L,int i,ElemType *e) LNode *p;int j=1;p=L->n ext;while(p&&j<i)p=p->next;j+;if(!p|j>i)return ERROR;*e=p->data;return OK;/*GetElem*/int main()int n,i;ElemType e;LinkList L=NULL; /* 定義指向單鏈表的指針 */ printf("please input n:"); /* 輸入單鏈表的元素個數(shù) */ scanf("%d",&n);if(n>0)printf("n1-Create LinkList:n");L=CreateList(n);printf("n2-Print LinkList:n");PrintList(L);printf("n3-GetElem from LinkList:n");printf("input i=");scanf("%d",&i);if(GetElem(L,i,&e)printf("No%i is %d",i,e);elseprintf("not exists");elseprintf("ERROR");return 0;運(yùn)行結(jié)果算法分析4、為第 3 題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。 并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。 插入算法代碼：運(yùn)行結(jié)果算法分析刪除算法代碼:運(yùn)行結(jié)果算法分析以下為選做實(shí)驗(yàn)：5、循環(huán)鏈表的應(yīng)用（約瑟夫回環(huán)問題）n 個數(shù)據(jù)元素構(gòu)成一個環(huán)，從環(huán)中任意位置開始計(jì)數(shù)，計(jì)到m 將該元素從表中取出，重復(fù)上述過程，直至表中只剩下一個元素。提示：用一個無頭結(jié)點(diǎn)的循環(huán)單鏈表來實(shí)現(xiàn) n 個元素的存儲。算法代碼6、設(shè)一帶頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)算法將表中值相同的元素僅保留一個結(jié)點(diǎn)。提示：指針p從鏈表的第一個元素開始，利用指針q從指針p位置開始向后搜索整個鏈表，刪除與之值相同的元素；指針p繼續(xù)指向下一個元素，開始下一輪的刪除，直至p= null為至，既完成了對整個鏈表元素的刪除相同值。算法代碼四、實(shí)驗(yàn)小結(jié)實(shí)驗(yàn)二棧和隊(duì)列一、實(shí)驗(yàn)?zāi)康?、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；2、掌握隊(duì)列的結(jié)構(gòu)特性及其入隊(duì)、出隊(duì)的操作，掌握循環(huán)隊(duì)列的特點(diǎn)及其操作。二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、順序棧：2、鏈棧：3、循環(huán)隊(duì)列：4、鏈隊(duì)、實(shí)驗(yàn)內(nèi)容和要求，運(yùn)1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補(bǔ)充完整。要求輸入元素序列行結(jié)果如下所示。#in clude<stdio.h>#in clude<malloc.h>#defi ne ERROR 0#defi ne OK 1#defi ne STACK_INT_SIZE 10 /*#defi ne STACKINCREMENT 5 /* typedef int ElemType; /* typedef structElemType *base;ElemType *top;存儲空間初始分配量*/ 存儲空間分配增量*/定義元素的類型*/int stacksize; /* SqStack;當(dāng)前已分配的存儲空間 */int InitStack(SqStack *S); /*int push(SqStack *S,ElemType e); /* int Pop(SqStack *S,ElemType *e); /* int CreateStack(SqStack *S); /* void PrintStack(SqStack *S); /*構(gòu)造空棧 */入棧 */出棧 */創(chuàng)建棧 */出棧并輸出棧中元素 */int InitStack(SqStack *S)S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType); if(!S->base) return ERROR;S->top=S->base; S->stacksize=STACK_INT_SIZE;return OK; /*InitStack*/int Push(SqStack *S,ElemType e)/*Push*/int Pop(SqStack *S,ElemType *e)/*Pop*/int CreateStack(SqStack *S)int e;if(InitStack(S) printf("Init Success!n");else printf("Init Fail!n"); return ERROR;printf("input data:(Terminated by inputing a character)n"); while(scanf("%d",&e)Push(S,e);return OK; /*CreateStack*/void PrintStack(SqStack *S)ElemType e;while(Pop(S,&e) printf("%3d",e);/*Pop_and_Print*/int mai n()SqStack ss;prin tf("n1-createStackn");CreateStack(&ss);prin tf("n 2-Pop&Printn");Prin tStack(&ss);return 0;算法分析：輸入元素序列 1 2 3 4 5，為什么輸出序列為5 4 3 2 1 ?體現(xiàn)了棧的什么特性？2、在第1題的程序中，編寫一個十進(jìn)制轉(zhuǎn)換為二進(jìn)制的數(shù)制轉(zhuǎn)換算法函數(shù)（要求利用棧來 實(shí)現(xiàn)），并驗(yàn)證其正確性。實(shí)現(xiàn)代碼驗(yàn)證3、閱讀并運(yùn)行程序，并分析程序功能。#in clude<stdio.h>#in clude<malloc.h>#in clude<stri ng.h>#defi ne M 20#defi ne elemtype char typedef structelemtype stackM;int top;stack no de;void in it(stack node *st);void push(stack node *st,elemtype x); void pop(stack node *st);void in it(stack node *st)st->top=0;void push(stack node *st,elemtype x)if(st->top=M)prin tf("the stack is overflow!' n");elsest_>top=st_>top+1; st->stackst->top=x;void pop(stack node *st)if(st->top>0) st->top-;else printf(Stack is Empty!' n”;int mai n()char sM;int i;stack node *sp;prin tf("create a empty stack!' n"); sp=malloc(sizeof(stack no de); ini t(sp);prin tf("i nput a expressi on:n ”)；gets(s);for(i=0;i<strle n(s);i+)if(si='(') push(sp,si);if(si=')')pop(sp);if(sp->top=0)prin tf("'('match')'!n");elseprintf("'('not match')'!n");return 0;輸入：2+(c-d)*6-(f-7)*a)/6運(yùn)行結(jié)果：輸入：a-(c-d)*6-(s/3-x)/2運(yùn)行結(jié)果：程序的基本功能：以下為選做實(shí)驗(yàn)：4、設(shè)計(jì)算法，將一個表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并按照后綴表達(dá)式進(jìn)行計(jì)算，得出表達(dá)式 得結(jié)果。實(shí)現(xiàn)代碼5、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列， 并且只設(shè)一個指針指向隊(duì)尾結(jié)點(diǎn) （不設(shè)隊(duì)頭指針） 試編寫相應(yīng)的置空隊(duì)列、入隊(duì)列、出隊(duì)列的算法。實(shí)現(xiàn)代碼：四、實(shí)驗(yàn)小結(jié)實(shí)驗(yàn)三 串的模式匹配一、實(shí)驗(yàn)?zāi)康? 、了解串的基本概念2 、掌握串的模式匹配算法的實(shí)現(xiàn)二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、模式匹配： 2、BF算法:三、實(shí)驗(yàn)內(nèi)容和要求1 、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果。#include<stdio.h>#include<string.h>#define MAXSIZE 100typedef structchar dataMAXSIZE;int length;SqString;串的比較 */int strCompare(SqString *s1,SqString *s2); /*void show_strCompare();void strSub(SqString *s,int start,int sublen,SqString *sub);/* 求子串 */void show_subString();int strCompare(SqString *s1,SqString *s2)int i;for(i=0;i<s1->length&&i<s2->length;i+) if(s1->datai!=s2->datai) return s1->datai-s2->datai;return s1->length-s2->length;void show_strCompare()SqString s1,s2;int k;printf("n*show Compare*n");printf("input string s1:"); gets(s1.data);s1.length=strlen(s1.data); printf("input string s2:"); gets(s2.data);s2.length=strlen(s2.data); if(k=strCompare(&s1,&s2)=0) printf("s1=s2n");else if(k<0)printf("s1<s2n");elseprintf("s1>s2n");printf("n*show over*n");void strSub(SqString *s,int start,int sublen,SqString *sub) int i;if(start<1|start>s->length|sublen>s->length-start+1) sub->length=0;for(i=0;i<sublen;i+) sub->datai=s->datastart+i-1;sub->length=sublen;void show_subString()SqString s,sub;int start,sublen,i; printf("n*show subString*n"); printf("input string s:");gets(s.data);s.length=strlen(s.data); printf("input start:"); scanf("%d",&start); printf("input sublen:"); scanf("%d",&sublen); strSub(&s,start,sublen,&sub); if(sub.length=0)printf("ERROR!n");elseprintf("subString is :"); for(i=0;i<sublen;i+) printf("%c",sub.datai);printf("n*show over*n");int main() int n; do printf("n-String-n"); printf("1. strComparen");printf("2. subStringn"); printf("0. EXITn"); printf("ninput choice:"); scanf("%d",&n); getchar(); switch(n)case 1:show_strCompare();break; case 2:show_subString();break; default:n=0;break; while(n); return 0;BF 算法。運(yùn)行程序 輸入： 1 student students 2 Computer Data Stuctures 10 4 運(yùn)行結(jié)果：2 、實(shí)現(xiàn)串的模式匹配算法。補(bǔ)充下面程序，實(shí)現(xiàn)串的#include<stdio.h>#include<string.h>#define MAXSIZE 100typedef structchar dataMAXSIZE;int length;SqString;int index_bf(SqString *s,SqString *t,int start); void getNext(SqString *t,int next);int index_kmp(SqString *s,SqString *t,int start,int next);void show_index();int index_bf(SqString *s,SqString *t,int start)補(bǔ)充代碼 void getNext(SqString *t,int next)int i=0,j=-1;next0=-1;while(i<t->length)if(j=-1)|(t->datai=t->dataj) i+;j+;nexti=j;elsej=nextj;void show_index()SqString s,t;int k,nextMAXSIZE=0,i;printf("n*show i