《數(shù)據(jù)結(jié)構(gòu)與算法》理論教案

教案

講授章節(jié)第1講概述

授課時數(shù)2

0教學目的：

1.了解數(shù)據(jù)結(jié)構(gòu)課程的重要性和課程的基本要求，以及本課程涵蓋的內(nèi)容；

2.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念；

3.理解算法描述和簡單的算法分析。

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.閱讀：導學通知、課程介紹、學習方法、校內(nèi)SPOC使用方法、本章節(jié)知識點等

2.觀看導學視頻

3.論壇討論、反饋疑難點

二.課堂教學

01.介紹課程重要性和意義，以及學習目標等

2.什么是數(shù)據(jù)結(jié)構(gòu)

2.1通過“中國軟件和信息技術(shù)服務(wù)業(yè)現(xiàn)狀”、“排隊候車”等案例介紹線性結(jié)構(gòu)。

表1中國軟件和信息技術(shù)服務(wù)業(yè)現(xiàn)狀

軟件業(yè)收入統(tǒng)計人均創(chuàng)收軟件從業(yè)人員數(shù)統(tǒng)計

年份

（億元）（億元）（萬人）

20154284874.6574

20164823282.3586

20175510389.2618

o20186190995.0645

201971768106.6673

0

圖1軍人排隊候車

2.2通過“早期華為組織結(jié)構(gòu)圖”、“族譜”等案例介紹樹形結(jié)構(gòu)

公司綜合辦公室

中研總部■市場總部■制造部■財經(jīng)系統(tǒng)■行政管理部

認證部■投融斐部■財務(wù)部■審討部

圖2華為早期的管理組織結(jié)構(gòu)圖

圖3族譜

2.3通過“高速鐵路網(wǎng)”、“哥尼斯堡七橋問題”介紹圖形結(jié)構(gòu)

圖4我國“四縱四橫”高速鐵路網(wǎng)

圖5哥尼斯堡七橋問題

討論：歐拉回路存在的充分必要條件是：

(1)圖是連通的：(2)圖中與每個頂點相連的邊數(shù)(即頂點度數(shù))必須是偶數(shù)。

3.基本概念和術(shù)語

3.1介紹數(shù)據(jù)(Data)、數(shù)據(jù)元素(DataElement)、數(shù)據(jù)項(DataIlem)、數(shù)據(jù)對象(DataObject)>

抽象數(shù)據(jù)類型(AbstractDataType)、數(shù)據(jù)結(jié)構(gòu)三個要素。

3.2課堂練習

(1)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將之分為()。【中南大學】

A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

(2)己知表頭元素為c的單鏈表在內(nèi)存中的存儲狀態(tài)如下表所示?！?012全國統(tǒng)考408】

現(xiàn)將f放于1014H處并插入到單鏈表中，若f在邏輯上位a和e之間，則a,e,f的璉接地

址”依次是()。

A.1010H,1014H,1004HB.1010H,I004H,10I4H

C.1014H,1010H,1004HD.1014H,1004H,1010H

4.算法和算法分析

4.1介紹算法的定義、特性、設(shè)計要求及算法效率的衡量方法。

4.2“百錢買百雞”問題

討論+翻轉(zhuǎn)：我國占代數(shù)學家張丘建在《算經(jīng)》一書中曾提出過著名的百錢買百雞問題，

小組討論“百錢買百雞”算法思路，開展翻轉(zhuǎn)課堂活動，最后教師總結(jié)算法的重要性。

4.3引導學生歸納總結(jié)各種常見階數(shù)時間復雜度

4.4課堂練習

(1)求整數(shù)n(n>=0)階乘的算法如下，其時間復雜度是()。【2012全國統(tǒng)考4081

