《數(shù)據(jù)結(jié)構(gòu)A》實驗指導(dǎo)書2012版_馬春江.

1、僚I處他車X歡謬昵HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY數(shù)據(jù)結(jié)構(gòu)A實驗指導(dǎo)書馬春江撰寫付勇智審核電氣與信息工程學(xué)院計算機工程系2013年12月、八,、刖言數(shù)據(jù)結(jié)構(gòu)課程開設(shè) 8個必做的實驗：1線性表基本操作的編程實現(xiàn)（2學(xué)時，驗證型），掌握線性表的建立、遍歷、插入、刪除等基本操作的 編程實現(xiàn)，也可以進(jìn)一步編程實現(xiàn)查找、逆序、排序等操作，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu)中任選，也 可以全部實現(xiàn)，用菜單進(jìn)行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。2、 堆棧和隊列基本操作的編程實現(xiàn)（2學(xué)時，驗證型），掌握堆棧和隊列的建立、進(jìn)棧、出棧、進(jìn)隊、出 隊

2、等基本操作的編程實現(xiàn)，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu)中任選，也可以全部實現(xiàn)，用菜單進(jìn)行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。3、串基本操作的編程實現(xiàn)（2學(xué)時，驗證型），掌握串的建立、遍歷、插入、刪除等基本操作的編程實現(xiàn)， 也可以進(jìn)一步編程實現(xiàn)查找、合并、剪裁等操作，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu)、索引結(jié)構(gòu)中任選，也 可以全部實現(xiàn)，用菜單進(jìn)行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。4、 二維數(shù)組基本操作的編程實現(xiàn)（ 2學(xué)時，驗證型），掌握數(shù)組的建立、讀取數(shù)據(jù)、壓縮存儲等基本操作 的編程實現(xiàn)，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu)中任選，也可以全部實現(xiàn)，用菜單進(jìn)行管理。也鼓

3、勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。5、二叉樹基本操作的編程實現(xiàn)（2學(xué)時，驗證型），掌握二叉樹的建立、遍歷、插入、刪除等基本操作的 編程實現(xiàn)，也可以進(jìn)一步編程實現(xiàn)查找等操作，存儲結(jié)構(gòu)主要采用鏈接結(jié)構(gòu)，用菜單進(jìn)行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。6、圖基本操作的編程實現(xiàn)（2學(xué)時，驗證型），掌握圖的建立、遍歷、插入、刪除等基本操作的編程實現(xiàn)， 也可以進(jìn)一步編程實現(xiàn)查找等操作，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu)中任選，也可以全部實現(xiàn)，用菜單進(jìn) 行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。7、查找技術(shù)的編程實現(xiàn)（2學(xué)時，綜合型），掌握查找技術(shù)的編程實現(xiàn)，可以實現(xiàn)一種，也

4、可以實現(xiàn)多種， 用菜單進(jìn)行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。8、排序技術(shù)的編程實現(xiàn)（2學(xué)時，綜合型），掌握排序技術(shù)的編程實現(xiàn)，可以實現(xiàn)一種，也可以實現(xiàn)多種， 用菜單進(jìn)行管理。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。9、實驗要求把每次實驗的程序文本和運行結(jié)果存入到本人的用戶目錄下供實驗老師檢查。10 、對實驗室要求是必須保證學(xué)生上機時人手一機；必須保證滿足課程要求的上機時數(shù) ；必須配備專職的數(shù)據(jù)結(jié)構(gòu)課程的實驗指導(dǎo)老師。目錄實驗一線性表基本操作的編程實現(xiàn)4實驗二堆棧和隊列基本操作的編程實現(xiàn)9實驗三串基本操作的編程實現(xiàn) 12實驗四二維數(shù)組基本操作的編程實現(xiàn) 16實驗五二叉樹基

5、本操作的編程實現(xiàn) 19實驗六圖基本操作的編程實現(xiàn) 24實驗七查找技術(shù)的編程實現(xiàn) 27實驗八排序技術(shù)的編程實現(xiàn) 29湖北汽車工業(yè)學(xué)院實驗報告班 號 學(xué) 號姓名選課班中的序號 完成日期年月日_至 節(jié)實驗一 線性表基本操作的編程實現(xiàn)一、實驗?zāi)康?. 了解線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的工作原理；2. 理解順序表和鏈表的工作原理；3. 掌握順序表和鏈表的程序設(shè)計；二、實驗要求編程實現(xiàn)通用的線性表常用功能程序，其中插入數(shù)據(jù)和刪除數(shù)據(jù)是必須實現(xiàn)的。存儲結(jié)構(gòu)由學(xué)生自己選擇。實驗題目采用班級目標(biāo)總體一致，細(xì)節(jié)由學(xué)生按照自己的能力隨意拓展和提高，程序源碼實現(xiàn)原創(chuàng)設(shè)計。存儲結(jié)構(gòu)最簡模式為：順序存儲，使用一維數(shù)組實現(xiàn)。

