數(shù)據(jù)結(jié)構(gòu)（C++語言描述）PPT全套完整教學(xué)課件

數(shù)據(jù)結(jié)構(gòu)（C++語言描述）1第一章緒論.pptx2第二章線性表.pptx 3第三章棧和隊列.pptx 4第四章樹.pptx 5第五章圖.pptx 6第六章查找.pptx 7第七章排序.pptx 5.1-靜態(tài)查找技術(shù).pptx 5.2-動態(tài)查找技術(shù).pptx 5.3-二叉查找樹的查找.pptx ..........

第一章緒論數(shù)據(jù)結(jié)構(gòu)算法C++部分概念數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容數(shù)據(jù)：外界信息進入計算機后，統(tǒng)稱為數(shù)據(jù)。一般分為數(shù)值和非數(shù)值型。數(shù)據(jù)元素：是數(shù)據(jù)處理的最小單位，是一個數(shù)據(jù)個體。

如處理某窗口前的隊列，隊列中所有人的信息稱數(shù)據(jù)，每個人的信息稱數(shù)據(jù)元素。什么是數(shù)據(jù)及數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)：有限個、類型相同、相互之間具有一定制約關(guān)系的數(shù)據(jù)元素組成的集合。如某窗口前的隊列，有限/類型相同/你先我后關(guān)系。幾種典型結(jié)構(gòu)：什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容：（以隊列為例）

邏輯關(guān)系（邏輯結(jié)構(gòu)）+基本操作（關(guān)系操作）------來源于生活實踐，和計算機無關(guān)。存儲實現(xiàn)（物理結(jié)構(gòu)）------數(shù)據(jù)及數(shù)據(jù)關(guān)系在內(nèi)存中的存儲?；静僮鞯膶崿F(xiàn)------某種存儲處理下各種基本操作的實現(xiàn)。典型應(yīng)用------這種數(shù)據(jù)結(jié)構(gòu)在生活實踐中的典型應(yīng)用。數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容指類型相同的一組元素和元素間的關(guān)系。根據(jù)關(guān)系不同，可分為以下幾種：集合關(guān)系：不同元素除了同屬于一個集合，相互間無其他制約關(guān)系。線性關(guān)系：元素間呈現(xiàn)你先我后的順序，是一種一對一的關(guān)系。樹形關(guān)系：元素間呈現(xiàn)一對多的關(guān)系。圖關(guān)系：元素間呈現(xiàn)多對多的關(guān)系。邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)的描述具有某種關(guān)系的數(shù)據(jù)在生活實踐中表現(xiàn)出的幾種功能相對獨立的數(shù)據(jù)處理（操作）。它和數(shù)據(jù)的邏輯結(jié)構(gòu)緊密相關(guān)，它來源于現(xiàn)實生活中關(guān)系自身的特點。無論哪種邏輯結(jié)構(gòu)，基本操作都可分為五大類：構(gòu)造類、屬性類、數(shù)據(jù)操縱類、遍歷類和典型應(yīng)用類。基本操作(關(guān)系操作)構(gòu)造類：在內(nèi)存中建立這種數(shù)據(jù)結(jié)構(gòu)。如一個隊列，有存儲空間，無或有若干元素。屬性類：對元素及元素之間關(guān)系的各類查詢。屬于東瞧瞧、西看看，不影響元素值及元素關(guān)系。如在線性結(jié)構(gòu)中查詢值為X的元素是否存在，隊列中隊首是誰。數(shù)據(jù)操縱類：對元素或元素關(guān)系有改變的操作。如插入或刪除某個元素，一般修改可以視作在同一位置上先刪除一個舊元素后再插入一個新元素，因此不再討論修改。遍歷類：對結(jié)構(gòu)中的每個元素訪問且只訪問一遍。因其重要且有時又較復(fù)雜，常常是其他操作的基礎(chǔ)，如遍歷樹結(jié)構(gòu)、圖結(jié)構(gòu)中的元素，所以特意把遍歷操作從屬性類中單獨拿出來研究。典型應(yīng)用類：每種結(jié)構(gòu)獨特的應(yīng)用。不同結(jié)構(gòu)其典型應(yīng)用各不相同，如線性結(jié)構(gòu)可以解決隊列問題、圖結(jié)構(gòu)可以解決兩個城市間最短路徑問題。數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的表示。數(shù)據(jù)要得到處理首先必須進入內(nèi)存。內(nèi)存中不僅要存儲數(shù)據(jù)元素的值，還要存儲元素間的關(guān)系。任何一種數(shù)據(jù)結(jié)構(gòu)基本操作的設(shè)計取決于其邏輯結(jié)構(gòu)，但基本操作的實現(xiàn)完全依賴其存儲結(jié)構(gòu)。元素及其關(guān)系在內(nèi)存中用什么結(jié)構(gòu)存儲適合，原則是存儲方式要有利于基本操作的實現(xiàn)。什么是存儲結(jié)構(gòu)順序存儲：用一塊連續(xù)的空間存儲數(shù)據(jù)，借助空間地址上的有序性存儲元素間的關(guān)系。順序存儲的結(jié)構(gòu)以下稱順序結(jié)構(gòu)。高級語言中，數(shù)組是地址連續(xù)的空間，有助于實現(xiàn)順序結(jié)構(gòu)。鏈?zhǔn)酱鎯Γ涸乜梢愿髯源鎯υ讵毩⒌目臻g中，不要求不同數(shù)據(jù)存儲的內(nèi)存空間連續(xù)，元素間的關(guān)系附帶存儲在數(shù)據(jù)各自占據(jù)的獨立空間中。數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)酱鎯σ卜Q鏈?zhǔn)浇Y(jié)構(gòu)。常見的存儲方式存儲數(shù)據(jù)及其關(guān)系的目的就是為了處理?；静僮鲗崿F(xiàn)方法以存儲方法為基礎(chǔ)。如果是順序結(jié)構(gòu)，操作實現(xiàn)就是對數(shù)組做各種不同的操作；如果是鏈?zhǔn)浇Y(jié)構(gòu)，操作實現(xiàn)就是對鏈表做各種不同的操作。同一種操作雖然在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)中具體實現(xiàn)方法不同，但目標(biāo)都要符合ADT對基本操作定義的條件和結(jié)果。如果某種存儲方式下，基本操作不易實現(xiàn)，說明存儲方式不好，可以考慮放棄這種存儲方法?；静僮鞯膶崿F(xiàn)數(shù)據(jù)結(jié)構(gòu)算法C++部分概念算法及算法特性算法時間復(fù)雜度算法空間復(fù)雜度算法具有5個特性：確定性：每一步有確定的含義，沒有二義性。有窮性：每一步在有限的時間內(nèi)完成，整個算法必須在有限步之后完成。可行性：每一步都是經(jīng)過有限次基本操作可以完成，自身沒有復(fù)雜的算法。有輸入：一個算法可以有零個或者若干個輸入作為解決問題的已知條件。有輸出：有零個或者若干個輸出作為算法運行結(jié)果。算法：是解決一個具體問題的方法和步驟。正確性：準(zhǔn)確反映并能滿足具體問題的要求?？勺x性：可供人們閱讀的容易程度。健壯性：對各種不同的輸入都要有相應(yīng)的反應(yīng)時間效率：算法的執(zhí)行時間?？臻g效率：算法執(zhí)行期間所需要的最大內(nèi)存空間。算法的基本要求：比如：選最大桔子問題，體育課排隊，5個數(shù)字的加法。正確的方式：計算思維，具體從編程語言出發(fā)。具體編程語言：輸入、輸出、賦值、兩兩比較、算術(shù)和邏輯運算，循環(huán)、函數(shù)（遞歸）等。

