計算機軟件技術(shù)基礎(chǔ)教程（第二版）PPT完整全套教學課件

計算機軟件技術(shù)基礎(chǔ)教程全套PPT課件目錄第1章緒論第3章結(jié)構(gòu)化開發(fā)方法第4章面向?qū)ο蟮南到y(tǒng)分析和設(shè)計第2章軟件工程概述第6章數(shù)據(jù)結(jié)構(gòu)概述第5章并發(fā)程序開發(fā)技術(shù)第7章線性表第8章棧和隊列第10章樹第11章圖第9章數(shù)組第15章互聯(lián)網(wǎng)軟件開發(fā)實踐第12章排序第14章數(shù)據(jù)庫基本概念與應用程序設(shè)計第13章查找第1部分軟件技術(shù)基礎(chǔ)第2部分數(shù)據(jù)結(jié)構(gòu)第3部分軟件技術(shù)實踐第1部分軟件技術(shù)基礎(chǔ)

第一章緒論1.1計算機軟件及其發(fā)展1.計算機軟件計算機軟件是指計算機程序和與之相關(guān)的文檔資料的總和。計算機軟件概念示意圖文檔是指編制程序所使用的技術(shù)資料和使用該程序的說明性資料（使用說明書等），即開發(fā)、使用和維護程序所需的一切資料。1.1計算機軟件及其發(fā)展2.計算機軟件的分類計算機軟件種類繁多，概括起來分為兩類：系統(tǒng)軟件和應用軟件。系統(tǒng)軟件：指操作系統(tǒng)及其與之相關(guān)的各種軟件的總稱；應用軟件：指為用戶的特殊目的而開發(fā)的軟件。系統(tǒng)軟件包括操作系統(tǒng)、語言開發(fā)系統(tǒng)和測試工具等。操作系統(tǒng)：個人桌面、移動端、服務器、嵌入式等；語言開發(fā)系統(tǒng)：編譯型、解釋型和混合型等；測試工具：測試軟件正確性的工具。1.1計算機軟件及其發(fā)展3.計算機軟件的發(fā)展計算機軟件是在計算機軟件技術(shù)和硬件技術(shù)發(fā)展的前提下得到發(fā)展的，其發(fā)展過程主要是從以下兩條線索來體現(xiàn)的：計算機操作系統(tǒng)的發(fā)展過程；計算機軟件開發(fā)系統(tǒng)的發(fā)展過程。1.1計算機軟件及其發(fā)展計算機軟件開發(fā)系統(tǒng)的發(fā)展主要體現(xiàn)在計算機語言的發(fā)展過程中，它經(jīng)歷了以下四個階段：1)機器語言階段：計算機能夠執(zhí)行的指令是二進制形式的指令，這些指令組成了機器指令系統(tǒng)。2)匯編語言階段：為了幫助程序員擺脫記憶機器指令的困難，出現(xiàn)了用指令符號來代替機器指令的匯編指令3)高級語言階段4)面向?qū)ο笳Z言和可視化語言階段：為了給用戶提供方便的編程接口并提高編程效率，就出現(xiàn)了面向?qū)ο笳Z言和可視化語言。1.2計算機軟件技術(shù)1.計算機軟件的主要范疇

按照計分支學科的內(nèi)容劃分，計算機軟件技術(shù)相應有以下八個領(lǐng)域：軟件工程技術(shù)程序設(shè)計技術(shù)軟件工具環(huán)境技術(shù)系統(tǒng)軟件技術(shù)數(shù)據(jù)庫技術(shù)實時軟件技術(shù)網(wǎng)絡(luò)軟件技術(shù)與實際工作相關(guān)的軟件技術(shù)1.2計算機軟件技術(shù)2.計算機軟件技術(shù)的現(xiàn)狀在國內(nèi)，軟件技術(shù)也有了很大的發(fā)展，在軟件工程、軟件工具環(huán)境、并行處理算法、軟件形式化等方面都取得了一系列成果。另外，國產(chǎn)操作系統(tǒng)的研制、面向?qū)ο蠹夹g(shù)的研究、網(wǎng)絡(luò)互連技術(shù)和移動互聯(lián)網(wǎng)技術(shù)等方面的進展都呈現(xiàn)出一派欣欣向榮的景象。。3.計算機軟件技術(shù)的發(fā)展趨勢

隨著計算機科學基礎(chǔ)理論和計算機硬件技術(shù)的發(fā)展以及計算機應用的有力推動，計算機軟件技術(shù)還會不斷提出新的問題、新的方向。1.3軟件技術(shù)基礎(chǔ)作為非計算機專業(yè)的學生和計算機應用人員，應掌握以下幾種軟件技術(shù)：軟件工程的基本概念，程序設(shè)計方法和程序設(shè)計語言，算法和數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫基本概念與應用程序設(shè)計，計算機網(wǎng)絡(luò)基本概念與互聯(lián)網(wǎng)程序設(shè)計等，這些內(nèi)容就構(gòu)成了軟件技術(shù)基礎(chǔ)。根據(jù)上述的內(nèi)容規(guī)劃，本書主要包括了3個部分，第一部分是軟件技術(shù)基礎(chǔ)，第二部分是數(shù)據(jù)結(jié)構(gòu)，第三部分是軟件技術(shù)實踐。

計算機軟件技術(shù)基礎(chǔ)教程第二章軟件工程概述2.1軟件危機1.什么是軟件危機

軟件危機是指在計算機軟件開發(fā)過程中遇到的一系列問題，如開發(fā)周期延長，成本增加，可靠性降低等。

軟件危機包含與下列問題相關(guān)的問題：如何開發(fā)軟件?(2)怎樣做才能滿足對軟件不斷增長的需求?(3)如何維護現(xiàn)有的、容量又在不斷增加的軟件?

2.1軟件危機

軟件危機以許多問題為表征，例如：(1)對軟件成本、開發(fā)成本和開發(fā)進度的估計常常不很準確；(2)用戶對“已完成的”軟件系統(tǒng)不滿意的現(xiàn)象經(jīng)常發(fā)生；(3)軟件產(chǎn)品的質(zhì)量往往不可靠；(4)軟件常常是不可維護的；(5)軟件通常沒有適當?shù)奈臋n資料；(6)軟件成本在計算機系統(tǒng)總成本中所占的比例連年上升；(7)軟件開發(fā)生產(chǎn)率的提高速度遠遠跟不上計算機應用的普及和發(fā)展的趨勢。2.1軟件危機2.解決軟件危機的途徑解決軟件危機必須具有以下兩方面的支持：(1)技術(shù)支持，包括：①有關(guān)的軟件工程技術(shù)、程序設(shè)計方法、程序設(shè)計技術(shù)等；②計算機硬件知識、相關(guān)應用領(lǐng)域的知識、有關(guān)軟件開發(fā)歷史的知識等。2.1軟件危機(2)管理支持，即在開發(fā)軟件過程中如何組織和管理眾多的各類人員協(xié)同作業(yè)。但是，僅靠這些還不能解決軟件危機的根本問題。于是人們又提出了基于知識的軟件工程方法，力求將軟件工程與知識工程、人工智能技術(shù)結(jié)合起來，以構(gòu)造基于知識的軟件開發(fā)環(huán)境。這不是本書討論的重點。2.2軟件過程軟件過程是指軟件開發(fā)實踐中所執(zhí)行的一系列活動、動作和任務的集合。一個軟件項目的開發(fā)，從需求獲取，需求分析，設(shè)計，實現(xiàn)，測試，發(fā)布和維護應當遵循一系列可規(guī)范化的步驟，而軟件過程解決的就是“路線圖”的問題。2.2軟件過程階

