第9章 線性結(jié)構(gòu)

1、第三部分第三部分 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)本章內(nèi)容 數(shù)據(jù)結(jié)構(gòu)概述 線性表 棧 隊(duì)列2 2l幾個(gè)常用術(shù)語： 數(shù)據(jù)：計(jì)算機(jī)能夠識(shí)別、存儲(chǔ)和處理的符號(hào)的集合。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位，由一或多個(gè)數(shù)據(jù)項(xiàng)組成。又稱結(jié)點(diǎn)、頂點(diǎn)、記錄、表目等。 數(shù)據(jù)項(xiàng)：具有獨(dú)立含義的數(shù)據(jù)的最小單位，又稱為域、字段。 數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素集合。9.1數(shù)據(jù)結(jié)構(gòu)概述3 3 例1：英文字母表 A,B.Z 數(shù)據(jù)對(duì)象是整個(gè)英文字母表，數(shù)據(jù)元素是字母字符，每個(gè)數(shù)據(jù)元素只由一個(gè)數(shù)據(jù)項(xiàng)組成。 例2：職工情況表 職工情況表是一個(gè)數(shù)據(jù)對(duì)象，每個(gè)職工情況為一數(shù)據(jù)元素，數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成4 4數(shù)據(jù)結(jié)構(gòu)的概念包括三方面的內(nèi)容數(shù)據(jù)數(shù)

2、據(jù)結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)集合線性樹圖數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序鏈接索引散列數(shù)據(jù)的運(yùn)算插入插入刪除刪除查找查找更新更新排序排序5 5數(shù)據(jù)的邏輯結(jié)構(gòu)l數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映出數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。 集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是“屬于同一集合”，集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。 線性結(jié)構(gòu)：除第一個(gè)和最后一個(gè)元素外，其他每個(gè)元素都僅有一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素。 樹形結(jié)構(gòu)：每個(gè)元素若有直接前驅(qū)元素（前件），只能有一個(gè)，但可以有多個(gè)直接后繼元素（后件）。 圖形結(jié)構(gòu)：每個(gè)元素都可以有多個(gè)前件和多個(gè)后件。6 6數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)l 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏

3、輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存儲(chǔ)器中的實(shí)現(xiàn)。l 四種基本的存儲(chǔ)映象方式： 順序方式 鏈接方式 索引方式 散列方式7 7順序方式l 將數(shù)據(jù)元素按照某種順序存放到一片連續(xù)的存儲(chǔ)單元內(nèi)，數(shù)據(jù)元素之間的邏輯關(guān)系是通過它們?cè)诖鎯?chǔ)器中的相對(duì)位置來體現(xiàn)的。l 例：英語字母表的順序存儲(chǔ)。ABCXYZl 優(yōu)點(diǎn)： 存儲(chǔ)密度高。 可對(duì)元素隨機(jī)訪問。l 缺點(diǎn)： 插入或刪除元素時(shí)效率低。 存儲(chǔ)空間需預(yù)先分配，太大浪費(fèi)，太小溢出。8 8線性表的插入9 929185663352431470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB

4、180 x1234FB1C0 x1234FB200 x1234FB24392918566339352431470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB180 x1234FB1C0 x1234FB200 x1234FB2429185663352431470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB180 x1234FB1C0 x1234FB200 x1234FB24296335245

5、631470 x1234FB000 x1234FB040 x1234FB080 x1234FB0C0 x1234FB100 x1234FB140 x1234FB180 x1234FB1C0 x1234FB200 x1234FB24線性表的刪除101029185663352431472918566335243147392918566335243147鏈表的插入和刪除1111鏈接方式l 邏輯上相鄰的元素在物理位置上未必相鄰，元素間的邏輯關(guān)系由附加的指針域表示。l 例：鏈接方式存儲(chǔ)的線性結(jié)構(gòu)第一個(gè)職工情況第一個(gè)職工情況第二個(gè)職工情況第二個(gè)職工情況最后一個(gè)職工情況最后一個(gè)職工情況headl 優(yōu)點(diǎn)： 插

