《項目課內(nèi)實訓(xùn)指導(dǎo)書》由會員分享，可在線閱讀，更多相關(guān)《項目課內(nèi)實訓(xùn)指導(dǎo)書（53頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、唐束科技學(xué)院 GUANGDONG UNIVERSITY OF SCIENCE & TECHNOLOGY 項目（課內(nèi)實訓(xùn)）指導(dǎo)書 系 別： 計算機系 專 業(yè)： 網(wǎng)絡(luò)工程 課 程： 數(shù)據(jù)結(jié)構(gòu) 制訂人： 理艷榮 審核人： 制訂時間： 2019年3月 第一部分 數(shù)據(jù)結(jié)構(gòu)實驗的目的、要求 一、 實驗?zāi)康? 上機實踐是各位對本門課程所學(xué)知識的一種全面、綜合的能力訓(xùn)練，是與課 堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)環(huán)節(jié)，也是對課堂教學(xué)與實 踐教學(xué)效果的一種檢驗。通常，實驗題中的問題比平時的習(xí)題復(fù)雜得多， 也更接 近實際。實驗著眼于原理與應(yīng)用的結(jié)合，使你們學(xué)會如何把書上

2、學(xué)到的知識運用 于解決實際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計工作所必需的基本技能； 另 一方面，能使書上的知識變 活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平 時的練習(xí)較偏重于如何編寫功能單一的 小”算法，而實驗題是軟件設(shè)計的綜合訓(xùn) 練，包括問題分析（需求分析）、總體結(jié)構(gòu)設(shè)計和用戶界面設(shè)計（概要設(shè)計）、程 序設(shè)計基本技能和技巧等，即一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此 外，還有很重要的一點是：機器是比任何教師都嚴厲的主考者。 為了達到上述目的，第二部分安排了實驗單元內(nèi)容，各單元的訓(xùn)練重點在于 基本的數(shù)據(jù)結(jié)構(gòu)，而不強調(diào)面面俱到。各實驗單元與教科書的各章具有緊密的對 應(yīng)關(guān)系。 二

3、、 要求： 1?做好每一次上機前的準備以提高上機效率： ① 預(yù)先認真閱讀相關(guān)實驗內(nèi)容，做到心中有明確的目的要求和任務(wù)，要有 備而來，應(yīng)該自己獨立的思考和設(shè)計你的算法和程序， 并爭取在規(guī)定的時間內(nèi)如 期完成上機工作任務(wù)。對于個別目前基礎(chǔ)較差的同學(xué)，實在是沒法完成任務(wù)的建 議你先參考其他同學(xué)的算法，勤學(xué)好問， 最終自己獨立完成，以增強你的感性認 識，強化你的實踐基礎(chǔ)，提高你的實踐能力。 ② 按照實驗內(nèi)容規(guī)定的習(xí)題題目，事先在實驗預(yù)習(xí)報告上編寫好源程序及 運行程序所需的典型數(shù)據(jù)，并經(jīng)人工靜態(tài)檢查認為無誤；手編程序應(yīng)書寫整齊， 應(yīng)在每個題目之間留出一定的空間， 以備記錄上機調(diào)試情況和運行結(jié)果

4、等； 對程 序中自己有疑問的地方，應(yīng)作出記號，以便上機時給以注意。 ③ 將想要上機驗證的問題草擬提綱；制定一個簡捷的程序調(diào)試計劃。 2. 上機時輸入和調(diào)式自己所編寫的程序。對 出錯信息”應(yīng)善于自己分析 判斷，并充分利用開發(fā)工具提供的錯誤信息和調(diào)試手段解決出現(xiàn)的問題， 及時修 改與完善算法、源程序， 隨時記錄有價值的內(nèi)容。 解決問題是學(xué)習(xí)調(diào)式程序的良 好機會。切不可不編程序或抄別人的程序去上機，應(yīng)從養(yǎng)成嚴謹?shù)目茖W(xué)作風(fēng)。 3. 程序調(diào)試通過后，應(yīng)運行程序并根據(jù)事先準備的典型數(shù)據(jù)驗證結(jié)果，在 運行時要注意在輸入不同數(shù)據(jù)時所得到的不同結(jié)果。 4. 為便于教師、助教檢查和以后復(fù)習(xí)，請不要刪除已