6、鼓勵使用鏈表結(jié)構(gòu)，一般可以采用單鏈表結(jié)構(gòu)，更 加復(fù)雜的可以采用循環(huán)鏈表或雙向鏈表結(jié)構(gòu)。時間足夠的情況下，希望把這些在課外全部自行編程實現(xiàn)。界面設(shè)計最簡模式為：無界面設(shè)計，極少提示。鼓勵更加人性化的界面設(shè)計，提示清晰，操作過程流暢。 如果啟用文件，則可以采用全程無界面設(shè)計模式。原始數(shù)據(jù)構(gòu)建方式最簡模式為：鍵盤輸入。其他的方式也在鼓勵之中：數(shù)據(jù)內(nèi)置，計算機自動生成，文件 讀入。數(shù)據(jù)類型最簡模式為：整數(shù)。其他依次鼓勵使用的為：實數(shù)、字符、英語字符串、漢字字符串。三、實驗內(nèi)容功能設(shè)計最簡模式為：原始數(shù)據(jù)構(gòu)建、全部數(shù)據(jù)遍歷、插入數(shù)據(jù)、刪除數(shù)據(jù)。其他的任何相關(guān)功能見參考 教材，鼓勵實現(xiàn)。開發(fā)語言最簡模式為

7、： C語言。以下依次為更加鼓勵的設(shè)計環(huán)境：C+（不帶對象），C+（帶對象），C+帶圖形包（帶對象），C+ wi ndows mfc （帶對象）。知識分布原始數(shù)據(jù)構(gòu)建、全部數(shù)據(jù)遍歷屬于 C語言。插入數(shù)據(jù)、刪除數(shù)據(jù)涉及的循環(huán)程序設(shè)計屬于C語言。但是插入數(shù)據(jù)、刪除數(shù)據(jù)涉及的數(shù)據(jù)移動的必要性、移動的所有位置和數(shù)量控制、具體移動的過程、移動對于 程序的時間效率產(chǎn)生的影響屬于數(shù)據(jù)結(jié)構(gòu)原理范疇。重點實驗內(nèi)容圖示教材圖3-2順序表插入操作的示意圖dtfct FULFIL IVV1址a47if101借科憤63ill1 . |0607y卜列冋WX01巖影0w iS 910oOKHEitWiinr掃述UlH7 |如

8、VT07.cXt6301H7 06071教材圖3-3順序表刪除操作的示意圖順序表的操作關(guān)鍵是要把相關(guān)的坐標(biāo)控制好，如合法的插入和刪除位置的范圍，移動數(shù)據(jù)兩邊的坐標(biāo)值。 完成任務(wù)最后要注意數(shù)據(jù)量的變化。newnode 222|Aheadp / Z-T 4*T ill 殳4 333命 444AJchp教材圖3-6單鏈表中進(jìn)行插入操作的示意圖follow? seatchp教材圖3-7單鏈表存儲刪除操作的示意圖鏈表編程主要是注意關(guān)鍵語句的次序相關(guān)性，注意不要出現(xiàn)“內(nèi)存垃圾”，把握好修改鏈的節(jié)奏和語句。 注意空間的結(jié)點的申請和釋放。重點實驗內(nèi)容參考源碼 順序表returninfo seqlist:i n