6、入和刪除元素時(shí)，不會(huì)引起大量元素的移動(dòng)。 可動(dòng)態(tài)申請(qǐng)和釋放結(jié)點(diǎn)空間。l 缺點(diǎn)： 每個(gè)結(jié)點(diǎn)中的指針域會(huì)耗費(fèi)一些存儲(chǔ)空間。 不能實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的隨機(jī)訪問。1212索引方式l 在存儲(chǔ)數(shù)據(jù)元素的同時(shí)，建立一個(gè)附加的索引表，索引表中的每一行稱為一個(gè)索引項(xiàng)。l 其一般形式為：（關(guān)鍵字，地址） 關(guān)鍵字：是指能夠唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)。例如，職工情況表中的“職工號(hào)”。l 優(yōu)點(diǎn)：檢索速度快。l 缺點(diǎn)： 增加的索引表會(huì)占用較多的存儲(chǔ)空間； 在插入和刪除數(shù)據(jù)元素時(shí)需要修改索引表，因而會(huì)花費(fèi)更多的時(shí)間。1313散列方式l 數(shù)據(jù)元素的存儲(chǔ)地址是用它的關(guān)鍵字計(jì)算出來的l 散列方式又稱為哈希表、雜湊表等。l

7、 優(yōu)點(diǎn)：檢索、增加和刪除元素的操作都很快。l 缺點(diǎn)：如果使用了不好的散列函數(shù)，可能會(huì)出現(xiàn)存儲(chǔ)單元的沖突，為解決沖突需要額外的時(shí)間和空間開銷。補(bǔ)充：四種存儲(chǔ)方式可以組合使用。u如硬盤文件的組織采用順序和鏈接結(jié)合方式。同一邏輯結(jié)構(gòu)可以采用不同的存儲(chǔ)方式，生成不同的數(shù)據(jù)結(jié)構(gòu)。1414數(shù)據(jù)的運(yùn)算l 數(shù)據(jù)的運(yùn)算是對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)所進(jìn)行的加工和處理。l 常用的數(shù)據(jù)運(yùn)算包括插入、刪除、查找、排序、更新等。l 數(shù)據(jù)的運(yùn)算定義在邏輯結(jié)構(gòu)之上，實(shí)現(xiàn)在存儲(chǔ)結(jié)構(gòu)之上。用算法描述。 算法是對(duì)解決問題方法的精確描述，是用來完成某個(gè)特定任務(wù)的有限步驟序列。1515算法的基本特征有窮性：一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，并且

8、每一步都能在有限的時(shí)間內(nèi)完成。確定性：算法中的每一條指令必須具有確切的含義，且無二義性。可行性：算法中描述的所有操作都可以通過讓已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次完成。輸入：一個(gè)算法應(yīng)該有0個(gè)或多個(gè)輸入。這些輸入應(yīng)取自于某個(gè)特定的對(duì)象集合。輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這些輸出是與輸入有某種特定關(guān)系的量。1616算法的描述l 自然語言描述、算法語言、程序設(shè)計(jì)語言（如C+）描述、流程圖描述等。算法的評(píng)價(jià)l 算法的時(shí)間復(fù)雜度：根據(jù)算法編寫出的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間。一般把程序運(yùn)行時(shí)（基本）語句的執(zhí)行次數(shù)作為估算程序執(zhí)行時(shí)間的量度。l 算法的空間復(fù)雜度：根據(jù)算法編寫出的程序在計(jì)算機(jī)上運(yùn)行時(shí)所

