第9章 線性結構

1、第三部分第三部分 數據結構基礎數據結構基礎本章內容 數據結構概述 線性表 棧 隊列2 2l幾個常用術語： 數據：計算機能夠識別、存儲和處理的符號的集合。 數據元素：數據的基本單位，由一或多個數據項組成。又稱結點、頂點、記錄、表目等。 數據項：具有獨立含義的數據的最小單位，又稱為域、字段。 數據對象：具有相同性質的數據元素集合。9.1數據結構概述3 3 例1：英文字母表 A,B.Z 數據對象是整個英文字母表，數據元素是字母字符，每個數據元素只由一個數據項組成。 例2：職工情況表 職工情況表是一個數據對象，每個職工情況為一數據元素，數據元素由多個數據項組成4 4數據結構的概念包括三方面的內容數據數

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

3、輯結構在計算機內存儲器中的實現。l 四種基本的存儲映象方式： 順序方式 鏈接方式 索引方式 散列方式7 7順序方式l 將數據元素按照某種順序存放到一片連續(xù)的存儲單元內，數據元素之間的邏輯關系是通過它們在存儲器中的相對位置來體現的。l 例：英語字母表的順序存儲。ABCXYZl 優(yōu)點： 存儲密度高。 可對元素隨機訪問。l 缺點： 插入或刪除元素時效率低。 存儲空間需預先分配，太大浪費，太小溢出。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 邏輯上相鄰的元素在物理位置上未必相鄰，元素間的邏輯關系由附加的指針域表示。l 例：鏈接方式存儲的線性結構第一個職工情況第一個職工情況第二個職工情況第二個職工情況最后一個職工情況最后一個職工情況headl 優(yōu)點： 插

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

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

8、每一步都能在有限的時間內完成。確定性：算法中的每一條指令必須具有確切的含義，且無二義性?？尚行裕核惴ㄖ忻枋龅乃胁僮鞫伎梢酝ㄟ^讓已實現的基本運算執(zhí)行有限次完成。輸入：一個算法應該有0個或多個輸入。這些輸入應取自于某個特定的對象集合。輸出：一個算法應該有一個或多個輸出。這些輸出是與輸入有某種特定關系的量。1616算法的描述l 自然語言描述、算法語言、程序設計語言（如C+）描述、流程圖描述等。算法的評價l 算法的時間復雜度：根據算法編寫出的程序在計算機上運行時所消耗的時間。一般把程序運行時（基本）語句的執(zhí)行次數作為估算程序執(zhí)行時間的量度。l 算法的空間復雜度：根據算法編寫出的程序在計算機上運行時所

9、需要的存儲空間的大小。包括指令、常量、變量所占用的空間；輸入數據占據的空間；程序執(zhí)行時需要使用的輔助空間。17179.2線性表l 通常所說的線性表是指其邏輯結構。是由（0）個相同類型的數據元素e0、e1、en-1 組成的有限序列 ?？沙橄蟮谋硎緸椋海╡0，e1，ei-1，ei，ei+1，en-1） 開始元素 中間元素 終端元素 線性表中元素的個數稱為表的長度。長度為0的表為空表。元素在表中的序號稱做元素的下標。1818線性表的存儲結構l 以順序方式存儲的線性表稱為順序表。 可以用一維數組實現順序表。例如英文字母表的順序存儲。char table26;l 以鏈接方式存儲的線性表稱為鏈表。 常用鏈

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

11、List()delete element; SeqList()delete element;/ /析構函數析構函數 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); / /把下標為把下標為i i的元素取至的元素取至x x int Search(const int &

12、x); int Search(const int &x); / /返回返回x x在表中的下標在表中的下標 void Insert(int i, const int &x); void Insert(int i, const int &x); / /在下標在下標i i處插入元素處插入元素x x void Delete(int i, int &x); void Delete(int i, int &x); / /返回下標為返回下標為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; ;/ /構造函數：構造函數：/ /建立一個空表建立一個空表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()函數：函數：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()函數：函數：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()函數：函數：voidvoid SeqList:Insert(int i, const int &x)SeqList:Insert

16、(int i, const int &x) if(ilength) if(ilength) cout cout下標越界下標越界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()函數：函數：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下標越界下標越界n;n; /Output()/Output()函數：函數：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; / /重載為成員函數行不行？重載為成員函數行不行？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 ; 會有什么問題么？會有什么問題么？調用時：調用時：l 不能寫成：不能寫成：coutx;coutx;l 只能寫成：只能寫成：xcout;xcout;線性表的鏈接存儲結構（鏈表）l 單鏈表中的結點：l 單鏈表：datanextl 帶頭結點的單鏈表：在一般形式的單鏈表中進行插入、刪除操作時，必須針對不同的情況采取不同的處理方法，這為編寫程序帶來一定的難度和潛在的危險。在帶頭結點的單鏈表中進行插入、刪除操作時，無須考慮特殊情況。l 空表 2121結點類的定義2222#include #include #incl

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

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; / /析構函數：析構函數：Chain:Chain()Chain:Chain() ClearList();ClearList();delete head;delete head; /Find()/Find()函數：函數：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()函數：函數：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下標越界下標越界n;n; Node Node * *p=head;p=head;int k=0;int k=0;/ /找到第找到第i-1i-1個結點個結點while(knext; k+; while(knext; k+; / /生成新結點生成新結點

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下標越界下標越界n;n;/ /找到第找到第i-1i-1個結點個結點 Node Node * *p=head;p=head;for(int k=0;knext;for(int k

28、=0;knext;/ /找到要刪除的結點找到要刪除的結點Node Node * *q=p-next; q=p-next; x=q-data; x=q-data; / /保存刪除結點的值保存刪除結點的值p-next=q-next;p-next=q-next;/ /改變第改變第i-1i-1個結點指針域個結點指針域delete q; delete q; / /刪除結點刪除結點length-;length-; /ClearList()/ClearList()函數清空表函數清空表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()函數：函數：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 設置尾指針的單循環(huán)鏈表l 雙鏈表l 雙循環(huán)鏈表24249.3棧（Stack）l 棧的定義：只能在一端進行插入和刪除運算的線性表。l 棧的特點：后進先出原則（Last In First Out，LIFO） 。l 術語：棧頂棧底入棧出棧2525棧的基本運算l 入棧、出棧、判?？?、取棧頂元素、置?？誥bcabcacbacbbacbacbcabcacabcabcbacba 棧的入棧和出棧操作可以穿插進行，所以對應于相同的入棧序列其出棧序列可以有多種。 討論：入棧序列為abc，出棧序列有多少種可能？ cabefd和efdcab 等均為不可能出現的出棧序列。2626順序棧l 以順序方式存儲的棧稱為順序棧。l 順序?？梢杂靡痪S數組實現。l 需要一個整型變量top指示當前棧頂位置 。l 當使用兩個棧時，可讓它們共享一個一維數組空間，以達到節(jié)省存儲空間和降低上溢發(fā)生頻率的目的。28a