數(shù)組和廣義表

1、邢振祥計算機應(yīng)用教研室7數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)第1章緒論本章討論的是數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，為鞏固理論知識的學(xué)習(xí)，本章的實驗內(nèi)容針對最基本的數(shù)據(jù)結(jié)構(gòu)一一數(shù)組，以及基于數(shù)組的簡單算法， 實現(xiàn)程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)的自然銜接，從數(shù)據(jù)結(jié)構(gòu)的角度重新思考如何進(jìn)行程序設(shè)計，從而提升程序設(shè)計乃至算法設(shè)計的能力。1.1實驗的一般步驟1.1.1概述數(shù)據(jù)結(jié)構(gòu)是一門實踐性很強的課程，只靠讀書和做習(xí)題是不能提高實踐能力的，尤其 是在數(shù)據(jù)結(jié)構(gòu)中要解決的問題更接近于實際。數(shù)據(jù)結(jié)構(gòu)的實驗是對學(xué)生的一種全面的綜合 訓(xùn)練，與程序設(shè)計語言課程中的實驗不同，數(shù)據(jù)結(jié)構(gòu)課程中的實驗多屬創(chuàng)造性的活動，需 要學(xué)生自己進(jìn)行問題分析、進(jìn)行數(shù)據(jù)結(jié)

2、構(gòu)和算法的設(shè)計、再上機調(diào)試和測試程序。數(shù)據(jù)結(jié) 構(gòu)的實驗是一種自主性很強的學(xué)習(xí)過程，其教學(xué)目的主要有兩個： 深化理解和掌握書本上的理論知識，將書本上的知識變“活”；理論和實踐相結(jié)合，使學(xué)生學(xué)會如何把書本上有關(guān)數(shù)據(jù)結(jié)構(gòu)和算法的知識用于解決實際問題，培養(yǎng)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用能力和軟件工程所 需要的實踐能力。為了達(dá)到上述目的，本書安排了如下三類實驗： 驗證實驗：其主要內(nèi)容是將書上的重要數(shù)據(jù)結(jié)構(gòu)上機實現(xiàn)，深化理解和掌握理論 知識，這部分的實驗不需要學(xué)生自己設(shè)計，只需將給定的方案實現(xiàn)即可；設(shè)計實驗：其主要內(nèi)容是針對具體問題，應(yīng)用某一個知識點，自己設(shè)計方案，并 上機實現(xiàn)，目的是培養(yǎng)學(xué)生對數(shù)據(jù)結(jié)構(gòu)的簡單應(yīng)用能力；綜

3、合實驗：其主要內(nèi)容是針對具體問題，應(yīng)用某幾個知識點，自己設(shè)計方案，并 上機實現(xiàn)，目的是培養(yǎng)學(xué)生對數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用能力。在驗證實驗中，由實驗?zāi)康摹嶒瀮?nèi)容、實現(xiàn)提示和實驗程序等四部分組成，其中實 驗?zāi)康拿鞔_了該實驗要學(xué)生掌握哪些知識點；實驗內(nèi)容規(guī)定了實驗的具體任務(wù)；實現(xiàn)提示 給出了數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計方法；實驗程序給出了實驗的范例程序，并且在主教材的隨 書光盤中有該實驗涉及到的數(shù)據(jù)結(jié)構(gòu)的全部實現(xiàn)。在驗證實驗中，不要求但鼓勵學(xué)生在完 成實驗任務(wù)的基礎(chǔ)上，對該實驗涉及的數(shù)據(jù)結(jié)構(gòu)的其他實現(xiàn)方法進(jìn)行探索。在設(shè)計實驗和綜合實驗中，由問題描述、基本要求、設(shè)計思想、思考題等四部分組成,其中問題描述是為學(xué)生建

4、立問題的背景環(huán)境，指明“問題是什么”；基本要求是對問題的 實現(xiàn)進(jìn)行基本規(guī)范，保證預(yù)定的訓(xùn)練意圖，使某些難點和重點不會被繞過去，而且也便于 教學(xué)檢查；設(shè)計思想給出了設(shè)計數(shù)據(jù)結(jié)構(gòu)和算法的主要思路；思考題引導(dǎo)學(xué)生在做完實驗 后進(jìn)行總結(jié)和擴充。雖然在設(shè)計實驗和綜合實驗中都給出了一定的設(shè)計方案，但是，學(xué)生不應(yīng)拘泥于這些 分析和設(shè)計，要盡量發(fā)揮想象力和創(chuàng)造力。對于一個實際問題，每個人可能會有不同的解 決辦法，本書給出的范例方案， 只是希望把學(xué)生的思路引入正軌，提出了思考問題的方法,但是不希望限制學(xué)生的思維，鼓勵學(xué)生自己設(shè)計解決方案。1.1.2驗證實驗的一般步驟驗證實驗安排的內(nèi)容在書上都能找到具體的實現(xiàn)方法