intfact(intn){

if(n<=l)rctum1;

教案

講授章節(jié)第2講線性表、順序表

授課時數(shù)2

0教學目的：

1.理解非空線性結(jié)構(gòu)的四個特征。

2.線性表是重要的線性結(jié)構(gòu)，要掌握線性表的定義。

3.掌握線性表的操作在順序表中的實現(xiàn)。

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

2.論壇討論、反饋疑難點

二.課堂教學

1.通過中國軟件和信息技術(shù)服務(wù)業(yè)現(xiàn)狀統(tǒng)計表，引入線性結(jié)構(gòu)學習，總結(jié)非空線性結(jié)構(gòu)的

四個特征

軟件業(yè)收入統(tǒng)計人均創(chuàng)收軟件從業(yè)人員數(shù)統(tǒng)計

年份

1億元）（億元）（萬人）

20154284874.6574

20164823282.3586

2UI75510389.2618

20186190995.0645

0201971768106.6673

2.線性表的概念

3.線性表的抽象數(shù)據(jù)類型

data?curl.n—.h?

%a|&2.....at?-l

,—mjaiSixc?

4.給定線性表的邏輯結(jié)構(gòu)設(shè)計算法

（1）遍歷線性表L

（2）合并線性表1:設(shè)La和Lb是元素屬于同一數(shù)據(jù)對象且非遞減有序的兩個線性表，

現(xiàn)要求將兩個線性表合并成一個新的非遞減有序的線性表Lc。

（3）合并線性表2:設(shè)La和Lb是元素屬于同一數(shù)據(jù)對象的兩個線性表，試將線性表Lb合

并到線性表La中。要求Lb中元素和La中元素相同的不再合并。

要分析為什么（2）和（3）的時間復雜度分別是O（m*n）和O（m+n）。

5.線性表的順序表示及類型定義

6.順序表上基本運算的實現(xiàn)

（1）構(gòu)造一個空順序表；（2）拷貝構(gòu)造函數(shù)；（3）遍歷順序表；（4）查找元素；15）求

前驅(qū)和后繼；（6）插入運算：（7）刪除運算；（8）逆置運算；（9）擴大表空間；

重點分析在插入和刪除操作中的時間復雜度。

7.算法設(shè)計舉例

（1）順序結(jié)構(gòu)線性表LA與LB的結(jié)點關(guān)鍵字為整數(shù)。LA與LB的元素按非遞減有序，

線性表空間足夠大。試給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持

非遞減有序。高效指最大限度的避免移動元素。

（2）【北京航空航天大學】已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時訶復雜

度為0（n）、空間復雜度為0（1）的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。（0（1）

表示算法的輔助空間為常量）。

（3）[2010全國統(tǒng)考408】設(shè)將n（n>l）個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時

間和空間兩方面都盡可能高效的算法，將R中保存的序列循環(huán)左移P（0<P<n）個位置，即

將R中的數(shù)據(jù)由（X0,Xl,...,Xn-l）變換為（Xp,Xp+l,...,Xn-1,X0,X1..,Xp-1）.要求：a）給出

算法的基本設(shè)計思想。b）采用C或C++或JAVA語言描述算法c）說明算法的時間復雜度和

空間女雜度。d）討論：若采用直接左移p位，空間笈雜度仍為0（1）,但時間女雜度為O（np）。

三.課后鞏固（線上）

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點：

1.重點是順序表的定義，基本操作的實現(xiàn)。

2.難點是高效算法設(shè)計，例如國家2010年碩士研究生入學考試算法題就有5種解法

教學方法、教學手段：

1.線性表和順序表的概念和類型定義（30分鐘）

2.順序表上基本運算的實現(xiàn)（30分鐘）

3.順序表算法舉例（30分鐘）

4.使用教具：計算機和投影儀；

5.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學堂在線MOOC、算法演示

動畫；

6.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法；課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題：

1.分析在順序存儲結(jié)構(gòu)卜.插入和刪除結(jié)點時平均需要移動多少個結(jié)點。

2.順序表la與1b非遞減有序，順序表空間足夠大。試設(shè)計一種高效算法，將1b中元素合到

la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素。

改為:順序表la非遞減有序，1b非遞增有序，求解該問題。

參考資料：

1.馮廣慧，吳昊，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,2019

2.陳守孔，胡瀟琨，李玲，馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工

業(yè)出版社，2020

教案

講授章節(jié)第3講單鏈表

授課時數(shù)2

0教學目的：

1.掌握鏈表的類型定義和基本操作的實現(xiàn)。

2.掌握單鏈表的建立方法，特別是頭插法和尾插法。

3.了解單鏈表的應(yīng)用。

教學內(nèi)容（講授提綱）

二.課前導學7線衛(wèi)5

1.觀看導學視頻

2.論壇討論、反饋疑難點

二.課堂教學

01從順序存儲結(jié)構(gòu)的優(yōu)缺點，引出鏈表的必要性

插入和刪除必須大量移動元素：必須預(yù)先確定空間；表空間不易擴充。

head

II—1?…

2.鏈表的類型定義

幾個概念：結(jié)點，首元結(jié)點，第一元素結(jié)點，頭結(jié)點，指針，頭指針

頭指針頭絲點甄結(jié)點

B—H3—?I

o

3,線性表的操作在單鏈表中的實現(xiàn)

（1）單鏈表的初始化；（2）清空單鏈表；（3）求表長；（4）遍歷鏈表；（5）查找位序為i

的元素的地址；（6）查找值為value的元素的位序；（7）查找值為value的元素的前驅(qū)；（8）求

某元素的后繼：（9）插入元素：（10）刪除元素。

4.單鏈表的建立方法（特別是頭插法和尾插法）

（1）頭插法；（2）尾插法。

5.算法設(shè)計舉例

（1）【2012全國統(tǒng)考408】假定采用帶頭結(jié)點的單鏈表保存單詞，當兩個單詞有相同的后

綴時.，則可共享相同的后綴存儲空間。例如，“l(fā)oading”和“being”的存儲映像如下圖所示，

設(shè)strl和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為（data,next）請設(shè)

0計一個時間上盡可能高效的算法，找出由sW和slr2所指的兩個鏈表共同后綴的起始位置（如

圖中字符i所在結(jié)點的位置p）。要求：a）給出算法的基衣設(shè)計思想。b）根據(jù)設(shè)計思想，采用

C或C++或JAVA語音描述算法，關(guān)鍵之處給出注釋。c）說明你所設(shè)計算法的時間復雜度。

（2）【2009全國統(tǒng)考408】已知一個帶有表頭結(jié)點的單鏈表，結(jié)點結(jié)構(gòu)為（dataJink）,假設(shè)

該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表

中倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)），若查找成功，算法輸出該結(jié)點的data域的值，并返

回1;否則，只返回0,要求：a）描述算法的基本設(shè)計思想：b）描述算法的詳細實現(xiàn)步驟；c）

根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言描述算法（使用C或C++或JAVA語言實現(xiàn)），關(guān)

鍵之處請給出簡要注釋。

三.課后鞏固（線上）

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點：

1.動態(tài)存儲（單鏈表）的概念。

2.單鏈表的算法設(shè)計。

教學方法、教學手段：

1.鏈表的定義和基本操作的實現(xiàn)（45分鐘）

2.鏈表生成和鏈表應(yīng)用的算法設(shè)計（45分鐘）

3.使用教具：計算機和投影儀；

4.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學堂在線MOOC、算法演示

動畫；

5.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法；課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題：

1.試述頭指針、頭結(jié)點、元素結(jié)點、首元結(jié)點的區(qū)別，說明頭指針和頭結(jié)點的作用。

2.分析順序存儲結(jié)構(gòu)和健式存儲結(jié)構(gòu)的優(yōu)缺點，說明何時應(yīng)該利用何種結(jié)構(gòu)。

3.為什么在單循環(huán)鏈表中常使用尾指針，若只設(shè)頭指針，插入元素的時間復雜度如何？

4.在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結(jié)點，能否刪除該結(jié)點，時間

復雜度如何？

5.設(shè)ha和腦分別是兩個帶頭結(jié)點的非遞減有序單鏈表的頭指針，試設(shè)計算法，將這兩

個有序鏈衣合并成個非遞增有序的單鏈衣。要求使用原鏈表空間，衣中無重復數(shù)據(jù)。

改：設(shè)施和腦分別是兩個帶頭結(jié)點的非遞減有序單鏈表的頭指針，試設(shè)計算法，將這

兩個有序鏈表合并成一個非遞減有序的單鏈表。要求使用原鏈表空間，表中無重復數(shù)據(jù)，

參考資料：

1.馮廣慧，吳昊，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,2Q19

2.陳守孔，胡瀟琨，李玲，馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工

業(yè)出版社,2020

3.翁惠玉，俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn)，高等教育出版社[M].高等教育出版社,2018