如冒泡排序，選擇排序的設(shè)計思想設(shè)計算法的誤區(qū)：從以往生活的經(jīng)驗出發(fā)，找解決問題的方法算法的執(zhí)行時間是指依據(jù)算法編制的程序運行時所消耗的時間。度量方法有運行后度量和運行前分析。運行后度量：指根據(jù)不同算法事先編制好的程序和同樣的測試數(shù)據(jù)，在程序運行時借助機器的計時功能進行計時。當(dāng)不同程序運行結(jié)束時，分別記錄實際的運行時間并進行比較。運行前分析：指在算法設(shè)計后，在實現(xiàn)程序運行前，根據(jù)幾個方面的影響因素對算法的執(zhí)行時間進行分析。算法的時間復(fù)雜度機器的運算速度：根據(jù)主頻和字長。編譯后代碼的質(zhì)量：因編譯優(yōu)化策略不同書寫程序所用的語言：語言越高級，運行效率低，編程效率高。問題的規(guī)模和數(shù)據(jù)的分布：規(guī)模大，分布特殊則處理方法可不同。算法采用的策略和方法：如用迭代或遞歸就不同。算法設(shè)計主要關(guān)注5，算法的策略和方法。運行前分析的依據(jù)用算法中標(biāo)準(zhǔn)操作即基本語句的執(zhí)行次數(shù)來度量運行時間?；菊Z句執(zhí)行次數(shù)越多，時間花費越多，執(zhí)行次數(shù)稱時間頻度。時間頻度和處理的數(shù)據(jù)規(guī)模n有關(guān)，可表示為n的函數(shù)T(n)。s=0;for(i=0;i<n;i++)

s=s+i;算法運行時間的度量---時間頻度s=0執(zhí)行1次，i=0執(zhí)行1次，i<n執(zhí)行n+1次，i++執(zhí)行n次，s=s+i執(zhí)行n次，共計執(zhí)行標(biāo)準(zhǔn)操作3n+3次。故算法的時間頻度為T(n)=3n+3。循環(huán)語句---需要計算實際運行的次數(shù)，不是看語句書寫的次數(shù)。分支語句---按照執(zhí)行語句多的那個分支計算。如：if(n>0){for(i=0;i<n;i++)cout<<i;}else

cout<<"n<=0!";算法運行時間的度量原則n>0時，為3n+3次；n<=0時，為1次。時間頻度為3n+3。

算法的時間復(fù)雜度

算法的時間復(fù)雜度

算法的時間復(fù)雜度

算法的時間復(fù)雜度找算法中和數(shù)據(jù)規(guī)模n有關(guān)的循環(huán)語句，計算循環(huán)體的執(zhí)行次數(shù)獲得時間頻度函數(shù)。觀察時間頻度函數(shù)中關(guān)于n的最高次項，去掉其系數(shù)，即是時間復(fù)雜度的大O表示。特殊地：如果算法中無執(zhí)行次數(shù)和數(shù)據(jù)規(guī)模n的相關(guān)語句，即時間頻度函數(shù)是一個常量，則時間復(fù)雜度為O(1)?？偨Y(jié)時間復(fù)雜度的計算方法：

