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

2第一節(jié)什么是數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)概述一般來說，用計(jì)算機(jī)解決一個具體問題時，大致需經(jīng)過以下幾個步驟：1、從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型。2、設(shè)計(jì)一個解此數(shù)據(jù)模型的算法。3、編出程序，進(jìn)行測試、調(diào)整直至得到最終解答。如：求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型為線性方程組；預(yù)報人口增長情況的數(shù)學(xué)模型為微分方程。然而：更多的非數(shù)值計(jì)算問題無法用數(shù)學(xué)方程加以描述。特點(diǎn)：每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格；表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)；對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。例子：P1例1.1學(xué)生健康情況管理。圖書館的書目檢索系統(tǒng)自動化問題。查號系統(tǒng)自動化；倉庫賬目管理……例子：求一組（n個）整數(shù)中的最大值。算法：基本操作是“比較兩個數(shù)的大小”。特點(diǎn)：在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說的樹形結(jié)構(gòu)；對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。另外例子：#字棋。教材P1例1.2人事檔案管理。例子：計(jì)算機(jī)對弈。算法：對弈的規(guī)則和策略。其他例子：多叉路口交通燈的管理問題。教材P1例1.3在n個城市之間建立通信網(wǎng)絡(luò)。特點(diǎn)課程之間的先后關(guān)系用圖結(jié)構(gòu)描述；通過實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。結(jié)論1、當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)：所處理的數(shù)據(jù)量大且具有一定的關(guān)系；對其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對其進(jìn)行組織、管理和檢索。2、《數(shù)據(jù)結(jié)構(gòu)》課程研究的主要內(nèi)容。計(jì)算機(jī)的操作對象的關(guān)系更加復(fù)雜，不再是單純的數(shù)值計(jì)算，而更多地是非數(shù)值性處理。數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型（非數(shù)值計(jì)算）及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中數(shù)據(jù)以及它們之間的邏輯關(guān)系和對數(shù)據(jù)的操作的一門課程。重點(diǎn)分析數(shù)據(jù)之間的抽象的相互關(guān)系，而不涉及數(shù)據(jù)的具體內(nèi)容。二、數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況起源于程序設(shè)計(jì)的發(fā)展，程序設(shè)計(jì)經(jīng)歷三個階段：無結(jié)構(gòu)階段；結(jié)構(gòu)化程序設(shè)計(jì)階段；面向?qū)ο箅A段。教材中詳述第二個階段，即P2-4中（2）-（5）。三、數(shù)據(jù)結(jié)構(gòu)與其他課程的關(guān)系數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。第二節(jié)基本概念和術(shù)語一、數(shù)據(jù)是對客觀事物的符號表示。在計(jì)算機(jī)科學(xué)中其含義是指所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號集合。含義極為廣泛：圖像、聲音等。二、數(shù)據(jù)元素（節(jié)點(diǎn)）：數(shù)據(jù)的基本單位是數(shù)據(jù)集合中的一個實(shí)體，是計(jì)算機(jī)程序中加工處理的基本單位。如學(xué)籍管理中每個學(xué)生的信息；“樹”中的每一點(diǎn)；“圖”中的每一個圓圈。數(shù)據(jù)元素按其組成可分為簡單型數(shù)據(jù)元素和復(fù)雜型數(shù)據(jù)元素。簡單型數(shù)據(jù)元素由一個數(shù)據(jù)項(xiàng)組成，所謂數(shù)據(jù)項(xiàng)就是數(shù)據(jù)中不可再分割的最小單位；復(fù)雜型數(shù)據(jù)元素由多個數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個概念的多方面信息。三、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)中所說的“關(guān)系”實(shí)際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。如前后關(guān)系；上下層關(guān)系；先后關(guān)系。根據(jù)數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)可將數(shù)據(jù)結(jié)構(gòu)分為三類：線性結(jié)構(gòu)——一個對一個。如，線性表、棧、隊(duì)列。樹形結(jié)構(gòu)——一個對多個。如，樹。圖狀結(jié)構(gòu)——多個對多個，如，圖。四、存儲結(jié)構(gòu)（物理結(jié)構(gòu)）是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲器中的具體實(shí)現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不但要表示其本身的實(shí)際內(nèi)容，還要表示清楚數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。即數(shù)據(jù)元素的表示和關(guān)系的表示兩部分。1、數(shù)據(jù)元素的表示：位數(shù)據(jù)域元素或結(jié)點(diǎn)（表示信息的最小單位）（子位串，對應(yīng)于各數(shù)據(jù)項(xiàng)）（位串）2、關(guān)系的表示：即常見的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：特點(diǎn)是借助于數(shù)據(jù)元素的相對存儲位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)；P6圖1.5a鏈?zhǔn)酱鎯Y(jié)構(gòu)：特點(diǎn)是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。P6圖1.5b數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān)：算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲結(jié)構(gòu) 五、數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。簡單地說，就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。常見的數(shù)據(jù)結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。1、根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常有下列四類基本結(jié)構(gòu)：集合（散列）；線性結(jié)構(gòu)（1：1）；樹形結(jié)構(gòu)（1：N）；圖狀結(jié)構(gòu)（M：N）。2、數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組（D，S）。其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例如：六.數(shù)據(jù)類型:數(shù)據(jù)的取值范圍及其操作的總稱。例:C語言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef自定義數(shù)據(jù)類型第二講課題名稱：第一章緒論 第3節(jié)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 第4節(jié)算法教學(xué)目標(biāo)： 1、使學(xué)生了解數(shù)據(jù)類型的表示和實(shí)現(xiàn)； 2、使學(xué)生了解用類C語言對算法的表示和實(shí)現(xiàn)。教學(xué)重點(diǎn)和難點(diǎn)：類C語言的理解主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：第三節(jié)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)為了表示一個算法，可以用不同的方法。常用的有自然語言、傳統(tǒng)流程圖、偽代碼、PAD圖等。1、用自然語言表示算法：通俗易懂，但文字冗長，易出現(xiàn)“歧義性”。如：“張先生對李先生說他的孩子考上了大學(xué)。”2、用流程圖表示算法：直觀形象，易于理解。三種基本結(jié)構(gòu)的表示：順序結(jié)構(gòu)、先擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。只有一個入口，只有一個出口，結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會被執(zhí)行到，結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。僅適用于小問題，現(xiàn)在已很少用。3、用偽代碼表示算法：4、用計(jì)算機(jī)語言表示算法：如C或PASCAL5、用類C或類PASCAL語言算法描述：介于偽碼與C之間選擇算法描述語言的準(zhǔn)則（1）該語言應(yīng)該具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能；（2）該語言應(yīng)該盡可能地簡捷，以便于掌握、理解；（3）使用該語言描述的算法應(yīng)該能夠比較容易地轉(zhuǎn)換成任何一種程序設(shè)計(jì)語言?！邦怌”描述語言是通過對C語言進(jìn)行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴(kuò)展修改，從而，增強(qiáng)了語言的描述功能。以下對類C做簡要說明。1.預(yù)定義常量及類型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2數(shù)據(jù)元素被約定為EntryType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)的表示（即存儲結(jié)構(gòu)的表示）使用類型定義（typedef）描述。2.算法描述為以下的函數(shù)形式：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{語句序列；}為了簡化函數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說明，必要時給出相應(yīng)的注釋即可。另外，在書寫算法時，應(yīng)該養(yǎng)成對重點(diǎn)語句段落添加注解的良好習(xí)慣。一般而言：abcde等用作數(shù)據(jù)元素名；ijklmn等用作整型變量名；pqr等用作指針變量名；當(dāng)函數(shù)返回值為函數(shù)結(jié)構(gòu)狀態(tài)代碼時，函數(shù)定義為Status類型；除值調(diào)用方式外，增添C++的引用調(diào)用的參數(shù)傳遞方式（&）。3.在算法描述中可以使用的賦值語句形式有：簡單賦值變量名=表達(dá)式；串聯(lián)賦值變量名1=變量名2=...=變量名n=表達(dá)式；成組賦值（變量名1，...，變量名n）=（表達(dá)式1，...，表達(dá)式n）；變量名[]=表達(dá)式；變量名[始下標(biāo)..終下標(biāo)]=變量名[始下標(biāo)..終下標(biāo)]；結(jié)構(gòu)賦值結(jié)構(gòu)名1=結(jié)構(gòu)名2；結(jié)構(gòu)名=（值1，值2，...，值n）；條件賦值變量名=條件表達(dá)式?表達(dá)式1：表達(dá)式2；交換賦值變量名1?變量名2；4.在算法描述中可以使用的選擇結(jié)構(gòu)語句形式有：條件語句1if（表達(dá)式）語句；條件語句2if（表達(dá)式）語句；else語句；開關(guān)語句1switch（表達(dá)式）{case值1：語句序列1；break；case值2：語句序列2；break；...case值n：語句序列n；break；default：語句序列n+1；}開關(guān)語句2switch{case條件1：語句序列1；break；case條件2：語句序列2；break；...case條件n：語句序列n；break；default：語句序列n+1；}5.在算法描述中可以使用的循環(huán)結(jié)構(gòu)語句形式有：for循環(huán)語句for（賦初值表達(dá)式;循環(huán)條件表達(dá)式;修改表達(dá)式序列）語句；while循環(huán)語句while（循環(huán)條件表達(dá)式）語句；do-while循環(huán)語句do{語句序列；}while（循環(huán)條件表達(dá)式）；6.在描述算法中可以使用的結(jié)束語句形式有：函數(shù)結(jié)束語句return表達(dá)式；return;case或循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）；7.在算法描述中可以使用的輸入輸出語句形式有：輸入語句scanf([格式串]，變量名1，...，變量名n)；輸出語句printf([格式串]，表達(dá)式1，...，表達(dá)式n);方括號（[]）中的內(nèi)容是可以省略的部分。8.在算法描述中使用的注釋格式為：單行注釋//文字序列9.在算法描述中可以使用的擴(kuò)展函數(shù)有：求最大值max（表達(dá)式1，...，表達(dá)式n）求最小值min（表達(dá)式1，...，表達(dá)式n）求絕對值abs(表達(dá)式)求不足整數(shù)值floor(表達(dá)式)求進(jìn)位整數(shù)值ceil(表達(dá)式)判定文件結(jié)束eof(文件變量)或eof判定行結(jié)束eoln(文件變量)或eoln10.邏輯運(yùn)算約定與運(yùn)算&&對于A&&B，當(dāng)A的值為0時，不再對B求值?；蜻\(yùn)算||對于A||B，當(dāng)A的值為非0時，不再對B求值。例子：【算法1-1】用類C描述將三個數(shù)值排序的算法。viodThree_Sort(int*x,int*y,int*z){//將x,y,z三個指針?biāo)甘镜膬?nèi)容按從小到大的順序重新排列if(*y<*x&&*y<*z)*x?*y;//挑選出最小的數(shù)值并換到x指針?biāo)傅拇鎯卧衑lseif(*z<*x&&*z<*y)*x?*z;if(*z<*y)*y?*z;//在y和z所指示的存儲單元中挑選出較小者換到y(tǒng)中}第四節(jié)算法1.4.1算法的概念算法是解決某個特定問題的一種方法或一個過程。計(jì)算機(jī)對數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。算法是執(zhí)行特定計(jì)算的有窮過程，是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。算法應(yīng)該具有下列五個特性（1）動態(tài)有窮：一個算法必須（對任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。算法必須是一個可執(zhí)行完的步驟，但一個具有死循環(huán)的程序亦稱之為程序，這是算法與程序的區(qū)別。有窮的概念不是純數(shù)學(xué)的，而是在實(shí)際上合理和可以接受的。注意：算法和程序是有區(qū)別的，即程序未必能滿足動態(tài)有窮。但在本課程中，只討論滿足動態(tài)有窮的程序，因此“算法”和“程序”是通用的。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時不會產(chǎn)生二義性。（“手舉過頭頂”）（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。（4）輸入：一個算法應(yīng)該有零個或多個輸入。（獲得信息。）（5）輸出：一個算法應(yīng)該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。（目的）舉例問題：按從小到大的順序重新排列x，y，z三個數(shù)值的內(nèi)容。算法：（1）輸入x，y，z三個數(shù)值；（2）從三個數(shù)值中挑選出最小者并換到x中；（3）從y，z中挑選出較小者并換到y(tǒng)中；（4）輸出排序后的結(jié)果。=>算法就是一個具有次序、步驟清楚、最后一定會執(zhí)行結(jié)束的可執(zhí)行步驟。算法與程序不同之處在于上述第一條。1.4.2算法的設(shè)計(jì)要求(1)正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能，并達(dá)到所期望的性能要求。(2)可讀性：為了便于理解、測試和修改算法，算法應(yīng)該具有良好的可讀性。(3)健壯性：算法中擁有對輸入數(shù)據(jù)、打開文件、讀取文件記錄、分配內(nèi)存空間等操作的結(jié)果檢測，并通過與用戶對話的形式做出相應(yīng)的處理選擇。(4)時間與空間效率：算法的時間與空間效率是指將算法變換為程序后，該程序在計(jì)算機(jī)上運(yùn)行時所花費(fèi)的時間及所占據(jù)空間的度量。1.4.3算法效率的度量一、算法的時間效率算法的時間效率主要由兩個因素決定：l 所需處理問題的數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費(fèi)的時間就多；l 在解決問題的過程中，基本操作的執(zhí)行次數(shù)。時間特性的分析如果我們將一個算法所花費(fèi)的時間設(shè)計(jì)成一個以數(shù)據(jù)量n為自變量的函數(shù)T(n)，這個函數(shù)在正整數(shù)定義域范圍內(nèi)一定是單調(diào)遞增的。好的算法應(yīng)該能夠在數(shù)據(jù)量n增長的同時，函數(shù)T(n)的增長速度比較緩慢。P11例子。二、空間效率的分析一個算法的空間效率是指在算法的執(zhí)行過程中，所占據(jù)的輔助空間數(shù)量。輔助空間就是除算法代碼本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時開辟的存儲空間單元。在有些算法中，占據(jù)輔助空間的數(shù)量與所處理的數(shù)據(jù)量有關(guān)，而有些卻無關(guān)。后一種是較理想的情況。在設(shè)計(jì)算法時，應(yīng)該注意空間效率。第三講課題名稱：第二章棧和隊(duì)列 第1節(jié)棧 第2節(jié)棧的應(yīng)用舉例教學(xué)目標(biāo)： 1、使學(xué)生了解棧的表示和實(shí)現(xiàn)； 2、使學(xué)生掌握棧的應(yīng)用。教學(xué)重點(diǎn)和難點(diǎn)：棧的應(yīng)用主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：從邏輯上看，棧和隊(duì)列都屬于線性結(jié)構(gòu)，是兩種特殊的線性表。其特殊性在于它們的操作是線性表操作的子集。確切地說就是，線性表上的插入、刪除操作是不受限制的，而棧和隊(duì)列上的插入、刪除操作是受某種特殊的限制的。因此，棧和隊(duì)列稱作操作受限的線性表。3.1.1棧的定義棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如下所示：進(jìn)行插入和刪除的一端是浮動端，通常被稱為棧頂，并用一個“棧頂指針”指示；而另一端是固定端，通常被稱為棧底。我們經(jīng)常將棧用下圖形式描述：棧：插入和刪除在一端進(jìn)行的線性表。棧頂：進(jìn)行插入和刪除的浮動端。用棧頂指針指示。棧底：固定端。進(jìn)棧（入棧）：數(shù)據(jù)存入。棧頂指針加1。出棧（退棧）：數(shù)據(jù)讀出，棧頂指針減1?？諚＃寒?dāng)棧中沒有元素時，稱棧為空棧。亦稱為后進(jìn)先出表（LIFO），亦稱下推表。結(jié)論：后進(jìn)先出（LastInFirstOut），簡稱為LIFO線性表。舉例1：家里吃飯的碗，通常在洗干凈后一個一個地落在一起存放，在使用時，若一個一個地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。舉例2：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時，將從最上面一層一層地拿取。因此，棧結(jié)構(gòu)的基本操作有以下五種：（1）初始化棧InitStack(S)（2）入棧Push(S,item)：將參數(shù)item中數(shù)據(jù)元素入棧S（3）出棧Pop(S,item)（4）獲取棧頂元素內(nèi)容GetTop(S,item)（5）判斷棧是否為空StackEmpty(S)3.1.2棧的順序存儲棧的順序存儲結(jié)構(gòu)是用一組連續(xù)的存儲單元依次存放棧中的每個數(shù)據(jù)元素，并用起始端作為棧底；用一個變量來指示當(dāng)前的棧頂位置。因此，棧的順序存儲的類型定義如下所示：#defineMAX_STACK10//棧的最大數(shù)據(jù)元素?cái)?shù)目typedefstructstack{StackEntryitem[MAX_STACK];//存放棧中數(shù)據(jù)元素的存儲單元inttop;//棧頂指針}STACK;棧的動態(tài)示意：上溢（滿棧時進(jìn)行入棧運(yùn)算）與下溢（空棧時進(jìn)行出棧運(yùn)算）問題。3.1.3棧的鏈?zhǔn)酱鎯θ羰菞Ｖ性氐臄?shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。人們將用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的棧稱作“鏈棧”。鏈棧通常用一個無頭結(jié)點(diǎn)的單鏈表表示。由于棧的插入刪除操作只能在一端進(jìn)行，而對于單鏈表來說，在首端插入刪除結(jié)點(diǎn)要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)在C語言中可用下列類型定義實(shí)現(xiàn)：typestructnode{//鏈棧的結(jié)點(diǎn)結(jié)構(gòu)StackEntryitem;//棧的數(shù)據(jù)元素類型structnode*next;//指向后繼結(jié)點(diǎn)的指針}NODE;typedefstructstack{NODE*top;}STACK;3.1.4棧的應(yīng)用舉例【舉例1】將從鍵盤輸入的字符序列逆置輸出比如，從鍵盤上輸入：tsetasisihT；算法將輸出：Thisisatest下面我們給出解決這個問題的完整算法。 typedefcharStackEntry; voidReverseRead() { STACKS;//定義一個棧結(jié)構(gòu)S charch; InitStack(&S);//初始化棧 while((ch=getchar())!=’\n’) //從鍵盤輸入字符，直到輸入換行符為止 Push(&S,ch);//將輸入的每個字符入棧 while(!StackEmpty(S)){ //依次退棧并輸出退出的字符 Pop(&S,&ch); putchar(ch); } putchar(‘\n’); }【舉例2】十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制使用展轉(zhuǎn)相除法將一個十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)；重復(fù)此操作，直到該十進(jìn)制數(shù)值為0為止。最后將所有的余數(shù)反向輸出就是所對應(yīng)的二進(jìn)制數(shù)值。比如：(692)10=(1010110100)2?！九e例3】檢驗(yàn)表達(dá)式中的括號匹配情況假設(shè)在一個算術(shù)表達(dá)式中，可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”和花括號“{”和“}”，并且這三種括號可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。現(xiàn)在需要設(shè)計(jì)一個算法，用來檢驗(yàn)在輸入的算術(shù)表達(dá)式中所使用括號的合法性。算術(shù)表達(dá)式中各種括號的使用規(guī)則為：出現(xiàn)左括號，必有相應(yīng)的右括號與之匹配，并且每對括號之間可以嵌套，但不能出現(xiàn)交叉情況。檢驗(yàn)括號是否匹配的方法可用“期待的急迫程度”這個概念描述。而這個處理過程恰與棧的特點(diǎn)相吻合。由此，在算法中設(shè)置一個棧。我們可以利用一個棧結(jié)構(gòu)保存每個出現(xiàn)的左括號，當(dāng)遇到右括號時，從棧中彈出左括號，檢驗(yàn)匹配情況。在檢驗(yàn)過程中，若遇到以下幾種情況之一，就可以得出括號不匹配的結(jié)論。（1）當(dāng)遇到某一個右括號時，棧已空，說明到目前為止，右括號多于左括號；（2）從棧中彈出的左括號與當(dāng)前檢驗(yàn)的右括號類型不同，說明出現(xiàn)了括號交叉情況；（3）算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。因此，在算法的開始和結(jié)束時，棧都應(yīng)該是空的。P53-54:解決這個問題的完整算法。第四講課題名稱：第二章棧和隊(duì)列 第3節(jié)隊(duì)列 第4節(jié)隊(duì)列的應(yīng)用舉例教學(xué)目標(biāo)： 1、使學(xué)生了解隊(duì)列的表示和實(shí)現(xiàn)； 2、使學(xué)生了解隊(duì)列的應(yīng)用。教學(xué)重點(diǎn)和難點(diǎn)：隊(duì)列的理解主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：第三節(jié)3.3.1隊(duì)列的定義隊(duì)列特殊性在于限定插入在線性表的一端進(jìn)行，刪除在線性表的另外一端進(jìn)行。如圖所示： 隊(duì)頭 隊(duì)尾3.3出隊(duì)：隊(duì)頭，刪除端，前端，front，front+1入隊(duì)：隊(duì)尾，插入端，后端，rear，rear+1插入端和刪除端都是浮動的。通常我們將插入端稱為隊(duì)尾，用一個“隊(duì)尾指針”rear指示；而刪除端被稱為隊(duì)頭，用一個“隊(duì)頭指針”front指示。結(jié)論：先進(jìn)先出（FirstInFirstOut），簡稱為FIFO線性表。舉例1：到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。舉例2：乘坐公共汽車，應(yīng)該在車站排隊(duì)，車來后，按順序上車。舉例3：在Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個應(yīng)用程序響應(yīng)一系列的“消息”，像用戶點(diǎn)擊鼠標(biāo)；拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個應(yīng)用程序創(chuàng)建一個隊(duì)列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過程就是不斷地從隊(duì)列中讀取消息，并依次給予響應(yīng)。下面我們給出隊(duì)列結(jié)構(gòu)的基本操作：（1）初始化隊(duì)列InitQueue(Q)（2）入隊(duì)EnQueue(Q,e):rear+1（3）出隊(duì)DeQueue(Q,e):front+1（4）獲取隊(duì)頭元素內(nèi)容GetHead(Q,e)（5）判斷隊(duì)列是否為空QueueEmpty(Q)其他基本操作參看P46-473.3.3隊(duì)列的鏈?zhǔn)酱鎯υ谟面準(zhǔn)酱鎯Y(jié)構(gòu)表示隊(duì)列時，需要設(shè)置隊(duì)頭指針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。為了操作方便，我們也給隊(duì)列添加一個頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)。由此，空的鏈隊(duì)列的判決條件為頭指針和尾指針均指向頭結(jié)點(diǎn)。下面是在C語言中，實(shí)現(xiàn)隊(duì)列鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義：typestructnode{//鏈?zhǔn)疥?duì)列的結(jié)點(diǎn)結(jié)構(gòu)QElemTypedata;//隊(duì)列的數(shù)據(jù)元素類型structQNode*next;//指向后繼結(jié)點(diǎn)的指針}Qnode,*QueuePtr;typedefstructqueue{//鏈?zhǔn)疥?duì)列QueuePtr*front;//隊(duì)頭指針QueuePtr*rear;//隊(duì)尾指針}LinkQueue;假設(shè)將要入隊(duì)的新結(jié)點(diǎn)s已被創(chuàng)建。入隊(duì)需要執(zhí)行下面三條語句：s->next=NULL;//\新結(jié)點(diǎn)s的next域?yàn)榭誶ear->next=s;//原尾指針指向的結(jié)點(diǎn)的next域指向srear=s;//尾指針指向s下面我們給出鏈?zhǔn)疥?duì)列的基本操作算法。（1）初始化隊(duì)列Q：創(chuàng)建頭結(jié)點(diǎn)并將頭指針與尾指針指向該結(jié)點(diǎn)voidInitQueue(LinkQueue*Q){Q->front=(QNode*)malloc(sizeof(QNode));if(Q->front==NULL)exit(ERROR);Q->rear=Q->front;Q.front.->next=NULL;}（2）入隊(duì)voidEnQueue(LinkQueue*Q,QElemTypee){s=(QNode*)malloc(sizeof(QNode));if(!s)exit(ERROR);s->data=e;//以上三句為創(chuàng)建新結(jié)點(diǎn)ss->next=NULL;Q->rear->next=s;Q->rear=s;//以上三句為s入列操作}（3）出隊(duì)voidDeQueue(LinkQueue*Q,QElemType*e){if(QueueEmpty(*Q))exit(ERROR);else{*e=Q->front->next->data;s=Q->front->next;Q->front->next=s->next;//修改指針free(s);}}（4）獲取隊(duì)頭元素內(nèi)容voidGetHead(LinkQueueQ,QElemType*e){if(QueueEmpty(Q))exit(ERROR);else*e=Q->front->next->data;}（5）判斷隊(duì)列Q是否為空intQueueEmpty(LinkQueueQ){if(Q->front==Q->rear)returnTRUE；elsereturnFALSE;}3.3.4隊(duì)列的順序存儲和順序棧類似，在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個指針front和rear分別指示隊(duì)列頭元素和尾元素的位置。隊(duì)列的順序存儲結(jié)構(gòu)如下圖所示：問題1：當(dāng)隊(duì)空時，隊(duì)頭和隊(duì)尾指針都為-1，隊(duì)列將處于下圖所示的狀態(tài)：此時若進(jìn)行入隊(duì)操作，就需要讓隊(duì)頭和隊(duì)尾指針都增1，再將新數(shù)據(jù)元素放入該位置。也就是說，這樣設(shè)置隊(duì)頭、隊(duì)尾指針位置，在進(jìn)行入隊(duì)操作時，空隊(duì)與非空隊(duì)狀態(tài)所需要執(zhí)行的操作不完全一樣。解決方法：在算法中，需要對這兩種情況加以區(qū)分，這勢必增加了算法的復(fù)雜性。因此，人們設(shè)想了一種解決方法，即讓隊(duì)頭指針指向隊(duì)列真正隊(duì)頭元素的前一個位置，如下圖所示。問題2：由于順序存儲結(jié)構(gòu)的存儲空間屬于靜態(tài)分配，所以，在添加數(shù)據(jù)元素時，可能會出現(xiàn)沒有剩余單元的情況。對于隊(duì)列來說，這一點(diǎn)又有它的特殊性。如下圖所示的隊(duì)列。 即所謂“假溢出”現(xiàn)象。解決方法：將存儲隊(duì)列元素的一維數(shù)組首尾相接，形成一個環(huán)狀。我們將這種形式表示的隊(duì)列稱之為循環(huán)隊(duì)列。假設(shè)為隊(duì)列開辟的數(shù)組單元數(shù)目為MAX_QUEUE，在C語言中，它的下標(biāo)在0~MAX_QUEUE-1之間，若增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算（一個整數(shù)數(shù)值整除以另一個整數(shù)數(shù)值的余數(shù)）實(shí)現(xiàn)。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；當(dāng)front或rear為MAXQUEUE-1時，上述兩個公式計(jì)算的結(jié)果就為0。這樣，就使得指針自動由后面轉(zhuǎn)到前面，形成循環(huán)的效果。各項(xiàng)基本操作算法。（1）初始化隊(duì)列QvoidInitQueue(QUEUE*Q){Q.base=(QElemType*)malloc(MAX_QUEUE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q->front=-1;Q->rear=-1;}（2）入隊(duì)溢出判斷voidEnQueue(QUEUE*Q,QElemTypee){if((Q->rear+1)%MAX_QUEUE==Q->front)exit(OVERFLOW);else{Q->rear=(Q->rear+1)%MAX_QUEUE;Q.base[Q->rear]=e;}}3）出隊(duì)voidDeQueue(QUEUE*Q,QElemType*e){if(QueueEmpty(*Q))exit(“Queueisempty.”);else{Q->front=(Q->front+1)%MAX_QUEUE;*e=Q.base[Q->front];}}（4）獲取隊(duì)頭元素內(nèi)容voidGetFront(QUEUEQ,QElemType*e){if(QueueEmpty(Q))exit(“Queueisempty.”);else*e=Q.base[(Q.front+1)%MAX_QUEUE];}（5）判斷隊(duì)列Q是否為空intQueueEmpty(QueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}第四節(jié)【舉例1】汽車加油站。隨著城市里汽車數(shù)量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結(jié)構(gòu)基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經(jīng)過三段路程，第一段是在入口處排隊(duì)等候進(jìn)入加油車道；第二段是在加油車道排隊(duì)等候加油；第三段是進(jìn)入出口處排隊(duì)等候離開。實(shí)際上，這三段都是隊(duì)列結(jié)構(gòu)。若用算法模擬這個過程，就需要設(shè)置加油車道隊(duì)列3個和2個出口車道和入口車道隊(duì)列。【舉例2】模擬打印機(jī)緩沖區(qū)。在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時，會出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時主機(jī)就要停下來等待打印機(jī)。顯然，這樣會降低主機(jī)的使用效率。為此人們設(shè)想了一種辦法：為打印機(jī)設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，當(dāng)主機(jī)需要打印數(shù)據(jù)時，先將數(shù)據(jù)依次寫入這個緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)實(shí)際上就是一個隊(duì)列結(jié)構(gòu)。【舉例3】CPU分時系統(tǒng)在一個帶有多個終端的計(jì)算機(jī)系統(tǒng)中，同時有多個用戶需要使用CPU運(yùn)行各自的應(yīng)用程序，它們分別通過各自的終端向操作系統(tǒng)提出使用CPU的請求，操作系統(tǒng)通常按照每個請求在時間上的先后順序，將它們排成一個隊(duì)列，每次把CPU分配給當(dāng)前隊(duì)首的請求用戶，即將該用戶的應(yīng)用程序投入運(yùn)行，當(dāng)該程序運(yùn)行完畢或用完規(guī)定的時間片后，操作系統(tǒng)再將CPU分配給新的隊(duì)首請求用戶，這樣即可以滿足每個用戶的請求，又可以使CPU正常工作?！九e例4】農(nóng)夫過河問題一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問題是他只有一條小船，船小到只能容下他和一件物品，另外，只有農(nóng)夫能撐船。顯然：狼吃羊，羊吃白菜，狼不吃白菜。請問：農(nóng)夫采取什么方案才能將所有的東西運(yùn)過河呢？求解這個問題的最簡單的方法是一步步進(jìn)行試探，每一步都搜索所有可能的選擇，對前一步合適的選擇再考慮下一步的各種方案。用計(jì)算機(jī)實(shí)現(xiàn)上述求解的搜索過程可以采用兩種不同的策略。一種是廣度優(yōu)先搜索：依賴的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。一種是深度優(yōu)先搜索：依賴的數(shù)據(jù)結(jié)構(gòu)是棧。廣度優(yōu)先的含義是：在搜索過程中，總是首先搜索下面一步的所有可能狀態(tài)，然后再進(jìn)一步考慮更后面的各種情況。搜索到的下面一步的所有可能狀態(tài)，放在隊(duì)列里，然后順序取出來對其分別進(jìn)行處理，處理過程中再把下一步的狀態(tài)放在隊(duì)列里……。由于先進(jìn)先出原則，前一步情況處理完后，才開始后面一步各情況的處理。下面是具體解決方案。首先選擇一個對問題中每個角色的位置進(jìn)行描述的方法。用四位二進(jìn)制數(shù)分別順序表示農(nóng)夫、狼、白菜、羊的位置：0表示在南岸；1表示在北岸。如：0101表示農(nóng)夫和白菜在南岸，狼和羊在北岸。此時是否為一安全狀態(tài)？農(nóng)夫過河問題即為從0000到1111狀態(tài)的動作序列問題。下圖標(biāo)出了送入隊(duì)列的各個狀態(tài)（位置分布）和搜索過程中經(jīng)歷結(jié)點(diǎn)的順序編號。請注意廣度優(yōu)先搜索法在面臨多個選擇時采用怎樣的訪問順序。即從初始狀態(tài)0到最終狀態(tài)15的動作序列為：農(nóng)夫把羊帶到北岸；農(nóng)夫獨(dú)自回到南岸；農(nóng)夫把白菜帶到北岸；農(nóng)夫帶羊返回南岸；農(nóng)夫把狼帶到北岸；農(nóng)夫獨(dú)自返回南岸；農(nóng)夫把羊帶到北岸。【舉例5】離散事件模擬假設(shè)某銀行有四個窗口對外接待客戶。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多時需在每個窗口前順次排隊(duì)，對于剛進(jìn)入銀行的客戶，如果某個窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)，反之，若四個窗口均有客戶，他會排在人數(shù)最少的隊(duì)伍后面。現(xiàn)在需要編制一個程序以模擬銀行的這種業(yè)務(wù)活動并計(jì)算一天中客戶在銀行逗留的平均時間。逗留：指到達(dá)與離開的時間差。逗留的平均時間=所有客戶逗留時間總和/客戶數(shù)。事件：稱客戶到達(dá)銀行和離開銀行這兩個時刻發(fā)生的事情為“事件”。（到達(dá)事件、離開事件）整個模擬程序?qū)词录l(fā)生的先后順序進(jìn)行處理，這樣一種模擬程序稱做事件驅(qū)動模擬。下面討論模擬程序的實(shí)現(xiàn)。首先討論模擬程序中需要的數(shù)據(jù)結(jié)構(gòu)及其操作。1、處理的主要對象是“事件”。事件主要信息是事件類型和事件發(fā)生的時刻?？蛻舻竭_(dá)事件：隨客戶到來自然形成客戶離開事件：客戶事務(wù)所需時間與等待時間決定由于程序驅(qū)動是按事件發(fā)生時刻的先后順序進(jìn)行，則事件表應(yīng)是有序表，其主要操作是插入和刪除事件。2、模擬程序中需要的另一種數(shù)據(jù)結(jié)構(gòu)是表示客戶排隊(duì)的隊(duì)列。四個窗口à四個隊(duì)列。隊(duì)列中有關(guān)客戶的主要信息是客戶到達(dá)的時刻和客戶辦理事務(wù)所需時間。每個隊(duì)列中的頭客戶即為正在窗口辦理事務(wù)的客戶。（而每個頭客戶都存在一個將要驅(qū)動的客戶離開事件。）因此，在任何時刻即將發(fā)生的事件只有下列五種可能：新的客戶到達(dá)；1號窗口客戶離開；2號窗口客戶離開；3號窗口客戶離開；4號窗口客戶離開。從以上分析，這個模擬程序只需要兩種數(shù)據(jù)結(jié)構(gòu)：有序鏈表和隊(duì)列。有序鏈表用于表達(dá)事件；隊(duì)列用于表達(dá)客戶排隊(duì)狀態(tài)。3、兩個主要操作步驟的實(shí)現(xiàn)：（1）新客戶到達(dá)事件的處理。在實(shí)際的銀行中，客戶到達(dá)的時刻及其辦理事務(wù)所需時間都是隨機(jī)的，在模擬程序中可用隨機(jī)數(shù)來代替。隨機(jī)數(shù)：其一為此時刻到達(dá)的客戶辦理事務(wù)所需時間durtime；其二為下一客戶將到達(dá)的時間間隔intertime。（則下一客戶到達(dá)時刻為occurtime+intertime）。所以：應(yīng)產(chǎn)生一個新的客戶到達(dá)事件插入事件表；剛到達(dá)的客戶則應(yīng)插入到當(dāng)前所含元素最少的隊(duì)列中；若該隊(duì)列在插入前為空，則還產(chǎn)生一個客戶離開事件插入事件表。（2）客戶離開事件的處理：首先計(jì)算該客戶在銀行逗留的時間；然后從隊(duì)列中刪除該客戶后查看隊(duì)列是否為空；若不空，則設(shè)定一個新的隊(duì)頭客戶離開事件。第五講課題名稱：第三章串 第1節(jié)串的邏輯結(jié)構(gòu) 第2節(jié)串的表示和實(shí)現(xiàn)教學(xué)目標(biāo)： 1、使學(xué)生了解串的概念； 2、使學(xué)生了解串的表示和實(shí)現(xiàn)。教學(xué)重點(diǎn)和難點(diǎn)：串的理解主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：第一節(jié)3.1.1串是由零個或多個字符組成的有限序列。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個有窮字符序列。串一般記作：s=‘a(chǎn)1a2...an’(n30)其中，s是串的名稱，用單引號或雙引號括起來的字符序列是串的值；ai可以是字母、數(shù)字或其他字符；串中字符的數(shù)目n被稱作串的長度。當(dāng)n=0時，串中沒有任何字符，其串的長度為0，通常被稱為空串?。如：s1=‘’而：s2=‘’與之不同。s1中沒有字符，是一個空串；而s2中有兩個空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串。相關(guān)概念：子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。例如，有下列四個串a(chǎn)，b，c，d：a=“WelcometoBeijing”b=“Welcome”c=“Bei”d=“welcometo”?子串的位置：子串在主串中第一次出現(xiàn)的第一個字符的位置。兩個串相等：兩個串的長度相等，并且各個對應(yīng)的字符也都相同。例如，有下列四個串a(chǎn)，b，c，d：a=“program”b=“Program”c=“pro”d=“program”串的邏輯結(jié)構(gòu)與線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。即串中的每一個數(shù)據(jù)元素僅由一個字符組成。然而，串的基本操作和線性表有很大區(qū)別。線性表的操作大多以“單個元素”作為操作對象。如：在線性表中查找某個元素、求取某個數(shù)據(jù)元素、在某個位置上插入一個元素和刪除一個元素…………串的基本操作通常以“串的整體”作為操作對象。如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串…………4.1.2串的基本操作：（1）創(chuàng)建串StrAssign(T,chars)：串賦值。即創(chuàng)建串T，并將chars的內(nèi)容賦予它。即生成一個值等于chars的串T。（2）判斷串是否為空StrEmpty(S)（3）計(jì)算串長度StrLength(S)（4）串連接Concat(T，S1，S2)：將串S2接在串S1后構(gòu)成一個新串T（5）求子串SubString(sub,S,pos,len)：將串S中從第pos個字符開始的連續(xù)len個字符組成的新子串賦給sub串。（6）串的定位Index(S,T)：即求串T在S中位置?！按哪Ｊ狡ヅ洹盨稱為主串；T稱為子串或模式串。（7）串復(fù)制strCopy(T,S)：串S存在，復(fù)制得串T。（8）串比較StrCompare(S,T):如果S>T則返回值>0；如果S=T則返回值=0；如果S<T則返回值<0。（9）串清空ClearString(S)：將串清空為空串。（10）串銷毀DestroyString(s):與串清除之區(qū)別。以上五種黃色字體操作為串類型的最小操作子集。即：這些操作不可能利用其他串操作來實(shí)現(xiàn)，但是其他串操作均可在這個最小操作子集上實(shí)現(xiàn)。（串清除與串銷毀除外）如：將s2串插入到串s1的第i個字符后面。SubString(s3,s1,1,i);SubString(s4,s1,i+1,Length(s1)-i);Concat(s3,s2);Concat(s3,s4);StrAssign(s1,s3);再如：刪除串s中第i個字符開始的連續(xù)j個字符。SubString(s1,s,1,i-1);SubString(s2,s,i+j,Length(s)-i-j+1);Concat(s1,s2);StrAssign(s,s1);再如：Index(s1，s2，pos)串的定位函數(shù)的實(shí)現(xiàn)?？衫门械龋ù容^）、求串長和求子串等操作實(shí)現(xiàn)之。算法的基本思想是：在主串s1中取從第i（i的初值為pos）個字符起、長度和串s2相等的子串和串s2比較；若相等，則求得函數(shù)值為i，否則i值增1直至串s1中不存在和串s2相等的子串為止。作業(yè)：P764.44.54.6第二節(jié)4.2.1順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)與線性表的順序存儲類似，用一組連續(xù)的存儲單元依次存儲串中的字符序列。在C語言中，有兩種實(shí)現(xiàn)方式：1.第一種稱為“定長順序存儲結(jié)構(gòu)”是事先定義字符串的最大長度，字符串存儲在一個定長的存儲區(qū)中。類型定義如下所示：#defineMAX_STRING255//用戶可在255以內(nèi)定義最大串長typedefunsignedcharSString[MAX_STRING];//0號單元存放串的長度，字符從1號單元開始存放說明：1、串的實(shí)際長度可在這予定義長度的范圍內(nèi)隨意。超過予定義長度的串值則被舍去，稱之為“截?cái)唷薄?、對串長有兩種表示方法：（1）如上述定義描述的一樣，以下標(biāo)為0的數(shù)組分量存放串的實(shí)際長度。（2）在串值后面加一個不計(jì)入串長的結(jié)束標(biāo)記字符。如\0。此時的串長為隱含值，顯然不便于進(jìn)行某些串操作。在這種存儲結(jié)構(gòu)表示時如何實(shí)現(xiàn)串的操作。下面以串聯(lián)接和求子串為例討論之。1、串聯(lián)接Concat(s1,s2)聯(lián)接后串s1的值的后一段和串s2的值相等，則只要進(jìn)行相應(yīng)的“串值復(fù)制”操作即可，只是需按前述約定，對超長部分實(shí)施“截?cái)唷辈僮鳌；诖畇1和串s2長度的不同情況，串值的產(chǎn)生可能有以下三種情況：(1)s1[0]+s2[0]<=MAX_STRING得到的新串是正確的結(jié)果。(2)s1[0]<MAX_STRING而s1[0]+s2[0]>MAX_STRING則將串s2的一部分截?cái)?，得到的串只是包含s2的一個子串。(3)s1[0]=MAX_STRING則得到的串并非聯(lián)接結(jié)果。算法見P63-64。2、求子串SubString(s1,s2,start,len)求子串的過程即為復(fù)制字符序列的過程，將串s2中從第start個字符開始長度為len的字符序列復(fù)制到串s1中。顯然，本操作不會有需截?cái)嗟那闆r，但是有可能產(chǎn)生用戶給出的參數(shù)不符合操作的初始條件，當(dāng)參數(shù)非法時，返回ERROR。算法見P64?？偨Y(jié)：1、綜上兩個操作可見，在順序存儲結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為“字符序列的復(fù)制”。2、另一操作特點(diǎn)是，如果在操作中出現(xiàn)串值序列的長度超過上界MAX_STRING時，約定用截尾法處理。這種情況不僅在求聯(lián)接串時可能發(fā)生，在串的其他操作中，如插入、置換等也可能發(fā)生?？朔@種弊端，唯有不限定串長的最大長度，即動態(tài)分配串值的存儲空間。2.第二種稱為“堆分配存儲”。是在程序執(zhí)行過程中，利用標(biāo)準(zhǔn)函數(shù)malloc和free動態(tài)地分配或釋放存儲字符串的存儲單元，并以一個特殊的字符作為字符串的結(jié)束標(biāo)志，它的好處在于：可以根據(jù)具體情況，靈活地申請適當(dāng)數(shù)目的存儲空間，從而提高存儲資源的利用率。類型定義如下所示：typedefstruct{char*ch;//若是非空串，則按串長分配存儲區(qū)，否則*ch為NULLintlength;//串長度}HString;這種存儲結(jié)構(gòu)表示時的串操作仍是基于“字符序列的復(fù)制”進(jìn)行的。如：串復(fù)制StrCopy(&T,S)：若串T已存在，則先釋放串T所占空間，當(dāng)串S不空時，首先為串T分配大小和串S長度相等的存儲空間，然后將串S的值復(fù)制到串T中。串插入StrInsert(&S,pos,T)：為串S重新分配大小等于串S和串T長度之和的存儲空間，然后進(jìn)行串值復(fù)制。不同的定義形式，算法中的處理也略有不同。下面我們給出在堆分配存儲方式下串的幾個基本操作的算法。（1）串的賦值StatusStrAssign(HString*s,char*chars){if(s->ch)free(s->ch);//若s已經(jīng)存在，將它占據(jù)的空間釋放掉for(len=0,c=chars;ch;len++,c++);//求chars串的長度if(!len){//空串s->ch=(char*)malloc(sizeof(char));s->ch[0]=’\0’;s->length=0;}else{s->ch=(char*)malloc((len+1)*sizeof(char));//分配空間if(!s->ch)returnERROR;s->ch[0..len]=chars[0..len];//對應(yīng)的字符賦值,包括串結(jié)束標(biāo)志s->length=len;//賦予字符串長度}returnOK;}2）判斷串是否為空intStrEmpty(HStrings){if(!s.length)returnTRUE;elsereturnFALSE;}（3）求串的長度intStrLength(HStrings){returns.length;}4）串連接intConcat(HString*s1,HString*s2){HStrings;StrAssign(&s,s1->ch);//將s1原來的內(nèi)容保留在s中l(wèi)en=StrLength(s1)+StrLength(s2);//計(jì)算s1和s2的長度之和free(s1->ch);//釋放s1原來占據(jù)的空間s1->ch=(char*)malloc((len+1)*sizeof(char));//重新為s1分配空間if(!s1)returnERROR;else{//連接兩個串的內(nèi)容s1->ch[0..StrLength(s)-1]=s->ch[0..StrLength(s)-1)];s1->ch[StrLength(s)..len+1]=s2->ch[0..StrLength(s2)];s1->length=len;free(s->ch);//釋放為臨時串s分配的空間returnOK;}}（5）求子串StatusSubString(HString*s1,HString*s2,intstart,intlen){len2=StrLength(s2);//計(jì)算s2的長度if(start<1||start>len2||len2<=0||len>len2-start+1){//判斷start和len的合理性，如果不合理則返回空串s1s1->ch=(char*)malloc(sizoef(char));s1->ch[0]=’\0’;s1->length=0;returnERROR;}s1->ch=(char*)malloc((len+1)*sizeof(char));if(!s1.ch)returnERROR;s1->ch[0..len-1]=s2.ch[start-1..start+len-2];s1->ch[len]=’\0’;//串尾s1->length=len;returnOK;}（6）串的定位**(串的模式匹配，即求子串s2中s1中的位置）intIndex(HStrings1,HStrings2){len1=StrLength(s1);len2=StrLength(s2);//計(jì)算s1和s2的長度i=0;j=0;//設(shè)置兩個掃描指針while(i<len1&&j<len2){if(s1.ch[i]==s2.ch[j]){i++;j++;}else{i=i-j+1;j=0;}//對應(yīng)字符不相等時，重新比較}if(j==len2)returni-len2+1;//找到s2在s1中的位置elsereturn0;}//P72圖4.24.2.2鏈?zhǔn)酱鎯Y(jié)構(gòu)由于串結(jié)構(gòu)中每個數(shù)據(jù)元素為一個字符，所以最直接的鏈?zhǔn)酱鎯Y(jié)構(gòu)是每個結(jié)點(diǎn)的數(shù)據(jù)域存放一個字符。優(yōu)點(diǎn)是操作方便；不足之處是存儲密度較低。所謂存儲密度為： 由于串中的字符個數(shù)不一定是每個結(jié)點(diǎn)存放字符個數(shù)的整倍數(shù)，所以，需要在最后一個結(jié)點(diǎn)的空缺位置上填充特殊的字符。這種存儲形式優(yōu)點(diǎn)是存儲密度高于結(jié)點(diǎn)大小為1的存儲形式；不足之處是做插入、刪除字符的操作時，可能會引起結(jié)點(diǎn)之間字符的移動，算法實(shí)現(xiàn)起來比較復(fù)雜。P68塊鏈存儲的類型定義。作業(yè)：P774.74.8第五講課題名稱：第四章數(shù)組和廣義表 第1節(jié)數(shù)組的定義數(shù)組的順序表示和實(shí)現(xiàn)矩陣的壓縮存儲教學(xué)目標(biāo)： 1、使學(xué)生了解數(shù)組和矩陣的概念； 2、使學(xué)生了解數(shù)組和矩陣的表示和實(shí)現(xiàn)。教學(xué)重點(diǎn)和難點(diǎn)：數(shù)組的理解主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：第一節(jié)4.1數(shù)組的定義1、數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，它可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。2、由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是一維數(shù)組的推廣。例如，二維數(shù)組A：AAm×n=a11a12…aa21a22…a…………am1am2…amn3、二維數(shù)組A可以看成是由m個行向量組成的向量，也可以看成是n個列向量組成的向量。4、數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。第二節(jié)4．2.1數(shù)組順序存放原因1、由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。2、數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般采用順序存儲的方法來表示數(shù)組。4.2.2數(shù)組存放1、行優(yōu)先順序或以行為主序存儲方式：將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C等語言中，數(shù)組就是按行優(yōu)先順序存儲的。AAm×n=a11a12…aa21a22…a…………am1am2…amn2、行優(yōu)先順序——先排最右的下標(biāo)，從右到左，最后排最左下標(biāo)。列優(yōu)先順序——先排最左下標(biāo)，從右向左，最后排最左下標(biāo)。例如：三維數(shù)組Am*n*p以行優(yōu)先方式順序存儲，則LOC(aijk)=LOC(a111)+[(i-1)*m*n+(j-1)*n+(k-1)]*d4.2.3數(shù)組存儲的特點(diǎn)只要知道開始結(jié)點(diǎn)的存放地址（即基地址）、維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時間內(nèi)存取，即順序存儲的數(shù)組是一個隨機(jī)存取結(jié)構(gòu)。第三節(jié)4.3.1相關(guān)概念1、壓縮存儲：為多個值相同的非零元素只分配一個存儲空間；對零元素不分配空間。2、特殊矩陣：非零元素按照一定的規(guī)律分布。常見的特殊矩陣有對稱矩陣、三角矩陣、對角矩陣等。對稱矩陣：元素的值按照主對角線對稱a1a1,1a1,2…a1,a2,1a2,2…a2,……ai,j…an,1an,2…an,naij=aji12341234213433144441對稱矩陣3、三角矩陣：上(下)三角矩陣是指矩陣的下（上）三角（不包括對角線）中的元素均為常數(shù)或零的n階矩陣，即非零元素的分布在矩陣中呈現(xiàn)為三角形。例如：一個4*4的三角矩陣。188818882188331844411234912349134991499914、上述各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一維數(shù)組中，并且一般都能找到矩陣中的元素與該一維數(shù)組元素的對應(yīng)關(guān)系，通過這個關(guān)系，仍能對矩陣的元素進(jìn)行隨機(jī)存取。4.3.2稀疏矩陣定義：簡單說，設(shè)矩陣A中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。設(shè)在矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認(rèn)為e≤0.05時稱之為稀疏矩陣。2、存儲：在存儲稀疏矩陣時，由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組(i,j,aij)惟一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元組順序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triple;/*三元組*/typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;第六講課題名稱：第四章數(shù)組和廣義表 第4節(jié)廣義表的定義 第5節(jié)廣義表的存儲結(jié)構(gòu)教學(xué)目標(biāo)： 1、使學(xué)生了解廣義表的概念； 2、使學(xué)生掌握廣義表的存儲結(jié)構(gòu)。教學(xué)重點(diǎn)和難點(diǎn)：、廣義表的應(yīng)用主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：第一節(jié)4.4廣義表是線性表的推廣L=(a1,a2,...,an),n≥0,ai可以是單元素，也可以是一個表。例如：A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)廣義表的長度廣義表的深度非空廣義表表頭(Head)：第一個元素表尾(Tail)：除第一個元素外其余元素構(gòu)成的表鏈表存儲C=(a,(b,c,d))D=(A,B,C)E=(a,E)第二節(jié)m元多項(xiàng)式的表示P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15=Az2+Bz+15A(x,y)=x10y3+2x6y3+3x5y2=(x10+2x6)y3+3x5y2=Cy3+Dy2B(x,y)=x4y4+6x3y4+2y=(x4+6x3)y4+2y=Ey4+Fy