段關(guān)鍵問題結(jié)

束

標

志問題定義問題是什么關(guān)于規(guī)模和目標的報告可行性研

究有可行的解嗎是否值得去解系統(tǒng)的實際模型，數(shù)據(jù)流圖（信息流動和處理情況），成本/效益分析需求分析系統(tǒng)必須做什么系統(tǒng)邏輯模型，數(shù)據(jù)流圖，數(shù)據(jù)字典，算法描述，需求說明書總體設(shè)計如何解決此問題可行的解法，系統(tǒng)流程圖，成本/效益分析，推薦的系統(tǒng)結(jié)構(gòu)，層次圖/結(jié)構(gòu)圖詳細設(shè)計如何實現(xiàn)此系統(tǒng)編碼的規(guī)格說明編碼和單元測試正確的程序模塊程序清單，單元測試方案和結(jié)果綜合測試符合要求的軟件綜合測試方案和結(jié)果，完整一致的系統(tǒng)配置軟件維護持久地滿足用戶完整準確的維護記錄，需求的軟件。生命周期方法學的階段任務2.2.2瀑布模型瀑布模型于1970年由溫斯頓.羅伊所(WintonRoyce)提出，是軟件工程最早的過程模型范例，在軟件工程中占有重要的地位。如右圖，瀑布模型基于軟件生命周期，其核心思想是按工序?qū)栴}化簡，采用預見性的方法，遵循預先計劃的需求、分析、設(shè)計、編程、測試的步驟順序進行，如同瀑布流水一般地自上而下。2.2.3增量模型增量模型是以迭代的方式進行的軟件開發(fā)過程。不同于瀑布式模型的順序性和依賴性，增量模型把軟件產(chǎn)品看作是由一系列的增量構(gòu)件組成，構(gòu)件的開發(fā)包括了設(shè)計、編程、集成和測試等任務，而且每個構(gòu)件由多個相互作用的模塊構(gòu)成，能夠完成特定的功能。一般情況下，第一個增量構(gòu)件需要實現(xiàn)軟件產(chǎn)品的基本需求，進而后面的增量構(gòu)件陸續(xù)提供附加特性和完善產(chǎn)品功能。增量模型的開發(fā)過程如圖2.2所示。2.2.5敏捷開發(fā)敏捷開發(fā)是一種循序漸進、快速響應和持續(xù)迭代的軟件開發(fā)方法。在敏捷開發(fā)中，以用戶不停進化的需求為導向，將軟件劃分成多個子項目，而每個子項目的成果是具有可視、可集成和可運行的軟件構(gòu)件。2.3軟件質(zhì)量的評價1.

可維護性軟件在運行階段尚需不斷“修正”，因為軟件雖經(jīng)測試但還不可避免地隱含著各種錯誤，這些錯誤在運行階段會逐步暴露出來，因而就要進行排錯。2.3軟件質(zhì)量的評價2.

可靠性可靠性通常包括正確性(Correctness)和健壯性(Robustness)這兩個相互補充的方面。正確性是指軟件系統(tǒng)本身沒有錯誤，所以在預期的環(huán)境條件下能夠正確地完成期望的功能。健壯性是指當系統(tǒng)遇到意外時(具體是什么意外，事先是很難預料的)，能按某種預定的方式作出適當?shù)奶幚?，能保護好重要的信息，隔離故障區(qū)，以防止事故蔓延等.2.3軟件質(zhì)量的評價3.

可理解性在相當長一段時間中，人們一直認為程序只是提供給計算機的，而不是給人閱讀的，所以只要它邏輯正確，計算機能按其邏輯正確執(zhí)行就足夠了，至于它是否易于被人理解則是無關(guān)緊要的。2.3軟件質(zhì)量的評價4.

效率效率是指系統(tǒng)能否有效地使用計算機資源，如時間和空間等。這一點以前一直是著重強調(diào)的，這是由于過去硬件價格昂貴造成的結(jié)果。由于以下一些原因，目前人們對效率的看法已有了變化。

計算機軟件技術(shù)基礎(chǔ)教程第三章結(jié)構(gòu)化開發(fā)方法3.1問題定義和可行性研究軟件開發(fā)一般涉及用戶和開發(fā)人員，即先由用戶提出問題，然后由軟件開發(fā)人員給出問題的解答。

但是，雙方交流時存在著隔閡。更有甚者，用戶本身也不知道他究竟要計算機做些什么。3.2需求分析在可行性研究的基礎(chǔ)上，就必須明確軟件系統(tǒng)必須“做什么”，并形成有關(guān)目標系統(tǒng)的需求說明書，這就是需求分析(RequirementAnalysis)。在軟件工程中，所謂“用戶要求”(或稱“需求”)是指軟件系統(tǒng)必須滿足的所有性質(zhì)和限制。用戶要求通常包括功能要求、性能要求、可靠性要求、安全保密要求、開發(fā)費用、開發(fā)周期以及可使用的資源等方面的限制，其中功能要求是最基本的，它又包括數(shù)據(jù)要求和加工要求兩方面。3.2需求分析

需求說明書主要有以下三個作用：(1)作為用戶和軟件人員之間的合同，為雙方相互了解提供基礎(chǔ)。(2)反映出問題的結(jié)構(gòu)，可以作為軟件人員進行設(shè)計和編程的基礎(chǔ)。(3)作為驗收的依據(jù)，即作為選取測試用例（如進行形式驗證）的依據(jù)。3.2需求分析3.2.1結(jié)構(gòu)化分析(SA方法)

由頂向下逐層分解3.2需求分析

用SA方法獲得的需求說明書由以下幾部分組成： (1)一套分層的數(shù)據(jù)流圖； (2)一本數(shù)據(jù)詞典； (3)一組小說明； (4)補充材料。3.2需求分析3.2.2數(shù)據(jù)流程圖

數(shù)據(jù)流圖主要用來描述目標系統(tǒng)的邏輯模型。SA方法采用“分解”的方式來理解一個復雜的系統(tǒng)，“分解”需要有描述的手段，數(shù)據(jù)流圖(DataFlowDiagram)就是作為描述“分解”的手段而引進的。3.2需求分析

數(shù)據(jù)流圖有四種基本成分：(1)數(shù)據(jù)流(用箭頭表示)；(2)加工(用圓表示)；(3)文件(用直線段表示)；(4)數(shù)據(jù)流的源點或終點(用方框表示)。3.2需求分析數(shù)據(jù)流

數(shù)據(jù)流“報名請求”由“姓名”、“年齡”、“性別”、“單位名”、“課程名”等成分組成，數(shù)據(jù)流“發(fā)票”由“姓名”、“單位名”、“金額”組成，它們的組成成分都是確定的。3.2需求分析