常見算法的時間復(fù)雜度：求和定理、求積定理求和定理：假定T1(n)、T2(n)是程序P1、P2的運行時間，并且T1(n)是O(f(n))的，而T2(n)是O(g(n))的。那么，先運行P1、再運行P2的總的運行時間是：T1(n)＋T2(n)＝O(MAX(f(n)，g(n))。for(i=0;i<n;i++)a[i]=0;//第一段for(i=0;i<n;i++)//第二段 for(j=0;j<n;j++)a[i]=i+j;按照求和定理為O(max(n,n2))=O(n2）計算時間復(fù)雜度的簡化工具：兩個定理求和定理、求積定理求積定理：如果T1(n)和T2(n)分別是O(f(n))和O(g(n))的，那么T1(n)×T2(n)是O(f(n)×g(n))的。for(i=0;i<n;i++) for(j=0;j<n;j++) {s=s+i+j;cout<<s;}按照求積定理，為O(n*n)=O(n2)計算時間復(fù)雜度的簡化工具：兩個定理通常考慮三個方面：最好情況的時間復(fù)雜度、最壞情況的時間復(fù)雜度和平均情況的時間復(fù)雜度。大O表示法中，O是數(shù)量級order的首字母。O(f(n))并不描述運行時間的精確值，只給出一個數(shù)量級。它表示：當(dāng)問題規(guī)模很大時，算法運行時間的增長受限于哪一個數(shù)量級的函數(shù)，簡稱為量階。算法的時間復(fù)雜度算法的空間消耗包括三個方面：實現(xiàn)算法的程序本身需要占據(jù)存儲空間待處理的數(shù)據(jù)需要在內(nèi)存中存儲，占據(jù)一定的空間處理數(shù)據(jù)的過程中需要一些額外的輔助空間。通常一和二是不可避免的，在設(shè)計算法時主要關(guān)注額外的輔助空間。漸進空間復(fù)雜度也稱空間復(fù)雜度：是當(dāng)數(shù)據(jù)規(guī)模n趨于無窮時使用輔助空間的量階，計為S(n)=O(f(n))。算法的空間復(fù)雜度inta[10]={1,6,2,5,8,9,5,4,3,12};intt,i;for(i=0;i<5;i++){ t=a[i]; a[i]=a[10-i-1]; a[10-i-1]=t;}一個數(shù)據(jù)序列逆置的示例：為完成n=10個元素的逆置，將a[0]和a[9]交換、a[1]和a[8]交換，最后直到a[4]和a[5]交換。使用的輔助空間為一個變量t，輔助空間數(shù)量和元素個數(shù)沒有關(guān)系，故其空間復(fù)雜度為O(1)。inta[10]={1,6,2,5,8,9,5,4,3,12},b[10];inti;for(i=0;i<10;i++) b[i]=a[10-i-1];for(i=0;i<10;i++) a[i]=b[i];一個數(shù)據(jù)序列逆置的示例：使用了具有n個元素空間的數(shù)組b作為輔助空間，空間復(fù)雜度為O(n)。在內(nèi)存足夠大的情況下，算法更加注重時間效率，忽略空間復(fù)雜度的計算?；蛘邇H當(dāng)算法的時間復(fù)雜度一致的情況下才可能比較空間復(fù)雜度的優(yōu)劣。說明：數(shù)據(jù)結(jié)構(gòu)算法

C++部分概念面向?qū)ο蠓盒蜋C制const機制異常處理面向?qū)ο蠓椒▽?shù)據(jù)和對數(shù)據(jù)的基本操作處理函數(shù)都封裝在一個類中，分別成為一個類的屬性和成員函數(shù)。整個類相當(dāng)于定義了一個新的數(shù)據(jù)類型，然后根據(jù)具體問題建立該類的對象（即變量），通過對象調(diào)用合適的函數(shù)來解決實際問題。面向?qū)ο笕蝿?wù)：將1-20之間的奇數(shù)存入內(nèi)存，之后在這組數(shù)中查找用戶輸入的任意一個整數(shù)并報告查找結(jié)果。面向過程VS面向?qū)ο螅簐oidsetValue(intb[],intn);voidfind(intb[],intn,intx);//查找x

intmain(){intdata[10],a;

setValue(data,10);

cout<<"a=";cin>>a;

find(data,10,a);return0;}面向過程：voidsetValue(intb[],intn){for(inti=0;i<n;i++)b[i]=2*i+1;}

voidfind(intb[],intn,intx){inti;for(i=0;i<n;i++)

if(b[i]==x)break;

if(i==n)

cout<<x<<"doesn'texistinthearray!";

else

cout<<x<<"existsinthearray!";cout<<endl;}classarr{private:int*a;intmaxSize,count;public:arr(intsize);voidappend(intx);voidfind(intx);~arr(){delete[]a;};};面向?qū)ο螅篴rr::arr(intsize){a=newint[size];maxSize=size;count=0;}

voidarr::append(intx){if(count==maxSize)return;a[count]=x;count++;}voidarr::find(intx){inti;for(i=0;i<count;i++)if(a[i]==x)break;if(i==count)cout<<x<<"doesn'texistinthearray!";elsecout<<x<<"existsinthearray!";cout<<endl;}面向?qū)ο螅篿ntmain(){arrobj(10);inta;

for(inti=0;i<10;i++)

//將幾個奇數(shù)放入對象obj.append(2*i+1);

cout<<"a=";cin>>a;

obj.find(a);return0;}數(shù)據(jù)結(jié)構(gòu)研究的是具有一定關(guān)系，且類型相同的一組元素。元素類型不特指某種具體類型，如整型、字符型或者復(fù)雜的結(jié)構(gòu)類型。元素?zé)o論何種類型，它們在關(guān)系、基本操作處理方法上是一樣的。因此在數(shù)據(jù)類型上使用泛型機制：函數(shù)模板、類模板泛型機制函數(shù)模板定義template<classT>Tmax(Tx,Ty){if(x>y)returnx;elsereturny;}函數(shù)模板的使用intmain{count<<max(3,5)<<max(‘a(chǎn)’,’h’)<<endl;}//自動檢測類型，編譯時產(chǎn)生模板函數(shù)函數(shù)模板類模板的定義template<classelemType>classarr{private:elemType*a;intmaxSize,count;public:arr(intsize);

類模板//參數(shù)前加const，保護參數(shù)在函數(shù)執(zhí)行中不得修改voidappend(constelemType&x);

//參數(shù)表后加const,保護調(diào)用函數(shù)的對象的值不得修改voidfind(constelemType&x)const;~arr(){delete[]a;};};

template<classelemType>//類模板中成員函數(shù)自動為函數(shù)模板arr<elemType>::arr(intsize){a=newelemType[size];maxSize=size;count=0;}類模板

template<classelemType>voidarr<elemType>::append(constelemType&x){if(count==maxSize)return;a[count]=x;count++;}template<classelemType>voidarr<elemType>::find(constelemType&x)const{inti;for(i=0;i<count;i++)

if(a[i]==x)break;類模板

if(i==count)cout<<x<<"doesn'texistinthearray!";

elsecout<<x<<"existsinthearray!";cout<<endl;}類模板的使用intmain(){arr<int>obj1(10);

//<int>使得類模板實例化為一個模板類

constarr<int>obj2(20);

inta;

constintb=100;

類模板

for(inti=0;i<10;i++)obj1.append(2*i+1);cout<<"a=";cin>>a;cout<<"Inobj1:";obj1.find(a);cout<<"Inobj1:";obj1.find(b);cout<<"Inobj2:";obj2.find(a);return0;}用const修飾變量，變量將變?yōu)槌Ａ?。常量一般有初值，在常量的生命周期中，終生不得改變其值。C++中const最普通的用法：constdoublePI=3.14;const機制函數(shù)voidfind(constelemType&x)const中修飾參數(shù)x的const和&組合。const修飾：變量x前加const，表明在函數(shù)的實現(xiàn)過程中參數(shù)x的值不需要改變。如函數(shù)voidf(constintx)，參數(shù)加了const后，編譯器會在程序編譯階段幫助程序檢查函數(shù)實現(xiàn)代碼中是否含有修改x值的語句，如果有就報錯。所以，如果確認函數(shù)實現(xiàn)中不準(zhǔn)備改變x的值，請養(yǎng)成加const的習(xí)慣。類定義時常見的兩種const用法：函數(shù)voidfind(constelemType&x)const中修飾參數(shù)x的const和&組合。const和&組合修飾：函數(shù)find的原型中，x前帶&符號，說明形參x不分配空間，是將來調(diào)用時實參的別名。如對它的調(diào)用obj1.find(a);形參x不分空間，和實參a共用空間。一般來說，如果一個函數(shù)只是使用實參a的值，并不想改變實參a的值，這個&就沒有必要用，只要加const便可。類定義時常見的兩種const用法：函數(shù)voidfind(constelemType&x)const中修飾參數(shù)x的const和&組合。const和&組合修飾：因為參數(shù)類型elemType是一種泛型類型，調(diào)用find函數(shù)時實參可能是復(fù)雜的結(jié)構(gòu)類型，加了&符號就有了明顯的好處：形參x不分空間，節(jié)省了空間消耗。沒有空間分配，在實參和形參打交道時，就不涉及拷貝構(gòu)造函數(shù)的執(zhí)行。