9、sert(i nt positi on,const int &item)/ 插入一個元素if(co un t+1=Maxsize) return overflow;if(positi oncoun t+1) retur n ran ge_error;coun t+;for(i nt i=co un t;i=positi on ;i-) dataarrayi=dataarrayi-1;dataarraypositi on-1=item;retur n success;retur ninfo seqlist:remove(i nt positi on) if(empty()retur n un d

10、erflow;if(positi oncount) retur n ran ge_error;for(i nt i=positi on-1;ico un t;i+) dataarrayi=dataarrayi+1;coun t-;retur n success;鏈表/溢出處理/計數(shù)器加一/循環(huán)移動數(shù)據(jù)/刪除一個元素/循環(huán)移動數(shù)據(jù)/計數(shù)器減一/給數(shù)據(jù)賦值/注意此處的次序相關(guān)性/計數(shù)器加一刪除一個結(jié)點returninfo lin klist:i nsert(i nt positi on,const int &item)/ 插入一個結(jié)點if(positi on=co un t+2)retur n r

11、an ge_error;node *newno dep=new no de,*searchp=headp-n ext,*followp=headpfor(i nt i=1; in ext;newno dep-data=item;newno dep-n ext=followp-n ext; followp-n ext =newno dep;coun t+;retur n success;retur ninfo lin klist:remove(i nt positi on) if(empty()retur n un derflow;/這里兩個指針的初始值設(shè)計一前一后if(positi on=co

12、 un t+1) retur n ran ge_error;node *searchp=headp-n ext,*followp=headp; for(i nt i=1; in ext;刪除結(jié)點的實際語句/釋放該結(jié)點/計數(shù)器減一followp-n ext=searchp-n ext; delete searchp;coun t-;retur n success;實驗測試數(shù)據(jù)設(shè)計通過對各種數(shù)據(jù)的輸入和輸出的結(jié)果對比分析，證實所有的功能的正確性，特別是需要 測試非法數(shù)據(jù)的響應(yīng)情況。實驗報告中需要提交這些數(shù)據(jù)以及結(jié)果和自己的分析。鼓勵提出一些錯誤 （Bug）報告和改進(jìn)建議。以下為一個小的測試數(shù)據(jù)范例

13、：邏輯結(jié)構(gòu)：線性表，存儲結(jié)構(gòu)：順序，操作：插入。數(shù)據(jù)申請空間的下標(biāo) 范圍：0-10，實際數(shù)據(jù)最后的位置 6，0號單元可以啟用，也可以不用或者使用其他的功能。測試地址必須包括：-5、-1、0、1、5、6、7、9、10、11、18等至少11個數(shù)據(jù)。也就是說插入或刪除必須考慮意外的兩種情況： 1順序表在分配的地址空間中，但是范圍超界，2.完全是不存在的地址。其他的正常的都需要測試：如正常的邊界。如順序表插入時，最后數(shù)據(jù)地址為5.則在6插入也是容許的。數(shù)據(jù)構(gòu)成的多態(tài)性學(xué)生可以根據(jù)自己的實力實現(xiàn)下面的某一個要求或同時實現(xiàn)多種數(shù)據(jù)類型的實現(xiàn)。1. 數(shù)據(jù)構(gòu)成為字符。由單個大寫字母構(gòu)成結(jié)點名稱。（小寫字母自動

14、換成大寫字母）2. 數(shù)據(jù)構(gòu)成為字符串。由美國人的姓名組成。（可以為兩個或三個單詞，首字母大寫）3. 數(shù)據(jù)構(gòu)成為中文字符串。由中文人名組成。4. 數(shù)據(jù)構(gòu)成為多個數(shù)據(jù)。如一個人的多種信息。如：學(xué)號、姓名、性別、課程名、分?jǐn)?shù)等。（也可以自己設(shè)計）實驗報告提示實驗報告主要按照以下的框架完成：本次實驗的實驗方式、目標(biāo)和其他背景信息。實驗的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基本概念和原理（最好附圖）。實驗的總體設(shè)計（功能和界面等，算法思路）。實驗的程序設(shè)計細(xì)節(jié)或測試細(xì)節(jié)。實驗的總收獲清單：（包含 弄懂的原理和一些結(jié)論、學(xué)會了新的一些語句或功能段源碼、學(xué)會了新的測試方法和過程、學(xué)會了內(nèi)部結(jié)構(gòu)控 制和一些軟件設(shè)計規(guī)范的細(xì)節(jié)

15、等等），實驗的遺憾和下一步努力的方向（總結(jié)自己未能達(dá)成的目標(biāo)和原因分析，提出可行的改進(jìn)方案）。報告中應(yīng)該涉及界面截圖、開發(fā)過程綜述（花費時間、總語句數(shù)、調(diào)試過程）、開發(fā)總結(jié)、重點源碼清單（本次實驗僅僅為插入和刪除）、致謝等。在實驗中受到其他同學(xué)的幫助時在報告最后的致謝中鼓勵實名感謝。實驗提交文件約定程序名一律類似為：T1123-02-17-某某某-鏈表實驗程序.cpp所有信息之間為中橫線。如果有文本文件，也是類似的結(jié)構(gòu)：T1123-2-17-某某某-鏈表實驗程序輸入數(shù)據(jù).txtT1123-2-17-某某某-鏈表實驗程序輸出數(shù)據(jù).txt報告電子版為T1123-2-17-某某某-實驗報告01.do

16、c（必須涉及工程的時候請打包管理，但是最后的文件名和內(nèi)部的文件名也需要如此管理。）思考題1. 線性表的順序存儲和鏈表存儲的差異？優(yōu)缺點分析?2. 那些操作引發(fā)了數(shù)據(jù)的移動？3. 算法的時間效率是如何體現(xiàn)的？4. 鏈表的指針是如何后移的？如何加強程序的健壯性?實驗使用參考書本實驗指導(dǎo)書主要參考書為：數(shù)據(jù)結(jié)構(gòu)與程序構(gòu)建馬春江付勇智孟繁軍編著ISBN 978-7-302-29404-7清華大學(xué)出版社2012年8月第1版四、實驗總結(jié)和體會湖北汽車工業(yè)學(xué)院實驗報告班 號 學(xué) 號姓名選課班中的序號 完成日期年月日_至 節(jié)實驗二棧和隊列基本操作的編程實現(xiàn)一、實驗?zāi)康?. 了解棧和隊列的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的工

17、作原理；2. 理解棧和隊列的用途；3. 掌握棧和隊列的程序設(shè)計；二、實驗要求由于本次實驗涉及到棧和隊列兩種數(shù)據(jù)結(jié)構(gòu)的原理，實驗題目將按照分級和分類的方式提供，任何學(xué)生都可以選擇其中之一或多個綜合來達(dá)成對原理的理解。細(xì)節(jié)由學(xué)生按照自己的能力隨意拓展和提高，程序源碼實 現(xiàn)原創(chuàng)設(shè)計。存儲結(jié)構(gòu)最簡模式為：順序存儲，使用一維數(shù)組實現(xiàn)。鼓勵使用鏈表結(jié)構(gòu)，一般可以采用單鏈表結(jié)構(gòu)。時 間足夠的情況下，希望把這些在課外全部自行編程實現(xiàn)。特別是希望和第一次實驗采取相反的策略進(jìn)行選擇， 以此來提高自己對于不同的存儲結(jié)構(gòu)的熟練運用。界面設(shè)計最簡模式為：無界面設(shè)計，極少提示。鼓勵更加人性化的界面設(shè)計，提示清晰，操作過程

18、流暢。 如果啟用文件，則可以采用全程無界面設(shè)計模式。原始數(shù)據(jù)構(gòu)建方式最簡模式為：鍵盤輸入。其他的方式也在鼓勵之中：數(shù)據(jù)內(nèi)置，計算機自動生成，文件 讀入。數(shù)據(jù)類型最簡模式為：整數(shù)。其他依次鼓勵使用的為：實數(shù)、字符、英語字符串、漢字字符串。三、實驗內(nèi)容功能設(shè)計難度系數(shù)分為五級制：1:很容易，2:較容易，3:有一定難度，4:難度較大，5:難度很大。1. 棧功能演示系統(tǒng)。難度系數(shù)：22. 漢字回文字符串的判斷程序。難度系數(shù)：33. 十進(jìn)制正整數(shù)轉(zhuǎn)換為八進(jìn)制的程序。難度系數(shù)：44. 環(huán)狀隊列功能演示系統(tǒng)。難度系數(shù)：25. 十進(jìn)制正小數(shù)轉(zhuǎn)換為八進(jìn)制的程序。難度系數(shù)：36. 用計算機自動產(chǎn)生作業(yè)名、申請時間

19、和打印時間的隨機數(shù)據(jù)，然后用隊列管理，隨時顯示隊列中的數(shù)據(jù)和已經(jīng)打印完畢的作業(yè)名。難度系數(shù)：4C+開發(fā)語言最簡模式為：C語言。以下依次為更加鼓勵的設(shè)計環(huán)境：C+（不帶對象），C+（帶對象），帶圖形包（帶對象），C+ wi ndows mfc （帶對象）。C語言。進(jìn)棧和出棧、進(jìn)隊和出隊等原理知識分布界面的顯示和控制、原始數(shù)據(jù)構(gòu)建、全部數(shù)據(jù)遍歷屬于 屬于數(shù)據(jù)結(jié)構(gòu)原理范疇。重點實驗內(nèi)容圖示討論的初始狀態(tài)相對初始狀態(tài)進(jìn)棧 444的效果相對初始狀態(tài)出棧 333的效果i16665554443top 3；期:3tOp 2:滋B3 :2333233312221222top 13 滋 2 ! !01110111

20、U111教材圖5-2順序棧的進(jìn)棧、出棧示意圖111A1 inks lack lop空環(huán)隊入隊9次，出隊4次再入隊3次，出隊3次再入隊4次圖6-4環(huán)狀隊列的操作示意圖重點實驗內(nèi)容參考源碼本次實驗無參考代碼，請參考教材。(Bug)報實驗測試數(shù)據(jù)設(shè)計通過對各種數(shù)據(jù)的輸入和輸出的結(jié)果對比分析，證實所有的功能的正確性，特別是需要 測試非法數(shù)據(jù)的響應(yīng)情況。 實驗報告中需要提交這些數(shù)據(jù)以及結(jié)果和自己的分析。鼓勵提出一些錯誤告和改進(jìn)建議。以下為一個小的測試數(shù)據(jù)范例：邏輯結(jié)構(gòu)：棧，存儲結(jié)構(gòu)：順序，操作：進(jìn)棧。數(shù)據(jù)申請空間的下標(biāo)范圍: 0-10，實際數(shù)據(jù)最后的位置 6, 0號單元可以啟用，也可以不用或者使用其他的

21、功能。測試必須包括：上溢、 溢。數(shù)據(jù)構(gòu)成的多態(tài)性學(xué)生可以根據(jù)自己的實力實現(xiàn)下面的某一個要求或同時實現(xiàn)多種數(shù)據(jù)類型的實現(xiàn)。5. 數(shù)據(jù)構(gòu)成為字符。由單個大寫字母構(gòu)成結(jié)點名稱。（小寫字母自動換成大寫字母）6. 數(shù)據(jù)構(gòu)成為字符串。由美國人的姓名組成。（可以為兩個或三個單詞，首字母大寫）7. 數(shù)據(jù)構(gòu)成為中文字符串。由中文人名組成。8. 數(shù)據(jù)構(gòu)成為多個數(shù)據(jù)。如一個人的多種信息。如：學(xué)號、姓名、性別、課程名、分?jǐn)?shù)等。（也可以自己設(shè) 計）9. 進(jìn)棧數(shù)據(jù)可以為象棋盤的位置坐標(biāo)。思考題棧和隊列的性質(zhì)？使用順序存儲和鏈表存儲的差異？優(yōu)缺點分析？棧和隊列引發(fā)了數(shù)據(jù)移動嗎？為什么？算法的時間效率是如何體現(xiàn)的？棧和隊列各

