數(shù)據(jù)結(jié)構(gòu)與算法線性表

·線性表的定義及ADT

·線性表的順序存儲結(jié)構(gòu)

·線性表的鏈接存儲結(jié)構(gòu)

·單向循環(huán)鏈表

·雙鏈表、雙向循環(huán)鏈表

·一元多項式的加法目錄第二章線性表1、線性表的定義及ADT1、線性結(jié)構(gòu)的定義：空或者只有一個結(jié)點?；蛘?、存在唯一的一個被稱之為”第一個“的結(jié)點。 2、存在唯一的一個被稱之為”最后一個“的結(jié)點。 3、除第一個結(jié)點之外，每個結(jié)點均只有一個前驅(qū)結(jié)點。 4、除最后一個結(jié)點之外，每個結(jié)點均只有一個后繼結(jié)點。分為以下幾大類：·線性表：進(jìn)通過它們之間的相對位置，確定它們之間的相互關(guān)系的線性結(jié)構(gòu)。 e.g:序列：a1、a2、a3…an-1、an·分類表·時間有序表·頻率有序表·序列2、結(jié)點或數(shù)據(jù)元素： 結(jié)點（數(shù)據(jù)元素）：由多個數(shù)據(jù)項構(gòu)成，每個數(shù)據(jù)項表示該結(jié)點的某種性質(zhì)。如：學(xué)生登記表中的每個學(xué)生結(jié)點，由學(xué)號、姓名、性別、系別……等構(gòu)成。 存放在外存中的結(jié)點通常稱之為記錄。1、線性表的定義及ADT3、線形表List的ADTADT2.1:線性表List的ADT Element:{xi|xiElemSet,i=1,2,3,……n,n>0}或

Φ;ElemSet為結(jié)點集合。 Relation:{<xi,xi+1>|xi,xi+1ElemSet,i=1,2,3,……n-1},x1為首結(jié)點，xn為尾結(jié)點。 Operations: Constructor

前提: 無或指定List的規(guī)模。

結(jié)果: 分配相應(yīng)空間及初始化。 Clear

前提: 無。

結(jié)果：

刪除表List中的所有結(jié)點并進(jìn)行初始化。 IsEmpty

前提：

無

結(jié)果：

表List為空返回True，否則返回False。 IsFull 前提：

無

結(jié)果：

表List為滿返回True，否則返回False。1、線性表的定義及ADT3、線形表List的ADT Length

前提：

無

結(jié)果：

返回表List中的結(jié)點個數(shù)。 Get

前提：

表List非空且已知結(jié)點序號無

結(jié)果：

返回相應(yīng)結(jié)點的數(shù)據(jù)值。 Prior 前提：

表List非空，已知結(jié)點序號且該結(jié)點非首結(jié)點。

結(jié)果：

返回其直接前驅(qū)結(jié)點的序號。 Next 前提：

表List非空，已知結(jié)點序號且該結(jié)點非尾結(jié)點

結(jié)果：

返回其直接后繼結(jié)點的序號。 Find 前提：

表List非空，已知結(jié)點的數(shù)據(jù)值。 結(jié)果：

查找成功，返回相應(yīng)結(jié)點序號，否則返回查找失敗標(biāo)志 Insert 前提：

已知待插入的數(shù)據(jù)值以及插入位置。 結(jié)果：

插入具有該數(shù)據(jù)值的結(jié)點，表List的結(jié)點個數(shù)增大1。 Delete 前提：

表List非空，已知被刪結(jié)點的數(shù)據(jù)值。 結(jié)果：

首先查找相應(yīng)結(jié)點，查找成功則刪除該結(jié)點，表List的結(jié)點個數(shù)將減少1。否則返回刪除失敗標(biāo)志。2、線性表的順序存儲結(jié)構(gòu)1、物理存儲位置的計算： ·順序表示：在物理位置上緊靠在一起。如用數(shù)組表示線性表。 ·設(shè)第一個結(jié)點的存儲地址為LOC(a0),余類推。設(shè)每個結(jié)點占用L個單元。則：an－1ai-1a1a0ai