提高了運行效率。故泛型類型參數(shù)前盡量加&符號，如果函數(shù)又不需要改變這個參數(shù)，請養(yǎng)成const加&組合的習(xí)慣。類定義時常見的兩種const用法：2.函數(shù)voidfind(constelemType&x)const中參數(shù)表后const的用法。

參數(shù)表后的const是保護調(diào)用它的對象的值不能被改變。

語句obj1.find(a)，這個const就是保護對象obj1的值。

一個成員函數(shù)不準(zhǔn)備改變調(diào)用它的對象的值，請養(yǎng)成在參數(shù)表后加const的習(xí)慣。如果沒有函數(shù)參數(shù)表后帶const的支持，常對象obj2是不能調(diào)用這個函數(shù)的。常對象obj2只能調(diào)用參數(shù)表后帶const的成員函數(shù)，加const就為常對象調(diào)用它開一扇窗。constarrobj2;obj2.find(10);類定義時常見的兩種const用法：template<classelemType>elemTypearr<elemType>::fetch(inti)const{if((i<0)||(i>=count)){cout<<"indexisoutofbound!"<<endl;exit(1);}elsereturna[i];}異常處理在數(shù)組類模板中的函數(shù)fetch讀取并返回下標(biāo)為i的元素考慮問題：當(dāng)i越界時返回什么合適？調(diào)用exit函數(shù)？throw，try，catch異常處理機制classtooSmall{};classtooBig{};異常處理template<classelemType>elemTypearr<elemType>::fetch(inti)const{if(i<0)throwtooSmall();if(i>=count)throwtooBig();elsereturna[i];}intmain(){arr<int>obj1(10);constarr<int>obj2(20);inti;

try{for(i=0;i<10;i++)obj1.append(2*i+1);

異常處理

while(cin>>i)

cout<<i<<":"<<obj1.fetch(i)<<endl;}catch(tooSmall){cout<<"indexistoosmall!"<<endl;}catch(tooBig){cout<<"indexistoobig!"<<endl;}

cout<<"Returntomain,itisOver!"<<endl;return0;}數(shù)據(jù)元素及元素間關(guān)系稱作數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)研究具有某種制約關(guān)系的一組元素及元素間關(guān)系在內(nèi)存中如何存儲、在各種存儲方式下關(guān)系操作如何實現(xiàn)，以及各種數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用。具體研究分邏輯結(jié)構(gòu)及基本操作、物理結(jié)構(gòu)、基本操作實現(xiàn)、典型應(yīng)用四個方面。在分析邏輯結(jié)構(gòu)和基本操作時，要完全脫離計算機而僅僅依賴現(xiàn)實生活中的元素特征來分析元素、元素關(guān)系及基本操作，最后給出用偽代碼描述的抽象數(shù)據(jù)類型。小結(jié)在物理結(jié)構(gòu)分析階段，討論元素及元素關(guān)系在內(nèi)存中如何存儲。存儲可以分順序存儲和鏈?zhǔn)酱鎯?，順序存儲使用一塊連續(xù)的空間存儲元素和元素之間的關(guān)系；鏈?zhǔn)酱鎯κ褂酶髯元毩⒌目臻g存儲每個元素，并在每個獨立的空間中附加字段以存儲元素之間關(guān)系。在基本操作實現(xiàn)分析階段，研究在各種存儲方式下基本操作的實現(xiàn)方法和步驟即算法。對于算法提出了時間復(fù)雜度和空間復(fù)雜度的概念及計算方法，并以此為依據(jù)，對不同算法進行性能比較。在典型應(yīng)用階段，給出所研究的數(shù)據(jù)結(jié)構(gòu)最適合的實際應(yīng)用問題。小結(jié)第二章線性表張同珍線性表

順序表及實現(xiàn)鏈表及實現(xiàn)一元多項式字符串稀疏矩陣一組特征相同且數(shù)量有限的元素構(gòu)成的集合。該集合可以為空，也可以不為空。當(dāng)不為空時，有唯一一個元素被稱為首元素，有唯一一個元素被稱為尾元素。除了尾元素，每個元素有且僅有一個直接后繼元素；除了首元素，每個元素有且僅有一個直接前驅(qū)元素。

線性結(jié)構(gòu)定義：線性表(List)、時間有序表(ChronologicalOrderedList)、排序表(SortedList)、頻率有序表(FrequencyOrderedList)等。線性表：通過元素之間的相對位置來確定它們之間相互關(guān)系。時間有序表：按元素到達結(jié)構(gòu)的時間先后，確定元素之間的關(guān)系。棧/隊列排序表：據(jù)元素的關(guān)鍵字值來確定其間的關(guān)系。頻率有序表：按元素的使用頻率確定它們之間的相互關(guān)系。常見的幾種線性結(jié)構(gòu)：一種僅由元素的相互位置確定它們之間相互關(guān)系的線性結(jié)構(gòu)，元素之間呈現(xiàn)出你先我后的關(guān)系。

線性表的規(guī)?；蜷L度是指線性表中元素的個數(shù)。特別地：當(dāng)元素的個數(shù)為零時，該線性表稱為空表。線性表Data:{xi|xi

ElemSet,i=1,2,3,……n,n>0}或Φ;ElemSet為元素集合。Relation:{<xi,xi+1>|xi,xi+1

ElemSet,i=1,2,3,……n-1},

x1為首元素，xn為尾元素。Operations:initialize

前提: 無或指定List的規(guī)模。結(jié)果: 分配相應(yīng)空間及初始化。isEmpty

前提：無

結(jié)果：表List為空返回true，否則返回false。isFull前提：無

