數(shù)據(jù)結(jié)構(gòu)和應(yīng)用概念和順序表講義

數(shù)據(jù)結(jié)構(gòu)和應(yīng)用概念和順序表講義思考問題數(shù)據(jù)結(jié)構(gòu)要研究什么問題？什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？如何描述線性表？線性表在計(jì)算機(jī)中如何存放？有幾種存儲形式？它們的特點(diǎn)是什么？如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？……2數(shù)據(jù)結(jié)構(gòu)問題的由來計(jì)算機(jī)求解問題的過程步驟：

調(diào)試程序編制程序求解結(jié)果運(yùn)行程序結(jié)果輸出用戶需求數(shù)據(jù)類型、格式、邏輯結(jié)構(gòu)數(shù)據(jù)邏輯運(yùn)算數(shù)據(jù)的物理操作分析抽象實(shí)際問題模型求解問題模型命令編程求解算法3數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)的專業(yè)技術(shù)基礎(chǔ)課。它研究的主要問題有：分析數(shù)據(jù)（計(jì)算機(jī)加工的對象）的特征選擇適當(dāng)邏輯存儲結(jié)構(gòu)和物理存儲結(jié)構(gòu)在存儲結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn)對數(shù)據(jù)的操作42.1數(shù)據(jù)結(jié)構(gòu)基本概念1．?dāng)?shù)據(jù)（data）

數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識別和處理的符號的集合。

2．?dāng)?shù)據(jù)元素（dataelement）

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨(dú)立的單位。但它還可以分割成若干個具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位5數(shù)據(jù)結(jié)構(gòu)（datastructure）

是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對數(shù)據(jù)所施加的運(yùn)算。

6數(shù)據(jù)的邏輯結(jié)構(gòu)

它是描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們在計(jì)算機(jī)中如何存放。一般用下列二元組來描述：

DS=（D，R）

其中：

D：是數(shù)據(jù)元素的有限集合；

R：是數(shù)據(jù)元素之間關(guān)系的集合。與數(shù)據(jù)在計(jì)算機(jī)中的存放的物理位置無關(guān)7舉例課題組由1名教師、1~3名研究生、1~6名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo)1~2名本科生。定義DS如下：

Group=（D，R）其中：

D={T，G1，…,Gn,S11,…Snm}1n3,1m2R={R1,R2}R1={<T,Gi>|1in,1n3}R2={<Gi,Sij>|1in,1jm,1n3,1m2}8數(shù)據(jù)的存儲結(jié)構(gòu)又稱物理結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映象),即數(shù)據(jù)在計(jì)算機(jī)中的存放。數(shù)據(jù)庫中的數(shù)據(jù)存放在計(jì)算機(jī)中的物理位置9邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)的；離開了機(jī)器，則無法進(jìn)行任何操作。任何一個算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)。10數(shù)據(jù)存儲結(jié)構(gòu)分類順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)11順序存儲結(jié)構(gòu)

把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu):d1d2

……dn數(shù)據(jù)域特點(diǎn):

連續(xù)存放;邏輯上相鄰,物理上也相鄰。結(jié)構(gòu)簡單，易實(shí)現(xiàn)。插入、刪除操作不便（需大量移動元素）。12鏈?zhǔn)酱鎯Y(jié)構(gòu)

以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實(shí)現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu):d1...d2dn

^數(shù)據(jù)域指針域特點(diǎn):非連續(xù)存放,借助指針來表示元素間的關(guān)系;插入、刪除操作簡單，只要修改指針即可；結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。13索引存儲結(jié)構(gòu)

數(shù)據(jù)按索引形式存放。存儲時分為：數(shù)據(jù)項(xiàng)和索引號；通過索引表記錄邏輯號（記錄號）和物理號（存儲序號）之間的對應(yīng)關(guān)系。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu):1221352455104327165

數(shù)據(jù)域索引順序號特點(diǎn)：非連續(xù)存放；檢索速度快；增、刪操作簡單。

序號：1234567數(shù)據(jù)項(xiàng)：索引號：14散列存儲結(jié)構(gòu)在數(shù)據(jù)元素與存儲位置之間建立一種存儲關(guān)系F，根據(jù)這種關(guān)系F，已知元素E，就可以得到它的存儲地址，即D=F（E）。哈希查找中的哈希表就是這樣一種存儲結(jié)構(gòu)。

