計(jì)算機(jī)軟件基礎(chǔ)教案2012(研)

課程名稱：計(jì)算機(jī)軟件基礎(chǔ)

教學(xué)目的及教學(xué)設(shè)想：

本課程是非計(jì)算機(jī)專業(yè)的一門公共計(jì)算機(jī)課程，綜合性與

實(shí)踐性強(qiáng)，內(nèi)容有一定的深度和難度。本課程是形成本專業(yè)專

門人才知識(shí)結(jié)構(gòu)與能力結(jié)構(gòu)的重要環(huán)節(jié)，也是學(xué)習(xí)本專業(yè)相關(guān)

課程的計(jì)算機(jī)軟件基礎(chǔ)課程。

通過教學(xué)，使學(xué)生具有計(jì)算機(jī)軟件方面的必備知識(shí)。要求:

掌握計(jì)算機(jī)軟件技術(shù)的基礎(chǔ)知識(shí)；掌握操作系統(tǒng)的基本原理；

掌握數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和常用算法；掌握軟件工程的基本概

念、理論和方法；了解數(shù)據(jù)庫(kù)的基本知識(shí)，掌握數(shù)據(jù)庫(kù)技術(shù)的

應(yīng)用；了解計(jì)算機(jī)網(wǎng)絡(luò)的基礎(chǔ)知識(shí)，掌握使用因特網(wǎng)的基本技

術(shù)；了解信息和計(jì)算機(jī)系統(tǒng)的安全保護(hù)技術(shù)。

根據(jù)非計(jì)算機(jī)專業(yè)的特點(diǎn)，教學(xué)以課堂上教師的講課為主,

自學(xué)、討論、答疑和完成作業(yè)為輔進(jìn)行。

主要教材或參考文獻(xiàn)：

[1]沈被娜，劉祖照，姚曉冬.《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》.清華大學(xué)

出版社，2000年7月第3版.

[2]鄭守春，許占文，徐全生，張勝男.《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》.

大連理工大學(xué)出版社，1998年2月第1版.

考核方式及說明：

筆試（開卷）90分；平時(shí)成績(jī)10分。

第1周

第1章信息與計(jì)算機(jī)

1.1信息與信息時(shí)代

1.1.1什么是信息

1.信息(information)的定義

(1)信息是對(duì)現(xiàn)實(shí)世界中存在的客觀實(shí)體、現(xiàn)象、關(guān)系進(jìn)行描述

的數(shù)據(jù)。

(2)信息是消息。

(3)信息是知識(shí)。

(4)信息是經(jīng)過加工后并對(duì)實(shí)體的行為產(chǎn)生影響的數(shù)據(jù)。

(5)構(gòu)成一定含義的一組數(shù)據(jù)。

2.數(shù)據(jù)(data)的定義

數(shù)據(jù)是現(xiàn)實(shí)世界客觀存在的實(shí)體或事物的屬性值，即指人們聽

到的事實(shí)和看到的現(xiàn)象。

數(shù)據(jù)可以是數(shù)字、文字或符號(hào)，還可以是聲音、語(yǔ)言、圖形等。

3.信息與數(shù)據(jù)的關(guān)系

(1)信息是有一定含義的數(shù)據(jù)。

(2)信息是經(jīng)過加工(處理)后的數(shù)據(jù)。

(3)信息是對(duì)決策有價(jià)值的數(shù)據(jù)。

(4)數(shù)據(jù)是信息的物理形式，是信息的載體。

4.信息的基本特性

(1)事實(shí)性：第一和基本的性質(zhì)，也是信息的中心價(jià)值。

(2)等級(jí)性：不同的使用目的要求不同等級(jí)的信息，例如有戰(zhàn)略

信息、策略信息、執(zhí)行信息等等。

(3)可壓縮性：可以對(duì)信息作濃縮處理，即進(jìn)行集中、綜合和概

括而又不丟失信息的本意。

(4)可擴(kuò)散性：信息可以通過各種渠道和手段向四面八方擴(kuò)散。

(5)可傳輸性：信息可以通過多種形式迅速傳輸，如電話、電報(bào)、

計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)、書報(bào)雜志、磁帶光盤等。

(6)共享性：信息可以被多個(gè)用戶共享而得到充分的利用。

(7)增值性與再生性：信息是有價(jià)值的，而且可以增值。

(8)轉(zhuǎn)換性：信息、物質(zhì)和能源是人類的三項(xiàng)重要的寶貴資源，

三位一體而又可以互相轉(zhuǎn)換。

5.三種不同層次的信息產(chǎn)品

(1)數(shù)據(jù)：通過數(shù)據(jù)采集獲得，用于事務(wù)處理系統(tǒng)。

(2)信息：通過數(shù)據(jù)處理獲得，用于管理信息系統(tǒng)。

(3)知識(shí)：通過數(shù)據(jù)融合獲得，是經(jīng)過分析與綜合的信息，用于

決策支持系統(tǒng)。

圖1.2信息的三中不同層次示意圖

1.1.2信息化是社會(huì)經(jīng)濟(jì)發(fā)展的必然結(jié)果

1.信息科學(xué)的巨大發(fā)展----認(rèn)識(shí)基礎(chǔ)

(1)自然科學(xué)---理論基礎(chǔ)

自然科學(xué)領(lǐng)域在信息科學(xué)方面的研究，為現(xiàn)代信息處理技術(shù)和

信息傳輸技術(shù)的進(jìn)一步發(fā)展準(zhǔn)備了理論基礎(chǔ)。

(2)社會(huì)科學(xué)一一經(jīng)濟(jì)屬性

在社會(huì)科學(xué)領(lǐng)域，通過對(duì)信息效用性、稀缺性、成本、價(jià)值的

研究，發(fā)現(xiàn)了信息已經(jīng)具備的經(jīng)濟(jì)屬性，從而在理論上確立了信息

作為經(jīng)濟(jì)資源的重要地位。

信息科學(xué)的巨大發(fā)展構(gòu)成現(xiàn)代信息化的認(rèn)識(shí)基礎(chǔ)，將信息在社

會(huì)經(jīng)濟(jì)中的重要性提高到了理論的高度。

2.信息技術(shù)的長(zhǎng)足進(jìn)步一一技術(shù)基礎(chǔ)

(1)信息處理技術(shù)

信息處理技術(shù)領(lǐng)域中新的計(jì)算機(jī)元器件技術(shù)使得計(jì)算機(jī)在微型

化的同時(shí)，性能大幅度提高，成本大幅度降低。計(jì)算機(jī)正在向智能

化、集成化、綜合化發(fā)展。

(2)信息傳輸技術(shù)(通信技術(shù))

在通信技術(shù)領(lǐng)域，各種物理信道的通信技術(shù)和通信方式不斷推

出和更新。寬帶、高速、大容量已經(jīng)成為現(xiàn)代通信信道的主要特征。

信息處理技術(shù)和通信技術(shù)的發(fā)展為當(dāng)代信息化提供了技術(shù)手段

和工具，成為當(dāng)代信息化的技術(shù)基礎(chǔ)。

3.社會(huì)生產(chǎn)力的提高——經(jīng)濟(jì)基礎(chǔ)

經(jīng)濟(jì)的高速增長(zhǎng)反映了社會(huì)生產(chǎn)力的空前提高，社會(huì)經(jīng)濟(jì)資源,

包括資金、原料?、人力、智力等資源，有可能從傳統(tǒng)的生產(chǎn)領(lǐng)域轉(zhuǎn)

向信息領(lǐng)域。

生產(chǎn)力水平的提高為當(dāng)代信息化提供了經(jīng)濟(jì)基礎(chǔ)。

4.信息需求已成為普遍的社會(huì)需求一一社會(huì)基礎(chǔ)

隨著人們對(duì)信息重要性認(rèn)識(shí)的深化以及信息利用水平的提高，

在社會(huì)、經(jīng)濟(jì)、文化、軍事等各領(lǐng)域，以及政府、企業(yè)、公眾等不

同層次的行為主體，對(duì)信息和信息技術(shù)的需求都有很大的增長(zhǎng)。

5.信息時(shí)代的特點(diǎn)

(1)市場(chǎng)環(huán)境變化巨大

(2)機(jī)遇與挑戰(zhàn)并存

(3)風(fēng)險(xiǎn)與效益并存