結(jié)果：表List為滿返回true，否則返回false。線性表List的ADT：描述關(guān)系和關(guān)系操作length

前提：無

結(jié)果：返回表List中的元素個數(shù)。get

前提：已知元素序號。

結(jié)果：

如果該序號元素存在，則返回相應(yīng)元素的數(shù)據(jù)值。find

前提：已知元素的數(shù)據(jù)值。

結(jié)果：

查找成功，返回元素的序號，否則返回查找失敗標(biāo)志。insert前提：已知待插入的元素及插入位置。

結(jié)果：如果插入位置合理，在指定位置插入該元素。線性表List的ADT：描述關(guān)系和關(guān)系操作remove前提：已知被刪元素的值。

結(jié)果：首先按值查找相應(yīng)元素，查找成功則刪除該元素。clear

前提:

無

結(jié)果：刪除表List中的所有元素。常見的基本操作來源于生活中對這種結(jié)構(gòu)的了解。基本操作可以分為幾大類型：結(jié)構(gòu)類、屬性類、數(shù)據(jù)操縱類、遍歷類和典型應(yīng)用類，線性表List的ADT：描述關(guān)系和關(guān)系操作熟練C++面向?qū)ο蟮木幊谭椒?、C++語法、書寫完整程序的技巧。接觸并逐步熟悉研究一種數(shù)據(jù)結(jié)構(gòu)的角度和方法。掌握順序結(jié)構(gòu)的基本功。掌握鏈?zhǔn)讲僮鞯幕竟ΑＵ莆諗?shù)據(jù)結(jié)構(gòu)工具的建造和工具使用的不同。掌握最基本且簡單的線性結(jié)構(gòu)-線性表結(jié)構(gòu)線性表這章的任務(wù)和目標(biāo)：

線性表

順序表及實現(xiàn)鏈表及實現(xiàn)一元多項式字符串稀疏矩陣元素存放在內(nèi)存中一塊連續(xù)的空間里。借助存儲空間物理上的連續(xù)性，元素可以按照其邏輯順序依次存放，即元素存放的物理順序和它的邏輯順序是一致的。順序存儲的線性表稱順序表。在高級語言的固有數(shù)據(jù)類型中，數(shù)組在存儲器中就表現(xiàn)為一塊連續(xù)的空間，因此用數(shù)組實現(xiàn)順序表非常合適。數(shù)組中各元素位置由其下標(biāo)來表示，它同時也是相應(yīng)元素的位置序號。順序結(jié)構(gòu)順序表的存儲映像圖elem為數(shù)組名字，數(shù)組存儲線性表。maxSize為len的上界；initSize為最大的存儲空間數(shù)，maxSize=initSize-1elem[0]用于其它特殊用途，如果不用于特殊用途maxSize=initSizelen為元素個數(shù)，即順序表長度；#include<iostream>#defineINITSIZE100usingnamespacestd;

//用于異常處理中識別錯誤類別classillegalSize{};classoutOfBound{};順序表seqList及操作的定義（seqList.h）template<classelemType>classseqList{private:elemType*elem;//順序表存儲數(shù)組，存放實際的數(shù)據(jù)元素。

intlen;//順序表中的元素個數(shù)，亦稱表的長度。

intmaxSize;//順序表的的最大可能的長度。

voiddoubleSpace();//私有函數(shù)，做內(nèi)部工具順序表seqList及操作的定義（seqList.h）

public:seqList(intsize=INITSIZE);//初始化順序表

//表為空返回true,否則返回false。boolisEmpty()const{return(len==0);}

//表為滿返回true，否則返回false。boolisFull()const{return(len==maxSize);}intlength()const{returnlen;}//表的長度，即實際存儲元素的個數(shù)。

順序表seqList及操作的定義（seqList.h）注意各處：const和const&的用法

elemTypeget(inti)const;//返回第i個元素的值//返回值等于e的元素的序號，無則返回0.intfind(constelemType&e)const;

//在第i個位置上插入新的元素（值為e），//使原來的第i個元素成為第i+1個元素。voidinsert(inti,constelemType&e);//若第i個元素存在，刪除并將其值放入e指向的空間。順序表seqList及操作的定義（seqList.h）

voidremove(inti,elemType&e);

voidclear(){len=0;};//清除順序表，使得其成為空表~seqList(){delete[]elem;};//釋放表占用的動態(tài)數(shù)組};順序表seqList及操作的定義（seqList.h）順序表基本操作的實現(xiàn)代碼（seqList.h）//屬性賦初值，注意模板函數(shù)用法：帽子和胡須template<classelemType>seqList<elemType>::seqList(intsize)//初始化順序表{elem=newelemType[size];//申請動態(tài)數(shù)組

if(!elem)throwillegalSize();maxSize=size-1;//0下標(biāo)位置用于查找時做哨兵位。

len=0;}順序表基本操作的實現(xiàn)代碼template<classelemType>voidseqList<elemType>::doubleSpace(){inti;elemType*tmp=newelemType[2*maxSize];if(!tmp)throwillegalSize();

for(i=1;i<=len;i++)tmp[i]=elem[i];

delete[]elem;elem=tmp;maxSize=2*maxSize-1;}查找操作：待查元素放哨兵位，從后往前比較

順序表基本操作的實現(xiàn)分析分析時間效率：查找成功情況：查找每個位置元素等概率1/n平均：(1+2+…+n)1/n=（n+1)/2時間復(fù)雜度：O(n)查找不成功情況：每次查找從尾部到哨兵位，比較n+1次時間復(fù)雜度：O(n)擺龍門陣：順序表基本操作的實現(xiàn)代碼template<classelemType>//注意各處const,const+&組合的用法intseqList<elemType>::find(constelemType&e)const//返回值等于e的元素的序號，無則返回0.{inti;elem[0]=e;//哨兵位先置為待查元素for(i=len;i>=0;i--)if(elem[i]==e)break;returni;}插入操作：新元素欲插在下標(biāo)為i的位置，i可能的取值為n+1,n,…,2,1。順序表基本操作的實現(xiàn)分析特別注意：是從后往前至i位置逐個元素后移一位。分析時間效率：插入每個位置等概率1/（n+1）移動的次數(shù)分別為0,1,2,…,n平均：(1+2+…+n)/(n+1)=n/2時間復(fù)雜度：O(n)擺龍門陣：順序表基本操作的實現(xiàn)代碼如何寫出一個完成的程序？“五步口訣法”：參數(shù)檢查空間是否支持核心操作對其他屬性的影響正確返回順序表基本操作的實現(xiàn)代碼template<classelemType>voidseqList<elemType>::insert(inti,constelemType&e){intk;if((i<1)||(i>len+1))return;//插入位置越界if(len==maxSize)doubleSpace();//空間滿了，無法插入元素

