《數(shù)據(jù)結(jié)構(gòu)》課件1第2章 線性表

第2章線性表線性表的邏輯結(jié)構(gòu)線性表的順序表示和實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)順序表和鏈表的比較線性表的應(yīng)用2.1線性表的邏輯結(jié)構(gòu)2線性表是由類型相同的數(shù)據(jù)元素組成的有限序列。線性表的數(shù)據(jù)元素可以是數(shù)字、字符或更復(fù)雜的信息。英語(yǔ)字母表：(’a’,’b’,’c’,’d’,……,’x’,’y’,’z’)一個(gè)人的一年的月收入：(5000,5200,4890,4890,……,5300)學(xué)生成績(jī)表：2.1線性表的邏輯結(jié)構(gòu)3

線性表的定義二元組表示

邏輯關(guān)系圖2.1線性表的邏輯結(jié)構(gòu)4

線性表的抽象數(shù)據(jù)類型定義GetElem(i,&e)初始條件：線性表已存在，1≤i≤length。操作結(jié)果：用e返回第i個(gè)元素的值。SetElem(i,e)初始條件：線性表已存在，1≤i≤length。操作結(jié)果：將線性表的第i個(gè)位置的元素賦值為e。Search(e)初始條件：線性表已存在。操作結(jié)果：在線性表中查找值為e的元素，若查找成功，返回其所在的位置，否則返回0。Insert(i,e)初始條件：線性表已存在，1≤i≤ength+1。操作結(jié)果：在線性表的第i個(gè)元素前插入元素e，線性表長(zhǎng)度加1。Delete(i,&e)初始條件：線性表已存在，1≤i≤length。操作結(jié)果：刪除線性表的第i個(gè)元素，并用e返回其值，線性表長(zhǎng)度減1。}2.2線性表的順序表示和實(shí)現(xiàn)1.線性表的順序存儲(chǔ)結(jié)構(gòu)——順序表5

2.2線性表的順序表示和實(shí)現(xiàn)2.順序表的實(shí)現(xiàn)6template<typenameT>classSqList{private: intmaxsize; //順序表可能達(dá)到的最大長(zhǎng)度

intlength; //順序表的長(zhǎng)度

T*elem; //存儲(chǔ)空間的基地址public: SqList(intsize=DEFAULT_SIZE); //構(gòu)造函數(shù)，DEFAULT_SIZE為符號(hào)常量

SqList(Ta[],intn); //構(gòu)造函數(shù) SqList(SqList<T>&sl); //復(fù)制構(gòu)造函數(shù)

~SqList(); //析構(gòu)函數(shù)

intLength(); //求順序表長(zhǎng)度

boolEmpty(); //判斷表是否為空

voidClear(); //清空順序表

voidPrintList(); //輸出表中的各個(gè)元素

boolGetElem(inti,T&e); //獲取指定位置的元素值

boolSetElem(inti,Te); //設(shè)置指定位置的元素值

intSearch(Te); //查找元素

boolInsert(inti,Te); //插入元素

boolDelete(inti,T&e); //刪除元素};類模板定義2.2線性表的順序表示和實(shí)現(xiàn)2.順序表的實(shí)現(xiàn)7基本操作//求順序表的長(zhǎng)度template<typenameT>intSqList<T>::Length(){ returnlength;}//判斷順序表是否為空template<typenameT>boolSqList<T>::Empty(){ if(length==0) returntrue; else returnfalse;}//清空順序表template<typenameT>voidSqList<T>::Clear(){ length=0;}//讀取元素的值template<typenameT>boolSqList<T>::GetElem(inti,T&e){ if(i<1||i>length) returnfalse; e=elem[i-1]; returntrue;}//設(shè)置元素的值template<typenameT>boolSqList<T>::SetElem(inti,Te){ if(i<1||i>length) returnfalse; elem[i-1]=e; returntrue;}//查找操作template<typenameT>intSqList<T>::Search(Te){ inti; for(i=0;i<length;i++) if(e==elem[i]) returni+1; return0;}2.2線性表的順序表示和實(shí)現(xiàn)2.順序表的實(shí)現(xiàn)8插入操作template<typenameT>boolSqList<T>::Insert(inti,Te){ if(length==maxsize)

returnfalse; if(i<1||i>length+1) returnfalse; for(intj=length;j>=i;j--) elem[j]=elem[j-1]; elem[i-1]=e; length++; returntrue;}算法分析