教案

講授章節(jié)第4講循環(huán)鏈表、雙鏈表

授課時數(shù)2

0教學目的：

1.掌握循環(huán)鏈表引入的背景：從任一結(jié)點開始可以訪問鏈表中的全部結(jié)點。

2.掌握循環(huán)鏈表（單循環(huán)鏈表，雙循環(huán)鏈表）和雙鏈表。

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

2.論壇討論、反饋疑難點

二.課堂教學

1.比較順序表和單鏈表操作的優(yōu)缺點，使用范圍

02.介紹單循環(huán)鏈表。指出：單循環(huán)鏈表往往只設(shè)尾指針

3.講解兩個只設(shè)尾指針的單循環(huán)鏈表合并成一個單循環(huán)鏈表的例子

4.雙鏈表的定義

為深刻的理解雙鏈表，展開討論：

p->prior->next==?;

P->ncxt->prior==?;

引導學生理解雙鏈表的特點：

p->prior->next==P->next->prior==p;

注意區(qū)分雙鏈表和雙循環(huán)鏈表是兩種鏈表。

5.線性表的操作在雙鏈表中的實現(xiàn)

o凡涉及一個方向的指針時，如求長度，取元素，元素定位等，其算法描述和單鏈表基本相

同。但是在插入或刪除結(jié)點時，一個結(jié)點就要修改兩個指針域，所以要比單鏈表復雜。由于雙