for(k=len+1;k>i;k--)elem[k]=elem[k-1];elem[i]=e;len++;}循環(huán)注意：左右邊界的檢查刪除操作：待刪元素在下標(biāo)為i的位置，i可能的取值為n,…,2,1。順序表基本操作的實現(xiàn)分析特別注意：是自i+1位置開始，從前往后逐個元素前移一位。分析時間效率：刪除每個位置等概率1/n移動的次數(shù)分別為0,1,2,…,n-1平均：(1+2+…+n-1)/n=（n-1）/2時間復(fù)雜度：O(n)擺龍門陣：順序表基本操作的實現(xiàn)代碼template<classelemType>//注意五步口訣法voidseqList<elemType>::remove(inti,elemType&e){intk;if((i<1)||(i>len))return;e=elem[i];

for(k=i;k<len;k++)elem[k]=elem[k+1];len--;}順序表基本操作的實現(xiàn)代碼template<classelemType>elemTypeseqList<elemType>::get(inti)const//返回第i個元素的值{if((i<1)||(i>len))throwoutOfBound();returnelem[i];}

順序表基本操作的實現(xiàn)代碼常見錯誤：混淆len和maxSize的含義，前者是實際元素的個數(shù)，后者是存儲空間的大小，也是最多能存多少元素的限制。seqList對象作為函數(shù)形參，直接用對象形式而不用引用形式,這樣即浪費空間又引起seqList類的復(fù)制構(gòu)造函數(shù)的執(zhí)行，降低運行效率。insert函數(shù)實現(xiàn)中忘記檢查位置i的合理性、忘了檢查表中是否有空間可以支持插入一個新的元素等，造成算法不完整?？梢栽囍褂梅治鰠?shù)、空間檢查、核心操作、對其他屬性的影響、正確返回的“五步口訣法”，就可以設(shè)計出一個相對完整的程序。順序表應(yīng)用---基本操作的測試main.cpp#include<iostream>#include"seqlist.h"usingnamespacestd;

//求兩個正整數(shù)集合的交集，用線性表處理集合問題。intmain(){seqList<int>list1(20),list2(20),list3(20);//實例化對象inti,j,x;

intlen1,len3;

//輸入第一個整數(shù)集合中的元素，輸入零結(jié)束：i=1;cout<<"輸入第一個正整數(shù)集合，以零為結(jié)束標(biāo)志：";cin>>x;

while(x!=0){list1.insert(i,x);i++;cin>>x;}//輸入第二個整數(shù)集合中的元素，輸入零結(jié)束：i=1;cout<<"輸入第一個正整數(shù)集合，以零為結(jié)束標(biāo)志：";cin>>x;

while(x!=0){list2.insert(i,x);i++;cin>>x;}

//求list1,list2的交集，結(jié)果存入list3len1=list1.length();j=1;for(i=1;i<=len1;i++){x=list1.get(i);if(list2.find(x)!=0)

{

list3.insert(j,x);j++;}}

//顯示list3中的元素cout<<"兩個集合的交集元素為：";len3=list3.length();for(i=1;i<=len3;i++){x=list3.get(i);cout<<x<<"";}cout<<endl;return0;}

線性表

順序表及實現(xiàn)

鏈表及實現(xiàn)一元多項式字符串稀疏矩陣順序表插入、刪除時間代價的分析，可以看出其時間復(fù)雜度是線性階的，而且會引起大量已存儲元素的位置移動。改進方法：鏈?zhǔn)浇Y(jié)構(gòu)各個元素的物理存放位置在存儲器中是任意的，不一定連續(xù)。每個元素放在一個獨立的存儲單元中，元素間的邏輯關(guān)系依靠存儲單元中附加指針來完成。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表，稱為鏈表。鏈?zhǔn)浇Y(jié)構(gòu)鏈表的存儲映像圖為了清晰看出邏輯關(guān)系，以后鏈表用圖(b)來表示。(a)(b)結(jié)構(gòu)體和指針的挑戰(zhàn)！結(jié)構(gòu)類型，結(jié)構(gòu)變量，結(jié)構(gòu)指針93classdateT{public:

intyear;

intmonth;

intday;};

dateTd,*p;d.year=2020;d.month=3;d.day=11;p=&d;cout<<p->year<<endl;cout<<p->month<<endl;cout<<p->day<<endl;dp類，對象，指針structdateT{intyear;intmonth;intday;};dp94classdateT{public:

intyear;

intmonth;

intday;};dateTd,*p;

p=newdataT;

p->year=1010;

p->month=1;

d->day=1;deletep;

p->year=2021;//非法

p=&d;//合法structdateT{intyear;intmonth;intday;};dp無名氏結(jié)點和鏈表：結(jié)點：datanext鏈表：頭指針head指向了頭結(jié)點。頭結(jié)點并不是線性表中的一部分，它的指針字段next給出了首結(jié)點的地址。線性表中最后一個結(jié)點的指針字段next的值為NULL。順著頭指針head，可以很方便地逐個訪問單鏈表中的所有結(jié)點。單鏈表特點：它的任何一個結(jié)點包含了一個存儲元素數(shù)據(jù)值的字段和一個存儲該結(jié)點的直接后繼結(jié)點地址的指針字段。提供一個單鏈表只需要給出頭結(jié)點的地址即頭指針。單鏈表結(jié)點類定義、單鏈表類定義單鏈表類：單鏈表結(jié)點類：（linkList.h）classoutOfBound{};template<classelemType>classlinkList;//類的前向說明template<classelemType>classnode{friendclasslinkList<elemType>;private:elemTypedata;node*next;單鏈表結(jié)點類：