假設(shè)在線性表的任意位置上插入元素的概率相等，即：則：

插入算法的時(shí)間復(fù)雜度為：O(n)

2.2線性表的順序表示和實(shí)現(xiàn)2.順序表的實(shí)現(xiàn)9刪除操作template<classT>boolSqList<T>::Delete(inti,T&e){ if(i<1||i>length) returnfalse; e=elem[i-1]; for(intj=i;j<length;j++) elem[j-1]=elem[j]; length--; returntrue;}

刪除算法的時(shí)間復(fù)雜度為：O(n)算法分析2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈表。鏈表是用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素，這些存儲(chǔ)單元可以連續(xù)也可以不連續(xù)，甚至可以零散分布在內(nèi)存中的任意位置。鏈表中，每個(gè)數(shù)據(jù)元素用一個(gè)結(jié)點(diǎn)來(lái)存儲(chǔ)，結(jié)點(diǎn)不僅包含元素本身的信息（稱為數(shù)據(jù)域），而且包含表示元素之間邏輯關(guān)系的信息（在C++語(yǔ)言中用指針來(lái)實(shí)現(xiàn)，稱為指針域）。由于線性表中的每個(gè)元素最多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素，因此采用鏈?zhǔn)酱鎯?chǔ)時(shí)，一種最簡(jiǎn)單、最常用的方法是在每個(gè)結(jié)點(diǎn)中除包含數(shù)據(jù)域之外只設(shè)置一個(gè)指針域，用于指向其后繼結(jié)點(diǎn)，這樣的鏈表稱為單鏈表；另一種方法是在每個(gè)結(jié)點(diǎn)中除包含數(shù)據(jù)域之外設(shè)置兩個(gè)指針域，分別用于指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，這樣的鏈表稱為雙鏈表。1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表102.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表是一種最簡(jiǎn)單的線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用它來(lái)存儲(chǔ)線性表時(shí)，為了能正確表示元素之間的邏輯關(guān)系，每個(gè)結(jié)點(diǎn)在存儲(chǔ)數(shù)據(jù)元素的同時(shí)，還必須存儲(chǔ)其后繼元素所在的地址信息。2.單鏈表的定義和表示11結(jié)點(diǎn)示意圖：p->data：該結(jié)點(diǎn)的數(shù)據(jù)元素p->next：指向該結(jié)點(diǎn)的后繼datanextp單鏈表結(jié)構(gòu)示意圖：a1a2an

∧…h(huán)ead頭結(jié)點(diǎn)：沒(méi)有存儲(chǔ)任何數(shù)據(jù)增加頭結(jié)點(diǎn)：算法實(shí)現(xiàn)更簡(jiǎn)單，效率更高頭指針指向單鏈表的頭結(jié)點(diǎn)空鏈表示意圖：∧head結(jié)點(diǎn)定義template<classT>structNode{ Tdata; //數(shù)據(jù)域

Node<T>*next; //指針域};2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)3.單鏈表的實(shí)現(xiàn)1212基本操作//求單鏈表的長(zhǎng)度template<typenameT>intLinkList<T>::Length(){ intlen=0; Node<T>*p=head->next; while(p!=NULL) { len++; p=p->next; } returnlen;}//判斷表是否為空template<typenameT>boolLinkList<T>::Empty(){ returnhead->next==NULL;}//讀取元素的值template<typenameT>boolLinkList<T>::GetElem(inti,T&e){ if(i<1||i>Length()) returnfalse; Node<T>*p; p=GetPtr(i);

e=p->data;

returntrue;}//清空單鏈表template<typenameT>voidLinkList<T>::Clear(){ Node<T>*p=head->next; while(p!=NULL) { head->next=p->next;

deletep;

p=head->next;

}}//設(shè)置元素的值template<typenameT>boolLinkList<T>::SetElem(inti,Te){ if(i<1||i>Length()) returnfalse; Node<T>*p; p=GetPtr(i); p->data=e; returntrue;}//查找template<typenameT>intLinkList<T>::Search(Te){ Node<T>*p=head->next; inti=1; while(p!=NULL&&p->data!=e) { p=p->next; i++; } if(p==NULL) return0; else returni;}2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)3.單鏈表的實(shí)現(xiàn)1313插入操作template<typenameT>boolLinkList<T>::Insert(inti,Te){ if(i<1||i>Length()+1) returnfalse; Node<T>*q,*p; p=GetPtr(i-1); q=newNode<T>;