5、通過的程序，包括有 問題待答疑的程序， 應(yīng)保存在自己的工作目錄內(nèi)。 源程序名應(yīng)能反映哪一次實驗 的哪一個題目，女口 Lab1_1.c表示實驗一的第1題，……，若有未完成調(diào)試的源 程序，可以作存盤保存處理，待課后繼續(xù)完成。 5、幾乎每個實驗都有超出《數(shù)據(jù)結(jié)構(gòu)》課程標準的內(nèi)容，是為有能力深入 學(xué)習(xí)或考研的同學(xué)準備的，教師與學(xué)生可根據(jù)實際情況做取舍。 三、考核或評價標準 實訓(xùn)成績將主要根據(jù)學(xué)生對待實訓(xùn)的態(tài)度、 對關(guān)鍵知識點和編程技巧的掌握 程度、實訓(xùn)報告的內(nèi)容、 答辯情況等進行綜合評定。 最后的成績將分優(yōu)秀、 良好、 中等、及格和不及格五個等級。具體評判標準如下： 優(yōu)秀：實訓(xùn)認真、刻苦，有鉆

6、研精神，不無故缺席。熟練掌握了本實訓(xùn)的關(guān) 鍵知識點，具有良好的獨立思考問題和解決問題的能力，具備了較好的運用 C 語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編制的程序運行正確。實訓(xùn)記錄內(nèi)容豐富、 齊 全，答辯時能清晰明了地闡明問題，回答問題反映敏捷、思路清晰。優(yōu)秀的分數(shù) 段為 100分——90 分。 良好：能認真對待實訓(xùn)，不無故缺席。掌握了本實訓(xùn)的關(guān)鍵知識點，具備了 較好的運用 C 語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編寫的程序運行正確。實訓(xùn)記 錄內(nèi)容齊全，答辯時能清晰明了地闡明問題，能正確回答全部問題。良好的分數(shù) 段為89分一一80分。 中等：能認真對待實訓(xùn)，不無故缺席。基本掌握了本實訓(xùn)的關(guān)鍵知識點，具

7、 備了一定的運用C語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編寫的程序運行基本正確， 無致命錯誤。實訓(xùn)記錄內(nèi)容較齊全， 答辯時能正確回答大部分問題。中等的分數(shù) 段為79分一一70分。 及格：對待實訓(xùn)不夠認真，有少量遲到、早退或無故缺席現(xiàn)象?；菊莆樟?本實訓(xùn)的主要內(nèi)容，具有了用運用 C語言處理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，但掌握 不全面、扎實，編寫的程序總體結(jié)構(gòu)符合要求，基本能正常運行，但還存在少量 錯誤。實訓(xùn)記錄內(nèi)容基本齊全，答辯時能在教師提示下正確回答大部分問題。及 格分數(shù)段為69分 60分。 不及格：對待實訓(xùn)馬虎、敷衍，經(jīng)常遲到、早退或無故缺席。不能正確理解 本實訓(xùn)的主要內(nèi)容，不具備基本的運用 C語言處

8、理數(shù)據(jù)結(jié)構(gòu)相應(yīng)類型能力，編 制的程序不能正常運行，或是抄襲他人程序， 應(yīng)付答辯。答辯時即使經(jīng)教師提示 仍不能正確回答大部分問題。不及格分數(shù)段小于 60分。 第二部分 數(shù)據(jù)結(jié)構(gòu)實驗內(nèi)容 預(yù)備實驗 C語言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識 、實驗?zāi)康? 1、 復(fù)習(xí)c語言中函數(shù)、數(shù)組、指針、結(jié)構(gòu)體與共用體等的概念。 2、 熟悉利用C語言進行程序設(shè)計的一般方法。 3、 為其它實驗提供答題參考。 環(huán)境中運行即可。 4、同學(xué)們可以把本小節(jié)程序直接復(fù)制到 Microsoft Visual C++ 6.0 二、實驗預(yù)習(xí) 說明以下C語言