(4)多媒體、全球互聯(lián)網(wǎng)、信息高速公路，是信息時(shí)代革命浪潮

中的三大主干技術(shù)。

1.1.3信息與計(jì)算機(jī)應(yīng)用

1.信息技術(shù)(InformationTechnology縮寫為IT)的三大組

成部分

(1)計(jì)算機(jī)硬件技術(shù)

(2)計(jì)算機(jī)軟件技術(shù)

(3)通信技術(shù)

它包含了信息的產(chǎn)生、檢測(cè)、變換、存儲(chǔ)、傳遞、處理、顯示、

識(shí)別、控制和利用托的活動(dòng)。

2.計(jì)算機(jī)的最主要特點(diǎn)

(1)高速自動(dòng)的操作功能

(2)具有記憶的能力

(3)可以進(jìn)行各種邏輯判斷

(3)精確高速的計(jì)算能力

3.計(jì)算機(jī)應(yīng)用

計(jì)算機(jī)科學(xué)與技術(shù)的劃時(shí)代的意義是為人類提供了通用智力工

具。

1.2計(jì)算機(jī)發(fā)展簡(jiǎn)史

1.2.1計(jì)算機(jī)發(fā)展的幾個(gè)重要階段(略)

1.從硬件的角度分

(1)20世紀(jì)40~50年代：第一代，電子管

(2)20世紀(jì)50年代末一60年代中：第二代，晶體管

(3)20世紀(jì)60年代中一70年代初：第三代，集成電路

(4)20世紀(jì)70年代中：第四代，超大規(guī)模集成電路

2.從應(yīng)用的角度分

(1)20世紀(jì)40-60年代：大型機(jī)時(shí)代

(2)20世紀(jì)70年代：中小型機(jī)時(shí)代

(3)20世紀(jì)80年代：個(gè)人計(jì)算機(jī)時(shí)代

(4)20世紀(jì)90年代：全球網(wǎng)絡(luò)時(shí)代

3.數(shù)字化信息的特點(diǎn)

(1)容易交換，只要有傳輸媒體，即可以暢通無(wú)阻，無(wú)處不達(dá);

(2)可以大容量、高速度傳輸，以滿足人們對(duì)信息的需求；

(3)穩(wěn)定性高，傳輸途中不受干擾，可以還其本來(lái)面貌。

1.2.2計(jì)算機(jī)應(yīng)用的領(lǐng)域(略)

根據(jù)學(xué)科劃分：

(1)科學(xué)研究與科學(xué)計(jì)算

(2)事務(wù)處理

(3)計(jì)算機(jī)輔助功能

(4)生產(chǎn)過程控制

(5)人工智能

(6)計(jì)算機(jī)網(wǎng)絡(luò)通信

(7)計(jì)算機(jī)教育

(8)多媒體

1.2.3計(jì)算機(jī)在現(xiàn)代人類活動(dòng)中的地位和作用

1.改變?nèi)祟惖墓ぷ骱蜕罘绞?/p>

分散一集中一分散

2.社會(huì)轉(zhuǎn)型

(1)從工業(yè)時(shí)代轉(zhuǎn)向信息時(shí)代

(2)從工業(yè)社會(huì)轉(zhuǎn)向知識(shí)社會(huì)

1.2.4計(jì)算機(jī)的現(xiàn)在和未來(lái)(自學(xué))

1.計(jì)算機(jī)的現(xiàn)在

(1)計(jì)算機(jī)在微小型化的同時(shí)，性能有了大幅度的提高

(2)計(jì)算機(jī)系統(tǒng)正向智能化、集成化、綜合化發(fā)展

2.計(jì)算機(jī)和信息技術(shù)的未來(lái)發(fā)展

(1)建立未來(lái)的應(yīng)用

(2)管理企業(yè)的應(yīng)用

(3)新的電子商務(wù)應(yīng)用

(4)解決人機(jī)文化差異的問題

1.3計(jì)算機(jī)與計(jì)算機(jī)系統(tǒng)

1.系統(tǒng)的定義

從技術(shù)的角度，定義：為完成特定任務(wù)而由相關(guān)部件或要素組

成的有機(jī)整體，成為系統(tǒng)。

2.系統(tǒng)的特點(diǎn)

(1)整體性(2)層次性(3)適應(yīng)性

1.3.1計(jì)算機(jī)系統(tǒng)的組成(自學(xué))

1.硬件系統(tǒng)說

(1)計(jì)算機(jī)硬件系統(tǒng)的組成

(2)計(jì)算機(jī)裸機(jī)

2.硬件與軟件結(jié)合說

(1)計(jì)算機(jī)軟件系統(tǒng)

(2)計(jì)算機(jī)系統(tǒng)的狹義說法

3.計(jì)算機(jī)廣義系統(tǒng)說

由五部分組成：

(1)人員(2)數(shù)據(jù)(3)設(shè)備

(4)程序(5)規(guī)程

1.3.2計(jì)算機(jī)的硬件與軟件(自學(xué))

1.微型計(jì)算機(jī)的硬件系統(tǒng)

⑴主機(jī)：CPU和內(nèi)存

(2)外存儲(chǔ)器

(3)輸入設(shè)備

(4)輸出設(shè)備

(5)微機(jī)系統(tǒng)總線：數(shù)據(jù)總線、地址總線和控制總線

2.微型計(jì)算機(jī)的軟件系統(tǒng)

(1)系統(tǒng)軟件

(2)應(yīng)用軟件

3.計(jì)算機(jī)硬件與軟件的關(guān)系

(1)互相依存

(2)無(wú)嚴(yán)格界面

(3)相互促進(jìn)

1.3.3多媒體計(jì)算機(jī)(自學(xué))

1.什么是多媒體計(jì)算機(jī)

(1)媒體

1)存儲(chǔ)信息的實(shí)體：磁帶、磁盤、光盤、半導(dǎo)體存儲(chǔ)器。

2)表現(xiàn)信息形式的載體：數(shù)字、文字、圖形、圖像、視頻。

(2)多媒體計(jì)算機(jī)的定義

多媒體計(jì)算機(jī)是以計(jì)算機(jī)為核心，可以綜合處理數(shù)值計(jì)算、文

本文件、圖形、圖像、聲頻、視頻等多種信息的計(jì)算機(jī)系統(tǒng)。

2.多媒體的基本要素

基本要素有：文本、圖形、圖像、動(dòng)畫、聲頻、視頻。

3.多媒體計(jì)算機(jī)的基本配置

(1)硬件配置：CPU、內(nèi)存大小、硬盤容量、光驅(qū)、視頻卡和顯

示器、聲卡和音響設(shè)備。

(2)軟件配置：最主要的是支持多媒體的操作系統(tǒng)(MPCOS)0

1.4計(jì)算機(jī)軟件技術(shù)發(fā)展過程

1.4.1高級(jí)語(yǔ)言階段

20世紀(jì)60年代，F(xiàn)ORTRAN、ALG0L60.COBOL.LISP、PL/1。

編譯系統(tǒng)主要靠手工編制，自動(dòng)化程度很低。

1.4.2結(jié)構(gòu)程序設(shè)計(jì)階段

20世紀(jì)60年代末發(fā)生了軟件危機(jī)。

1.程序的正確性

(1)三種基本結(jié)構(gòu)：順序、選擇和循環(huán)

(a)順序(b)選擇(c)循環(huán)

圖1.7程序的三種基本結(jié)構(gòu)

(2)語(yǔ)義形式化

用數(shù)學(xué)符號(hào)嚴(yán)格地按照一定規(guī)則形式地表達(dá)某種程序語(yǔ)言，以

達(dá)到語(yǔ)義的精確化合編譯自動(dòng)化。

2.程序設(shè)計(jì)方法論

(1)由頂向下法

由頂向下、逐步細(xì)化，是結(jié)構(gòu)程序設(shè)計(jì)的一種方法。分解一個(gè)

大系統(tǒng)為若干個(gè)子系統(tǒng)。

(2)自底向上的方法

自底開發(fā)程序模塊，再處理各模塊之間的聯(lián)系，組合成整個(gè)軟

件系統(tǒng)。

(3)模塊化

模塊劃分的的基本原則。

3.軟件生產(chǎn)管理

(1)軟件工程：軟件生產(chǎn)作為一種工程需要某種合理管理的體

