C++課件第9章線性結(jié)構(gòu)(guo20120509)

第九章線性結(jié)構(gòu)本章內(nèi)容1.數(shù)據(jù)結(jié)構(gòu)概述2.線性表3.棧4.隊列5.數(shù)組9.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)：計算機能夠識別、存儲和處理的符號的集合

。數(shù)據(jù)對象：具有相同性質(zhì)的數(shù)據(jù)元素集合。

數(shù)據(jù)元素：數(shù)據(jù)的基本單位，由一個或多個數(shù)據(jù)項組成。又稱為結(jié)點、頂點、記錄、表目等。數(shù)據(jù)項：具有獨立含義的數(shù)據(jù)的最小單位，又稱為域、字段。9.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)對象中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系概念和術(shù)語例：職工情況表職工情況表是一種數(shù)據(jù)結(jié)構(gòu)，每個職工情況為一數(shù)據(jù)元素，職工的每項基本信息為一個數(shù)據(jù)項，部門的所有職工構(gòu)成一個數(shù)據(jù)對象。9.1數(shù)據(jù)結(jié)構(gòu)概述9.1數(shù)據(jù)結(jié)構(gòu)概述9.1數(shù)據(jù)結(jié)構(gòu)概述例：排隊問題Customer(λ)Queue(B-1)Server(μ)

邏輯結(jié)構(gòu)：排隊方式，數(shù)據(jù)間的邏輯關(guān)系。

存儲結(jié)構(gòu)：計算機中隊列的存儲方法。

運算：排隊過程中各種操作的實現(xiàn)方法。

數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運算數(shù)據(jù)結(jié)構(gòu)包含內(nèi)容之一：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)：例：職工情況表表尾元素表頭元素中間元素

數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映出數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。

9.1數(shù)據(jù)結(jié)構(gòu)概述每個元素最多有一個直接前驅(qū)和一個直接后繼，即為線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包含內(nèi)容之一：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)的分類：1）集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是“屬于同一集合”，集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。例：2）線性結(jié)構(gòu)：除第一個和最后一個元素外，其他每個元素都僅有一個直接前驅(qū)元素和一個直接后繼元素。例：9.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)包含內(nèi)容之一：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)的分類：例：例：3）樹形結(jié)構(gòu)：每個元素若有直接前驅(qū)元素，只能有一個，但可以有多個直接后繼元素。4）圖形結(jié)構(gòu)：每個元素都可以有多個直接前驅(qū)元素和多個直接后繼元素。9.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)包含內(nèi)容之二：數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機內(nèi)存儲器中的實現(xiàn)。四種基本的存儲映象方式：1）順序方式2）鏈接方式3）索引方式4）散列方式繼續(xù)9.1數(shù)據(jù)結(jié)構(gòu)概述

將數(shù)據(jù)元素按照某種順序存放到一片連續(xù)的存儲單元內(nèi)，數(shù)據(jù)元素之間的邏輯關(guān)系是通過它們在存儲器中的相對位置來體現(xiàn)的。例：英語字母表的順序存儲。ABC……XYZ9.1數(shù)據(jù)結(jié)構(gòu)概述順序方式

邏輯上相鄰的元素在物理位置上未必相鄰，元素間的邏輯關(guān)系由附加的指針域表示。第一個職工情況第二個職工情況最后一個職工情況…h(huán)ead∧例：職工情況鏈表（鏈接方式存儲的線性結(jié)構(gòu)）9.1數(shù)據(jù)結(jié)構(gòu)概述鏈接方式索引表數(shù)據(jù)9.1數(shù)據(jù)結(jié)構(gòu)概述關(guān)鍵字地址索引方式關(guān)鍵字：是指能夠惟一標識一個數(shù)據(jù)元素的一個或多個數(shù)據(jù)項。

數(shù)據(jù)元素的存儲位置是用它的關(guān)鍵字計算出來的。散列方式存儲的數(shù)據(jù)結(jié)構(gòu)又稱為哈希表、雜湊表等。

9.1數(shù)據(jù)結(jié)構(gòu)概述散列方式數(shù)據(jù)結(jié)構(gòu)包含內(nèi)容之三：數(shù)據(jù)的運算數(shù)據(jù)的運算：對數(shù)據(jù)對象中的數(shù)據(jù)所進行的加工和處理。數(shù)據(jù)運算的特點：

數(shù)據(jù)的運算定義在邏輯結(jié)構(gòu)之上，實現(xiàn)在存儲結(jié)構(gòu)之上。數(shù)據(jù)運算的實現(xiàn)用算法描述。常用的數(shù)據(jù)運算：插入、刪除、查找、排序、更新等。9.1數(shù)據(jù)結(jié)構(gòu)概述算法1.什么是算法