9、中的概念 1、 函數(shù)： 略 2、 數(shù)組： 略 3、 指針： 略 4、 結(jié)構(gòu)體 略 5、 共用體 略 、實驗內(nèi)容和要求 (一)、調(diào)試程序：輸出100以內(nèi)所有的素數(shù)(用函數(shù)實現(xiàn)) #in clude 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",

10、i); prin tf("\n"); return 0; } 運行結(jié)果： （二）、調(diào)試程序：對一維數(shù)組中的元素進行逆序排列。 #in clude #defi ne N 10 int mai n(){ int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp; printf("\nthe original Array is:\n "); for(i=0;i

11、1]; a[N-i-1]=temp; } prin tf("\nthe cha nged Array is:\n"); for(i=0;i

12、置上的元素在該行中最大，而在該列中最小， 則該元素即為該二維數(shù)組的一個鞍點。 要求從鍵盤上輸入一個二維數(shù)組， 當鞍點存在時， 鞍點找出來。 #include #define M 3 #define N 4 int main(){ int a[M][N],i,j,k; printf("\n 請輸入二維數(shù)組的數(shù)據(jù)： \n"); for(i=0;i

13、][j]); printf("\n"); } for(i=0;ia[i][k]) k=j; for(j=0;j

14、維數(shù)組的元素。 #in clude int mai n(){ int a[3][4]={1,3,5,7,9,11,13,15,17,19,21,23}; int *p; for(p=a[0];p

15、 Press any key to continue （五卜 調(diào)試程序：設(shè)有一個教師與學(xué)生通用的表格，教師的數(shù)據(jù)有姓名、年齡、職業(yè)、教 研室四項，學(xué)生有姓名、年齡、專業(yè)、班級四項，編程輸入人員的數(shù)據(jù)，再以表格輸出。 #in clude #defi ne N 10 struct stude nt{ char name[8]; /* 姓名 */ int age; /*年齡 */ char job; /*職業(yè)或?qū)I(yè)，用 s或t表示學(xué)生或教師*/ union { int class; /* 班級 */ char office[10]; /*教研室 */ }

16、depa; }stu[N]; int mai n(){ int i; int n; printf("\n請輸入人員數(shù)(<10人):"); scan f("%d",&n); for(i=0;i

17、lse scan f("%s",stu[i].depa.office); } printf("n ame age job class/office\n"); for(i=0;i

18、; } } 輸入的數(shù)據(jù)： Wan g,19,s,99061 Li 36 t computer 運行結(jié)果: (六)、設(shè)某班級有M( 6)名學(xué)生，本學(xué)期共開設(shè) N (3)門課程，要求實現(xiàn)如下 程序(算法)。 1?輸入學(xué)生的學(xué)號、姓名和N門課程的成績(輸入提示和輸出顯示使用漢字 系統(tǒng))，輸出實驗結(jié)果。 2. 計算每個學(xué)生本學(xué)期N門課程的總分，輸出總分和N門課程成績排在前3 名學(xué)生的學(xué)號、姓名和成績。 3. 按學(xué)生總分和N門課程成績關(guān)鍵字升序用選擇排序排列名次,總分相同者 同名次。 //Seletsort.c #include "stdio.h" #include "str

19、ing.h" #defi ne M 6 #defi ne N 3 void 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 nt { char n ame[10]; int nu mber; int score[N+1]; /*score[N] 為 總 分,score[0]-score[2]為學(xué)科成績 */ }stu[M]; mai n() { int i,j,k; for (i=

20、0;i

21、",&stu[i].score[2]); for(i=0;i0&&stu[i].score[