制。

(2)軟件生命周期法(見第6章)

1.4.3自動(dòng)程序設(shè)計(jì)階段

1軟件工程支撐環(huán)境

把過去分散編制的d：牛開發(fā)工具，集成為整體性的系統(tǒng)，稱為

軟件工程支撐環(huán)境，也稱為CASE(computeraidedsoftware

engineering)o它支持軟件開發(fā)和維護(hù)的全過程。

Rational軟件公司是由PaulLevy和MikeDevlin于1991年

在硅谷成立的。它的一個(gè)CASE工具是RationalRose,在面向?qū)ο?/p>

技術(shù)和面向?qū)ο蠊ぞ呤袌?chǎng)上占到領(lǐng)先位置。

2.程序設(shè)計(jì)基本方法的進(jìn)一步改進(jìn)

（1）傳統(tǒng)軟件開發(fā)方法的缺點(diǎn)

1）要求開發(fā)者有一定的計(jì)算機(jī)專業(yè)知識(shí)和程序設(shè)計(jì)經(jīng)驗(yàn)；

2）軟件開發(fā)的各階段缺少反饋。

⑵改進(jìn)

1）快速原型法

2）甚高級(jí)語(yǔ)言（非過程化語(yǔ)言）

3）軟件可重用法

3.第四代語(yǔ)言（4GL）

（1）語(yǔ)言分代

1）第一代語(yǔ)言：1946-1950,機(jī)器語(yǔ)言；

2）第二代語(yǔ)言：1950-1960,匯編語(yǔ)言；

3）第三代語(yǔ)言：1960-1980,過程化編程語(yǔ)言；

4）第四代語(yǔ)言：1980-1995,非過程化高級(jí)語(yǔ)言；

5）第五代語(yǔ)言：1995-，應(yīng)用程序開發(fā)用專家系統(tǒng)。

⑵第四代語(yǔ)言與其他軟件技術(shù)的關(guān)系

1）與數(shù)據(jù)庫(kù)的關(guān)系：數(shù)據(jù)庫(kù)是4GL的基礎(chǔ)

2）與第三代語(yǔ)言的關(guān)系：依賴3GL,轉(zhuǎn)換成3GL

3）與圖形軟件的關(guān)系：有可視化4GL

4.面向?qū)ο缶幊陶Z(yǔ)言（見6.3.3節(jié)）

習(xí)題1.1-1.9

第2章常用數(shù)據(jù)結(jié)構(gòu)與算法

2.1概述

2.1.1什么是數(shù)據(jù)結(jié)構(gòu)

作為一門課程，數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值運(yùn)算的程序設(shè)計(jì)問題。

2.1.2有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)

1.數(shù)據(jù)

數(shù)據(jù)(Data)是信息的載體，它可以用計(jì)算機(jī)表示并加工，如

數(shù)、字符、符號(hào)等的集合。

2.數(shù)據(jù)元素

數(shù)據(jù)元素(dataelement)是數(shù)據(jù)集合中的一個(gè)個(gè)體，是數(shù)據(jù)

的基本單位。如集合N={1,2,3,4,5)中的整數(shù)1至5均為數(shù)據(jù)元素。

學(xué)生登記表中的一條記錄，也是一個(gè)數(shù)據(jù)元素。

3.數(shù)據(jù)對(duì)象

具有相同性質(zhì)的數(shù)據(jù)元素的集合稱為世界對(duì)象(dataobject)。

4.數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(datastructure)是指同一數(shù)據(jù)對(duì)象中各數(shù)據(jù)元素間

存在的關(guān)系。用集合論方法定義數(shù)據(jù)結(jié)構(gòu)為

S=(D,R)

數(shù)據(jù)結(jié)構(gòu)S是一個(gè)二元組，其中D是一個(gè)數(shù)據(jù)元素的非空有限

集合，R是定義在D上的關(guān)系的非空有限集合。

5.邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)：研究數(shù)據(jù)元素及其關(guān)系的數(shù)學(xué)特性，簡(jiǎn)稱

數(shù)據(jù)結(jié)構(gòu)。

”(2)數(shù)據(jù)的物理結(jié)構(gòu)：是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映像，也就是具

體實(shí)現(xiàn)，簡(jiǎn)稱存儲(chǔ)結(jié)構(gòu)。

6.數(shù)據(jù)類型

(1)概念

數(shù)據(jù)類型(datatype)是指程序設(shè)計(jì)語(yǔ)言中允許的變量類型。

(2)數(shù)據(jù)類型的分類

1)基本數(shù)據(jù)類型：如整型、實(shí)型、布爾型等，它們變量的值是

不可再分的。

2)結(jié)構(gòu)數(shù)據(jù)類型：如數(shù)組、結(jié)構(gòu)體等，它們變量的值是可再分

的，或者說它們是帶結(jié)構(gòu)的數(shù)據(jù)。

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

(1)算法

算法是解決某一特定類型問題的有限運(yùn)算序列。

(2)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系

算法的實(shí)現(xiàn)必須借助程序設(shè)計(jì)語(yǔ)言中提供的數(shù)據(jù)類型及其運(yùn)

算；數(shù)據(jù)結(jié)構(gòu)是算法和程序設(shè)計(jì)的基本部分，它對(duì)程序設(shè)計(jì)的質(zhì)量

影響很大。

2.1.3算法描述語(yǔ)言

1.自然語(yǔ)言

2.流程圖(框圖)等圖形工具

3.高級(jí)程序設(shè)計(jì)語(yǔ)言，如C語(yǔ)言

4.類高級(jí)程序設(shè)計(jì)語(yǔ)言，如類C語(yǔ)言

2.1.4算法分析技術(shù)初步

1.時(shí)間復(fù)雜度

⑴例

設(shè)對(duì)一個(gè)nXn矩陣A自乘后送入矩陣B,其算法步驟為

(Dfori=1ton

②forj=1ton

③B[i,j]-0

④fork=1ton

⑤B[i,j]*-b[i,j]+a[i,k]*a[k,j]

⑥end(k)

⑦end(j)

⑧end(i)

分析：語(yǔ)句3重復(fù)次數(shù)為R,語(yǔ)句5重復(fù)次數(shù)為3若語(yǔ)句3

執(zhí)行1次的時(shí)間為3語(yǔ)句5執(zhí)行1次的時(shí)間為3忽略控制語(yǔ)句

的執(zhí)行時(shí)間，次算法耗用的時(shí)間近似為

T{n)-t山+tiii

當(dāng)〃很大時(shí)，有

表明當(dāng)〃很大時(shí)，75)和力的比值是常數(shù),即7(〃)和I是同階

的，記作7(〃)=的冷。

(2)頻度

在算法中，一條語(yǔ)句重復(fù)的次數(shù)，稱為該語(yǔ)句的頻度，記作網(wǎng)力。

例子中分別是語(yǔ)句3和5的頻度。

(3)時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是以算法中頻度最大的語(yǔ)句的頻度來(lái)度量的，記作

7?=0(/(力)。例子中，時(shí)間復(fù)雜度為T5)=05)。

(4)常見的時(shí)間復(fù)雜度

0(1)：常量型

0(72),0(772),-?*,0(Z?k):多項(xiàng)式型

0(1og2n),o(7?log2z?)：對(duì)數(shù)型

0(2n),0(en)：指數(shù)型

(5)時(shí)間復(fù)雜度比較

2nn

0(1)<0(log2z?)<0(T?)<0(7?log22?)<0(z?)<<0(2)<0(e)

2.空間復(fù)雜度

(1)概念

空間復(fù)雜度是指在算法中所需的輔助空間單元，而不包括問題

的原始數(shù)據(jù)占用的空間。

(2)表示

空間復(fù)雜度的表示與實(shí)踐復(fù)雜度類似。

本例中所需的輔助空間單元為i、j、k,所以空間復(fù)雜度為S5)

=0(1)O

作業(yè)：(P101)2.5(1)(2)(3),注意(4)(5)有錯(cuò),不要了。

2.2線性表

2.2.1線性表的定義和運(yùn)算

1,什么是線性表

線性表是數(shù)據(jù)元素的有限序列。例：

n維向量x=(aba2,-,an),其中每個(gè)分量為一個(gè)數(shù)據(jù)元素；學(xué)

