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

軟件技術(shù)系課程名稱：數(shù)據(jù)結(jié)構(gòu)和算法文件編號：SJ1K-001版本號:1.0二〇一〇年四月六日教案2009年－2010學(xué)年第二學(xué)期課程名稱數(shù)據(jù)結(jié)構(gòu)和算法任課教師楊勇授課對象系別軟件技術(shù)系本次課學(xué)時2學(xué)時年級班次章節(jié)題目第一章數(shù)據(jù)結(jié)構(gòu)和算法概述目的要求(含技能要求)了解數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和掌握、算法的基本概念和性質(zhì)、算法的性能分析和評價本節(jié)重點數(shù)據(jù)結(jié)構(gòu)基本概念、算法基本概念、算法特性以及算法分析本節(jié)難點算法的時間復(fù)雜度分析教學(xué)方法講解+案例教學(xué)教學(xué)用具多媒體教室、機房問題引入從學(xué)生所了解的生活常識，引出數(shù)據(jù)結(jié)構(gòu)的不同類型。如從學(xué)生信息檢索系統(tǒng)數(shù)據(jù)庫中，學(xué)生信息表引出線性結(jié)構(gòu)；人機對弈引出樹形結(jié)構(gòu)；教學(xué)計劃安排問題引出圖形結(jié)構(gòu)。難點與重點講解方法采用講解+案例教學(xué)，講述數(shù)據(jù)結(jié)構(gòu)的基本概念以及相關(guān)的術(shù)語，算法的含義特征以及算法的分析評價方法。本次課小節(jié)課程小節(jié)1、數(shù)據(jù)結(jié)構(gòu)定義、相關(guān)術(shù)語2、算法的定義、要素、性質(zhì)3、算法及其復(fù)雜度分析教后札記1、什么是數(shù)據(jù)結(jié)構(gòu)2、什么是算法3、算法復(fù)雜度評定方法討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后：第一章數(shù)據(jù)結(jié)構(gòu)和算法概述【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）初步掌握數(shù)據(jù)結(jié)構(gòu)和算法的基本概念和應(yīng)用能力（2）算法時間復(fù)雜度分析的能力2．知識目標(biāo)：（1）數(shù)據(jù)結(jié)構(gòu)的概念和用語；（2）算法的定義，算法性質(zhì)、地位和特征；（3）算法分析與評價；3．職業(yè)素質(zhì)目標(biāo)：★算法時間復(fù)雜度分析邏輯思維能力★算法時間復(fù)雜度獨立思考應(yīng)用能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。能夠正確分析算法時間復(fù)雜度的能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。能夠正確、及時處理學(xué)生操作過程中出現(xiàn)的問題及錯誤?！局饕獌?nèi)容】1．了解數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語數(shù)據(jù)：計算機操作對象的總稱，它是計算機處理的符號的集合，集合中的個體為一個數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)：是由若干特性相同的數(shù)據(jù)元素構(gòu)成的集合，且在集合上存在一種或多種關(guān)系。由關(guān)系不同可將數(shù)據(jù)結(jié)構(gòu)分為四類：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合結(jié)構(gòu)。邏輯結(jié)構(gòu)：數(shù)據(jù)元素和數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。存儲結(jié)構(gòu)：數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)處理：數(shù)據(jù)處理是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。數(shù)據(jù)類型：數(shù)據(jù)類型是指程序設(shè)計語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設(shè)計語言中的一個基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。2．了解算法的概念、性質(zhì)、地位和特性算法：進(jìn)行程序設(shè)計的另一不可缺少的要素。算法是對問題求解的一種描述，是為解決一個或一類問題給出的一種確定規(guī)則的描述。一個完整的算法應(yīng)該具有下列五個要素：有窮性、確定性、可行性、有輸入和有輸出。一個正確的算法應(yīng)對苛刻且?guī)в械箅y性的輸入數(shù)據(jù)也能得出正確的結(jié)果，并且對不正確的輸入也能作出正確的反映。3．能夠?qū)唵蔚乃惴ㄟM(jìn)行時間復(fù)雜度的分析。評價一個算法的好壞，通常用時間復(fù)雜度和空間復(fù)雜度進(jìn)行評價。算法的時間復(fù)雜度：比較不同算法效率的一種準(zhǔn)則，算法時間復(fù)雜度的估算基于算法中基本操作的重復(fù)執(zhí)行次數(shù)，或處于最深層循環(huán)內(nèi)的語句的頻度。算法的時間復(fù)雜度：比較不同算法效率的一種準(zhǔn)則，算法時間復(fù)雜度的估算基于算法中基本操作的重復(fù)執(zhí)行次數(shù)，或處于最深層循環(huán)內(nèi)的語句的頻度。算法空間復(fù)雜度：可作為算法所需存儲量的一種量度，它主要取決于算法的輸入量和輔助變量所占空間，若算法的輸入僅取決于問題本身而和算法無關(guān)，則算法空間復(fù)雜度的估算只需考察算法中所用輔助變量所占空間，若算法的空間復(fù)雜度為常量級，則稱該算法為原地工作的算法?！緦W(xué)習(xí)方法】自主學(xué)習(xí)、教師講解、課后習(xí)題練習(xí)【教學(xué)方法】多媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】本門課程的總體安排和學(xué)習(xí)的要求：（10分鐘）數(shù)據(jù)結(jié)構(gòu)的概念和術(shù)語的講解：（20分鐘）算法的概念、要素和特征：（15分鐘）算法的分析和評價（包括：案例分析）：（40分鐘）本章小結(jié)和習(xí)題安排：（5分鐘）?！玖?xí)題要求】1、學(xué)生獨立完成，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次作業(yè)的成績，記錄學(xué)生期末總成績的2%【實驗要求】本章無上機實驗授課對象系別軟件技術(shù)系本次課學(xué)時4學(xué)時年級班次章節(jié)題目第二章學(xué)生信息管理系統(tǒng)設(shè)計目的要求(含技能要求)了解三層結(jié)構(gòu)進(jìn)行系統(tǒng)設(shè)計和開發(fā)的思想，并進(jìn)行通用模塊層類的封裝和實現(xiàn)。算法的基本概念和性質(zhì)算法的性能分析和評價本節(jié)重點簡易學(xué)生信息系統(tǒng)設(shè)計、數(shù)據(jù)庫設(shè)計、公用模塊設(shè)計本節(jié)難點公用模塊設(shè)計與實現(xiàn)教學(xué)方法講解+案例教學(xué)+任務(wù)驅(qū)動法，“教學(xué)做”三位一體法教學(xué)用具多媒體教室、機房問題引入從學(xué)生所熟悉的簡易學(xué)生信息管理系統(tǒng)的功能講解入手，進(jìn)行本課程教學(xué)的引入。難點與重點講解方法采用講解、案例教學(xué)以及模仿訓(xùn)練，講述公用模塊層類封裝和開發(fā)的要點。本次課小節(jié)課程小節(jié)學(xué)生分組、選取項目，以及簡要功能設(shè)計和數(shù)據(jù)庫設(shè)計。公用模塊層類的封裝和實現(xiàn)。教后札記初步能應(yīng)用三層結(jié)構(gòu)開發(fā)思想，進(jìn)行公用模塊層類的設(shè)計與開發(fā)。組建學(xué)生項目開發(fā)小組，為培養(yǎng)學(xué)生團(tuán)隊意識和后面的課程設(shè)計奠定基礎(chǔ)。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第二章學(xué)生信息管理設(shè)計【學(xué)習(xí)目標(biāo)】1.能力目標(biāo)：（1）簡單數(shù)據(jù)庫設(shè)計的能力（2）通用模塊類封裝的能力（3）與數(shù)據(jù)庫連接獲取的能力（4）制作主界面的能力2．知識目標(biāo)：（1）三層結(jié)構(gòu)的思想；（2）簡易學(xué)生信息管理系統(tǒng)模塊設(shè)計；（3）簡易學(xué)生信息管理系統(tǒng)數(shù)據(jù)庫設(shè)計。（4）簡易學(xué)生信息管理系統(tǒng)通用模塊層實現(xiàn)?！菊n前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。能夠正確分析算法時間復(fù)雜度的能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。能夠正確、及時處理學(xué)生操作過程中出現(xiàn)的問題及錯誤。【主要內(nèi)容】系統(tǒng)設(shè)計以簡易的學(xué)生信息管理系統(tǒng)的開發(fā)來講述數(shù)據(jù)結(jié)構(gòu)和算法。重在常用的數(shù)據(jù)結(jié)構(gòu)和算法的講解，通過項目實作和可視化界面來展現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法的結(jié)果。為了讓教師教學(xué)和學(xué)生自學(xué)帶來方便，在書中盡量使業(yè)務(wù)簡化，功能簡潔，突出數(shù)據(jù)結(jié)構(gòu)和算法的實踐。本書的功能結(jié)構(gòu)模塊圖如下：數(shù)據(jù)庫設(shè)計在本書中，主要目標(biāo)是進(jìn)行常用的數(shù)據(jù)結(jié)構(gòu)和算法的學(xué)習(xí)，為了使教師和學(xué)生不陷于復(fù)雜的業(yè)務(wù)處理中，我們只用一張學(xué)生信息表student_info來實現(xiàn)。其表結(jié)構(gòu)設(shè)計如下：字段名稱描述數(shù)據(jù)類型是否主鍵備注St_id學(xué)生idint主鍵自動增長St_name學(xué)生姓名Varchar(20)St_num學(xué)號Varchar(20)St_sex性別intSt_age年齡intSt_address家庭地址Varchaer(100)St_phone電話號碼intSt_banji班級編號intSt_yw_cj語文成績intSt_sx_cj數(shù)學(xué)成績intSt_yy_cj英語成績intSt_ty_cj體育成績intSt_zz_cj政治成績int公用模塊設(shè)計 在本書的后續(xù)各個模塊功能的實現(xiàn)，采用三層結(jié)構(gòu)的思想來進(jìn)行開發(fā)。即通用模塊層，業(yè)務(wù)層和表現(xiàn)層。在本書的第二部分業(yè)務(wù)層，主要是通過數(shù)據(jù)結(jié)構(gòu)和算法來講述學(xué)生信息管理系統(tǒng)的業(yè)務(wù)處理，第三部分表現(xiàn)層，通過調(diào)用業(yè)務(wù)層類的有關(guān)方法來展現(xiàn)相關(guān)的信息。 在本節(jié)講述通用模塊層的實現(xiàn),包括：學(xué)生信息實體類的實現(xiàn)，數(shù)據(jù)庫訪問類的實現(xiàn)、學(xué)生信息數(shù)據(jù)控制類的實現(xiàn)，具體如下：1）實體類實現(xiàn) 用以實現(xiàn)學(xué)生信息對象的封裝，主要內(nèi)容包括：與數(shù)據(jù)庫學(xué)信息表字段對應(yīng)的屬性和構(gòu)造函數(shù)的重載。2）數(shù)據(jù)庫訪問類實現(xiàn) 該類主要用以完成與數(shù)據(jù)庫的訪問，包括：與數(shù)據(jù)庫的連接，從數(shù)據(jù)庫中提取數(shù)據(jù)放入數(shù)據(jù)集中，將進(jìn)行改動的數(shù)據(jù)集保存到數(shù)據(jù)庫中，以及執(zhí)行給定標(biāo)準(zhǔn)的SQL語句。3）學(xué)生信息控制類的實現(xiàn)：該類主要實現(xiàn)的功能如下：將數(shù)據(jù)庫中的學(xué)生信息通過數(shù)據(jù)庫訪問對象的方法調(diào)用，放入數(shù)據(jù)集對象ds中。通過數(shù)據(jù)集對象ds為學(xué)生信息數(shù)組base_info分配空間，并對每個成員進(jìn)行初始化，為業(yè)務(wù)層提供學(xué)生信息的準(zhǔn)備。在業(yè)務(wù)層發(fā)生對學(xué)生信息進(jìn)行改動后，傳入新的學(xué)生信息數(shù)組，調(diào)用數(shù)據(jù)庫訪問層的方法，將學(xué)生信息更新到數(shù)據(jù)庫中去?！緦W(xué)習(xí)方法】自主學(xué)習(xí)、教師講解、課題模仿練習(xí)【教學(xué)方法】媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】學(xué)生信息管理系統(tǒng)設(shè)計和功能介紹：（10分鐘）學(xué)生信息管理系統(tǒng)數(shù)據(jù)庫設(shè)計介紹（5分鐘）學(xué)生分組，選定一個簡易項目，進(jìn)行數(shù)據(jù)庫設(shè)計（30分鐘）學(xué)生分組進(jìn)行數(shù)據(jù)庫實現(xiàn)，每個學(xué)生確定一個實體表（20分鐘）學(xué)生基本信息實體類的講解。（5分鐘）學(xué)生模仿學(xué)生基本信息實體類，進(jìn)行各自所設(shè)計的實體類的實現(xiàn)（20分鐘）數(shù)據(jù)庫訪問類封裝講解（15分鐘）學(xué)生模仿進(jìn)行數(shù)據(jù)庫訪問層類的封裝實現(xiàn)（30分鐘）學(xué)生基本信息控制類的封裝與實現(xiàn)（15分鐘）學(xué)生模仿實現(xiàn)所設(shè)計的實體信息控制類的封裝（25分鐘）本次課程小結(jié)（5分鐘）【習(xí)題要求】本章暫無【實驗要求】1、學(xué)生獨立完成實驗1的內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次實驗作業(yè)的成績，記錄學(xué)生期末總成績的2%4、實驗附加思考題，可以列入本次實驗的總成績中，并記錄到學(xué)生期末總成績中。授課對象系別軟件技術(shù)系本次課學(xué)時6學(xué)時年級班次章節(jié)題目第三章學(xué)生基本信息管理（順序表）目的要求(含技能要求)掌握線性表、順序表的概念和性質(zhì)，利用順序表的思想進(jìn)行學(xué)生基本信息的管理本節(jié)重點線性表的概念和性質(zhì)，順序表概念和性質(zhì)，學(xué)生信息管理順序表實現(xiàn)本節(jié)難點用順序表的思想進(jìn)行學(xué)生基本信息管理教學(xué)方法項目教學(xué)法，任務(wù)驅(qū)動法，“教學(xué)做”三位一體法教學(xué)用具多媒體教室+機房問題引入從學(xué)生基本信息管理功能界面的講述入手，引入學(xué)生信息管理業(yè)務(wù)實現(xiàn)。難點與重點講解方法以項目為引領(lǐng)，學(xué)生基本信息管理為任務(wù)驅(qū)動，將課堂講解、案例解學(xué)、模仿實作融為一體，進(jìn)行教學(xué)。本次課小節(jié)課程小節(jié)線性表的基本概念和性質(zhì)順序表的基本概念和性質(zhì)利用順序表的思想進(jìn)行學(xué)生基本信息的增、刪、改、查以及保存的功能實現(xiàn)順序表操作的算法時間復(fù)雜度分析教后札記掌握線性表和順序表的基本概念和性質(zhì)。利用順序表思想進(jìn)行業(yè)務(wù)類封裝。通過用戶界面實現(xiàn)業(yè)務(wù)類方法調(diào)用，顯示數(shù)據(jù)。初步實現(xiàn)簡單三層結(jié)構(gòu)項目開發(fā)。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第三章學(xué)生基本信息管理（順序表）【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）面向?qū)ο缶幊棠芰?。?）順序表思想進(jìn)行業(yè)務(wù)封裝能力（3）用順序表對數(shù)據(jù)進(jìn)行增、刪、改、查操作的能力（4）通過界面進(jìn)行業(yè)務(wù)類調(diào)用實現(xiàn)的能力2．知識目標(biāo)：（1）線性表的概念和性質(zhì)；（2）順序表的概念、性質(zhì)和操作；（3）利用順序表實現(xiàn)學(xué)生基本信息增、刪、改、查操作；（4）應(yīng)用可視化界面實現(xiàn)學(xué)生基本信息管理；3．職業(yè)素質(zhì)目標(biāo)：★順序表操作的邏輯思維能力★獨立進(jìn)行順序表操作思考解決問題能力★分小組進(jìn)行小模塊開發(fā)的團(tuán)隊協(xié)作能力★創(chuàng)新能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力。數(shù)據(jù)結(jié)構(gòu)和算法的基本概念和性質(zhì)。教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。能夠正確、及時處理學(xué)生操作過程中出現(xiàn)的問題及錯誤。具有順序表的理論知識和編程能力。【主要內(nèi)容】1、線性表的定義和性質(zhì)1）線性表（LinearList）含義：定義：線性表是具有相同的物理含義，同一數(shù)據(jù)類型的n（n>=0）個數(shù)據(jù)元素的有限序列。理解：它解決元素之間存在“一對一”的邏輯關(guān)系。通常記為：其中，是第一個數(shù)據(jù)元素，又稱為起始結(jié)點；是最后一個數(shù)據(jù)元素，又稱為終端結(jié)點；n為數(shù)據(jù)元素的個數(shù)，即線性表的長度，稱為表長，當(dāng)n＝0時稱為空表。在線性表中相鄰元素之間存在著順序關(guān)系。對于元素而言，稱為的直接前驅(qū)，稱為的直接后繼。 2）線性表的特性：有且僅有一個開始結(jié)點，它沒有直接前驅(qū)。有且僅有一個終端結(jié)點，它沒有直接后繼。除了開始結(jié)點和終端結(jié)點外，其余結(jié)點都有且僅有一個直接前驅(qū)和一個直接后繼。2、順序表的定義和性質(zhì) 1）順序表（SequentialList）的含義： 定義：在計算機中，按順序存儲結(jié)構(gòu)存儲的線性表簡稱為順序表。 2）順序表的特征：存儲單元地址連續(xù)（需要一段連續(xù)空間）。邏輯上相鄰的數(shù)據(jù)元素其物理地址也相鄰。隨機存儲。存儲密度大（100%）3、學(xué)生信息管理業(yè)務(wù)實現(xiàn)： 學(xué)生基本信息管理模塊，主要實現(xiàn)學(xué)生基本信息的增、刪、改、查以及保存的功能。整個模塊的設(shè)計和實現(xiàn)的思路如下：創(chuàng)建順序表類，用以實現(xiàn)學(xué)生基本信息順序表的管理。創(chuàng)建學(xué)生基本信息管理業(yè)務(wù)類，用以實現(xiàn)學(xué)生信息順序表的增、刪、改等的業(yè)務(wù)處理。具體的步驟如下：從通用模塊層中，獲取學(xué)生基本信息，并初始化學(xué)生基本信息順序表。在學(xué)生信息查詢方法中，給定學(xué)生的id，找到對應(yīng)的學(xué)生信息并進(jìn)行返回。在增加學(xué)生信息方法中，在學(xué)生基本信息順序表指定位置i，添加學(xué)生的信息elem。在刪除學(xué)生信息方法中，在學(xué)生基本信息順序表中，刪除指定位置i的學(xué)生信息。在修改學(xué)生信息方法中，在學(xué)生基本信息順序表中，修改指定學(xué)生id的信息。在保存方法中，實現(xiàn)對學(xué)生基本信息順序表發(fā)生增、刪、改后的信息保存。1）學(xué)生基本信息順序表的構(gòu)建 創(chuàng)建學(xué)生基本信息順序表類，用以實現(xiàn)學(xué)生信息數(shù)據(jù)在順序表中的增、刪、改的操作。該類的主要成員包括：Student_info[]Data：一維無界數(shù)組，用以構(gòu)建學(xué)生基本信息順序表Length：用以記錄順序表中，實際的學(xué)生信息個數(shù)。2）學(xué)生基本信息管理業(yè)務(wù)類的定義學(xué)生基本信息管理業(yè)務(wù)類，是通過順序表的思想，用來實現(xiàn)學(xué)生信息的增、刪、改的操作。3）學(xué)生基本信息管理業(yè)務(wù)類的初始化該方法用以初始化學(xué)生基本信息順序表，具體步驟如下：通過學(xué)生數(shù)據(jù)控制層對象StudentManger獲取學(xué)生的基本信息。初始化順序表的空間大小，以及初始順序表長度。從數(shù)據(jù)庫中提取的學(xué)生信息，逐個初始化順序表的元素。4）查找學(xué)生基本信息查找實現(xiàn) 本方法是指給定學(xué)生的學(xué)生id號，查找對應(yīng)學(xué)生的基本信息，并返回學(xué)生在順序表中對應(yīng)對應(yīng)位置和相關(guān)基本信息?；舅悸窞椋簩樞虮碇忻總€元素進(jìn)行循環(huán)。逐個查找每個學(xué)生元素的id與給定學(xué)生的id是否相同，若相同則找到返回相關(guān)信息，否則繼續(xù)循環(huán)查找。如果循環(huán)完仍然未找到，返回null。5）新增學(xué)生基本信息業(yè)務(wù)實現(xiàn)具體的實現(xiàn)步驟如下：獲取現(xiàn)有順序表的長度n，判斷插入位置i是否合法，不合法返回false。判斷i是否超越所定義順序表的最大值，若越界返回false。如是在順序表末尾插入學(xué)生信息，直接將信息插入，順序表長度自加，返回true。將……之間的所有結(jié)點依次后移，為新元素讓出第i個位置。將新結(jié)點elem插入到第i個位置。表長Length自加，返回true。6）刪除學(xué)生基本信息業(yè)務(wù)實現(xiàn)刪除學(xué)生基本信息的步驟如下：獲取學(xué)生基本信息表的長度，判斷所要刪除結(jié)點位置是否合法，不合法，返回false。獲取所要刪除的學(xué)生基本信息。將第i個學(xué)生后面的學(xué)生信息……之間的結(jié)點順序依次向上移動。并使表長length自減。7）修改學(xué)生基本信息業(yè)務(wù)實現(xiàn) 修改學(xué)生的基本信息是指：對特定學(xué)生id的基本信息發(fā)生修改，在順序表中作相應(yīng)的變化，具體的實現(xiàn)步驟如下：從學(xué)生順序表中，進(jìn)行循環(huán)，逐個提取學(xué)生基本信息中的學(xué)生id。判斷所提取的學(xué)生id與所要修改的學(xué)生id是否一致。如果一致，進(jìn)行學(xué)生信息的修改，并返回true。若不一致，繼續(xù)循環(huán)，循環(huán)完畢仍未找到，返回false。8）學(xué)生基本信息保存業(yè)務(wù)實現(xiàn) 學(xué)生基本信息的保存是指：通過界面調(diào)用上面的增、刪、改等方法，對學(xué)生基本信息順序表的信息發(fā)生改變后，將改變后的結(jié)果保存到數(shù)據(jù)庫中，在這里直接調(diào)用學(xué)生數(shù)據(jù)控制層對象StudentManger的Save_info（）方法即可。【學(xué)法】自主學(xué)習(xí)、教師講解、課題模仿練習(xí)，課后習(xí)題和上機實驗【教學(xué)方法】項目教學(xué)+媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】學(xué)生基本信息管理功能描述（5分鐘）線性表的定義和性質(zhì)：（5分鐘）順序表的定義和性質(zhì)（5分鐘）學(xué)生基本信息順序表節(jié)點類創(chuàng)建實現(xiàn)講解（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿創(chuàng)建對應(yīng)的節(jié)點類（10分鐘）學(xué)生基本信息管理業(yè)務(wù)類的定義和初始化（15分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)業(yè)務(wù)類的定義和順序表的初始化（20分鐘）學(xué)生基本信息查找講解（10分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)順序表信息的查找（15分鐘）在順序表中實現(xiàn)學(xué)生基本信息的增加。（10分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)順序表節(jié)點詳細(xì)的增加（20分鐘）在順序表中實現(xiàn)學(xué)生基本信息的刪除。（10分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)順序表節(jié)點詳細(xì)的刪除（15分鐘）在順序表中實現(xiàn)學(xué)生信息的修改。（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)順序表節(jié)點詳細(xì)的修改（10分鐘）實現(xiàn)學(xué)生信息的保存。（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)實體詳細(xì)的保存（5分鐘）本次課程小結(jié)（5分鐘）通過表現(xiàn)層調(diào)用業(yè)務(wù)類進(jìn)行界面功能實現(xiàn)以及調(diào)試（90分鐘）【習(xí)題要求】1、學(xué)生獨立完成本章習(xí)題內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次作業(yè)的成績，記錄學(xué)生期末總成績的2%4、附加思考題，可以列入本次作業(yè)的加分項，并記錄到學(xué)生期末總成績中?！緦嶒炓蟆?、學(xué)生獨立完成實驗2的內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次實驗作業(yè)的成績，記錄學(xué)生期末總成績的2%4、實驗附加思考題，可以列入本次實驗的總成績中，并記錄到學(xué)生期末總成績中。授課對象系別軟件技術(shù)系本次課學(xué)時8學(xué)時年級班次章節(jié)題目第4章學(xué)生成績信息管理（鏈表）目的要求(含技能要求)掌握鏈表的基本功能和存儲方式，利用單向鏈表實現(xiàn)學(xué)生成績信息的管理。了解循環(huán)鏈表和雙向鏈表的功能和簡單的操作。本節(jié)重點鏈表和單向鏈表的基本功能和操作。本節(jié)難點用單向鏈表的思想實現(xiàn)學(xué)生成績信息的管理教學(xué)方法項目教學(xué)法，任務(wù)驅(qū)動法，模仿學(xué)習(xí)法，“教學(xué)做”三位一體法教學(xué)用具多媒體教室、機房問題引入從學(xué)生成績信息管理功能界面的講述入手，引入學(xué)生成績信息管理業(yè)務(wù)實現(xiàn)難點與重點講解方法以項目為引領(lǐng)，學(xué)生成績信息管理為任務(wù)驅(qū)動，將課堂講解、案例解學(xué)、模仿實作融為一體，進(jìn)行教學(xué)。本次課小節(jié)課程小節(jié)鏈表的基本概念和存儲方式。單向鏈表的基本概念以及操作。利用單向鏈表的思想進(jìn)行學(xué)生成績信息的增、刪、改、查以及保存的功能實現(xiàn)。單向循環(huán)鏈表的基本概念和操作。雙向鏈表和雙向循環(huán)鏈表的基本功能和操作。教后札記掌握單向鏈表的基本概念和性質(zhì)。利用單向鏈表思想進(jìn)行學(xué)生成績信息業(yè)務(wù)類封裝。通過用戶界面實現(xiàn)業(yè)務(wù)類方法調(diào)用，顯示數(shù)據(jù)。初步實現(xiàn)簡單三層結(jié)構(gòu)項目開發(fā)。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第四章學(xué)生成績信息管理（鏈表）【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）面向?qū)ο缶幊棠芰Α＃?）鏈表思想進(jìn)行業(yè)務(wù)封裝能力（3）應(yīng)用鏈表對學(xué)生成績信息進(jìn)行增、刪、改、查操作的能力（4）通過界面進(jìn)行業(yè)務(wù)類調(diào)用實現(xiàn)能力2．知識目標(biāo)：（1）鏈表的概念和存儲方式；（2）單向鏈表的概念性質(zhì)和操作；（3）利用單向鏈表實現(xiàn)學(xué)生成績信息增、刪、改、查操作；（4）應(yīng)用可視化界面實現(xiàn)學(xué)生成績信息管理；（5）雙向鏈表的基本概念和操作；（6）循環(huán)鏈表的基本概念和操作；3．職業(yè)素質(zhì)目標(biāo)：★鏈表操作的邏輯思維能力★應(yīng)用單向鏈表獨立思考解決問題能力★小組項目團(tuán)隊協(xié)作開發(fā)能力★創(chuàng)新能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力。線性表的基本概念和性質(zhì)。順序表基本概念、性質(zhì)和操作應(yīng)用能力。教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。能夠正確、及時處理學(xué)生操作過程中出現(xiàn)的問題及錯誤。能夠應(yīng)用各種常用鏈表實現(xiàn)數(shù)據(jù)增、刪、改、查的能力?！局饕獌?nèi)容】1、鏈表的基本概念和存儲方式在線性表的順序存儲結(jié)構(gòu)中，其特點是邏輯關(guān)系上相鄰的兩個結(jié)點在物理位置上也相鄰，因此可以隨機存取表中的任一結(jié)點，并且結(jié)點的存儲位置可用一個簡單直觀的公式來表示。但也正是這個特點造成順序存儲的一些缺點。例如，存儲空間空閑、存儲容量難以擴充、當(dāng)進(jìn)行插入和刪除運算時需移動大量的結(jié)點、效率較低等。1）鏈表的定義：鏈表是線性表的一種，是通過鏈?zhǔn)酱鎯Ψ绞絹肀４鏀?shù)據(jù)的線性表。2）鏈表的存儲方式：在計算機內(nèi)存中利用存儲單元（不要求連續(xù)）來存放結(jié)點的值及它在內(nèi)存中的地址，各個結(jié)點的存放順序及位置可以以任意順序進(jìn)行，原來相鄰的結(jié)點在計算機內(nèi)存中的存儲位置不一定相鄰，從一個元素查找下一個元素必須通過地址（指針）才能實現(xiàn)，因此它不能像順序表那樣隨機訪問，而只能按順序訪問。2、單向鏈表含義單向鏈表（Singlelinkedlist）是最簡單的鏈表，每個結(jié)點包含一個數(shù)據(jù)域和一個指針域，結(jié)點之間的關(guān)系是通過指針域來訪問的，最后一個結(jié)點的指針域為空。3、應(yīng)用單向鏈表思想進(jìn)行學(xué)生成績信息管理業(yè)務(wù)實現(xiàn)：學(xué)生成績信息管理模塊，主要實現(xiàn)學(xué)生成績信息的增、刪、改、查以及保存的功能。整個模塊的設(shè)計和實現(xiàn)的思路如下：創(chuàng)建學(xué)生成績單向鏈表類，用以實現(xiàn)單個學(xué)生成績信息的記錄。創(chuàng)建學(xué)生成績信息管理業(yè)務(wù)類，用以實現(xiàn)學(xué)生成績信息單向鏈表的增、刪、改等的業(yè)務(wù)處理。具體的步驟如下：從通用模塊層中，獲取學(xué)生成績信息，并初始化學(xué)生成績單向鏈表對象。在學(xué)生成績查詢方法中，給定學(xué)生的id，找到對應(yīng)的學(xué)生成績信息進(jìn)行返回。在增加學(xué)生成績方法中，在學(xué)生成績單向鏈表中指定位置i，添加學(xué)生成績信息elem。在刪除學(xué)生成績方法中，在學(xué)生成績單向鏈表中，刪除指定位置i的學(xué)生成績信息。在修改學(xué)生成績方法中，在學(xué)生成績單向鏈表中，修改指定學(xué)生id成績信息。在保存方法中，實現(xiàn)對學(xué)生成績單向鏈表發(fā)生增、刪、改后的信息保存。1）學(xué)生成績單向鏈表結(jié)點類構(gòu)建 創(chuàng)建學(xué)生成績信息單向鏈表結(jié)點類，用以實現(xiàn)學(xué)生成績信息數(shù)據(jù)在單向鏈表中的增、刪、改的管理。該類的主要成員包括：Student_infoData：數(shù)據(jù)域，學(xué)生信息對象，用以記錄學(xué)生的基本信息和成績信息nodeNext：指針域，用以指向下一個學(xué)生的結(jié)點。2）學(xué)生成績信息管理業(yè)務(wù)類構(gòu)建 學(xué)生成績信息業(yè)務(wù)類，是應(yīng)用單向鏈表的思想，用以實現(xiàn)學(xué)生成績信息的增、刪、改、查等操作，主要的成員和方法如下所示：3）學(xué)生成績信息單向鏈表創(chuàng)建 該方法用以實現(xiàn)學(xué)生成績單向鏈表的初始化。主要的思路是從數(shù)據(jù)控制對象中得到已有的所有學(xué)生成績，分別創(chuàng)建結(jié)點，初始化各個學(xué)生的成績，并添加到對象鏈表中。具體步驟如下： （1）、為鏈表對象L，分配內(nèi)存空間，并使指針域為空，帶頭結(jié)點的空單向鏈表創(chuàng)建好。 （2）、定義局部單向鏈表對象p，用以創(chuàng)建鏈表其他學(xué)生成績信息結(jié)點。 （3）、利用數(shù)據(jù)控制層對象的學(xué)生信息數(shù)組，逐個讀取，初始化單向鏈表結(jié)點，并添加到單向鏈表中，具體作法如下： 逐個循環(huán)，為局部學(xué)生成績鏈表對象p，分配新空間。 從數(shù)據(jù)控制層學(xué)生信息數(shù)組獲取信息，為對象p的數(shù)據(jù)域賦值。 修改局部對象p和成員單向鏈表對象L的指針域。4）學(xué)生成績信息的查詢 該方法是根據(jù)所輸入的學(xué)生id信息，在單向鏈表中進(jìn)行查找，返回學(xué)生在鏈表中的位置和該學(xué)生的所有信息。具體思路如下： （1）、調(diào)用該方法之前，先創(chuàng)建學(xué)生信息對象elem，并把所要查找的學(xué)生id賦值到elem對象的學(xué)生id屬性st_id。（在C#中應(yīng)用引用傳值，在Java中用對象傳值）。 （2）、聲明局部變量intplace=0；用以記錄所找id在鏈表中的位置。 （3）、聲明局部學(xué)生成績信息鏈表結(jié)點p=L；通過p=p.next操作，來實現(xiàn)從鏈表頭到鏈表尾的搜索。 （4）、對鏈表的各個結(jié)點進(jìn)行搜索，判斷各個結(jié)點的學(xué)生id與輸入對象elem的學(xué)生id是否相等，若相等，表示找到。返回所找學(xué)生信息和所在的位置。 （5）、若循環(huán)完畢仍未找到，返回位置null。5）學(xué)生成績信息鏈表中插入學(xué)生成績信息 在單向鏈表插入結(jié)點的基本思路如下：將學(xué)生成績信息x的新結(jié)點插入到表的第i個位置上，即插入到與之間。為此，必須首先找到結(jié)點的存儲位置（用p表示），然后建立一個數(shù)據(jù)域為x的新結(jié)點（用s表示），并令結(jié)點的指針域指向新結(jié)點，而新結(jié)點的指針域則指向結(jié)點，從而實現(xiàn)了三個結(jié)點，x，之間邏輯關(guān)系的變化。單鏈表插入運算的示意圖如圖4.5所示。圖4.5在單鏈表中插入結(jié)點x 學(xué)生成績信息單向鏈表插入的流程圖如下：6）學(xué)生成績信息的刪除 該方法的功能是，刪除單向鏈表中第i個結(jié)點的信息，并返回是否刪除成功和所刪除的學(xué)生成績信息。具體步驟為：首先，使指針p指向要刪除結(jié)點的直接前驅(qū)；然后，將要刪除的學(xué)生信息賦值給要返回的對象。最后，將p的指針域指向要刪除結(jié)點的直接后繼。圖4.7反映了刪除結(jié)點時指針的變化。圖4.7刪除單鏈表中值為x的結(jié)點7）學(xué)生成績信息的修改 該方法用以修改指定學(xué)生id的學(xué)生成績信息，實現(xiàn)的思想與學(xué)生成績信息查找相似。8）學(xué)生成績信息的保存 學(xué)生成績信息的保存是指：在單向鏈表中進(jìn)行了增、刪、改后，要將學(xué)生成績信息保存到數(shù)據(jù)庫中。在這里我們通過調(diào)用數(shù)據(jù)控制層的save_info（）來實現(xiàn)。 單向循環(huán)鏈表：單鏈表結(jié)點之間是用一個指針域鏈接，其終端結(jié)點的指針域的值為NULL，表示單鏈表的結(jié)束。若將單鏈表的終端結(jié)點的指針域指向頭結(jié)點，則整個鏈表頭尾結(jié)點相鏈形成一個環(huán)，從而就構(gòu)成了循環(huán)鏈表（circularlinkedlist）。如圖4.9所示：aa1an…h(huán)ead圖4.9單循環(huán)鏈表循環(huán)鏈表的主要優(yōu)點是從表中任一結(jié)點出發(fā)，都能通過后移操作來掃描整個鏈表（對單鏈表而言，則只能從頭結(jié)點開始）。單向循環(huán)鏈表上的操作與前面討論的單鏈表的操作基本一致，差別僅僅在于算法中控制循環(huán)中止的條件不是判斷指針是否為空，而是判斷指針是否指向頭指針。在單向循環(huán)鏈表的其他操作方法，與單向鏈表操作類似，只是終止條件由p!=NULL改為p!=L即可。雙向鏈表和雙向循環(huán)鏈表在循環(huán)鏈表中，雖然從任一結(jié)點出發(fā)都可以找到其前驅(qū)結(jié)點，但時間復(fù)雜度為O(n)，原因在于其每個結(jié)點只含有一個指向其直接后繼的指針域，這對于尋找后繼結(jié)點是很方便的。若想快速確定一個結(jié)點的直接前驅(qū)，則可以在單鏈表的基礎(chǔ)上，每個結(jié)點再加上一個指針域存儲其直接前驅(qū)的地址，這樣就構(gòu)成了雙向鏈表（Doublelinkedlists）。其結(jié)點形式如圖4.10所示。圖4.10雙向鏈表的結(jié)點結(jié)構(gòu)其中，prior域指向其前驅(qū)結(jié)點，next指向其后繼結(jié)點，data域存放結(jié)點本身的信息。1）雙向鏈表插入操作由于雙向鏈表是一種對稱結(jié)構(gòu)，每個結(jié)點既有指向其直接前驅(qū)的指針域，又有指向其直接后繼的指針域，因此與單鏈表相比，要在雙向鏈表中查找一個已知結(jié)點的直接前驅(qū)和直接后繼要方便得多。以下算法實現(xiàn)在雙向鏈表中第i個結(jié)點前插入值為x的新結(jié)點。圖4.11反映了雙向鏈表中插入結(jié)點時指針的變化情況。圖4.11雙向鏈表的插入運算2）雙向鏈表的刪除操作以下算法實現(xiàn)在雙向鏈表中刪除第i個結(jié)點。圖4.12反映了雙向鏈表中刪除結(jié)點時指針的變化情況。圖4.12雙向鏈表的刪除運算【學(xué)法】自主學(xué)習(xí)、教師講解、課題模仿練習(xí)、課外探討學(xué)習(xí)、課后習(xí)題和上機實驗【教學(xué)方法】項目教學(xué)+媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】學(xué)生成績信息管理功能描述（5分鐘）鏈表的基本功能和存儲方式：（5分鐘）單向鏈表的定義和理解（10分鐘）學(xué)生成績信息單向鏈表節(jié)點類創(chuàng)建實現(xiàn)講解（3分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿創(chuàng)建對應(yīng)的節(jié)點類（7分鐘）學(xué)生成績信息管理業(yè)務(wù)類的定義和初始化（15分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)業(yè)務(wù)類的定義和單向鏈表的初始化（20分鐘）學(xué)生成績信息查找講解（10分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)鏈表信息的查找（15分鐘）在單向鏈表中實現(xiàn)學(xué)生成績信息的增加。（15分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)單向鏈表節(jié)點詳細(xì)的增加（30分鐘）在單向鏈表中實現(xiàn)學(xué)生成績信息的刪除。（15分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)單向鏈表節(jié)點詳細(xì)的刪除（30分鐘）在單向鏈表中實現(xiàn)學(xué)生信息的修改。（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)單向鏈表節(jié)點詳細(xì)的修改（10分鐘）實現(xiàn)學(xué)生成績信息的保存。（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)實體詳細(xì)的保存（5分鐘）單向循環(huán)鏈表的概念和操作。（20分鐘）雙向鏈表的概念和操作。（30分鐘）雙向循環(huán)鏈表的概念和操作。（10分鐘）本次課程小結(jié)（5分鐘）通過表現(xiàn)層調(diào)用業(yè)務(wù)類進(jìn)行界面功能實現(xiàn)以及調(diào)試（90分鐘）【習(xí)題要求】1、學(xué)生獨立完成本章習(xí)題內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次作業(yè)的成績，記錄學(xué)生期末總成績的2%4、附加思考題，可以列入本次作業(yè)的加分項，并記錄到學(xué)生期末總成績中?！緦嶒炓蟆?、學(xué)生獨立完成實驗3的內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次實驗作業(yè)的成績，記錄學(xué)生期末總成績的2%4、實驗附加思考題，可以列入本次實驗的總成績中，并記錄到學(xué)生期末總成績中。授課對象系別軟件技術(shù)系本次課學(xué)時4學(xué)時年級班次章節(jié)題目第5章學(xué)生基本信息審核（棧）目的要求(含技能要求)掌握棧的基本概念、性質(zhì)和操作、利用棧的思想思想學(xué)生基本信息審核本節(jié)重點棧的基本概念和操作，以及棧的應(yīng)用本節(jié)難點應(yīng)用棧的思想實現(xiàn)學(xué)生基本信息的審核教學(xué)方法項目教學(xué)法，任務(wù)驅(qū)動法，模仿學(xué)習(xí)法，“教學(xué)做”三位一體法教學(xué)用具多媒體教室、機房問題引入從學(xué)生基本信息審核管理功能界面的講述入手，介紹簡單的學(xué)生基本信息審核的流程，以及實現(xiàn)的步驟。難點與重點講解方法以項目為引領(lǐng)，學(xué)生基本信息審核管理為任務(wù)驅(qū)動，將課堂講解、案例解學(xué)、模仿實作融為一體，進(jìn)行教學(xué)。本次課小節(jié)課程小節(jié)棧的基本概念、性質(zhì)和操作棧的存儲方式和分類利用順序棧實現(xiàn)學(xué)生基本信息的審核棧的其它應(yīng)用教后札記掌握棧的基本概念、性質(zhì)、操作、分類。利用順序棧實現(xiàn)學(xué)生基本信息審核業(yè)務(wù)類的封裝。通過用戶界面實現(xiàn)業(yè)務(wù)類方法的調(diào)用，顯示數(shù)據(jù)，實現(xiàn)審核的功能。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第五章學(xué)生基本信息審核（棧）【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）面向?qū)ο缶幊棠芰?。?）棧的基本概念和編程能力。（3）應(yīng)用棧的思想實現(xiàn)學(xué)生基本信息審核的業(yè)務(wù)類封裝編程能力。（4）通過界面進(jìn)行業(yè)務(wù)類調(diào)用顯示的能力2．知識目標(biāo)：（1）棧的基本概念、類型和存儲方式；（2）順序棧的概念和操作；（3）利用順序棧實現(xiàn)學(xué)生基本信息的審核；（4）應(yīng)用可視化界面實現(xiàn)學(xué)生基本信息審核管理；（5）了解鏈棧的基本概念和操作；（6）了解棧編程思想的其它應(yīng)用。3．職業(yè)素質(zhì)目標(biāo)：★順序棧進(jìn)行編程的邏輯思維能力★利用順序棧獨立思考解決問題能力★分小組進(jìn)行團(tuán)隊開發(fā)能力★創(chuàng)新能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力具備順序表、鏈表的理論知識和操作能力。教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。能夠正確、及時處理學(xué)生操作過程中出現(xiàn)的問題及錯誤。具備應(yīng)用順序表和鏈表進(jìn)行編程的能力。.能夠應(yīng)用棧的思想進(jìn)行編程的能力。【主要內(nèi)容】1、棧的基本概念棧（stack）是限制在表的一端進(jìn)行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂（top），另一個固定端稱為棧底（bottom）。當(dāng)表中沒有元素時稱為空棧。如圖5.2所示棧中有三個元素，進(jìn)棧的順序是a1、a2、a3，當(dāng)需要出棧時其順序為a3、a2、a1，所以棧又稱為后進(jìn)先出的線性表（LastInFirstOut），簡稱LIFO表。2、棧的存儲存儲結(jié)構(gòu)由于棧是運算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也是適用的，只是操作不同而已。1）順序棧利用順序存儲方式實現(xiàn)的棧稱為順序棧。類似于順序表的定義，棧中的數(shù)據(jù)元素用一個預(yù)設(shè)的足夠長度的一維數(shù)組來實現(xiàn)：student_info[]elem，棧底位置可以設(shè)置在數(shù)組的任一個端點，而棧頂是隨著插入和刪除而變化的，用一個inttop來作為棧頂?shù)闹羔槪该鳟?dāng)前棧頂?shù)奈恢?，同樣將elem和top封裝在一個類中，順序棧的類型描述如下： publicclassStack {//定義順序棧 constintMax_size=100;//順序棧最大容量 publicstudent_info[]elem=newstudent_info[Max_size];//保存部門信息 publicinttop=-1;//棧指針}定義一個指向順序棧的指針：Stacks;2）鏈棧用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。通常鏈棧用單鏈表來表示，因此其結(jié)點結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同，在此用LinkStack表示，即有： publicclassLinkStack {//定義鏈棧 publicstudent_infoelem;//保存部門信息 LinkStacknext;//棧指針}說明top為棧頂指針：LinkStacktop;3、用順序棧實現(xiàn)學(xué)生基本信息的審核學(xué)生基本信息審核模塊，可假想學(xué)生的基本信息資料放入一個文件箱里，先放進(jìn)去的后審核，后放入的先審核。利用順序棧的思想實現(xiàn)學(xué)生基本信息的審查、修改、保存的功能。整個模塊的設(shè)計和實現(xiàn)的思路如下：創(chuàng)建學(xué)生基本信息審核順序棧類，用以記錄要進(jìn)行審核學(xué)生的基本信息。創(chuàng)建學(xué)生基本信息業(yè)務(wù)類，用以實現(xiàn)學(xué)生基本信息顯示、進(jìn)棧、出棧以及審核后的保存。從數(shù)據(jù)控制層中，獲取學(xué)生成績信息，并放入到學(xué)生信息數(shù)組sx[]中，供表現(xiàn)層調(diào)用。在入棧方法中，從表現(xiàn)層中將要進(jìn)行審核的學(xué)生基本信息壓入到順序棧中。在出棧方法中，從順序棧中獲取要進(jìn)行審核的學(xué)生信息，并返回給表現(xiàn)層。在保存方法中，從表現(xiàn)層將進(jìn)行修改的學(xué)生基本信息傳入，調(diào)用數(shù)據(jù)控制層的方法實現(xiàn)學(xué)生信息的保存。1）學(xué)生基本信息審核順序棧類的構(gòu)建該類是利用順序棧的思想，來保存需要進(jìn)行審核的學(xué)生基本信息，其主要的成員有： Student_info[]Data：用以記錄需要進(jìn)行審核的學(xué)生基本信息 inttop：棧頂指針變量2）學(xué)生基本信息審核業(yè)務(wù)類的構(gòu)建該類用以實現(xiàn)學(xué)生基本信息的初始化，為審核業(yè)務(wù)提供入棧、出棧以及修改后的學(xué)生基本信息的保存。3）學(xué)生基本信息和順序棧的初始化該方法是在業(yè)務(wù)對象實例化時，實現(xiàn)調(diào)用，進(jìn)行必要的初始化，其主要思想是：從數(shù)據(jù)控制層獲取學(xué)生基本信息的長度。初始化學(xué)生基本信息數(shù)組以及相應(yīng)的每個成員，供界面調(diào)用和學(xué)生信息保存時使用。初始化順序棧數(shù)組的大小以及棧指針的值。判斷學(xué)生信息順序棧是否為空5）要審核的學(xué)生信息入棧首先判斷學(xué)生信息順序棧是否已滿，然后實現(xiàn)入棧的操作。6）要審核的學(xué)生信息出棧首先進(jìn)行順序棧是否為空的判斷，在將學(xué)生基本信息出棧，并返回出棧學(xué)生的位置，供界面使用，7）審核后的學(xué)生信息保存根據(jù)所修改信息的學(xué)生id，找到學(xué)生數(shù)組的對于位置，進(jìn)行修改，并調(diào)用數(shù)據(jù)控制層類的方法實現(xiàn)信息保存。4、棧的應(yīng)用：數(shù)制轉(zhuǎn)換問題將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3456，r=8為例轉(zhuǎn)換方法如下：NN/8（整除）N%8（求余）34674333低4335415466606高所以：（3456）10=（6563）8我們看到所轉(zhuǎn)換的8進(jìn)制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果?！緦W(xué)法】自主學(xué)習(xí)、教師講解、課題模仿練習(xí)、課外探討學(xué)習(xí)、課后習(xí)題和上機實驗【教學(xué)方法】項目教學(xué)+媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】學(xué)生基本信息審核管理功能描述（5分鐘）棧的基本概念、性質(zhì)、存儲方式以及操作：（10分鐘）學(xué)生基本信息審核順序棧類的構(gòu)建講解（3分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿創(chuàng)建對應(yīng)順序棧類（7分鐘）學(xué)生基本信息審核管理業(yè)務(wù)類的定義和初始化（10分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)業(yè)務(wù)類的定義和初始化（10分鐘）學(xué)生基本信息審核順序棧是否為空判斷（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿創(chuàng)建對應(yīng)順序棧是否為空判斷（5分鐘）學(xué)生基本信息審核入棧操作（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)入棧操作（10分鐘）學(xué)生基本信息審核出棧操作（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)出棧操作（10分鐘）學(xué)生基本信息審核信息保存。（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)審核信息保存（5分鐘）棧的應(yīng)用：數(shù)制轉(zhuǎn)換問題（20分鐘）本次課程小結(jié)（5分鐘）通過表現(xiàn)層調(diào)用業(yè)務(wù)類進(jìn)行界面功能實現(xiàn)以及調(diào)試（60分鐘）【習(xí)題要求】1、學(xué)生獨立完成本章習(xí)題內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次作業(yè)的成績，記錄學(xué)生期末總成績的2%4、附加思考題，可以列入本次作業(yè)的加分項，并記錄到學(xué)生期末總成績中?！緦嶒炓蟆?、學(xué)生獨立完成實驗4的內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次實驗作業(yè)的成績，記錄學(xué)生期末總成績的2%4、實驗附加思考題，可以列入本次實驗的總成績中，并記錄到學(xué)生期末總成績中。授課對象系別軟件技術(shù)系本次課學(xué)時4學(xué)時年級班次章節(jié)題目第6章學(xué)生成績信息審核（隊列）目的要求(含技能要求)掌握隊列的基本概念、性質(zhì)和操作、利用隊列的思想思想學(xué)生成績信息審核本節(jié)重點隊列的基本概念和操作，以及隊列的應(yīng)用本節(jié)難點應(yīng)用循環(huán)隊列的思想實現(xiàn)學(xué)生成績信息的審核教學(xué)方法項目教學(xué)法，任務(wù)驅(qū)動法，模仿學(xué)習(xí)法，“教學(xué)做”三位一體法教學(xué)用具多媒體教室、機房問題引入從學(xué)生基本成績審核管理功能界面的講述入手，介紹簡單的學(xué)生成績息審核的流程，以及實現(xiàn)的步驟。難點與重點講解方法以項目為引領(lǐng)，學(xué)生成績信息審核管理為任務(wù)驅(qū)動，將課堂講解、案例解學(xué)、模仿實作融為一體，進(jìn)行教學(xué)。本次課小節(jié)課程小節(jié)隊列和循環(huán)隊列的基本概念、性質(zhì)和操作鏈隊的概念和存儲方式利用循環(huán)隊列實現(xiàn)學(xué)生成績信息的審核教后札記1、掌握隊列的基本概念、性質(zhì)、操作、分類。2、利用循環(huán)隊列實現(xiàn)學(xué)生成績信息審核業(yè)務(wù)類的封裝。3、通過用戶界面實現(xiàn)業(yè)務(wù)類方法的調(diào)用，顯示數(shù)據(jù)，實現(xiàn)審核的功能。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第六章學(xué)生成績信息審核（隊列）【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）面向?qū)ο缶幊棠芰Α＃?）隊列的基本概念和編程思想能力。（3）應(yīng)用循環(huán)隊列的思想實現(xiàn)學(xué)生成績信息審核的業(yè)務(wù)類封裝編程能力。（4）通過界面進(jìn)行業(yè)務(wù)類調(diào)用顯示的能力2．知識目標(biāo)：（1）隊列的基本概念、類型和存儲方式；（2）順序隊列、循環(huán)隊列的概念和操作；（3）利用循環(huán)隊列實現(xiàn)學(xué)生成績信息的審核；（4）應(yīng)用可視化界面實現(xiàn)學(xué)生成績信息審核管理；（5）了解鏈隊的基本概念和操作；3．職業(yè)素質(zhì)目標(biāo)：★循環(huán)隊列編程的邏輯思維能力★應(yīng)用循環(huán)隊列獨立思考解決問題能力★分小組進(jìn)行團(tuán)隊協(xié)作開發(fā)能力★創(chuàng)新能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力。具備順序表、鏈表、棧的理論知識和操作能力。教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。能夠正確、及時處理學(xué)生操作過程中出現(xiàn)的問題及錯誤。具備應(yīng)用順序表和鏈表進(jìn)行編程的能力。能夠應(yīng)用隊列的思想進(jìn)行編程的能力?！局饕獌?nèi)容】1、隊列概念隊列(Queues)是一種先進(jìn)先出（FIFO即：FirstInFirstOut）的線性表，它只允許在表的一端插入元素，而在表的另一端刪除元素。在隊列中，允許插入元素一端稱為隊尾（rear），允許刪除元素的一端稱為對頭（front）。如下圖所示：1是隊頭，6是隊尾，取出數(shù)據(jù)只能從隊頭取出，存入數(shù)據(jù)只能在隊尾中進(jìn)行。圖6.2隊列2、順序隊列概念隊列的順序的順序存儲結(jié)構(gòu)稱為順序隊列，它是利用一組地址連續(xù)的存儲單元存放隊列中的元素。由于隊列中的插入和刪除限定在表的兩端進(jìn)行，因此設(shè)置隊頭指針和隊尾指針，分別指出當(dāng)前的隊首元素和隊尾元素。3、循環(huán)隊列 在順序隊列的基礎(chǔ)上，我們將數(shù)組的最后一個元素的下一個元素，邏輯上認(rèn)為是數(shù)組的第一個元素，這樣就形成邏輯上的環(huán)。具體實現(xiàn)：通過整除去余來實現(xiàn)入隊操作：rear=(rear+1)%M;sq[rear]=x;出隊操作：front=(front+1)%M;x=sq[front];存在的問題：如圖6.4（a）和（b）所示，容量為6的循環(huán)隊列中，在隊列初始狀態(tài)一致時（都有3個元素），當(dāng)三個元素出隊時即隊空有：front=rear，當(dāng)三個元素入隊時即隊滿有：front=rear。圖6.4循環(huán)隊列為空的情形解決的辦法，犧牲一個元素空間，約定以“隊列的尾指針?biāo)傅奈恢玫南乱粋€位置是隊頭指針”表示隊滿，而隊頭、尾指針的值相同時表示隊列為空。具體描述如下：隊空條件：front==rear隊滿條件：(rear+1)%M==front4、鏈隊列隊列在使用中數(shù)據(jù)元素變動比較大，因此隊列常用鏈?zhǔn)酱鎯Y(jié)構(gòu)。用鏈表表示的隊列稱為鏈隊列，簡稱鏈隊。為操作方便鏈隊大多采用帶頭結(jié)點鏈表結(jié)構(gòu)。但是，只設(shè)頭指針的單鏈表結(jié)構(gòu)不能完成滿足隊列的操作要求，為此應(yīng)再增加一個尾指針，使其指向鏈表最后一個結(jié)點。這樣，一個鏈隊顯然由一個頭指針和尾指針唯一確定，鏈隊列描述如下： publicclassQueue {//學(xué)生隊列 publicStudentelem//數(shù)據(jù)元素 publicQueuefront，rear; //鏈棧指針}鏈隊列的示意圖如下：圖6.4連隊列示意圖5、循環(huán)隊列實現(xiàn)學(xué)生成績信息的審核學(xué)生基本成績審核模塊，假想學(xué)生的成績單，放在一個隊列里，先來的先審核，后來的后審核。用過循環(huán)隊列實現(xiàn)學(xué)生成績信息審查、修改、保存的功能。整個模塊的設(shè)計和實現(xiàn)的思路如下：創(chuàng)建學(xué)生成績信息順序隊列類，用以記錄要進(jìn)行審核學(xué)生的成績信息。創(chuàng)建學(xué)生成績信息業(yè)務(wù)類，用以實現(xiàn)學(xué)生成績信息顯示，入隊、出隊以及審核后的保存。從數(shù)據(jù)控制層中，獲取學(xué)生成績信息，并放入到學(xué)生信息數(shù)組sx[]中，供表現(xiàn)層調(diào)用。在入隊方法中，從表現(xiàn)層中將要進(jìn)行審核的學(xué)生成績信息壓入到循環(huán)隊列中。在出隊方法中，從循環(huán)隊列中獲取要進(jìn)行審核的學(xué)生成績信息，并返回給表現(xiàn)層。在保存方法中，從表現(xiàn)層將進(jìn)行修改的學(xué)生成績信息傳入，調(diào)用數(shù)據(jù)控制層的方法實現(xiàn)學(xué)生信息的保存。1）學(xué)生成績信息審核順序隊列類的構(gòu)建：該類是利用循環(huán)隊列的思想，來保存需要進(jìn)行審核的學(xué)生成績信息，其主要的成員有： Student_info[]Data：用以記錄需要進(jìn)行審核的學(xué)生成績信息 intfront，rear：隊頭、隊尾指針變量2）學(xué)生成績信息審核業(yè)務(wù)類的構(gòu)建該類用以實現(xiàn)學(xué)生基本信息的初始化，并實現(xiàn)學(xué)生成績信息審核的入隊、出隊以及修改后的學(xué)生成績信息的保存。3）學(xué)生成績基本信息和順序隊列的初始化：該方法是在業(yè)務(wù)對象實例化時，實現(xiàn)調(diào)用，進(jìn)行必要的初始化，步驟如下：從數(shù)據(jù)控制層獲取學(xué)生基本信息的長度。初始化學(xué)生基本信息數(shù)組以及每個成員，供表現(xiàn)層調(diào)用和學(xué)生成績信息保存時使用。初始化循環(huán)隊列數(shù)組的大小以及隊頭、隊尾指針變量的值。4）學(xué)生成績信息入隊操作：實現(xiàn)學(xué)生成績信息入隊的操作，實現(xiàn)步驟如下：從應(yīng)用界面中傳入要進(jìn)行入隊的學(xué)生信息。進(jìn)行順序隊列是否已滿。若滿返回不成功標(biāo)志0。進(jìn)行學(xué)生信息元素入隊操作，修改隊尾指針值。并返回成功標(biāo)志1。5）學(xué)生成績信息出隊操作：實現(xiàn)學(xué)生成績信息出隊的操作，實現(xiàn)步驟如下：進(jìn)行順序隊列是否已空。進(jìn)行學(xué)生信息出隊操作，修改隊尾頭指針值。并返回在循環(huán)隊列中的位置和出隊的學(xué)生成績信息。6）學(xué)生成績信息修改后的保存：用以實現(xiàn)學(xué)生成績信息修改的保存，具體步驟如下：從界面中傳入所進(jìn)行修改的學(xué)生成績信息。調(diào)用數(shù)據(jù)控制層對象的方法實現(xiàn)修改后的學(xué)生成績信息保存。【學(xué)法】自主學(xué)習(xí)、教師講解、課題模仿練習(xí)、課外探討學(xué)習(xí)、課后習(xí)題和上機實驗【教學(xué)方法】項目教學(xué)+多媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】學(xué)生成績信息審核管理功能描述（5分鐘）隊列、循環(huán)隊列的基本概念、性質(zhì)、存儲方式以及操作：（20分鐘）學(xué)生成績信息審核順序隊列類的構(gòu)建講解（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿創(chuàng)建對應(yīng)順序隊列類（5分鐘）學(xué)生成績信息審核管理業(yè)務(wù)類的定義和初始化（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)業(yè)務(wù)類的定義和初始化（15分鐘）學(xué)生成績信息審核入隊操作（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)入隊操作（15分鐘）學(xué)生成績信息審核出隊操作（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)出隊操作（15分鐘）學(xué)生成績信息審核信息保存。（5分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿實現(xiàn)審核信息保存（5分鐘）通過表現(xiàn)層調(diào)用業(yè)務(wù)類進(jìn)行界面功能實現(xiàn)以及調(diào)試（70分鐘）本次課程小結(jié)（5分鐘）【習(xí)題要求】1、學(xué)生獨立完成本章習(xí)題內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次作業(yè)的成績，記錄學(xué)生期末總成績的2%4、附加思考題，可以列入本次作業(yè)的加分項，并記錄到學(xué)生期末總成績中。【實驗要求】1、學(xué)生獨立完成實驗5的內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次實驗作業(yè)的成績，記錄學(xué)生期末總成績的2%4、實驗附加思考題，可以列入本次實驗的總成績中，并記錄到學(xué)生期末總成績中授課對象系別軟件技術(shù)系本次課學(xué)時4學(xué)時年級班次章節(jié)題目第7章樹和二叉樹目的要求(含技能要求)了解樹的基本概念和操作，掌握二叉樹的基本概念和性質(zhì)，理解二叉樹遍歷的思想，并能對二叉樹作簡單的應(yīng)用。本節(jié)重點樹的基本概念、二叉樹的概念和性質(zhì)、二叉樹的遍歷本節(jié)難點二叉樹的概念、性質(zhì)以及遍歷教學(xué)方法講解+案例教學(xué)教學(xué)用具多媒體教室、機房問題引入以家族血緣關(guān)系圖來引入樹形結(jié)構(gòu)的概念難點與重點講解方法本章重點在于講解二叉樹的概念、性質(zhì)、遍歷。主要是理論講解，在講解過程中，可多結(jié)合生活實例進(jìn)行講解。講解+案例教學(xué)法本次課小節(jié)課程小節(jié)樹的基本概念和操作二叉樹的概念、性質(zhì)以及存儲方式。二叉樹的遍歷和簡單應(yīng)用。教后札記通過講解和課后大量的習(xí)題聯(lián)練習(xí)，來加強樹的概念，二叉樹的概念、性質(zhì)、遍歷以及簡單的應(yīng)用。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第七章樹和二叉樹【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）面向?qū)ο缶幊棠芰Α＃?）樹型結(jié)構(gòu)的抽象思維能力。（3）二叉樹應(yīng)用能力。2．知識目標(biāo)：（1）樹的基本概念、存儲方式以及操作；（2）二叉樹的基本概念、類型、性質(zhì)及其操作；（3）二叉樹的遍歷；（4）二叉樹的應(yīng)用；3．職業(yè)素質(zhì)目標(biāo)：★樹形結(jié)構(gòu)邏輯思維能力★利用樹形結(jié)構(gòu)獨立思考解決問題能力★創(chuàng)新能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力。具有線性結(jié)構(gòu)的理論知識和操作能力。教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。具有樹形結(jié)構(gòu)的理論知識和編程能力。具備線性結(jié)構(gòu)的理論知識和編程能力?！局饕獌?nèi)容】1、樹的基本概念、特點和操作：1）樹的定義：由此可抽象出樹的遞歸定義：樹是n(n≥0)個結(jié)點的有限集合。它滿足如下條件： (1)有一個特殊的結(jié)點稱為根結(jié)點(Root)； (2)除根結(jié)點之外的其余結(jié)點可分為m(m≥0)個互不相交的有限集合：T1，T2，T3，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(Subtree)。 (3)特別地，可以允許不包括任何結(jié)點的樹，把它稱為空樹。只有一個結(jié)點的樹稱為最小樹。2）樹的特點：在一棵樹中，通常將一個結(jié)點定義為其子樹的根結(jié)點的前趨結(jié)點，而其子樹的根結(jié)點就是它的后繼結(jié)點。因此，從邏輯上看，樹形結(jié)構(gòu)具有以下特點：（1）樹的根結(jié)點沒有前前驅(qū)結(jié)點，除了根結(jié)點之外的所有結(jié)點都有且僅有一個前驅(qū)結(jié)點。（2）樹中所有結(jié)點可以有零個或多個后繼結(jié)點。由此可見，樹形結(jié)構(gòu)描述的是層次關(guān)系，樹的結(jié)點之間存在一對多或多對一的關(guān)系。3）樹的基本術(shù)語：結(jié)點的度(Degree)：一個結(jié)點分出的子樹個數(shù)稱為該結(jié)點的度。葉子結(jié)點：度數(shù)為零的結(jié)點稱為葉子結(jié)點。非終結(jié)結(jié)點：度數(shù)不為零的結(jié)點稱為非終結(jié)結(jié)點，又叫做分支結(jié)點。樹的度：樹中結(jié)點的度數(shù)最大值稱為樹的度。樹中結(jié)點之間的關(guān)系：通常用家族關(guān)系來形象地描述結(jié)點之間的關(guān)系。根結(jié)點的子樹稱為該結(jié)點的孩子(Child)，相應(yīng)地，該結(jié)點稱為孩子的雙親(Parents)。結(jié)點的層次(Level)：一棵樹從根結(jié)點開始定義，根為第一層，根的孩子為第二層。若某結(jié)點在第i層，則其子樹的根就在第i+1層。其雙親在同一層的結(jié)點互為堂兄弟。例如，在圖7-2中樹根結(jié)點A是第一層，B、C、D是第二層，E、F、G、H、I是第三層，J、K、L是第四層，其中E、F和G、H、I互為堂兄弟。樹的深度(Depth)：樹中結(jié)點的最大層次稱為樹的深度或稱為高度。如圖7-2中樹的深度為4。有序樹：將樹中結(jié)點的各子樹看成是從左到右依次有序且不能交換，這樣的樹稱為有序樹。無序樹：對子樹的次序不加區(qū)別的樹稱為無序樹。森林(Forest)：m≥0棵互不相交的樹的集合。4）樹的基本操作：（1）SetNull（T）置T為空樹。（2）Root（T）或Root(x)求出樹T的根結(jié)點或求結(jié)點x所在的樹的根結(jié)點（3）Parent（T，x）求出樹T中x結(jié)點的父結(jié)點。（4）Child（T，x，i）求出樹T中結(jié)點x的第i個子結(jié)點。（5）Create（x，F(xiàn)）生成一棵以結(jié)點x為根結(jié)點，以森林F為子樹的樹。（6）AddChild（y，i，x）把以結(jié)點x為根的樹置為結(jié)點y的第i棵子樹。若樹中無結(jié)點y或結(jié)點y的子樹個數(shù)小于i-1，則返回NULL。（7）DelChild（x，i）刪除結(jié)點x的第i棵子樹。（8）Traverse（T）按某個次序依次訪問樹中各個結(jié)點，并使每個結(jié)點只能被訪問一次。以上這些運算的具體實現(xiàn)，要依賴于樹所采用的存儲結(jié)構(gòu)。2、二叉樹的概念和性質(zhì)：1）二叉樹定義：二叉樹可以定義為結(jié)點的有限集合，這個集合或者為空集，或者由一個根結(jié)點與兩個互不相交的、分別稱為這個根的左子樹和右子樹的二叉樹組成，下面介紹兩種特殊的二叉樹。滿二叉樹：如果一棵二叉樹的任何結(jié)點或者是樹葉結(jié)點，或者有兩棵非空子樹，則此二叉樹稱為滿二叉樹。圖7-7(a)為一棵滿二叉樹。完全二叉樹：若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可以小于2，其余各層結(jié)點的度數(shù)必須為2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹為完全二叉樹。圖7-7（b）為一棵完全二叉樹。圖7-7滿二叉樹和完全二叉樹示例2）二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）。性質(zhì)2：深度為k的二叉樹最多有2k-1個結(jié)點（k≥1）。性質(zhì)3：包含n（n>0）個結(jié)點的二叉樹的分支數(shù)為n-1。性質(zhì)4：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2＋1。性質(zhì)5：具有n個結(jié)點的完全二叉樹的深度k為＋1。[性質(zhì)6]設(shè)擁有n個結(jié)點的完全二叉樹中某結(jié)點的序號為i(1≤i≤n)。則有以下關(guān)系成立。=1\*GB3①當(dāng)i=1時，該結(jié)點為二叉樹的根。若i＞1，則該結(jié)點雙親結(jié)點的編號為[1／2]；=2\*GB3②當(dāng)2i+1＞n時，該結(jié)點無左孩子。否則，其左孩子的編號為2i。=3\*GB3③若2i+1＞n該結(jié)點無右孩子。否則，其右孩子編號為2i+1。3）二叉樹性質(zhì)的應(yīng)用：3、二叉樹的存儲結(jié)構(gòu)：1）順序存儲結(jié)構(gòu)該存儲結(jié)構(gòu)是把二叉樹的所有結(jié)點按照一定的次序存儲到計算機內(nèi)存中的一片連續(xù)存儲單元中。為此，必須把所有結(jié)點安排成一個適當(dāng)?shù)木€性序列，使得結(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系2）鏈?zhǔn)酱鎯Y(jié)構(gòu)由于樹形結(jié)構(gòu)比線性結(jié)構(gòu)更強調(diào)靈活的變化，所以一般情況下二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。此時，每個結(jié)點由三個域組成：數(shù)據(jù)域、左指針域、右指針域?；窘Y(jié)構(gòu)如下： publicclassnode {//學(xué)生信息樹結(jié)點 publicStudent_infoelem//數(shù)據(jù)元素 publicnodeLchild,Rchild;; //樹左右子樹指針}該鏈?zhǔn)酱鎯Y(jié)構(gòu)便于從根結(jié)點開始往下查找。但若需要查找雙親結(jié)點，則可增加一個指針指向雙親結(jié)點（此時稱為三叉鏈表），此時，結(jié)點的結(jié)構(gòu)形式為： publicclassnode {//學(xué)生信息樹結(jié)點 publicStudent_infoelem//數(shù)據(jù)元素 publicnodeLchild,Rchild，Parent; //樹左右子樹和父結(jié)點指針}4、二叉樹的遍歷：在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點，或者對樹中所有結(jié)點逐一進(jìn)行某種處理。這就提出來了遍歷二叉樹的問題，即：按照一定的規(guī)律訪問二叉樹上的每一個結(jié)點，且每個結(jié)點只能訪問一次。這里“訪問”的含義很廣，可以是對結(jié)點作某種處理。在線性結(jié)構(gòu)中，因為除尾結(jié)點外，每個結(jié)點都有唯一的后繼，所以只需從首結(jié)點開始，依次取后繼結(jié)點就可以遍歷線性結(jié)構(gòu)中的每個結(jié)點。但二叉樹是一種非線性結(jié)構(gòu)，每一個結(jié)點可能有兩個后繼，因此需要找到一種規(guī)律，將層次型的二叉樹轉(zhuǎn)換為一個線性序列。由二叉樹的遞歸定義可知，二叉樹由三個基本單元組成，即：根結(jié)點、左子樹、右子樹。因此，若能依次遍歷這三部分，便可以遍歷整個二叉樹。若以L，T，R分別表示遍歷左子樹、訪問根結(jié)點、遍歷右子樹，則有六種遍歷方案TLR，LTR，LRT，TRL，RTL，RLT。通常限定先遍歷左子樹，后遍歷右子樹。所以，二叉樹的遍歷主要指前三種。1）二叉樹遍歷遞歸算法（1）先序遍歷遞歸算法先序遍歷二叉樹的運算定義為：若二叉樹為空，則空操作；否則（1）訪問根結(jié)點。（2）先序遍歷左子樹。（3）先序遍歷右子樹。（2）中序遍歷遞歸算法中序遍歷二叉樹的運算定義為：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹。（2）訪問根結(jié)點。（3）中序遍歷右子樹。（3）后序遍歷遞歸算法后序遍歷二叉樹的運算定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹。（2）后序遍歷右子樹。（3）訪問根結(jié)點。2）二叉樹遍歷非遞歸算法3）二叉樹遍歷的簡單應(yīng)用【學(xué)法】自主學(xué)習(xí)、教師講解、課外習(xí)題練習(xí)【教學(xué)方法】媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】樹的基本概念、理解和特點（15分鐘）樹的相關(guān)術(shù)語和操作（20分鐘）二叉樹的相關(guān)概念（10分鐘）二叉樹的性質(zhì)（25分鐘）二叉樹性質(zhì)應(yīng)用（15分鐘）二叉樹的存儲方式（5分鐘）二叉樹的遍歷遞歸算法（30分鐘）二叉樹非遞歸算法（40分鐘）二叉樹遍歷的簡單應(yīng)用（15分鐘）。本章小結(jié)（5分鐘）【習(xí)題要求】1、學(xué)生獨立完成本章習(xí)題內(nèi)容，不允許抄襲。對抄襲者記0分或倒扣分處罰。2、嚴(yán)格按照考核內(nèi)容進(jìn)行評判。3、本次作業(yè)的成績，記錄學(xué)生期末總成績的2%4、附加思考題，可以列入本次作業(yè)的加分項，并記錄到學(xué)生期末總成績中?！緦嶒炓蟆繜o授課對象系別軟件技術(shù)系本次課學(xué)時6學(xué)時年級班次章節(jié)題目第8章查找（學(xué)生基本信息查找）目的要求(含技能要求)掌握查找的基本概念，應(yīng)用常用的查找方法實現(xiàn)學(xué)生基本信息的查找，并比較各種查找的效率。本節(jié)重點查找的基本概念，順序查找、折半查找、索引查找以及哈希查找實現(xiàn)。本節(jié)難點學(xué)生信息折半查找和哈希查找算法實現(xiàn)。教學(xué)方法項目教學(xué)法，任務(wù)驅(qū)動法，模仿學(xué)習(xí)法，“教學(xué)做”三位一體法教學(xué)用具多媒體教室、機房問題引入從學(xué)生基本信息查詢管理功能界面的講述入手，介紹簡單的學(xué)生基本信息查找的相關(guān)功能，以及實現(xiàn)的步驟。難點與重點講解方法以項目為引領(lǐng)，學(xué)生基本信息查找管理為任務(wù)驅(qū)動，將課堂講解、案例解學(xué)、模仿實作融為一體，進(jìn)行教學(xué)。本次課小節(jié)課程小節(jié)查找的基本概念學(xué)生基本信息順序查找的思想以及實現(xiàn)學(xué)生基本信息折半查找的思想以及實現(xiàn)學(xué)生基本信息索引查找的思想以及實現(xiàn)學(xué)生基本信息哈希查找的思想以及實現(xiàn)教后札記1、熟練掌握查找的相關(guān)概念。2、應(yīng)用常見的查找方法實現(xiàn)學(xué)生基本信息的查找。討論、思考題、作業(yè)(含實訓(xùn)作業(yè))見后第八章查找（學(xué)生基本信息查找）【學(xué)習(xí)目標(biāo)】能力目標(biāo)：（1）面向?qū)ο缶幊棠芰?。?）信息查找的分析能力。（3）應(yīng)用常用的查找方法實現(xiàn)學(xué)生信息查找的編程能力。（4）通過界面進(jìn)行業(yè)務(wù)類調(diào)用顯示的能力2．知識目標(biāo)：（1）查找的基本概念和分類；（2）順序查找的基本思想及其實現(xiàn)；（3）折半查找的基本思想及其實現(xiàn)；（4）索引查找的基本思想及其實現(xiàn)；（5）哈希查找的基本思想及其實現(xiàn)；；3．職業(yè)素質(zhì)目標(biāo)：★數(shù)據(jù)信息查找的邏輯思維能力★利用各種查找獨立思考解決問題能力★分小組進(jìn)行團(tuán)隊協(xié)作開發(fā)能力★創(chuàng)新能力【課前準(zhǔn)備】環(huán)境要求：PC電腦VisualStudio2005、SQLServer2000、MyEclipse學(xué)生要求：具備SQLServer數(shù)據(jù)庫理論知識和操作能力。具備面向?qū)ο蟪绦蛟O(shè)計C/S結(jié)構(gòu)開發(fā)能力。具有線性結(jié)構(gòu)的理論知識和操作能力。教師要求：能夠進(jìn)行三層結(jié)構(gòu)的C/S項目開發(fā)能力。具備一定的數(shù)據(jù)庫設(shè)計和分析能力。具有信息各種查找的設(shè)計知識和查找算法的編程能力。具備線性結(jié)構(gòu)和樹形結(jié)構(gòu)的理論知識和編程能力。【主要內(nèi)容】1、查找的基本概念1）查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合稱為查找表。查找表分為靜態(tài)查找表和動態(tài)查找表：靜態(tài)查找表：僅對查找表進(jìn)行查找操作，即查找關(guān)鍵字的等于給定值的數(shù)據(jù)元素是否在查找表中，查找前后不能改變表。動態(tài)查找表：對查找表除進(jìn)行查找操作外，可能還要向表中插入數(shù)據(jù)元素，或刪除表中數(shù)據(jù)元素的表。2）關(guān)鍵字?jǐn)?shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以標(biāo)識數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字；反之，把可以標(biāo)識若干記錄的關(guān)鍵字為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素只有一個數(shù)據(jù)項時，其關(guān)鍵字即為該數(shù)據(jù)元素的值。3）查找查找是指在查找表中查找一個其關(guān)鍵字值等于某一給定值的數(shù)據(jù)元素（或記錄）。若表中存在這樣一個數(shù)據(jù)元素（或記錄），則稱查找成功；若表中不存在關(guān)鍵字值等于給定值的數(shù)據(jù)元素（或記錄），則稱查找失敗，此時查找的結(jié)果可能給出一個“空”記錄或“空”指針。因為查找是對已存入計算機中的數(shù)據(jù)所進(jìn)行的操作，所以采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示查找表，即表中結(jié)點是按何種方式組織的。為了提高查找速度，我們經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來組織查找表。因此在研究各種查找算法時，我們首先必須清楚這些算法的數(shù)據(jù)結(jié)構(gòu)，特別是存儲結(jié)構(gòu)。查找有內(nèi)查找和外查找之分。若整個查找過程全部在計算機內(nèi)存中進(jìn)行，則稱之為內(nèi)查找；反之，若在查找過程中還需要訪問外存，則稱之為外查找。2、學(xué)生基本信息順序查找：1）算法思想：順序查找的基本思想是：從查找表的一端開始逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較，若找到一個記錄的關(guān)鍵字與給定值相等，則查找成功；若整個表中的記錄均比較過，仍未找到關(guān)鍵字等于給定值的記錄，則查找失敗。從學(xué)生信息表中數(shù)據(jù)可以得到，按姓名來進(jìn)行查找，沒有任何規(guī)律，即是無序的。我們只能從查找表開始逐個進(jìn)行查找。解決的思路如下：將整個學(xué)生成績表，以關(guān)鍵字姓名來看是無序的查找表。依次從查找表中取出一條記錄，將其中的姓名關(guān)鍵字與所要查找的關(guān)鍵字姓名K進(jìn)行比較。如果找到與給定值K一致的關(guān)鍵字，返回查找成功，否則繼續(xù)查找，若在查找表查找完畢仍未找到，返回查找失敗。2）算法流程圖：3）算法實現(xiàn)：學(xué)生基本信息順序表查找類實現(xiàn)。學(xué)生基本信息順序查找業(yè)務(wù)類的實現(xiàn)。4）順序查找時間復(fù)雜度的評價：3、學(xué)生基本信息折半查找：1）算法思想：首先：設(shè)查找表的元素存儲在一維數(shù)組r[1]…r[n]中，表中的元素已經(jīng)按學(xué)生序號關(guān)鍵字遞增（或遞減）的方式排好序。然后：將待查值k與有序表r[1]到r[n]的中點位置上的關(guān)鍵字r[mid].key進(jìn)行比較，比較結(jié)果有三種可能：若r[mid].key>k，說明若存在要查找的元素，該元素一定在數(shù)組的前半部分，從而查找范圍縮小了一半，修改查找范圍的上界n=mid-1，繼續(xù)對數(shù)組的前半部分進(jìn)行二分查找。若r[mid].key<k，說明若存在要查找的元素，該元素一定在數(shù)組的后半部分，從而查找范圍縮小了一半，修改查找范圍的下界為mid+1，繼續(xù)對數(shù)組的后半部分進(jìn)行二分查找。若r[mid].key=k，說明查找成功，mid所指元素即為要查找的數(shù)據(jù)。最后：這重復(fù)以上過程，查找范圍每次縮小1/2，當(dāng)查找范圍變?yōu)榭諘r，表示查找失敗。2）流程圖：3）算法實現(xiàn)：學(xué)生基本信息折半查找類實現(xiàn)。學(xué)生基本信息折半查找業(yè)務(wù)類的實現(xiàn)。4）折半查找時間復(fù)雜度的評價：4、學(xué)生基本信息索引查找1）索引查找思想：分塊查找又稱為索引查找，是對順序查找方法的一種改進(jìn)，其效率介于順序查找和折半查找之間。在索引查找過程中，首先將表分成若干塊，每一塊中的關(guān)鍵字不一定有序，但塊之間是有序的，即后一塊記錄的關(guān)鍵字均大于前一個塊中的最大關(guān)鍵字；此外還建立索引表，索引表按關(guān)鍵字有序。初看表中的學(xué)生語文成績數(shù)據(jù)，好像沒有什么規(guī)律可言，不能采用上節(jié)的折半查找來實現(xiàn)，只能利用順序查找來實現(xiàn)，當(dāng)數(shù)據(jù)量比較大時，查找效率不佳。仔細(xì)觀察數(shù)據(jù)可以發(fā)現(xiàn)，前5個成績小于60，中間8個在60到80之間，后面兩個大于80。我們可以采用如下的策略來設(shè)計查找：首先將學(xué)生成績表的數(shù)據(jù)分成三個區(qū)間<60;60~80,>80。其次，將所要查找的學(xué)生成績先鎖定在這三個區(qū)間當(dāng)中的一個。最后，再利用順序查找法，在所鎖定的區(qū)間進(jìn)行查找。2）索引查找流程圖：3）算法實現(xiàn)：學(xué)生基本信息索引查找類實現(xiàn)。學(xué)生基本信息索引查找業(yè)務(wù)類的實現(xiàn)。4）索引查找時間復(fù)雜度的評價：5、學(xué)生基本信息哈希查找1）算法思想：我們從所給的查找表中的數(shù)據(jù)，以關(guān)鍵字聯(lián)系電話，很難找到合理的規(guī)律。不能利用前面的二分查找和索引查找來解決問題。好像只能通過順序查找來解決問題，但順序查找很浪費時間，當(dāng)數(shù)據(jù)量很大時，一個個進(jìn)行比較，效率極低。我們注意觀察10個學(xué)生的電話號碼的末尾數(shù)各不相同，按電話號碼的末尾數(shù)由小到大組成新的查找表（例如末尾數(shù)為0，對應(yīng)新查找表下標(biāo)為0，末尾數(shù)為1，對應(yīng)新查找表下標(biāo)為1，……，末尾數(shù)為9，對應(yīng)下標(biāo)為9）。當(dāng)我們輸入要查找的電話號碼，取其末尾數(shù)與新查找表對應(yīng)的元素進(jìn)行比較（末尾數(shù)為0與下標(biāo)為0的元素比較，……，末尾數(shù)為9與下標(biāo)為9的元素比較）若相等則查找成功，否則查找失?。此斎氲碾娫捥柎a與對應(yīng)下標(biāo)的電話號碼不一致）?？梢娛褂眠@樣的查找方法只須作一次比較，就會等到結(jié)果，顯然效率大大提高。2）哈希查找算法流程圖3）學(xué)生基本信息哈希查找算法實現(xiàn)4）哈希查找的基本概念哈希表、哈希函數(shù)、哈希查找。5）構(gòu)建哈希函數(shù)的常用方法直接定址法、數(shù)字分析法、除留余數(shù)法、平均取中法、折疊法、基數(shù)轉(zhuǎn)換法、隨機數(shù)法6）解決哈希查找地址沖突的常用方法開放地址法：（1）線性探查法（2）二次探查法（3）隨機探查法鏈地址法：鏈地址法解決沖突的實例：7）哈希查找的性能分析。【學(xué)法】自主學(xué)習(xí)、教師講解、課題模仿練習(xí)、課外探討學(xué)習(xí)、課后習(xí)題和上機實驗【教學(xué)方法】項目教學(xué)+媒體教學(xué)講解+案例教學(xué)【教學(xué)實施】學(xué)生基本信息查找管理功能描述（5分鐘）查找的基本概念。（15分鐘）學(xué)生基本信息順序查找思想講解以及實現(xiàn)（15分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿進(jìn)行實體基本信息順序查找的實現(xiàn)（30分鐘）學(xué)生基本信息折半查找思想講解以及實現(xiàn)（15分鐘）學(xué)生根據(jù)所設(shè)計的實體，模仿進(jìn)行實體基本信息折半查