算法是對解決問題方法的精確描述，是用來完成某個特定任務(wù)的有限步驟序列。

9.1數(shù)據(jù)結(jié)構(gòu)概述例如:用輾轉(zhuǎn)相除法求兩個正整數(shù)M和N的最大公因數(shù)的算法為:step1:求M除以N的余數(shù)R;step2:若R=0,算法結(jié)束,即N為M和N的最大公因數(shù)Step3:否則,置M←N,N←R,返回step12.算法的基本特征有窮性一個算法必須在執(zhí)行有窮步后結(jié)束，并且每一步都能在有限的時間內(nèi)完成。確定性算法中的每一條指令必須具有確切的含義，且無二義性。可行性算法中描述的所有操作都可以通過讓已實現(xiàn)的基本運算執(zhí)行有限次完成。輸入一個算法應(yīng)該有０個或多個輸入。輸出一個算法應(yīng)該有一個或多個輸出。算法算法3.算法的描述

4.算法的評價

自然語言描述、程序設(shè)計語言描述、流程圖描述等。以下采用C++語言作為描述算法的工具

1）算法的時間復(fù)雜度：根據(jù)算法編寫出的程序在計算機上運行時所消耗的時間。2）算法的空間復(fù)雜度：根據(jù)算法編寫出的程序在計算機上運行時所需要的存儲空間的大小。9.1數(shù)據(jù)結(jié)構(gòu)概述算法算法時間復(fù)雜度的度量一般把程序運行時語句的執(zhí)行次數(shù)（不包括說明語句）作為估算程序執(zhí)行時間的量度。例：估算以下函數(shù)的時間復(fù)雜度。intmin(inta[],intn){intk,i;

k=0; //執(zhí)行1次

for(i=1;i<n;i++) //執(zhí)行n次

if(a[i]<a[k])k=i; //執(zhí)行n-1次

returnk;//執(zhí)行1次

}語句執(zhí)行頻度：f(n)=2n+1忽略低次項，記為：f(n)=O(n)

它與n

成正比算法常見的算法時間復(fù)雜度O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、O(n3)、O(2n)時間函數(shù)的增長率9.1數(shù)據(jù)結(jié)構(gòu)概述線性表

線性表是由ｎ（ｎ≥０）個相同類型的數(shù)據(jù)元素e0、e1、…、en-1組成的有限序列?？沙橄蟮谋硎緸椋海╡0，e1，……，ei-1，ei，ei+1，……en-1）

開始元素中間元素終端元素建空表、求表長、查找、插入、刪除、排序等。9.2線性表1.線性表的定義

線性表中元素的個數(shù)稱為表的長度。長度為0的表為空表。元素在表中的序號稱做元素的下標。2.線性表常用的基本運算線性表的順序存儲結(jié)構(gòu)（順序表）以順序方式存儲的線性表稱為順序表。可以用一維數(shù)組實現(xiàn)順序表。例：用C++的一維數(shù)組實現(xiàn)對英文字母表的順序存儲。

chartable[26];或：char*table=newchar[26];

應(yīng)該把存儲線性表的一維數(shù)組和實現(xiàn)順序表各種運算的函數(shù)封裝在一起，即定義順序表類。討論：9.2線性表字符型順序表類定義繼續(xù)單擊超鏈接查看以下函數(shù)的實現(xiàn)：構(gòu)造函數(shù)

Find()

Search()Insert()

Delete()

output()

重載“<<”的函數(shù)9.2線性表順序表類的構(gòu)造函數(shù)SeqList::SeqList(intm){element=newchar[m];Maxsize=m;length=0;}

函數(shù)的功能是：建立一個空表。9.2線性表boolSeqList::Find(inti,char&x){ if(i<0||i>length-1)returnfalse; x=element[i]; returntrue;}

順序表類的Find()函數(shù)函數(shù)的功能是：把下標為i的元素取至x。9.2線性表順序表類的Search()函數(shù)函數(shù)的功能是：返回x在表中的下標。intSeqList::Search(constchar&x){for(inti=0;i<length;i++) if(element[i]==x)returni;return-1;}

9.2線性表順序表類的Insert()函數(shù)函數(shù)的功能是：在下標i處插入元素x

。boolSeqList::Insert(inti,constchar&x){if(i<0||i>length)returnfalse;//下標越界

if(length==Maxsize)returnfalse;//表已滿

for(intk=length-1;k>=i;k--)element[k+1]=element[k];element[i]=x;length++;returntrue;

}9.2線性表順序表類的Delete()函數(shù)函數(shù)的功能是：返回下標為i的元素至x，并刪除之