鏈表有兩個指針域，求前卵和后繼都很方便。

s->prior=p->prior：

p->prior->ncxt=s;

s->next=p;

p->prior=s;

p->prior->next=p->next;

0p->next->prior=p->prior;

deletep;

92雙缺中暗由巨

6.算法設(shè)計舉例

（1）將單循環(huán)鏈表改為雙循環(huán)鏈表。假設(shè)一個單循環(huán)鏈表，其結(jié)點含有三個域pre、data、

nexto其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針（null）；next為指針域，它指向后繼

結(jié)點。請設(shè)計算法，將此表改成雙向循環(huán)鏈表。

（2）已知一雙向循環(huán)鏈表，從第二個結(jié)點至表尾遞增有序，（設(shè)alvxvan）。試編寫算法，

將第一個結(jié)點刪除并插入表中適當位置，使整個鏈表遞增有序。

（3）［2015全國統(tǒng)考408】用單鏈表保存m個整數(shù),節(jié)點的結(jié)構(gòu)為（data,國k）,K|data|<n（n

為正整數(shù)）?，F(xiàn)要求設(shè)計一個時間復雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅

保留第一次出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表head如下。

HE?AD1HEAD

匚土WG一國土EH—EB一匣］刪除后03-03—ES-ELD

三.課后鞏固（線上）

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點:

1.循環(huán)鏈表和雙鏈表的概念C

2.難點是循環(huán)鏈表和雙鏈表的應(yīng)用算法設(shè)計。

教學方法、教學手段:

1.循環(huán)鏈表和雙鏈表（45分鐘）

2.算法設(shè)計（45分鐘）

3.使用教具：計算機和投影儀；

4.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學堂在線MOOC、算法演示

動畫；

5.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法；課后觀

看習題視頻，并在校內(nèi)SP0C完成知識點在線測試。

作業(yè)、討論題、思考題:

1.設(shè)la是一個雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入元素x,使表中元素

依然遞增有序。改為：設(shè)la是一個雙向循環(huán)鏈表，其表中元素遞減有序。試寫一算法插入元素

X,使表中元素依然遞減有序。

2.設(shè)計一算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式

各自僅有奇次塞或偶次塞頂，并要求利用原鏈表中的結(jié)點空間來構(gòu)造這兩個鏈表。

參考資料:

1.馮廣慧，吳吳，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）1MJ.電子工業(yè)出版社,2019

2.陳守孔，胡瀟琨，李玲，馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）［M］.機械工

業(yè)出版社,2020

3.翁忠玉，俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn)，高等教育出版社［M］.高等教育出版社,2018

教案

講授章節(jié)第5講棧

授課時數(shù)2

0教學目的：

1理解棧和隊列仍屬于線性結(jié)構(gòu)，其操作是線性表操作的子集，是操作受限的線性表。但

從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。

2.掌握棧的定義及操作。棧是只準在一端進行插入和刪除操作的線性表，該端稱為棧的頂

端。

3.掌握棧的順序和鏈式存儲結(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實現(xiàn)棧的操作。

4.棧的應(yīng)用：表達式求值。

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

02.論壇討論、反饋疑難點

二.課堂教學

1.棧的基本概念：棧、棧頂、棧尾，棧只在棧頂操作。

o

2.棧的抽象數(shù)據(jù)類型定義

3.順序棧及棧的操作在順序棧中的實現(xiàn)

4.鏈棧及棧的操作在順序棧中的實現(xiàn)

5.課堂練習

（1）【2010全國統(tǒng)考408】若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替

0進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（）o

A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b

（2）［2013全國統(tǒng)考408】一個棧的入棧序列為1,2,其出棧序列是pl,p2,p3…pn。

若p2為3,則p3可能取值的個數(shù)是（）。A.n-3B.n-2C.n-1D.無法確定

6.棧的應(yīng)用

（1）過程調(diào)用

（2）消除遞歸

（3）使用棧進行數(shù)制轉(zhuǎn)換

（4）中綴表達式的求值

算術(shù)表達式中運算符（+,-,*,/等）的優(yōu)先規(guī)則

設(shè)置兩個工作棧：運算符棧SI和操作數(shù)棧S2oS2存放表達式的運算結(jié)果。

算法思想：

1首先置操作數(shù)棧S2為空棧，置運算符棧的棧底為表達式的起始符#（優(yōu)先級最低）。

2依次讀入表達式的每個字符ch,直至表達式結(jié)束：

若ch是操作數(shù)，則進S2棧；

若ch是運算符，若其優(yōu)先級不高于棧頂運算符的優(yōu)先級時，則取出枝S2的棧頂和次

棧頂?shù)膬蓚€元素以及棧S1的棧頂運算符，進行相應(yīng)的運算，并將結(jié)果放入棧S2中；如此下去，