public:node():next(NULL){};node(constelemType&e,node*N=NULL){data=e;next=N;};};單鏈表類：（linkList.h）template<classelemType>classlinkList{private:node<elemType>*head;public:linkList();//構(gòu)造函數(shù)，建立一個空表boolisEmpty()const;//表為空返回true,否則返回false。boolisFull()const{returnfalse;};//表為滿返回true,否則返回false。intlength()const;//表的長度單鏈表類：

elemTypeget(inti)const;//返回第i個元素的值//返回值等于e的元素的序號，從第1個開始，無則返回0.intfind(constelemType&e)const;//在第i個位置上插入新的元素（值為e）。voidinsert(inti,constelemType&e);//若第i個元素存在，刪除并將其值放入e指向的空間。voidremove(inti,elemType&e);voidreverse()const;//元素就地逆置voidclear();//清空表，使其為空表~linkList();};鏈表基本操作的實現(xiàn)代碼（linkList.h）//屬性賦初值，模板函數(shù)用法template<classelemType>linkList<elemType>::linkList()//構(gòu)造函數(shù)，建立一個空表{head=newnode<elemType>();}template<classelemType>boollinkList<elemType>::isEmpty()const//表為空返回true,否則返回false。{if(head->next==NULL)returntrue;returnfalse;}插入操作：將元素x插入在P指針?biāo)附Y(jié)點之后鏈表基本操作的實現(xiàn)分析擺龍門陣！找核心操作插入總結(jié)：遵循“先武裝自己，再融入隊伍”在內(nèi)存中創(chuàng)建新結(jié)點。武裝新結(jié)點：將x寫入新結(jié)點的data字段，p指針?biāo)附Y(jié)點的下一結(jié)點地址寫入新結(jié)點的next字段，使p所指結(jié)點的下一結(jié)點成為新結(jié)點的直接后繼結(jié)點。將新結(jié)點地址寫入p的next字段，使新結(jié)點成為p所指結(jié)點的直接后繼結(jié)點。鏈表基本操作的實現(xiàn)分析插入具體語句：tmp=newnode<elemType>();tmp->data=e;tmp->next=p->next;p->next=tmp;或者：tmp=newnode<elemType>(e,p->next);p->next=tmp;鏈表基本操作的實現(xiàn)分析時間復(fù)雜度分析：當(dāng)P已經(jīng)指向了插入位置的前一個結(jié)點時，插入操作和結(jié)點個數(shù)無關(guān)，時間復(fù)雜度為O(1)?；蛘撸阂粋€四合一語句p->next=newnode<elemType>(e,p->next);鏈表基本操作的實現(xiàn)代碼template<classelemType>voidlinkList<elemType>::insert(inti,constelemType&e)//在第i個位置上插入新的元素（值為e）。{if(i<1)return;//參數(shù)i越界intj=0;node<elemType>*p=head;

while(p&&j<i-1){j++;p=p->next;}

if(!p)return;//參數(shù)i越界p->next=newnode<elemType>(e,p->next);}五步口訣法!刪除操作：刪除P指針?biāo)附Y(jié)點之后的那個結(jié)點鏈表基本操作的實現(xiàn)分析擺龍門陣！找核心操作刪除總結(jié)：記住待刪除結(jié)點地址。將值為x的結(jié)點旁路掉?；厥赵敬鎯的結(jié)點占用的空間。具體語句：node*q=p->next;p->next=q->next;deleteq;鏈表基本操作的實現(xiàn)分析時間復(fù)雜度分析：當(dāng)P已經(jīng)指向了待刪除結(jié)點的前一個結(jié)點時，刪除操作和結(jié)點個數(shù)無關(guān)，時間復(fù)雜度為O(1)。鏈表基本操作的實現(xiàn)分析查找操作：找值為x的結(jié)點，順首結(jié)點逐個向后檢查、匹配。

單鏈表和順序表中，時間復(fù)雜度都是O(n)。

找第k個結(jié)點，順序表O(1），鏈表O(n)。其他基本操作：

isFull：因每次只申請一個結(jié)點空間，故總為false。clear：除了頭結(jié)點刪除并釋放整個單鏈表中結(jié)點，回到初始化后的狀態(tài)。鏈表基本操作的實現(xiàn)代碼template<classelemType>intlinkList<elemType>::length()const//表的長度{intcount=0;node<elemType>*p;p=head->next;while(p)

{count++;p=p->next;}returncount;}鏈表基本操作的實現(xiàn)代碼template<classelemType>//注意：五步口訣法elemTypelinkList<elemType>::get(inti)const//返回第i個元素的值,首元素為第1個元素{if(i<1)throwoutOfBound();intj=1;node<elemType>*p=head->next;while(p&&j<i){p=p->next;j++;}if(p)returnp->data;throwoutOfBound();}

鏈表基本操作的實現(xiàn)代碼template<classelemType>intlinkList<elemType>::find(constelemType&e)const//返回值等于e的元素的序號，從第1個開始，無則返回0.{inti=1;node<elemType>*p=head->next;

while(p)

{if(p->data==e)break;i++;p=p->next;}if(p)returni;return0;}兩種常用技巧：兄弟協(xié)同法、首席插入法template<classelemType>//P、Q兄弟協(xié)同法voidlinkList<elemType>::clear()//清空表，使其為空表{node<elemType>*p,*q;

p=head->next;head->next=NULL;

while(p)

{q=p->next;deletep;p=q;}}heo…∧head頭結(jié)點pq最速插入位置—脖子//首席插入法template<classelemType>voidlinkList<elemType>::insert(constelemTypea[],intn){node*tmp,for(inti=0;i<n;i++){tmp=newnode(a[i],head->next);head->next=tmp;}}114a[5]={1,3,5,7,9}971…∧head頭結(jié)點首結(jié)點練習(xí)：對一個單鏈表進行就地逆置---擺龍門陣115heo…∧head頭結(jié)點首結(jié)點存儲映像圖：olh…∧head頭結(jié)點首結(jié)點helloolleh116heo…∧head頭結(jié)點heo…∧head頭結(jié)點pqpqeho…∧head頭結(jié)點pq“兄弟協(xié)同法”+“首席插入法”實現(xiàn)單鏈表的就地逆置template<classelemType>voidlinkList<elemType>::reverse(){node<elemType>*p,*q;//兄弟倆協(xié)同p=head->next;head->next=NULL;while(p){q=p->next;p->next=head->next;head->next=p;//首席插入p=q;}}常見錯誤：指針p未被初始化或者為空，讀取其指向的字段如p->data，如循環(huán)檢查p所指的結(jié)點中值是否x，可用while(p&&p->data!=x)p=p->next。p原本指向了一個結(jié)點，但其指向的結(jié)點空間已經(jīng)釋放，仍要讀取其所指結(jié)點的字段。如p=head;deletep;p=p->next;p->next非法訪問了不能訪問的內(nèi)存空間。末結(jié)點的next不再指向空，而是指向頭結(jié)點。單循環(huán)鏈表空單向循環(huán)鏈表，只有頭結(jié)點。優(yōu)點：從表中任何一個結(jié)點出發(fā)，都可以順next指針訪問到所有結(jié)點。為了循環(huán)方便，不帶頭結(jié)點的單循環(huán)鏈表居多，head直接指向首結(jié)點。不帶頭結(jié)點的單循環(huán)鏈表空單向循環(huán)鏈表，head指向空。每個結(jié)點有prior和next兩個指針，分別指向直接前驅(qū)和直接后繼結(jié)點雙向鏈表空雙向鏈表，只有頭、尾結(jié)點。優(yōu)點：根據(jù)待查元素在前或后半段，決定自head向后還是自tail向前。不帶頭、尾結(jié)點的雙向循環(huán)鏈表雙向循環(huán)鏈表空雙向鏈表雙向鏈表node*tmp=newnode()//（1）tmp->data=x;//（2）tmp->prior=p;tmp->next=p->next;tmp->prior->next=tmp;//（3）tmp->next->prior=tmp;//（4）插入：將元素x插入到p指針?biāo)附Y(jié)點之后。如果新結(jié)點插入在首結(jié)點位置，操作又有不同，請課后練習(xí)。