應該注意的是：數(shù)據(jù)流圖中描述的是數(shù)據(jù)流而不是控制流。下圖中“取下一張卡片”是一個控制流而不是數(shù)據(jù)流，因為并沒有任何數(shù)據(jù)沿著這個箭頭流動，所以這個箭頭應該從圖中刪去。習慣使用框圖(程序流程圖)的軟件人員特別應該注意不要犯這種錯誤。3.2需求分析2.加工

加工是對數(shù)據(jù)進行的操作。3.文件

文件是暫時存儲的數(shù)據(jù)。4.源點和終點

一個數(shù)據(jù)處理系統(tǒng)的內(nèi)部用數(shù)據(jù)流、文件和加工三種成分表示一般已足夠了，然而為了便于理解，有時還可以畫出數(shù)據(jù)流的源點和終點來說明它的來龍去脈。3.2需求分析3.2.3數(shù)據(jù)詞典1.數(shù)據(jù)詞典與數(shù)據(jù)流圖的聯(lián)系2.數(shù)據(jù)詞典條目的各種類型3.2需求分析3.2.4需求分析階段的其他工作

除了前面討論的工作之外，需求分析階段還應完成下列工作：1)確定設(shè)計限制2)確定驗收準則3)編寫“初步用戶手冊”4)復查需求說明書3.3總體設(shè)計軟件工程的分析階段的工作結(jié)果是需求說明書，它明確地描述了用戶要求軟件系統(tǒng)“做什么”。既然明確了“問題”，我們就可以著手尋求“問題的答案”，即建立一個符合用戶要求的軟件系統(tǒng)。總體設(shè)計是決定軟件的結(jié)構(gòu)，包括數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)(本章節(jié)只討論程序結(jié)構(gòu))。3.3總體設(shè)計3.3.1模塊化概念3.3.2模塊化設(shè)計方法3.3.3總體設(shè)計的其它工作3.4詳細設(shè)計詳細設(shè)計的主要任務1）為每個模塊進行詳細的算法設(shè)計；2）對模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進行設(shè)計；3）對數(shù)據(jù)庫進行物理設(shè)計，即確定數(shù)據(jù)庫的物理結(jié)構(gòu)；4）其他可能的設(shè)計，即代碼設(shè)計、輸入輸出格式設(shè)計和人機對話設(shè)計；5）編寫詳細的設(shè)計說明書；6）評審3.4詳細設(shè)計結(jié)構(gòu)化程序設(shè)計建立在BohmJacopini證明的結(jié)構(gòu)定理之上的，基本要點是：

1）采用自頂向下、逐步求精的程序設(shè)計方法；2）使用三種基本控制結(jié)構(gòu)構(gòu)造程序，避免使用GOTO語句。3.5軟件編程軟件編程(Coding)的任務是為每個模塊編寫程序，也就是說，將詳細設(shè)計的結(jié)果轉(zhuǎn)換為用某種程序設(shè)計語言編寫的程序，這個程序必須是無錯的，并且應有必要的內(nèi)部文檔和外部文檔?？紤]到讀者已經(jīng)具備了編程的知識和經(jīng)驗，本節(jié)不再討論怎樣編程，而是討論在軟件工程的背景下，怎樣編寫“良好的”程序。3.5軟件編程隨著軟件系統(tǒng)規(guī)模和復雜性的增加，人們逐步認識到程序經(jīng)常需要被人閱讀，而且閱讀程序是軟件開發(fā)工作中的一個重要環(huán)節(jié)。有人認為讀程序的時間恐怕比編寫程序的時間還要多。在這種背景下，人們開始認識到：程序?qū)嶋H上也是一種供人閱讀的“文章”，只不過它不是用自然語言而是用程序設(shè)計語言編寫而已。一個邏輯上雜亂無章的程序是沒有什么價值的，因為它無法供人閱讀，無法再利用。3.5軟件檢驗1.軟件測試的目的及原則軟件測試的主要手段有動態(tài)測試、靜態(tài)測試和正確性證明。軟件測試的目的是為了發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程；一個好的測試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯誤；一次成功的測試應該是發(fā)現(xiàn)了至今為止尚未發(fā)現(xiàn)的錯誤。

3.5軟件檢驗在軟件測試中應注意以下原則：1）測試用例應由輸入數(shù)據(jù)和預期的輸出數(shù)據(jù)兩部分組成。2）測試用例不僅選用合理的輸入數(shù)據(jù)，還要選擇不合理的輸入數(shù)據(jù)。3）除了檢查程序是否做了它應該做的事，還應該檢查程序是否做了他不應該做的事。4）應制定測試計劃并嚴格執(zhí)行，排除隨意性。5）長期保留測試用例。6）對發(fā)現(xiàn)較多錯誤的程序段，應進行更深入的測試。7）程序員避免測試自己的程序。3.5軟件檢驗2.動態(tài)測試動態(tài)測試是指通過運行程序發(fā)現(xiàn)錯誤。傳統(tǒng)的測試大多是動態(tài)測試。動態(tài)測試方法中根據(jù)測試用例的設(shè)計方法不同，分為黑盒測試和白盒測試兩類。

1）黑盒法。該方法把被測試對象看成一個黑盒子，測試人員完全不考慮程序內(nèi)部結(jié)構(gòu)和處理過程，只在軟件的接口處進行測試，依據(jù)需求規(guī)格說明書，檢查程序是否滿足功能要求。因此，黑盒測試又稱為功能測試或數(shù)據(jù)驅(qū)動測試。3.5軟件檢驗2）白盒法。

該方法把測試對象看作一個打開的盒子，測試人員須了解程序的內(nèi)部結(jié)構(gòu)和處理過程，以檢查處理過程的細節(jié)為基礎(chǔ)，對程序中盡可能多的邏輯路徑進行測試，檢驗內(nèi)部控制結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)是否有錯，實際的運行狀態(tài)和預期的狀態(tài)是否一致。白盒測試是結(jié)構(gòu)測試，被測對象基本上是源程序，以程序的內(nèi)部邏輯為基礎(chǔ)設(shè)計測試用例。3.5軟件檢驗3.靜態(tài)測試靜態(tài)測試指被測試程序不在機器上運行，而是采用人工檢測和計算機輔助靜態(tài)分析的手段對程序進行檢測，這種技術(shù)也稱評審。將評審過程與開發(fā)過程結(jié)合起來，是評審成為前一階段之后必須進行的步驟是一種評審方式。程序走查是另一種有效的評審方式。評審的目的是盡量快、盡量多地發(fā)現(xiàn)錯誤。3.5軟件檢驗4.正確性證明程序正確性證明是用某種方法確切地證明程序是沒有錯誤的，其最常用的方法是歸納斷言法。程序的正確性證明距離實用還有一段路要走。3.5軟件檢驗5.測試步驟測試過程通常分三步進行：

1）模塊測試（ModuleTesting）。又稱單元測試，指對源程序中每一個程序單元進行測試，檢查各個模塊是否正確實現(xiàn)規(guī)定的功能，從而發(fā)現(xiàn)模塊在編碼中或算法中的錯誤。

2）聯(lián)合測試（IntegrationTesting）。又稱集成測試，指在模塊測試的基礎(chǔ)上，將所有的模塊按照設(shè)計要求組裝成一個完整的系統(tǒng)進行的測試，它可以發(fā)現(xiàn)概要設(shè)計時的錯誤。

