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

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

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

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

存儲(chǔ)結(jié)構(gòu)：計(jì)算機(jī)中隊(duì)列的存儲(chǔ)方法。

運(yùn)算：排隊(duì)過程中各種操作的實(shí)現(xiàn)方法。

數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算數(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ù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

9.1數(shù)據(jù)結(jié)構(gòu)概述每個(gè)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼，即為線性結(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)：除第一個(gè)和最后一個(gè)元素外，其他每個(gè)元素都僅有一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素。例：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)：每個(gè)元素若有直接前驅(qū)元素，只能有一個(gè)，但可以有多個(gè)直接后繼元素。4）圖形結(jié)構(gòu)：每個(gè)元素都可以有多個(gè)直接前驅(qū)元素和多個(gè)直接后繼元素。9.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)包含內(nèi)容之二：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存儲(chǔ)器中的實(shí)現(xiàn)。四種基本的存儲(chǔ)映象方式：1）順序方式2）鏈接方式3）索引方式4）散列方式繼續(xù)9.1數(shù)據(jù)結(jié)構(gòu)概述

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

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

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

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

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

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

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

4.算法的評(píng)價(jià)

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

1）算法的時(shí)間復(fù)雜度：根據(jù)算法編寫出的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間。2）算法的空間復(fù)雜度：根據(jù)算法編寫出的程序在計(jì)算機(jī)上運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小。9.1數(shù)據(jù)結(jié)構(gòu)概述算法算法時(shí)間復(fù)雜度的度量一般把程序運(yùn)行時(shí)語句的執(zhí)行次數(shù)（不包括說明語句）作為估算程序執(zhí)行時(shí)間的量度。例：估算以下函數(shù)的時(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忽略低次項(xiàng)，記為：f(n)=O(n)

它與n

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

線性表是由ｎ（ｎ≥０）個(gè)相同類型的數(shù)據(jù)元素e0、e1、…、en-1組成的有限序列。可抽象的表示為：（e0，e1，……，ei-1，ei，ei+1，……en-1）

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

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

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

應(yīng)該把存儲(chǔ)線性表的一維數(shù)組和實(shí)現(xiàn)順序表各種運(yùn)算的函數(shù)封裝在一起，即定義順序表類。討論：9.2線性表字符型順序表類定義繼續(xù)單擊超鏈接查看以下函數(shù)的實(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ù)的功能是：建立一個(gè)空表。9.2線性表boolSeqList::Find(inti,char&x){ if(i<0||i>length-1)returnfalse; x=element[i]; returntrue;}

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

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

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

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ù)的功能是：返回下標(biāo)為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)點(diǎn)：

1）存儲(chǔ)密度高；

2）可方便地訪問給定下標(biāo)的元素。（隨機(jī)存取）討論：

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

缺點(diǎn)：

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

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

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

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

。

單鏈表的一般形式：

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

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

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

空表：

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

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

單擊超鏈接查看以下函數(shù)的實(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ù)的功能是：建立一個(gè)空表。9.2線性表?

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

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

head=0;}

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

。ai-1ai①p②q

③x④⑤?

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

。刪除結(jié)點(diǎn)過程演示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為輸出流對(duì)象

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

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

優(yōu)點(diǎn)：

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

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

以鏈接方式存儲(chǔ)線性表的優(yōu)缺點(diǎn)

缺點(diǎn)：

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

2）不便于對(duì)線性表中元素進(jìn)行隨機(jī)存取。

鏈表適用于表長(zhǎng)不確定且插入和刪除操作頻繁的線性表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線性表?xiàng)５母拍睿?）1.棧的定義

3.棧的特點(diǎn)

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

入棧：向棧頂插入一個(gè)元素。

出棧：從棧頂取出一個(gè)元素。討論：

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

三個(gè)元素依次進(jìn)棧，則可能的出棧序列有：棧的概念（2）9.3棧A,B,CA,C,BB,A,CB,C,AC,B,A不可能的出棧序列：C,A,B4.棧的基本運(yùn)算：入棧、出棧、判棧空、取棧頂元素、置棧空L2:

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

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

以順序方式存儲(chǔ)的棧稱為順序棧。順序棧可以用一維數(shù)組實(shí)現(xiàn)。棧頂指示器（top）：指示當(dāng)前棧頂位置。棧容量（Maxsize）：棧中最多可以存放的元素個(gè)數(shù)。順序棧（1）9.3棧ABCDE01234…..Maxsize-1top棧底棧頂stack運(yùn)算：判棧空、判棧滿、入棧、出棧、取棧頂元素、置棧空;空棧：top=-1棧滿：top=Maxsize-1

順序棧（2）9.3棧

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

2.隊(duì)列的特點(diǎn)

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

入隊(duì)、出隊(duì)、判隊(duì)空、判隊(duì)滿、取隊(duì)頭元素、置隊(duì)空

順序隊(duì)列（1）9.4隊(duì)列

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

1.入隊(duì)、出隊(duì)和取隊(duì)頭元素：

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

循環(huán)隊(duì)列隊(duì)空時(shí)：front==rear

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

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

ABCD