5、，并且在主教材的隨書光盤中也 都有相應(yīng)的程序?qū)崿F(xiàn)。這些驗證實驗是學(xué)生在學(xué)習(xí)完一種數(shù)據(jù)結(jié)構(gòu)后進(jìn)行的，對于深化理 解和掌握相應(yīng)數(shù)據(jù)結(jié)構(gòu)具有很重要的意義。1. 預(yù)備知識的學(xué)習(xí)由于篇幅所限，本書沒有整理驗證實驗所用到的預(yù)備知識，但主教材中的相關(guān)內(nèi)容已 經(jīng)敘述得很清楚了，需要學(xué)生在實驗前復(fù)習(xí)實驗所用的預(yù)備知識。這需要學(xué)生有自主的學(xué) 習(xí)意識和整理知識的能力。2. 上機前的準(zhǔn)備將實現(xiàn)提示中給出的數(shù)據(jù)類型和算法轉(zhuǎn)換為對應(yīng)的程序，并進(jìn)行靜態(tài)檢查，盡量減少 語法錯誤和邏輯錯誤。很多學(xué)生在上機時只帶一本數(shù)據(jù)結(jié)構(gòu)書或?qū)嶒炛笇?dǎo)書，而書上只有算法設(shè)計而沒有實 驗程序，于是就直接在鍵盤上輸入程序，結(jié)果不僅程序的輸入速度慢，

6、而且編譯后出現(xiàn)很 多錯誤。上機前的充分準(zhǔn)備能高效利用機時，在有限的時間內(nèi)完成更多的實驗內(nèi)容。3. 上機調(diào)試和測試程序調(diào)試程序是一個辛苦但充滿樂趣的過程，也是培養(yǎng)程序員素質(zhì)的一個重要環(huán)節(jié)。很多 學(xué)生都有這樣的經(jīng)歷：化了好長時間去調(diào)試程序，錯誤卻越改越多。究其原因，一方面， 是對調(diào)試工具不熟悉，出現(xiàn)了錯誤提示卻不知道這種錯誤是如何產(chǎn)生的；另一方面，沒有 認(rèn)識到努力預(yù)先避免錯誤的重要性，也就是對程序進(jìn)行靜態(tài)檢查。對程序進(jìn)行測試，首先需要設(shè)計測試數(shù)據(jù)。 在數(shù)據(jù)結(jié)構(gòu)中測試數(shù)據(jù)需要考慮兩種情況： 一般情況：例如循環(huán)的中間數(shù)據(jù)、隨機產(chǎn)生的數(shù)據(jù)等；特殊情況：例如循環(huán)的邊界條件、數(shù)據(jù)結(jié)構(gòu)的邊界條件等。4. 實驗

7、報告在實驗后要總結(jié)和整理實驗報告，實驗報告的一般格式請參見附錄一。1.1.3設(shè)計實驗和綜合實驗的一般步驟設(shè)計實驗和綜合實驗的自主性比較強，涉及到的知識點也比較多，可以在課程設(shè)計中 完成，設(shè)計實驗推薦單人完成，綜合實驗推薦多人完成，主要目的是為了培養(yǎng)數(shù)據(jù)結(jié)構(gòu)的 應(yīng)用能力、軟件工程的規(guī)范訓(xùn)練、團(tuán)隊精神和良好的科學(xué)作風(fēng)。1. 問題分析在設(shè)計實驗和綜合實驗中的問題描述通常都很簡潔，因此，首先要充分理解問題，明 確問題要求做什么，限制條件是什么，也就是對所需完成的任務(wù)做出明確的描述。例如： 輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍以及輸入的形式; 哪些屬于非法輸入，等等。在問題分

8、析時還應(yīng)該準(zhǔn)備好測試數(shù)據(jù)。2. 概要設(shè)計概要設(shè)計是對問題描述中涉及到的數(shù)據(jù)定義抽象數(shù)據(jù)類型，設(shè)計數(shù)據(jù)結(jié)構(gòu)，設(shè)計算法 的偽代碼描述。在這個過程中，要綜合考慮系統(tǒng)的功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單， 抽象數(shù)據(jù)類型盡可能做到數(shù)據(jù)封閉，基本操作的說明盡可能明確。而不必過早地考慮存儲 結(jié)構(gòu)，不必過早地考慮語言的實現(xiàn)細(xì)節(jié)，不必過早地表述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。3. 詳細(xì)設(shè)計在詳細(xì)設(shè)計階段，需要設(shè)計具體的存儲結(jié)構(gòu)（即用C+描述抽象數(shù)據(jù)類型對應(yīng)的類）以及算法所需的輔助數(shù)據(jù)結(jié)構(gòu)，算法在偽代碼的基礎(chǔ)上要考慮細(xì)節(jié)問題并用C+描述。此外，還要設(shè)計一定的用戶界面。數(shù)據(jù)結(jié)構(gòu)課程實驗的主要目的是為了培養(yǎng)數(shù)據(jù)結(jié)構(gòu) 的應(yīng)用能

9、力，因此在實驗中不要求圖形界面，只需要在屏幕上提示用戶每一步操作的輸入、 將結(jié)果輸出即可。4. 編碼實現(xiàn)和靜態(tài)檢查將詳細(xì)設(shè)計階段的結(jié)果進(jìn)一步優(yōu)化為C+程序，并做靜態(tài)檢查。很多初學(xué)者在編寫程序后都有這樣的心態(tài)：確信自己的程序是正確的，認(rèn)為上機前的 任務(wù)已經(jīng)完成，檢查錯誤是計算機的事。這種心態(tài)是極為有害的，這樣的上機調(diào)試效率是 極低的。事實上，即使有幾十年經(jīng)驗的高級軟件工程師，也經(jīng)常利用靜態(tài)檢查來查找程序 中的錯誤。5. 上機調(diào)試和測試程序掌握調(diào)試工具，設(shè)計測試數(shù)據(jù)，上機調(diào)試和測試程序。調(diào)試正確后，認(rèn)真整理源程序和注釋，給出帶有完整注釋且格式良好的源程序清單和結(jié)果。6. 總結(jié)并整理實驗報告在實驗后

