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

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