22、自的主要作用？實驗使用參考書本實驗指導(dǎo)書主要參考書為：數(shù)據(jù)結(jié)構(gòu)與程序構(gòu)建馬春江付勇智孟繁軍編著ISBN 978-7-302-29404-7清華大學(xué)出版社2012年8月第1版四、實驗總結(jié)和體會湖北汽車工業(yè)學(xué)院實驗報告班號選課班中的序號學(xué)號姓名完成日期年月日至節(jié)實驗三 串基本操作的編程實現(xiàn)一、實驗?zāi)康?. 了解串的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的工作原理；2. 理解串的特殊性；3. 掌握順序串、鏈串、索引結(jié)構(gòu)的程序設(shè)計；二、實驗要求本次實驗涉及到字符串工作原理，實驗題目將按照基本功能展示和應(yīng)用級別的方式提供，任何學(xué)生都可以 選擇其中之一或多個綜合來達(dá)成對原理的理解。細(xì)節(jié)由學(xué)生按照自己的能力隨意拓展和提高，程序

23、源碼實現(xiàn)原 創(chuàng)設(shè)計。存儲結(jié)構(gòu)字符串使用順序存儲，使用一維數(shù)組實現(xiàn)會引發(fā)大量的數(shù)據(jù)移動。而單獨使用鏈表結(jié)構(gòu)，又會引 發(fā)程序設(shè)計相當(dāng)困難。最終的解決方案是聯(lián)合使用數(shù)組和鏈表的思想，推出更復(fù)雜的索引結(jié)構(gòu)，用最小的數(shù)據(jù) 移動量解決上面的兩個致命問題。但是在實驗中，可以使用單獨的存儲結(jié)構(gòu)進(jìn)行訓(xùn)練，以便對這種特殊的線性 表結(jié)構(gòu)和第一次實驗中涉及到的線性表結(jié)構(gòu)做一個較為全面的對比。界面設(shè)計最簡模式為：無界面設(shè)計，極少提示。鼓勵更加人性化的界面設(shè)計，提示清晰，操作過程流暢。 如果啟用文件，則可以采用全程無界面設(shè)計模式。原始數(shù)據(jù)構(gòu)建方式最簡模式為：鍵盤輸入。其他的方式也在鼓勵之中：數(shù)據(jù)內(nèi)置，計算機自動生成，文件