生表，一個(gè)學(xué)生的記錄為一個(gè)數(shù)據(jù)元素。

2.線性表的一般表示形式

L=(a,,a.2,,,,,an)

其中L為線性表，a,(i=1,2,…,n)是屬于某數(shù)據(jù)對(duì)象的元素，n(n

20)為元素個(gè)數(shù)，又稱為表長(zhǎng)，n=0為空表。

3.線性表的結(jié)構(gòu)特點(diǎn)

數(shù)據(jù)元素之間是線性關(guān)系，具體有四句話：

(1)線性表中必存在唯一的一個(gè)“第一個(gè)”元素；

(2)必存在唯一的一個(gè)“最后一個(gè)”元素；

(3)除第一個(gè)元素以外，每個(gè)元素有且只有一個(gè)前驅(qū)元素；

(4)除最后一個(gè)元素以外，每個(gè)元素有且只有一個(gè)后繼元素。

4.線性表的形式定義

L=(D,R)

其中D={aba2,...,ar,}

R={〈a—i,a〉|a.i-i,aj￡D,2WiWn}

若線性表中的數(shù)據(jù)元素相互之間可比較，且aiNa-,i=

2,3,...,n,則稱L為有序表，否則稱為無(wú)序表。

5.線性表的基本運(yùn)算

(1)插入：在兩個(gè)確定元素之間插入一個(gè)新元素；

(2)刪除：刪除線性表中某個(gè)元素；

(3)查找：按某種要求查找線性表的一個(gè)元素，需要時(shí)可以進(jìn)行

更新；

(4)排序：按給定要求對(duì)表中元素重新排序。

6.線性表的存儲(chǔ)結(jié)構(gòu)

(1)順序存儲(chǔ)結(jié)構(gòu)：向量；

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈表。

2.2.2順序存儲(chǔ)線性表

1.順序存儲(chǔ)結(jié)構(gòu)

(1)順序存儲(chǔ)結(jié)構(gòu)的含義

是用一組地址連續(xù)的存儲(chǔ)單元存放線性表的數(shù)據(jù)元素，稱為線

性表的順序存儲(chǔ)結(jié)構(gòu)，也稱為向量式存儲(chǔ)結(jié)構(gòu)，又稱為隨機(jī)存儲(chǔ)結(jié)

構(gòu)。用高級(jí)語(yǔ)言中的一維數(shù)組類型表示，例如A[l:n]0

(2)求順序存儲(chǔ)線性表中第i個(gè)元素的存儲(chǔ)地址

設(shè)：已知線性表中每個(gè)元素占1個(gè)單元，且線性表在內(nèi)存中的

首地址為：adr(a,)=b,則線性表中第i個(gè)元素的存儲(chǔ)地址為

adr(aj=adr(aj+(i-1)1

2.順序存儲(chǔ)結(jié)構(gòu)的插入、刪除運(yùn)算

⑴插入

設(shè)長(zhǎng)度為n的線性表(a1,a2,a),要求在第i-1與第i個(gè)元

素之間插入一個(gè)新元素X0

1)順序存儲(chǔ)線性表的插入過程

將第n至第i個(gè)元素一次向后移動(dòng)一個(gè)位置，原第i個(gè)元素的

位置被空出來(lái)了；

將x放入被空出的存儲(chǔ)單元；

將線性表的長(zhǎng)度增10

2)插入算法

設(shè)存放線性表的向量為V[l,m](m>n),算法如下：

①INSERTLIST(V,n,i,x)

②if(i<l)OR(i>n+l)then{參數(shù)錯(cuò)return}

③forj=ntoistep(-1)

④V[j+1]-V[j]

⑤end(j)

⑥V[i]-x

⑦n—n+1

return

3)插入算法說明

語(yǔ)句1是將異常情況作出錯(cuò)處理。

語(yǔ)句2-4是將后移n-(i-1)個(gè)元素，即i-1個(gè)元素不用移動(dòng)；

step(T)表示j從n開始每次減1,j為iT時(shí)停止循環(huán)。

語(yǔ)句5是將元素x送入原第i個(gè)元素的位置。

語(yǔ)句6是將線性表的長(zhǎng)度增加lo

⑵刪除

設(shè)長(zhǎng)度為n的線性表⑸,a2,a”)，要求刪除第i個(gè)元素。

1)順序存儲(chǔ)線性表的刪除過程

將第i個(gè)元素aj以后的元素ai+1,*,?,a”依次向前移動(dòng)一個(gè)位置。

將線性表的長(zhǎng)度減1。

2)刪除算法

設(shè)存放線性表的向量為V[l,m](m>n),算法如下：

①DELETELIST(V,n,i)

②if(i<l)OR(i>n)then{參數(shù)錯(cuò)return}

③forj=iton-1

④V[j]-V[j+1]

⑤end(j)

⑥n*-n-l

return

3)刪除算法說明

語(yǔ)句1是將異常情況作出錯(cuò)處理。

語(yǔ)句2-4是將前移n-(i-l)個(gè)元素，即i-1個(gè)元素不用移動(dòng)。

語(yǔ)句5是將線性表的長(zhǎng)度減少lo

3.順序存儲(chǔ)結(jié)構(gòu)的插入、刪除運(yùn)算的時(shí)間分析

運(yùn)算的時(shí)間主要移動(dòng)元素上，且移動(dòng)元素的個(gè)數(shù)與線性表的程

度，以及與被插入或刪除元素在線性表中的位置i有關(guān)。

用最少移動(dòng)次數(shù)，最多移動(dòng)次數(shù)，平均移動(dòng)次數(shù)來(lái)分析。

(1)插入算法

最少移動(dòng)次數(shù)0(i=n+l),最多移動(dòng)次數(shù)n(i=l),

平均移動(dòng)次數(shù)=(0+1+…+n)/(n+l)=n/2

(2)刪除算法

最少移動(dòng)次數(shù)0(i=n),最多移動(dòng)次數(shù)n-1(i=l),

平均移動(dòng)次數(shù)=(0+1+…+(nT))/n=(n-l)/2

作業(yè)：(P102)2.8,2.11

第2周

2.2.3線性鏈表

1.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

(1)順序存儲(chǔ)線性表的插入、刪除運(yùn)算的不足

1)可能要移動(dòng)大量的數(shù)據(jù)元素，當(dāng)n很大的時(shí)候，花費(fèi)很多時(shí)

間;

2)需要預(yù)留存儲(chǔ)單元，浪費(fèi)資源；若預(yù)留資源不足，會(huì)溢出。

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的含義

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不需要一組連續(xù)的存儲(chǔ)單元，它的數(shù)據(jù)元素可以

分散存放在存儲(chǔ)空間中，為了使線性表在邏輯上保持連續(xù)，必須在

每個(gè)元素中存放其后繼元素的地址。這樣由n個(gè)結(jié)點(diǎn)組成的序列便

構(gòu)成一個(gè)鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

(3)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(又稱指針類型結(jié)構(gòu))示意圖如下：

datanext

1)數(shù)據(jù)域與指針域：指針類型結(jié)構(gòu)中，每一個(gè)數(shù)據(jù)元素由兩部

分組成：一部分是存放元素的值，稱為數(shù)據(jù)域，用“data”表示；

苗一部分為存放后繼元素的存儲(chǔ)地址，稱為指針域，用“next”表

示。

2)頭指針：指示鏈表中第一個(gè)結(jié)點(diǎn)地址的指針，稱為頭指針，

用“head”表示。

3)空指針：鏈表中最后一個(gè)結(jié)點(diǎn)的指針為空指針，用“nil”或

“A”表示。

2.線性鏈表的基本運(yùn)算

(1)基本操作

線性鏈表的四種基本操作，如29頁(yè)的表2.2所示。

設(shè)P、q、s均為指針型變量，指向數(shù)據(jù)域?yàn)閐ata,指針域?yàn)閚ext

的結(jié)點(diǎn)。

1)指針賦值

將某地址指針值賦給一個(gè)指針變量。有兩種情況：

①s-p〃將指針變量p的內(nèi)容賦給另一個(gè)指針變量s//

例：若p=2000,經(jīng)過語(yǔ)句s—p后，s=2000

②q-next(p)〃將指針變量p的next域內(nèi)容賦給

另一個(gè)指針變量s//

