第2章線性表

線性表的邏輯結(jié)構(gòu)

線性表的順序存儲及實現(xiàn)

線性表的鏈接存儲及實現(xiàn)

順序表和鏈表的比較

線性表的其他存儲方法本章的基本內(nèi)容是：2.1線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？2.1線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？現(xiàn)實生活中，許多問題抽象出的數(shù)據(jù)模型是線性表，如何存儲這種線性結(jié)構(gòu)并實現(xiàn)插入、刪除、查找等基本操作呢？線性表的定義線性表：簡稱表，是n（n≥0）個具有相同類型的數(shù)據(jù)元素的有限序列。線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)?？毡恚洪L度等于零的線性表，記為：L=()。非空表記為：L＝（a1,a2,…,ai-1,ai,…,an)2.1線性表的邏輯結(jié)構(gòu)其中，ai（1≤i≤n）稱為數(shù)據(jù)元素；下角標(biāo)i表示該元素在線性表中的位置或序號。a1a3a4ana22.1線性表的邏輯結(jié)構(gòu)線性表的特性1.有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1,ai)，即ai-1是ai的前驅(qū)，ai是ai-1的后繼；a1無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。

線性表的抽象數(shù)據(jù)類型定義ADTListData

線性表中的數(shù)據(jù)元素具有相同類型，相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitList

前置條件：表不存在輸入：無

功能：表的初始化輸出：無

后置條件：建一個空表2.1線性表的邏輯結(jié)構(gòu)DestroyList

前置條件：表已存在

輸入：無

功能：銷毀表

輸出：無

后置條件：釋放表所占用的存儲空間Length

前置條件：表已存在

輸入：無

功能：求表的長度

輸出：表中數(shù)據(jù)元素的個數(shù)

后置條件：表不變2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Get

前置條件：表已存在

輸入：元素的序號i

功能：在表中取序號為i的數(shù)據(jù)元素

輸出：若i合法，返回序號為i的元素值，否則拋出異常

后置條件：表不變Locate

前置條件：表已存在

輸入：數(shù)據(jù)元素x

功能：在線性表中查找值等于x的元素

輸出：若查找成功，返回x在表中的序號，否則返回0

后置條件：表不變2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義Insert

前置條件：表已存在

輸入：插入i；待插x

功能：在表的第i個位置處插入一個新元素x

輸出：若插入不成功，拋出異常

后置條件：若插入成功，表中增加一個新元素Delete

前置條件：表已存在

輸入：刪除位置i

功能：刪除表中的第i個元素

輸出：若刪除成功，返回被刪元素，否則拋出異常

后置條件：若刪除成功，表中減少一個元素2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Empty

前置條件：表已存在

輸入：無

功能：判斷表是否為空

輸出：若是空表，返回1，否則返回0

后置條件：表不變ADT進(jìn)一步說明:（1）線性表的基本操作根據(jù)實際應(yīng)用是而定；（2）復(fù)雜的操作可以通過基本操作的組合來實現(xiàn)；（3）對不同的應(yīng)用，操作的接口可能不同。2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表——線性表的順序存儲結(jié)構(gòu)例：（34,23,67,43）342367434存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表——線性表的順序存儲結(jié)構(gòu)例：（34,23,67,43）34236743存儲空間的起始位置4用什么屬性來描述順序表？順序表的容量（最大長度）順序表的當(dāng)前長度2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表——線性表的順序存儲結(jié)構(gòu)例：（34,23,67,43）342367434如何實現(xiàn)順序表的內(nèi)存分配？順序表一維數(shù)組0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：數(shù)組的長度Max線性表的長度Length數(shù)組的長度大于等于當(dāng)前線性表的長度如何求得任意元素的存儲地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：cLoc(ai)Loc(a1)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度Loc(ai)=Loc(a1)+(i-1)×c隨機存?。涸贠(1)時間內(nèi)存取數(shù)據(jù)元素2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：cLoc(ai)Loc(a1)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)存儲結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示；存取結(jié)構(gòu)是在一個數(shù)據(jù)結(jié)構(gòu)上對訪問操作的時間性能的一種描述。存儲結(jié)構(gòu)和存取結(jié)構(gòu)“順序表是一種隨機存取的存儲結(jié)構(gòu)”的含義為：在順序表這種存儲結(jié)構(gòu)上進(jìn)行的訪問，其時間性能為O(1)。順序表類的聲明constintMaxSize=100;template<classDataType>//模板類classSeqList{public:SeqList();//構(gòu)造函數(shù)

