軟件開發(fā)技術(shù)基礎(chǔ) 第4版 課件 1.基本概念及線性數(shù)據(jù)結(jié)構(gòu)

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

——基本概念及線性數(shù)據(jù)結(jié)構(gòu)基本概念1．?dāng)?shù)據(jù)（data）

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

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

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對獨(dú)立的單位。但它還可以分割成若干個(gè)具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良2基本概念3．?dāng)?shù)據(jù)結(jié)構(gòu)

是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存貯結(jié)構(gòu)對數(shù)據(jù)所施加的運(yùn)算。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良3基本概念3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良4線性結(jié)構(gòu)——通迅錄、成績單、花名冊樹形結(jié)構(gòu)——電子字典、家譜、目錄圖狀結(jié)構(gòu)——交通線路、通信網(wǎng)絡(luò)基本概念3．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良5(1)順序存貯所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰。(2)鏈?zhǔn)酱尜A所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的。(3)索引存貯（略） (4)散列存貯（略）基本概念3．算法分析西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良61）時(shí)間復(fù)雜度一個(gè)算法中的時(shí)間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級(jí)來衡量。數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個(gè)數(shù)n稱為問題的規(guī)模，當(dāng)n不斷變化時(shí)，語句的執(zhí)行次數(shù)也會(huì)變化2）空間復(fù)雜度

與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開銷規(guī)模。線性數(shù)據(jù)結(jié)構(gòu)

線性表是由有限個(gè)同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。a1無前趨，an無后繼。線性表的存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良7線性數(shù)據(jù)結(jié)構(gòu)：順序表采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲(chǔ)位置也彼此相鄰。假定元素a1的物理地址是Loc(a1)，每個(gè)元素占d個(gè)存儲(chǔ)單元，則第i個(gè)元素的存儲(chǔ)位置為：Loc(ai)=Loc(a1)+(i-1)*d

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良8順序表主要算法判定線性表是否為空求線性表的長度在表中第i個(gè)位置插入新元素x

在表中刪除第i個(gè)元素在表中查找某個(gè)元素西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良9線性數(shù)據(jù)結(jié)構(gòu)：棧棧是限制在表的一端進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良10a1a3a2進(jìn)棧出棧top線性數(shù)據(jù)結(jié)構(gòu)：棧的主要操作創(chuàng)建空棧。進(jìn)棧(push)操作:在棧頂插入元素。出棧(pop)操作:在棧頂刪除元素。讀棧頂元素:只是讀出棧頂元素，并不改變棧內(nèi)元素。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良11線性數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列隊(duì)列是只能在表的一端進(jìn)行插入、在另一端進(jìn)行刪除操作的線性表。允許刪除元素的一端稱為隊(duì)頭，允許插入元素的一端稱為隊(duì)尾。解決隊(duì)列假溢出的辦法是將存放隊(duì)列元素的數(shù)組首尾相接，形成循環(huán)隊(duì)列。循環(huán)隊(duì)列的基本操作方式為：入隊(duì)列時(shí)先執(zhí)行rear=(rear+1)%M，再將新元素在rear指示位置加入；出隊(duì)列時(shí)先執(zhí)行front=(front+1)%M，再將下標(biāo)為front的元素取出。

西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良12線性數(shù)據(jù)結(jié)構(gòu)：循環(huán)隊(duì)列西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良13將隊(duì)空和對滿的條件加以區(qū)分:

隊(duì)空條件:

front=rear

隊(duì)滿條件:(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE

(a)循環(huán)隊(duì)列空(b)非空循環(huán)隊(duì)列(c)循環(huán)隊(duì)列滿線性數(shù)據(jù)結(jié)構(gòu)：單鏈表西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良14單鏈表用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。由于邏輯上相鄰的元素其物理位置不一定相鄰，為了建立元素間的邏輯關(guān)系，需要在線性表的每個(gè)元素中附加其后繼元素的地址信息。這種地址信息稱為指針。附加了其他元素指針的數(shù)據(jù)元素稱為結(jié)點(diǎn)。帶頭結(jié)點(diǎn)單鏈表的邏輯結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良15為了能順次訪問每個(gè)結(jié)點(diǎn)，需要保存單鏈表第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。這個(gè)地址稱為線性表的頭指針，本節(jié)用head表示。為了操作上的方便，可以在單鏈表的頭部增加一個(gè)特殊的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的類型與其他結(jié)點(diǎn)一樣，只是頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?。head

a1a2an∧帶頭結(jié)點(diǎn)的單鏈表帶頭結(jié)點(diǎn)單鏈表的邏輯結(jié)構(gòu)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良16head38數(shù)據(jù)域指針域38229486

a2

86…

…

94…

…

a3

NULL

a1

22

存儲(chǔ)地址單鏈表存儲(chǔ)結(jié)構(gòu)示意圖單鏈表中指針移動(dòng)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良17圖2單鏈表指針后移一步ai2167ai+17650ai-192579257p=p.next2167pp

圖1帶頭結(jié)點(diǎn)的空鏈表head∧∧單鏈表插入結(jié)點(diǎn)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良18(a)第1步,生成結(jié)點(diǎn)s(b)第2步，s結(jié)點(diǎn)指向結(jié)點(diǎn)ai

(c)第3步，結(jié)點(diǎn)ai-1指向s結(jié)點(diǎn)圖3

在單鏈表中插入結(jié)點(diǎn)x

pai-1

xai

sp.next=s③ai-1

ai

px

s②s.next=p.nextai-1

ai

px

s①單鏈表刪除結(jié)點(diǎn)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心趙英良19刪除第i個(gè)結(jié)點(diǎn)，需進(jìn)行如下操作：

①若第i個(gè)結(jié)點(diǎn)存在則找到第i和第i-1個(gè)結(jié)點(diǎn)的指針p和q②通過語句q.n