10、要總結(jié)和整理課程設(shè)計報告，課程設(shè)計報告的一般格式請參見附錄二。1.2設(shè)計實驗1.2.1在數(shù)組中求最小值1. 問題描述已知一個數(shù)組，求該數(shù)組中值最小的元素。2. 基本要求 對于由確定元素組成的數(shù)組（即在程序中直接賦值），實現(xiàn)求最小值; 隨機生成數(shù)組元素（即由機器生成隨機數(shù)），實現(xiàn)求最小值；分析算法的時間性能。3. 設(shè)計思想我們都知道“打擂臺”這個名詞，它的意思是說，如果有若干人比武，先有一個人站在臺上，再上去一個人與其交手，敗者下臺，勝者留在臺上。如此下去，直到所有人都上 臺比過為止，最后留在臺上的就是勝者。按照這個思路，首先把數(shù)組a0的值賦給變量 min，min就是開始時的擂主，然后讓下一個元

11、素與它比較，將二者中值較小者保存在min中，直到數(shù)組中所有元素都比完為止。最后min中保存的就是數(shù)組中所有元素的最小值。4. 算法描述下面給出具體的在以個整型數(shù)組中求最小值的算法。在數(shù)組中求最小值算法int ArrayMin (int a , int n )min=a0;for (i=1; i<n; i+ )if ( ai<min ) min=ai; return mi n;【思考題】在數(shù)組中求最大值和最小值，要求算法有較好的時間性能； 在數(shù)組中求最大值和次最大值，要求算法有較好的時間性能。#數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)1.2.2統(tǒng)計候選人得票1. 問題描述設(shè)有n個候選人參加選舉，統(tǒng)計每個候選

12、人最后的得票情況。2. 基本要求以數(shù)組作為存儲結(jié)構(gòu)； 設(shè)計統(tǒng)計得票算法，將最后的得票情況統(tǒng)計并輸出。3. 設(shè)計思想可以將每個候選人設(shè)計為一個結(jié)構(gòu)類型，包括名字和得票數(shù)，將n個候選人組成一個結(jié)構(gòu)數(shù)組，其存儲結(jié)構(gòu)定義如下：con st int n=10;/假設(shè)有10個人參加選舉struct Pers onchar *n ame;int count; Leader n;可以從鍵盤依次輸入選舉情況，每次輸入一個人的名字，將輸入的名字與結(jié)構(gòu)數(shù)組 Leader進(jìn)行比較，將對應(yīng)候選人的得票數(shù)加1。4. 算法描述票統(tǒng)計算法void Elect ion (Pers on Leader , i nt n )cin

13、»n ame;while ( name!="#")for (i=0; i<n; i+ )if (strcmp( L, name) =0) Leaderi.count+; cin»n ame;for (i=0; i<n; i+ )cout<<L<<"得票數(shù)為："<<Leaderi.count<<endl;【思考題】將該問題用C+中的類實現(xiàn)。11數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)1.3綜合實驗10.3.1順序查找最好、最壞和平均的時間性能1. 問題描述在

14、一維整型數(shù)組 A n中順序查找與給定值相等的元素。2. 基本要求 只考慮查找成功的情況； 求出最好、最壞、平均情況下待查值與數(shù)組元素的實際比較次數(shù)； 總結(jié)實驗結(jié)果，給出結(jié)論。3. 設(shè)計思想所謂順序查找就是從數(shù)組的第一個元素開始，依次比較每一個元素與待查值是否相等。為了測算待查值與數(shù)組元素的實際比較次數(shù)，需要在算法中設(shè)置計算比較次數(shù)的累加器 count,算法結(jié)束后輸出其值。4. 算法描述順序查找算法int Find (int A , int n, int k )coun t=0;for (i=0; i<n; i+ )if (+count && Ai= =k ) break;

15、cout<<"比較次數(shù)為"<<count<<endl;return i;【思考題】如果考慮查找失敗的情況，應(yīng)如何修改算法？ 對于排序問題設(shè)計一個算法，并分析最好、最壞和平均的時間性能。1.3.2比較解決相同問題的不同算法的時間性能1. 問題描述在一個數(shù)組中確定第k小的元素(假定數(shù)組元素可以進(jìn)行比較)。2. 基本要求采用模板函數(shù)實現(xiàn)；至少采用兩種方法求解；分析不同算法的時間性能。3.設(shè)計思想方法一：采用起泡排序，將數(shù)組中的所有元素排序，然后輸出第k個元素。起泡排序的基本思想是：兩兩比較相鄰元素，如果反序則交換，直到全部元素都排好序為止。起泡

16、排序算法template <class T>T BubbleSort (T r , int n, T k )for (i=1; i<n; i +)for (j=0; j<n - i; j+ )if( rj>r j+1)j <-> rj+1;交換元素return rk -1;/第k小元素在數(shù)組中下標(biāo)為 k-1的位置該算法的時間性能是O(n2)。|方法二：采用選擇排序，當(dāng)找出第k小元素后，不再進(jìn)行排序過程。選擇排序的基本思想是：第i趟排序通過n-i次關(guān)鍵碼的比較，在 n-i+1 (1 < i w n-1)個記錄中選取關(guān)鍵碼 最小的記錄，并和第i個記錄