直至ch的優(yōu)先級高于棧頂運算符的優(yōu)先級，將ch入S1枝。

三.課后鞏固（線上）

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點：

1.重點是棧的概念和基礎(chǔ)知識。

2.難點：中綴表達式求值。

教學方法、教學手段：

1.棧的基本概念和順序棧（45分鐘）

2.鏈棧、中綴表達式求值（45分鐘）

3.使用教具：計算機和投影儀；

4.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”、學堂在線MOOC、算法演示動畫；

5.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法：課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題：

1.有五個數(shù)依次進棧：I、2、3、4、5。在各種出棧的序列中以3、4先出的序列有哪幾個。

2.鐵路進行列車調(diào)度時，常把站臺設(shè)計成棧式結(jié)構(gòu)，若進站的六輛列車順序為：1,2,3,

4,5,6,那么是否能夠得到435612,325641,154623和135426的出站序列,如果不能，說明

為什么不能；如果能，說明如何得到（即寫出”進棧"或"出棧”的序列）。

3.設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，“abba”和"abccba”是“回文”，“abcdc”

和“ababab”則不是“回文”，試寫一個算法，判別讀入的一個以@為結(jié)束符的字符序列是否是“回

文

參考資料：

I.馮廣慧，吳昊，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,2019

2.陳守孔，胡瀟琨，李玲，馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版七2020

教案

講授章節(jié)第6講校的應(yīng)用

授課時數(shù)2

教學目的：

1.掌握棧的定義的本質(zhì)：LIFO。棧是只準在一端進行插入和刪除操作的線性表，該瑞稱為

棧的頂端。

2.掌握棧的應(yīng)用：中綴表達式轉(zhuǎn)為后綴表達式，并求值。

3.掌握遞歸過程的應(yīng)用。

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

2.論壇討論、反饋疑難點

二.課堂教學

本次課繼續(xù)學習棧的應(yīng)用。

1.中綴表達式轉(zhuǎn)為后綴表達式

（1）算法思想及實現(xiàn)

（2）舉例：中綴表達式12*（6/205）轉(zhuǎn)為后綴表達式

（3）介紹中綴表達式轉(zhuǎn)為后綴表達式的簡單方法

2.課堂練習

（1）[2012全國統(tǒng)考408】已知操作符包括，+',＜，（和）。將中綠表達式

a+b-a*（（c+d）/e-D+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f-*-g+時，用棧來存放暫時還不能確定運

算次序的操作符。若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是（）。

A.5B.7C.8D.11

（2）【2014全國統(tǒng)考408】假設(shè)棧初始為空，將中綴表達式a/b+（c*d-e*f）/g轉(zhuǎn)換為等價的

后綴表達式的過程中，當掃描到f時，棧中的元素依次是（）。

A.+（*-B.+（-*C./+（*-*D./+-*

3.后綴表達式求值

（1）算法思想及實現(xiàn)

（2）舉例：后綴表達式1262/0.5-*求值

4.遞歸：若在一個函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)部，直接（或間接）出現(xiàn)定義本身的

應(yīng)用，則稱它們是遞歸的，或者是遞歸定義的。

5.遞歸過程的應(yīng)用

問題的定義是遞歸的：f（n）=n*f（n-l）

數(shù)據(jù)結(jié)構(gòu)是遞歸的：鏈表

問題的解法是遞歸的：Hanoi塔問題

6.遞歸算法的優(yōu)缺點

7.遞歸的消除

(1)采用迭代算法

(2)尾遞歸的消除

(3)利用棧消除任何遞歸

三.課后鞏固(線上)

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點；

1.中綴表達式轉(zhuǎn)成前綴、后綴表達式，并對兩種表達式求值。