q->data=e; q->next=p->next; p->next=q; returntrue;}2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)3.單鏈表的實(shí)現(xiàn)1414刪除操作template<typenameT>boolLinkList<T>::Delete(inti,T&e){ if(i<1||i>Length()) returnfalse; Node<T>*p,*q; p=GetPtr(i-1); q=p->next; e=q->data; p->next=q->next; deleteq; returntrue;}2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)4.雙鏈表1515雙向鏈表（雙鏈表）的結(jié)點(diǎn)中有兩個(gè)指針，分別指向前驅(qū)和后繼。從雙鏈表的任一結(jié)點(diǎn)開(kāi)始，都可以方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。雙鏈表結(jié)點(diǎn)結(jié)構(gòu)：雙向鏈表通常采用帶頭結(jié)點(diǎn)的循環(huán)鏈表形式，稱為循環(huán)雙鏈表p->back：指向該結(jié)點(diǎn)的前驅(qū)p->data：

該結(jié)點(diǎn)的數(shù)據(jù)元素p->next：

指向該結(jié)點(diǎn)的后繼Back

data

nextp循環(huán)雙鏈表結(jié)構(gòu)：template<typenameT>structDbNode{ Tdata; DbNode<T>*prior; DbNode<T>*next;};結(jié)點(diǎn)定義：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)4.雙鏈表1616插入操作template<typenameT>boolDbLinkList<T>::Insert(inti,T&e){ if(i<1||i>Length()+1) returnfalse; DbNode<T>*p,*q; p=GetPtr(i-1); //p指向第i-1個(gè)結(jié)點(diǎn)

q=newDbNode<T>; //q指向新建結(jié)點(diǎn)

q->data=e; //為新結(jié)點(diǎn)的數(shù)據(jù)域賦值

q->prior=p; //新結(jié)點(diǎn)的前驅(qū)指向p q->next=p->next; //新結(jié)點(diǎn)的后繼指向p的后繼

if(p->next!=NULL) //若p存在后繼結(jié)點(diǎn)，修改其前驅(qū)指針

p->next->prior=q; p->next=q; //修改p的后繼指針

returntrue;}2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)4.雙鏈表1717刪除操作template<typenameT>boolDbLinkList<T>::Delete(inti,T&e){ if(i<1||i>Length()) returnfalse; DbNode<T>*p,*q; p=GetPtr(i-1); //p指向第i-1個(gè)結(jié)點(diǎn)

q=p->next; //q指向第i個(gè)結(jié)點(diǎn)

p->next=q->next; //修改p的后繼

if(q->next!=NULL) //若q存在后繼結(jié)點(diǎn)，修改其前驅(qū)指針

q->next->prior=p; e=q->data; //用e存儲(chǔ)要?jiǎng)h除的元素值

deleteq; //釋放被刪除結(jié)點(diǎn)所占的空間

returntrue;}2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)5.循環(huán)鏈表1818循環(huán)單鏈表：將終端結(jié)點(diǎn)的next域由指向頭結(jié)點(diǎn)，結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。示意圖：空循環(huán)鏈表的條件：head->next==head循環(huán)雙鏈表：將終端結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)的prior域指向終端結(jié)點(diǎn)，結(jié)點(diǎn)結(jié)構(gòu)與雙鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。示意圖：循環(huán)雙鏈表中可以通過(guò)head->prior快速找到終端結(jié)點(diǎn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)5.循環(huán)鏈表1919循環(huán)鏈表的基本操作實(shí)現(xiàn)算法與對(duì)應(yīng)非循環(huán)鏈表的算法基本相同，主要差別是對(duì)于空表或到達(dá)終端結(jié)點(diǎn)的判定條件不同。在單鏈表中，判斷空表的條件是head->next==NULL，判斷指針p指向終端結(jié)點(diǎn)的條件是p->next==NULL。在循環(huán)鏈表中，判斷空表的條件是head->next==head，判斷指針p指向終端結(jié)點(diǎn)的條件是p->next==head。2.4順序表和鏈表的比較201.空間性能的比較存儲(chǔ)空間的分配存儲(chǔ)密度的大小2.時(shí)間性能的比較由于順序表需要分配一定長(zhǎng)度的連續(xù)的存儲(chǔ)空間，因此，當(dāng)線性表的長(zhǎng)