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

·線(xiàn)性表的定義及ADT

·線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)

·線(xiàn)性表的鏈接存儲(chǔ)結(jié)構(gòu)

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

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

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

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

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

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

前提: 無(wú)。

結(jié)果：

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

前提：

無(wú)

結(jié)果：

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

無(wú)

結(jié)果：

表List為滿(mǎn)返回True，否則返回False。1、線(xiàn)性表的定義及ADT3、線(xiàn)形表List的ADT Length

前提：

無(wú)

結(jié)果：

返回表List中的結(jié)點(diǎn)個(gè)數(shù)。 Get

前提：

表List非空且已知結(jié)點(diǎn)序號(hào)無(wú)

結(jié)果：

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

表List非空，已知結(jié)點(diǎn)序號(hào)且該結(jié)點(diǎn)非首結(jié)點(diǎn)。

結(jié)果：

返回其直接前驅(qū)結(jié)點(diǎn)的序號(hào)。 Next 前提：

表List非空，已知結(jié)點(diǎn)序號(hào)且該結(jié)點(diǎn)非尾結(jié)點(diǎn)

結(jié)果：

返回其直接后繼結(jié)點(diǎn)的序號(hào)。 Find 前提：

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

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

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

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

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

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

LOC(ai) =LOC(ai-1)+L =LOC(ai-2)+2L =LOC(ai-i)+i*L =LOC(a0)+i*L ·隨機(jī)存取：訪(fǎng)問(wèn)任何一個(gè)數(shù)據(jù)元素或結(jié)點(diǎn)花費(fèi)同樣多時(shí)間。2、線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)template<classElemType>classSeqList{private:ElemType*elem;//順序表存儲(chǔ)數(shù)組，存放實(shí)際的數(shù)據(jù)結(jié)點(diǎn)。

intlength;//順序表中的結(jié)點(diǎn)個(gè)數(shù)，亦稱(chēng)表的長(zhǎng)度。intMaxSize; //順序表的的最大可能的長(zhǎng)度。

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)滿(mǎn)，滿(mǎn)則返回TRUE，否則FALSE。intLength()const;//表的長(zhǎng)度ElemTypeGet(inti)const; //返回第i個(gè)結(jié)點(diǎn)的值intNext(inti)const;//若第i個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)存在，返回其下標(biāo)，//否則返回0intPrior(inti)const;//若第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)存在，返回其下標(biāo)， //否則返回0

intFind(ElemTypee);//返回值等于e的結(jié)點(diǎn)的序號(hào)，無(wú)則返回02、線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)template<classElemType>classSeqList{

….

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

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

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

在一般情況下，插入后成為第i個(gè)結(jié)點(diǎn)，移動(dòng)n-i+1)次 插入后成為第1個(gè)結(jié)點(diǎn)，移動(dòng)n次 插入后成為第i個(gè)結(jié)點(diǎn)，移動(dòng)n-i+1次 插入后成為第n個(gè)結(jié)點(diǎn)，移動(dòng)1次。 插入后成為第n＋1個(gè)結(jié)點(diǎn)，移動(dòng)0次?？偣瞡+1種情況 ·在長(zhǎng)度為n的線(xiàn)性表中插入一個(gè)結(jié)點(diǎn)的平均次數(shù)為：

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

在一般情況下，刪除第i個(gè)結(jié)點(diǎn)，移動(dòng)n-i次

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

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

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

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

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

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

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

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

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

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

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

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

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

……………….};3、線(xiàn)形表的鏈接存儲(chǔ)結(jié)構(gòu)·在迭代器中，基本操作Find和IsFound的實(shí)現(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、線(xiàn)形表的鏈接存儲(chǔ)結(jié)構(gòu)·在迭代器中，基本操作Inser和Delete的實(shí)現(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é)點(diǎn)，刪除失敗。ListNode<ElemType>*P=Ptr->Next;Ptr->Next=Ptr->Next->Next;deleteP;Current=head;return1;}

3、線(xiàn)形表的鏈接存儲(chǔ)結(jié)構(gòu)·在迭代器中，基本操作Inser和Delete的實(shí)現(xiàn)程序2.8:類(lèi)List的賦值運(yùn)算符=的實(shí)現(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é)點(diǎn)數(shù)據(jù)值，創(chuàng)建新結(jié)點(diǎn)，并插入到當(dāng)前鏈表。return*this;}4、單向循環(huán)鏈表head

……

head

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

……

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

tail

……

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

tailhead

A

B

C

tailhead

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

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