2.用遞歸解決的問題：問題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問題的解法是遞歸

的，掌握典型問題的算法。將遞歸算法轉(zhuǎn)為非遞歸算法，特別是尾遞歸的消除。

教學方法、教學手段：

1.復習棧的基本概念、中綴表達式轉(zhuǎn)為后綴表達式并求值(45分鐘)

2.遞歸過程、消除遞歸(45分鐘)

3.使用教具：計算機和投影儀；

4.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學堂在線MOOC、算法演示

動畫；

5.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法；課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題：

1.寫出下列中綴表達式的后綴表達式：

(1)A*B*C(2)(A+B)*C-D(3)A*B+C/①-E)(4)(A+B)*D+E/(F+A*D)+C

2.選擇題：4個園盤的Hahoi塔，總的移動次數(shù)為()。

A.7B.8C.15D.16

3.已知Ackerman函數(shù)定義如下，試寫出遞歸算法。

/7+1m=0

Akm(m,n)=akir^m-1,1)in*0,n=0

akn^m-\,akn^m9n-1))w0,〃工0

4.整數(shù)序列如，a2,an，給出求解最大值的遞歸程序。

5討論：有哪些方式可以避免順序隊列的假溢出，如何判斷隊列滿和空

參考資料：

1.馮廣慧，吳昊，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)(C++語言版)[M].電子工業(yè)出版社,2019

2.陳守孔，胡瀟琨，李玲，馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析(第四版)[M].機械工

業(yè)出版社,2020

3.翁惠玉，俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn)，高等教育出版社[M].高等教育出版社,2018

教案

講授章節(jié)第7講隊列

授課時數(shù)2

0教學目的：

1.隊列的基本概念和算法，其木質(zhì)是：FIFO。

2.掌握鏈隊列空的條件是首尾指針相等，而循環(huán)隊列滿的條件的判定，則有犧牲一個單元

和設(shè)標記等方法。

3.棧和隊列的綜合應(yīng)用

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

2.論壇討論、反饋疑難點

0二.課堂教學

1.隊列的基本概念和術(shù)語，其本質(zhì)是：FIFOo

o

2.隊列的類型定義

3.隊列的順序表示和實現(xiàn).重點講解循環(huán)隊列

提出問題一產(chǎn)生矛盾一解決矛盾：順序隊列的假溢出一循環(huán)隊列一隊頭隊尾相等時是滿和

空的判斷。

循環(huán)隊列的入隊、出隊、求隊列元素個數(shù)等操作中，都要注意取模操作。

4.隊列的鏈式表示和實現(xiàn)

05.課堂練習

[2014全國統(tǒng)考4081循環(huán)隊列存放在一維數(shù)組中，endl指向隊頭元素，end2

指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M—

1個元素，初始時為空。下列判斷隊空和隊滿的條件中，王確的是（）。

A.隊空：end1==end2;隊滿end1==(end2+l)modM

B.隊空：endl==cnd2:隊滿：cnd2==(endl+l)mod(M-l)

C.隊空：end2==(end1+1)modM;隊滿：endl==(end2+1)modM

D.隊空：encl1==(end2+1)modM;隊滿：end2==(end1+1)mod(M-1)

6.算法設(shè)計舉例

(1)假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，不設(shè)頭指針，

試設(shè)計相應(yīng)的入隊列和出隊列的算法

(2)要求完全利用循環(huán)隊列中的元素空間，設(shè)置一個標志域lag,并以tag的值是0或1

來區(qū)分尾指針和頭指針相同時的隊列狀態(tài)是"空''還是“不空請編寫與此結(jié)構(gòu)相對應(yīng)的入隊和

出隊的算法。

(3)請利用兩個棧SI和S2來模擬一個隊列?！旧虾＝煌ù髮W】【度門大學】

三.課后鞏固(線上)

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點:

1.隊列的概念，循環(huán)隊列和鏈隊列操作的實現(xiàn)。

2.循環(huán)隊列中隊列空川隊頭指針等于隊尾指針來判斷，隊列滿則可用犧牲一個單元及設(shè)標

記等方法。這里特別注意入隊、出隊和求元素個數(shù)等操作中的取模運算。

3.難點是棧和隊列的綜合運用

教學方法、教學手段:

1.隊列的基本概念、循環(huán)隊列(45分鐘)

2.鏈隊列(20分鐘)

3.算法設(shè)計舉例(25分鐘)

4.使用教具：計算機和投影儀；

5.輔助教學：雨課堂、校內(nèi)SPOC、百科園、學堂在線MOOC、算法演示動畫；

6.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法：課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題:

1.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為。和3,當從

隊列中刪除一個元素，再加入兩個元素后，rear和from的值分別為多少？

2.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊和出隊的時間如何？若

只設(shè)尾指針呢？

3.循環(huán)隊列存儲在數(shù)組中，則入隊時的操作為().

A.rear=rear+1B.rear=(rear+l)%(m-1)

C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)

