數(shù)據(jù)結(jié)構(gòu)slide2020年第2章學(xué)習(xí)指導(dǎo)與習(xí)題

第2章線性表學(xué)習(xí)指導(dǎo)

1、時(shí)間

2020年3月24日周二(1-4班3-4節(jié),5-10班、數(shù)學(xué)、大數(shù)據(jù)專業(yè)5-6節(jié))

2020年3月26日周四(1-4班3-4節(jié)，5-10班、數(shù)學(xué)、大數(shù)據(jù)專業(yè)5-6節(jié))

2020年3月31日周二(1-4班34節(jié),5-10班、數(shù)學(xué)、大數(shù)據(jù)專業(yè)5-6節(jié))

2020年4月02日周四(1-4班3-4節(jié),5-10班、數(shù)學(xué)、大數(shù)據(jù)專業(yè)5-6節(jié))

4次課共8學(xué)時(shí)。

2、內(nèi)容

課前觀看視頻課件；

騰訊課堂/騰訊會(huì)議講解本章重點(diǎn)和難點(diǎn)；

QQ群交流，中間根據(jù)需要采用QQ視頻或騰訊視頻講解);

投票方式答題(點(diǎn)名、檢查上課人數(shù))；

問答。

具體安排:

(1)線性表的邏輯結(jié)構(gòu)特性和抽象數(shù)據(jù)類型(ADT)的設(shè)計(jì)；

3月24日(2)線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；

線上(3)順序存儲(chǔ)實(shí)現(xiàn)中的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算

法。

(4)鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)中單鏈表的創(chuàng)建、查找、插入和刪除等基本操作及

相關(guān)算法；

3月26日

(5)雙向鏈表的插入和刪除等基本操作及相關(guān)算法；

線上

(6)循環(huán)鏈表的特點(diǎn)及創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算

法。

(7)棧與隊(duì)列的定義、特點(diǎn)和性質(zhì)；

3月31日

(8)棧與隊(duì)列的設(shè)計(jì)、實(shí)現(xiàn)以及基本操作和相關(guān)算法；

線上

(9)棧和隊(duì)列在表達(dá)式求值、括號(hào)匹配、數(shù)制轉(zhuǎn)換問題中的應(yīng)用。

(10)串的定義、性質(zhì)和特點(diǎn)；

(11)串的設(shè)計(jì)、實(shí)現(xiàn)方法和基本操作；

(12)串的簡(jiǎn)單模式匹配算法及KMP算法等。

(13)數(shù)組的存儲(chǔ)表示方法；

4月2日

(14)數(shù)組在存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；

(H308?)

(15)特殊矩陣的壓縮存儲(chǔ)方法；

(16)稀疏矩陣的兩種壓縮存儲(chǔ)方法；

(17)以三元組表示稀疏矩陣時(shí)矩陣運(yùn)算所采用的算法及實(shí)現(xiàn)；

(18)廣義表的定義、特點(diǎn)和性質(zhì)。

3、本章知識(shí)要點(diǎn)

數(shù)據(jù)對(duì)象中除第一個(gè)無素雙外的依何一小完素?唯一的嘴驅(qū)，除果后一個(gè)無

去血，卜的a一個(gè)無米彳嘛一的后健完去。

3.1線性表邏輯結(jié)構(gòu)

線性表是n(n>=0)個(gè)數(shù)據(jù)元素的有限序列，同一線性表中的數(shù)據(jù)元素必定具

有相同特性，即屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶<a,,a,">關(guān)系。n

定義為線性表的長(zhǎng)度；n為0表示該線性表為空表。常把線性表表示為：

(a/,a2,a；,???,a,",a：,a,+/,,a”)

簡(jiǎn)言之，在線性表中，除第一個(gè)元素?zé)o前驅(qū)、最后一個(gè)元素?zé)o后繼之外，其

他任何一個(gè)元素都有唯一的直接前驅(qū)元素和唯一的一個(gè)直接后繼元素。

序偶出/+/>/=1….n-1,稱a,?為出+/的直接前驅(qū)，a,+/為a,的直接后繼。

序：指元素之間的“位序”，而非元素值的升序、降序，或其他順序。

3.2、線性表的ADT操作及實(shí)現(xiàn)

數(shù)學(xué)模型：

線性表LIST=(D,R)

D={a(-1a,6Elementset,z=1,2,n,n>0}

R={H}

H={a,>|a,./,a,eD,i=2,…，n}

操作：

1)Initlist(L)

2)Listlength(L)

3)GetNode(L,i)

4)LocateNode(L,x)

5)InsertList(L,x,i)

6)Delete(L,i)

注意與教材的區(qū)別：

1)ListInsert(L,p,e)；

2)LocateElem(L,e,Compare())；

3)GetElem(L,p,&e)；

4)ListDelete(&L,p,&e)；