特點(diǎn)：數(shù)據(jù)元素間無內(nèi)在聯(lián)系；存儲形式不定。15數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算是指對存放在物理結(jié)構(gòu)上的數(shù)據(jù),按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。常見操作有：輸入、檢索、插入、刪除、修改、排序等。16數(shù)據(jù)結(jié)構(gòu)分類

線性表堆棧隊(duì)列串?dāng)?shù)組樹二叉樹圖線性結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)DS17數(shù)據(jù)結(jié)構(gòu)基本類型線性結(jié)構(gòu)——

通迅錄、成績單、花名冊樹形結(jié)構(gòu)——

電子字典、家譜、目錄圖狀結(jié)構(gòu)——

交通線路、通信網(wǎng)絡(luò)18算法（algorithm）

通俗地講，算法就是一種解題的方法。更嚴(yán)格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：⑴輸入：具有0個或多個輸入的外界量（算法開始前的初始量）⑵輸出：至少有一個輸出，是算法執(zhí)行完后的結(jié)果。⑶有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。⑷確定性：每條指令的含義都必須明確，無二義性。⑸可行性：每條指令的執(zhí)行時間都是有限的。191．時間復(fù)雜度

一個算法花費(fèi)的時間與算法中語句的執(zhí)行次數(shù)成正比，哪個算法中語句執(zhí)行次數(shù)多，它花費(fèi)時間就多。

數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個數(shù)n稱為問題的規(guī)模，當(dāng)n不斷變化時，語句的執(zhí)行次數(shù)也會變化。一個算法中的時間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級來衡量。 例如：for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

d[i][j]=data[i][j]+1;算法分析O(n2)20算法的評價算法評價的標(biāo)準(zhǔn)：時間復(fù)雜度

指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時間。用“O（數(shù)量級）”來表示，稱為“階”。常見的時間復(fù)雜度有：

O（1）O（logn）O（n）O（n2

）常數(shù)階對數(shù)階線性階平方階空間復(fù)雜度

指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲空間。度量同時間復(fù)雜度。

21時間復(fù)雜度舉例（a）X：=X+1；（b）FORI：=1TOnDOX：=X+1；（c）FORI：=1TOnDOFORJ：=1TOnDOX：=X+1；O（1）O（n）O（n2

）222、空間復(fù)雜度

與時間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時所占用的內(nèi)存開銷規(guī)模。但我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。討論方法與時間復(fù)雜度類似，不再贅述。232.2

線性數(shù)據(jù)結(jié)構(gòu)

線性表是由有限個同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個直接前趨ai-1和一個直接后繼ai+1。a1無前趨，an無后繼。例如，一星期七天的英文縮寫表示：（Sun，Mon，The，wed，Thu，F(xiàn)ri，Sat）是一個線性表，其中的元素是字符串，表的長度為7。24線性表的邏輯結(jié)構(gòu)定義：

線性表是n（n0）個元素a1,a2,…,an

的有限序列；表中每個數(shù)據(jù)元素，除了第1個和最后1個外，有且僅有一個前趨元素和后繼元素。形式定義：含有n個數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表示為：Linear_list=(D,R)

其中:D={ai|aiD0,i=1,2,3,…,n,n0}R={N},N={<ai-1,ai>|ai-1,aiD0,i=1,…,n}D是數(shù)據(jù)元素的有限集合，R是D上邏輯關(guān)系的有限集合。關(guān)系N是一個有序偶對的集合。25順序表

采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲位置也彼此相鄰。

假定元素a1的物理地址是Loc(a1)，每個元素占d個存儲單元，則第i個元素的存儲位置為：Loc(ai)=Loc(a1)+(i-1)*d

length=nmaxsize01i-2i-1in-1a2…ai-1aiai+1a1…an26線性表元素存儲示意圖

a1a2….ai….元素序號內(nèi)存狀態(tài)存儲地址12….

i….LOC(a1)LOC(a1)+1….LOC(a1)+(i-1)….27順序表類型描述structSeqList{ ElemType*data; //順序表存儲數(shù)組的地址

intmaxsize; //順序表最大允許長度

intlength; //順序表當(dāng)前長度

}；

SeqListlist; //定義一個線性表list

（1）ElemType代表數(shù)組的類型。（2）數(shù)組data需要在初始化函數(shù)中利用new操作動態(tài)申請，maxsize為其長度。數(shù)組的下標(biāo)從0開始。（3）length表示線性表當(dāng)前長度，初始長度為0（空表），最大不超過maxsize。28線性表的基本操作Setnull（L）置空表Length（L）求表長度；求表中元素個數(shù)Get（L，i）取表中第i個元素（1in）Prior（L，i）取i的前趨元素Next（L，i）取i的后繼元素Locate（L，x）返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）刪除元素Empty（L）判別表是否為空29順序表的主要算法（1）順序表的初始化