9、需要的存儲(chǔ)空間的大小。包括指令、常量、變量所占用的空間；輸入數(shù)據(jù)占據(jù)的空間；程序執(zhí)行時(shí)需要使用的輔助空間。17179.2線性表l 通常所說的線性表是指其邏輯結(jié)構(gòu)。是由（0）個(gè)相同類型的數(shù)據(jù)元素e0、e1、en-1 組成的有限序列 。可抽象的表示為：（e0，e1，ei-1，ei，ei+1，en-1） 開始元素 中間元素 終端元素 線性表中元素的個(gè)數(shù)稱為表的長度。長度為0的表為空表。元素在表中的序號(hào)稱做元素的下標(biāo)。1818線性表的存儲(chǔ)結(jié)構(gòu)l 以順序方式存儲(chǔ)的線性表稱為順序表。 可以用一維數(shù)組實(shí)現(xiàn)順序表。例如英文字母表的順序存儲(chǔ)。char table26;l 以鏈接方式存儲(chǔ)的線性表稱為鏈表。 常用鏈

10、表形式有單鏈表、循環(huán)鏈表和雙鏈表等。線性表常用的基本運(yùn)算l 創(chuàng)建一個(gè)空表；判表空；求表長；l 刪除下標(biāo)為i的數(shù)據(jù)元素；刪除表中所有元素；l 在下標(biāo)為i的元素之前插入一個(gè)新的數(shù)據(jù)元素；l 取下標(biāo)為i的數(shù)據(jù)元素；在表中查找與給定值x相等的數(shù)據(jù)元素。19192020#include #include #include #include using namespace std;using namespace std;class SeqListclass SeqListpublic:public: SeqList(int m=10); SeqList(int m=10); / /構(gòu)造函數(shù)構(gòu)造函數(shù) Seq

11、List()delete element; SeqList()delete element;/ /析構(gòu)函數(shù)析構(gòu)函數(shù) bool IsEmpty()return length=0;bool IsEmpty()return length=0;/ /判表是否為空判表是否為空 int Length()return length;int Length()return length;/ /返回表長返回表長 bool Find(int i, int &x); bool Find(int i, int &x); / /把下標(biāo)為把下標(biāo)為i i的元素取至的元素取至x x int Search(const int &

12、x); int Search(const int &x); / /返回返回x x在表中的下標(biāo)在表中的下標(biāo) void Insert(int i, const int &x); void Insert(int i, const int &x); / /在下標(biāo)在下標(biāo)i i處插入元素處插入元素x x void Delete(int i, int &x); void Delete(int i, int &x); / /返回下標(biāo)為返回下標(biāo)為i i的元素至的元素至x x，并刪除之，并刪除之 void ClearList()length=0;void ClearList()length=0;/ /將表清空將表

13、清空 void Output(ostream &out); void Output(ostream &out); / /輸出表中所有元素的值輸出表中所有元素的值 friend ostream& operator(ostream &out, SeqList &x); friend ostream& operator(ostream &out, SeqList &x); private:private:int Maxsize, length;int Maxsize, length;int int * *element;element; ;/ /構(gòu)造函數(shù)：構(gòu)造函數(shù)：/ /建立一個(gè)空表建立一個(gè)空表Se

14、qList:SeqList(int m)SeqList:SeqList(int m) element=new intm; element=new intm; Maxsize=m; Maxsize=m; length=0; length=0; /Find()/Find()函數(shù)：函數(shù)：bool bool SeqList:Find(int i, int &x)SeqList:Find(int i, int &x) if(ilength-1) if(ilength-1)return false;return false; x=elementi; x=elementi; return true; ret

15、urn true; /Search()/Search()函數(shù)：函數(shù)：intint SeqList:Search(const int &x)SeqList:Search(const int &x) for(int i=0;ilength;i+) for(int i=0;ilength;i+) if(elementi=x) return i; if(elementi=x) return i; return -1; return -1; /Insert()/Insert()函數(shù)：函數(shù)：voidvoid SeqList:Insert(int i, const int &x)SeqList:Insert

16、(int i, const int &x) if(ilength) if(ilength) cout cout下標(biāo)越界下標(biāo)越界n;n; if(length=Maxsize) if(length=Maxsize) cout cout=i; k-) for(int k=length-1; k=i; k-) elementk+1=elementk; elementk+1=elementk; elementi=x; elementi=x; length+; length+; /Delete()/Delete()函數(shù)：函數(shù)：voidvoid SeqList:Delete(int i, int &x)Se