17、交換作為有序序列的第i個記錄。選擇排序算法template <class T>T SelectSort( T r , int n, T k )for (i=0; i<k; i+ )對n個元素進(jìn)行k趟簡單選擇排序in dex=i;for (j=i+1; j< n; j+ )/ 找最小元素if (rj<rindex ) index=j;if (index!=i) rj <-> rindex;/交換元素該算法的時間性能是O(kx n)。return rk -1;第k小元素在數(shù)組中下標(biāo)為k-1的位置【思考題】你還能設(shè)計出其他算法嗎？自行設(shè)計另外一種方法，并分析

18、其時間性能。13數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)第2章線性表線性表是最簡單、最常用的基本數(shù)據(jù)結(jié)構(gòu)，在實際問題中有著廣泛的應(yīng) 用。通過本章的驗證實驗，鞏固對線性表邏輯結(jié)構(gòu)的理解，掌握線性表的存 儲結(jié)構(gòu)及基本操作的實現(xiàn)，為應(yīng)用線性表解決實際問題奠定良好的基礎(chǔ)。通 過本章的設(shè)計實驗和綜合實驗，進(jìn)一步培養(yǎng)以線性表作為數(shù)據(jù)結(jié)構(gòu)解決實際 問題的應(yīng)用能力。2.1驗證實驗2.1.1順序表操作驗證1.實驗?zāi)康恼莆站€性表的順序存儲結(jié)構(gòu)；驗證順序表及其基本操作的實現(xiàn); 掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。2. 實驗內(nèi)容 建立含有若干個元素的順序表；對已建立的順序表實現(xiàn)插入、刪除、查找等基本操作。3. 實現(xiàn)提示首先定義順序表的數(shù)

19、據(jù)類型一一順序表類SeqList，包括題目要求的插入、刪除、查找等基本操作，為便于查看操作結(jié)果，設(shè)計一個輸出函數(shù)依次輸出順序表的元素。const int MaxSize =10;template <class T>定義模板類 SeqListclass SeqListpublic:SeqList( ) length=0;無參構(gòu)造函數(shù)SeqList(T a , int n );有參構(gòu)造函數(shù)void Insert( int i, T x ); 在線性表中第i個位置插入值為x的元素T Delete(int i);刪除線性表的第i個元素int Locate (T x );/按值查找，求線性表

20、中值為x的元素序號void PrintList ( ) ;/遍歷線性表，按序號依次輸出各元素21數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)private:T dataMaxSize;/存放數(shù)據(jù)元素的數(shù)組in t le ngth;/線性表的長度；其次，建立含有n個數(shù)據(jù)元素的順序表，即設(shè)計構(gòu)造函數(shù)。算法如下:順序表有參構(gòu)造函數(shù) SeqListtemplate <class T>SeqList: SeqList (T a , int n )if (n>MaxSize ) throw "參數(shù)非法"for (i=0; i<n; i+ )datai=ai;len gth=n;最后，對建立

21、的順序表設(shè)計插入、刪除、查找等基本操作的算法。插入算法II順序表插入算法Inserttemplate <class T>void SeqList:lnsert (int i, T x )if (length>=MaxSize ) throw "上溢"if (i<1 | i>length+1 ) throw "位置"for ( j=length; j>=i; j -)dataj=dataj -1;/注意第j個元素存在數(shù)組下標(biāo)為 j-1處datai- 1=x; len gth+;刪除算法順序表刪除算法 Deletetemp

22、late <class T>T SeqList:Delete (int i)if (length=0) throw "下溢"if (i<1 | i>length ) throw "位置" x=datai -1;for (j=i; j<le ngth; j+ )dataj- 1=dataj;注意此處j已經(jīng)是元素所在的數(shù)組下標(biāo)length-;return x;查找算法templOthvclOss T> int SeqList:Locate (T x) i+1for (i=0; i<le ngth; i+ )if (

23、datai=x ) return i+1;下標(biāo)為i的元素等于x，返回其序號return 0;退出循環(huán)，說明查找失敗4.實驗程序/以下為頭函數(shù)，文件名為 SeqList.h#ifndef SeqList_H#defi ne SeqList_Hconst int MaxSize=100; /100只是示例性的數(shù)據(jù)，可以根據(jù)實際問題具體定義 template <class T>/定義模板類 SeqListclass SeqListpublic:SeqList( )le ngth=0; SeqList(T a , int n); void In sert(i nt i, T x); T D

24、elete(int i); int Locate(T x); void Prin tList();private:T dataMaxSize;int len gth;/無參構(gòu)造函數(shù)，創(chuàng)建一個空表/有參構(gòu)造函數(shù)/在線性表中第i個位置插入值為x的元素/刪除線性表的第i個元素/按值查找，求線性表中值為x的元素序號遍歷線性表，按序號依次輸出各元素/存放數(shù)據(jù)元素的數(shù)組/線性表的長度#en dif/以下為SeqList類中成員函數(shù)的定義部分，文件名為SeqList.cpp#in clude "SeqList.h" template <class T>SeqList<T

