【正文】 return head。 } else { tempdata = num。 tempnext = NULL。 temppre = tail。 tailnext = temp。 tail = temp。 } } return head 。 } 雙向鏈表的操作 ? 雙向鏈表的遍歷 ? 有鏈?zhǔn)坠?jié)點(diǎn)，則可以沿著后繼指針從頭至尾遍歷 ? 有鏈尾節(jié)點(diǎn)，則可以沿著前驅(qū)指針從尾向頭遍歷 例子 7：編寫一個(gè)函數(shù)，輸出雙向鏈表中各節(jié)點(diǎn)的 data成員的值 void outputBidirList(node * head) { cout List: 。 node *curNode = head。 while ( curNode ) { if (curNode pre) cout 。 cout curNodedata。 if (curNode next) cout 。 curNode = curNode next。 } cout endl。 return。 } 雙向鏈表的操作 ? 在雙向鏈表中插入和刪除一個(gè)節(jié)點(diǎn) ? 優(yōu)點(diǎn)：獲取插入節(jié)點(diǎn)或被刪除節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)比較方便 ? 注意點(diǎn)：需要維護(hù)的指針較多 例子 8：編寫函數(shù)，將整數(shù) n插入到一個(gè)已排序的雙向鏈表中 (從小到大 ) node * insertData(int n, node * head) { node *curNode = head。 // 指向插入點(diǎn)的后節(jié)點(diǎn) node *preNode = NULL。 // 指向插入點(diǎn)的前節(jié)點(diǎn) node *newNode = NULL。 // 指向新建節(jié)點(diǎn) //尋找插入位置 while((curNode != NULL)amp。amp。(curNodedata n)) { preNode = curNode。 curNode = curNodenext。 } newNode = new node 。 // 為新節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存 if (newNode == NULL) {// 內(nèi)存分配不成功 cout Not memory available!。 return head。 } 例子 8：編寫函數(shù)，將整數(shù) n插入到一個(gè)已排序的雙向鏈表中 (從小到大 ) newNodedata = n。 if(preNode==NULL) { //鏈頭 newNodenext = curNode。 newNodepre = NULL。 if (curNode != NULL) curNodepre = newNode。 return newNode。 } if (curNode == NULL) { // 鏈尾 newNodepre = preNode。 preNodenext = newNode。 newNodenext = NULL。 return head。 } 例子 8：編寫函數(shù)，將整數(shù) n插入到一個(gè)已排序的雙向鏈表中 (從小到大 ) else {//鏈中 preNodenext = newNode。 newNodenext = curNode。 newNodepre = preNode。 curNodepre = newNode。 return head。 } } 例子 9：編寫函數(shù)，在雙向鏈表中查找并刪除指定 node * deleteData(int n, node * head) { node *curNode = head。 // 指向當(dāng)前節(jié)點(diǎn) while ( curNode amp。amp。 curNodedata != n) curNode = curNodenext。 if (curNode == NULL) { coutCan39。t find n endl。 return head。 } 例子 9：編寫函數(shù)，在雙向鏈表中查找并刪除指定 if (curNodepre == NULL) { head = headnext。 headpre = NULL。 } else { curNodeprenext = curNodenext。 if (curNodenext != NULL) curNodenextpre=curNodepre。 } delete curNode。 return head。 // 返回鏈?zhǔn)字羔? } 學(xué)習(xí)目的檢測(cè) ? 理解自引用結(jié)構(gòu)和鏈表的含義 ? 掌握通過動(dòng)態(tài)分配和釋放內(nèi)存來建立和維護(hù)鏈表 作業(yè) +上機(jī) ? ? ? 第 10章 面向?qū)ο蟪绦蛟O(shè)計(jì)基本概念 講授內(nèi)容 ? 面向?qū)ο蟪绦蛟O(shè)計(jì)方法的產(chǎn)生和發(fā)展 ? 面向?qū)ο蟪绦蛟O(shè)計(jì)語言 ? 面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn) ? 類和對(duì)象的基本概念 ? 消息 面向?qū)ο笳Z言和方法 (1/6) ? 六十年代末期 ——Simula 67（ 面向?qū)ο笳Z言的鼻祖 ） ? 包含了類和繼承的概念 ? 類 ——描述特性相同或相近的一組對(duì)象的結(jié)構(gòu)和行為 ? 繼承 ——將多個(gè)類組織成層次結(jié)構(gòu)，實(shí)現(xiàn)數(shù)據(jù)和操作的共享 面向?qū)ο笳Z言和方法 (2/6) ? 七十年代末八十年代初 ——Smalltalk（ 第一個(gè)真正的集成開發(fā)環(huán)境 ） ? 包含類和繼承，更嚴(yán)格的信息隱藏 ? 帶有一個(gè)巨大的、標(biāo)準(zhǔn)類庫(kù) ? 第一個(gè)使用 MVC(ModelViewController)模式開發(fā)交互式應(yīng)用軟件 面向?qū)ο笳Z言和方法 (3/6) ? Smalltalk使面向?qū)ο蠓椒槿藗冏⒛? ? 面向?qū)ο笳Z言被分為兩大陣營(yíng) ? 純粹的面向?qū)ο笳Z言： Smalltalk、Eiffel、 Java ? 混合型面向?qū)ο笳Z言： C++和 CLOS ? 基于對(duì)象的語言： Ada支持?jǐn)?shù)據(jù)抽象類型（包）、函數(shù)和運(yùn)算符重載、多態(tài)性，但不支持繼承 面向?qū)ο笳Z言和方法 (4/6) ? 結(jié)構(gòu)化程序設(shè)計(jì) ? 軟件的結(jié)構(gòu)化分析、設(shè)計(jì)方法 ? 工程化的概念的方法 ? 但無法很好地支持越來越復(fù)雜、龐大的系統(tǒng)需求 ? 面向?qū)ο蠓椒? ? 直接將問題的求解映射到問題本身上 ? 有目的地將系統(tǒng)分解為模塊 ? 將問題分解為一系列的實(shí)體（對(duì)象） ? 方便設(shè)計(jì)，可維護(hù)性、可擴(kuò)充性好 面向?qū)ο笳Z言和方法 (5/6) ? 簡(jiǎn)單的例子 ——圖書館管理系統(tǒng) ? 包含 reader（ 讀者）對(duì)象、 librarian（ 圖書管理員）對(duì)象、 bookshelf（ 書架）對(duì)象等 ? 所有的操作由各對(duì)象協(xié)作完成 ? 借書 ? reader對(duì)象向 librarian對(duì)象提出借書請(qǐng)求 ? librarian對(duì)象向 bookshelf對(duì)象提出查書和取書請(qǐng)求 ? 然后逐步響應(yīng)，逐步返回，共同完成借書操作 ? 萬物皆對(duì)象 面向?qū)ο笳Z言和方法 (6/6) ? 面向?qū)ο蠓椒ǖ囊恍┨匦? ? 程序設(shè)計(jì)的重點(diǎn)在數(shù)據(jù)而不是函數(shù) ? 程序由對(duì)象組成 ? 對(duì)象之間通過相互協(xié)作來完成功能 ? 大多數(shù)對(duì)象的定義以數(shù)據(jù)為中心 ? 函數(shù)與相關(guān)的數(shù)據(jù)緊密結(jié)合 ? 數(shù)據(jù)可以被隱藏 ? 很容易擴(kuò)充新的數(shù)據(jù)和函數(shù) 類、對(duì)象和消息 (1/10) ? 面向?qū)ο蟪绦蛟O(shè)計(jì)的一般步驟 ? 分析實(shí)際問題，分辨并抽取其中的類和對(duì)象 ? 設(shè)計(jì)相應(yīng)的類，并根據(jù)這些類創(chuàng)建各種對(duì)象 ? 協(xié)調(diào)這些對(duì)象完成程序功能（消息） 類、對(duì)象和消息 (2/10) ? 萬物皆對(duì)象 ? 每個(gè)學(xué)生、每個(gè)班級(jí)、每個(gè)學(xué)校、每個(gè)國(guó)家、每棵樹、每本書、每部汽車 ——具體的實(shí)體 ? “ 張三 ” 、 “ 李四 ” 都是對(duì)象 ，但“人”不是 ? “人”不是具體的實(shí)體，是類，是抽象概念 ? 類是某些對(duì)象共同特征的表示 ? 類是創(chuàng)建對(duì)象的模板，對(duì)象是類的實(shí)例 類、對(duì)象和消息 (3/10) ? 如何區(qū)分類和對(duì)象 ——以“人”和“張三”為例 ? “人”描述了所有人（包括“張三” ）都具有的屬性和行為，如有姓名、身高、體重，有鼻子、眼睛、四肢，能交流、能思維等等 ? 類（“人”）描述的概念是抽象的 ? “人”的姓名是什么？ ? “人”的身高是什么？ ? 對(duì)象（“張三”）是具體的 ? “張三”的姓名是“張三” ? “張三”的身高是 185CM 類、對(duì)象和消息 (4/10) ? 還有哪些類和對(duì)象的例子 ? 教室 ——301105教室 ? 國(guó)家 ——中國(guó) ? 學(xué)校 ——國(guó)防科技大學(xué) ? …… 例子：讀者類 Reader class Reader { public: Reader()。 //構(gòu)造函數(shù) int registration(char *name)。 //注冊(cè) int borrowBook(int bookNo)。 //借書 int returnBook(int bookNo)。 //還書 private: char *name。 //姓名 char *certifNo。 //借書證號(hào) }。 類、對(duì)象和消息 (5/10) ? 格式說明 ? 類的定義以關(guān)鍵字 class開頭 ? class后面是類名（ Reader） ? 類名后面花括號(hào)擴(kuò)起來的部分是類的體 ? 類的定義以分號(hào)結(jié)尾 類、對(duì)象和消息 (6/10) ? 內(nèi)容說明 ? 類的定義可以包含數(shù)據(jù)和函數(shù) ? 關(guān)鍵字 public后面定義了類的公有成員 ? 類 Reader有四個(gè)公有成員函數(shù)： Reader、registration（ 注冊(cè)）、 borrowBook（ 借書）和 returnBook（ 還書） ? 關(guān)鍵字 private后面定義的是類的私有成員 ? 類 Reader包含兩個(gè)私有數(shù)據(jù)成員，姓名（ name）和借書證號(hào)（ certifNo） ? 數(shù)據(jù)成員和成員函數(shù)都可以是私有的或公有的 類、對(duì)象和消息 (7/10) ? 自定義類是一種新的自定義類型，可以聲明變量、指針、數(shù)組等 ? 對(duì)象各自擁有自己的數(shù)據(jù)空間，互不干擾 Reader zhang。 //聲明 Reader類的對(duì)象 zhang Reader reader[1000]。 //聲明 Reader類的數(shù)組 Reader *rptr = amp。zhang。 //聲明 Reader類型的指針 Reader amp。ref = zhang。 //聲明 Reader類型的引用 類、對(duì)象和消息 (8/10) ? 對(duì)象可以響應(yīng)消息 ? 對(duì)象 zhang可以響應(yīng) registration（ 注冊(cè)）、 borrowBook（ 借書）和returnBook（ 還書）三種消息 ? 要對(duì)象 zhang借書可以向?qū)ο?zhang發(fā)borrowBook消息 ? 對(duì)象 zhang則通過執(zhí)行成員 borrowBook來響應(yīng)消息 類、對(duì)象和消息 (9/10) ? C++將“向?qū)ο蟀l(fā)消息”處理成“調(diào)用對(duì)象的某個(gè)成員函數(shù)” ? 調(diào)用對(duì)象 zhang的成員函數(shù)borrowBook (12)。 rpt?borrowBook(12)。 (12)。 類、對(duì)象和消息 (10/10) ? 消息機(jī)制的特性 ? 同一對(duì)象可以接收不同的消息，并有不同的響應(yīng)。如對(duì)象 zhang可接收注冊(cè)、借書、還書三種消息 ? 給不同對(duì)象發(fā)送同一消息會(huì)產(chǎn)生不同的效果。 ? 對(duì)消息的響應(yīng)不是必須的。對(duì)象可以響應(yīng)消息，也可以忽略某些消息 ? 對(duì)象之間是平等的，每個(gè)對(duì)象都可以向其它對(duì)象發(fā)消息，讓其為自己服務(wù) 面向?qū)ο蟪绦蛟O(shè)計(jì)特點(diǎn)(1/5) ? 抽象和封裝 ? 抽象 ——提取和表現(xiàn)事物的核心特性，不描述背景細(xì)節(jié) ? 類的定義是對(duì)實(shí)體的抽象和描述（定義類Reader時(shí)，要描述哪些特性？） ? 封裝 ——把數(shù)據(jù)及與數(shù)據(jù)相關(guān)的操作組織在一個(gè)單獨(dú)的程序單元（對(duì)象）中 ? 結(jié)構(gòu)清晰，對(duì)象之間的獨(dú)立性好，接口關(guān)系簡(jiǎn)單，可擴(kuò)充性和可維護(hù)性好 面向?qū)ο蟪绦蛟O(shè)計(jì)特點(diǎn)(2/5) ? 數(shù)據(jù)隱藏和訪問機(jī)制 ? 對(duì)象對(duì)內(nèi)部數(shù)據(jù)提供了不同級(jí)別的保護(hù) ? 對(duì)象私有的代碼和數(shù)據(jù)不能被外界直接訪問 ? 外界只