第3章-數(shù)據(jù)描述資料

第3章數(shù)據(jù)描述----初窺門徑：由第一種數(shù)據(jù)結(jié)構(gòu)線性表談起主要內(nèi)容基本概念線性表的描述與分析公式化描述（依次表示）鏈表描述（鏈?zhǔn)奖硎荆╅g接尋址線性表的應(yīng)用2數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)對象和實例以及構(gòu)成實例的每個元素之間所存在的各種關(guān)系。學(xué)習(xí)依次3ADT該數(shù)據(jù)結(jié)構(gòu)有什么特點？有哪些操作？C++實現(xiàn)可執(zhí)行的C++代碼是怎樣的？性能分析空間消耗如何？關(guān)鍵操作的時間性能如何？應(yīng)用用在什么地方？怎么用？線性表特征linear-list是最常用且最簡潔的一種數(shù)據(jù)結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列其中數(shù)據(jù)元素可以是各種各樣的，包括一個數(shù)、一個符號、一條記錄等同一線性表中的元素必定具有相同特性，即屬同一數(shù)據(jù)對象相鄰數(shù)據(jù)元素之間存在序偶關(guān)系4線性表實例形式：(e1,e2,…,en)n——有窮自然數(shù)，表的長度ei——表中元素，視為原子n=0，空表n>0，e1——第一個元素，en——最終一個元素el優(yōu)先于e2，e2優(yōu)先于e3，…—僅有的元素間關(guān)系5線性表舉例字母表(A,B,C,……,Z)奧斯卡近10年

最佳影片6年份片名2006Crash2007TheDeparted2008NoCountryforOldMen2009SlumdogMillionaire2010TheHurtLocker2011TheKing'sSpeech

2012TheArtist

2013Argo201412yearsaslave2015Birdman線性表操作創(chuàng)建一個線性表確定線性表是否為空確定線性表的長度查找第k個元素查找指定的元素刪除第k個元素在第k個元素之后插入一個新元素7數(shù)據(jù)是計算機的處理對象，也是計算機的關(guān)鍵所在。數(shù)據(jù)操作包括增、刪、改、查四種線性表之ADT8抽象數(shù)據(jù)類型LinearList{實例 0或多個元素的有序集合操作 Create()：創(chuàng)建一個空線性表 Destroy()：刪除表 IsEmpty()：假如表為空則返回true，否則返回false Length()：返回表的大小(即表中元素個數(shù))Find(k,x)：找尋表中第k個元素，并把它保存到x中；假如不存在，則返回false Search(x)：返回元素x在表中的位置；假如x不在表中，返回0 Delete(k,x)：刪除表中第k個元素，并把它保存到x中；函數(shù)返回修改后的線性表 Insert(k,x)：在第k個元素之后插入x；函數(shù)返回修改后的線性表 Output(out)：把線性表放入輸出流out之中}提出問題我們已經(jīng)知道了線性表應(yīng)當(dāng)是什么樣子的線性表應(yīng)當(dāng)具備哪些功能這些構(gòu)成了線性表的邏輯結(jié)構(gòu)接下來，一個自然而然的問題是線性表的物理結(jié)構(gòu)應(yīng)當(dāng)是怎樣的？9e1e2en主要內(nèi)容基本概念線性表的描述與分析公式化描述（依次表示）鏈表描述間接尋址線性表的應(yīng)用10H1.線性表的公式化描述公式化描述（依次存儲）用數(shù)組來描述線性表實例數(shù)組位置——單元（cell）、節(jié)點（node）每個數(shù)組單元保存線性表的一個元素11e1e2enC++類定義12template<classT>classLinearList{public:LinearList(intMaxListSize=10);//構(gòu)造函數(shù)

~LinearList(){delete[]element;}//析構(gòu)函數(shù)

boolIsEmpty()const{returnlength==0;}intLength()const{returnlength;}boolFind(intk,T&x)const;//返回列表的第k個元素

intSearch(constT&x)const;//返回x的位置

LinearList<T>&Delete(intk,T&x);//刪除第k個元素，將其保存在x中

LinearList<T>&Insert(intk,constT&x);//在第k個元素后插入x

voidOutput(ostream&out)const;private:intlength;intMaxSize;T*element;//一維動態(tài)數(shù)組};C++實現(xiàn)：創(chuàng)建和釋放template<classT>LinearList<T>::LinearList(intMaxListSize){//Constructorforformula-basedlinearlist.

MaxSize=MaxListSize;element=

newT[MaxSize];length=0;}~LinearList(){delete[]element;}13C++實現(xiàn)：Find(1~n)template<classT>boolLinearList<T>::Find(intk,T&x)const{//Setxtothek'thelementofthelist.//Returnfalseifnok'th;trueotherwise.if(k<1||k>length)returnfalse;//nok'thx=element[k-1];returntrue;}時間困難性：Θ(1)因其關(guān)鍵操作只有一條賦值語句14C++實現(xiàn)：Searchtemplate<classT>intLinearList<T>::Search(constT&x)const{//Locatex.Returnpositionofxiffound.//Return0ifxnotinlist.for(inti=0;i<length;i++)if(element[i]==x)return++i;return0;}時間困難性：Θ(length)15刪除元素——Delete刪除第k個元素k是否合法——OutOfBounds異樣，Θ(1)元素k+1,k+2,…,length向前移動一個位置——消退空位，Θ((length-k)s)Delete(2,x)16C++實現(xiàn)：Deletetemplate<classT>LinearList<T>&LinearList<T>::Delete(intk,T&x){

if(Find(k,x))//當(dāng)k是個合理的值時{

for(inti=k;i<length;i++)element[i-1]=element[i];length--;return*this;}elsethrowOutOfBounds();//當(dāng)k不是個合理的值時return*this;//visualneedsthis}17Θ((length-k)s)插入元素——Insert插入到第k個元素之后k是否合法——OutOfBounds異樣，Θ(1)另一種錯誤：表滿——數(shù)組無空間容納新元素，拋出NoMem異樣，Θ(1)常規(guī)狀況下，元素k+1,k+2,…,length向后移動一個位置