25、>: SeqList(T a , int n)if (n>MaxSize) throw "參數(shù)非法"for (i nt i=0; i<n; i+)datai=ai;len gth=n;template <class T>void SeqList<T>:I nsert(i nt i, T x) if (length>=MaxSize) throw "上溢”;if (i<1 | i>length+1) throw " 位置"for (int j=le ngth; j>=i; j_)d

26、ataj=dataj-1;/注意第j個元素存在數(shù)組下標(biāo)為j-1處datai-1=x;len gth+;template <class T>T SeqList<T>:Delete(int i)if (length=0) throw "下溢"if (i<1 | i>length) throw "位置"T x=datai-1;for (int j=i; j<le ngth; j+)dataj-1=dataj;/注意此處j已經(jīng)是元素所在的數(shù)組下標(biāo)len gth-;return x;template <class T

27、>int SeqList<T>:Locate(T x)for (in t i=0; i<le ngth; i+)i+1if (datai=x) return i+1 ;/下標(biāo)為i的元素等于x，返回其序號return 0;/退出循環(huán)，說明查找失敗template <class T>void SeqList<T>:Pri ntList()for (in t i=0; i<le ngth; i+) cout<<datai<<e ndl;/以下為主函數(shù)#i nclude<iostream.h>引用輸入輸出流庫函數(shù)

28、的頭文件#i nclude"SeqList.cpp"引用順序表的類聲明和定義void mai n()int r =1,2, 3, 4, 5;SeqList <in t> a(r, 5);cout<<"執(zhí)行插入操作前數(shù)據(jù)為："<<endl;a.Prin tList( );/輸出所有元素trya.I nsert(2,3);catch (char *s)cout<<s<<e ndl;cout<<"執(zhí)行插入操作后數(shù)據(jù)為："<<e ndl;a.Prin tLis

29、t( );/輸出所有元素cout<<"值為3的元素位置為:"cout<<a.Locate(3)<<endl;/查找元素3,并返回在單鏈表中位置cout<<"執(zhí)行刪除第一個元素操作，刪除前數(shù)據(jù)為："<<e ndl;a.Prin tList( );/輸出所有元素trya.Delete(1);/ 刪除元素 1catch (char *s)cout<<s<<e ndl;cout<<"刪除后數(shù)據(jù)為："<<e ndl;a.Prin tLis

30、t( );/輸出所有元素2.1.2單鏈表操作驗證1. 實驗?zāi)康恼莆站€性表的鏈接存儲結(jié)構(gòu)；驗證單鏈表及其基本操作的實現(xiàn)； 進(jìn)一步掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。2. 實驗內(nèi)容 用頭插法(或尾插法)建立帶頭結(jié)點的單鏈表；對已建立的單鏈表實現(xiàn)插入、刪除、查找等基本操作。3. 實現(xiàn)提示首先，將單鏈表中的結(jié)點定義為如下結(jié)構(gòu)類型：template <class T>struct NodeT data;Node<T> *n ext;其次，定義單鏈表的數(shù)據(jù)類型一一單鏈表類LinkList，包括題目要求的插入、刪除、查找等基本操作，為便于查看操作結(jié)果，設(shè)計一個輸出函數(shù)依次輸出單鏈

31、表的元素。template <class T>class Lin kListpublic:LinkList (T a , int n ) ; /建立有n個元素的單鏈表LinkList ();析構(gòu)函數(shù)void Insert (int i, T x );/在單鏈表中第i個位置插入元素值為 x的結(jié)點T Delete (int i);/在單鏈表中刪除第i個結(jié)點int Locate (T x);/求單鏈表中值為x的元素序號void PrintList ( ) ;/遍歷單鏈表，按序號依次輸出各元素private:Node<T> *first;單鏈表的頭指針;再次，設(shè)計單鏈表類Lin

32、kList的構(gòu)造函數(shù)和析構(gòu)函數(shù)。 用頭插法或尾插法建立單鏈表。頭插法建立單鏈表的算法如下：頭插法 建立單鏈表template <class T>LinkList: LinkList (T a , int n )first =new Node<T>first-> next=NULL;初始化一個空鏈表for (i=0; i<n; i+ )s=new Node<T> s->data=ai;為每個數(shù)組元素建立一個結(jié)點s-> next=first -> next;/插入到頭結(jié)點之后first-> next=s; 析構(gòu)函數(shù)用于釋放單鏈

33、表中所有結(jié)點，算法如下:單鏈表的析構(gòu)函數(shù)算法LinkListtemplate <class T>Lin kList: Lin kList ()p=first;/工作指針p初始化while ( p)釋放單鏈表的每一個結(jié)點的存儲空間q=p;暫存被釋放結(jié)點p=p-> next; 工作指針p指向被釋放結(jié)點的下一個結(jié)點，使單鏈表不斷開 delete q;最后，對所建立的單鏈表設(shè)計插入、刪除、查找等基本操作的算法。 插入算法單鏈表插入算法Insert 1 template <class T>void LinkList:lnsert (int i, T x )p=first;

34、j=0;/工作指針p初始化while ( p && j<i -1)p=p-> next;/工作指針p后移j+；if (!p) throw "位置"else s=new Node<T> s-> data=x; /向內(nèi)存申請一個結(jié)點 s,其數(shù)據(jù)域為x &> next=p->next;/將結(jié)點s插入到結(jié)點 p之后p-> next=s;刪除算法單鏈表的刪除算法 Delete template <class T>T LinkList:Delete (int i)p=first ; j=0;工作指針p初