3）系統(tǒng)測試（SystemTesting）。系統(tǒng)測試將硬件、軟件和操作人員視為一個整體，檢驗它是否有不符合需求說明書的地方，可以發(fā)現(xiàn)設(shè)計和分析階段的錯誤。

計算機軟件技術(shù)基礎(chǔ)教程第四章面向?qū)ο蟮南到y(tǒng)分析和設(shè)計4.1面向?qū)ο蠹夹g(shù)概論

面向?qū)ο蠹夹g(shù)的概念和方法，本質(zhì)上是一種合理的思維方法，是不依賴于程序設(shè)計語言的應用軟件開發(fā)的基本核心技術(shù)。因此，要深刻理解C++語言和Java語言及其他面向?qū)ο蟮能浖_發(fā)技術(shù)，掌握面向?qū)ο缶幊?，首先應該學習面向?qū)ο蠹夹g(shù)的基本要點。越是深入理解面向?qū)ο蠹夹g(shù)的理論和方法，就越能讓您在自己的應用領(lǐng)域中最大限度地發(fā)揮思維能力和創(chuàng)造本領(lǐng)，也就越能高屋建瓴地掌握面向?qū)ο蟮能浖到y(tǒng)開發(fā)設(shè)計。4.1面向?qū)ο蠹夹g(shù)概論4.1.1引論軟件開發(fā)原理的變革

軟件工程技術(shù)的發(fā)展，其目的是提高計算機性能和應用范圍，其關(guān)鍵是提高軟件質(zhì)量和生產(chǎn)效率。從匯編語言到高級語言，標志著軟件工程技術(shù)和軟件生產(chǎn)率的一次質(zhì)的飛躍，促成這次飛躍的技術(shù)因素是編譯理論和實現(xiàn)方法的完善，使我們實現(xiàn)了從高級源碼到機器代碼的自動轉(zhuǎn)換。隨著應用需求的擴大和變化，軟件生產(chǎn)的方式和效率仍然遠遠跟不上社會發(fā)展的需要。2.面向?qū)ο笳Z言的三個里程碑4.1面向?qū)ο蠹夹g(shù)概論4.1.2面向?qū)ο蟮幕靖拍?.對象、類、消息2.封裝性、繼承性和多態(tài)性3.概念內(nèi)涵的區(qū)別4.1面向?qū)ο蠹夹g(shù)概論4.1.3面向?qū)ο蟮姆治龇椒?．OOA方法評介2．OOA步驟3．OOA模型4．OOA視圖5．OOA提交4.1面向?qū)ο蠹夹g(shù)概論4.1.4面向?qū)ο笤O(shè)計初步1．OOD模型

關(guān)于建立OOD模型，上一節(jié)已提到有多種方法。這里介紹的是有代表性的OOD方法，它是采用擴展OOA模型以得到OOD模型，即在將OOA模型橫向劃分為五個層次的基礎(chǔ)上，再將系統(tǒng)縱向劃分為四個部件：問題域部分、人機交互部分、任務管理部分、數(shù)據(jù)管理部分。4.1面向?qū)ο蠹夹g(shù)概論下面簡要介紹這個OOD體系結(jié)構(gòu)的各個部分：(1)問題論域部分，設(shè)計構(gòu)造一組為底層應用建立模型的類和對象，細化分析結(jié)果；(2)人機交互部分，設(shè)計一組有關(guān)類接口視圖的用戶模型的類和對象，設(shè)計用戶界面；(3)任務管理部分，確定系統(tǒng)資源的分配，設(shè)計用于系統(tǒng)中類的行為控制的對象／類；(4)數(shù)據(jù)管理部分，確定持久對象的存儲，將對象轉(zhuǎn)換成數(shù)據(jù)庫記錄或表格。4.1面向?qū)ο蠹夹g(shù)概論2.什么是優(yōu)良的OOD

在對OOD作進一步的討論之前，我們先說明一個優(yōu)良的OOD應具備的基本條件，這些也正是我們要努力達到的目標。

類和類的繼承必須具有高度凝集性；

類與類之間的耦合應該很松散。只有一個例外，具有類的繼承關(guān)系必須是緊密聯(lián)系的，因而子類與父類要緊密耦合；

某個類的數(shù)據(jù)實現(xiàn)細節(jié)對于別的類來說應該是隱藏的；4.1面向?qū)ο蠹夹g(shù)概論

（4）設(shè)計應該具有最優(yōu)的可重用性；

（5）盡力使類、對象和方法的定義具有簡單性；

（6）對所設(shè)計的類和類族，應注意保持其協(xié)議或接口的穩(wěn)定性；

（7）類的層次結(jié)構(gòu)設(shè)計規(guī)模適度，不要太深或太淺；

（8）系統(tǒng)整體規(guī)模要最小化。4.1面向?qū)ο蠹夹g(shù)概論4.復雜對象的構(gòu)造設(shè)計3.對象標識設(shè)計1）分類2）概括3）聚集5.實例一個GIS的OOD模型4.1面向?qū)ο蠹夹g(shù)概論4.2面向?qū)ο蟮南到y(tǒng)分析和系統(tǒng)設(shè)計

系統(tǒng)分析和設(shè)計的最終目標是推出一個可被接受的自動信息系統(tǒng).

該系統(tǒng)可用于以下幾種方式中的一種或多種：(1)應用于系統(tǒng)開發(fā)所期待的事務領(lǐng)域內(nèi)的軟件；(2)面向零售商、郵購客戶等進行出售的軟件；(3)應用于為一個事務所開發(fā)的產(chǎn)品內(nèi)部的軟件。4.2面向?qū)ο蟮南到y(tǒng)分析和系統(tǒng)設(shè)計

系統(tǒng)模型一般包括以下六個組成部分：系統(tǒng)輸入、處理過程、系統(tǒng)輸出、系統(tǒng)控制、系統(tǒng)響應和系統(tǒng)界面

4.2面向?qū)ο蟮南到y(tǒng)分析和系統(tǒng)設(shè)計