Θ((length-k)s)18插入操作示意Insert(3,7)19C++實現(xiàn)：Inserttemplate<classT>LinearList<T>&LinearList<T>::Insert(intk,constT&x){if(k<0||k>length)throwOutOfBounds();//k非法if(length==MaxSize)throwNoMem();//表空間滿for(inti=length-1;i>=k;i--)//常規(guī)狀況element[i+1]=element[i];element[k]=x;length++;return*this;}20C++實現(xiàn)：Outputtemplate<classT>voidLinearList<T>::Output(ostream&out)const{//Putthelistintothestreamout.

for(inti=0;i<length;i++)out<<element[i]<<"";}//overload<<template<classT>ostream&operator<<(ostream&out,constLinearList<T>&x){x.Output(out);returnout;}Θ(length)21運用示例創(chuàng)建一個大小為5的整數(shù)線性表L輸出該表的長度（0）在第0個元素之后插入2（表為2）在第一個元素之后插入6（表為2，6）找尋并輸出第一個元素（2）輸出表的長度（2）刪除并輸出第一個元素（6）22程序#include<iostream.h>#include"llist.h"#include"xcept.h“voidmain(void){try{LinearList<int>L(5);cout<<"Length="<<L.Length()<<endl;cout<<"IsEmpty="<<L.IsEmpty()<<endl;

L.Insert(0,2).Insert(1,6);cout<<"Listis"<<L<<endl;cout<<"IsEmpty="<<L.IsEmpty()<<endl;23程序（續(xù)）intz;L.Find(1,z);cout<<"Firstelementis"<<z<<endl;cout<<"Length="<<L.Length()<<endl;L.Delete(1,z);cout<<"Deletedelementis"<<z<<endl;cout<<"Listis"<<L<<endl;}catch(...){cerr<<"Anexceptionhasoccurred"<<endl;}}24評價空間效率低三個表，元素總數(shù)不超過5000個，但任何一個表的元素都可能達(dá)到5000個必需為每個表安排5000個元素的空間，共需15000個元素的空間提高空間效率思路：三個表共用一個數(shù)組兩個額外數(shù)組first[i]——第i個表的第一個元素在數(shù)組中的位置last[i]——第i個表最終一個元素在數(shù)組中的位置25多個表共享空間設(shè)置兩個虛擬邊界表first[0]=last[0]=-1first[m+1]=last[m+1]=MaxSize-1可使全部表的處理均相同，無需特殊處理表1和表m26新元素插入表i的位置k之后不僅要考慮表內(nèi)元素的移動，由于共享一個數(shù)組，還要考慮相鄰表的連接最好狀況：僅需表i內(nèi)部元素移動表i和i+1之間有空位：last[i]<first[i+1]，k+1~length后移一個位置表i-1和表i之間有空位：last[i-1]<first[i]，元素1~k-1前移一個位置27插入操作（續(xù)）需相鄰表移動的狀況表j-1~表j（j<i）之間有空位，表j~i-1前移表k~表k+1（k>i）之間有空位，表i+1~k后移效率差！為了改善空間困難性，搞壞了時間困難性28H1.線性表依次存儲小結(jié)常數(shù)級操作(Θ(1))IsEmptyLengthFind線性操作(Θ(n))----近似SearchDeleteInsertOutput29主要內(nèi)容基本概念線性表的描述與分析公式化描述鏈表描述間接尋址線性表的應(yīng)用30H2.線性表的鏈表描述與公式化描述的本質(zhì)區(qū)分：