22、N]!=stu[i-1].score[N]) { k++; printf("%4d",k); printf(" %4d",stu[i-1].number); printf(" %s",stu[i-1].name); for(j=0;j

23、* 對離散數(shù)學(xué)成績進行排序 */ print_score(stu,M,1); /*輸出離散數(shù)學(xué)前 3 名同學(xué)成績 */ changesort(stu,M,2); /* 對大學(xué)英語成績進行排序 */ 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) L flag=O; for(i=0;i

24、 k=i; for(m=i+1;ma[k].score[j]) { k=m; temp=a[i]; a[i]=a[k]; a[k]=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é)號 姓名分數(shù)\n"); k=1; for(i=0;k< N&&i< n;i++) { if(i>0&&a[i].s

25、core[j]!=a[i-1].score[j]) k++; prin tf(" %4d ",k); prin tf("%4d",a[i]. number); printf(" %s",a[i]. name); printf(" %6d",a[i].score[j]); prin tf("\n"); 簡單選擇排序： 請輸入第 1 名學(xué)生分數(shù) 姓 名 史孟晨 編 號 01 數(shù)據(jù)結(jié)構(gòu) 87 離散數(shù)學(xué) 90 大學(xué)英語 78 請輸入第 2 名學(xué)生分數(shù) 姓 名 袁欣 編 號 02 數(shù)據(jù)結(jié)構(gòu) 78 離散數(shù)學(xué) 80 大學(xué)英語 92 請輸

26、入第 3 名學(xué)生分數(shù) 姓 名 趙宇 編 號 03 數(shù)據(jù)結(jié)構(gòu) 88 離散數(shù)學(xué) 76 大學(xué)英語 95 請輸入第 4 名學(xué)生分數(shù) 姓 名 滕芷 編 號 04 數(shù)據(jù)結(jié)構(gòu) 79 離散數(shù)學(xué) 84 大學(xué)英語 88 請輸入第 5 名學(xué)生分數(shù) 姓 名 張一析 編 號 05 數(shù)據(jù)結(jié)構(gòu) 78 離散數(shù)學(xué) 68 大學(xué)英語 91 請輸入第 6 名學(xué)生分數(shù) 姓 名 白曉彤 編 號 06 數(shù)據(jù)結(jié)構(gòu) 88 離散數(shù)學(xué) 76 大學(xué)英語 90 學(xué)生總分成績排序表 名次 學(xué)號 姓 名 數(shù)據(jù)結(jié)構(gòu) 離散數(shù)學(xué) 大學(xué)英語 總

27、分 1 3 趙宇 88 76 95 259 2 1 史孟晨 87 90 78 255 3 6 白曉彤 88 76 90 254 4 4 滕芷 79 84 88 251 5 2 袁欣 78 80 92 250 6 5 張一析 78 68 91 237 選擇交換 成績 1 排序表 名次學(xué)號 姓名 分數(shù) 1 3 趙宇 88 1 6 白曉彤 88 2 1 史孟晨 87 3 4 滕芷 79 選擇交換 成績 2 排序表 名次學(xué) 號 姓名 分數(shù) 1 1 史孟晨

28、90 2 4 滕芷 84 3 2 袁欣 80 選擇交換 成績 3 排序表 名次學(xué) 號 姓名 分數(shù) 1 3 趙宇 95 2 2 袁欣 92 3 5 張一析 91 Press any key to continue 輸入的數(shù)據(jù)及運行結(jié)果截屏：

29、醫(yī)大團編B崗大屢編醫(yī)大履編B曷大 ? ? 數(shù) 分 生 睜止 - 6 5」啟衆(zhòng) 4 9 4 8「U長 5 8 8 1 6 8 6 0 7 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 P\a aj\Debuq\aaarexe" 口 8 6 0 7 9 表 12 3 4 5

30、 6 9 5 2 0 8 5 4 7 5 5 3 2 2 10 2 5 5 2 2 0 6 97 6 4 0 7 8 8 8 0 1 7 9 9 5 8 2 9 8 9 7 8 8 8 8 7 8 9 8 8 7 7 4 分8 的87 8 9 分8 7 ?表 序名搟辰序看辰 數(shù)91 5 2 分9 9 表 H- 3 2 5 % 交次 3 筆 12 3 1 丿彳扌/ Ji 丿彳 析M 琴 張養(yǎng)孟芷排孟芷廉丟“ 豐勲娜止欣T 1姓趙量滕2 H3姓爹張O 趙史SB譬書號'a號 成 3 ￡ 1 4 成 14-2 5% % 交次

31、 交次 112 3? 1 2 迤名 四、心得體會 本學(xué)期開設(shè)的《數(shù)據(jù)結(jié)構(gòu)》課程已經(jīng)告一段落，現(xiàn)就學(xué)習(xí)體會進行學(xué)習(xí)總 結(jié)。 這是一門純屬于設(shè)計的科目，它需用把理論變?yōu)樯蠙C調(diào)試。剛開始學(xué)的時 候確實有很多地方很不理解，每次上課時老師都會給我們出不同的設(shè)計題目， 對 于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后， 我決定靜下 心來，仔細去寫程序。老師會給我們需要編程的內(nèi)容一些講解， 順著老師的思路， 來完成自己的設(shè)計，我