系統(tǒng)分析和設(shè)計(包含實施)的一個一般模型包括三個主要的要素：活動(分析、設(shè)計和實施)、活動中所涉及的人(客戶、信息技術(shù)人員)和輸入輸出(在圖中所有帶有標號的區(qū)域)。4.3系統(tǒng)分析方法1、OOA過程模型OOA過程應該包含以下步驟：(1)得到問題論域的初始化描述(問題敘述)。(2)識別對象，定義它們的類。(3)識別對象的內(nèi)部特征，創(chuàng)建數(shù)據(jù)字典(包含類、屬性和關(guān)聯(lián)的描述)：(4)識別對象的外部特征：(5)劃分主題，建立主題圖。(6)定義usecase，建立交互圖：(7)建立詳細說明。(8)原型開發(fā)。4.3系統(tǒng)分析方法1、OOA過程模型4.3系統(tǒng)分析方法2、研究問題論域及用戶需求3、對象識別客觀性方法4、識別對象的內(nèi)部特征5、識別對象的外部特征4.4系統(tǒng)設(shè)計階段和步驟在對系統(tǒng)進行詳細的分析之后，就可以轉(zhuǎn)入系統(tǒng)設(shè)計階段。系統(tǒng)設(shè)計是對問題的解和建立解法的高層決策。系統(tǒng)設(shè)計包括解決將整個系統(tǒng)劃分為子系統(tǒng)、確定子系統(tǒng)的軟件和硬件部分的分配、為詳細設(shè)計指定框架等問題。4.4系統(tǒng)設(shè)計階段和步驟1、系統(tǒng)劃分2、設(shè)計階段3、設(shè)計步驟4.4系統(tǒng)設(shè)計階段和步驟(1)將系統(tǒng)分層分割，細化成一系列子系統(tǒng)。(2)標識問題的一致性特性。(3)給子系統(tǒng)分配處理程序和任務。(4)根據(jù)數(shù)據(jù)結(jié)構(gòu)、文件和數(shù)據(jù)庫，為實現(xiàn)數(shù)據(jù)存儲選擇基本策略。(5)標識全局資源和確定控制訪問這些資源的機制。(6)選擇實現(xiàn)軟件控制方法：(7)考慮邊界條件。(8)建立交替使用的優(yōu)先權(quán)。在面向?qū)ο笙到y(tǒng)設(shè)計中，一般需要進行如下幾個步驟：4.4系統(tǒng)設(shè)計階段和步驟(1)將系統(tǒng)分層分割，細化成一系列子系統(tǒng)。(2)標識問題的一致性特性。(3)給子系統(tǒng)分配處理程序和任務。(4)根據(jù)數(shù)據(jù)結(jié)構(gòu)、文件和數(shù)據(jù)庫，為實現(xiàn)數(shù)據(jù)存儲選擇基本策略。(5)標識全局資源和確定控制訪問這些資源的機制。(6)選擇實現(xiàn)軟件控制方法：(7)考慮邊界條件。(8)建立交替使用的優(yōu)先權(quán)。在面向?qū)ο笙到y(tǒng)設(shè)計中，一般需要進行如下幾個步驟：4.5評審和修正OOA模型分析模型的一致性和完整性O(shè)OA模型的評審策略從OOA到OOD的過渡4.6系統(tǒng)文檔編制、實現(xiàn)和測試1、編制設(shè)計文檔一個完善的軟件系統(tǒng)，需要配備完善的文檔材料。在面向?qū)ο筌浖O(shè)計中，各個階段的成果都需要及時地以文檔的形式記錄出來，以方便下一階段的使用及為客戶、用戶或經(jīng)銷商服務。4.6系統(tǒng)文檔編制、實現(xiàn)和測試面向設(shè)計者的文檔的一般結(jié)構(gòu)4.6系統(tǒng)文檔編制、實現(xiàn)和測試2、系統(tǒng)實現(xiàn)

在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計之后，按照迭代的軟件開發(fā)過程，接下來的步驟便是依據(jù)分析和設(shè)計的成果實現(xiàn)該系統(tǒng)。采用面向?qū)ο筌浖O(shè)計方法進行開發(fā)的基于對象的系統(tǒng)的實現(xiàn)與傳統(tǒng)的結(jié)構(gòu)化程序的實現(xiàn)有很大的區(qū)別。4.6系統(tǒng)文檔編制、實現(xiàn)和測試3、系統(tǒng)測試系統(tǒng)級測試

對于系統(tǒng)級的測試，常用的測試方法有黑盒測試法和白盒測試法兩種。對象級測試

計算機軟件技術(shù)基礎(chǔ)教程第五章并發(fā)程序開發(fā)技術(shù)5.1并發(fā)程序開發(fā)技術(shù)自從計算機問世以來，就產(chǎn)生了“計算機程序”這一概念。在多道程序設(shè)計出現(xiàn)以前，計算機運行程序的最大特征是“順序性”。5.1并發(fā)程序開發(fā)技術(shù)程序的順序執(zhí)行具有如下特征：(1)順序性。(2)獨占性(3)封閉性。(4)可再現(xiàn)性。

若先執(zhí)行數(shù)據(jù)接收程序，則數(shù)據(jù)發(fā)送程序要一直等待數(shù)據(jù)接收程序結(jié)束，才能運行；反之亦然。5.1并發(fā)程序開發(fā)技術(shù)為了增強計算機系統(tǒng)的處理能力和提高各種資源的利用率，現(xiàn)代計算機系統(tǒng)中普遍采用了多道程序設(shè)計技術(shù)，其主要特征體現(xiàn)在以下方面：(1)并發(fā)性。(2)共享性(3)獨占性。(4)互相制約性。5.2進程和線程進程

進程是一個程序在給定的條件下對一組數(shù)據(jù)的一次動態(tài)執(zhí)行過程。進程具有以下基本特征：(1)動態(tài)性。(2)并發(fā)性。(3)獨立性。(4)異步性。(5)結(jié)構(gòu)性。

計算機軟件技術(shù)基礎(chǔ)教程第2部分數(shù)據(jù)結(jié)構(gòu)

目錄第1章緒論第3章結(jié)構(gòu)化開發(fā)方法第4章面向?qū)ο蟮南到y(tǒng)分析和設(shè)計第2章軟件工程概述第6章數(shù)據(jù)結(jié)構(gòu)概述第5章并發(fā)程序開發(fā)技術(shù)第7章線性表第8章棧和隊列第10章樹第11章圖第9章數(shù)組第15章互聯(lián)網(wǎng)軟件開發(fā)實踐第12章排序第14章數(shù)據(jù)庫基本概念與應用程序設(shè)計第13章查找第1部分軟件技術(shù)基礎(chǔ)第2部分數(shù)據(jù)結(jié)構(gòu)第3部分軟件技術(shù)實踐第六章數(shù)據(jù)結(jié)構(gòu)概述6.1數(shù)據(jù)結(jié)構(gòu)的引入

從提出一個實際問題到計算機解出答案，需要經(jīng)歷下列步驟：分析階段、設(shè)計階段、編碼階段和測試維護階段等。其中分析階段就是從實際問題中提取操作對象以及操作對象之間的關(guān)系。下面我們來看幾個例子。6.1數(shù)據(jù)結(jié)構(gòu)的引入

[例6.1]

計算機管理圖書目錄問題書名作者登錄號分類號出版日期定價Java語言李曉等9700001873.8792-991977/3/2643.5UNIX系統(tǒng)張昊9600012973.874-1261996/9/1923.5··················6.1數(shù)據(jù)結(jié)構(gòu)的引入

[例6.2]

計算機和人對弈問題6.1數(shù)據(jù)結(jié)構(gòu)的引入

[例6.3]

