數(shù)組和廣義表

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

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

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

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

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

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

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

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

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

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

11、素與它比較，將二者中值較小者保存在min中，直到數(shù)組中所有元素都比完為止。最后min中保存的就是數(shù)組中所有元素的最小值。4. 算法描述下面給出具體的在以個(gè)整型數(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ù)組中求最大值和次最大值，要求算法有較好的時(shí)間性能。#數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)1.2.2統(tǒng)計(jì)候選人得票1. 問(wèn)題描述設(shè)有n個(gè)候選人參加選舉，統(tǒng)計(jì)每個(gè)候選

12、人最后的得票情況。2. 基本要求以數(shù)組作為存儲(chǔ)結(jié)構(gòu)； 設(shè)計(jì)統(tǒng)計(jì)得票算法，將最后的得票情況統(tǒng)計(jì)并輸出。3. 設(shè)計(jì)思想可以將每個(gè)候選人設(shè)計(jì)為一個(gè)結(jié)構(gòu)類型，包括名字和得票數(shù)，將n個(gè)候選人組成一個(gè)結(jié)構(gòu)數(shù)組，其存儲(chǔ)結(jié)構(gòu)定義如下：con st int n=10;/假設(shè)有10個(gè)人參加選舉struct Pers onchar *n ame;int count; Leader n;可以從鍵盤(pán)依次輸入選舉情況，每次輸入一個(gè)人的名字，將輸入的名字與結(jié)構(gòu)數(shù)組 Leader進(jìn)行比較，將對(duì)應(yīng)候選人的得票數(shù)加1。4. 算法描述票統(tǒng)計(jì)算法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;【思考題】將該問(wèn)題用C+中的類實(shí)現(xiàn)。11數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)1.3綜合實(shí)驗(yàn)10.3.1順序查找最好、最壞和平均的時(shí)間性能1. 問(wèn)題描述在

14、一維整型數(shù)組 A n中順序查找與給定值相等的元素。2. 基本要求 只考慮查找成功的情況； 求出最好、最壞、平均情況下待查值與數(shù)組元素的實(shí)際比較次數(shù)； 總結(jié)實(shí)驗(yàn)結(jié)果，給出結(jié)論。3. 設(shè)計(jì)思想所謂順序查找就是從數(shù)組的第一個(gè)元素開(kāi)始，依次比較每一個(gè)元素與待查值是否相等。為了測(cè)算待查值與數(shù)組元素的實(shí)際比較次數(shù)，需要在算法中設(shè)置計(jì)算比較次數(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)如何修改算法？ 對(duì)于排序問(wèn)題設(shè)計(jì)一個(gè)算法，并分析最好、最壞和平均的時(shí)間性能。1.3.2比較解決相同問(wèn)題的不同算法的時(shí)間性能1. 問(wèn)題描述在一個(gè)數(shù)組中確定第k小的元素(假定數(shù)組元素可以進(jìn)行比較)。2. 基本要求采用模板函數(shù)實(shí)現(xiàn)；至少采用兩種方法求解；分析不同算法的時(shí)間性能。3.設(shè)計(jì)思想方法一：采用起泡排序，將數(shù)組中的所有元素排序，然后輸出第k個(gè)元素。起泡排序的基本思想是：兩兩比較相鄰元素，如果反序則交換，直到全部元素都排好序?yàn)橹?。起?/p>

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的位置該算法的時(shí)間性能是O(n2)。|方法二：采用選擇排序，當(dāng)找出第k小元素后，不再進(jìn)行排序過(guò)程。選擇排序的基本思想是：第i趟排序通過(guò)n-i次關(guān)鍵碼的比較，在 n-i+1 (1 < i w n-1)個(gè)記錄中選取關(guān)鍵碼 最小的記錄，并和第i個(gè)記錄

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

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

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