5)PriorElem(L,cur_e,&pre.e)

6)NextElem(L,cur_e,&next_e)；

7)ClearList(&L)；

8)ListrFirst(L)；

9)ListEnd(L)；,…

3.3線性表存儲(chǔ)結(jié)構(gòu)

(D順序存儲(chǔ)

線性表中任一數(shù)據(jù)元素的存儲(chǔ)位置為：LOC(a,)=LOC(a/)+(z")*L

一維數(shù)組實(shí)現(xiàn)線性表，也就是采用一位數(shù)組作為線性表的存儲(chǔ)結(jié)構(gòu)，利用一

維素組元素的地址連續(xù)來表示線性表元素的位序，這是一種靜態(tài)存儲(chǔ)結(jié)構(gòu)。

例如：ElementTypeA[Max];

思考：intA[Max],*pa;

前提：pa=A;或pa=&A[0];

請(qǐng)問：A、pa、A[i]、*(pa+i)、pa[i]、*(A+i)之間的關(guān)系？i=l...Max-1

操作：

■插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為〃Z2;平均時(shí)間復(fù)雜度均為0(〃)。

■刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為(〃-/)/2；平均時(shí)間復(fù)雜度均為0(〃)。

(2)鏈?zhǔn)酱鎯?chǔ)

線性鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，所占用的存儲(chǔ)空間是在程序的執(zhí)行過程中得

到的，當(dāng)線性鏈表要增加一個(gè)結(jié)點(diǎn)時(shí)，向系統(tǒng)申請(qǐng)一個(gè)存儲(chǔ)空間，刪除結(jié)點(diǎn)時(shí)要

將空間釋放。

由線性鏈表的結(jié)點(diǎn)定義，每個(gè)結(jié)點(diǎn)中均只含有一個(gè)指針域，用于指向其后繼

結(jié)點(diǎn)，故也稱單鏈表。

循環(huán)鏈表是線性表的另一種形式的鏈?zhǔn)酱鎯?chǔ)表示。它的特點(diǎn)是表中最后一個(gè)

結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)，并且可將頭

指針設(shè)成指向最后一個(gè)結(jié)點(diǎn)(尾指針)?？盏难h(huán)鏈表由只含一個(gè)自成循環(huán)的頭

結(jié)點(diǎn)表示。

若每個(gè)結(jié)點(diǎn)中均含有兩個(gè)指針域，一個(gè)用于指向其后繼結(jié)點(diǎn)，另一個(gè)用于指

向其前驅(qū)結(jié)點(diǎn)，則稱其為雙向鏈表。

若雙向鏈表中的兩個(gè)鏈均構(gòu)成回路，則稱為雙向循環(huán)鏈表。

重點(diǎn)理解：線性鏈表頭結(jié)點(diǎn)的作用。

操作：

■插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為?；平均時(shí)間復(fù)雜度均為0(?)。

■刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為?；平均時(shí)間復(fù)雜度均為0(?)。

(3)線性鏈表靜態(tài)存儲(chǔ)結(jié)構(gòu)與動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)的比較

(4)風(fēng)別針對(duì)每一種存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)每一個(gè)操作

3.4棧和隊(duì)列

棧是限定只能在表的一端(表尾)進(jìn)行插入和刪除操作的線性表；允許插入

和刪除的一端，稱為棧頂“印)；另一端則稱為棧底(兒例加)；棧又叫做后進(jìn)先出

(LIF0)的線性表。

為了指示當(dāng)前的棧頂元素，需設(shè)一個(gè)指針/op指示當(dāng)前棧頂?shù)奈恢?，稱為棧

頂指針。

隊(duì)列也是受限的線性表。限定只能在隊(duì)列的一端插入元素，另一端刪除元素。

插入元素的一端是隊(duì)尾他〃)，刪除元素的一端是隊(duì)頭價(jià)。M。隊(duì)列具有先進(jìn)先出

的特點(diǎn)，因此稱為先進(jìn)先出(FIFO)線性表。

重點(diǎn)：(1)棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)；

(2)棧和隊(duì)列的ADT操作；

(3)棧和隊(duì)列的應(yīng)用。

3.5串

串是由〃(心=0)個(gè)任意字符組成的有限序列。當(dāng)〃為零時(shí)，稱為空串。由一

個(gè)或多個(gè)空格符組成的串稱為空格串。

子串：串中任意連續(xù)的字符組成的子序列稱為該串的子串。

主串：包含子串的串。

子串的位置：子串的第一個(gè)字符在主串中的序號(hào)稱為子串的位置。

兩個(gè)串相等：當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置上的字符都相同。

重點(diǎn)：(1)串的存儲(chǔ)結(jié)構(gòu)及比較；

(2)串的操作；

(3)模式匹配算法(KMP)。

3.6數(shù)組與廣義表