32、們可以開始運行自己的程序。 這門課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問題，最為突出的，書本上 的知識與老師的講解都比較容易理解，但是當自己采用剛學(xué)的知識點編寫程序時 卻感到十分棘手，有時表現(xiàn)在想不到適合題意的算法，有時表現(xiàn)在算法想出來后， 只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序 的編寫 剛開始學(xué)的時候確實有很多地方我很不理解，每次上上機課時老師都會給 我們出不同的設(shè)計題目，對于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)， 撞了幾次壁之后，我決定靜下心來，仔細去寫程序。老師會給我們需要編程的 內(nèi)容一些講解，順著老師的思路，來完成自己的設(shè)計，我們可以開始運行自己

33、的程序，可是好多處的錯誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯誤， 但是程序還是得繼續(xù)下去，我多次請教了老師和同學(xué)，逐漸能自己找出錯誤， 并加以改正。 TC 里檢查錯誤都是用英文來顯示出來的，經(jīng)過了這次課程設(shè)計， 現(xiàn)在已經(jīng)可以了解很多錯誤在英文里的提示，這對我來說是一個突破性的進 步，眼看著一個個錯誤通過自己的努力在我眼前消失，覺得很是開心。此次的 程序設(shè)計能夠成功，是我和我的同學(xué)三個人共同努力作用的結(jié)果。在這一段努 力學(xué)習(xí)的過程中，我們的編程設(shè)計有了明顯的提高。 其實現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它 上面花費了好多心血，覺得它很難， 是需用花費了大量的時間編寫

34、出來的。 現(xiàn)在 真正的明白了一些代碼的應(yīng)用， 每個程序都有一些共同點，通用的結(jié)構(gòu)，相似的 格式。只要努力去學(xué)習(xí)，就會靈活的去應(yīng)用它。 以上便是我對《數(shù)據(jù)結(jié)構(gòu)》這門課的學(xué)習(xí)總結(jié)，我會抓緊時間將沒有吃透 的知識點補齊 , 克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁 進！ 實驗一順序表與鏈表 、實驗?zāi)康? 1、 掌握線性表中元素的前驅(qū)、后續(xù)的概念。 2、 掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。 3、 對線性表相應(yīng)算法的時間復(fù)雜度進行分析。 4、 理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點（優(yōu)缺點） 。 二、實驗預(yù)習(xí) 說明以下概念（到主要參考教材上查找答案） 1、

35、 線性表： 2、 順序表： 3、 鏈表： 、實驗內(nèi)容和要求 1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結(jié)果。 #in clude #in clude #defi ne ERROR 0 #defi ne OK 1 #defi ne INIT_SIZE 5 /* #defi ne INCREM 5 /* typedef int ElemType; /* typedef struct Sqlist{ ElemType *slist; /* int len gth; /* int listsize; /* }Sqli

36、st; 初始分配的順序表長度*/ 溢出時，順序表長度的增量 */ 定義表元素的類型*/ 存儲空間的基地址*/ 順序表的當前長度*/ 當前分配的存儲空間*/ 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