24、 讀入。數(shù)據(jù)類型英語字符串、漢字字符串。三、實驗內(nèi)容功能設(shè)計難度系數(shù)分為五級制：1:很容易，2:較容易，3:有一定難度，4:難度較大，5:難度很大。1.字符串的查找和其他基本功能的實現(xiàn)。難度系數(shù)：22.統(tǒng)計文件中各種信息，如字符個數(shù)，行數(shù)等。難度系數(shù)：23.中央語次序互換系統(tǒng)的設(shè)計。難度系數(shù)：34.多個文本文件敏感水印信息的抄襲判別系統(tǒng)。（可以把多個文件拷貝到一個文件中）難度系數(shù)：45.索引系統(tǒng)的部分功能實現(xiàn)。（將來可以拓展為課程設(shè)計）難度系數(shù)：5C+開發(fā)語言最簡模式為：C語言。以下依次為更加鼓勵的設(shè)計環(huán)境：C+（不帶對象），C+（帶對象），帶圖形包（帶對象），C+ wi ndows mfc

25、（帶對象）。知識分布界面的顯示和控制、數(shù)據(jù)輸入、全部數(shù)據(jù)遍歷屬于C語言。字符串的重要操作在存儲結(jié)構(gòu)中的具體實現(xiàn)等原理屬于數(shù)據(jù)結(jié)構(gòu)原理范疇。主要操作名稱表表7-2字符串的主要操作操作 名稱建議算法名稱編程細(xì)節(jié)約定串初始化create (stri ng)求串長strle ngth(stri ng)返回串string 的長度串賦值strassig n( stri ng1,stri ng2)stri ng1是一個串變量，stri ng2 是一個串常量或串變量（通常stri ng2是一個串常量時稱為串賦值，是一個串變量稱為串復(fù)制）。將string2 的串值賦值給string1 ， string1原來的值

26、被覆蓋掉串連接strcon cat(stri ng1,stri ng2,stri ng) 或 strc on cat(stri ng1,stri ng2)兩個串的聯(lián)接就是將一個串的串值放在另一個串的 后面，連接成一個串。前者是產(chǎn)生新串stri ng ，string1和string2不改變；后者是在string1的后面聯(lián)接 string2的串值，string1改變，string2不改變。例如：stri ng1= bei , stri ng2=jing ，前者操作結(jié)果是string= bei jing ，后者操作結(jié)果是 string1= bei jing 求子串strsub(stri ng,i,l

27、e n)串 string 存在，1 i strlength(string), 0 lenw strlength(string)-i+1。返回從串 string 的第 i個字符開始的長度為len的子串。len=0得到的是 空串。例如：strsub( abcdefghi ,3,4)=cdef串比較strcomp(stri ng1,stri ng2)若 stri ng仁=stri ng2,操作返 回值為 0 ;若string1string2,返回值 string2,返回值0子串定位stri ndex(stri ng,substri ng)尋找子串substring 在主串string中首次出現(xiàn)的位置

