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

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

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

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

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

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

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

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

2.1軟件危機(jī)

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

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

束

標(biāo)

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

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

可維護(hù)性軟件在運(yùn)行階段尚需不斷“修正”，因?yàn)檐浖m經(jīng)測(cè)試但還不可避免地隱含著各種錯(cuò)誤，這些錯(cuò)誤在運(yùn)行階段會(huì)逐步暴露出來，因而就要進(jìn)行排錯(cuò)。2.3軟件質(zhì)量的評(píng)價(jià)2.

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

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

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

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

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

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

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

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

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

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

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

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

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

文件是暫時(shí)存儲(chǔ)的數(shù)據(jù)。4.源點(diǎn)和終點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

在對(duì)OOD作進(jìn)一步的討論之前，我們先說明一個(gè)優(yōu)良的OOD應(yīng)具備的基本條件，這些也正是我們要努力達(dá)到的目標(biāo)。

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

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

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

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

（5）盡力使類、對(duì)象和方法的定義具有簡(jiǎn)單性；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[例6.1]

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

[例6.2]

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

[例6.3]

多叉路口交通燈管理問題6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.1引論什么是數(shù)據(jù)計(jì)算機(jī)處理的對(duì)象是數(shù)據(jù)，那么什么是數(shù)據(jù)呢？數(shù)據(jù)是客觀事物在計(jì)算機(jī)中的表示，是信息的載體，具有可識(shí)別性、可加工處理性和可存儲(chǔ)性等特征，是計(jì)算機(jī)程序加工處理的對(duì)象?？勺R(shí)別性是指計(jì)算機(jī)能夠識(shí)別數(shù)據(jù)，為此必須對(duì)客觀事物進(jìn)行編碼；可存儲(chǔ)性是指數(shù)據(jù)能夠存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)設(shè)備上；可加工處理性是指計(jì)算機(jī)能夠以程序設(shè)計(jì)人員設(shè)計(jì)的算法，對(duì)數(shù)據(jù)進(jìn)行加工處理，以得到預(yù)期的結(jié)果。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.2名詞定義數(shù)據(jù)(Data)是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，即數(shù)據(jù)這個(gè)集合中的一個(gè)個(gè)體（客體）。數(shù)據(jù)對(duì)象(DataObject)具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(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ù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)方法，即為數(shù)據(jù)的存儲(chǔ)結(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)容直接前趨與直接后繼學(xué)號(hào)姓名性別課名成績(jī)95001王麗女物理8195002劉建東男物理76···············95031陳立平男物理92學(xué)生成績(jī)表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ù)，應(yīng)用計(jì)算機(jī)語言，可按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在該數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.4數(shù)據(jù)的邏輯結(jié)構(gòu)分類通常我們將數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有以下兩大類：1)線性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一種典型的線性結(jié)構(gòu)。本書第7章到第8章介紹的都是線性結(jié)構(gòu)。2)非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。第9章到第11章介紹的都是非線性結(jié)構(gòu)。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.5存儲(chǔ)方法1.順序存儲(chǔ)方法2.鏈接存儲(chǔ)方法3.索引存儲(chǔ)方法4.散列存儲(chǔ)方法6.3關(guān)于算法的描述及算法分析6.3.1算法的概念算法是由若干條指令組成的有限序列，它必須滿足以下性質(zhì)：1.輸入性2.輸出性3.有窮性4.確定性5.可行性6.3關(guān)于算法的描述及算法分析6.3.2算法分析衡量一個(gè)算法的好壞，除其“正確性”外，還應(yīng)考慮：(1)執(zhí)行算法所消耗的時(shí)間；(2)執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要應(yīng)考慮輔存量的大?。?3)其他諸如：算法是否易讀，是否易于調(diào)試、測(cè)試等。6.3關(guān)于算法的描述及算法分析6.3.2算法分析求兩個(gè)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算法分析當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)是算法時(shí)間復(fù)雜度的數(shù)量級(jí)，即算法的漸近時(shí)間復(fù)雜度。通常我們可以通過判定程序段中重復(fù)次數(shù)最多的語句的頻度來估算算法的時(shí)間復(fù)雜度。6.3關(guān)于算法的描述及算法分析6.3.2算法分析

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

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

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

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

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

