數(shù)據(jù)結(jié)構(gòu)課件

第一章緒論1．1數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)（Data）是信息的載體，它能夠被計(jì)算機(jī)識別、存儲和加工處理。它是計(jì)算機(jī)程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等.一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)（DataItem）組成.數(shù)據(jù)項(xiàng)是在數(shù)據(jù)處理時不能再分割的最小單位；數(shù)據(jù)對象（DataObject）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。

數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：⑴集合結(jié)構(gòu).⑵線性結(jié)構(gòu).⑶樹型結(jié)構(gòu).⑷圖形結(jié)構(gòu).（a）集合結(jié)構(gòu)

（b）線性結(jié)構(gòu)

（c）樹型結(jié)構(gòu)

（d）圖形結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)可采用順序存儲或鏈?zhǔn)酱鎯Φ姆椒?。順序存儲方法是把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。鏈?zhǔn)酱鎯Ψ椒▽壿嬌舷噜彽脑夭灰笃湮锢砦恢孟噜?，元素間的邏輯關(guān)系通過附設(shè)的指針字段來表示，由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針類型來實(shí)現(xiàn)。抽象數(shù)據(jù)類型（AbstructDataType，簡稱ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義可以由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成，而數(shù)據(jù)結(jié)構(gòu)又包括數(shù)據(jù)元素及元素間的關(guān)系，因此抽象數(shù)據(jù)類型一般可以由元素、關(guān)系及操作三種要素來定義。1.2 算法和算法分析1.一個算法應(yīng)該具有下列特性：⑴有窮性。⑵確定性⑶可行性。⑷輸入。⑸輸出。2.時間復(fù)雜度一個程序的時間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時間。

f(n)＝Ο(g(n))例如，一個程序的實(shí)際執(zhí)行時間為T(n)＝2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。使用大Ο記號表示的算法的時間復(fù)雜度，稱為算法的漸進(jìn)時間復(fù)雜度常見的漸進(jìn)時間復(fù)雜度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)⒉空間復(fù)雜度一個程序的空間復(fù)雜度（Spacecomplexity）是指程序運(yùn)行從開始到結(jié)束所需的存儲量。第二章線性表2.1線性表的定義線性表定義如下：線性表是具有相同數(shù)據(jù)類型的n(n>=0)個數(shù)據(jù)元素的有限序列，通常記為：(a1，a2，…ai-1，ai，ai+1，…an)

其中n為表長，n＝0時稱為空表。2.2線性表的基本操作線性表上的基本操作有：⑴線性表初始化：Init_List(L)⑵求線性表的長度：Length_List(L)⑶取表元：Get_List(L,i)⑷按值查找：Locate_List(L,x)，ｘ是給定的一個數(shù)據(jù)元素。⑸插入操作：Insert_List(L,i,x)⑹刪除操作：Delete_List(L,i)2.3線性表的順序存儲及運(yùn)算實(shí)現(xiàn)2.3.1順序表線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱其為順序表。設(shè)a１的存儲地址為Loc(a１)，每個數(shù)據(jù)元素占d個存儲地址，則第i個數(shù)據(jù)元素的地址為：

Loc(ai)=Loc(a１)+(i-1)*d1<=i<=n2.3.2虛擬實(shí)現(xiàn)2.2.3特點(diǎn):(1)存儲空間必須是連續(xù)的,預(yù)分配.(2)邏輯順序與物理順序一致,用物理上的相鄰來表示邏輯上的線性關(guān)系.(3)任意相鄰元素之間無空閑空間,且相距為L.(4)已知基地址,可以計(jì)算出任意元素的存儲地址:

LOC(ai)=base+(i-1)*L2.4單鏈表2.4.1存儲方式:

用任意存儲空間單元來存放線性表的各個元素,為了能體現(xiàn)元素之間的邏輯關(guān)系(線性),在存放每個元素的同時,也存放相關(guān)元素的信息(相關(guān)元素的存儲地址),即用指針來表示元素之間的邏輯關(guān)系.2.4.2鏈表是由一個個結(jié)點(diǎn)構(gòu)成的，結(jié)點(diǎn)定義如下：

typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；定義頭指針變量：

LinkListH；2.5特點(diǎn):H160

存儲空間不一定連續(xù);邏輯關(guān)系是由指針來體現(xiàn)的;邏輯上相鄰,物理上不一定相鄰;非隨機(jī)存取(順序存取),即訪問任何一個元素的時間不同.2.5循環(huán)鏈表對于單鏈表而言，最后一個結(jié)點(diǎn)的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點(diǎn)相連，就構(gòu)成了單循環(huán)鏈表。2.6雙向鏈表存放元素的同時,存放其前驅(qū)和后繼元素的信息;

雙向鏈表結(jié)點(diǎn)的定義如下：

typedefstructdlnode{datatypedata;structdlnode*prior,*next;}DLNode,*DLinkList;priornextdata2.6.1插入結(jié)點(diǎn)：指針p所指的結(jié)點(diǎn)前插入指針s所指

的結(jié)點(diǎn)(1)s->prior=p->prior;a1a3a2ps插入前：sa1a2p插入后：a3(2)p->prior->next=s;(3)s->next=p;(4)p->prior=s;

指針操作的順序不是唯一的，但也不是任意的，操作①必須要放到操作④的前面完成，否則*p的前驅(qū)結(jié)點(diǎn)的指針就丟掉了2.6.2刪除結(jié)點(diǎn)：刪除指針p所指的結(jié)點(diǎn)p刪除前：刪除后：a1a2a3p->next->proir=p->prior釋放結(jié)點(diǎn)：free(p);p->prior->next=p->nexta1a2a3p順序表與鏈表的比較基于空間的比較存儲分配的方式順序表的存儲空間是靜態(tài)分配的鏈表的存儲空間是動態(tài)分配的存儲密度=