。boolSeqList::Delete(inti,char&x){if(Find(i,x)){ for(intk=i;k<length-1;k++)element[k]=element[k+1]; length--; returntrue; }elsereturnfalse; }9.2線性表順序表類的output()函數(shù)函數(shù)的功能是：輸出表中所有元素的值

。voidSeqList::output(ostream&out)const{ for(inti=0;i<length;i++) out<<element[i]<<"";}9.2線性表順序表類的友元函數(shù)函數(shù)的功能是：為方便輸出，重載“<<”

。ostream&operator<<(ostream&out,constSeqList&x){ x.output(out); returnout; }

9.2線性表

優(yōu)點：

1）存儲密度高；

2）可方便地訪問給定下標的元素。（隨機存?。┯懻摚?/p>

順序表的優(yōu)缺點

缺點：

1）插入和刪除運算的實現(xiàn)效率低。

2）表的容量需預(yù)先指定，適應(yīng)性差。

順序表適用于表長已知且插入和刪除操作不頻繁的線性表9.2線性表例：將一串字符存入順序表，刪除其中所有的數(shù)字字符。程序的輸出結(jié)果是：

1C++2FORTRAN3PASCAL4BASICC++FORTRANPASCALBASIC9.2線性表線性表的鏈接存儲結(jié)構(gòu)（鏈表）以鏈接方式存儲的線性表稱為鏈表。常用的鏈表形式有單鏈表、雙鏈表和循環(huán)鏈表等

。

單鏈表的一般形式：

單鏈表中結(jié)點的一般形式：

datanext注意：在一般形式的單鏈表中進行插入、刪除操作時，必須針對不同的情況采取不同的處理方法，這為編寫程序帶來一定的難度和潛在的危險。

空表：head=NULL9.2線性表帶頭結(jié)點的單鏈表9.2線性表

空表：

帶頭結(jié)點的單鏈表的一般形式：

單鏈表的常用操作：建空表、判表空、求表長、查找表中元素、插入元素、刪除元素、清空表、輸出表中元素等字符型單鏈表類的定義繼續(xù)

單擊超鏈接查看以下函數(shù)的實現(xiàn)：構(gòu)造函數(shù)

析構(gòu)函數(shù)

Find()

Search()

Insert()

Delete()

ClearList()

output()

重載“<<”的函數(shù)9.2線性表字符型單鏈表類的構(gòu)造函數(shù)Chain::Chain(){ head=newNode; head->next=0; length=0;}

函數(shù)的功能是：建立一個空表。9.2線性表?

空表：字符型單鏈表類的析構(gòu)函數(shù)Chain::~Chain(){ ClearList();//釋放數(shù)據(jù)結(jié)點空間

deletehead;//釋放頭結(jié)點空間

head=0;}

函數(shù)的功能是：釋放鏈表空間。9.2線性表字符型單鏈表類的Find()函數(shù)函數(shù)的功能是：把下標為i的元素取至x。9.2線性表字符型單鏈表類的Search()函數(shù)函數(shù)的功能是：返回x在表中的下標。9.2線性表字符型單鏈表類的Insert()函數(shù)函數(shù)的功能是：在下標i處插入元素x

。ai-1ai①p②q

③x④⑤?

插入過程演示9.2線性表a0head….字符型單鏈表類的Delete()函數(shù)函數(shù)的功能是：返回下標為i的元素至x，并刪除之

。刪除結(jié)點過程演示ai-1aiai+1①p②q③④9.2線性表a0head….字符型單鏈表類的ClearList()函數(shù)函數(shù)的功能是：把表清空，即將單鏈表置為空表

。9.2線性表字符型單鏈表類的output()函數(shù)函數(shù)的功能是：輸出表中所有元素的值

。voidChain::output(ostream&out)const{Node*p=head->next;while(p!=0){ out<<p->data<<“”;//out為輸出流對象

p=p->next;}}9.2線性表字符型單鏈表類的友元函數(shù)函數(shù)的功能是：為方便輸出，重載“<<”

。ostream&operator<<(ostream&out,constChain&x){ x.output(out); returnout;}9.2線性表

優(yōu)點：

1）插入和刪除運算的實現(xiàn)效率比較高。

2）在存儲長度變化比較大的線性表時適應(yīng)性較好。討論：

以鏈接方式存儲線性表的優(yōu)缺點

缺點：

1）需要增加額外的空間表示元素之間的邏輯關(guān)系。

2）不便于對線性表中元素進行隨機存取。