多叉路口交通燈管理問題6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.1引論什么是數(shù)據(jù)計算機處理的對象是數(shù)據(jù)，那么什么是數(shù)據(jù)呢？數(shù)據(jù)是客觀事物在計算機中的表示，是信息的載體，具有可識別性、可加工處理性和可存儲性等特征，是計算機程序加工處理的對象。可識別性是指計算機能夠識別數(shù)據(jù)，為此必須對客觀事物進行編碼；可存儲性是指數(shù)據(jù)能夠存儲在計算機的存儲設(shè)備上；可加工處理性是指計算機能夠以程序設(shè)計人員設(shè)計的算法，對數(shù)據(jù)進行加工處理，以得到預期的結(jié)果。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.2名詞定義數(shù)據(jù)(Data)是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，即數(shù)據(jù)這個集合中的一個個體（客體）。數(shù)據(jù)對象(DataObject)具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)是指數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.3數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容(1)研究數(shù)據(jù)元素之間固有的客觀聯(lián)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）。(2)研究數(shù)據(jù)在計算機內(nèi)部的存儲方法，即為數(shù)據(jù)的存儲結(jié)構(gòu)（StorageStructure），又稱物理結(jié)構(gòu)。(3)研究如何在數(shù)據(jù)的各種結(jié)構(gòu)（邏輯的和物理的）上施加有效的操作或處理（算法）。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.3數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容直接前趨與直接后繼學號姓名性別課名成績95001王麗女物理8195002劉建東男物理76···············95031陳立平男物理92學生成績表6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.3數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容綜上所述，我們可以將數(shù)據(jù)結(jié)構(gòu)定義為：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，應用計算機語言，可按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在該數(shù)據(jù)上定義了一個運算的集合。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.4數(shù)據(jù)的邏輯結(jié)構(gòu)分類通常我們將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有以下兩大類：1)線性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是有且僅有一個開始結(jié)點和一個終端結(jié)點，且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表就是一種典型的線性結(jié)構(gòu)。本書第7章到第8章介紹的都是線性結(jié)構(gòu)。2)非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。第9章到第11章介紹的都是非線性結(jié)構(gòu)。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.5存儲方法1.順序存儲方法2.鏈接存儲方法3.索引存儲方法4.散列存儲方法6.3關(guān)于算法的描述及算法分析6.3.1算法的概念算法是由若干條指令組成的有限序列，它必須滿足以下性質(zhì)：1.輸入性2.輸出性3.有窮性4.確定性5.可行性6.3關(guān)于算法的描述及算法分析6.3.2算法分析衡量一個算法的好壞，除其“正確性”外，還應考慮：(1)執(zhí)行算法所消耗的時間；(2)執(zhí)行算法所耗費的存儲空間，其中主要應考慮輔存量的大小；(3)其他諸如：算法是否易讀，是否易于調(diào)試、測試等。6.3關(guān)于算法的描述及算法分析6.3.2算法分析求兩個n階方陣的乘積C=A×B，下面是算法描述：＃definen自然數(shù)MATRIXMLT(A,B,C)FloatA[][n],B[][n],C[][n];{inti,j,k;(1) for(i=0;i<n;i++)n+1(2) for(j=0；j<n;j++)n(n+1)(3) {C[i][j]=0;n2(4) for(k=0;k<n;k++)n2(n+1)(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];}}n36.3關(guān)于算法的描述及算法分析6.3.2算法分析當我們評價一個算法的時間性能時，主要標準是算法時間復雜度的數(shù)量級，即算法的漸近時間復雜度。通常我們可以通過判定程序段中重復次數(shù)最多的語句的頻度來估算算法的時間復雜度。6.3關(guān)于算法的描述及算法分析6.3.2算法分析

計算機軟件技術(shù)基礎(chǔ)教程第七章線性表7.1線性表的基本概念及運算線性表是計算機程序設(shè)計中最常遇到的一種操作對象，也是數(shù)據(jù)結(jié)構(gòu)中最簡單、最重要的結(jié)構(gòu)形式之一。實際上，線性表結(jié)構(gòu)在程序設(shè)計中大量使用，它對我們來說并不是一個陌生的概念。在這一章里，我們將從一個新的角度來更加系統(tǒng)地討論它。7.1線性表的基本概念及運算7.1.1線性表的邏輯結(jié)構(gòu)定義學生成績登記表

線性表是由n（n≥0）個數(shù)據(jù)元素a1,a2,…,an構(gòu)成的有限序列。其中，將數(shù)據(jù)元素的個數(shù)n定義為表的長度。當n=0時稱為空表，通常將非空的線性表（n>0）記作：（a1,a2,…,an）。7.1線性表的基本概念及運算7.1.2線性表的運算1.置空表SETNULL(L)2.求長度LENGTH(L)3.取結(jié)點GET(L,i)4.定位LOCATE(L,x)5.插入INSERT(L,x,i)6.刪除DELETE(L,i)7.取直接前趨PRIOR(L,ai)8.取直接后繼NEXT(L,ai)7.1線性表的基本概念及運算7.1.2線性表的運算[例7.1]利用線性表的基本運算清除表Ｌ中多余的重復結(jié)點。7.1線性表的基本概念及運算7.1.2線性表的運算PURGE(L) /*刪除線性表Ｌ中重復出現(xiàn)的多余結(jié)點*/Linear_list*L; {inti=1,j,x,y; while(i<LENGTH(L))/*每次循環(huán)使當前第i個結(jié)點是無重復值的結(jié)點*/{x=GET(L,i);/*取當前第i個結(jié)點*/j=i+1;while(j<=LENGTH(L)){y=GET(L,j); /*取當前第j個結(jié)點*/if(x==y)DELETE(L,j); /*刪除當前第j個結(jié)點*/elsej++;}i++;}} /*PURGE*/7.2線性表的順序存儲結(jié)構(gòu)7.2.1順序表Loc?(ai+1)=Loc?(ai)+cLoc?(ai)=Loc?(a1)+(i1)c1≤i≤n7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運算1．插入運算2.刪除運算7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運算1．插入運算我們在線性表的第i?(1≤i≤n+1)個位置上，插入一個

新結(jié)點x，使長度為n的線性表

（a1,…,ai1,ai,…,an）變成長度為n+1的線性表

（a1,…,ai1,x,ai,…,an）7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運算1．插入運算7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運算2．刪除運算線性表的刪除運算是指將表的第i（1≤i≤n）個結(jié)點

刪去，使長度為n的線性表

（a1,…,ai1,ai,ai+1,…,an）變成長度為n1的線性表