SeqList(DataTypea[],intn);~SeqList();//析構(gòu)函數(shù)intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:DataTypedata[MaxSize];intlength;};2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——無參構(gòu)造函數(shù)操作接口：SeqList()

算法描述：SeqList<DataType>

::SeqList(){length=0;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)

datalength0順序表的實現(xiàn)——有參構(gòu)造函數(shù)操作接口：SeqList(DataTypea[],intn)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表

數(shù)組a351224334253512243342順序表的實現(xiàn)——有參構(gòu)造函數(shù)template<classDataType>SeqList<DataType>

::SeqList(DataTypea[],intn){if(n>MaxSize)throw"參數(shù)非法";

for(i=0;i<n;i++)

data[i]=a[i];length=n;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)算法描述：順序表的實現(xiàn)——插入操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x

,ai,…,an)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化33順序表的實現(xiàn)——插入例：（35，12，24，42），在i=2的位置上插入33。表滿：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序號）2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)435122442a1a2a3a401234422412335什么時候不能插入？注意邊界條件算法描述——偽代碼1.如果表滿了，則拋出上溢異常;2.如果元素的插入位置不合理，則拋出位置異常;3.將最后一個元素至第i個元素分別向后移動一個位置；4.將元素x填入位置i處；5.表長加1；2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——插入順序表的實現(xiàn)——插入template<classDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length>=MaxSize)throw"上溢";

if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];data[i-1]=x;length++;}算法描述——C++描述2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)基本語句？順序表的實現(xiàn)——插入最好情況（i=n+1）：基本語句執(zhí)行0次，時間復(fù)雜度為O(1)。最壞情況（i=1）：基本語句執(zhí)行n+1次，時間復(fù)雜度為O(n)。平均情況（1≤i≤n+1）：時間復(fù)雜度為O(n)。時間性能分析2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)操作接口：DataTypeDelete(inti)刪除前：(a1,…,ai-1,ai,ai+1,…,an)刪除后：(a1,…,ai-1,ai+1,…,an)

順序表的實現(xiàn)——刪除2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出偽代碼和C++描述的算法；3.分析時間復(fù)雜度。2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——刪除535a1a2a3a401234422412334a5122442順序表的實現(xiàn)——按位查找操作接口：DataTypeGet(inti)

2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑

n算法描述：template<classDataType>DataTypeSeqList<DataType>

::Get(inti){

if(i>=1&&i<=length)returndata[i-1];}時間復(fù)雜度？順序表的實現(xiàn)——按值查找操作接口：intLocate(DataTypex)

2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值為12的元素，返回在表中的序號。iii注意序號和下標(biāo)之間的關(guān)系template<classDataType>intSeqList<DataType>

::Locate(DataTypex){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——按值查找算法描述：時間復(fù)雜度？順序表類的聲明constintMaxSize=100;template<classDataType>//模板類classSeqList{public:SeqList(intmaxlen=MaxSize);//構(gòu)造函數(shù)

SeqList(DataTypea[],intn);~SeqList();//析構(gòu)函數(shù)intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:

DataType*data;intlength;intmaxsize;

booladdSpace(intsize=10);};2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)(動態(tài)數(shù)組)順序表的實現(xiàn)——構(gòu)造函數(shù)操作接口：SeqList(int

maxlen=MaxSize)

算法描述：SeqList<DataType>

::SeqList(int

maxlen):length(0),maxsize(maxlen){if(maxlen<=0)throw“參數(shù)非法”; data=new

DataType[maxlen];}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)(動態(tài)數(shù)組)

datalength0順序表的實現(xiàn)——分配空間操作接口：booladdSpace(int

size=10)

算法描述：boolSeqList<DataType>

::addSpace(int

size){if(size<=0)returnfalse;tmpdata=data;maxlen+=size;data=new

DataType[maxlen];for(i=0;i<length;i++)data[i]=tmpdata[i];delete[]tmpdata;returntrue;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)(動態(tài)數(shù)組)順序表的優(yōu)缺點順序表的優(yōu)點：⑴無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間；⑵隨機存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。