4.設(shè)用變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出

此循環(huán)隊列的定義，并寫出相應(yīng)的入隊(Queuein)和出隊(QueueOul)算法。

5.討論：循環(huán)隊列的優(yōu)點是什么，如何判斷“空”和“滿”。

參考資料:

1.馮廣慧，吳昊，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)(C++語言版)[M].電子工業(yè)出版社,2019

2.陳守孔，胡瀟琨,李玲馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版七2020

教案

講授章節(jié)第8講串

授課時數(shù)2

0教學目的：

1.理解串的模式匹配。

2.掌握樸素模式匹配算法及改進（KMP）算法、求next口和nextval。的算法。

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

2.論壇討論、反饋疑難點

二.課堂教學

1.串的概念和術(shù)語

02.串的表示和實現(xiàn)

比較順序存儲、鏈式存儲（存儲密度低）、塊鏈式存儲（算法實現(xiàn)復雜），字符串一般采用

順序存儲結(jié)構(gòu)表示和實現(xiàn)。

3.樸素模式匹配算法

（1）算法思想及實現(xiàn)

（2）舉例模擬匹配過程，主串S="GoogleGooseGood"，模式串T="Good”。

4.KMP算法——KMP—Knuth,Morris,Pratt三人發(fā)明

高德納（DonaldErvinKnuth,1938年），美國著名計算

機科學家，斯坦福大學電腦系榮譽教授。高德納教授被譽

為現(xiàn)代計算機科學的鼻祖，在計算機科學及數(shù)學領(lǐng)域發(fā)表

o了多部具廣泛影響的論文和著作，與EdsgcrWybe

Dijkstra并稱為我們這個時代最偉大的計算機科學家的

人。高德納還是TheArtofComputerProgramming（中

譯本《計算機程序設(shè)計藝術(shù)》）的作者以及TeX和Metafont

排版軟件的發(fā)明人。

（1）算法特點，無需回溯，在O（n+m）的時間量級上完成串的模式匹配操作

（2）KMP算法思想

（3）求解next數(shù)組的算法思想，舉例手工模擬過程

（4）算法實現(xiàn)

05.next數(shù)組的改進

討論：模式串P=,aaaab'?其next函數(shù)值為01234,若主串為‘a(chǎn)aabaaabaaaab',當i=4,j

=4時siWpj,由next|j］的指示還需進行i=4、j=3,i=4、j=2,i=4、j=1等三次比較實際

L，由于模式中第1、2、3個字符和第4個字符都相等，囚此這種比較是不必要的，可以將模

式串一次向右滑動4個字符直接進行i=5、j=l的比較。也就是說，若next[jl=k,當si與pj

失配且pj=pk,則下一步不需將主串中的si與pk比較，而是直接與next[k]進行比較。由以上

思想對nexl函數(shù)進行改進。

6.樸素模式匹配算法與KMP算法的比較

雖然樸素模式匹配算法的時間復雜度是O（n*m）,但在一般情況下，其實際的執(zhí)行時T近似

于O（n+m）,因此至今仍被采用。KMP算法僅當主串與模式間存在許多“部分匹配”的情況下才

顯得快得多。KMP算法的最大特點是主串指針不回溯，在整個匹配過程中，對主串從頭到尾掃

描一遍，對于處理存儲在外存上的大文件是非常有效的。

7.課堂練習

【2015全國統(tǒng)考408】己知字符串S為"abaabaabacacaabaabcc"，模式串t為"abaabc'1,

采用KMP算法進行匹配，第一次出現(xiàn)“失配”（s[i]!=中]）時，i=j=5,則下次開始匹配時，i和

j的值分別是（）o

A.i=l,j=0B.i=5>j=0C.i=5?j=2D.i=6?j=2

8.算法設(shè)計舉例，寫出一個遞歸算法來實現(xiàn)字符串逆序存儲?！局锌圃貉芯可骸?/p>

三.課后鞏固（線上）

觀看習題視頻，并在校內(nèi)SPOC完成知識點測試；在“百利園”完成線性結(jié)構(gòu)闖關(guān)訓練。