第七講課題名稱：第六章樹和二叉樹第1節(jié)樹的定義和基本術(shù)語第2節(jié)二叉樹教學(xué)目標(biāo)： 1、使學(xué)生了解樹的定義和基本術(shù)語等主要內(nèi)容； 2、使學(xué)生了解二叉樹的存儲結(jié)構(gòu)。教學(xué)重點(diǎn)和難點(diǎn)：二叉樹的定義、基本運(yùn)算以及存儲結(jié)構(gòu)。主要教學(xué)方法和手段：多媒體課件講授教學(xué)課時：2課時課的類型：講授課教學(xué)內(nèi)容：第一節(jié)樹的定義和基本術(shù)語1、樹：是n（n≥0）個結(jié)點(diǎn)的有限集。當(dāng)n=0時，稱為空樹；在任意一棵非空樹中滿足如下條件：(1)有且僅有一個特定的稱為根（root）的結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個或多個直接后繼。(2)當(dāng)n>1時，其余n-1個結(jié)點(diǎn)可以劃分成m（m>0）個互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個直接前驅(qū)，但有零個或多個直接后繼。由此可以看出，樹的定義是遞歸。JJIACBDHGFEKLM2、樹的結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向子樹的分支；結(jié)點(diǎn)的度：節(jié)點(diǎn)擁有的子樹數(shù)（結(jié)點(diǎn)的孩子數(shù)目）；終端結(jié)點(diǎn)（葉子）：度為0的結(jié)點(diǎn)；非終端結(jié)點(diǎn)（分支結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)；結(jié)點(diǎn)的層次：樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹的根為第2層，以此類推；樹的度：樹中所有結(jié)點(diǎn)度的最大值；樹的深度：樹中所有結(jié)點(diǎn)層次的最大值；孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；父結(jié)點(diǎn)：B是A的孩子，則A是B的父親；兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；堂兄弟結(jié)點(diǎn)：其父結(jié)點(diǎn)在同一層上的結(jié)點(diǎn)；祖先結(jié)點(diǎn)：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。3、有序樹和無序樹：在樹中，如果各子樹Ti是按照一定的次序從左向右安排的，且相對次序是不能隨意改變的，則稱為有序樹，否則稱為無序樹。森林：m（m≥0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個森林；反之，給m棵獨(dú)立的樹增加一個根結(jié)點(diǎn)，并把這m棵樹作為該結(jié)點(diǎn)的子樹，森林就變成一棵樹。第二節(jié)二叉樹6.2.1二叉樹的定義二叉樹是由n(n>=0)個結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況。二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。二叉樹的5種基本形態(tài)其中：(c)和（d）是不同的兩棵二叉樹。(a)(a)空二叉樹AABABACB(b)只有根的二叉樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹二叉樹的5種基本形式6.2.2二叉樹的性質(zhì)1、性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)證明：用數(shù)學(xué)歸納法1)當(dāng)i=1時，整個二叉樹只有一根結(jié)點(diǎn)，此時2i-1=20=1，結(jié)論成立。2)設(shè)i=k時結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個?，F(xiàn)證明當(dāng)i=k+1時，結(jié)論成立：因?yàn)槎鏄渲忻總€結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即2×2k-1=2(k+1)-1，故結(jié)論成立。2、性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)證明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為深度為k的m叉樹至多有個結(jié)點(diǎn)。3、性質(zhì)3：任何一個二叉樹中度為2的結(jié)點(diǎn)數(shù)目(n2)比度為0的結(jié)點(diǎn)數(shù)目(n0)少1，即n2＝n0-1。證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)，設(shè)二叉樹中分支數(shù)目為B。①n=n0+n1+n2除根結(jié)點(diǎn)外，每個結(jié)點(diǎn)均對應(yīng)一個進(jìn)入它的分支：②n=B+1二叉樹中的分支都是由度為1和度為2的結(jié)點(diǎn)發(fā)出③B=n1+2n24、滿二叉樹深度為k且有2k-1個結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內(nèi)從左到右，逐層進(jìn)行編號（1，2，…，n）。高度為高度為3的滿二叉樹5、完全二叉樹深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1~n的位置序號分別與滿二叉樹的結(jié)點(diǎn)1~n的位置序號一一對應(yīng)，則為完全二叉樹，滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。6、性質(zhì)4：一個有n個結(jié)點(diǎn)的完全二叉樹的深度為?log2n?+1或élog2(n+1)ù證明：設(shè)n個結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)性質(zhì)2有2k-1-1＜n≤2k-1可得2k-1≤n＜2k，即k-1≤log2n＜k因?yàn)閗是整數(shù)，所以k-1=?log2n?，k=?log2n?+1,故結(jié)論成立。2k-1＜n+1≤2k→k-1＜log2(n+1)≤k→k=élog2(n+1)ù7、性質(zhì)5：完全二叉樹中的某結(jié)點(diǎn)編號為i，則1)若該結(jié)點(diǎn)有左孩子，則左孩編號為2i2）若該結(jié)點(diǎn)有右孩子，則右孩子結(jié)點(diǎn)編號為2i+13）若該結(jié)點(diǎn)有雙親，則雙親結(jié)點(diǎn)編號為?i/2?6.2.3.1二叉樹的順序存儲二叉樹的順序存儲指的是用元素在數(shù)組中的下標(biāo)表示一個結(jié)點(diǎn)與其孩子和父結(jié)點(diǎn)的關(guān)系.1、完全二叉樹的順序存儲EDEDCFABABCDEF123456789101112#defineMAX_TREE_SIZE100typedefTelemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;2、非完全二叉樹的順序存儲EEGFCDABABCDEFG12