順序表的缺點：⑴插入和刪除操作需要移動大量元素；⑵表的容量難以確定，表的容量難以擴充；⑶造成存儲空間的碎片。

2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)單鏈表：線性表的鏈接存儲結(jié)構(gòu)。存儲思想：用一組任意的存儲單元存放線性表的元素。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表靜態(tài)存儲分配順序表事先確定容量鏈表動態(tài)存儲分配運行時分配空間連續(xù)不連續(xù)零散分布0200020803000325…………存儲特點：邏輯次序和物理次序不一定相同。

2.元素之間的邏輯關(guān)系用指針表示。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)例：(a1,a2

,a3,a4)的存儲示意圖單鏈表a10200a20325a30300a4∧2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧結(jié)點數(shù)據(jù)域指針域單鏈表是由若干結(jié)點構(gòu)成的；單鏈表的結(jié)點只有一個指針域。data：存儲數(shù)據(jù)元素next：存儲指向后繼結(jié)點的地址datanext單鏈表的結(jié)點結(jié)構(gòu)：數(shù)據(jù)域指針域template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表datanext單鏈表的結(jié)點結(jié)構(gòu)：如何申請一個結(jié)點？s=newNode<int>;template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表datanext單鏈表的結(jié)點結(jié)構(gòu)：……sNodes=newNode<int>;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表datanext……sNode如何引用數(shù)據(jù)元素？s->data;*s.data;data如何引用指針域？nexts->next;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表重點在數(shù)據(jù)元素之間的邏輯關(guān)系的表示，所以，將實際存儲地址抽象。什么是存儲結(jié)構(gòu)？2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表頭指針：指向第一個結(jié)點的地址。尾標(biāo)志：終端結(jié)點的指針域為空。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不統(tǒng)一，缺點？如何將空表與非空表統(tǒng)一？對第一個結(jié)點的操作與對其他結(jié)點的操作，使用語句可一致？頭結(jié)點：在單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點，以便空表和非空表處理統(tǒng)一，并且可統(tǒng)一對任意位置的結(jié)點的操作實現(xiàn)。

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表非空表firsta1a2an∧空表first∧template<classDataType>classLinkList{public:LinkList()；LinkList(DataTypea[],intn);~LinkList();intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);voidPrintList();private:Node<DataType>*first;};單鏈表類的聲明2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——遍歷操作操作接口：

voidPrintList();核心操作（關(guān)鍵操作）：工作指針后移。從頭結(jié)點（或開始結(jié)點）出發(fā)，通過工作指針的反復(fù)后移而將整個單鏈表“審視”一遍的方法稱為掃描（或遍歷）。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1pa2pan∧aippp單鏈表的實現(xiàn)——遍歷操作操作接口：

voidPrintList();2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)template<classDataType>voidLinkList<DataType>::PrintList(){p=first->next;while(p!=NULL){cout<<p->data;p=p->next;}}p++能否完成指針后移？a1a2pp++p->next單鏈表的實現(xiàn)——按位查找操作接口：

DataTypeGet(inti);2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1a2an∧aipp查找失敗1.工作指針p初始化;累加器count初始化;2.重復(fù)執(zhí)行下述操作，直到p為空：