17、qList:Delete(int i, int &x) if(Find(i,x) if(Find(i,x) for(int k=i;klength-1;k+) for(int k=i;klength-1;k+) elementk=elementk+1; elementk=elementk+1; length-; length-; else cout else cout下標(biāo)越界下標(biāo)越界n;n; /Output()/Output()函數(shù)：函數(shù)：voidvoid SeqList:SeqList: Output(ostream &out)Output(ostream &out) for(int i=0

18、;ilength;i+) for(int i=0;ilength;i+) outelementi ; outelementi ; / /友元方式重載友元方式重載 “” “”：ostream& operator(ostream &out, const SeqList &x)ostream& operator(ostream &out, const SeqList &x) x.Output(out); x.Output(out); return out; return out; / /友元方式重載友元方式重載 “” “”：ostream& operator(ostream &out, const

19、SeqList &x)ostream& operator(ostream &out, const SeqList &x) for(int i=0;ix.length;i+)for(int i=0;ix.length;i+) outx.elementi ; outx.elementi ;return out;return out; / /重載為成員函數(shù)行不行？重載為成員函數(shù)行不行？SeqList & SeqList:operator(ostream &out)SeqList & SeqList:operator(ostream &out) for(int i=0;ilength;i+)for(i

20、nt i=0;ilength;i+) outelementi ; outelementi ; 會(huì)有什么問題么？會(huì)有什么問題么？調(diào)用時(shí)：調(diào)用時(shí)：l 不能寫成：不能寫成：coutx;coutx;l 只能寫成：只能寫成：xcout;xcout;線性表的鏈接存儲(chǔ)結(jié)構(gòu)（鏈表）l 單鏈表中的結(jié)點(diǎn)：l 單鏈表：datanextl 帶頭結(jié)點(diǎn)的單鏈表：在一般形式的單鏈表中進(jìn)行插入、刪除操作時(shí)，必須針對(duì)不同的情況采取不同的處理方法，這為編寫程序帶來一定的難度和潛在的危險(xiǎn)。在帶頭結(jié)點(diǎn)的單鏈表中進(jìn)行插入、刪除操作時(shí)，無須考慮特殊情況。l 空表 2121結(jié)點(diǎn)類的定義2222#include #include #incl

21、ude #include using namespace std;using namespace std;class Chain;class Chain; / /單鏈表類單鏈表類ChainChain的前視聲明的前視聲明class class NodeNode/ /單鏈表結(jié)點(diǎn)類的定義單鏈表結(jié)點(diǎn)類的定義 friend class Chain;friend class Chain; / /定義類定義類ChainChain為友元為友元private:private: int data;int data;/ /結(jié)點(diǎn)的數(shù)據(jù)域結(jié)點(diǎn)的數(shù)據(jù)域 Node Node * *next;next;/ /結(jié)點(diǎn)的指針域結(jié)點(diǎn)

22、的指針域; ;2323class class ChainChain/ /單鏈表類的定義單鏈表類的定義 public:public:Chain();Chain();Chain();Chain();bool IsEmpty() return length=0; bool IsEmpty() return length=0; int Length() return length; int Length() return length; bool Find(int i,int &x);bool Find(int i,int &x);int Search(const int &x);int Search

23、(const int &x); void Insert(int i,const int &x);void Insert(int i,const int &x); void Delete(int i,int &x);void Delete(int i,int &x);void ClearList();void ClearList(); void Output(ostream &out)const;void Output(ostream &out)const; friend ostream& operator(ostream &out,const Chain &x)friend ostream&

24、operatornext=NULL; head-next=NULL; length=0; length=0; / /析構(gòu)函數(shù)：析構(gòu)函數(shù)：Chain:Chain()Chain:Chain() ClearList();ClearList();delete head;delete head; /Find()/Find()函數(shù)：函數(shù)：bool Chain:Find(int i, int &x)bool Chain:Find(int i, int &x) if(ilength-1) return false;if(ilength-1) return false;Node Node * *p=head-n

25、ext;p=head-next;int k=0;int k=0;while(ki)while(knext;p=p-next;k+;k+; x=p-data;x=p-data;return true;return true; /Search()/Search()函數(shù)：函數(shù)：int Chain:Search(const int &x)int Chain:Search(const int &x) Node Node * *p=head-next;p=head-next;int i=0;int i=0;while(p!=NULL)while(p!=NULL) if(p-data=x) return i

26、;if(p-data=x) return i;p=p-next;p=p-next;i+;i+; return -1;return -1; void Chain:Insert(int i, const int &x)void Chain:Insert(int i, const int &x) if(ilength)if(ilength)coutcout下標(biāo)越界下標(biāo)越界n;n; Node Node * *p=head;p=head;int k=0;int k=0;/ /找到第找到第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)while(knext; k+; while(knext; k+; / /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)

27、Node Node * *q=new Node;q=new Node;q-data=x;q-data=x;q-next=p-next;q-next=p-next;p-next=q;p-next=q;length+;length+; void Chain:Delete(int i, int &x) void Chain:Delete(int i, int &x) if(ilength)if(ilength)coutcout下標(biāo)越界下標(biāo)越界n;n;/ /找到第找到第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) Node Node * *p=head;p=head;for(int k=0;knext;for(int k

28、=0;knext;/ /找到要?jiǎng)h除的結(jié)點(diǎn)找到要?jiǎng)h除的結(jié)點(diǎn)Node Node * *q=p-next; q=p-next; x=q-data; x=q-data; / /保存刪除結(jié)點(diǎn)的值保存刪除結(jié)點(diǎn)的值p-next=q-next;p-next=q-next;/ /改變第改變第i-1i-1個(gè)結(jié)點(diǎn)指針域個(gè)結(jié)點(diǎn)指針域delete q; delete q; / /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)length-;length-; /ClearList()/ClearList()函數(shù)清空表函數(shù)清空表void Chain:ClearList()void Chain:ClearList() Node Node * *p=hea

29、d-next, p=head-next, * *q;q;while(p!=NULL)while(p!=NULL) q=p;q=p;p=p-next;p=p-next;delete q;delete q; head-next=NULL; head-next=NULL; length=0;length=0; /Output()/Output()函數(shù)：函數(shù)：void Chain:void Chain: Output(ostream &out)utput(ostream &out) Node Node * *p=head-next;p=head-next;while(p!=NULL)while(p!=

30、NULL) outdatanext; outdatanext; / /友元方式重載友元方式重載 “” “”：ostream& operator(ostream &out, Chain &x)ostream& operator(ostream &out, Chain &x) x.output(out); x.output(out); return out; return out; 其它形式的鏈表l 單循環(huán)鏈表l 設(shè)置尾指針的單循環(huán)鏈表l 雙鏈表l 雙循環(huán)鏈表24249.3棧（Stack）l 棧的定義：只能在一端進(jìn)行插入和刪除運(yùn)算的線性表。l 棧的特點(diǎn)：后進(jìn)先出原則（Last In First Out，LIFO） 。l 術(shù)語：棧頂棧底入棧出棧2525棧的基本運(yùn)算l 入棧、出棧、判?？?、取棧頂元素、置?？誥bcabcacbacbbacbacbcabcacabcabcbacba 棧的入棧和出棧操作可以穿插進(jìn)行，所以對(duì)應(yīng)于相同的入棧序列其出棧序列可以有多種。 討論：入棧序列為abc，出棧序列有多少種可能？ cabefd和efdcab 等均為不可能出現(xiàn)的出棧序列。2626順序棧l 以順序方式存儲(chǔ)的棧稱為順序棧。l 順序?？梢杂靡痪S數(shù)組實(shí)現(xiàn)。l 需要一個(gè)整型變量top指示當(dāng)前棧頂位置 。l 當(dāng)使用兩個(gè)棧時(shí)，可讓它們共享一個(gè)一維數(shù)組空間，以達(dá)到節(jié)省存儲(chǔ)空間和降低上溢發(fā)生頻率的目的。28a