28、。若 substring 在 string中，則操作返回substring在string中首次出現(xiàn)的位置，否則返回值為-1。如：strindex（ abcdebda , bc ）=2,strindex（ abcdebda , ba ）=-1串插入stri nsert(stri ng,i, substri ng)串 string 、 substring存在， 1 w i wstrle ngth(stri ng)+1。將串 substri ng 插入到串string 的第i個字符位置上串刪除strdelete(stri ng,i,le n)串 string 存在，1 w i w strlength

29、(string), 0 w lenw strle ngth(stri ng)-i+1。刪除串 stri ng 中從第i個字符開始的長度為len的子串串替換strreplace(stri ng, substri ng01, substri ng02)串 string 、 substring01 、 substring02 存在， substri ng01 不為空。用串 substri ng02 替換串string中出現(xiàn)的所有與串substri ng01相等的不重疊的子串串遍歷strtraverse(stri ng)把字符串中所有字符從頭至尾依次輸出重點實驗內(nèi)容參考源碼retur ninfo st

30、ri ng:strmodify(i nt begi npositi on ,i nt en dpositi on, char n ewstr)int i,j,k,str_le ngth,co un t, newle ngth,retur nvalue;char *n ewdata;coun t=e ndpositi on-begi npositi on+1;str_le ngth=strle n(n ewstr);if(le ngth=0)return empty;if(beg in positi onlen gth|e ndpositi onlen gth|begi npositi on=0

31、|e ndpositi onen dpositi on)return ran ge_error;如果位置錯誤則返回錯誤標(biāo)志for(i=0,j=begi npositio n-1;istr_le ngth &icou nt)當(dāng)輸入串的長度大于需要修改串的長度時，處理后面多的一部分n ewle ngth=str_le ngth-co unt;n ewdata=new char newle ngth;for(i=co un t,k=0;istr_le ngth;i+,k+)n ewdatak=n ewstri;retur nvalue=stri nsert(e ndpositi on+1, newd

32、ata ,n ewle ngth);if(retur nvalue=overflow)return overflow;if(str_le ngthvcou nt)當(dāng)輸入串的長度小于需要修改串的長度時，直接刪除一部分strdelete(begi npositi on+str_le ngth,e ndpositi on);retur n success;實驗測試數(shù)據(jù)設(shè)計通過對各種數(shù)據(jù)的輸入和輸出的結(jié)果對比分析，證實所有的功能的正確性，特別是需要測試非法數(shù)據(jù)的響應(yīng)情況。實驗報告中需要提交這些數(shù)據(jù)以及結(jié)果和自己的分析。鼓勵提出一些錯誤(Bug)報告和改進(jìn)建議。對字符串的修改功能，將有三種情況，新串長分

33、別小于、等于、大于原串長。這個細(xì)節(jié)和一般線性表有著很大的不同。數(shù)據(jù)構(gòu)成的多態(tài)性學(xué)生可以根據(jù)自己的實力實現(xiàn)下面的某一個要求或同時實現(xiàn)多種數(shù)據(jù)類型的實現(xiàn)。字符串可以體現(xiàn)在人名、地名、物品名，可以體現(xiàn)在英語文章，一般性口語造句?？梢泽w現(xiàn)在各種文字中，如 英語或中文。思考題1. 字符串的順序存儲和鏈表存儲的差異？C語言中是如何實現(xiàn)字符串的?2. 在字符串處理方面主要有什么操作？3. 字符串的操作的主要特點是什么？4. 索引結(jié)構(gòu)的最大優(yōu)點是什么？在哪些實際系統(tǒng)中有應(yīng)用？5. 舉出幾個字符串的應(yīng)用范例？實驗使用參考書本實驗指導(dǎo)書主要參考書為：數(shù)據(jù)結(jié)構(gòu)與程序構(gòu)建馬春江付勇智孟繁軍編著ISBN 978-7-3

34、02-29404-7清華大學(xué)出版社2012年8月第1版四、實驗總結(jié)和體會湖北汽車工業(yè)學(xué)院實驗報告班 號 學(xué) 號姓名選課班中的序號 完成日期年月日_至 節(jié)實驗四 二維數(shù)組基本操作的編程實現(xiàn)一、實驗?zāi)康?. 了解線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的工作原理；2. 理解順序表和鏈表的工作原理；3. 掌握順序表和鏈表的程序設(shè)計；二、實驗要求掌握二維數(shù)組的建立、讀取數(shù)據(jù)、壓縮存儲等基本操作的編程實現(xiàn)，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)或鏈接結(jié)構(gòu) 中任選，也可以全部實現(xiàn)。也鼓勵學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計。三、實驗內(nèi)容1. 修改程序：補充推箱子游戲的遺缺的部分，使之能正常運行，邏輯結(jié)果正確。之后增加至少一關(guān)自己的

35、關(guān)數(shù)，墻體，箱子的最初位置，人的最初位置由自己設(shè)定，要求必須有解，而且有一定的破解難度。主要的問 題是部分移動方向的代碼沒有給出，另外計數(shù)器的整體工作不正常，更完善的修改包括啟用棧結(jié)構(gòu)實現(xiàn)后悔的 機制。2. 運行程序了解二維結(jié)構(gòu)：稀疏矩陣的壓縮和解壓縮、生命繁衍模型、迷宮問題等，通過這些程序的運行 過程或結(jié)果體會二維結(jié)構(gòu)在程序設(shè)計中的重要性和實用性。原始數(shù)據(jù)構(gòu)建方式最簡模式為：鍵盤輸入。其他的方式也在鼓勵之中：數(shù)據(jù)內(nèi)置，計算機自動生成，文件讀入。 思考問題1. 數(shù)組的下標(biāo)從什么地址開始？好處是什么？2. 二維數(shù)組的表達(dá)能力僅僅限于橫向和縱向的數(shù)據(jù)關(guān)系嗎？3. 壓縮數(shù)據(jù)主要的思路是什么？4. 為