數(shù)據(jù)結(jié)構(gòu)中的關(guān)聯(lián)元素不保證存儲空間上的關(guān)聯(lián)——定位O(1)O(n)節(jié)點內(nèi)容數(shù)據(jù)對象實例的元素為了正確定位，必需保留關(guān)聯(lián)節(jié)點的位置31線性表的鏈表描述線性表L=(e1,e2,…,en)每個元素ei放在不同節(jié)點的數(shù)據(jù)域內(nèi)僅有的結(jié)構(gòu)就是元素次序，“el優(yōu)先于e2，e2優(yōu)先于e3，…”——所謂“關(guān)聯(lián)”，就是下一個節(jié)點節(jié)點ei的鏈接域（指針域）保存指向節(jié)點ei+1的指針32線性表的鏈表描述（續(xù)）en的鏈接域設(shè)置為NULL（0）——無后繼節(jié)點——尾節(jié)點e1——首節(jié)點，沒有其他節(jié)點的鏈接域指向它，首指針——正確定位數(shù)據(jù)的關(guān)鍵！單向鏈表——鏈（chain）33鏈表節(jié)點：ChainNodetemplate<classT>classChainNode{friendChain<T>;friendChainIterator<T>;private:Tdata;//數(shù)據(jù)域ChainNode<T>*link;//鏈接域}34單向鏈表：Chaintemplate<classT>classChain{friendChainIterator<T>;public:Chain(){first=0;}~Chain();boolIsEmpty()const{returnfirst==0;}intLength()const;boolFind(intk,T&x)const;intSearch(constT&x)const;Chain<T>&Delete(intk,T&x);Chain<T>&Insert(intk,constT&x);voidOutput(ostream&out)const;private:ChainNode<T>*first;//首指針：特殊重要?。?！};運用鏈

Chain<int>L;35析構(gòu)函數(shù)：刪除鏈表中全部節(jié)點template<classT>Chain<T>::~Chain(){ChainNode<T>*next;//臨時變量，用于限制指針while(first){//當(dāng)下一個節(jié)點存在next=first->link;deletefirst;first=next;}}【繪圖演示】時間困難性Θ(n)資源，而非內(nèi)容36length操作——確定鏈表長度template<classT>intChain<T>::Length()const{ChainNode<T>*current=first;//臨時變量，用于限制指針intlen=0;while(current){len++;current=current->link;}returnlen;}時間困難性Θ(n)37查找操作template<classT>boolChain<T>::Find(intk,T&x)const{

if(k<1)returnfalse;ChainNode<T>*current=first;intindex=1;//用于與k比對

while(index<k&¤t){current=current->link;index++;}if(current){x=current->data;returntrue;}returnfalse;}找尋第k個元素

困難性為Θ(k)公式描述為Θ(1)狀況1：目標(biāo)非法，k過小狀況2：目標(biāo)合法，且存在狀況3：目標(biāo)非法，k過大38搜尋操作template<classT>intChain<T>::Search(constT&x)const{ChainNode<T>*current=first;intindex=1;//用于記錄x所在位置kwhile(current&¤t->data!=x){current=current->link;index++;}if(current)returnindex;return0;}困難性為Θ(n)公式描述也為Θ(n)39輸出函數(shù)template<classT>voidChain<T>::Output(ostream&out)const{ChainNode<T>*current;for(current=first;current;current=current->link)out<<current->data<<"";}template<classT>ostream&operator<<(ostream&out,constChain<T>&x){x.Output(out);returnout;}困難性為Θ(n)40刪除元素的方法找到前驅(qū)和后繼令前驅(qū)的鏈接域指向后繼釋放被刪除節(jié)點所占用的內(nèi)存空間41刪除操作的實現(xiàn)template<classT>Chain<T>&Chain<T>::Delete(intk,T&x){

if(k<1||!first)throwOutOfBounds();//k不合法或列表空

ChainNode<T>*p=first;//臨時變量，最終指向第k個元素

if(k==1)//刪除第一個元素

first=first->link;//令列表頭指向下一節(jié)點——刪除表頭狀況1：目標(biāo)非法，因其過小或表為空狀況2：目標(biāo)合法，刪第一個元素狀況3：目標(biāo)合法，刪其他元素狀況4：目標(biāo)非法，因其過大42刪除操作的實現(xiàn)else{//p獲得k-1個元素ChainNode<T>*q=first;for(intindex=1;index<k-1&&q;index++)q=q->link;//這句話是關(guān)鍵：指針右移?。?！if(!q||!q->link)throwOutOfBounds();//k>列表長度p=q->link;//k'thq->link=p->link;}//k-1項指向k+1項//釋放第k項占用的內(nèi)存空間x=p->data;deletep;return*this;}【繪圖演示】43插入元素的方法新節(jié)點插入在第k個元素的后面，O(k)k=0：新節(jié)點成為新的首節(jié)點，將它的link指向原首節(jié)點，而線性表的first指針指向新節(jié)點k≠0：令節(jié)點k的link域指向新節(jié)點，新節(jié)點的link指向原來的節(jié)點k+144插入操作的實現(xiàn)template<classT>Chain<T>&Chain<T>::Insert(intk,constT&x){if(k<0)throwOutOfBounds();

ChainNode<T>*p=first;//臨時變量，最終指向第k個元素

for(intindex=1;index<k&&p;index++)

p=p->link;

if(k>0&&!p)throwOutOfBounds();//k>列表長度狀況1：目標(biāo)非法，因其過小狀況2：目標(biāo)非法，因其過大狀況3：目標(biāo)合法，插入到表中或表后狀況4：目標(biāo)合法，插入到表頭【繪圖演示】45插入操作的實現(xiàn)（續(xù)）//insert

ChainNode<T>*y=newChainNode<T>;y->data=x;if(k){//插入p后面

y->link=p->link;//新元素指向原k+1項

p->link=y;} //第k項指向新元素

else{//插入第一個位置

y->link=first;//新元素指向原表頭

first=y;} //新元素作為新表頭

return*this;}這兩句話能互換依次嗎？46鏈表描述引出的新操作Erase：刪除鏈表全部節(jié)點，釋放內(nèi)存空間template<classT>voidChain<T>::Erase(){ChainNode<T>*next;while(first){next=first->link;deletefirst;first=next;}}47Zero操作清空列表，但不刪除任何節(jié)點，不釋放內(nèi)存空間，僅斷開first指針與鏈表節(jié)點的連接voidZero(){first=0;}48Append操作在鏈表末端添加一個元素新增一個數(shù)據(jù)成員last來跟蹤尾節(jié)點template<classT>Chain<T>&Chain<T>::Append(constT&x){

ChainNode<T>*y;y=newChainNode<T>;y->data=x;y->link=0;if(first){//chainisnotempty

last->link=y;last=y;}

else//chainisempty

first=last=y;

return*this;}49循環(huán)鏈表優(yōu)化操作實現(xiàn)的兩種鏈表形式單向循環(huán)鏈表（singlylinkedcircularlist），簡稱循環(huán)鏈表（circularlist）

——鏈表最終一個節(jié)點指向第一個節(jié)點鏈表前部附加一個頭節(jié)點（headnode）50兩種改進(jìn)形式的結(jié)構(gòu)51優(yōu)化的Search函數(shù)【帶頭節(jié)點】template<classT>intCircularList<T>::Search(constT&x)const{

ChainNode<T>*current=first->link;

intindex=1;

first->data=x;//關(guān)鍵：設(shè)置一個終止條件while(current->data!=x){current=current->link;index++;}

//areweathead?

return((current==first)?0:index);}52雙向鏈表每個節(jié)點兩個指針Left——指向前一節(jié)點Right——指向后一節(jié)點進(jìn)一步簡化代碼設(shè)計53雙向鏈表節(jié)點template<classT>classDoubleNode{friendDouble<T>;private:Tdata;DoubleNode<T>*left,*right;};54雙向鏈表類實現(xiàn)（續(xù)）template<classT>classDouble{public:Double(){LeftEnd=RightEnd=0;};~Double();intLength()const;boolFind(intk,T&x)const;intSearch(constT&x)const;Double<T>&Delete(intk,T&x);Double<T>&Insert(intk,constT&x);voidOutput(ostream&out)const;private:DoubleNode<T>*LeftEnd,*RightEnd;};雙向循環(huán)鏈表可省掉RightEnd55H2小結(jié)單向鏈表單向循環(huán)鏈表帶頭節(jié)點的單向循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表56H2小結(jié)（續(xù)）空間困難性公式化——空間全部用來保存列表元素

鏈表——額外空間保存鏈接指針鏈表——動態(tài)安排，占用空間與當(dāng)前列表大小成比例，利用率高

公式化——靜態(tài)安排，無法預(yù)料實際需求，奢侈或不足時間困難性插入、刪除操作，鏈表描述性能更好隨機訪問，公式化描述性能更優(yōu)57快速練習(xí)已知單向鏈表節(jié)點的定義，請寫出以下函數(shù)的C++實現(xiàn)~Chain();intLength()const;boolFind(intk,T&x)const;intSearch(constT&x)const;Chain<T>&Delete(intk,T&x);Chain<T>&Insert(intk,constT&x);58template<classT>classChainNode{friendChain<T>;private:Tdata;ChainNode<T>*link;}依次表VS單向鏈表59操作(ADT)順序表單向鏈表DestroyΘ(1)Θ(n)IsEmptyΘ(1)Θ(1)LengthΘ(1)Θ(n)FindΘ(1)Ο(k)SearchΟ(n)Ο(n)DeleteΟ((n-k)s)Ο(k)InsertΟ((n-k)s)Ο(k)OutputΘ(n)Θ(n)主要內(nèi)容基本概念線性表的描述與分析公式化描述鏈表描述間接尋址線性表的應(yīng)用60間接尋址元素的存儲——鏈接方式，動態(tài)存儲，通過指針訪問，連續(xù)元素存儲不連續(xù)指針的組織——公式化方式，連續(xù)元素的指針在存儲上是連續(xù)的61元素i的定位方式首先找到元素指針table[i-1]——公式化再由指針找到元素——多一次間接尋址鏈表描述：指針分散在節(jié)點中——類似超鏈接方式間接尋址：指針集中在數(shù)組中——類似書目索引方式62間接尋址列表類定義template<classT>classIndirectList{public:IndirectList(intMaxListSize=10);//constructor

~IndirectList();//destructor

boolIsEmpty()const{returnlength==0;}intLength()const{returnlength;}boolFind(intk,T&x)const;

intSearch(constT&x)const;Θ(1)，與公式化描述的實現(xiàn)特別相像63間接尋址列表類定義（續(xù)）

IndirectList<T>&Delete(intk,T&x);IndirectList<T>&Insert(intk,constT&x);

voidOutput(ostream&out)const;private:T**table;//1DarrayofTpointers

intlength,MaxSize;};64構(gòu)造函數(shù)和析構(gòu)函數(shù)template<classT>IndirectList<T>::IndirectList(intMaxListSize){//Constructor.

MaxSize=MaxListSize;table=newT*[MaxSize];length=0;}template<classT>IndirectList<T>::~IndirectList(){//Deletethelist.

for(inti=0;i<length;i++)deletetable[i];delete[]table;}數(shù)組保存元素指針，比元素所需空間少很多，可確定程度解決公式化描述的缺點65Find函數(shù)的實現(xiàn)template<classT>boolIndirectList<T>::Find(intk,T&x)const{//Setxtothek'thelementinthechain.//Returnfalseifnok'th;returntrueotherwise.if(k<1||k>length)returnfalse;//nok'thx=*table[k-1];returntrue;}Θ(1)，與公式化描述實現(xiàn)相像Find、Length、IsEmpty——隨機訪問（依據(jù)元素索引編號訪問）66刪除操作template<classT>IndirectList<T>&IndirectList<T>::Delete(intk,T&x){//Setxtothek'thelementanddeleteit.//ThrowOutOfBoundsexceptionifnok'thelement.

if(Find(k,x)){//movepointersk+1,...,down

for(inti=k;i<length;i++)table[i-1]=table[i];length--;return*this;}elsethrowOutOfBounds();return*this;//Visualneedsthisline}公式化：定位Θ(1)，刪除——元素移動Θ((length-k)s)

鏈表：定位Θ(k)，刪除Θ(1)間接：定位Θ(1)，刪除——指針移動Θ(length–k)67插入操作template<classT>IndirectList<T>&IndirectList<T>::Insert(intk,constT&x){//Insertxafterthek'thelement.if(k<0||k>length)throwOutOfBounds();if(length==MaxSize)throwNoMem();

//moveoneup

for(inti=length-1;i>=k;i--)table[i+1]=table[i];table[k]=newT;*table[k]=x;length++;return*this;}時間困難性類似刪除操作68間接尋址小結(jié)結(jié)合公式化描述和鏈表描述的優(yōu)點定位元素是Θ(1)其他多數(shù)操作也是Θ(1)，而不是Θ(n)！插入、刪除無需移動數(shù)據(jù)空間上接近鏈表，優(yōu)于公式化69幾種描述方法的比較間接尋址結(jié)合了公式化和鏈表的優(yōu)點，適用于表元素本身很大插入、刪除操作頻繁確定表長度、按編號訪問元素操作頻繁描述方法操作查找第k個元素刪除第k個元素插入第k元素后公式化Θ(1)O((n-k)s)O((n-k)s)鏈表O(k)O(k)O(k+s)間接尋址Θ(1)O(n-k)O(n-k)70主要內(nèi)容基本概念線性表的描述與分析公式化描述鏈表描述間接尋址線性表的應(yīng)用71箱子排序（binsort）班級學(xué)生信息——鏈表存儲按成果排序：O(n2)成果特點：0～5分，有限個箱子分?jǐn)?shù)，相同成果同一箱子箱子按依次連接按分?jǐn)?shù)排序72箱子排序例73箱子排序?qū)崿F(xiàn)方法箱子——鏈表排序方法逐個刪除鏈表每個節(jié)點，所刪除節(jié)點放入適當(dāng)?shù)南渥又校矗翰迦胂鄳?yīng)鏈表）收集并鏈接全部箱子，產(chǎn)生排序鏈表74箱子排序?qū)崿F(xiàn)方法輸入鏈表為Chain類型：連續(xù)地刪除鏈表首元素并將其插入到相應(yīng)箱子鏈表的首部逐個刪除每個箱子中的元素（從最終一個箱子起先）并將其插入到一個初始為空的鏈表的首部75鏈表數(shù)據(jù)域——Node類classNode{friendostream&operator<<(ostream&,constNode&);friendvoidBinSort(Chain<Node>&,int);public:intoperator!=(Nodex)const{return(score!=x.score);}private:intscore;char*name;};ostream&operator<<(ostream&out,constNode&x){out<<x.score<<'';returnout;}Chain類須要Node類支持這兩個操作76箱子排序?qū)崿F(xiàn)voidBinSort(Chain<Node>&X,intrange){//Sortbyscore.

intlen=X.Length();Nodex;Chain<Node>*bin;bin=newChain<Node>[range+1];

//以下部分為關(guān)鍵：將元素放入箱子

for(inti=1;i<=len;i++){X.Delete(1,x);bin[x.score].Insert(0,x);}元素的取值范圍77箱子排序?qū)崿F(xiàn)（續(xù)）for(intj=range;j>=0;j--)while(!bin[j].IsEmpty()){bin[j].Delete(1,x);X.Insert(0,x);}delete[]bin;}Delete操作——Θ(1)第一個循環(huán)Θ(n)，其次個循環(huán)Θ(n+range)總困難性Θ(n+range)78優(yōu)化：作為Chain類的成員函數(shù)干脆操縱Chain的數(shù)據(jù)成員【程序3-44】節(jié)點重復(fù)被多個鏈表運用，避開對new和delete的頻繁調(diào)用template<classT>voidChain<T>::BinSort(intrange){//Sb;//binindexChainNode<T>**bottom,**top;bottom=newChainNode<T>*[rang