例：若p=2000,p指向的結(jié)點(diǎn)的指針域內(nèi)容為1200,經(jīng)過語(yǔ)句

q-next(p)后，q=1200。

2)指針移動(dòng)

當(dāng)前指針指向鏈表的下一個(gè)結(jié)點(diǎn)的地址指針。

p—next(p)〃將指針變量p的next域內(nèi)容賦給指針變量p//

例：若p=2000,p指向的結(jié)點(diǎn)的指針域內(nèi)容為1200,經(jīng)過語(yǔ)句

p-next⑹后，p=1200。

3)后插

在P指向的結(jié)點(diǎn)地址后插入一個(gè)新元素。

s是保存新元素的指針變量(新的)。

next(s)-next(p)〃將指針變量p的next域內(nèi)容賦給指針

變量s的next域〃

next(p)-s〃將指針變量s的地址賦給指針變量p的next域//

例：若p=2000,p指向的結(jié)點(diǎn)的指針域內(nèi)容為1200,s的地址

為3000。經(jīng)過語(yǔ)句next(s)-next(p)和后，p的next域內(nèi)容為3000,

s的next域內(nèi)容為1200。

注意：這兩條語(yǔ)句的次序不能換。

4)前插

在P指向的結(jié)點(diǎn)地址前插入一個(gè)新元素。

先要找到P指向的結(jié)點(diǎn)之前的結(jié)點(diǎn)指針q,然后利用3)的后插

算法。找到方法是從頭指針(賦給q)開始，判斷“next(q)=p?二

①q-head〃將頭指針變量head的地址賦給指針變量q〃

②While(next(q)Wp)do

③{q-next(q)}〃在next(q)=p時(shí)退出循環(huán)，否則指針移動(dòng)〃

④next(q)*-s〃將新結(jié)點(diǎn)的地址s賦給q的指針域//

⑤next(s)*-p〃將已知結(jié)點(diǎn)的地址p賦給s的指針域〃

注意：后兩條語(yǔ)句的次序可以交換。思考為什么？

(2)結(jié)點(diǎn)的動(dòng)態(tài)生成與回收

設(shè)存儲(chǔ)器中有一個(gè)空白鏈表，表示沒有使用的存儲(chǔ)單元，可供

用戶使用。空白鏈表的頭指針為av。

1)從空白鏈表中獲得一個(gè)結(jié)點(diǎn)，地址指針是Po算法如下：

(將空白鏈表的第1個(gè)結(jié)點(diǎn)給用戶使用。)

GETNODE(P)

①p-av〃取走空白鏈表中的第1個(gè)結(jié)點(diǎn)，將av賦給p//

②av-next(av)〃將空白鏈表中原第2個(gè)結(jié)點(diǎn)置為頭結(jié)點(diǎn)〃

③return

2)回收一個(gè)由p指針指向的結(jié)點(diǎn)。算法如下：

(將回收的結(jié)點(diǎn)作為空白鏈表的第1個(gè)結(jié)點(diǎn))

RET(P)

①next(p)-av〃原空白鏈表中的頭指針av賦給p的指針域//

②av-p〃將指針p賦給頭指針av//o

(3)return

(3)插入運(yùn)算

1)要求：在頭指針為head的鏈表中，值為a的結(jié)點(diǎn)前，插入一

個(gè)值為b的結(jié)點(diǎn)。

2)分析：主要是要尋找包含指定元素a的結(jié)點(diǎn)及之前的結(jié)點(diǎn)q。

分析沒有找到包含指定元素a的結(jié)點(diǎn)的異常情況及解決方法：

①若鏈表為空表：b為鏈表的第1個(gè)結(jié)點(diǎn)。

②若鏈表中無(wú)值為a的結(jié)點(diǎn)：將b添加到鏈表的末尾。

3)在非空鏈表中，尋找包含指定元素a的結(jié)點(diǎn)之前的結(jié)點(diǎn)qo

算法如下：(排除了a包含在第1個(gè)結(jié)點(diǎn)及空表)

L00KF0R(head,a,q)

①q-head〃將頭指針變量head的地址賦給指針變量q//

②while(next(q)Ttnil)and(data(next(q))Wa)do

③{q—next(q)}〃如果q的下一個(gè)結(jié)點(diǎn)存在，同時(shí)它的data

域的值不等于a,則移動(dòng)q指向下一個(gè)結(jié)點(diǎn)

退出循環(huán)時(shí)有兩種情況：q為最后一個(gè)結(jié)點(diǎn)，

或者q的下一個(gè)結(jié)點(diǎn)的data域的值為a//

④return

4)插入算法

INLINKST(head,a,b)

①GETNODE(p);data(p)-b;

〃取一個(gè)空結(jié)點(diǎn)P，并將值b放入p的data域〃

②if(head=nil)then(head-p;next(p)-nil;return)

〃處理空表情況，p為頭指針，p的指針域?yàn)榭铡?/p>

③if(data(head)=a)then{next(p)-head;head-p;return}

〃處理第1個(gè)結(jié)點(diǎn)值為a的情況：p的指針域是

原來(lái)的頭指針head,再將?p置為頭指針head//

④L00KF0R(head,a,q)〃調(diào)用函數(shù),尋找元素a之前的結(jié)點(diǎn)q//

⑤next(p)-next(q);next(q)-p

〃處理返回值的情況：①找到q,它的下一個(gè)結(jié)點(diǎn)的data

域的值為a：將q的指針域內(nèi)容賦給新結(jié)點(diǎn)p的指針域，

再將新結(jié)點(diǎn)的地址指針賦給q的指針域。

②q為最后一個(gè)結(jié)點(diǎn)，將q的指針域內(nèi)容(為空)賦給新

結(jié)點(diǎn)P的指針域，再將新結(jié)點(diǎn)的地址指針賦給q的指針域

//

從上可以看出，這兩種情況的程序可以合并。

⑥r(nóng)eturn

(4)刪除運(yùn)算

1)要求：在頭指針為head的鏈表中，刪除元素值為a的結(jié)點(diǎn)。

2)分析：同樣也要尋找包含指定元素a的結(jié)點(diǎn)及之前的結(jié)點(diǎn)q。

算法還需要處理四種情況：

①若鏈表為空表：不刪除。

②若鏈表中只有一個(gè)值為a的結(jié)點(diǎn)：刪除元素a的結(jié)點(diǎn)后，鏈

表變?yōu)榭毡怼?/p>

③在鏈表中找到值為a的結(jié)點(diǎn)，且不是第1個(gè)結(jié)點(diǎn)：刪除。

④若鏈表中無(wú)值為a的結(jié)點(diǎn)：不刪除。

4)刪除算法

DELINKS?(head,a)

①if(head=nil)then{空表return}〃空表情況//

②if(data(head)=a)then{s*-next(head);RET(head);

head*-s;return)〃處理頭結(jié)點(diǎn)值為a的情況：

將第2個(gè)結(jié)點(diǎn)指針(在a結(jié)點(diǎn)的指針域中)先暫存在s

變量中，在刪除第1個(gè)結(jié)點(diǎn)(回I收)，最后修改頭指針〃

③LOOKFOR(head,a,q)〃調(diào)用函數(shù),找元素a之前的結(jié)點(diǎn)q〃

④if(next(q)=nil)then{無(wú)此結(jié)點(diǎn)return}

〃處理未找到a的情況〃

⑤p-next(q);next(q)-next(p)〃處理找到a的情況〃

⑥RET(p)

⑦return

3.線性鏈表的其他形式

(1)具有頭結(jié)點(diǎn)的線性鏈表

在M靠的第二個(gè)結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)，該結(jié)點(diǎn)的結(jié)構(gòu)和鏈

表中的其他結(jié)點(diǎn)相同，只是它的數(shù)據(jù)域中不存放線性表的元素，它

的指針指向線性表的第一個(gè)元素。

具有頭結(jié)點(diǎn)的線性鏈表為空表時(shí)，只有一個(gè)頭結(jié)點(diǎn)，其指針域

為空。

(2)循環(huán)鏈表

1)循環(huán)鏈表的定義

循環(huán)鏈表是另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的特點(diǎn)是表中最后一個(gè)結(jié)

點(diǎn)的指針域不為空，而是指向表頭，整個(gè)鏈表形成一個(gè)環(huán)。