36、什么用數(shù)組可以存儲超出計算機數(shù)據(jù)要求的范圍的數(shù)字？5. 舉出幾個數(shù)組的應(yīng)用范例？實驗使用參考書本實驗指導(dǎo)書主要參考書為：數(shù)據(jù)結(jié)構(gòu)與程序構(gòu)建馬春江付勇智孟繁軍編著ISBN 978-7-302-29404-7清華大學(xué)出版社2012年8月第1版 參考代碼void box:right()if(mappositi on hpositi onl+1=0)mappositi on hpositi onl+1=4;if(flag=1)mappositi on hpositi on l=2; flag=0; elsemappositi on hpositi on l=0; positi onl+;else if

37、(mappositi on hpositi onl+1=2) 人要到目標(biāo)位置上mappositi on hpositi onl+1=4; if(flag=1)mappositi on hpositi on l=2; elsemappositi on hpositi on l=0;恢復(fù)目標(biāo)位置恢復(fù)原來的狀態(tài)flag=1;標(biāo)志位，記錄人在目標(biāo)位置上positi onl+;else if(mappositi on hpositi onl+1=3&mappositi on hpositi onl+2=0) 位置上mappositi on hpositi onl+2=3;mappositi on hpo

38、siti onl+1=4;if(flag=1) mappositi on hpositi on l=2; flag=0; elsemappositi on hpositi on l=0;positi onl+;else if(mappositi on hpositi onl+1=5&mappositi on hpositi onl+2!=1)位置上推出將箱子推到空白要將箱子從目標(biāo)if(mappositi on hpositi onl+2=2) mappositi on hpositi onl+2=5;mappositi on hpositi onl+1=4; if(flag=1)mapposi

39、ti on hpositi on l=2;下一個位置還是目標(biāo)位置else mappositi on hpositi on l=0; flag=1; else if(mappositio nhpositio nl+2=0)下一個位置是空白mappositi on hpositi onl+2=3;mappositi on hpositi onl+1=4;if(flag=1)mappositi on hpositi on l=2;else mappositi on hpositi on l=0; flag=1; positi onl+;要將箱子推到目else if(mappositi on hpos

40、iti onl+1=3&mappositi on hpositi onl+2=2)標(biāo)位置上mappositio nhpositio nl+2=5;箱子在目標(biāo)位置上mappositi on hpositi onl+1=4;if(flag=1)人在目標(biāo)位置上 mappositi on hpositi on l=2; flag=0; else / 人不在目標(biāo)位置上mappositi on hpositi on l=0;positi onl+;else cou nt-;抵消人不動的情況test_flag();四、實驗總結(jié)和體會湖北汽車工業(yè)學(xué)院實驗報告班 號 學(xué) 號姓名選課班中的序號 完成日期年月日_至

41、 節(jié)實驗五二叉樹基本操作的編程實現(xiàn)一、實驗?zāi)康?. 了解二叉樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的工作原理；2. 理解二叉樹的功能；3. 掌握二叉樹的程序設(shè)計；二、實驗要求二叉樹基本操作的編程實現(xiàn)二叉樹基本操作的編程實現(xiàn)（2學(xué)時，驗證型），掌握二叉樹的建立、遍歷、插入、刪除等基本操作的編程 實現(xiàn)，存儲結(jié)構(gòu)主要采用鏈接結(jié)構(gòu)。實驗性質(zhì)驗證性實驗（學(xué)時數(shù)：2H）三、實驗內(nèi)容本次實驗分為三種模式：第一種：全部自行編程，完成二叉樹構(gòu)建和遍歷的操作。第二種：使用教材中的程序構(gòu)建基本框架，將三種根序遍歷的遞歸實現(xiàn)和層次遍歷回填并且調(diào)試成功。注意如果僅僅顯示成多個數(shù)據(jù)，三種根序遍歷相對是比較簡單的。如a b c d 可以先

42、行嘗試去完成。如果要把結(jié)果顯示成線性表的邏輯結(jié)構(gòu)，即帶有括號和逗號分隔的形式，就有一定的技巧性。如（a,b,c.d ）比較難，可以在上面的程序設(shè)計結(jié)束后再改進(jìn)。注意報告中的二叉樹應(yīng)該是自己設(shè)計的，每個學(xué)生的都是不同的，結(jié)果首先自己分析出來，然后再通過程 序的運行結(jié)果進(jìn)行對比，從而理解一些設(shè)計原理。第三種：用c進(jìn)行程序的改進(jìn)和提高，把下面的程序源碼進(jìn)行輸入和改寫，調(diào)試，直到成功。1. 建立二叉樹，并以前序遍歷的方式將結(jié)點內(nèi)容輸出。2. 將一個表示二叉樹的數(shù)組結(jié)構(gòu)轉(zhuǎn)換成鏈表結(jié)構(gòu)。3. 將表達(dá)式二叉樹方式存入數(shù)組，以遞歸方式建立表達(dá)式之二叉樹狀結(jié)構(gòu)，再分別輸出前序、中序及后 序遍歷結(jié)果，并計算出表達(dá)