鏈表適用于表長不確定且插入和刪除操作頻繁的線性表9.2線性表例：將一字符串存入單鏈表，刪除其中所有的數(shù)字字符。程序的輸出結(jié)果是：

1C++2FORTRAN3PASCAL4BASICC++FORTRANPASCALBASIC9.2線性表練習(xí)單鏈表類的Insertx()函數(shù)函數(shù)的功能是：在表中查找有無值為x的元素，若有，則顯示“已存在”，否則，將值為x的元素插到表頭

。練習(xí)單鏈表類的Insertx()函數(shù)函數(shù)的功能是：在表中查找有無值為x的元素，若有，則顯示“已存在”，否則，將值為x的元素插到表頭

。其他形式的鏈表（1）單循環(huán)鏈表設(shè)置尾指針的單循環(huán)鏈表9.2線性表其他形式的鏈表（2）雙鏈表雙循環(huán)鏈表9.2線性表棧的概念（1）1.棧的定義

3.棧的特點

棧中元素的變化是按后進先出原則進行，因此又稱棧為后進先出（LastInFirstOut，簡稱LIFO）表。棧是限定只能在表的同一端進行插入和刪除運算的線性表。9.3棧2.棧的術(shù)語棧頂：允許進行插入和刪除的一端。棧底：與棧頂相對的一端。

入棧：向棧頂插入一個元素。

出棧：從棧頂取出一個元素。討論：

棧的入棧和出棧操作可以穿插進行，所以對應(yīng)于相同的入棧序列其出棧序列可以有多種。例：設(shè)A,B,C

三個元素依次進棧，則可能的出棧序列有：棧的概念（2）9.3棧A,B,CA,C,BB,A,CB,C,AC,B,A不可能的出棧序列：C,A,B4.棧的基本運算：入棧、出棧、判?？?、取棧頂元素、置?？誏2:

入棧序列為：12345；出棧序列為：14a5bQ:a=？、b=？練習(xí)9.3棧L1:

入棧序列為：123；棧容量為2。Q:可能的出棧序列有哪些？A:a=3,b=2A:123、132、213、231

以順序方式存儲的棧稱為順序棧。順序?？梢杂靡痪S數(shù)組實現(xiàn)。棧頂指示器（top）：指示當前棧頂位置。棧容量（Maxsize）：棧中最多可以存放的元素個數(shù)。順序棧（1）9.3棧ABCDE01234…..Maxsize-1top棧底棧頂stack運算：判?？?、判棧滿、入棧、出棧、取棧頂元素、置棧空;空棧：top=-1棧滿：top=Maxsize-1

順序棧（2）9.3棧

字符型順序棧類的定義與實現(xiàn)：9.3棧例：利用棧實現(xiàn)將一個非負的十進制整數(shù)轉(zhuǎn)換為B（2≤B≤16)進制整數(shù)。隊列的概念（1）1.隊列的定義

2.隊列的特點

隊列中元素的變化是按先進先出原則進行，因此又稱隊為先進先出（FirstInFirstOut，簡稱FIFO）表。只能在表的一端進行插入，而在另一端進行刪除的線性表。9.4隊列3.隊列的基本運算

入隊、出隊、判隊空、判隊滿、取隊頭元素、置隊空

順序隊列（1）9.4隊列

以順序方式存儲的隊稱為順序隊。順序隊可以用一維數(shù)組實現(xiàn)。隊頭指示器（front）：指示當前隊頭位置。隊尾指示器（rear）：指示將要入隊元素所在的位置。隊列操作演示假溢出：當隊中還有空間可放數(shù)據(jù)，但不能執(zhí)行入隊操作。順序循環(huán)隊列（1）9.4隊列解決假溢出問題的三種方法。1）建立一個足夠大的存儲空間。rear9.4隊列CD01234frontE2）平移元素。3）循環(huán)隊列方式。隊頭、隊尾指針循環(huán)移動。rear討論：順序循環(huán)隊列的操作

1.入隊、出隊和取隊頭元素：

循環(huán)順序隊列（2）9.4隊列入隊：elem[rear]=x;rear=（rear+1）%Maxsize;出隊：front=（front+1）%Maxsize;取隊頭元素：x=elem[front];求隊列長度：方法1：(Maxsize+rear-front)%Maxsize方法2：設(shè)一個計數(shù)變量(count),由入隊和出隊操作控制計數(shù)9.4隊列2.判隊空和判隊滿的方法

循環(huán)隊列隊空時：front==rear

循環(huán)順序隊列（3）9.4隊列

01234frontrear循環(huán)隊列隊滿時：front==rear

ABCD