（a1,…,ai1,ai+1,…,an）7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運算2．刪除運算7.3線性表的鏈式存儲結(jié)構(gòu)上一節(jié)研究了線性表的順序存儲結(jié)構(gòu)，它的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰。這一特點使得順序表具有如下的優(yōu)缺點，其優(yōu)點是：可以隨機存取表中任意元素；其存儲位置可用一個簡單直觀的公式來表示。然而，這一特點也鑄成了這種存儲結(jié)構(gòu)的三個缺點：第一，在進行插入或刪除運算時，需移動大量元素；第二，在給長度變化較大的線性表預先分配空間時，必須按最大空間分配，使存儲空間不能得到充分利用；第三，表的容量難以擴充。7.3線性表的鏈式存儲結(jié)構(gòu)為了克服順序表的缺點，可以采用鏈接方式存儲線性表，通常我們將鏈接方式存儲的線性表稱為鏈表（LinkedList）。從實現(xiàn)的角度看，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表。靜態(tài)鏈表是順序的存儲結(jié)構(gòu)，在物理地址上是連續(xù)的，而且需要預先分配地址空間大小。所以靜態(tài)鏈表的初始長度一般是固定的，在做插入和刪除操作時不需要移動元素，僅需修改指針。動態(tài)鏈表是用內(nèi)存申請函數(shù)動態(tài)申請內(nèi)存的，所以在鏈表的長度上沒有限制。動態(tài)鏈表因為是動態(tài)申請內(nèi)存的，所以每個節(jié)點的物理地址不連續(xù)，要通過指針來順序訪問。7.3線性表的鏈式存儲結(jié)構(gòu)7.3.1單鏈表結(jié)點結(jié)構(gòu)：data域：數(shù)據(jù)域next域：指針域7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算1．建立單鏈表 1）頭插法建表 2）尾插法建表2．插入及刪除運算 1）插入運算 2）刪除運算2．查找運算 1）按序號查找 2）按值查找7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算1.建立單鏈表-頭插法建表7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算linklistCREATLISTF(){charch; /*逐個輸入字符，以“$”為結(jié)束符，返回單鏈表頭指針*/linklisthead,s;head=NULL; /*鏈表開始為空*/ch=getchar(); /*讀入第一個結(jié)點的值*/while(ch!='$'){s=(linklist)malloc(sizeof(linklist));/*生成新結(jié)點*/s－>data=ch; /*將輸入數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中*/s－>next=head;head=s; /*將新結(jié)點插入到表頭上*/ch=getchar(); /*讀入下一個結(jié)點的值*/}returnhead; /*返回鏈表頭指針*/} /*CREATLISTF*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算1.建立單鏈表-尾插法建表7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算linklistCREATLISTR()/*尾插法建立單鏈表，返回表頭指針*/{charch;linklisthead,s,r;head=NULL;/*鏈表初值為空*/r=NULL;/*尾指針初值為空*/ch=getchar();/*讀入第一個結(jié)點值*/while(ch!=′$′)/*以“$”為輸入結(jié)束符*/{s=(linklist)malloc(sizeof(linklist));/*生成新結(jié)點s*/s－>data=ch;if(head==NULL)head=s;/*新結(jié)點s插入空表*/elser－>next=s;/*非空表，新結(jié)點s插入到尾結(jié)點*/ r=s;/*尾指針r指向新的表尾*/ch=getchar(?);/*讀入下一結(jié)點值*/}if(r!=NULL)r－>next=NULL;/*對非空表，將尾結(jié)點的指針域置空*/returnhead;/*返回單鏈表頭指針*/} 7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算簡化后的尾插法-附加頭節(jié)點7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算linklistCREATLISTR1()/*尾插入法建立帶頭結(jié)點的單鏈表，返回表頭指針*/{charch;linklisthead,s,r;head=(linklist)malloc(sizeof(linklist));/*生成頭結(jié)點head*/r=head;

/*尾指針指向頭結(jié)點*/ch=getchar();while(ch!=′$′) /*“$”為輸入結(jié)束符*/{s=(linklist)malloc(sizeof(linklist));

/*生成新結(jié)點*s*/s－>data=ch;r－>next=s; /*新結(jié)點插入表尾*/r=s; /*尾指針r指向新的表尾*/ch=getchar(); /*讀入下一個結(jié)點的值*/}r－>next=NULL;returnhead; /*返回表頭指針*/} /*CREATLISTR1*/簡化后的尾插法-附加頭節(jié)點7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算2.插入與刪除-插入運算7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算2.插入與刪除-插入運算INSERTAFTER?(linklistp,datatypex) /*將值為x的新結(jié)點插入p之后*/{linklists;s=(linklist)?malloc?(sizeof?(linklist)); /*生成新結(jié)點s*/s－>data=x;s－>next=p－>next;p－>next=s;/*將*s插入*p之后*/} /*INSERTAFTER*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算[例7.2]

在單鏈表上，將值為x的新結(jié)點插入在結(jié)點p前。7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算/*在帶頭結(jié)點的單鏈表head中，將值為x的新結(jié)點插入p之前*/INSERTBEFORE(linklisthead,linklistp,datatypex){linklists,q;s=(linklist)malloc(sizeof(linklist)); /*生成新結(jié)點*s*/s－>data=x;q=head; /*從頭指針開始*/while(q－>next!=p)q=q－>next;/*查找p的前趨結(jié)點q*/s－>next=p;q－>next=s;/*將新結(jié)點s插入p之前*/} /*INSERTBEFORE*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算[例7.3]

在單鏈表上實現(xiàn)線性表的插入運算INSERT(L,x,i)。INSERT(linklistL,datatypex,inti){linklistp;intj;j=i1;p=GET(L,j); /*找第i1個結(jié)點p*/if(p==NULL)print(″error″); /*i<1或i>(n+1)*/elseINSERTAFTER(p,x);/*將值為x的新結(jié)點插到p之后*/} /*INSERT*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算2.插入與刪除-刪除運算7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算2.插入與刪除-刪除運算DELETE(linklistp,linklisthead)/*刪去單鏈表head的結(jié)點p*/{linklistq;q=head;while(q－>next!=p)q=q－>next;/*查找p的前趨結(jié)點q*/q－>next=p－>next; /*刪除結(jié)點p*/free(p); /*釋放結(jié)點p*/} /*DELETE*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算[例7.4]

在單鏈表上實現(xiàn)線性表的刪除運算DELETE(L,i)。DELETE(linklistL,inti)/*刪去帶頭結(jié)點的單鏈表L的第i個結(jié)點*/{linklistp,r;intj;j=i1;p=GET(L,j); /*找到第i1個結(jié)點*/if((p!=NULL)&&(p－>next!=NULL)){r=p－>next; /*r為結(jié)點p的后繼*/p－>next=r－>next; /*將結(jié)點r從鏈表上摘下*/free(r); /*釋放結(jié)點r*/}else /*i<1或i>n*/printf(″error″)} /*DELETE*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算[例7.5]

將兩個遞增單鏈表合并為一個遞增單鏈表，要求不另開辟空間。UNION(linklistla,linklistlb);/*合并遞增單鏈表la和lb*/{linklistp,q,r,u;p=la－>next;q=lb－>next;r=la; /**r為*p的直接前趨*/while((p!=NULL)&&(q!=NULL)){if(p－>data>q－>data){u=q－>next;r－>next=q;r=q;q－>next=p;q=u;}else{r=p;p=p－>next;}}if(q!=NULL)r－>next=q;} /*UNION*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算3.查找運算-按序號查找/*在帶頭結(jié)點的單鏈表head中查找第i個結(jié)點，若找到，則返回該結(jié)點的存儲位置；否則返回NULL*/linklistGET(linklisthead,inti){intj;linklistp;p=head;j=0; /*從頭結(jié)點開始掃描*/while((p－>next!=NULL)&&(j<i)){p=p－>next; /*掃描下一個結(jié)點*/j++; /*已掃描結(jié)點計數(shù)器*/}if(i==j)returnp; /*找到了第i個結(jié)點*/elsereturnNULL; /*找不到，i≤0或i>n*/} /*GET*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.2單鏈表的基本運算3.查找運算-按值查找/*在帶頭結(jié)點的單鏈表head中查找其結(jié)點值等于key的結(jié)點，若找到則返回該結(jié)點的位置p；否則返回NULL*/linklistLOCATE(linklisthead,datatypekey){linklistp; p=head－>next; /*從開始結(jié)點比較*/while(p!=NULL)if(p－>data!=key)p=p－>next; /*沒找到，繼續(xù)循環(huán)*/if(p==NULL)returnNULL;elsereturnp;

/*找到結(jié)點key，退出循環(huán)*/} /*LOCATE*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.3循環(huán)鏈表單循環(huán)鏈表7.3線性表的鏈式存儲結(jié)構(gòu)7.3.3循環(huán)鏈表僅設(shè)尾指針rear的單循環(huán)鏈表7.3線性表的鏈式存儲結(jié)構(gòu)7.3.3循環(huán)鏈表[例7.6]

在循環(huán)鏈表的第i個元素之后插入元素x。INSERT(linklisthead,datatypex,inti)/*在循環(huán)鏈表第i個元素之后插入元素x*/{linklists; intj;s=(linklist)malloc(sizeof(linklist));s－>data=x; /*生成值為x的新結(jié)點*/p=head;j=0;while((p－>next!=head)&&(j<i)){p=p－>next;j++;}if(i=j){s－>next=p－>next;p－>next=s;}/*插入操作*/elseprintf(″error″);} /*INSERT*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.3循環(huán)鏈表[例7.7]

一元多項式的表示及相加。多項式結(jié)點形式多項式的循環(huán)鏈式存儲結(jié)構(gòu)7.3線性表的鏈式存儲結(jié)構(gòu)7.3.3循環(huán)鏈表polynode*polyadd(polynodepa,polynodepb); /*多項式相加運算A=A+B*/{polynodep,q,r,s; folatx; p=pa－>next;q=pb－>next; s=pa; /**s為*p的直接前趨*/ while((p!=pa)&&(q!=pb)) {if(p－>exp<q－>exp){s=p;p=p－>next;} /*p指針后移*/if(p－>exp>q－>exp){r=q－>next;q－>next=p;s－>next=q;s=q;q=r;}else{x=p－>coef+q－>coef;if(x!=0){p－>coef=x;s=p;}else{s－>next=p－>next;free(p)}p=s－>next;r=q;q=q－>next;free(r);}}if(q!=qb)s－>next=q; /*將B中剩余結(jié)點鏈入多項式A中*/} /*polyadd*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.4雙向鏈表typedefstructdnode{datatypedata;structdnodeprior,next;}dlinklist;dlinklisthead;7.3線性表的鏈式存儲結(jié)構(gòu)7.3.4雙向鏈表

雙循環(huán)鏈表示意圖7.3線性表的鏈式存儲結(jié)構(gòu)7.3.4雙向鏈表雙向鏈表上刪除結(jié)點*p刪除算法描述如下：DELETENODEP(dlinklistp)/*刪除雙向鏈表結(jié)點*p*/{p－>prior－>next=p－>next;p－>next－>prior=p－>prior; free(p);} /*DELETENODEP*/7.3線性表的鏈式存儲結(jié)構(gòu)7.3.4雙向鏈表雙向鏈表上的前插操作插入算法描述如下：DINSERTBEFORE(dlinklistp,datatypex)/*在結(jié)點p之前插入值為x的結(jié)點*/{dlinklists; s=(dlinklist)malloc(sizeof(dlinklist)); s－>data=x;s－>prior=p－>prior;s－>next=p; p－>prior－>next=s;p－>prior=s;} /*DINSERTBEFORE*/7.3線性表的鏈式存儲結(jié)構(gòu)以上詳細介紹了線性表及其兩種存儲結(jié)構(gòu)，在實際應用中究竟如何選擇，主要根據(jù)具體問題的要求和性質(zhì)，再結(jié)合順序和鏈式兩種存儲結(jié)構(gòu)的特點來決定，通常從以下幾方面考慮：1）存儲空間2）運算時間3）程序設(shè)計語言