20、中值為x的元素序號(hào)void PrintList ( ) ;/遍歷線性表，按序號(hào)依次輸出各元素21數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)private:T dataMaxSize;/存放數(shù)據(jù)元素的數(shù)組in t le ngth;/線性表的長(zhǎng)度；其次，建立含有n個(gè)數(shù)據(jù)元素的順序表，即設(shè)計(jì)構(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;最后，對(duì)建立

21、的順序表設(shè)計(jì)插入、刪除、查找等基本操作的算法。插入算法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個(gè)元素存在數(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，返回其序號(hào)return 0;退出循環(huán)，說(shuō)明查找失敗4.實(shí)驗(yàn)程序/以下為頭函數(shù)，文件名為 SeqList.h#ifndef SeqList_H#defi ne SeqList_Hconst int MaxSize=100; /100只是示例性的數(shù)據(jù)，可以根據(jù)實(shí)際問(wèn)題具體定義 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;/無(wú)參構(gòu)造函數(shù)，創(chuàng)建一個(gè)空表/有參構(gòu)造函數(shù)/在線性表中第i個(gè)位置插入值為x的元素/刪除線性表的第i個(gè)元素/按值查找，求線性表中值為x的元素序號(hào)遍歷線性表，按序號(hào)依次輸出各元素/存放數(shù)據(jù)元素的數(shù)組/線性表的長(zhǎng)度#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個(gè)元素存在數(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，返回其序號(hào)return 0;/退出循環(huán)，說(shuō)明查找失敗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>引用輸入輸出流庫(kù)函數(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í)行刪除第一個(gè)元素操作，刪除前數(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單鏈表操作驗(yàn)證1. 實(shí)驗(yàn)?zāi)康恼莆站€性表的鏈接存儲(chǔ)結(jié)構(gòu)；驗(yàn)證單鏈表及其基本操作的實(shí)現(xiàn)； 進(jìn)一步掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。2. 實(shí)驗(yàn)內(nèi)容 用頭插法(或尾插法)建立帶頭結(jié)點(diǎn)的單鏈表；對(duì)已建立的單鏈表實(shí)現(xiàn)插入、刪除、查找等基本操作。3. 實(shí)現(xiàn)提示首先，將單鏈表中的結(jié)點(diǎn)定義為如下結(jié)構(gòu)類型：template <class T>struct NodeT data;Node<T> *n ext;其次，定義單鏈表的數(shù)據(jù)類型一一單鏈表類LinkList，包括題目要求的插入、刪除、查找等基本操作，為便于查看操作結(jié)果，設(shè)計(jì)一個(gè)輸出函數(shù)依次輸出單鏈

31、表的元素。template <class T>class Lin kListpublic:LinkList (T a , int n ) ; /建立有n個(gè)元素的單鏈表LinkList ();析構(gòu)函數(shù)void Insert (int i, T x );/在單鏈表中第i個(gè)位置插入元素值為 x的結(jié)點(diǎn)T Delete (int i);/在單鏈表中刪除第i個(gè)結(jié)點(diǎn)int Locate (T x);/求單鏈表中值為x的元素序號(hào)void PrintList ( ) ;/遍歷單鏈表，按序號(hào)依次輸出各元素private:Node<T> *first;單鏈表的頭指針;再次，設(shè)計(jì)單鏈表類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;初始化一個(gè)空鏈表for (i=0; i<n; i+ )s=new Node<T> s->data=ai;為每個(gè)數(shù)組元素建立一個(gè)結(jié)點(diǎn)s-> next=first -> next;/插入到頭結(jié)點(diǎn)之后first-> next=s; 析構(gòu)函數(shù)用于釋放單鏈

33、表中所有結(jié)點(diǎn)，算法如下:單鏈表的析構(gòu)函數(shù)算法LinkListtemplate <class T>Lin kList: Lin kList ()p=first;/工作指針p初始化while ( p)釋放單鏈表的每一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間q=p;暫存被釋放結(jié)點(diǎn)p=p-> next; 工作指針p指向被釋放結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使單鏈表不斷開(kāi) delete q;最后，對(duì)所建立的單鏈表設(shè)計(jì)插入、刪除、查找等基本操作的算法。 插入算法單鏈表插入算法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)存申請(qǐng)一個(gè)結(jié)點(diǎn) s,其數(shù)據(jù)域?yàn)閤 &> next=p->next;/將結(jié)點(diǎn)s插入到結(jié)點(diǎn) 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 個(gè)結(jié)點(diǎn)p=p-> next;j+;if (!p | !p-> next) throw "位置"/結(jié)點(diǎn)p不存在或結(jié)點(diǎn)p的后繼結(jié)點(diǎn)不存在 else q=p-> next; x=q -> data; 暫存被刪結(jié)點(diǎn)p-> next=q -> next;摘鏈delete q;return x;查找算法23數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(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í)驗(yàn)程序/以下為頭函數(shù)，文件名為L(zhǎng)inkList.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個(gè)元素的單鏈表Li nkList( );/ 析構(gòu)函數(shù)void Insert(int i, T x);在單鏈表中第i個(gè)位置插入元素值為x的結(jié)點(diǎn)T Delete(int i);/在單鏈表中刪除第i個(gè)結(jié)點(diǎn)int Locate(T x);求單鏈表中值為x的元素序號(hào)void Prin tList();遍歷單鏈表，按序號(hào)依次輸出各元素private:Node<T> *first;/單鏈表的頭指針;#en dif/以下為頭函數(shù) LinkList.h中LinkList類的成員函數(shù)的定義，文件名為L(zhǎng)inkList.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)實(shí)驗(yàn)指導(dǎo)first-next=NULL;/初始化一個(gè)空鏈表for (i nt i=0; i<n; i+)Node<T> *s;s=new Node<T> s->data=ai;/為每個(gè)數(shù)組元素建立一個(gè)結(jié)點(diǎn)s-> next=first-> next;插入到頭結(jié)點(diǎn)之后first->n ext=s;template <

39、class T>Lin kList<T>: Li nkList ()Node<T> *p, *q;p=first;/工作指針p初始化while (p)II釋放單鏈表的每一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間q=p;暫存被釋放結(jié)點(diǎn)p=p-> next; 工作指針p指向被釋放結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使單鏈表不斷開(kāi) 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)存申請(qǐng)一個(gè)結(jié)點(diǎn)s,其數(shù)據(jù)域?yàn)?xs->next=p->next;將結(jié)點(diǎn)s插入到結(jié)點(diǎn) p之后p_>n ext=s;template <class T>T LinkList<T>:Delete(int i)Node<T> *p; int j;#數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)p=first ; j=0;/工作指