但何敏粗鄢是一個(gè)地址速催的一蓿向菱。一瓶檄粒是；二維孤俶也是，所系

同的是二處熟糧的為一個(gè)無素又是一個(gè)一僮救修；……

數(shù)組是連續(xù)的、有限的、有序的、同構(gòu)的數(shù)據(jù)元素的集合；

L0C(a,)=L0C(a/)+(i-7)*L(一維數(shù)組)

LOC(a,7)=LOC(a//)+[(z-7)*N+/-/]*L(行序?yàn)橹鞯拇鎯?chǔ)方式)

特殊矩陣：三角矩陣、對(duì)稱矩陣或?qū)蔷仃?，值相同或零元素的分布在矩?/p>

中有一定的規(guī)律。

稀疏矩陣：非零元素個(gè)數(shù)遠(yuǎn)小于矩陣(零)元素個(gè)數(shù)。

壓縮存儲(chǔ)：為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間以節(jié)省存儲(chǔ)空間；對(duì)零元

不分配空間。

重點(diǎn)：矩陣壓縮存儲(chǔ)后的轉(zhuǎn)置運(yùn)算的兩種實(shí)現(xiàn)方法及其時(shí)間復(fù)雜度的比較。

廣義表：LS=(a/,a2,...,a“)LS為廣義表的名稱，〃為廣義表的長(zhǎng)度，a,可以是

單個(gè)元素，也可以是廣義表，稱為JS的原子和子表。當(dāng)廣義表非空時(shí)，稱第一

個(gè)元素a/為表頭(Head),稱其余元素組成的表⑸用,…,4,)為表尾(Tail)。

要求理解廣義表的定義，能讀懂廣義表的存儲(chǔ)結(jié)構(gòu)。

3.7本章小結(jié)

1)知識(shí)點(diǎn)

其

象

抽

基W

據(jù)

他

數(shù)

序

本

存

型

類

概

存

儲(chǔ)

義

定

念?

⑴域性及定義(DADT定義⑴肱序表的特點(diǎn)⑴單銃表的特點(diǎn)⑴裾環(huán)鞋

⑵邏輯特征⑵基本掾作⑵順序表類定義⑵單愜表類定義⑺雙fit我

⑶基本操作的實(shí)⑶基本操作的實(shí)⑶靜態(tài)鏈衰

現(xiàn)及時(shí)間性能現(xiàn)及時(shí)間性能

2)小結(jié)

?線

跨殊隙性表

a

?

取

按

口加憧義序

再

存

存

OJAOT懂UJAiHa

tt

JLI

4、習(xí)題

（1）單項(xiàng)選擇題

1）一個(gè)向量（即一批地址連續(xù)的存儲(chǔ)單元）第一個(gè)元素的存儲(chǔ)地址是100,

每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是（）。

A.110B.108C.100D.120

2）線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種

（）的存儲(chǔ)結(jié)構(gòu)。

A.隨機(jī)存取B.索引存取C.順序存取D.散列存取

3）線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說法（）。

A,正確B.不正確

4）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。

A.必須是連續(xù)的B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以

5）在以下的敘述中，正確的是（）o

A.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)

B.線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

C.線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

D.線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)

6）每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找，這種說法（）0

A.正確B.不正確

7）不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）0

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

8）帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）o

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

9）非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足（）。

A.p->next==NULLB.p==NULL

C.p->next==headD.p==head

10）在雙向循環(huán)鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是（）0

A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;

D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;

11）在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p

之間插入s結(jié)點(diǎn)，則執(zhí)行（）。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

B.q->next=s;s->next=p;C.p->next=s;s->next=q;

12）在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)

點(diǎn)，則執(zhí)行（）。

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;C.p->next=s;s->next=p;

13）在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（）。

A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；

C.p->next=p->next;D.p=p->next->next；

14）從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情

況下，需平均比較（）個(gè)結(jié)點(diǎn)。

A.nB.n/2C.（n-l）/2D.（n+l）/2

15）在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)

雜度是（）。

2

A.0（1）B.0（n）C.0（n）D.0（nlog2n）

16）給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是（）。

2

A.0（1））B.0（n）C.O（n）D.O（n*log2n）

（2）填空題（將正確的答案填在相應(yīng)的空中）

1）單鏈表可以做的鏈接存儲(chǔ)表示。

2）在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，另一個(gè)指向

3）在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s（值為e）所指結(jié)點(diǎn)時(shí)，可執(zhí)行如

下操作：

q=head;

while（q->next!=p）q=q->next;

s=newNode;s->data=e;

q->next=;〃填空

s->next=;〃填空

4）在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：

q=p->next;

p->next=;//填空

delete_______;〃填空

5）在一個(gè)單鏈袤而所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行

s->next=和p->next=的操作。

6）對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的

時(shí)間復(fù)雜度是;在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的