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