順序表的初始化主要是為ElemType類型的數(shù)組申請空間，下面的初始化函數(shù)為順序表申請了長度為size的空間。

voidInit(SeqList*L,intsize) { if(size>0) { L->maxsize=size; L->length=0; L->data=newElemType[size];//申請空間

} elsecout<<"線性表初始化長度錯誤"; }30（2）在表中第i個位置插入新元素x

算法實(shí)現(xiàn)的主要步驟：①判斷插入位置的合理性以及表是否已滿。②從最后一個元素開始依次向前，將每個元素向后移動一個位置，直到第i個元素為止。③向空出的第i個位置存入新元素x。④最后還要將線性表長度加一。示例31

0

1

2

i-2

i-1

i

n

maxsize

a1

a2

a3

ai-1

x

ai

an-1

an

0

1

2

i-2

i-1

i

…

n-1

maxsize

a1

a2

a3

ai-1

ai

ai+1

an

序號

內(nèi)容

序號

內(nèi)容

插入前

插入后順序表中插入元素前后狀態(tài)

……………………………32插入算法示意舉例

設(shè)有數(shù)列{4,5,8,10,21,30,43,59}，長度為8，在“21”和“30”之間插入元素“25”。算法描述：從數(shù)列右邊開始，即從第8個元素開始；為在第5個元素“21”后插入“25”，則要把其后的3個元素右移，移動元素個數(shù)是3（8-5）；

for(intj=L->length-1;j>=i-1;j--)//length是元素個數(shù)(8)

L->data[j+1]=L->data[j];

//j是插入位置(5)

將空出的第6個位置，存放“25”。

L->data[i-1]=x;//將x存放在第i-1位置表長度加“1”

L->length++;//加“1”后，結(jié)果為“9”最后，得到的結(jié)果數(shù)列是{4,5,8,10,21,25,30,43,59}

33voidInsert(SeqList*L,inti,ElemTypex){if(i<1||i>L->length+1||L->length==L->maxsize)cout<<"插入位置錯誤或表滿"; else{ for(intj=L->length-1;j>=i-1;j--)L->data[j+1]=L->data[j];//元素依次右移

L->data[i-1]=x; //向第i個位置存入新元素x L->length++;//表長度加一

}}順序表插入算法34（3）在表中刪除第i個元素

算法實(shí)現(xiàn)的主要步驟是： ①判斷刪除位置的合理性。

②從第i+1個元素開始，依次向后直到最后一個元素為止，將每個元素向前移動一個位置。這時第i個元素已經(jīng)被覆蓋刪除。 ③最后還要將線性表長度減一。35

0

1

2

i-2

i-1

i

n-1

maxsize

a1

a2

a3

ai-1

ai+1

an

0

1

2

…

i-2

i-1

i

…

n-1

maxsize

a1

a2

a3

ai-1

ai

ai+1

…

an

序號

內(nèi)容

序號

內(nèi)容

刪除前

刪除后

順序表中刪除元素前后狀態(tài)

………………………36刪除算法示意舉例設(shè)有數(shù)列{4,5,8,10,21,25,30,43,59}，長度為9，將第6位的元素“25”刪除。算法描述：從第7個元素開始(i+1)；將第7個元素“30”存入第6位，將“25”覆蓋，即元素左移，移動元素個數(shù)是3（9-6）；

for(intj=i;j<=L->length-1;j++)//length是元素個數(shù)(9)

L->data[j-1]=L->data[j];//i是刪除位置(6)長度減“1”

L->length--；//操作后，length等于8最后，得到的結(jié)果數(shù)列是{4,5,8,10,21,30,43,59}

37voidDelete(SeqList*L,inti){if(i<1||i>L->length) cout<<"表中沒有第"<<i<<"個元素";else{ for(intj=i;j<=L->length-1;j++)L->data[j-1]=L->data[j];//數(shù)據(jù)元素左移

L->length--; } }順序表刪除算法38（4）在表中查找某個元素

下面是根據(jù)數(shù)據(jù)元素本身的值進(jìn)行查詢的算法，x為需要查找的元素，算法返回元素的實(shí)際位置。查找算法: intFind(SeqList*L,ElemTypex) { for(inti=0;i<L->length;i++) {//查找成功,返回元素位置

if(L->data[