43、式之結(jié)果。有興趣和精力的學(xué)生可以自行學(xué)習(xí)線索二叉樹的程序構(gòu)建，對比某些功能的設(shè)計上的差異。思考問題1. 二叉樹是樹嗎？它的定義為什么是遞歸的?2. 三種根序遍歷主要思路是什么？3. 如果不用遍歷算法一般啟用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)后序遍歷？4. 舉出二叉樹的應(yīng)用范例？參考代碼#i nclude#in clude#in clude#in cludeusing n amespace std;enum returni nfo success,fail,overflow,u nderflow, nolchild, no rchild, no father,haveso nl,haves onr, haveas

44、 on, havetwos on s,ra nge_error,quit;定義返回信息清單#defi ne Maxsize 100/定義廣義表數(shù)組的長度char defaultbtree1=a(b,c(,d);/默認(rèn)廣義表數(shù)據(jù)表示的二叉樹范例1char defaultbtree2=a(b(c(d,e),f(,g),h(i,j);/ 默認(rèn)廣義表數(shù)據(jù)表示的二叉樹范例2class nodefrie nd class btree;/二叉樹類的友元類public:node(char initdata=0,int initdeep=0,node *initl=NULL,node *initr=NULL,n

45、 ode *in itf=NULL, node *initn=N ULL);no de() ;protected:char data;二叉樹結(jié)點中的數(shù)據(jù)，此處定義為字符int deep;設(shè)置二叉樹結(jié)點的深度n ode *lchild; 左兒子node *rchild; / 右兒子node *father; /父親結(jié)點n ode *n ext;/用單鏈表處理所有結(jié)點時指向下一個結(jié)點;no de: no de(char in itdata,i nt in itdeep ,node *in itl, node *in itr, node *initf,node *in it n)data=in it

46、data;deep=in itdeep;lchild=i nitl;rchild=in itr;father=i nitf;n ext=in it n;class stackdata 創(chuàng)建一個stackdata類，在非遞歸遍歷算法中需要friend class btree;private:node *li nk; int flag;public:stackdata() ; stackdata() ;class btree /創(chuàng)建一個二叉樹類 private:char btreedataMaxsize; char an swer;node *root;node *workinp,*linkrea

47、r; int btreeco unt;bool firstbracket; countnow; leafc ount;coun tall;son deep;int/廣義表字符數(shù)組/用于回答菜單選項/指向根結(jié)點位置的指針/定義一個工作指針，尾部指針/結(jié)點個數(shù)計數(shù)器顯示廣義表時處理第一個括號，為1是,每一次需要使用計數(shù)器時臨時保存該值變成0就不是了intintintpublic:btree( node *in itrootp);btree()root=NULL;firstbracket=1;coun tall=0;btreeco un t=0;btree() ;void in itfirstbra

48、cket();/創(chuàng)建兒子結(jié)點時保存當(dāng)前深度/遞歸函數(shù)內(nèi)部統(tǒng)計結(jié)點個數(shù)/二叉樹統(tǒng)計后的結(jié)點個數(shù)把第一個括號標(biāo)志位恢復(fù)成1為默認(rèn)數(shù)據(jù)，2為鍵盤輸入returni nfo createroot();void visit (node *searchp);void showbtreedata();int rgetco unt(node *searchp);int getco un t();retur ninfo cha ngework in pp();retur ninfo findno de(); returninfo addchild();retur ninfo delete no de();ret

49、urni nfo get in formati on();returninfo createbtree(int choice); / 根據(jù)廣義表字符串生成二叉樹，choice=1/建立樹根函數(shù)/訪問當(dāng)前結(jié)點數(shù)據(jù)域/在主界面中顯示當(dāng)前工作數(shù)組/遞歸統(tǒng)計二叉樹中的結(jié)點個數(shù)/記錄二叉樹中的結(jié)點個數(shù)/將工作指針指向左兒子、右兒子或者父親/查找結(jié)點/增加左兒子或者右兒子刪除結(jié)點/獲取二叉樹結(jié)點和葉子信息returninfo gliststravel(node *searchp);/ 以廣義表 glists 表示法輸出二叉樹 returni nfo in de nttravel( node *search

50、p);/ 以凹入 in de nt 表示法輸出二叉樹 returninfo preorder (node *searchp);/ 遞歸先根遍歷retur ninfo ino rder returni nfo postorder returni nfo n rpreorder retur ninfo nrino rder(n ode *searchp);遞歸中根遍歷 (n ode *searchp);遞歸后根遍歷 (n ode *searchp);非遞歸先根遍歷 (n ode *searchp);非遞歸中根遍歷returninfo nrpostorder (node *searchp); 非遞歸后根遍歷returni nfo levelorder(node *searchp); 層次遍歷;returni nfo btree:preorder( node *se