LOC(ai) =LOC(ai-1)+L =LOC(ai-2)+2L =LOC(ai-i)+i*L =LOC(a0)+i*L ·隨機存?。涸L問任何一個數(shù)據(jù)元素或結(jié)點花費同樣多時間。2、線性表的順序存儲結(jié)構(gòu)template<classElemType>classSeqList{private:ElemType*elem;//順序表存儲數(shù)組，存放實際的數(shù)據(jù)結(jié)點。

intlength;//順序表中的結(jié)點個數(shù)，亦稱表的長度。intMaxSize; //順序表的的最大可能的長度。

public:SeqList(intInitSize); //構(gòu)造函數(shù)~SeqList(); //析構(gòu)函數(shù)

voidClear(); //清空順序表boolIsEmpty()const{return(length==0);} //表為空返回TRUE,否則返回FALSE。boolIsFull()const{return(length==MaxSize)};//表是否已經(jīng)滿，滿則返回TRUE，否則FALSE。intLength()const;//表的長度ElemTypeGet(inti)const; //返回第i個結(jié)點的值intNext(inti)const;//若第i個結(jié)點的直接后繼結(jié)點存在，返回其下標(biāo)，//否則返回0intPrior(inti)const;//若第i個結(jié)點的直接前驅(qū)結(jié)點存在，返回其下標(biāo)， //否則返回0

intFind(ElemTypee);//返回值等于e的結(jié)點的序號，無則返回02、線性表的順序存儲結(jié)構(gòu)template<classElemType>classSeqList{

….

intFind(ElemTypee);//返回值等于e的結(jié)點的序號，無則返回0intInsert(inti,constElemType&e);//在第i個位置上插入新的結(jié)點（值為e），并//使原來的第i個結(jié)點至最后一個結(jié)點的序號依次加1。//插入成功返回1，否則為0intDelete(ElemType&e,inti);//若第i個結(jié)點存在，刪除并將其值放入e, //若i非法，則刪除失敗，返回0。};

注意：本處慣例，0號單元不用。Length既是順序表的當(dāng)前結(jié)點個數(shù)，同時又是尾結(jié)點的指針。2、線性表的順序存儲結(jié)構(gòu)2、主要函數(shù)的實現(xiàn) ·順序表的創(chuàng)建：template<classElemType>SeqList<ElemType>::SeqList(intInitSize){ //構(gòu)造函數(shù)if(InitSize>0){elem=newElemType[InitSize];//申請連續(xù)空間，返回空間首地址。Exception(!elem,”thereisnospaceinmemory”)//若申請空間失敗，則程序中斷。length=0;MaxSize=InitSize-1; }}251247998936length2、線性表的順序存儲結(jié)構(gòu) ·查找及其分析：成功查找的情況template<classElemType>intSeqList<ElemType>::Find(ElemTypee){//按照下標(biāo)從大到小順序查找值為e的數(shù)組結(jié)點的下標(biāo)并將其返回。//elem[0]做哨兵用,保證即使查找失敗，也可以在哨兵位上能找到值e。elem[0]=e;inti=length;//初始位置為尾結(jié)點所在下標(biāo)while(elem[i]!=e)i--;//不等時繼續(xù)向前比較，找到返回結(jié)點下標(biāo)，否則返回0。returni; }成功查找時的平均比較次數(shù)：等概率情況,n為表中結(jié)點數(shù)

∑(n-i+1)/n=(n+1)/2時間復(fù)雜性為O(n)。i=n12、主要函數(shù)的實現(xiàn)251247998936length2、線性表的順序存儲結(jié)構(gòu)3、插入和刪除的時間復(fù)雜性分析： ·插入（插如之后成為第i個結(jié)點，注意從第1個結(jié)點開始）：124789361401234567899插入 ·如圖99插入之后成為第3個結(jié)點，移動5－（3－1）次。 在一般情況下，插入之后成為第i個結(jié)點，移動n-(i-1)=n-i+1次。template<classElemType>intSeqList<ElemType>::Insert(inti,constElemType&e){ //在位置i上插入一個值為e的結(jié)點，原來的第i個結(jié)點變?yōu)榈?/i+1個結(jié)點，其余后繼結(jié)點序號同樣加1，插入成功返回1。Exception((i<1)||(i>length+1),”iisnotcorrect.”);//插入位置i不合法Exception(MaxSize==length,”nospacefornewitem.”);//存儲空間已經(jīng)滿了，無法插入。//從尾結(jié)點起到第i個結(jié)點逐個向后移動一個位置for(intj=length;j>=i;j--)elem[j+1]=elem[j];elem[i]=e; //將要插入的結(jié)點值放入第i個結(jié)點的位置length++; //順序表結(jié)點個數(shù)加1return1; //插入成功返回1}lengtht2、線性表的順序存儲結(jié)構(gòu)3、插入和刪除的時間復(fù)雜性分析：124789361401234567812479989361499插入124789361412478936141247893614 ·插入（插如之后成為第i個結(jié)點，注意從第1個結(jié)點開始）： ·如圖99插入之后成為第3個結(jié)點，移動5－（3－1）次。 在一般情況下，插入之后成為第i個結(jié)點，移動n-(i-1)=n-i+1次。2、線性表的順序存儲結(jié)構(gòu)3、插入和刪除的時間復(fù)雜性分析： ·插入后成為第3個結(jié)點，移動5－（3－1）次。

在一般情況下，插入后成為第i個結(jié)點，移動n-i+1)次 插入后成為第1個結(jié)點，移動n次 插入后成為第i個結(jié)點，移動n-i+1次 插入后成為第n個結(jié)點，移動1次。 插入后成為第n＋1個結(jié)點，移動0次。總共n+1種情況 ·在長度為n的線性表中插入一個結(jié)點的平均次數(shù)為：

∑(n-i+1)/(n+1)=n/2時間復(fù)雜性為O(n)。i=1n+12、線性表的順序存儲結(jié)構(gòu)3、插入和刪除的時間復(fù)雜性分析： ·刪除：1247893614012345678 ·如圖結(jié)點的數(shù)據(jù)值為89的結(jié)點刪除將移動5－3次。 在一般情況下，刪除第i個結(jié)點，移動n-1次。template<classElemType>intSeqList<ElemType>::Delete(ElemType&e,inti){//若第i個結(jié)點存在，刪除并將其值放入e,若i非法，刪除失敗。Exception((i<1)||(i>length),”iisillgeal.”);e=elem[i];//將第i個結(jié)點值首先讀出，用于返回。for(intj=i;j<length;j++)elem[j]=elem[j+1];//第i+1個結(jié)點到尾結(jié)點逐個前移。length--; //表長度減1。returni; //返回成功標(biāo)志i。}length刪除892、線性表的順序存儲結(jié)構(gòu)3、插入和刪除的時間復(fù)雜性分析： ·刪除（刪除線性表的第i個結(jié)點）：1247893614012345678124736141247361412473614刪除2、線性表的順序存儲結(jié)構(gòu)3、插入和刪除的時間復(fù)雜性分析： ·刪除第3個結(jié)點，移動5-3次。

在一般情況下，刪除第i個結(jié)點，移動n-i次

刪除第1個結(jié)點，移動n-1次 刪除第i個結(jié)點，移動n-i次 刪除第n個結(jié)點，移動0次?？偣瞡種情況 ·在長度為n的線性表中刪除一個結(jié)點的平均次數(shù)為：

∑(n-i)/n=(n-1)/2時間復(fù)雜性為O(n)。i=1n ·另外，通過數(shù)據(jù)場之值x查找結(jié)點，代價O(n)。

查找第i個結(jié)點，代價O(1)。3、線形表的鏈接存儲結(jié)構(gòu)1、單鏈接表：通常用于表示線性結(jié)構(gòu)，如：線性表·結(jié)點的表示：參照下圖所示的情況：ElementNext·單鏈接表的表示：參照下圖所示的情況：其中head是表首指針?！腅lementNextheadABZ∧headABZ頭結(jié)點：不是線性表之中的結(jié)點。但增加此結(jié)點后，操作容易。Element:數(shù)據(jù)場－通常用于保存結(jié)點的數(shù)據(jù)元素或數(shù)據(jù)值Next:指針場－給出直接后繼結(jié)點的地址3、線形表的鏈接存儲結(jié)構(gòu)1、單鏈接表、雙鏈表和雙向循環(huán)鏈表及其初始化。3、線形表的鏈接存儲結(jié)構(gòu)鏈表的ADT（抽象數(shù)據(jù)類型）鏈表類AbsList的定義ADT2.2鏈表類

AbsList的定義。template<classElemType>classAbsList{public:AbsList(){}; //構(gòu)造函數(shù) virtual~AbsList(){} //析構(gòu)函數(shù) virtualIsEmpty()const=0;//判表空嗎？ virtualIsFull()const=0;//判表滿嗎？ virtualvoidMakeEmpty()=0;//將表清空。 firiendclassAbsListItr<ElemType>;private: AbsList(constAbsList&){}//凍結(jié)復(fù)制另一鏈表的構(gòu)造函數(shù)。}；3、線形表的鏈接存儲結(jié)構(gòu)鏈表類迭代器類AbsList的定義ADT2.3鏈表迭代器類

AbsListItr的定義。template<classElemType>classAbsListItr{public: AbsListItr(constAbsList<ElemType>&L){}//構(gòu)造函數(shù)。 AbsListItr(constAbsListItr&);

//通過復(fù)制構(gòu)造當(dāng)前迭代器。 virtual~AbsListItr(){} //析構(gòu)函數(shù) //以下函數(shù)是基本數(shù)據(jù)操縱類成員函數(shù)。 virtualvoidInsert(constElemType&x)=0;//插入在當(dāng)前結(jié)點(值為x)之后。 virtualintRemove(constElemType&x)=0;//刪除值為x的結(jié)點。 virtualintFind(constElemType&x)=0;//查找值為x的結(jié)點。 virtualintIsFound(constElemType&x)const=0;//查找值為x的結(jié)點成功否。 //訪問當(dāng)前結(jié)點運算符。 virtualintoperator+()const=0;//判當(dāng)前結(jié)點存在嗎？ virtualconstElemType&operator()()const=0;//取當(dāng)前結(jié)點內(nèi)容。 //定位運算符及函數(shù)。 virtualvoidZeroth()=0;//定位于鏈表的首結(jié)點之前。 virtualvoidFirst()=0;//定位于鏈表的首結(jié)點。 virtualvoidoperator++()=0;//定位于鏈表的下一個結(jié)點。 virtualvoidoperator++(int)=0;//定位于鏈表的下一個結(jié)點。protected: AbsListItr(){}//凍結(jié)無參的構(gòu)造函數(shù)。}；請改正書上這行！3、線形表的鏈接存儲結(jié)構(gòu)單鏈接表、基本操作及迭代器的實現(xiàn)。·結(jié)點類的定義：ElementNextElement:數(shù)據(jù)場－通常用于保存結(jié)點的數(shù)據(jù)元素或數(shù)據(jù)值。Next:指針場－給出直接后繼結(jié)點的地址。程序2.5單鏈表結(jié)點類。template<classElemType>classList; //單鏈表類的向前說明。template<classElemType>classListItr; //單鏈表迭代器類的向前說明。template<classElemType>classListNode{ friendclassList<ElemType>; //單鏈表類為其友元類,便于訪問結(jié)點類中的私有成員。friendclassListItr<ElemType>;//單鏈表迭代器類為其友元類,便于訪問結(jié)點類中的私有成員。private: ListNode<ElemType>*Next;//指向下一個結(jié)點的指針。 ElemTypeElement; //結(jié)點數(shù)據(jù)。public: ListNode(constElemType&E,ListNode<ElemType>*N=NULL) :Element(E),Next(N){} //構(gòu)造函數(shù) ListNode():Next(NULL){} //構(gòu)造函數(shù) ~ListNode(){}; //析構(gòu)函數(shù)};3、線形表的鏈接存儲結(jié)構(gòu)單鏈接表、基本操作及迭代器的實現(xiàn)?！捂溄颖眍悾篍lementNext程序2.6:單鏈表類。template<classElemType>classListItr; //單鏈表迭代器類的向前說明。template<classElemType>classList:publicAbsList<ElemType>{ friendclassListItr<ElemType>;//單鏈表迭代器類為其友元類。private:ListNode<ElemType>*head;//指向頭結(jié)點的指針。public:List(){head=newListNode<ElemType>();}~List(){MakeEmpty();deletehead;} //析構(gòu)函數(shù)constList&operator=(constList&R);//完成復(fù)制功能。intIsEmpty()const{returnhead->Next==NULL;}intIsFull()const{return0;}voidMakeEmpty();};3、線形表的鏈接存儲結(jié)構(gòu)單鏈接表、基本操作及迭代器的實現(xiàn)。迭代器類：ElementNext程序2.7:迭代器類。template<classElemType>classListItr:publicAbsListItr<ElemType>{ private: ListNode<ElemType>*consthead; //指向頭結(jié)點的常指針。 ListNode<ElemType>*Current; //指向當(dāng)前結(jié)點的指針。public: ListItr(constList<ElemType>&L):head(L.head) {Current=L.IsEmpty()?head:head->Next;} ~ListItr(){} //析構(gòu)函數(shù) intFind(constElemType&x); //查找值為x的結(jié)點，查找成功則使其成為當(dāng)前結(jié)點，并返回True。 intIsFound(constElemType&x)const;//查找值為x的結(jié)點，查找成功返回//True，否則返回False;不改變指針Current的值。 voidInsert(constElemType&x);//插入成功，新結(jié)點成為當(dāng)前結(jié)點。 intRemove(constElemType&x);//刪除值為x的結(jié)點的操作。

3、線形表的鏈接存儲結(jié)構(gòu)單鏈接表、基本操作及迭代器的實現(xiàn)。迭代器類：ElementNext程序2.7:迭代器類（續(xù)）。 ………… intoperator+()const{returnCurrent&&Current!=head;} //當(dāng)前結(jié)點非空則返回True。 constElemType&operator()()const; //取當(dāng)前結(jié)點的數(shù)據(jù)值。 voidoperator++(); //使當(dāng)前結(jié)點的直接后繼結(jié)點成為當(dāng)前結(jié)點。 voidoperator++(int){operator++();}//定義為前綴++運算符。 voidZeroth(){Current=head;}//當(dāng)前指針指向頭結(jié)點。 voidFirst(); //當(dāng)前指針指向首結(jié)點。 constListItr&operator=(constListItr&);//賦值運算符。};3、線形表的鏈接存儲結(jié)構(gòu)CurrentBATmpx單鏈接表結(jié)點類、基本操作及迭代器的實現(xiàn)?！げ迦氩僮鞯膶崿F(xiàn)：將新結(jié)點插入到當(dāng)前結(jié)點（指針Current指向的結(jié)點）之后。Tmp=newListNode();Tmp->Element=x;3、線形表的鏈接存儲結(jié)構(gòu)CurrentBATmpx2.

Current->Next=Tmp注意：1、2不可顛倒，否則鏈表將脫鏈。時間代價：O(1)可用一個語句取代上述操作，即：Current->Next=newListNode(x,Current->Next);

·插入操作的實現(xiàn)：將新結(jié)點插入到當(dāng)前結(jié)點（指針Current指向的結(jié)點）之后。1.Tmp->Next=Current->Next·指針p和指向的對象的關(guān)系：·程序語句：p->next->next->next->pbacElementNext·指針pp->指針p指向的對象(結(jié)點)p->nextp->next->p->next->nextp->next->next->3、線形表的鏈接存儲結(jié)構(gòu)·刪除：刪除Current所指向的結(jié)點之后繼結(jié)點。要知被刪結(jié)點的前驅(qū)結(jié)點的地址CurrentCurrentbacpp=Current->Next3、線形表的鏈接存儲結(jié)構(gòu)·刪除：刪除Current所指向的結(jié)點之后繼結(jié)點。要知被刪結(jié)點的前驅(qū)結(jié)點的地址CurrentCurrentbacpCurrent->Next=p->Next;3、線形表的鏈接存儲結(jié)構(gòu)·刪除：刪除Current所指向的結(jié)點之后繼結(jié)點。要知被刪結(jié)點的前驅(qū)結(jié)點的地址CurrentCurrentacdeletep;注意：必須釋放p->。時間O(1)。養(yǎng)成良好的程序設(shè)計習(xí)慣。3、線形表的鏈接存儲結(jié)構(gòu)·和順序存儲的線性表的操作的比較：插入：O(1)刪除：O(1)FINDith:O(i)平均O(n)FINDkey:平均O(n)插入：O(n)刪除：O(n)FINDith:O(1)FINDkey:平均O(n)單鏈表順序存儲的線性表3、線形表的鏈接存儲結(jié)構(gòu)·在迭代器中，基本操作的實現(xiàn)template<classElemType>classListItr:publicAbsListItr<ElemType>{private:

ListNode<ElemType>*consthead;//指向頭結(jié)點的常指針。 ListNode<ElemType>*Current;//指向當(dāng)前結(jié)點的指針。public: ListItr(constList<ElemType>&L):head(L.head) {Current=L.IsEmpty()?head:head->Next;} ~ListItr(){}//析構(gòu)函數(shù) intFind(constElemType&x); //查找值為x的結(jié)點，查找成功則使其成為當(dāng)前結(jié)點，并返回True。

intIsFound(constElemType&x)const; //查找值為x的結(jié)點，查找成功返回True，否則返回False;不改變指 //針Current的值。

voidInsert(constElemType&x);//插入成功，新結(jié)點成為當(dāng)前結(jié)點。

intRemove(constElemType&x);//刪除值為x的結(jié)點的操作。

……………….};3、線形表的鏈接存儲結(jié)構(gòu)·在迭代器中，基本操作Find和IsFound的實現(xiàn)template<classElemType>intListItr<ElemType>::Find(constElemType&x){ListNode<ElemType>*Ptr=head->Next;while(Ptr!=NULL&&!(Ptr->Element==x))Ptr=Ptr->Next;if(

Ptr==NULL)return0;Current=Ptr;return1;}template<classElemType>intListItr<ElemType>::IsFound(constElemType&x)const{ListNode<ElemType>*Ptr=head->Next;while(Ptr!=NULL&&!(Ptr->Element==x))Ptr=Ptr->Next;returnPtr!=NULL;}3、線形表的鏈接存儲結(jié)構(gòu)·在迭代器中，基本操作Inser和Delete的實現(xiàn)template<classElemType>voidListItr<ElemType>::Insert(constElemType&x){//插入操作。Exception(Current==NULL,“Thelocationisillegal!”);ListNode<ElemType>*p;p=newListNode<ElemType>(x,Current->Next);Current=Current->Next=p;}template<classElemType>intListItr<ElemType>::Remove(constElemType&x){ListNode<ElemType>*Ptr=head;while(Ptr->Next!=NULL&&!(Ptr->Next->Element==x))Ptr=Ptr->Next;if(

Ptr->Next==NULL)return0;//未找到數(shù)據(jù)值為x的結(jié)點，刪除失敗。ListNode<ElemType>*P=Ptr->Next;Ptr->Next=Ptr->Next->Next;deleteP;Current=head;return1;}

3、線形表的鏈接存儲結(jié)構(gòu)·在迭代器中，基本操作Inser和Delete的實現(xiàn)程序2.8:類List的賦值運算符=的實現(xiàn)。template<classElemType>constList<ElemType>&List<ElemType>::

operator=(constList<ElemType>&R){if(this==&R)return*this; //同一單鏈表，不必賦值。MakeEmpty(); //清空單鏈表。ListItr<ElemType>Itr(*this);for(ListItr<ElemType>Ritr(R);+Ritr;Ritr++)Itr.Insert(Ritr()); //根據(jù)單鏈表R的結(jié)點數(shù)據(jù)值，創(chuàng)建新結(jié)點，并插入到當(dāng)前鏈表。return*this;}4、單向循環(huán)鏈表head

……

head

2、帶頭結(jié)點的單向循環(huán)鏈表的初態(tài)1、帶頭結(jié)點的單向循環(huán)鏈表帶頭結(jié)點的單向循環(huán)鏈表head

……

head＝NULL2、不帶頭結(jié)點的單向循環(huán)鏈表的初態(tài)1、不帶頭結(jié)點的單向循環(huán)鏈表不帶頭結(jié)點的單向循環(huán)鏈表4、單向循環(huán)鏈表

tail

……

tail＝NULL2、不帶頭結(jié)點的單向循環(huán)鏈表的初態(tài)1、不帶頭結(jié)點的單向循環(huán)鏈表不帶頭結(jié)點的單向循環(huán)鏈表（使用尾指針）5、雙鏈表、雙向循環(huán)鏈表

tailhead

A

B

C

tailhead

(1).帶頭結(jié)點和最后一個結(jié)點的雙鏈表初始化headBCDA(2).雙向循環(huán)鏈表的一種實現(xiàn)方案head=NULL;初始化PriorElementNextPriorElementNext5、雙鏈表、雙向循環(huán)鏈表·刪除：給出待刪結(jié)點的地址就可以把它刪除。如；刪除數(shù)據(jù)場之值為a的結(jié)點，地址由 current給出。headabCurrentctailheadabCurrentctailheadabCurrentctail執(zhí)行：Current->Prior->Next=current->Next;后執(zhí)行：Current->Next->Prior=Current->Prior;后

最后執(zhí)行：deleteCurrent;將結(jié)點刪除。5、雙鏈表、雙向循環(huán)鏈表·插入：注意插入次序。如：將數(shù)據(jù)場為x的結(jié)點，插在當(dāng)前結(jié)點之后。headabctailxheadabCurrentctailxheadabctailx·p->prior=Current;·p->Next=Current->Next;CurrentCurrentppp·Current->Next->prior=p;·Current->Next=p;6、一元多項式的加法一元多項式的表示及相加；StructTerm{floatcoef;intexp;Term(intc,inte){coef=c;exp=e;}

…………}; ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8AH703198517BH81227-98∧∧coefexplinkCH70111227517∧6、一元多項式的加法一元多項式的表示及相加； ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點都刪除。pa、pb后移。 否則將相加后的系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa、pb后移。 pa->指數(shù)?。簩⑾禂?shù)、及相應(yīng)指數(shù)送入單鏈表C,pa后移。 pa->指數(shù)大：將鏈表B系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pb后移。 注意：將任何一個多項式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70∧coefexpnNext6、一元多項式的加法一元多項式的表示及相加； ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點都刪除。pa、pb后移。 否則將相加后的系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa、pb后移。 pa->指數(shù)?。簩⑾禂?shù)、及相應(yīng)指數(shù)送入單鏈表C,pa后移。 pa->指數(shù)大：將鏈表B系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pb后移。 注意：將任何一個多項式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111coefexpnNext∧6、一元多項式的加法一元多項式的表示及相加； ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點都刪除。pa、pb后移。 否則將相加后的系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa、pb后移。 pa->指數(shù)?。簩⑾禂?shù)、及相應(yīng)指數(shù)送入單鏈表C,pa后移。 pa->指數(shù)大：將鏈表B系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pb后移。 注意：將任何一個多項式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111227coefexpnNext∧6、一元多項式的加法一元多項式的表示及相加； ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點都刪除。pa、pb后移。 否則將相加后的系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa、pb后移。 pa->指數(shù)小：將系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa后移。 pa->指數(shù)大：將鏈表B系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pb后移。 注意：將任何一個多項式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111227∧coefexpnNext6、一元多項式的加法一元多項式的表示及相加； ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點都刪除。pa、pb后移。 否則將相加后的系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa、pb后移。 pa->指數(shù)小：將系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pa后移。 pa->指數(shù)大：將鏈表B系數(shù)、及相應(yīng)指數(shù)送入單鏈表C,pb后移。 注意：將任何一個多項式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111227517∧coefexpnNext ·注意：本書的程序?qū)崿F(xiàn)時，對單鏈表使用了帶有表頭的表示方法。另外，使用了 迭代器(本書稱之為游標(biāo)類)。迭代器是一種“指針”抽象。6、一元多項式的加法一元多項式的表示及相加；程序的實現(xiàn) ·如：多項式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8AH703198517BH81227-98∧∧coefexplinkCH70111227517∧coefexplinkmain(){TermR(-1,-1);//多項式輸入的結(jié)束標(biāo)志。Polynomial<Term>a(R),b(R),c;cin>>a>>b;// 讀入2個多項式，通過對>>重載實現(xiàn)。c=a; //多項式a并不破壞，將其值送入c。c+b; //完成多項式c、b相加，結(jié)果保存在多項式c之中。cout<<c;//將多項式c輸出。return0;}template<classElemType>classPolynomial{public:Polynomial(constElemType&P){Stop_flag=P;}Polynomial(){}~Polynomial(){}Polynomial&operator=(constPolynomial&T);Polynomial&operator+(constPolynomial&T);friendistream&operator>>(istream&is,Polynomial<ElemType>&T);friendostream&operator<<(ostream&os,constPolynomial<ElemType>&T);private:List<ElemType>poly;

ElemTypeStop_flag;//用于判斷多項式輸入結(jié)束。};StructTerm{floatcoef;intexp;Term(intc,inte){coef=c;exp=e;}…………};6、一元多項式的加法template<classElemType>Polynomial<ElemType>&Polynomial<ElemType>::operator+(constPolynomial<ElemType> &T) { ElemTypeelemA,elemB; Polynomial<ElemType>C; ListItr<ElemType>ItrA(poly); ListItr<ElemType>ItrB(T.poly); ListItr<ElemType>ItrC(C.poly);

for(;+ItrA&&+ItrB;){ elemA=ItrA();elemB=ItrB();

switch(compare(elemA,elemB)){

case‘=’: elemA+=elemB;

if(!Is_Empty(elemA))ItrC.Insert(elemA); ++ItrA;++ItrB;

break;

case‘>’: ItrC.Insert(elemB);++ItrB;break;

case‘<’: ItrC.Insert(elemA);++ItrA;break; } }

if(+ItrA)for(;+ItrA;++ItrA){elemA=ItrA();ItrC.Insert(elemA);}

else

for(;+ItrB;++ItrB){elemB=ItrB();ItrC.Insert(elemB);} *this=C;return*this;}papc

3198517∧pbp

1312527∧7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣·靜態(tài)鏈表的實現(xiàn)： 用于沒有動態(tài)存儲分配功能的語言，如FORTRAN、COBOL等；當(dāng)然也可用于C/c++ 等高級語言。缺點：必須預(yù)估存區(qū)的大小，造成浪費。優(yōu)點：插、刪操作省時?！.g:設(shè)集合A=(c,b,e,g,f,d)和B=(a,b,n,f)。求集合運算(A－B)∪(B－A)的結(jié) 果。解：A－B=(c,e,g,d);B－A=(a,n)。(A－B)∪(B－A)=(c,e,g,d,a,n)。程序執(zhí)行步驟： 1、將用作存儲空間的數(shù)組的所有單元分配至可利用空間表(也稱：空閑?；騻?用鏈(保存未被使用的結(jié)點的單鏈表)。 2、建立集合A的靜態(tài)鏈表。 3、逐個輸入集合B的元素，同時查找A的靜態(tài)鏈表有無該元素。有則刪 除，無則插入該結(jié)點。 4、集合B的元素輸入完畢，則在原集合A的靜態(tài)鏈表中得到了集合運算 (A－B)∪(B－A)的結(jié)果。7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。datacurspace[0]space[1]space[2]space[3]space[4]space[5]space[6]space[7]space[8]space[9]space[10]space[11]datacur1234567891011-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈經(jīng)初始化之后的情況：注意此處的地址是下標(biāo)地址。10234567891011datacurvoidInitSpace_SL(SLinkList&Space){for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1]=-1;}intMalloc_SL(SLinkList&Space){i=space[0].cur;if(space[0].cur!=-1);space[0].cur=space[i].cur;returni;}intfree_SL(SLinkList&Space,intk){space[k].cur=space[0].cur;space[0].cur=k;}10234567891011datacur1234567891011 ·為了形象起見，和動態(tài)分配的單鏈表表示相似，備用鏈初 始化之后通常表示成以下形式。-1-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表的初始化。0234567891011datacur10s工作鏈：備用鏈：-1-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素c之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rc7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面湣?·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素b之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcb7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑棧或備用鏈。 ·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素e之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbe7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素g之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbeg7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面湣?·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素f之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbegf7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面湣?·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素d之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbegfd7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 3、逐個輸入集合B的元素。 ·輸入a,查找A的靜態(tài)鏈表。a不在，插入。0234567891011datacur10s工作鏈：備用鏈：rcbegfda-1-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫成以下圖形：注意此處的地址