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

第2章線性表學習指導

1、時間

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

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

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

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

4次課共8學時。

2、內(nèi)容

課前觀看視頻課件；

騰訊課堂/騰訊會議講解本章重點和難點；

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

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

問答。

具體安排:

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

3月24日(2)線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)；

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

法。

(4)鏈式存儲實現(xiàn)中單鏈表的創(chuàng)建、查找、插入和刪除等基本操作及

相關(guān)算法；

3月26日

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

線上

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

法。

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

3月31日

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

線上

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

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

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

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

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

4月2日

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

(H308?)

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

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

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

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

3、本章知識要點

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

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

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

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

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

定義為線性表的長度；n為0表示該線性表為空表。常把線性表表示為：

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

簡言之，在線性表中，除第一個元素無前驅(qū)、最后一個元素無后繼之外，其

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

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

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

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

數(shù)學模型：

線性表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線性表存儲結(jié)構(gòu)

(D順序存儲

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

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

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

例如：ElementTypeA[Max];

思考：intA[Max],*pa;

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

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

操作：

■插入：平均移動結(jié)點次數(shù)為〃Z2;平均時間復雜度均為0(〃)。

■刪除：平均移動結(jié)點次數(shù)為(〃-/)/2；平均時間復雜度均為0(〃)。

(2)鏈式存儲

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

到的，當線性鏈表要增加一個結(jié)點時，向系統(tǒng)申請一個存儲空間，刪除結(jié)點時要

將空間釋放。

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

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

循環(huán)鏈表是線性表的另一種形式的鏈式存儲表示。它的特點是表中最后一個

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

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

結(jié)點表示。

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

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

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

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

操作：

■插入：平均移動結(jié)點次數(shù)為?；平均時間復雜度均為0(?)。

■刪除：平均移動結(jié)點次數(shù)為?；平均時間復雜度均為0(?)。

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

(4)風別針對每一種存儲結(jié)構(gòu)，實現(xiàn)每一個操作

3.4棧和隊列

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

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

(LIF0)的線性表。

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

頂指針。

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

插入元素的一端是隊尾他〃)，刪除元素的一端是隊頭價。M。隊列具有先進先出

的特點，因此稱為先進先出(FIFO)線性表。

重點：(1)棧和隊列的存儲結(jié)構(gòu)；

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

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

3.5串

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

個或多個空格符組成的串稱為空格串。

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

主串：包含子串的串。

子串的位置：子串的第一個字符在主串中的序號稱為子串的位置。

兩個串相等：當且僅當兩個串的長度相等且對應(yīng)位置上的字符都相同。

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

(2)串的操作；

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

3.6數(shù)組與廣義表

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

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

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

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

LOC(a,7)=LOC(a//)+[(z-7)*N+/-/]*L(行序為主的存儲方式)

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

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

稀疏矩陣：非零元素個數(shù)遠小于矩陣(零)元素個數(shù)。

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

不分配空間。

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

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

單個元素，也可以是廣義表，稱為JS的原子和子表。當廣義表非空時，稱第一

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

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

3.7本章小結(jié)

1)知識點

其

象

抽

基W

據(jù)

他

數(shù)

序

本

存

型

類

概

存

儲

義

定

念?

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

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

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

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

2)小結(jié)

?線

跨殊隙性表

a

?

取

按

口加憧義序

再

存

存

OJAOT懂UJAiHa

tt

JLI

4、習題

（1）單項選擇題

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

每個元素的長度為2,則第5個元素的地址是（）。

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

2）線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)，而鏈式存儲結(jié)構(gòu)是一種

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

A.隨機存取B.索引存取C.順序存取D.散列存取

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

A,正確B.不正確

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

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

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

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

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

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

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

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

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

A.正確B.不正確

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

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

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

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

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

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

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

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

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

10）在雙向循環(huán)鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是（）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）在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p

之間插入s結(jié)點，則執(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）在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)

點，則執(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）在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(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）從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情

況下，需平均比較（）個結(jié)點。

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

15）在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復

雜度是（）。

2

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

16）給定有n個元素的向量，建立一個有序單鏈表的時間復雜度是（）。

2

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

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

1）單鏈表可以做的鏈接存儲表示。

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

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

下操作：

q=head;

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

s=newNode;s->data=e;

q->next=;〃填空

s->next=;〃填空

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

q=p->next;

p->next=;//填空

delete_______;〃填空

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

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

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

時間復雜度是;在給定值為x的結(jié)點后插入一個新結(jié)點的