…………}; ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8AH703198517BH81227-98∧∧coefexplinkCH70111227517∧6、一元多項(xiàng)式的加法一元多項(xiàng)式的表示及相加； ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點(diǎn)都刪除。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后移。 注意：將任何一個(gè)多項(xiàng)式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70∧coefexpnNext6、一元多項(xiàng)式的加法一元多項(xiàng)式的表示及相加； ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點(diǎn)都刪除。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后移。 注意：將任何一個(gè)多項(xiàng)式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111coefexpnNext∧6、一元多項(xiàng)式的加法一元多項(xiàng)式的表示及相加； ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點(diǎn)都刪除。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后移。 注意：將任何一個(gè)多項(xiàng)式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111227coefexpnNext∧6、一元多項(xiàng)式的加法一元多項(xiàng)式的表示及相加； ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點(diǎn)都刪除。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后移。 注意：將任何一個(gè)多項(xiàng)式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111227∧coefexpnNext6、一元多項(xiàng)式的加法一元多項(xiàng)式的表示及相加； ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；結(jié)果保留在CH的單鏈表之中。 ·算法：指數(shù)等：若系數(shù)之和為零，則兩結(jié)點(diǎn)都刪除。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后移。 注意：將任何一個(gè)多項(xiàng)式的多余部分，插入在單鏈表C之后。AH703198517BH81227-98∧∧CH70111227517∧coefexpnNext ·注意：本書(shū)的程序?qū)崿F(xiàn)時(shí)，對(duì)單鏈表使用了帶有表頭的表示方法。另外，使用了 迭代器(本書(shū)稱(chēng)之為游標(biāo)類(lèi))。迭代器是一種“指針”抽象。6、一元多項(xiàng)式的加法一元多項(xiàng)式的表示及相加；程序的實(shí)現(xiàn) ·如：多項(xiàng)式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8AH703198517BH81227-98∧∧coefexplinkCH70111227517∧coefexplinkmain(){TermR(-1,-1);//多項(xiàng)式輸入的結(jié)束標(biāo)志。Polynomial<Term>a(R),b(R),c;cin>>a>>b;// 讀入2個(gè)多項(xiàng)式，通過(guò)對(duì)>>重載實(shí)現(xiàn)。c=a; //多項(xiàng)式a并不破壞，將其值送入c。c+b; //完成多項(xiàng)式c、b相加，結(jié)果保存在多項(xiàng)式c之中。cout<<c;//將多項(xiàng)式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;//用于判斷多項(xiàng)式輸入結(jié)束。};StructTerm{floatcoef;intexp;Term(intc,inte){coef=c;exp=e;}…………};6、一元多項(xiàng)式的加法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)鏈表的實(shí)現(xiàn)： 用于沒(méi)有動(dòng)態(tài)存儲(chǔ)分配功能的語(yǔ)言，如FORTRAN、COBOL等；當(dāng)然也可用于C/c++ 等高級(jí)語(yǔ)言。缺點(diǎn)：必須預(yù)估存區(qū)的大小，造成浪費(fèi)。優(yōu)點(diǎn)：插、刪操作省時(shí)。·e.g:設(shè)集合A=(c,b,e,g,f,d)和B=(a,b,n,f)。求集合運(yùn)算(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、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至可利用空間表(也稱(chēng)：空閑?；騻?用鏈(保存未被使用的結(jié)點(diǎn)的單鏈表)。 2、建立集合A的靜態(tài)鏈表。 3、逐個(gè)輸入集合B的元素，同時(shí)查找A的靜態(tài)鏈表有無(wú)該元素。有則刪 除，無(wú)則插入該結(jié)點(diǎn)。 4、集合B的元素輸入完畢，則在原集合A的靜態(tài)鏈表中得到了集合運(yùn)算 (A－B)∪(B－A)的結(jié)果。7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑?；騻溆面湣atacurspace[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、將用作存儲(chǔ)空間的數(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 ·為了形象起見(jiàn)，和動(dòng)態(tài)分配的單鏈表表示相似，備用鏈初 始化之后通常表示成以下形式。-1-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表的初始化。0234567891011datacur10s工作鏈：備用鏈：-1-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素c之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rc7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑棧或備用鏈。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素b之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcb7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素e之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbe7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑棧或備用鏈。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素g之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbeg7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑棧或備用鏈。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素f之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbegf7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑?；騻溆面?。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 2、建立集合A的靜態(tài)鏈表: ·集合A的靜態(tài)鏈表：在輸入元素d之后。0234567891011-1datacur10-1s工作鏈：備用鏈：rcbegfd7、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑棧或備用鏈。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址是下標(biāo)地址。10234567891011datacur 3、逐個(gè)輸入集合B的元素。 ·輸入a,查找A的靜態(tài)鏈表。a不在，插入。0234567891011datacur10s工作鏈：備用鏈：rcbegfda-1-17、應(yīng)用：靜態(tài)鏈表和稀疏矩陣 1、將用作存儲(chǔ)空間的數(shù)組的所有單元分配至空閑棧或備用鏈。 ·備用鏈通常畫(huà)成以下圖形：注意此處的地址