35、始化while ( p && j<i -1)/查找第 i-1 個結(jié)點p=p-> next;j+;if (!p | !p-> next) throw "位置"/結(jié)點p不存在或結(jié)點p的后繼結(jié)點不存在 else q=p-> next; x=q -> data; 暫存被刪結(jié)點p-> next=q -> next;摘鏈delete q;return x;查找算法23數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)單鏈表查找算法Locatetemplate <class T>int LinkList: Locate (T x)p=first - &

36、gt;n ext; j=1;while ( p && p -> data!=x)p=p-> next;/工作指針p后移j+；if ( p) return j; else return 0;4.實驗程序/以下為頭函數(shù)，文件名為LinkList.h#ifndef Lin kList_H#defi ne Lin kList_Htemplate <class T> struct NodeT data;Node<T> *next;此處<T>也可以省略;template <class T>class Lin kListpublic

37、:LinkList(T a , int n);/建立有n個元素的單鏈表Li nkList( );/ 析構(gòu)函數(shù)void Insert(int i, T x);在單鏈表中第i個位置插入元素值為x的結(jié)點T Delete(int i);/在單鏈表中刪除第i個結(jié)點int Locate(T x);求單鏈表中值為x的元素序號void Prin tList();遍歷單鏈表，按序號依次輸出各元素private:Node<T> *first;/單鏈表的頭指針;#en dif/以下為頭函數(shù) LinkList.h中LinkList類的成員函數(shù)的定義，文件名為LinkList.cpp#i nclude&qu

38、ot;L in kList.h"template <class T>LinkList<T>: LinkList(T a , int n)first=new Node<T>#數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)first-next=NULL;/初始化一個空鏈表for (i nt i=0; i<n; i+)Node<T> *s;s=new Node<T> s->data=ai;/為每個數(shù)組元素建立一個結(jié)點s-> next=first-> next;插入到頭結(jié)點之后first->n ext=s;template <

39、class T>Lin kList<T>: Li nkList ()Node<T> *p, *q;p=first;/工作指針p初始化while (p)II釋放單鏈表的每一個結(jié)點的存儲空間q=p;暫存被釋放結(jié)點p=p-> next; 工作指針p指向被釋放結(jié)點的下一個結(jié)點，使單鏈表不斷開 delete q;template <class T>void Lin kList<T>:l nsert(i nt i, T x)Node<T> *p; int j;p=first ; j=0; II工作指針p初始化while (p &

40、;& j<i-1)p=p->next;II工作指針p后移j+;if (!p) throw "位置"else Node<T> *s;s=new Node<T>s->data=x;II向內(nèi)存申請一個結(jié)點s,其數(shù)據(jù)域為 xs->next=p->next;將結(jié)點s插入到結(jié)點 p之后p_>n ext=s;template <class T>T LinkList<T>:Delete(int i)Node<T> *p; int j;#數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)p=first ; j=0;/工作指

41、針p初始化while (p && j<i-1)/查找第 i-1 個結(jié)點p=p->n ext;j+；p的后繼結(jié)點不存在if仲|(zhì) !p->next) throw "位置"/結(jié)點p不存在或結(jié)點 else Node<T> *q; int x;q=p-> next; x=q->data;暫存被刪結(jié)點p->n ext=q->n ext;摘鏈delete q;return x;template <class T> int Lin kList<T>:Locate(T x) Node<T>

42、; *p; int j; p=first->n ext; j=1; while (p && p->data!=x) p=p->n ext;j+;if (p) return j;else return 0;template <class T>void Li nkList<T>:Pri ntList()Node<T> *p;p=first->n ext;while (p)cout<<p->data<<e ndl;p=p->n ext;/以下為主函數(shù)#i nclude<iostrea

43、m.h>/引用輸入輸出流庫函數(shù)的頭文件#in clude"Li nkList.cpp"/引用單鏈表類的聲明和定義void mai n()int r =1,2, 3, 4, 5;Li nkList <in t> a(r, 5);cout<<"執(zhí)行插入操作前數(shù)據(jù)為："<<e ndl;a.Prin tList();顯示鏈表中所有元素trya.Insert(2, 5);catch (char *s)cout<<s<<e ndl;cout<<"執(zhí)行插入操作后數(shù)據(jù)為："

44、<<e ndl;a.Prin tList();顯示鏈表中所有元素cout<<"值為5的元素位置為:"cout<<a.Locate(5)<<endl;/查找元素5,并返回在單鏈表中位置cout<<"執(zhí)行刪除操作前數(shù)據(jù)為："<<e ndl;a.Prin tList();顯示鏈表中所有元素trya.Delete(1);/刪除元素 4catch (char *s)cout<<s<<e ndl;cout<<"執(zhí)行刪除操作后數(shù)據(jù)為："<

45、;<e ndl;a.Prin tList();顯示鏈表中所有元素【思考題】為單鏈表的結(jié)點設(shè)計一個結(jié)點類，重新實現(xiàn)單鏈表基本操作的驗證。2.2設(shè)計實驗 2.2.1數(shù)組的循環(huán)移位1. 問題描述對于一個給定的整型數(shù)組循環(huán)右移i位。2. 基本要求 在原數(shù)組中實現(xiàn)循環(huán)右移，不另外申請空間;時間性能盡可能好； 分析算法的時間復(fù)雜度。27數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)將這個問題看作是把數(shù)組 ab轉(zhuǎn)換成數(shù)組ba (a代表數(shù)組的前i個元素，b代表數(shù)組中 余下的n-i個元素)，先將a逆置得到arb,再將b逆置得到abr，最后將整個arbr逆置得到 (arbr)r=ba。設(shè)Reverse函數(shù)執(zhí)行將數(shù)組元素逆置的操作，對ab