2.1工作指針p后移;2.2count++;3.返回p->data的值；pcount=1pcount=2p查找成功count=itemplate<classDataType>DataTypeLinkList<DataType>::Get(inti){p=first->next;count=1;while(p!=NULL){if(count==i)returnp->data;p=p->next;count++;}throw“參數(shù)錯誤”;Node<DataType>tmp;returntmp.data;}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——按位查找算法描述——C++描述template<classDataType>intLinkList<DataType>::Length(){p=first->next;count=0;while(p!=NULL){p=p->next;count++;}returncount;//注意count的初始化和返回值之間的關(guān)系}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——按位查找——計算表長算法描述——C++描述template<classDataType>intLinkList<DataType>::Locate(DataTypex){p=first->next;count=1;

while(p!=NULL){if(p->data==x)returncount;//查找成功，返回序號p=p->next;count++;}return0;//退出循環(huán)表明查找失敗}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——按值查找算法描述——C++描述單鏈表的實現(xiàn)———插入操作接口：

voidInsert(inti,DataTypex);

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)如何實現(xiàn)結(jié)點ai-1、x和ai之間邏輯關(guān)系的變化？pxsfirsta1ai-1an∧ai算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;注意分析邊界情況——表頭、表尾。

單鏈表的實現(xiàn)———插入2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1an∧aipxs算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;pxs∧由于單鏈表帶頭結(jié)點，表頭、表中、表尾三種情況的操作語句一致。

算法描述——偽代碼

1.工作指針p初始化；

2.查找第i-1個結(jié)點并使工作指針p指向該結(jié)點；

3.若查找不成功，則插入位置不合理，拋出插入位置異常；否則，3.1生成一個元素值為x的新結(jié)點s；

3.2將新結(jié)點s插入到結(jié)點p之后；2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———插入

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;//工作指針p應(yīng)指向頭結(jié)點

while(p!=NULL&&count<i-1)//查找第i–1個結(jié)點

{p=p->next;

count++;}if(p==NULL)throw"位置";//沒有找到第i–1個結(jié)點

else{s=newNode;s->data=x;//申請一個結(jié)點ss->next=p->next;p->next=s;//結(jié)點s插入結(jié)點p之后

}}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———插入基本語句？時間復(fù)雜度？單鏈表的實現(xiàn)———無參構(gòu)造函數(shù)操作接口：LinkList()構(gòu)造空表，即僅構(gòu)造頭結(jié)點。算法描述：first=newNode<DataType>;first->next=NULL;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)初始化first∧template<classDataType>LinkList<DataType>::LinkList(){ first=newNode<DataType>; first->next=NULL;}單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結(jié)點插在頭結(jié)點的后面。算法描述：first=newNode<DataType>;first->next=NULL;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組a3512243342初始化first∧單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結(jié)點插在頭結(jié)點的后面。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組a3512243342算法描述：s=newNode<DataType>;s->data=a[0];s->next=first->next;first->next=s;插入第一個元素結(jié)點first∧35s∧單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結(jié)點插在頭結(jié)點的后面。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組a3512243342算法描述：s=newNode<DataType>;s->data=a[1];s->next=first->next;first->next=s;依次插入每一個結(jié)點12sfirst35∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode<DataType>;first->next=NULL;for(i=0;i<n;i++){s=newNode<DataType>;s->data=a[i];

s->next=first->next;first->next=s;}}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)尾插法：將待插入結(jié)點插在終端結(jié)點的后面。

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)算法描述：first=newNode<DataType>;rear=first;數(shù)組a3512243342初始化firstrear尾插法：將待插入結(jié)點插在終端結(jié)點的后面。

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)算法描述：s=newNode<DataType>;s->data=a[0];rear->next=s;rear=s;數(shù)組a3512243342插入第一個元素結(jié)點firstrear35srear尾插法：將待插入結(jié)點插在終端結(jié)點的后面。

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)算法描述：s=newNode<DataType>;s->data=a[1];rear->next=s;rear=s;數(shù)組a3512243342依次插入每一個結(jié)點first35rear12srear尾插法：將待插入結(jié)點插在終端結(jié)點的后面。

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)算法描述：rear->next=NULL;數(shù)組a3512243342最后一個結(jié)點插入后first3542srear∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode;//生成頭結(jié)點

r=first;//尾指針初始化for(i=0;i<n;i++){s=newNode;s->data=a[i];

r->next=s;r=s;}r->next=NULL;}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)算法描述：單鏈表的實現(xiàn)———刪除操作接口：

DataTypeDelete(inti);

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)p如何實現(xiàn)結(jié)點ai-1和ai之間邏輯關(guān)系的變化？firsta1ai-1ai+1ai算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;q單鏈表的實現(xiàn)———刪除2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;注意分析邊界情況——表頭、表尾。