37、); /* 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

38、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

39、sq(Sqlist *L){ int i; for(i=1;i<=L->length;i++) printf("%5d",L->slist[i-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(ElemTy

40、pe)); if(!L->slist) return ERROR; L->listsize+=INCREM; } for(k=L->length-1;k>=i-1;k--){ L->slist[k+1]= L->slist[k]; } L->slist[i-1]=e; L->length++; return OK; }/*ListInsert*/ /* 在順序表中刪除第 i 個元素 */ int ListDelete_sq(Sqlist *L,int i){ } /* 在順序表中查找指定值元素，返回其序號 */ int ListLocate(Sqlist *L,Elem

41、Type 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:(loc

42、ation,data)\n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("\n3-Print Sqlist:\n"); PrintList_sq(&sl); printf("\n"); } else printf("ERROR"); return 0; } 運行結(jié)果(運行結(jié)果截屏粘貼到這里) 算法分析(參照教材上的“算法分析”部分填寫本部分內(nèi)容， 2、為第 1 題補充刪除和查找功能函數(shù)，并在主函數(shù)中補充代碼驗證算法的正確性。 刪除算法代碼： 運行結(jié)果 算法分析 查找算法代碼： 運行結(jié)果 算法分析

43、 3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結(jié)果。 #in clude #in clude #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)

44、; /* int GetElem(LinkList L,int i,ElemType *e); /* */ 輸出帶頭結(jié)點單鏈表的所有元素 */ */ 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=N

45、ULL; /* p_>n ext=q; /* p=q; } retur n head; }/*CreateList*/ head-> next=NULL; prin tf("i nput 輸入元素值*/ 結(jié)點指針域置空*/ 新結(jié)點連在表末尾*/ 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(Lin

46、kList L,int i,ElemType *e){ LNode *p;int j=1; p=L->n ext; while(p&&jnext;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){

47、 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); else printf("not exists"); }else printf("ERROR"); return 0; } 運行

48、結(jié)果 算法分析 4、為第 3 題補充插入功能函數(shù)和刪除功能函數(shù)。 并在主函數(shù)中補充代碼驗證算法的正確性。 插入算法代碼： 運行結(jié)果 算法分析 刪除算法代碼: 運行結(jié)果 算法分析 以下為選做實驗： 5、循環(huán)鏈表的應(yīng)用（約瑟夫回環(huán)問題） n 個數(shù)據(jù)元素構(gòu)成一個環(huán)，從環(huán)中任意位置開始計數(shù)，計到 m 將該元素從表中取出，重復(fù)上 述過程，直至表中只剩下一個元素。 提示：用一個無頭結(jié)點的循環(huán)單鏈表來實現(xiàn)

49、n 個元素的存儲。 算法代碼 6、設(shè)一帶頭結(jié)點的單鏈表，設(shè)計算法將表中值相同的元素僅保留一個結(jié)點。 提示：指針p從鏈表的第一個元素開始，利用指針 q從指針p位置開始向后搜索整個鏈表， 刪除與之值相同的元素；指針 p繼續(xù)指向下一個元素，開始下一輪的刪除，直至 p== null 為至，既完成了對整個鏈表元素的刪除相同值。 算法代碼 四、實驗小結(jié) 實驗二棧和隊列 一、實驗?zāi)康? 1、 掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作； 2、 掌握隊列的結(jié)構(gòu)特性及其入隊、出隊的操作，掌握循環(huán)隊列的特點及其操作。 二、實驗預(yù)習(xí) 說明以下概念 1、 順序棧： 2、 鏈棧： 3、 循環(huán)隊列：

50、 4、 鏈隊 、實驗內(nèi)容和要求 ，運 1、閱讀下面程序，將函數(shù) Push和函數(shù)Pop補充完整。要求輸入元素序列 行結(jié)果如下所示。 #in clude #in clude #defi ne ERROR 0 #defi ne OK 1 #defi ne STACK_INT_SIZE 10 /* #defi ne STACKINCREMENT 5 /* typedef int ElemType; /* typedef struct{ ElemType *base; ElemType *top; 存儲空間初始分配量*/ 存儲空間