46、cdefgh向左循環(huán)移動 3個位置的過程如下：Reverse(0, i -1);得到cbadefghReverse(i, n-1);得到cbahgfedReverse(O, n-1);/得到defghabc具體分析過程請參見主教材第一章思想火花。4.算法描述循環(huán)右移算法void Con verse (int A , i nt n, int i )Reverse( A, 0, i -1);/前 i 個元素逆置Reverse( A, i, n -1);/后 n-i 個元素逆置Reverse( A, 0, n -1);/整個數(shù)組逆置void Reverse(int A , int from, int

47、 to )/將數(shù)組 A 中元素從 from 到 to 逆置for (i=0; i< (to-from+1 )/2; i+ )Afrom+i <-> Ato - i;/交換元素【思考題】你還有其他解決方法嗎？請設(shè)計算法并上機實現(xiàn)。2.2.2集合的交、并和差運算的實現(xiàn)1. 問題描述用有序單鏈表表示集合，實現(xiàn)集合的交、并和差運算。2. 基本要求 對集合中的元素，用有序單鏈表進(jìn)行存儲；實現(xiàn)交、并、差運算時，不另外申請存儲空間； 充分利用單鏈表的有序性，算法有較好的時間性能。3. 設(shè)計思想首先，建立兩個帶頭結(jié)點的有序單鏈表表示集合A和B。單鏈表的結(jié)點結(jié)構(gòu)和建立算法請參見2.1.2，需要

48、注意的是：利用頭插法建立有序單鏈表，實參數(shù)組應(yīng)該是降序排列。其次，根據(jù)集合的運算規(guī)則，利用單鏈表的有序性，設(shè)計交、并和差運算。 根據(jù)集合的運算規(guī)則，集合 A B中包含所有既屬于集合 A又屬于集合B的元素。 因此，需查找單鏈表 A和B中的相同元素并保留在單鏈表 A中。算法如下：Li.A 厶、丄求集合 的交集算法void Interest ( Node *A, Node *B )/A、B分別是兩個單鏈表的頭指針，最后的結(jié)果在單鏈表pre=A; p=A -> next; q=B -> next;A中29數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)根據(jù)集合的運算規(guī)則，集合 A B中包含所有或?qū)儆诩?A或?qū)儆诩螧的

49、元素。 因此，對單鏈表 B中的每個元素X,在單鏈表A中進(jìn)行查找，若存在和 x不相同的元素， 則將該結(jié)點插入到單鏈表 A中。算法請參照求集合的交集自行設(shè)計。 根據(jù)集合的運算規(guī)則，集合 A- B中包含所有屬于集合 A而不屬于集合B的元素。 因此，對單鏈表 B中的每個元素X，在單鏈表A中進(jìn)行查找，若存在和 x相同的結(jié)點，則 將該結(jié)點從單鏈表 A中刪除。算法請參照求集合的交集自行設(shè)計?！舅伎碱}】如果表示集合的單鏈表是無序的，應(yīng)如何實現(xiàn)集合的交、并和差運算？2.3綜合實驗 2.3.1約瑟夫環(huán)問題1. 問題描述設(shè)有編號為1, 2, ,n的n(n>0)個人圍成一個圈，每個人持有一個密碼 m,從第1個人

50、開始報數(shù)，報到 m時停止報數(shù)，報 m的人出圈，再從他的下一個人起重新報數(shù)，報 到m時停止報數(shù)，報 m的出圈，如此下去，直到所有人全部出圈為止。當(dāng)任意給定 n和m后，設(shè)計算法求 n個人出圈的次序。2. 基本要求 建立模型，確定存儲結(jié)構(gòu)； 對任意n個人，密碼為 m,實現(xiàn)約瑟夫環(huán)問題； 出圈的順序可以依次輸出，也可以用一個數(shù)組存儲。首先，設(shè)計實現(xiàn)約瑟夫環(huán)問題的存儲結(jié)構(gòu)。由于約瑟夫環(huán)問題本身具有循環(huán)性質(zhì)，考 慮采用循環(huán)鏈表，為了統(tǒng)一對表中任意結(jié)點的操作，循環(huán)鏈表不帶頭結(jié)點。將循環(huán)鏈表的 結(jié)點定義為如下結(jié)構(gòu)類型：struct Nodeint data; 編號Node *n ext;；其次，建立一個不帶頭

51、結(jié)點的循環(huán)鏈表并由頭指針first指示。具體算法請參見2.1.2自行設(shè)計。最后，設(shè)計約瑟夫環(huán)問題的算法。下面給出偽代碼描述，操作示意圖如圖2-1所示。1. 工作指針pre和p初始化，計數(shù)器count初始化；pre=first; p=first->next; count=2;/為便于刪除操作，從 2開始計數(shù)2. 循環(huán)直到p=pre2.1 如果 count=m，貝U2.1.1輸出結(jié)點p；2.1.2刪除結(jié)點p；2.1.3計數(shù)器count清零，重新開始計數(shù)；2.2否則，執(zhí)行2.2.1工作指針pre和p后移；2.2.2計數(shù)器增1；3.退出循環(huán)，鏈表中只剩下一個結(jié)點p,輸出結(jié)點p后將結(jié)點p刪除;co