41、針p初始化while (p && j<i-1)/查找第 i-1 個(gè)結(jié)點(diǎn)p=p->n ext;j+；p的后繼結(jié)點(diǎn)不存在if仲|(zhì) !p->next) throw "位置"/結(jié)點(diǎn)p不存在或結(jié)點(diǎn) else Node<T> *q; int x;q=p-> next; x=q->data;暫存被刪結(jié)點(diǎn)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>/引用輸入輸出流庫(kù)函數(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é)點(diǎn)設(shè)計(jì)一個(gè)結(jié)點(diǎn)類，重新實(shí)現(xiàn)單鏈表基本操作的驗(yàn)證。2.2設(shè)計(jì)實(shí)驗(yàn) 2.2.1數(shù)組的循環(huán)移位1. 問(wèn)題描述對(duì)于一個(gè)給定的整型數(shù)組循環(huán)右移i位。2. 基本要求 在原數(shù)組中實(shí)現(xiàn)循環(huán)右移，不另外申請(qǐng)空間;時(shí)間性能盡可能好； 分析算法的時(shí)間復(fù)雜度。27數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)將這個(gè)問(wèn)題看作是把數(shù)組 ab轉(zhuǎn)換成數(shù)組ba (a代表數(shù)組的前i個(gè)元素，b代表數(shù)組中 余下的n-i個(gè)元素)，先將a逆置得到arb,再將b逆置得到abr，最后將整個(gè)arbr逆置得到 (arbr)r=ba。設(shè)Reverse函數(shù)執(zhí)行將數(shù)組元素逆置的操作，對(duì)ab

46、cdefgh向左循環(huán)移動(dòng) 3個(gè)位置的過(guò)程如下：Reverse(0, i -1);得到cbadefghReverse(i, n-1);得到cbahgfedReverse(O, n-1);/得到defghabc具體分析過(guò)程請(qǐng)參見(jiàn)主教材第一章思想火花。4.算法描述循環(huán)右移算法void Con verse (int A , i nt n, int i )Reverse( A, 0, i -1);/前 i 個(gè)元素逆置Reverse( A, i, n -1);/后 n-i 個(gè)元素逆置Reverse( A, 0, n -1);/整個(gè)數(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;/交換元素【思考題】你還有其他解決方法嗎？請(qǐng)?jiān)O(shè)計(jì)算法并上機(jī)實(shí)現(xiàn)。2.2.2集合的交、并和差運(yùn)算的實(shí)現(xiàn)1. 問(wèn)題描述用有序單鏈表表示集合，實(shí)現(xiàn)集合的交、并和差運(yùn)算。2. 基本要求 對(duì)集合中的元素，用有序單鏈表進(jìn)行存儲(chǔ)；實(shí)現(xiàn)交、并、差運(yùn)算時(shí)，不另外申請(qǐng)存儲(chǔ)空間； 充分利用單鏈表的有序性，算法有較好的時(shí)間性能。3. 設(shè)計(jì)思想首先，建立兩個(gè)帶頭結(jié)點(diǎn)的有序單鏈表表示集合A和B。單鏈表的結(jié)點(diǎn)結(jié)構(gòu)和建立算法請(qǐng)參見(jiàn)2.1.2，需要

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

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

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

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

52、un t=2(a) 一般情況(b)只剩下一個(gè)結(jié)點(diǎn)的特殊情況 圖2-1約瑟夫環(huán)問(wèn)題存儲(chǔ)示意圖#數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)#數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)【思考題】采用順序存儲(chǔ)結(jié)構(gòu)如何實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題？如果每個(gè)人持有的密碼不同，應(yīng)如何實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題?31數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)2.3.2 一元多項(xiàng)式相加1. 問(wèn)題描述已知 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è)計(jì)存儲(chǔ)結(jié)構(gòu)表示一元多項(xiàng)式；設(shè)計(jì)算法實(shí)現(xiàn)一元多項(xiàng)式相加； 分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。3.

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

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

55、gt;q-> exp，則結(jié)點(diǎn)q應(yīng)為結(jié)果中的一個(gè)結(jié)點(diǎn)，將q插入到第一個(gè)鏈表中結(jié)點(diǎn)p之刖； 若p-> exp=q-> exp，則結(jié)點(diǎn)p與結(jié)點(diǎn)q為同類項(xiàng)，將q的系數(shù)加到p的系數(shù)上。若 相加結(jié)果不為0，則結(jié)點(diǎn)p應(yīng)為結(jié)果中的一個(gè)結(jié)點(diǎn)，同時(shí)刪除結(jié)點(diǎn) q;若相加結(jié)果為0，則 表明結(jié)果中無(wú)此項(xiàng)，刪除結(jié)點(diǎn) p和結(jié)點(diǎn)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é)點(diǎn)q插入到結(jié)

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