pqpq表尾的特殊情況：雖然被刪結(jié)點不存在，但其前驅(qū)結(jié)點卻存在。p->next=NULLfirsta1ana2∧算法描述——偽代碼1.工作指針p初始化；2.查找第i-1個結(jié)點并使工作指針p指向該結(jié)點；3.若p不存在或p不存在后繼結(jié)點，則拋出位置異常；否則，3.1暫存被刪結(jié)點和被刪元素值；3.2摘鏈，將結(jié)點p的后繼結(jié)點從鏈表上摘下；3.3釋放被刪結(jié)點；3.4返回被刪元素值；

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———刪除template<classDataType>DataTypeLinkList<DataType>::Delete(inti){p=first;count=0;

while(p!=NULL&&count<i-1)

{p=p->next;count++;}if(p==NULL||p->next==NULL)

throw"位置";else{q=p->next;x=q->data;p->next=q->next;deleteq;returnx;}}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———刪除單鏈表的實現(xiàn)——析構(gòu)函數(shù)析構(gòu)函數(shù)將單鏈表中所有結(jié)點的存儲空間釋放。

2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)操作接口：~LinkList();firsta1a2an∧aiq算法描述：q=first;first=first->next;deleteq;first注意：保證鏈表未處理的部分不斷開

單鏈表的實現(xiàn)——析構(gòu)函數(shù)template<classDataType>LinkList<DataType>::~LinkList(){while(first!=NULL)

{q=first;

first=first->next;

deleteq;}}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法描述：啟示：算法設(shè)計的一般過程算法設(shè)計的一般步驟：第一步：確定入口（已知條件）、出口（結(jié)果）；第二步：根據(jù)一個小實例畫出示意圖；第三步：①正向思維：選定一個思考問題的起點，逐步提出問題、解決問題；②逆向思維：從結(jié)論出發(fā)分析為達(dá)到這個結(jié)論應(yīng)該先有什么；③正逆結(jié)合；第四步：寫出頂層較抽象算法，分析邊界情況；第五步：驗證第四步的算法；第六步：寫出具體算法；第七步：進(jìn)一步驗證，手工運行。循環(huán)鏈表firsta1ai-1an∧aip從單鏈表中某結(jié)點p出發(fā)如何找到其前驅(qū)？將單鏈表的首尾相接，將終端結(jié)點的指針域由空指針改為指向頭結(jié)點，構(gòu)成單循環(huán)鏈表，簡稱循環(huán)鏈表。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)循環(huán)鏈表空表和非空表的處理一致附設(shè)頭結(jié)點first空循環(huán)鏈表firsta1ai-1anai非空循環(huán)鏈表2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1ai-1anai循環(huán)鏈表——插入xspxspxsp算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;

while(p->next!=first&&count<i-1){p=p->next;count++;}if(i<=0||count<i-1)throw"位置";else{s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;}}

循環(huán)鏈表——插入與單鏈表的插入操作相比，差別是什么？2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)循環(huán)條件：p!=NULL

p!=firstp->next!=NULL

p->next!=first循環(huán)鏈表循環(huán)鏈表中沒有明顯的尾端如何避免死循環(huán)2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)如何查找開始結(jié)點和終端結(jié)點？循環(huán)鏈表firsta1ai-1anai開始結(jié)點：first->next終端結(jié)點：將單鏈表掃描一遍，時間為O(n)2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)reara1ai-1anai開始結(jié)點：rear->next->next終端結(jié)點：rear循環(huán)鏈表帶尾指針的循環(huán)鏈表一個存儲結(jié)構(gòu)設(shè)計得是否合理，取決于基于該存儲結(jié)構(gòu)的運算是否方便，時間性能是否提高。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表如何求結(jié)點p的直接前驅(qū)，時間性能？firsta1ai-1anaip為什么可以快速求得結(jié)點p的后繼？如何快速求得結(jié)點p的前驅(qū)？2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表：在單鏈表的每個結(jié)點中再設(shè)置一個指向其前驅(qū)結(jié)點的指針域。雙鏈表結(jié)點結(jié)構(gòu)：priordatanextdata：數(shù)據(jù)域，存儲數(shù)據(jù)元素；prior：指針域，存儲該結(jié)點的前趨結(jié)點地址；next：指針域，存儲該結(jié)點的后繼結(jié)點地址。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)template<classDataType>structDulNode{DataTypedata;DulNode<DataType>*prior,*next;};

雙鏈表啟示？時空權(quán)衡——空間換取時間priordatanext定義結(jié)點結(jié)構(gòu)：2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;ai-1ai操作接口：

voidInsert(DulNode<DataType>*p,DataTypex);