52、un t=2(a) 一般情況(b)只剩下一個結(jié)點的特殊情況 圖2-1約瑟夫環(huán)問題存儲示意圖#數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)#數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)【思考題】采用順序存儲結(jié)構(gòu)如何實現(xiàn)約瑟夫環(huán)問題？如果每個人持有的密碼不同，應(yīng)如何實現(xiàn)約瑟夫環(huán)問題?31數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)2.3.2 一元多項式相加1. 問題描述已知 A(x) =a°+aix+a2X2+anxn和 B(x) =b°+bix+b2x2+bmxm，并且在 A(x)和 B(x)中指數(shù)相差很多，求 A(x)=A(x) + B( x)。2. 基本要求 設(shè)計存儲結(jié)構(gòu)表示一元多項式；設(shè)計算法實現(xiàn)一元多項式相加； 分析算法的時間復(fù)雜度和空間復(fù)雜度。3.

53、 設(shè)計思想一元多項式求和實質(zhì)上是合并同類項的過程，其運算規(guī)則為：若兩項的指數(shù)相等，則系數(shù)相加； 若兩項的指數(shù)不等，則將兩項加在結(jié)果中。一元多項式A(x) =ao+aix+a2x2+ +anxn由n+1個系數(shù)唯一確定，因此，可以用一個 線性表(a。，ai, a2,務(wù))來表示，每一項的指數(shù)i隱含在其系數(shù)ai的序號里。但是，當(dāng)多項式的指數(shù)很高且變化很大時，在表示多項式的線性表中就會存在很多零元素。一個 較好的存儲方法是只存非零元素，但是需要在存儲非零元素系數(shù)的同時存儲相應(yīng)的指數(shù)。 這樣，一個一元多項式的每一個非零項可由系數(shù)和指數(shù)唯一表示。由于兩個一元多項式相加后，會改變多項式的系數(shù)和指數(shù)，因此采用順

54、序表不合適。 采用單鏈表存儲，則每一個非零項對應(yīng)單鏈表中的一個結(jié)點，且單鏈表應(yīng)按指數(shù)遞增有序 排列。結(jié)點結(jié)構(gòu)如圖 2-2所示。coefexpn ext圖2-2 一元多項式單鏈表的結(jié)點結(jié)構(gòu)其中，coef:系數(shù)域，存放非零項的系數(shù)；exp :指數(shù)域，存放非零項的指數(shù)；next :指針域，存放指向下一結(jié)點的指針。將兩個一元多項式用兩個單鏈表存儲后，如何實現(xiàn)二者相加呢？設(shè)兩個工作指針p和q,分別指向兩個單鏈表的開始結(jié)點。通過對結(jié)點p的指數(shù)域和結(jié)點q的指數(shù)域進(jìn)行比較進(jìn)行同類項合并，則出現(xiàn)下列三種情況： 若p->exp<q->exp，則結(jié)點p應(yīng)為結(jié)果中的一個結(jié)點； 若p->exp&

55、gt;q-> exp，則結(jié)點q應(yīng)為結(jié)果中的一個結(jié)點，將q插入到第一個鏈表中結(jié)點p之刖； 若p-> exp=q-> exp，則結(jié)點p與結(jié)點q為同類項，將q的系數(shù)加到p的系數(shù)上。若 相加結(jié)果不為0，則結(jié)點p應(yīng)為結(jié)果中的一個結(jié)點，同時刪除結(jié)點 q;若相加結(jié)果為0，則 表明結(jié)果中無此項，刪除結(jié)點 p和結(jié)點q；算法用偽代碼描述如下：J1.工作指針P、q初始化；ft/ 2. while （ p存在且q存在）執(zhí)行下列三種情形之一2.1如果p-> exp<q-> exp，則指針p后移;22 如果 p-> exp>q-> exp,則2.2.1將結(jié)點q插入到結(jié)

56、點p之前；2.2.2指針q指向原指結(jié)點的下一個結(jié)點；2.3 如果 p-> exp=q-> exp，則2.3.1 p-> coef =p-> coef+q->coef ； 2.3.2如果p-> coef =0，則執(zhí)行下列操作，否則，指針p后移;刪除結(jié)點p；使指針p指向它原指結(jié)點的下一個結(jié)點；2.3.3刪除結(jié)點q；2.3.4使指針q指向它原指結(jié)點的下一個結(jié)點；3. 如果q不為空，將結(jié)點q鏈接在第一個單鏈表的后面；【思考題】用順序表如何實現(xiàn)兩個多項式相加，設(shè)計算法并與單鏈表實現(xiàn)進(jìn)行比較。33數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)第3章棧、隊列和串本章的實驗內(nèi)容圍繞三種特殊線性表一一棧、隊列和串展開。棧和隊列廣泛應(yīng)用在各種軟件系統(tǒng)中，掌握棧和隊列的存儲結(jié)構(gòu)及基本操 作的實現(xiàn)是以棧和隊列作為數(shù)據(jù)結(jié)構(gòu)解決實際問題的基礎(chǔ)，尤其棧有很多經(jīng)典 應(yīng)用，深刻理解并