線性表

順序表及實現(xiàn)鏈表及實現(xiàn)一元多項式字符串稀疏矩陣在數(shù)學(xué)上，一元多項式一般表示為如下形式：pn(x)=p0+p1x+p2x2+…+pnxn在計算機內(nèi)實現(xiàn)時，可以用線性表來表示:p=(p0，p1，p2，…，

pi

…，pn)，其中結(jié)點pi(0≤i≤n)表示冪為i項的系數(shù)。一元多項式一種方法是：為了表示系數(shù)和項的對應(yīng)關(guān)系。i次冪項的系數(shù)pi存放在下標(biāo)為i的數(shù)組結(jié)點中，即便pi為0，相應(yīng)的數(shù)組分量也不能挪作它用。另外一種處理方法是：只存儲系數(shù)不為0的項，每一項除了存儲它的系數(shù)，還要存儲它的冪。

兩個多項式的加法處理起來比第一種方法復(fù)雜。

用數(shù)組時，要預(yù)估一個多項式的規(guī)模，分配足夠的空間。一元多項式存儲方法每個結(jié)點存放一元多項式中的一項的信息。信息包括該項的系數(shù)和冪，零系數(shù)項不予存儲。鏈?zhǔn)酱鎯Φ暮锰幨嵌囗検降捻棓?shù)可以動態(tài)地增長，不存在溢出問題。用單鏈表表示一元多項式。在存儲實現(xiàn)時，按照冪由小到大的原則進行，這樣該單鏈表便成為冪有序的單鏈表。鏈表中的結(jié)點，包含兩個部分：數(shù)據(jù)部分和指針部分。數(shù)據(jù)部分又包含了系數(shù)coef和冪exp二個字段。一元多項式的鏈?zhǔn)酱鎯σ辉囗検降逆準(zhǔn)酱鎯Χ囗検饺纾?A=7+3x+9x8+5x17 B=8x+22x7-9x8兩個一元多項式相加對pa和pb所指結(jié)點，反復(fù)執(zhí)行如下操作，直至其中一個單鏈表中的結(jié)點全部讀取完畢。冪指數(shù)相等：如果這二個結(jié)點的系數(shù)之和為零，和式中不增加項，否則按照相加后的系數(shù)、相應(yīng)冪指數(shù)創(chuàng)建一個新結(jié)點，作為和式單鏈表C的末結(jié)點，pa、pb后移。指針pa冪指數(shù)?。喊磒a指向的結(jié)點的系數(shù)、冪指數(shù)創(chuàng)建一個新結(jié)點作為單鏈表C的末結(jié)點，pa后移，pb不變。指針pb冪指數(shù)?。喊磒b指向的結(jié)點的系數(shù)、冪指數(shù)創(chuàng)建一個新結(jié)點作為單鏈表C的末結(jié)點，pb后移，pa不變。兩個一元多項式相加將非空多項式單鏈表(可能是A的單鏈表，也可能是B的單鏈表)中的剩余結(jié)點，按序逐個創(chuàng)建新結(jié)點插入在單鏈表C的尾部多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）#ifndefPOLYNOMIAL_H_INCLUDED#definePOLYNOMIAL_H_INCLUDED#include"linklist.h"usingnamespacestd;多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）structType{intcoef;//系數(shù)intexp;//冪指數(shù)}template<classelemType>structNode{elemTypedata;Node*next;};分開定義結(jié)點的好處多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）template<classelemType>structPolynomial{private:Node<elemType>*head;elemTypestop_flag;//用于判斷多項式輸入結(jié)束。public://從用戶處獲取結(jié)束標(biāo)志并初始化多項式Polynomial(constelemType&stop);voidgetPoly();//讀入一個多項式。多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）voidaddPoly(constPolynomial&L1,constPolynomial&L2);

//L3=L1+l2。voiddispPloy();//顯示一個多項式voidclear();//釋放多項式空間~Polynomial(){clear();deletehead;};};多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）//getStop為外部函數(shù)，即非類成員函數(shù)template<classelemType>voidgetStop(elemType&stopFlag)//從用戶處獲取結(jié)束標(biāo)志{intc,e;cout<<"請輸入系數(shù)、指數(shù)對作為結(jié)束標(biāo)志,如(0,0):";cin>>c>>e;stopFlag.coef=c;stopFlag.exp=e;}多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）template<classelemType>Polynomial<elemType>::Polynomial(constelemType&stop)

//初始化多項式{head=newNode<elemType>();stop_flag.coef=stop.coef;stop_flag.exp=stop.exp;}

template<classelemType>voidPolynomial<elemType>::getPoly()//讀入一個多項式{Node<elemType>*p,*tmp;elemTypee;多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）p=head;cout<<“請按照指數(shù)從小到大輸入系數(shù)、指數(shù)對，”

<<最后輸入結(jié)束標(biāo)志對結(jié)束：\n";cin>>e.coef>>e.exp;

while(true){if((e.coef==stop_flag.coef)&&(e.exp==stop_flag.exp))break;多項式Polynomial及其部分基本操作的聲明、定義（polynomial.h）

tmp=newNode<elemType>();tmp->data.coef=e.coef;tmp->data.exp=e.exp;tmp->next=NULL;p->next=tmp;p=tmp;

cin>>e.coef