pxs注意指針修改的相對順序2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表的操作——刪除(p->prior)->next=p->next;

(p->next)->prior=p->prior;

操作接口：

DataTypeDelete(DulNode<DataType>*p);

ai-1aipai結(jié)點p的指針是否需要修改？deletep;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)存儲分配方式比較順序表采用順序存儲結(jié)構(gòu)，即用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過存儲位置來實現(xiàn)。鏈表采用鏈接存儲結(jié)構(gòu)，即用一組任意的存儲單元存放線性表的元素，用指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。2.4順序表和鏈表的比較2.4順序表和鏈表的比較時間性能比較

時間性能是指實現(xiàn)基于某種存儲結(jié)構(gòu)的基本操作（即算法）的時間復(fù)雜度。

按位查找：順序表的時間為Ｏ(1)，是隨機存??；鏈表的時間為Ｏ(n)，是順序存取。插入和刪除：順序表需移動表長一半的元素，時間為Ｏ(n)；鏈表不需要移動元素，在給出某個合適位置的指針后，插入和刪除操作所需的時間僅為Ｏ(1)。2.4順序表和鏈表的比較空間性能比較

空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。

定義結(jié)點的存儲密度：數(shù)據(jù)域占用的存儲量整個結(jié)點占用的存儲量存儲密度＝結(jié)點的存儲密度：順序表：結(jié)點的存儲密度為1（只存儲數(shù)據(jù)元素），沒有浪費空間；鏈表：結(jié)點的存儲密度<1（包括數(shù)據(jù)域和指針域），有指針的結(jié)構(gòu)性開銷。2.4順序表和鏈表的比較空間性能比較

空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。

定義結(jié)點的存儲密度：數(shù)據(jù)域占用的存儲量整個結(jié)點占用的存儲量存儲密度＝結(jié)構(gòu)的存儲密度：順序表：需要預(yù)分配存儲空間，如果預(yù)分配得過大，造成浪費，若估計得過小，又將發(fā)生上溢；鏈表：不需要預(yù)分配空間，只要有內(nèi)存空間可以分配，單鏈表中的元素個數(shù)就沒有限制。結(jié)論⑴若線性表需頻繁查找卻很少進(jìn)行插入和刪除操作，或其操作和元素在表中的位置密切相關(guān)時，宜采用順序表作為存儲結(jié)構(gòu)；若線性表需頻繁插入和刪除時，則宜采用鏈表做存儲結(jié)構(gòu)。⑵當(dāng)線性表中元素個數(shù)變化較大或者未知時，最好使用鏈表實現(xiàn)；而如果用戶事先知道線性表的大致長度，使用順序表的空間效率會更高。2.4順序表和鏈表的比較總之，線性表的順序?qū)崿F(xiàn)和鏈表實現(xiàn)各有其優(yōu)缺點，不能籠統(tǒng)地說哪種實現(xiàn)更好，只能根據(jù)實際問題的具體需要，并對各方面的優(yōu)缺點加以綜合平衡，才能最終選定比較適宜的實現(xiàn)方法。靜態(tài)鏈表：用數(shù)組來表示單鏈表，用數(shù)組元素的下標(biāo)來模擬單鏈表的指針。靜態(tài)鏈表2.5線性表的其它存儲方法data：存儲放數(shù)據(jù)元素；next：也稱游標(biāo)，存儲該元素的后繼在數(shù)組的下標(biāo)。數(shù)組元素（結(jié)點）的構(gòu)成：datanext數(shù)據(jù)域指針域例：線性表(張，王，李，趙，吳)的靜態(tài)鏈表存儲2.5線性表的其它存儲方法靜態(tài)鏈表張2王3李4趙5吳-101234567878-11datanextfirstavailfirst：靜態(tài)鏈表頭指針，為了方便插入和刪除操作，通常靜態(tài)鏈表帶頭結(jié)點；avail：空閑鏈表頭指針，空閑鏈表由于只在表頭操作，所以不帶頭結(jié)點；2.5線性表的其它存儲方法靜態(tài)鏈表靜態(tài)鏈表的存儲結(jié)構(gòu)定義如下：constintMaxSize=100;//100只是示例數(shù)據(jù)template<classDataType>structSNode{DataTypedata;//DataType表示不確定的數(shù)據(jù)類型

