線性表1-順序表及單鏈表

數(shù)據(jù)結(jié)構(gòu)與算法2009年秋季授課教師：張劍波方芳授課班級：111081-4班115081-2班Chapter3線性表本章教學內(nèi)容3.2線性表ADT3.3線性表的公式化描述（數(shù)組表示）3.4線性表的鏈表描述3.5線性表的應(yīng)用3.2線性表（Linear_List）1、線性表（Linear_List）的示例例如：1、（0，1，2，3，4，5，6，7，8，9）；學號姓名性別年齡成績高數(shù)英語物理體育98011張娟女208086819098012趙立軍男1982728986……………………

2、一本書可以看成是一個線性表；

3、學生成績檔案表：線性表是n(n≥0)個相同類型數(shù)據(jù)元素構(gòu)成的有限序列，其中n為線性表的長度。

n=0的線性表稱為空表；

n>0時，非空表，通常記為（e1,e2,…,ei-1,ei,ei+1,…en-1,en）

ei(1≤i≤n)是線性表中第i個元素

e1：第一個元素（無前驅(qū)）

en：最后一個元素（無后繼）

ei優(yōu)先于ei+1（ei是ei+1的前驅(qū)，ei+1是ei的后繼）線性表的定義線性表的ADT（ADT3-1）本書：線性表的描述公式化描述使用數(shù)組，借助數(shù)學公式指明每個元素存儲位置。鏈表描述每個元素中包含指向下一個元素的指針。間接尋址建立一張單獨的元素地址表，存放指向元素的指針。模擬指針類似鏈表描述，用整數(shù)代替C++指針。1、順序表的定義2、順序表的特點用一組地址連續(xù)的存儲單元依次存放線性表中的各數(shù)據(jù)元素。邏輯結(jié)構(gòu)上相鄰的元素其物理結(jié)構(gòu)也相鄰。3、用一維數(shù)組描述順序表中數(shù)據(jù)元素的存儲區(qū)域。3.3線性表的公式化描述（順序表）使用一維數(shù)組element[]，按照數(shù)學公式將每個元素映射到數(shù)組中的特定位置。第i個元素放置在element[i-1]：location(i)=i-1變量

length