2)具有頭結(jié)點(diǎn)的循環(huán)鏈表

是指帶有頭結(jié)點(diǎn)的循環(huán)鏈表。

3)循環(huán)鏈表的優(yōu)點(diǎn)

只要給出循環(huán)鏈表中任一結(jié)點(diǎn)的地址，就可以查遍表中所有結(jié)

點(diǎn)，而不必從頭指針開始。

(3)雙向鏈表

1)雙向鏈表的定義

在線性鏈表中增加一個(gè)指針域，其指針指向直接前驅(qū)，稱為雙

向鏈表。

2)雙向鏈表的優(yōu)點(diǎn)

從表中某一給定的結(jié)點(diǎn)可以隨意向前或向后查看。

但在做插入、刪除運(yùn)算時(shí)，需同時(shí)修改兩個(gè)方向上的指針。

4.線性鏈表的應(yīng)用實(shí)例----元多項(xiàng)式相加(略)

2.2.4向量和鏈表的比較(自學(xué))

1.線性表的長(zhǎng)度是否固定

向量一固定，線性鏈表一不固定

2.線性表的主要操作是什么

向量一查詢，線性鏈表一插入和刪除

向量一隨意，口線性鏈表一提供指針類型變量

作業(yè)：(P102)2.12,2.13

補(bǔ)充題：對(duì)具有頭結(jié)點(diǎn)的線性表，寫出插入算法。

2.3棧與隊(duì)

2.3.1棧的結(jié)構(gòu)和運(yùn)算

1.棧的定義

(1)棧(stack)：棧是限定只能在表的一端進(jìn)行插入和刪除操作

的線性表。又稱為后進(jìn)先出的線性表。

(2)棧頂(top)：棧中允許插入或刪除的一端稱為棧頂。

(3)棧底(bottom)：棧中不允許插入或刪除的一端稱為棧底。

(4)空棧：棧中沒有元素時(shí)，稱為空棧。

(5)進(jìn)棧(入棧，push)：向棧中插入元素，稱為進(jìn)棧。

(6)退棧(出棧,pop)：將棧中元素刪除，稱為退棧。

2.順序棧

(1)順序棧的定義

1)順序棧：用向量作為棧的存儲(chǔ)結(jié)構(gòu)。高級(jí)語(yǔ)言中用一維數(shù)組

來(lái)表示，其中m表示棧允許的最大容量。

2)棧頂指示器：設(shè)置一個(gè)簡(jiǎn)單變量(top)用來(lái)指示棧頂位置，

稱為棧頂指示器。

3)?？眨寒?dāng)棧頂指示器top=0時(shí)，表示?？?。

4)棧滿：當(dāng)棧頂指示器top=m時(shí)，表示棧滿。

5)棧上溢：當(dāng)棧頂指示器top=m時(shí)再有元素進(jìn)棧，棧將溢出，

稱為上溢。

6)棧下溢：當(dāng)?？諘r(shí)要作退棧操作，棧也將溢出，稱為下溢。

(2)順序棧的插入運(yùn)算(進(jìn)棧)

1)要求：將元素x插入順序棧

2)分析：先令top加1,再將元素x送入s[top]中。但要先判

斷是否會(huì)“上溢”。

3)算法：

PUSH(s,m,top,x)//將元素x送入棧中//

①if(top=m)then{“上溢〃,return)

②top'-top+1

③s[top]-x〃處理正常入?！?/p>

④return

(3)順序棧的刪除運(yùn)算(退棧)

1)要求：將棧頂元素取出。

2)分析：先將棧頂元素放入y,再將棧頂指針top減1。但要先

判斷是否會(huì)“下溢二

3)算法：

P0P(s,top,y)〃退棧，將棧頂元素送入y中〃

①if(top=0)then{“下溢"，return}

②y*-s[top]

③top-topT〃處理正常出?！?/p>

④return

3.鏈棧(自學(xué))

(1)鏈棧的定義：用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，稱為鏈棧。若

top=nil,則表示棧空。鏈棧不會(huì)出現(xiàn)“上溢”，除非內(nèi)存中已不存

在可用空間。

(2)鏈棧的插入運(yùn)算

(3)鏈棧的刪除運(yùn)算

4.棧的應(yīng)用(自學(xué))

5.棧的練習(xí)題(自學(xué))

已知有四個(gè)元素，它們關(guān)鍵字分別是1,2,3,4。如果入棧的

次序是4321,假設(shè)入棧時(shí)可以出棧，問：哪幾種排列是可能的出棧

過程？

作業(yè)：(P103)2.21

第3周

2.3.2隊(duì)的結(jié)構(gòu)和運(yùn)算

1.隊(duì)的定義

(1)隊(duì)(queue)：隊(duì)是限定只允許在一端進(jìn)行插入，在另一端進(jìn)

行刪除操作的線性表。又稱為先進(jìn)先出的線性表。

(2)隊(duì)尾：隊(duì)中允許插入的一端稱為隊(duì)尾。

⑶隊(duì)尾指示器（rear）：指向隊(duì)尾元素。

⑷排頭：隊(duì)中允許刪除的一端稱為排頭。

⑸排頭指示器（front）：指向排頭元素。

2.順序隊(duì)

（1）順序隊(duì)的定義

1）順序隊(duì)：用向量作為隊(duì)的存儲(chǔ)結(jié)構(gòu)。高級(jí)語(yǔ)言中用一維數(shù)組

來(lái)表示，其中m表示隊(duì)允許的最大容量。

2）順序隊(duì)空:front=rear（初始時(shí)front=rear=0）。

3）入隊(duì)：rear增1,front不變。即初始時(shí)front=0,rear=l0

4）出隊(duì)：front增1,rear不變。

5）隊(duì)上溢：當(dāng)隊(duì)中已有m個(gè)元素時(shí)再有元素入隊(duì)，隊(duì)將溢出，

稱為隊(duì)上溢。

6）隊(duì)下溢：當(dāng)隊(duì)空時(shí)要作出隊(duì)操作，隊(duì)也將溢出，稱為隊(duì)下溢。

7）假溢出：當(dāng)rear=m時(shí)，無(wú)法再繼續(xù)入隊(duì)，但隊(duì)不滿，這時(shí)稱

為隊(duì)假溢出。因?yàn)橹挥挟?dāng)rear-front=m時(shí)，才是真滿。

8）循環(huán)隊(duì)列：把存放隊(duì)列的數(shù)組形成一個(gè)頭尾相接的環(huán)形，稱

為循環(huán)隊(duì)列。

（2）循環(huán)隊(duì)列的插入運(yùn)算

1）要求：將元素x插入循環(huán)隊(duì)列CQ[0:m-l]o假設(shè)頭尾指示器

初始時(shí)front=rear=m-1。

注意front指向隊(duì)列第一個(gè)元素的前一個(gè)位置。

2）分析：有兩種算法：①先找到插入位置，然后進(jìn)行判斷隊(duì)是

否滿，若不滿，再插入數(shù)據(jù)xo②先判斷隊(duì)是否滿，若不滿，再找

到插入位置，最后插入數(shù)據(jù)XO

3）循環(huán)隊(duì)列的插入算法1

ADDCQ（CQ,m,front,rear,x）〃將x插入隊(duì)列CQ中〃

①rear—（rear+1）modm〃求模運(yùn)算，找到應(yīng)插入的位置〃

②if（front=rear）then{"隊(duì)滿“；rear*-（rear-1）modm；

return}〃判斷，若隊(duì)滿，恢復(fù)原隊(duì)尾指示器，返回〃

③CQ[rear]-x〃插入數(shù)據(jù)的操作〃

④return

4）循環(huán)隊(duì)列的插入算法2

ADDCQ2(CQ,m,front,rear,x)〃將x插入隊(duì)列CQ中〃

①if(front=(rear+1)modm)then{"隊(duì)滿“，return}

〃判斷，若隊(duì)滿，返回〃

②rear-(rear+1)modm〃求模運(yùn)算，找到應(yīng)插入的位置〃

③CQ[rear]-x〃插入數(shù)據(jù)的操作〃

④return

(3)循環(huán)隊(duì)列的刪除運(yùn)算

1)要求：將循環(huán)隊(duì)列CQ[0:mT]的隊(duì)首元素取出，并刪除。假

設(shè)頭尾指示器初始時(shí)front=rear=m-10