51、分配增量*/ 定義元素的類型*/  int stacksize; /* }SqStack; 當前已分配的存儲空間 */ 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(SqSta

52、ck *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; i

53、f(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); }/*Po

54、p_and_Print*/ int mai n(){ SqStack ss; prin tf("\n1-createStack\n"); CreateStack(&ss); prin tf("\n 2-Pop&Print\n"); Prin tStack(&ss); return 0; } 算法分析：輸入元素序列 1 2 3 4 5 ，為什么輸出序列為 5 4 3 2 1 ?體現(xiàn)了棧的什么 特性？ 2、在第1題的程序中，編寫一個十進制轉(zhuǎn)換為二進制的數(shù)制轉(zhuǎn)換算法函數(shù)（要求利用棧來 實現(xiàn)），并驗證其正確性。 實現(xiàn)代碼 驗證 3、閱讀并運行程序，并分析程序功能。 #in

55、 clude #in clude #in clude #defi ne M 20 #defi ne elemtype char typedef struct { elemtype stack[M]; 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;

56、 } void push(stack node *st,elemtype x) { if(st->top==M) prin tf("the stack is overflow!' n"); else { st_>top=st_>top+1; st->stack[st->top]=x; } } void pop(stack node *st) { if(st->top>0) st->top--; else printf( Stack is Empty!' n ”; } int mai n() { char s[M]; int i; stack node *s

57、p; 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;itop==0) prin tf("'('match')'!\n"); else printf("'('not match')'!\n");

58、 return 0; } 輸入：2+((c-d)*6-(f-7)*a)/6 運行結(jié)果： 輸入：a-((c-d)*6-(s/3-x)/2 運行結(jié)果： 程序的基本功能： 以下為選做實驗： 4、設(shè)計算法，將一個表達式轉(zhuǎn)換為后綴表達式，并按照后綴表達式進行計算，得出表達式 得結(jié)果。 實現(xiàn)代碼 5、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列， 并且只設(shè)一個指針指向隊尾結(jié)點 （不設(shè)隊頭指針） 試編寫相應(yīng)的置空隊列、入隊列、出隊列的算法。 實現(xiàn)代碼： 四、實驗小結(jié) 實驗三 串的模式匹配 一、實驗?zāi)康? 1 、了解串的基本概念 2 、掌握串的模式匹配算法的實現(xiàn) 二、實驗預(yù)習(xí) 說明以下

59、概念 1、模式匹配： 2、BF算法: 三、實驗內(nèi)容和要求 1 、閱讀并運行下面程序，根據(jù)輸入寫出運行結(jié)果。 #include #include #define MAXSIZE 100 typedef struct{ char data[MAXSIZE]; int length; }SqString; 串的比較 */ int strCompare(SqString *s1,SqString *s2); /* void show_strCompare(); void strSub(SqString *s,int start,int

60、sublen,SqString *sub); /* 求子串 */ void show_subString(); int strCompare(SqString *s1,SqString *s2){ int i; for(i=0;ilength&&ilength;i++) if(s1->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i]; return s1->length-s2->length; } void show_strCompare(){ SqString s1,s2; int k; pri

61、ntf("\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=s2\n"); else if(k<0) printf("s1s2\n"); printf("\n***sh

62、ow 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;idata[i]=s->data[start+i-1]; sub->length=sublen; } void show_subString(){ SqString s,sub; int start,suble

63、n,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"); else{ printf("subString is :")

64、; for(i=0;i

65、are();break; case 2:show_subString();break; default:n=0;break; } }while(n); return 0; } BF 算法。 運行程序 輸入： 1 student students 2 Computer Data Stuctures 10 4 運行結(jié)果： 2 、實現(xiàn)串的模式匹配算法。補充下面程序，實現(xiàn)串的 #include #include #define MAXSIZE 100 typedef struct{ char data[MAXSIZE]; int length

66、; }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){ 補充代碼 } void getNext(SqString *t,int next[]){ int i=0,j=-1; next[0]=-1; while(ilength){ if((j==-1)||(t->data[i]==t->data[j])){ i++;j++;next[i]=j; }else j=next[j]; } } void show_index(){ SqString s,t; int k,next[MAXSIZE]={0},i; printf("\n***show i