計算機軟件技術(shù)基礎(chǔ)教程第八章棧和隊列8.1棧8.1.1棧的基本概念及其運算8.1棧8.1.1棧的基本概念及其運算(1)置空?！猄etNull(S)，完成對棧的初始化。(2)判斷棧是否為空—Empty(S)，若棧S為空，則返回真；否則，返回假。(3)進棧—Push(S，e)，在棧S的棧頂插入數(shù)據(jù)元素e。(4)出棧—Pop(S)，刪除棧S的棧頂數(shù)據(jù)元素，并把出棧數(shù)據(jù)元素返回。(5)取棧頂元素—GetTop(S)，取棧S的棧頂數(shù)據(jù)元素，并把數(shù)據(jù)元素返回。該操作完成后，棧的狀態(tài)不變。8.1棧8.1.2棧的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)2.鏈式存儲結(jié)構(gòu)8.1棧8.1.2棧的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)--順序棧structStack{ datatypeelements[maxsize]； intTop；}其中，maxsize是棧的容量，datatype是棧中數(shù)據(jù)元素的數(shù)據(jù)類型，Top指示當前棧頂位置，棧底位置為0。8.1棧8.1.2棧的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)--順序棧8.1棧8.1.2棧的存儲結(jié)構(gòu)(1)置空棧：將棧進行初始化，主要是將棧頂指針Top初始化為–1。voidSetNuLLS(structStack*S){ S－>Top=–1；} /SetNuLLS/(2)判斷棧是否為空：在進行出棧操作時，首先必須判斷棧不為空，否則會出錯。intEmptyS(structStack*s){ if(S－>Top>=0)return(0)； elsereturn(1)；} /*EmptyS*/8.1棧8.1.2棧的存儲結(jié)構(gòu)(3)進棧：將數(shù)據(jù)元素E插入棧頂。

structStack*PushS(structStack*S,datatypeE){if(S－>Top>=maxsize-1){printf("StackOverflow")； /

上溢現(xiàn)象。/return(NULL)；}else{S－>Top++； S－>elements[S－>Top]=E；

}return(s)；} /*PushS*/8.1棧8.1.2棧的存儲結(jié)構(gòu)(4)出棧：首先判斷棧是否為空，若空則表示下溢，否則刪除棧頂數(shù)據(jù)元素。datatypePOPS(structStack*S){datatype*temp; if(EmptyS(S)){printf("StackUnderflow")；return?(NULL)；}else{STop--; temp=(datatype*)malloc(sizeof(datatype));*temp=S－>elements[S－>Top+1];return(temp);}}/*PopS*/8.1棧8.1.2棧的存儲結(jié)構(gòu)(5)取棧頂元素：只把棧頂元素的值取出，而不調(diào)整棧頂指針Top的值。datatype*GetTopS(structStack*S){datatype*temp;if(EmptyS(S)){printf("Stackisempty")；return?(NULL)；}else{temp=(datatype*)malloc(sizeof(datatype));*temp=S－>elements[S－>Top];return?(temp);}} /*GetTopS*/8.1棧8.1.2棧的存儲結(jié)構(gòu)2.鏈式存儲結(jié)構(gòu)—鏈棧8.1棧8.1.2棧的存儲結(jié)構(gòu)2.鏈式存儲結(jié)構(gòu)—鏈棧鏈棧定義如下：structNode{datatypeelement; structNode*next;};structNode*top;8.1棧8.1.2棧的存儲結(jié)構(gòu)voidPUSHL(structNode*S,datatypeE){structNode*p; /*進棧*/p=(structNode*)malloc(1,sizeof(structNode));p－>element=E;p－>next=S;S=p;}top鏈棧的進棧操作8.1棧8.1.2棧的存儲結(jié)構(gòu)top

datatypePOPL(structNode*S) /*出棧*/{datatype*X; if(S==NULL){printf("Stackisunderflow"); return(NULL);}else{ X=(datatype*)