2)分析：先判斷隊(duì)是否空，若不空，找到刪除元素的位置，將

隊(duì)首元素放入y,排頭指示器front增1。

3)算法：

DELCQ(CQ,m,front,rear,y)〃刪除隊(duì)首元素送入y中//

①if(front=rear)then{“隊(duì)空"，return}

〃判斷，若隊(duì)空，返回〃

②front-(front+1)modm〃求模運(yùn)算，找到刪除的位置〃

③y-CQ(front)〃刪除操作，將隊(duì)首元素賦值給y〃

④return

3.鏈隊(duì)

(1)鏈隊(duì)的定義：用鏈表作為隊(duì)的存儲(chǔ)結(jié)構(gòu)，稱為鏈隊(duì)。頭指針

front固定指向頭結(jié)點(diǎn)，注意：頭結(jié)點(diǎn)不放數(shù)據(jù)；尾指針指向隊(duì)尾

元素，front=rear表示隊(duì)空。鏈隊(duì)不會(huì)出現(xiàn)“上溢”，除非內(nèi)存

中已不存在可用空間。

(2)鏈隊(duì)的插入運(yùn)算

分析：由于是隊(duì)，故插入到鏈表的最后。

ADDLINK(front,rear,x)〃在鏈隊(duì)中插入x結(jié)點(diǎn)〃

①GETNODE(p)〃獲取一個(gè)空白結(jié)點(diǎn)p〃

②data(p)-x;next(p)-nil〃給空結(jié)點(diǎn)賦值〃

(3)next(rear)-p;rear-p

〃將結(jié)點(diǎn)P插入到隊(duì)尾，修改隊(duì)尾指示器〃

④return

(3)鏈隊(duì)的刪除運(yùn)算

分析：由于是隊(duì)，故刪除鏈表的第一個(gè)元素。

DELLINK(front,rear,y)〃刪除排頭元素，并賦值給y//

①if(front=rear)then{“隊(duì)空"，return}

〃判斷，若隊(duì)空，返回〃

②y-data(next(front));next(front)-next(next(front))

〃將排頭元素取出賦給y,//

//修改頭結(jié)點(diǎn)的指針域，它指向排頭結(jié)點(diǎn)〃

③if(next(front)=nil)thenrear-front

〃若刪除結(jié)束時(shí)鏈隊(duì)已成為空隊(duì)，修改隊(duì)尾指示器〃

④return

4.隊(duì)的應(yīng)用(略)

2.4數(shù)組

2.4.1數(shù)組的定義

1.二維數(shù)組(數(shù)學(xué)中的矩陣)

例：

aw6112???CLIn

Cl22Cl2n

A=???

????????????

Clm\dm2???Clinn

2.用線性表定義二維數(shù)組

令B=(K,R)

其中K={1|IWiWm,IWjWn}

R由兩個(gè)關(guān)系組成

行R0W={KijrKij+1|IWiWm,IWjWnT}

歹|JCOL={^.KHUIlWiWm-1,IWjWn}

2.4.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

用一維連續(xù)單元存放多維的數(shù)組。

1.按行優(yōu)先順序存放

⑴二維數(shù)組

先第1行n個(gè)元素，再第2行n個(gè)元素，…。

設(shè)每個(gè)元素僅占一個(gè)單元地址，則此的地址為：

Loc(ai。=Loc(an)+(i-1)Xn+(j-1)

(IWiWm,IWjWn)

⑵三維數(shù)組

以左下標(biāo)為主序的存儲(chǔ)方式。

設(shè)每個(gè)元素僅占一個(gè)單元地址，則a地的地址為：

Loc(aijk)=Loc(am)+(i-1)XmXn+(j-1)Xn+(k-l)

(IWiWl,FWm,lWkWn)

(c,BASIC語(yǔ)言按行優(yōu)先)

2.按列優(yōu)先順序存放

(1)二維數(shù)組

先第1列m個(gè)元素，再第2列m個(gè)元素，…。

設(shè)每個(gè)元素僅占一個(gè)單元地址，則a”的地址為：

Loc(aij)=Loc(an)+(j-1)Xm+(i-1)

(IWiWm,IWjWn)

⑵三維數(shù)組

以左下標(biāo)為主序的存儲(chǔ)方式。

設(shè)每個(gè)元素僅占一個(gè)單元地址，則ae的地址為：

Loc(ajjk)=Loc(am)+(k-l)X1Xm+(j-1)X1+(i-1)

(IWiWl,iWjWm,lWkWn)

(FORTRAN語(yǔ)言按列優(yōu)先)

3.特殊矩陣的存放方式

(1)下三角矩陣的存儲(chǔ)方式

矩陣A是一個(gè)下三角矩陣。

其非零元素按行優(yōu)先順序存放。

由于第1行到第iT行的非零元素個(gè)數(shù)為：

1+2+…+(i-l)=i(i-l)/2

設(shè)每個(gè)元素僅占一個(gè)單元地址，則非零元素aSj的地址為：

Loc(aij)=Loc(an)+i(i-l)/2+(j-1)

(1WjWiWn)

(2)三對(duì)角陣的存儲(chǔ)方式

主對(duì)角線盒兩條次對(duì)角線上的元素可以是非零，其余元素均為

0,這種矩陣稱為三對(duì)角陣。

非零元素按行優(yōu)先順序存放，則非零元素配的地址為：

Loc(aij)=Loc(an)+2(iT)+(j-1)

(i=l,j=l,2

或i=n,j=(n-l),n

或1<i<n,j=(i-l),i,i+1)

2.4.3稀疏矩陣(略)

2.4.4數(shù)組的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(略)

作業(yè)：(P103)2.22,2.25

2.5樹與二叉樹

2.5.1樹的定義及其存儲(chǔ)結(jié)構(gòu)

1.樹的定義和術(shù)語(yǔ)

(1)樹的遞歸定義

樹(Tree)是由n(n》0)個(gè)結(jié)點(diǎn)組成的有限集合T,其中有且僅

有一個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)(root),其余結(jié)點(diǎn)可以分為m(m20)個(gè)互不

相交的有限集合T?T%…,L,其中每一個(gè)集合「本身又是一棵樹，

稱為根結(jié)點(diǎn)的子樹。

當(dāng)n=0時(shí)、稱為空樹。

(2)用二元組關(guān)系定義樹

用二元組關(guān)系定義樹為

Tree=(T,R)

數(shù)據(jù)結(jié)構(gòu)樹(Tree)由數(shù)據(jù)元素集合T及關(guān)系R組成。其中

T是具有相同類型的數(shù)據(jù)元素集合T=｛xbX%…,xj。若T為

空集(T=①)，則R=⑦，稱為空樹；否則R是T上某個(gè)二元關(guān)系H

的集合，即R=集｝。H的描述如下:

1)在T中存在唯一的稱為根的元素root,它在H關(guān)系下無(wú)前驅(qū)。

2)若T-｛root｝#①，則存在m個(gè)子集TbT2,(m>0),對(duì)任意

的jWk(lWj,kWm),有T」riTk=①，且存在唯一的數(shù)據(jù)元素xPR

(IWiWm),滿足〈root,Xi>￡H。

3)對(duì)應(yīng)于Ti,T2,Tm,H-｛〈root,xD,…，〈root,x)｝劃分為m

個(gè)子集用，…,HKm>0),對(duì)任意的jWk(lWj,kWm),有子0昂=①,

乩滿足上的二元關(guān)系。因此，(「，｛HJ)也是一課符合本定義的樹,

稱為根root的子樹。

(3)常用術(shù)語(yǔ)

1)結(jié)點(diǎn)(node)：表示樹中的元素。

2)結(jié)點(diǎn)的度、樹的度(degree)：結(jié)點(diǎn)擁有的子樹數(shù)，稱為結(jié)點(diǎn)

的度；一棵樹中最大的結(jié)點(diǎn)度數(shù)，稱為這棵樹的度。

3)葉子(leaf)：度為零的結(jié)點(diǎn)，又稱端結(jié)點(diǎn)。

4)孩子(child)：除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都是其前驅(qū)結(jié)點(diǎn)的孩

子。又稱子女。

5)雙親(parents)：對(duì)應(yīng)于孩子的上層結(jié)點(diǎn)，稱為這些結(jié)點(diǎn)的

