教案紙（首頁(yè)）第1頁(yè)第次課學(xué)時(shí)授課時(shí)間________教學(xué)主題棧和隊(duì)列棧的特點(diǎn)；棧的表示和實(shí)現(xiàn)；棧的典型應(yīng)用與實(shí)現(xiàn)教學(xué)要求通過(guò)本章的學(xué)習(xí)，學(xué)生應(yīng)達(dá)到如下基本要求：1、掌握棧的邏輯結(jié)構(gòu)特性，棧抽象數(shù)據(jù)類型的描述方法。2、掌握棧的先進(jìn)后出特點(diǎn)。3、掌握棧基本運(yùn)算在兩類存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)算法。4、掌握棧在實(shí)際求解問(wèn)題中的應(yīng)用方法。教學(xué)重點(diǎn)棧的邏輯結(jié)構(gòu)特點(diǎn)；順序棧和鏈棧的基本算法設(shè)計(jì)。教學(xué)難點(diǎn)棧與線性表的異同；順序棧和鏈棧的基本算法設(shè)計(jì)教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、板書、上機(jī)實(shí)操講授要點(diǎn)1、棧的邏輯結(jié)構(gòu)特性。2、棧抽象數(shù)據(jù)類型的描述方法。3、順序棧的算法設(shè)計(jì)方法。4、鏈棧的算法設(shè)計(jì)方法。5、棧在表達(dá)式求值中的應(yīng)用。作業(yè)完成學(xué)習(xí)通上第三章中有關(guān)棧的練習(xí)作業(yè)。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁(yè)為每次課教案首頁(yè)教案紙（續(xù)頁(yè)）第5頁(yè)教學(xué)內(nèi)容備注與后記3.1棧1、棧的定義棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。特點(diǎn)：后進(jìn)先出關(guān)于棧的幾個(gè)概念：允許進(jìn)行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。棧的插入操作通常稱為進(jìn)?；蛉霔?。棧的刪除操作通常稱為退棧或出棧。舉實(shí)例說(shuō)明，加深學(xué)生對(duì)棧的理解和認(rèn)識(shí)。2、棧的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)——順序棧鏈?zhǔn)酱鎯?chǔ)——鏈棧3、棧的基本運(yùn)算InitStack(&s)：初始化棧。構(gòu)造一個(gè)空棧s。DestroyStack(&s)：銷毀棧。釋放棧s占用的存儲(chǔ)空間。StackEmpty(s)：判斷棧是否為空:若棧s為空，則返回真；否則返回假。Push(&S，e)：進(jìn)棧。將元素e插入到棧s中作為棧頂元素。Pop(&s，&e)：出棧。從棧s中退出棧頂元素，并將其值賦給e。GetTop(s，&e)：取棧頂元素。返回當(dāng)前的棧頂元素，并將其值賦給e。4、順序棧的基本操作實(shí)現(xiàn)typedefstruct{ElemTypedata[MaxSize]；inttop； //棧頂指針}SqStack；順序棧的6種基本運(yùn)算實(shí)現(xiàn)。例3-4。5、鏈棧的基本操作實(shí)現(xiàn)typedefstructlinknode{ElemTypedata; //數(shù)據(jù)域structlinknode*next; //指針域}LinkStNode;順序棧的6種基本運(yùn)算實(shí)現(xiàn)。例3-5。3.2棧的典型應(yīng)用與實(shí)現(xiàn)1、簡(jiǎn)單表達(dá)式求值這里限定的簡(jiǎn)單表達(dá)式求值問(wèn)題是：用戶輸入一個(gè)包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號(hào)的合法算術(shù)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。中綴表達(dá)式：1+2*3后綴表達(dá)式：123*+前綴表達(dá)式：+1*23利用棧的特點(diǎn)將表達(dá)式轉(zhuǎn)化成后綴表達(dá)式，再利用棧求出表達(dá)式的值。2、求解迷宮問(wèn)題（選講內(nèi)容）給定一個(gè)M×N的迷宮圖、入口與出口、行走規(guī)則。求一條從指定入口到出口的路徑。利用棧后進(jìn)先出的特點(diǎn)求解上述問(wèn)題并實(shí)現(xiàn)算法。教學(xué)總結(jié)：本章節(jié)給大家介紹了棧的基本定義，棧的特點(diǎn)是后進(jìn)先出。利用棧的這個(gè)特性可以解決實(shí)際生活中遇到的一些問(wèn)題。

第次課學(xué)時(shí)授課時(shí)間______教學(xué)主題棧和隊(duì)列隊(duì)列的特點(diǎn)，表示和實(shí)現(xiàn)；隊(duì)列的應(yīng)用與實(shí)現(xiàn)教學(xué)要求1、掌握隊(duì)列的邏輯結(jié)構(gòu)特性，隊(duì)列抽象數(shù)據(jù)類型的描述方法。2、掌握隊(duì)列的先進(jìn)后出特點(diǎn)。3、掌握隊(duì)列基本運(yùn)算在兩類存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)算法。4、掌握隊(duì)列在實(shí)際求解問(wèn)題中的應(yīng)用方法教學(xué)重點(diǎn)順序隊(duì)的基本運(yùn)算算法設(shè)計(jì)；鏈隊(duì)的基本運(yùn)算算法設(shè)計(jì)；利用隊(duì)列求解復(fù)雜的應(yīng)用問(wèn)題。雙鏈表的查找、插入和刪除操作過(guò)程及其實(shí)現(xiàn)。教學(xué)難點(diǎn)順序隊(duì)和鏈隊(duì)的基本運(yùn)算算法設(shè)計(jì)；利用隊(duì)列求解復(fù)雜的應(yīng)用問(wèn)題。教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、板書、上機(jī)實(shí)操講授要點(diǎn)1、隊(duì)列的邏輯結(jié)構(gòu)特性。2、隊(duì)列抽象數(shù)據(jù)類型的描述方法。3、順序隊(duì)的算法設(shè)計(jì)方法。4、鏈隊(duì)的算法設(shè)計(jì)方法。作業(yè)完成學(xué)習(xí)通上第三章作業(yè)中有關(guān)隊(duì)列的練習(xí)題。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁(yè)為每次課教案首頁(yè)教案紙（續(xù)頁(yè)）教學(xué)內(nèi)容備注與后記3.3隊(duì)列1、隊(duì)列的定義隊(duì)列簡(jiǎn)稱隊(duì)，它也是一種運(yùn)算受限的線性表。。特點(diǎn)：先進(jìn)先出。隊(duì)列的幾個(gè)概念：進(jìn)行插入的一端稱做隊(duì)尾（rear）。進(jìn)行刪除的一端稱做隊(duì)首或隊(duì)頭（front）。向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素。從隊(duì)列中刪除元素稱為出隊(duì)或離隊(duì)，元素出隊(duì)后，其后繼元素就成為隊(duì)首元素。2、隊(duì)列的基本運(yùn)算InitQueue(&q)：初始化隊(duì)列。構(gòu)造一個(gè)空隊(duì)列q。DestroyQueue(&q)：銷毀隊(duì)列。釋放隊(duì)列q占用的存儲(chǔ)空間。QueueEmpty(q)：判斷隊(duì)列是否為空。若隊(duì)列q為空，則返回真；否則返回假。enQueue(&q，e)：進(jìn)隊(duì)列。將元素e進(jìn)隊(duì)作為隊(duì)尾元素。deQueue(&q，&e)：出隊(duì)列。從隊(duì)列q中出隊(duì)一個(gè)元素，并將其值賦給e。3、隊(duì)列的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)——順序隊(duì)鏈?zhǔn)酱鎯?chǔ)——鏈隊(duì)4、順序隊(duì)的基本運(yùn)算實(shí)現(xiàn)typedefstruct{ElemTypedata[MaxSize]；intfront，rear；//隊(duì)首和隊(duì)尾指針}SqQueue;順序隊(duì)的四要素：隊(duì)空條件：front=rear隊(duì)滿條件：rear=MaxSize－1元素e進(jìn)隊(duì)：rear++;data[rear]=e;元素e出隊(duì)：front++;e=data[front];順序隊(duì)實(shí)現(xiàn)隊(duì)列中的基本運(yùn)算。5、循環(huán)隊(duì)列的基本運(yùn)算實(shí)現(xiàn)把數(shù)組的前端和后端連接起來(lái)，形成一個(gè)環(huán)形的順序表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，稱為環(huán)形隊(duì)列或循環(huán)隊(duì)列。rear=(rear+1)%MaxSizefront=(front+1)%MaxSize循環(huán)隊(duì)列的四要素：隊(duì)空條件：front=rear隊(duì)滿條件：(rear+1)%MaxSize=front進(jìn)隊(duì)e操作：rear=(rear+1)%MaxSize;將e放在rear處出隊(duì)操作：front=(front+1)%MaxSize;取出front處元素e;6、鏈隊(duì)的基本運(yùn)算實(shí)現(xiàn)typedefstruct{DataNode*front; //指向單鏈表隊(duì)頭結(jié)點(diǎn)DataNode*rear; //指向單鏈表隊(duì)尾結(jié)點(diǎn)}LinkQuNode;鏈隊(duì)的四要素：隊(duì)空條件：rear=NULL隊(duì)滿條件：不考慮進(jìn)隊(duì)e操作：將包含e的結(jié)點(diǎn)插入到單鏈表表尾出隊(duì)操作：刪除單鏈表首數(shù)據(jù)結(jié)點(diǎn)鏈隊(duì)實(shí)現(xiàn)隊(duì)列中的基本運(yùn)算。3.4隊(duì)列的應(yīng)用與實(shí)現(xiàn)求解報(bào)數(shù)問(wèn)題設(shè)有n個(gè)人站成一排，從左向右的編號(hào)分別為1～n，現(xiàn)在從左往右報(bào)數(shù)“1，2，1，2，…”，數(shù)到“1”的人出列，數(shù)到“2”的立即站到隊(duì)伍的最右端。報(bào)數(shù)過(guò)程反復(fù)進(jìn)行，直到n個(gè)人都出列為止。要求給出他們的出列順序。例如，當(dāng)n=8時(shí)，初始序列為12345678則出列順序?yàn)?