記錄當前元素數(shù)目。length=5數(shù)組下標索引位置1234567abcde0123456數(shù)據(jù)元素公式化描述的線性表類（程序3-1）template<classT>classLinearList{public:

LinearList(intMaxListSize=10);

~LinearList(){delete[]element;}boolIsEmpty()const{returnlength==0;}/*判斷是否為空*/intLength()const{returnlength;}/*返回長度*/boolFind(intk,T&x)const;/*尋找第k個元素，保持在x中，else，返回false*/intSearch(constT&x)const;/*返回元素x在表中的位置，如果不在則返回0*/

LinearList<T>&Delete(intk,T&x);/*刪除表中第k個元素，保存于x中，函數(shù)返回修改后的鏈表*/LinearList<T>&Insert(intk,constT&x);/*在第K個元素之后插入x，函數(shù)返回修改后的鏈表*/LinearList<T>&Reverse();voidOutput(ostream&out)const;private:intlength;intMaxSize;T*element;//動態(tài)一維數(shù)組};補充：替換new的異常處理#include<new.h>1、定義自己的異常處理類classNoMem{public:NoMem(){}};2、定義VC要求的異常函數(shù)intmy_new_handler(size_tx){throwNoMem();return0;};3、環(huán)境設(shè)置與恢復(fù)_PNHold_Handler=_set_new_handler(my_new_handler);使用：int*p=newint[1000];_set_new_handler(old_Handler);-操作1-創(chuàng)建空表（程序3-3）template<classT>LinearList<T>::LinearList(intMaxListSize){MaxSize=MaxListSize;element=newT[MaxSize];length=0;}-操作2-取元素（程序3-3）template<classT>boolLinearList<T>::Find(intk,T&x)const{//將第k個元素取至x中if(k<1||k>length)returnfalse;

x=element[k-1];

returntrue;}時間復(fù)雜度：Θ(1)-操作3-查找（程序3-3）template<classT>intLinearList<T>::Search(constT&x)const{//返回值為x的元素下標?！咀⒁狻看颂幱行聵藶閇1,n]for(inti=0;i<length;i++)

if(element[i]==x)

return++i;

return0;}時間復(fù)雜度：Θ(n)（a1,…,ak-1,ak,ak+1…,an）（a1,…,ak-1,ak+1,…,an）1a12a2……kakk+1ak+1……lengthan……MaxSize1a12a2……kak+1k+1ak+2……length-1an……MaxSize刪除前刪除后-操作4：刪除刪除算法（程序3-4）template<classT>LinearList<T>&LinearList<T>::Delete(intk,T&x){if(Find(k,x)){

for(inti=k;i<length;i++)element[i-1]=element[i];

//元素前移

length--;

return*this;}else{throwOutOfBounds();//越界異常return*this;}}時間復(fù)雜度：O(length-k)-刪除算法分析刪除算法的時間代價主要耗費在移動數(shù)據(jù)元素上，移動數(shù)據(jù)元素的個數(shù)取決于刪除元素的位置。

最好情形：刪除表尾元素，不需要移動其它元素（移動個數(shù)為0）；

最壞情形：刪除序號為1的元素，需要將表中其他的元素全部向前移（移動個數(shù)為n-1）；刪除時，數(shù)據(jù)平均移動次數(shù)AMN：可供刪除的位置有n個；假設(shè)刪除第i個元素的概率為Pi，刪除第i個元素，數(shù)據(jù)移動的次數(shù)為（n-i）個；不失一般性，等概率Pi=1/n（a1,…,ak,ak+1,…,an）（a1,…,ak,x,ak+1,…,an）1a12a2……kakk+1ak+1……lengthan……MaxSize1a12a2……kakk+1xk+2ak+1……lengthan-1length+1an…MaxSize插入x插入前插入后-操作5：插入插入算法（程序3-5）template<classT>LinearList<T>&LinearList<T>::Insert(intk,constT&x){if(k<0||k>length)throwOutOfBounds();//越界異常if(length==MaxSize)throwNoMem();//空間異常

for(inti=length-1;i>=k;i--)element[i+1]=element[i];

//元素后移

element[k]=x;

length++;

return*this;}時間復(fù)雜度：O(length-k)-插入算法分析插入算法的時間代價主要耗費在移動數(shù)據(jù)元素上，移動數(shù)據(jù)元素的個數(shù)取決于插入元素的位置。

最好情形：在表尾追加一個新元素，不需要移動其它元素（移動個數(shù)為0）；

最壞情形：在序號為1的元素之前插入一個元素，需要將表中所有的元素全部向后移（移動個數(shù)為n）；插入時，數(shù)據(jù)平均移動次數(shù)AMN：可供插入的位置有n+1個；假設(shè)在第i個元素之前插入一個元素的概率為Pi，在第i個元素之前插入，數(shù)據(jù)移動的次數(shù)為（n-i+1）個；不失一般性，等概率Pi=1/（n+1）-操作6-輸出（程序3-6）template<classT>voidLinearList<T>::Output(ostream&out)const{//Putthelistintothestreamout.for(inti=0;i<length;i++)out<<element[i]<<"";}template<classT>//輸出流操作符<<重載ostream&operator<<(ostream&out,constLinearList<T>&x){x.Output(out);returnout;}外部調(diào)用：cout<<L;時間復(fù)雜度：Θ(length)-操作7：順序表的原地逆置template<classT>LinearList<T>&LinearList<T>::Reverse(){

空間要求：只能使用一個臨時變量T}for(inti=0;i<length/2;i++)Swap(element[i],element[length-1-i]);return*this;公式化描述方法（順序表）分析【特點】邏輯結(jié)構(gòu)上相鄰的元素其物理結(jié)構(gòu)也相鄰。查找、刪除、插入算法：與表的大小呈線性的關(guān)系?！救秉c】空間的低效利用。問題2：插入、刪除算法涉及頻繁元素移動，如何改進？問題1：如何做到根據(jù)元素增長，動態(tài)分配T*element？【優(yōu)點】存取操作速度快。多個線性表公用一個數(shù)組空間first[1]last[1]first[2]first[3]last[2]last[3]一種解決空間低效利用的方法！1234……789使用線性表（程序3-7）程序運行結(jié)果：課后作業(yè)編碼實現(xiàn)：Page85【練習7】【練習8】有序表的合并、拆分函數(shù)原型聲明（參考形式）template<classT>LinearList<T>&LinearList<T>::Merge(LinearList<T>&LA,LinearList<T>&LB);10月7日前發(fā)至：fangfangcug@126.com

郵件名稱：11108X-XX-順序表合并、拆分本章教學內(nèi)容3.2線性表ADT3.3線性表的公式化描述（數(shù)組表示）3.4線性表的鏈表描述3.5線性表的應(yīng)用3.4鏈表描述1、定義用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序通過鏈表中指針鏈接次序?qū)崿F(xiàn)的。為了表示每個元素ai與其直接后繼ai+1之間的邏輯關(guān)系存儲數(shù)據(jù)元素本身的信息；存儲指示其直接后繼的信息（即直接后繼的存儲位置）。鏈式存儲結(jié)構(gòu)中每個數(shù)據(jù)元素占用一個節(jié)點（Node），一個節(jié)點由兩個域組成：

數(shù)據(jù)域（設(shè)域名為data）：存儲數(shù)據(jù)元素信息的域；

指針域（設(shè)域名為link）：存儲直接后繼存儲位置的域，指針域中存儲的信息稱作指針或鏈。datalink鏈表節(jié)點結(jié)構(gòu)adatalink例：設(shè)有線性表（A,B,C,D,E,F），該線性表的鏈表形式如下：ABCDEF∧firstlast鏈表邏輯結(jié)構(gòu)示意圖（1）數(shù)據(jù)域：存放數(shù)據(jù)元素A、B、C、D、E、F的域；（2）指針域：存放指針的域；（3）節(jié)點：包含數(shù)據(jù)域值和指針域值；（4）第一個節(jié)點（首元節(jié)點）：節(jié)點A；尾節(jié)點：節(jié)點F;（5）A節(jié)點稱為B節(jié)點的直接前驅(qū)，B節(jié)點稱為A節(jié)點的直接后繼；（6）first稱為表頭指針；last稱為鏈尾指針；（7）最后一個節(jié)點的指針不指向任何節(jié)點，稱為空指針（NULL）。鏈表中常用的幾個概念鏈表中每個節(jié)點可以包含若干個數(shù)據(jù)域和指針域。根據(jù)指針的數(shù)量和性質(zhì)的不同，可以將鏈表分為以下類型:按指針數(shù)量分類按指針性質(zhì)分類單鏈表——只有一個指針域多鏈表——有多個指針域（多為雙向鏈表）普通鏈表（非循環(huán)鏈表）循環(huán)鏈表鏈表的分類1、定義：若鏈表中的每個節(jié)點只有一個指針域。2、單鏈表的邏輯狀態(tài)和物理狀態(tài)數(shù)據(jù)元素之間的相對關(guān)系是由鏈表中的指針域所指示的；單鏈表中的節(jié)點之間由鏈建立起來的邏輯順序必須和線性表中相應(yīng)的數(shù)據(jù)元素的順序相一致；數(shù)據(jù)元素在內(nèi)存中以任意次序存放。單鏈表中必須指出第一個節(jié)點的存儲地址，所以需要設(shè)立一個特殊的指針，稱為頭指針。整個鏈表的存取都是從頭指針開始進行的。單鏈表（線性鏈表）例：設(shè)有線性表（a1，a2，a3，a4，a5，a6），采用單鏈表進行存儲，其物理狀態(tài)如下圖所示:存儲地址數(shù)據(jù)域指針域21a58234a24545a3665058a13466a42182a6NULL8758first單鏈表存儲狀態(tài)示例單鏈表的邏輯結(jié)構(gòu)示意圖鏈接（指針）域數(shù)據(jù)域abcdeNULLfirst鏈表中每個節(jié)點代表一個元素；每個節(jié)點包含一個指針，指向下一個節(jié)點；

最后一個節(jié)點的指針域是NULL。單鏈表類定義-節(jié)點類ChianNode（程序3-8）template<classT>classChainNode{friendChain<T>;private:Tdata;ChainNode<T>*link;};linkdata單鏈表類定義-單鏈表類Chian（程序3-8）template<classT>classChain{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;//指向第一個節(jié)點的指針};線性表的鏈表描述不需要指定表的最大長度。補充：指針的基本操作實例操作內(nèi)容執(zhí)行操作的語句執(zhí)行前后指針指向節(jié)點指針指向后繼指針移動指針改接指針改接后繼p=qp=q->linkp=p->linkp->link=qp->link=q->linkBCDpqEFq-操作1：刪除表中所有節(jié)點（程序3-9）template<classT>Chain<T>::~Chain(){

ChainNode<T>*next;

while(first)

{

next=first->link;

deletefirst;

first=next;}}時間復(fù)雜度：Θ(n)-操作2：確定鏈表長度（程序3-10）template<classT>intChain<T>::Length()const{//Returnthenumberofelementsinthechain.ChainNode<T>*current=first;intlen=0;

while(current){len++;current=current->link;}returnlen;}時間復(fù)雜度：Θ(n)-操作3：在鏈表中查找第k個元素（程序3-11）template<classT>boolChain<T>::Find(intk,T&x)const{//Setxtothek'thelementinthechain.//Returnfalseifnok'th;returntrueotherwise.if(k<1)returnfalse;ChainNode<T>*current=first;intindex=1;//indexofcurrent

while(index<k&¤t){current=current->link;index++;}if(current){x=current->data;returntrue;}returnfalse;//nok'thelement}時間復(fù)雜度：Θ(n)-操作4：在鏈表中搜素（程序3-12）template<classT>intChain<T>::Search(constT&x)const{//Locatex.Returnpositionofxiffound.//Return0ifxnotinthechain.ChainNode<T>*current=first;intindex=1;//indexofcurrent

while(current&¤t->data!=x){current=current->link;index++;}if(current)returnindex;return0;}時間復(fù)雜度：Θ(n)-操作5：輸出鏈表（程序3-13）template<classT>voidChain<T>::Output(ostream&out)const{

//Insertthechainelementsintothestreamout.

ChainNode<T>*current;

for(current=first;current;current=current->link)

out<<current->data<<"";}//overload<<template<classT>ostream&operator<<(ostream&out,constChain<T>&x){

x.Output(out);

returnout;}時間復(fù)雜度：Θ(n)-操作6：刪除節(jié)點：Delete(1,x)abcdeNULLfirstp=first;first=first->link;deletep;p刪除表頭節(jié)點刪除節(jié)點：Delete(3,x)abdeNULLfirstc第1步，到達要刪除節(jié)點的前一個節(jié)點

。ccbq刪除非表頭節(jié)點刪除節(jié)點：Delete(3,x)第2步，保存指向待刪節(jié)點的指針。p=q->link;qabcdeNULLfirstp刪除節(jié)點：Delete(3,x)第3步，改變前節(jié)點的指針域，使其指向待刪節(jié)點的后一節(jié)點。q->link=p->link;deletep;qabcdeNULLfirstp-刪除算法（程序3-14）template<classT>Chain<T>&Chain<T>::Delete(intk,T&x){

//Setxtothek'thelementanddeleteit.

//ThrowOutOfBoundsexceptionifnok'thelement.

if(k<1||!first)throwOutOfBounds();//nok'th

//pwilleventuallypointtok'thnode

ChainNode<T>*p=first;

//moveptok'th&removefromchainif(k==1)

//palreadyatk'thfirst=first->link;//remove

-刪除算法（續(xù)）（程序3-14）else{

//useqtogettok-1'stChainNode<T>*q=first;for(intindex=1;index<k-1&&q;index++)

q=q->link;if(!q||!q->link)throwOutOfBounds(

);

//nok'thp=q->link;

//k'thq->link=p->link;}

//removefromchain

//savek'thelementandfreenodep

x=p->data;

deletep;

retu