本章節(jié)的教學重點、難點:

1.本章重點是串的模式匹配、手工描述求匹配串的nexl和nextval函數(shù)值。

2.難點是KMP算法的推導過程。

教學方法、教學手段:

1.串的概念和術(shù)語、串的表示和實現(xiàn)（30分鐘）

2.KMP算法、求解next和nextval（50分鐘）

3.算法設(shè)計（10分鐘）

3.使用教具：計算機和投影儀；

4.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”、學堂在線MOOC、算法演示動畫；

5.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法；課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題：

1.設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非

空且不同于S本身）的個數(shù)是多少？

2.用順序結(jié)構(gòu)存儲的串S,編寫算法刪除S中第i個字符開始的j個字符。

3.模式率t=44abcaabbcaabdab'',求模式市的next和nextval數(shù)組的值。

4.對S='aabcbabcaabcaaba',T='bca',畫出以T為模式串,S為目標串的匹配過程。

5.函數(shù)voidinsert（charchar*t,intpos）表示將字符串t插入到字符串s中，插入位置為

poso請編寫實現(xiàn)該函數(shù)的算法。假設(shè)分配給字符串s的空間足夠讓字符串t插入。

6.討論：kmp算法的特點是什么？BF算法已經(jīng)不適用了嗎？

參考資料：

1.馮廣慧，吳昊，文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,2019

2.陳守孔，胡瀟琨，李玲，馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版社,2020

教案

講授章節(jié)第9講樹、二叉樹的概念和性質(zhì)

授課時數(shù)2

0教學目的：

1.理解樹是復雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二又樹的遞歸定義，基本概念，術(shù)語。

2.掌握二叉樹的性質(zhì)，存儲結(jié)構(gòu)

教學內(nèi)容（講授提綱）

一.課前導學（線上）

1.觀看導學視頻

2.論壇討論、反饋疑難點

二.課堂教學

1.樹的基本概念合術(shù)語

0

o

2.二叉樹的基本概念和特點，二叉樹的5種基本形態(tài)

3.二叉樹的5個性質(zhì)1對每個性質(zhì)，都要會證明）

性質(zhì)1：一個非空二叉網(wǎng)的第i層上至多有2M個結(jié)點（i>l）o

性質(zhì)2：深度為k的二叉樹至多有2k—1個結(jié)點（k>l）o

性質(zhì)3：任何一棵二叉網(wǎng)中，若葉子數(shù)為no,度為2的結(jié)點個數(shù)為m，則110=112+1。

性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為「log2（〃+l）］。

性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹按層次自上而下（每層自左而右）對結(jié)點

0從1到n進行編號，則對任意一個結(jié)點i（l<i<n）有：

（1）若i=l,則結(jié)點i為根，無雙親；若i>l,則結(jié)點i的雙親結(jié)點的編號是

（2）若2iWn,則i的左孩子的編號是2i,否則i無左孩子。

（3）若2i+，n,則i的右孩子的編號是2i+l,否則i無右孩子。

4.課堂練習

（1）[2011全國統(tǒng)考408】若一棵完全二叉樹有768個結(jié)點,則該二叉樹中葉結(jié)點的個數(shù)

是（）＜■

A.257B.258C.384D.385

（2）[2009全國統(tǒng)考4）8】已知一棵完全二叉樹的第6層（設(shè)根是第1層）有8個口一結(jié)點，

則該完全二叉樹的結(jié)點個數(shù)最多是（）。

A.39B.52C.IllD.119

三.課后鞏固（線上）

課后觀看習題視頻，并在校內(nèi)SPOC完成知識點測試。

本章節(jié)的教學重點、難點：

重點和難點是二叉樹的特點和5個性質(zhì)。

教學方法、教學手段：

1.樹的概念和術(shù)語（30分鐘）

2.二又樹的概念和性質(zhì)（45分鐘）

3.課堂練習（15分鐘）

4.使用教具：計算機和投影儀；

5.輔助教學：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學堂在線MOOC、算法演示

動畫；

6.課前觀看導學視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學法；課后觀

看習題視頻，并在校內(nèi)SPOC完成知識點在線測試。

作業(yè)、討論題、思考題：

1.設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點個數(shù)分別為4,2,1,1,求葉子數(shù)。

2.一棵完全二叉樹有500個結(jié)點，請問該完全二叉樹有多少個葉子結(jié)點？有多少個度為1

的結(jié)點？有多少個度為2的結(jié)點？如果完全二叉樹有501個結(jié)點，結(jié)果如何？請寫出推導過程