intnext;//指針域（也稱游標(biāo)）}SList[MaxSize];在線性表(張，王，李，趙，吳)中“王”之后插入“孫”2.5線性表的其它存儲方法張2王3李4趙5吳-101234567878-11datanext靜態(tài)鏈表張2王

6李4趙5吳-1012345678孫

38-11datanext王之后插入孫availavailfirstfirst2.5線性表的其它存儲方法靜態(tài)鏈表假設(shè)結(jié)點s插在結(jié)點p之后，則修改指針的操作為：

s=avail;//利用空閑鏈的第一個結(jié)點

avail=SList[avail].next;//空閑鏈的頭指針后移

SList[s].data=x;//將x填入下標(biāo)為s的結(jié)點

SList[s].next=SList[p].next;//將下標(biāo)為s的結(jié)點插入到

SList[p].next=s;//下標(biāo)為p的結(jié)點后面在線性表(張，王，李，趙，吳)中刪除“趙”2.5線性表的其它存儲方法張2王3李4趙5吳-101234567878-11datanext靜態(tài)鏈表張2王

3李

5趙5吳-1012345678

78-11datanext刪除趙摘鏈在線性表(張，王，李，趙，吳)中刪除“趙”2.5線性表的其它存儲方法張2王3李4趙5吳-101234567878-11datanext靜態(tài)鏈表張2王

3李

5

6吳-1012345678

78-11datanext刪除趙歸還空間2.5線性表的其它存儲方法靜態(tài)鏈表假設(shè)刪除結(jié)點p的后繼結(jié)點，則修改指針的操作為：

q=SList[p].next;//暫存被刪結(jié)點的下標(biāo)

SList[p].next=SList[q].next;//摘鏈

SList[q].next=avail;//將結(jié)點q插在鏈avail的最前端

avail=q;//空閑鏈頭指針avail指向結(jié)點q2.5線性表的其它存儲方法靜態(tài)鏈表相對于順序表而言，靜態(tài)鏈表有什么優(yōu)點？

優(yōu)點：在執(zhí)行插入和刪除操作時，只需修改游標(biāo)，不需要移動表中的元素，從而改進(jìn)了在順序表中插入和刪除操作需要移動大量元素的缺點。缺點：沒有解決連續(xù)存儲分配帶來的表長難以確定的問題；靜態(tài)鏈表還需要維護(hù)一個空閑鏈；靜態(tài)鏈表不能隨機存取。

間接尋址間接尋址：是將數(shù)組和指針結(jié)合起來的一種方法，它將數(shù)組中存儲數(shù)據(jù)元素的單元改為存儲指向該元素的指針。2.5線性表的其它存儲方法012i-1n-1Max-1……

空閑

長度a1aiana2插入操作移動的不是元素而是指向元素的指針。當(dāng)元素占用的空間較多時，比順序表的插入操作快得多。多項式(Polynomial)n階多項式Pn(x)有n+1項。

系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列

多項式的順序存儲表示第一種：

private:(靜態(tài)數(shù)

intdegree; 組表示)floatcoef[maxDegree+1];

Pn(x)可以表示為：

pl.degree=n pl.coef[i]=ai,0

i

na0

a1

a2……an………012degreemaxDegree-1coefn第二種：private: (動態(tài)數(shù)

intdegree;組表示) float*coef; Polynomial::Polynomial(int

sz){ degree=sz;

coef=newfloat[degree+1]; }以上兩種存儲表示適用于指數(shù)連續(xù)排列的多項式。但對于絕大多數(shù)項的系數(shù)為零的多項式（稱為稀疏多項式），如

P101(x)=3+5x50-4x101,不經(jīng)濟。第三種：

structterm{//多項式的項定義 floatcoef;//系數(shù)

intexp; //指數(shù)

};statictermtermArray[maxTerms];//項數(shù)組staticintfree,maxTerms;//當(dāng)前空閑位置指針

a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

m初始化：//termPolynomial::termArray[MaxTerms];//intPolynomial::free=0;class