雙親。

6)兄弟(sibling)：同一雙親的孩子。

7)結(jié)點(diǎn)的層次(level)：從根結(jié)點(diǎn)開始，根為第一層，根的直

接后繼結(jié)點(diǎn)為第二層，其余各層依次類推。

8)深度(depth)；樹中結(jié)點(diǎn)的層次數(shù)。

9)森林(forest)：是m(m10)棵互不相交的樹的結(jié)合。

10)有序樹：樹中結(jié)點(diǎn)在同層中按從左至右的有序排列、不能互

換的，稱為有序樹。反之，稱為無(wú)序樹。

2.樹的存儲(chǔ)結(jié)構(gòu)——鏈?zhǔn)浇Y(jié)構(gòu)

(1)指針域個(gè)數(shù)不同-一異構(gòu)型

每個(gè)結(jié)點(diǎn)設(shè)有多個(gè)指針域，其中每一個(gè)指針指向一棵子樹的根

結(jié)點(diǎn)。根據(jù)每一個(gè)結(jié)點(diǎn)的子樹數(shù)設(shè)置相應(yīng)的指針域，由于樹中每個(gè)

結(jié)點(diǎn)的度數(shù)不盡相同，則一棵樹中各結(jié)點(diǎn)的結(jié)構(gòu)形式也不同，稱為

結(jié)構(gòu)異構(gòu)型。

好處：節(jié)省存儲(chǔ)空間。缺點(diǎn)：運(yùn)算不方便。

(2)指針域個(gè)數(shù)相同-一同構(gòu)型

每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)均為樹的度數(shù)，一棵樹中各結(jié)點(diǎn)的結(jié)構(gòu)

形式相同，稱為結(jié)構(gòu)同構(gòu)型。

好處：運(yùn)算方便。缺點(diǎn)：出現(xiàn)很多空指針域，浪費(fèi)空間。

空指針域的計(jì)算方法：設(shè)一棵有n個(gè)結(jié)點(diǎn)k叉樹，則共有nk個(gè)

指針域，有用的指針域?yàn)閚T個(gè)?？罩羔樣虻膫€(gè)數(shù)是：nk-(nT)

對(duì)不同的k值，

isnk

._n(k-1)+12〃+l2

k=3,------=----?—

nk3n3

,c〃(左一1)+1〃+l1

k=2,------=---x—

nk2n2

當(dāng)k=2時(shí)-，空指針域的比例最低，這就是二叉樹。

2.5.2二叉樹及其性質(zhì)

1.二叉樹的定義

(1)二叉樹的遞歸定義

二叉樹是由n(n20)個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諛?n=0),

或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹與右子樹的互不相交的二叉

樹構(gòu)成。

(2)用二元組關(guān)系定義二叉樹

用二元組關(guān)系定義二叉樹BT為

BT=(D,R)

其中D為相同類型元素的集合口={xbx2,xn},若D為空集(D=

①)，則R=①，稱為空二叉樹；若D#①，則R是D上某個(gè)二元關(guān)系

H的集合，即R={H}oH的描述如下：

1)在D中存在唯一的稱為根的元素r,它在H關(guān)系下無(wú)前驅(qū)。

2)若D-{r}W①，則D-{r}=①，DR}且/nDR=①。

3)若DLW中，則在DL中存在唯一的元素XL,滿足<r,XL>￡H,且

存在D上的關(guān)系MEHo

若DRW①，則在DR中存在唯一的元素XR,滿足〈r,XR〉￡H,且存

在DR上的關(guān)系O

4)(D,?HL)是一棵符合本定義的二叉樹，稱為根r的左子樹；

(DR,HR)是一棵符合本定義的二叉樹，稱為根r的右子樹。

(3)二叉樹與樹的區(qū)別

二叉樹的結(jié)點(diǎn)的子樹有明確的左、右之分，而普通樹沒有。

(4)二叉樹的存儲(chǔ)結(jié)構(gòu)

用具有兩個(gè)指針域的鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，其中每個(gè)結(jié)

點(diǎn)由數(shù)據(jù)域(data)、左指針域(Lchild)和右指針域(Rchild)

組成。

LchilddataRchild

2.二叉樹的基本性質(zhì)

(1)二叉樹的第i層上至多有2i(i21)個(gè)結(jié)點(diǎn)。

證明：用數(shù)學(xué)歸納法證明。

i=l,則結(jié)點(diǎn)數(shù)為2一=1,只有一個(gè)根結(jié)點(diǎn)，結(jié)論成立。

按數(shù)學(xué)歸納法，假定第iT層上的結(jié)點(diǎn)數(shù)至多有2°-°-=2-2個(gè)。

由于二叉樹中每一個(gè)結(jié)點(diǎn)的度數(shù)最大為2,因此，第i層的結(jié)點(diǎn)數(shù)

至多是第iT層上的結(jié)點(diǎn)數(shù)的2倍，于是2X2-=2T。證畢！

(2)深度為h的二叉樹中至多含有-1個(gè)結(jié)點(diǎn)。

證明：利用性質(zhì)⑴的結(jié)論。每一層上取最多的結(jié)點(diǎn)數(shù)，有

1+2+??-+2"+=2h-1o證畢！

⑶在任意二叉樹中，若有n。個(gè)葉子結(jié)點(diǎn)，山個(gè)度數(shù)為2的結(jié)點(diǎn),

則必有n()=n2+1o

證明：增加幾個(gè)變量：度數(shù)為1的結(jié)點(diǎn)結(jié)點(diǎn)數(shù)為整棵樹的

結(jié)點(diǎn)數(shù)為n,連線(邊)數(shù)為b。

結(jié)點(diǎn)總數(shù)是度數(shù)為0、1、2的結(jié)點(diǎn)的和，n=n0+ni+n2

除根結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)都有與其雙親的指針，n=b+1

而b又可以看做結(jié)點(diǎn)與它的子女之間的聯(lián)系，b=ni+2n2

后兩個(gè)式子消去b,得到n=m+2n2+1

再代入第一個(gè)式子，得到n0+ni+n2=n!+2n2+1

于是有n0=n2+1o證畢！

3.幾種特殊形式的二叉樹

(1)滿二叉樹

深度為h且含有2h-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。圖2.1

所示為一棵深度為4的滿二叉樹。

可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行編號(hào)，其次序是自上至下，自左至

右。

圖2.1滿二叉樹

(2)完全二叉樹

如果一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按與滿二叉樹相同的的編號(hào)方

式對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),若樹中n個(gè)結(jié)點(diǎn)和滿二叉樹1?n編號(hào)完全一致,

則稱該樹為完全二叉樹。圖2.2(a)是一棵完全二叉樹，圖2.2(b)

(a)(b)

圖2.2完全二叉樹與非完全二叉樹

(3)平衡二叉樹

平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列

性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和

右子樹的深度之差的絕對(duì)值不超過1.

左子樹和右子樹的深度之差稱為平衡因子，只能是T、0、1。

圖2.3(a)是一棵平衡二叉樹，圖2.3(b)是一棵非平衡二叉樹。

(a)(b)

圖2.3平衡二叉樹與非平衡二叉樹

4.一般樹轉(zhuǎn)為二叉樹

由于二叉樹的優(yōu)良性質(zhì)，所以人們想法找出一般樹與二叉樹的

對(duì)應(yīng)關(guān)系，而且是---對(duì)應(yīng)的。

將一棵普通樹轉(zhuǎn)換為二叉樹的方法如下：

(1)將普通樹的兄弟結(jié)點(diǎn)之間加一連線；

(2)對(duì)每個(gè)結(jié)點(diǎn)，除了與它的第一個(gè)孩子保持聯(lián)系外，去除與其

他孩子的聯(lián)系；

(3)以樹根為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)45°。

圖2.4(a)是一課普通樹，圖2.4(b)是一棵(1)、(2)步后的結(jié)

果，圖2.4(c)是轉(zhuǎn)換成的二叉樹。

這種轉(zhuǎn)換是唯一的。并且右子樹是空的。

圖2.4-一般樹轉(zhuǎn)換為二叉樹

2.5.3二叉樹的遍歷

遍歷(traversing)是指循某條搜索路線，依次訪問某數(shù)據(jù)結(jié)

構(gòu)中的全部結(jié)點(diǎn)，而且每