刪去，使長(zhǎng)度為n的線性表

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

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

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

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

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

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

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

將兩個(gè)遞增單鏈表合并為一個(gè)遞增單鏈表，要求不另開辟空間。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線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算3.查找運(yùn)算-按序號(hào)查找/*在帶頭結(jié)點(diǎn)的單鏈表head中查找第i個(gè)結(jié)點(diǎn)，若找到，則返回該結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL*/linklistGET(linklisthead,inti){intj;linklistp;p=head;j=0; /*從頭結(jié)點(diǎn)開始掃描*/while((p－>next!=NULL)&&(j<i)){p=p－>next; /*掃描下一個(gè)結(jié)點(diǎn)*/j++; /*已掃描結(jié)點(diǎn)計(jì)數(shù)器*/}if(i==j)returnp; /*找到了第i個(gè)結(jié)點(diǎn)*/elsereturnNULL; /*找不到，i≤0或i>n*/} /*GET*/7.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算3.查找運(yùn)算-按值查找/*在帶頭結(jié)點(diǎn)的單鏈表head中查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p；否則返回NULL*/linklistLOCATE(linklisthead,datatypekey){linklistp; p=head－>next; /*從開始結(jié)點(diǎn)比較*/while(p!=NULL)if(p－>data!=key)p=p－>next; /*沒找到，繼續(xù)循環(huán)*/if(p==NULL)returnNULL;elsereturnp;

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

在循環(huán)鏈表的第i個(gè)元素之后插入元素x。INSERT(linklisthead,datatypex,inti)/*在循環(huán)鏈表第i個(gè)元素之后插入元素x*/{linklists; intj;s=(linklist)malloc(sizeof(linklist));s－>data=x; /*生成值為x的新結(jié)點(diǎn)*/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(″e(cuò)rror″);} /*INSERT*/7.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.3循環(huán)鏈表[例7.7]

一元多項(xiàng)式的表示及相加。多項(xiàng)式結(jié)點(diǎn)形式多項(xiàng)式的循環(huán)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.3循環(huán)鏈表polynode*polyadd(polynodepa,polynodepb); /*多項(xiàng)式相加運(yùn)算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é)點(diǎn)鏈入多項(xiàng)式A中*/} /*polyadd*/7.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.4雙向鏈表typedefstructdnode{datatypedata;structdnodeprior,next;}dlinklist;dlinklisthead;7.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.4雙向鏈表

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

計(jì)算機(jī)軟件技術(shù)基礎(chǔ)教程第八章棧和隊(duì)列8.1棧8.1.1棧的基本概念及其運(yùn)算8.1棧8.1.1棧的基本概念及其運(yùn)算(1)置空?！猄etNull(S)，完成對(duì)棧的初始化。(2)判斷棧是否為空—Empty(S)，若棧S為空，則返回真；否則，返回假。(3)進(jìn)?！狿ush(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棧的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu)--順序棧structStack{ datatypeelements[maxsize]； intTop；}其中，maxsize是棧的容量，datatype是棧中數(shù)據(jù)元素的數(shù)據(jù)類型，Top指示當(dāng)前棧頂位置，棧底位置為0。8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu)--順序棧8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)(1)置空棧：將棧進(jìn)行初始化，主要是將棧頂指針Top初始化為–1。voidSetNuLLS(structStack*S){ S－>Top=–1；} /SetNuLLS/(2)判斷棧是否為空：在進(jìn)行出棧操作時(shí)，首先必須判斷棧不為空，否則會(huì)出錯(cuò)。intEmptyS(structStack*s){ if(S－>Top>=0)return(0)； elsereturn(1)；} /*EmptyS*/8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)(3)進(jìn)棧：將數(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棧的存儲(chǔ)結(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棧的存儲(chǔ)結(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棧的存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)—鏈棧8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)—鏈棧鏈棧定義如下：structNode{datatypeelement; structNode*next;};structNode*top;8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)voidPUSHL(structNode*S,datatypeE){structNode*p; /*進(jìn)棧*/p=(structNode*)malloc(1,sizeof(structNode));p－>element=E;p－>next=S;S=p;}top鏈棧的進(jìn)棧操作8.1棧8.1.2棧的存儲(chǔ)結(jié)構(gòu)top

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