Polynomial{//多項式定義public:……private:intstart,finish;//多項式始末位置}兩個多項式存儲的例子

A(x)=2.0x1000+1.8

B(x)=1.2+51.3x50+3.7x101

兩個多項式存放在termArray中A.startA.finishB.startB.finishfreecoefexp1.82.01.251.33.7……01000050101……maxTerms兩個多項式的相加結(jié)果多項式另存掃描兩個相加多項式，若都未檢測完：

若當(dāng)前被檢測項指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項式。若當(dāng)前被檢測項指數(shù)不等，將指數(shù)小者加到結(jié)果多項式。若有一個多項式已檢測完，將另一個多項式剩余部分復(fù)制到結(jié)果多項式。PolynomialPolynomial::Add(PolynomialB){

PolynomialC;

int

a=start;

int

b=B.start;

C.start=free;

floatc;

while(a<=finish&&b<=B.finish)

Switch

(compare(termArray[a].exp,termArray[b].exp)){

//比較對應(yīng)項指數(shù)

case‘=’://指數(shù)相等

c=termArray[a].coef+termArray[b].coef;if(c)NewTerm(c,termArray[a].exp);

a++;b++;

break;case'>':

NewTerm(termArray[b].coef,

termArray[b].exp);

b++;

break;

case'<':

NewTerm(termArray[a].coef,

termArray[a].exp);

a++;

}for(;a<=finish;a++)//a未檢測完時

NewTerm(termArray[a].coef,

termArray[a].exp);for(

;b<=B.finish;b++)//b未檢測完時

NewTerm(termArray[b].coef,

termArray[b].exp);

C.finish=free-1;

return

C;}在多項式中加入新的項void

Polynomial::NewTerm(floatc,

inte){

//把一個新的項加到多項式C(x)中

if(free>=maxTerms){cout<<"Toomanytermsinpolynomials”<<

endl;return;

}

termArray[free].coef=c;

termArray[free].exp=e;

free++;}

多項式順序存儲表示的缺點插入和刪除時項數(shù)可能有較大變化，因此要移動大量數(shù)據(jù)不利于多個多項式的同時處理采用多項式的鏈表表示可以克服這類困難：多項式的項數(shù)可以動態(tài)地增長，不存在存儲溢出問題。插入、刪除方便，不移動元素。多項式的鏈表存儲表示在多項式的鏈表表示中，每個結(jié)點三個數(shù)據(jù)成員：通過鏈接指針，可以將多項式各項按指數(shù)遞增的順序鏈接成一個單鏈表。在此結(jié)構(gòu)上，新項的加入和廢項的刪除執(zhí)行簡單的鏈表插入和刪除操作即可解決。多項式的鏈表結(jié)構(gòu)coefexpnext

Data

Term多項式(polynomial)類的鏈表定義structTerm{

//多項式結(jié)點定義

floatcoef; //系數(shù)

intexp; //指數(shù)

Term*next; //鏈接指針

Term(floatc,inte,Term*link=NULL)

{coef=c;exp=e;next=link;} Term*InsertAfter(floatc,inte);

friendostream&operator

<<

(ostream&,

constTerm&);};classPolynomial{

//多項式類的定義public: Polynomal(){first=newTerm(0,-1);} //構(gòu)造函數(shù)

Polynomal(Polynomal&R);//復(fù)制構(gòu)造函數(shù)

intmaxOrder(); //計算最大階數(shù)private: Term*first;

friendostream&operator<<(ostream&,constPolynomal&);friendistream&operator>>(istream&,

Polynomal&);friendvoidAdd(Polynomial&A,Polynomial&B,

Polynomial&C);

friendvoidMul(Polynomial&A,Polynomial&B,

Polynomial&C);};Term*Term::InsertAfter(floatc,inte){//在調(diào)用此函數(shù)的對象后插入一個新項

next=newTerm(c,e,next);

//創(chuàng)建一個新結(jié)點，自動鏈接

returnnext; //插入到this結(jié)點后面};

ostream&operator<<(ostream&out,constTerm&x){//Term的友元函數(shù)：輸出一個項x的內(nèi)容到輸出流對//象out中去。

if(x.coef==0.0)returnout;//零系數(shù)項不輸出

out<<x.coef; //輸出系數(shù)

switch(x.exp){ //輸出指數(shù)

case0:break; //指數(shù)為0,不出現(xiàn)‘X’

case1:out<<“X”;break;//在系數(shù)后輸出‘X’

default: