計算機軟件基礎教案2012(研)

課程名稱：計算機軟件基礎

教學目的及教學設想：

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

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

門人才知識結構與能力結構的重要環(huán)節(jié)，也是學習本專業(yè)相關

課程的計算機軟件基礎課程。

通過教學，使學生具有計算機軟件方面的必備知識。要求:

掌握計算機軟件技術的基礎知識；掌握操作系統(tǒng)的基本原理；

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

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

應用；了解計算機網(wǎng)絡的基礎知識，掌握使用因特網(wǎng)的基本技

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

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

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

主要教材或參考文獻：

[1]沈被娜，劉祖照，姚曉冬.《計算機軟件技術基礎》.清華大學

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

[2]鄭守春，許占文，徐全生，張勝男.《計算機軟件技術基礎》.

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

考核方式及說明：

筆試（開卷）90分；平時成績10分。

第1周

第1章信息與計算機

1.1信息與信息時代

1.1.1什么是信息

1.信息(information)的定義

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

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

(2)信息是消息。

(3)信息是知識。

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

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

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

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

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

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

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

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

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

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

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

4.信息的基本特性

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

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

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

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

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

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

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

計算機網(wǎng)絡系統(tǒng)、書報雜志、磁帶光盤等。

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

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

(8)轉換性：信息、物質和能源是人類的三項重要的寶貴資源，

三位一體而又可以互相轉換。

5.三種不同層次的信息產品

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

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

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

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

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

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

1.信息科學的巨大發(fā)展----認識基礎

(1)自然科學---理論基礎

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

信息傳輸技術的進一步發(fā)展準備了理論基礎。

(2)社會科學一一經(jīng)濟屬性

在社會科學領域，通過對信息效用性、稀缺性、成本、價值的

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

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

信息科學的巨大發(fā)展構成現(xiàn)代信息化的認識基礎，將信息在社

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

2.信息技術的長足進步一一技術基礎

(1)信息處理技術

信息處理技術領域中新的計算機元器件技術使得計算機在微型

化的同時，性能大幅度提高，成本大幅度降低。計算機正在向智能

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

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

在通信技術領域，各種物理信道的通信技術和通信方式不斷推

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

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

和工具，成為當代信息化的技術基礎。

3.社會生產力的提高——經(jīng)濟基礎

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

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

向信息領域。

生產力水平的提高為當代信息化提供了經(jīng)濟基礎。

4.信息需求已成為普遍的社會需求一一社會基礎

隨著人們對信息重要性認識的深化以及信息利用水平的提高，

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

同層次的行為主體，對信息和信息技術的需求都有很大的增長。

5.信息時代的特點

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

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

(3)風險與效益并存

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

中的三大主干技術。

1.1.3信息與計算機應用

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

成部分

(1)計算機硬件技術

(2)計算機軟件技術

(3)通信技術

它包含了信息的產生、檢測、變換、存儲、傳遞、處理、顯示、

識別、控制和利用托的活動。

2.計算機的最主要特點

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

(2)具有記憶的能力

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

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

3.計算機應用

計算機科學與技術的劃時代的意義是為人類提供了通用智力工

具。

1.2計算機發(fā)展簡史

1.2.1計算機發(fā)展的幾個重要階段(略)

1.從硬件的角度分

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

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

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

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

2.從應用的角度分

(1)20世紀40-60年代：大型機時代

(2)20世紀70年代：中小型機時代

(3)20世紀80年代：個人計算機時代

(4)20世紀90年代：全球網(wǎng)絡時代

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

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

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

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

1.2.2計算機應用的領域(略)

根據(jù)學科劃分：

(1)科學研究與科學計算

(2)事務處理

(3)計算機輔助功能

(4)生產過程控制

(5)人工智能

(6)計算機網(wǎng)絡通信

(7)計算機教育

(8)多媒體

1.2.3計算機在現(xiàn)代人類活動中的地位和作用

1.改變人類的工作和生活方式

分散一集中一分散

2.社會轉型

(1)從工業(yè)時代轉向信息時代

(2)從工業(yè)社會轉向知識社會

1.2.4計算機的現(xiàn)在和未來(自學)

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

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

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

2.計算機和信息技術的未來發(fā)展

(1)建立未來的應用

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

(3)新的電子商務應用

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

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

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

從技術的角度，定義：為完成特定任務而由相關部件或要素組

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

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

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

1.3.1計算機系統(tǒng)的組成(自學)

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

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

(2)計算機裸機

2.硬件與軟件結合說

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

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

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

由五部分組成：

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

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

1.3.2計算機的硬件與軟件(自學)

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

⑴主機：CPU和內存

(2)外存儲器

(3)輸入設備

(4)輸出設備

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

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

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

(2)應用軟件

3.計算機硬件與軟件的關系

(1)互相依存

(2)無嚴格界面

(3)相互促進

1.3.3多媒體計算機(自學)

1.什么是多媒體計算機

(1)媒體

1)存儲信息的實體：磁帶、磁盤、光盤、半導體存儲器。

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

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

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

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

2.多媒體的基本要素

基本要素有：文本、圖形、圖像、動畫、聲頻、視頻。

3.多媒體計算機的基本配置

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

示器、聲卡和音響設備。

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

1.4計算機軟件技術發(fā)展過程

1.4.1高級語言階段

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

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

1.4.2結構程序設計階段

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

1.程序的正確性

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

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

圖1.7程序的三種基本結構

(2)語義形式化

用數(shù)學符號嚴格地按照一定規(guī)則形式地表達某種程序語言，以

達到語義的精確化合編譯自動化。

2.程序設計方法論

(1)由頂向下法

由頂向下、逐步細化，是結構程序設計的一種方法。分解一個

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

(2)自底向上的方法

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

件系統(tǒng)。

(3)模塊化

模塊劃分的的基本原則。

3.軟件生產管理

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

制。

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

1.4.3自動程序設計階段

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

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

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

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

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

在硅谷成立的。它的一個CASE工具是RationalRose,在面向對象

技術和面向對象工具市場上占到領先位置。

2.程序設計基本方法的進一步改進

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

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

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

⑵改進

1）快速原型法

2）甚高級語言（非過程化語言）

3）軟件可重用法

3.第四代語言（4GL）

（1）語言分代

1）第一代語言：1946-1950,機器語言；

2）第二代語言：1950-1960,匯編語言；

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

4）第四代語言：1980-1995,非過程化高級語言；

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

⑵第四代語言與其他軟件技術的關系

1）與數(shù)據(jù)庫的關系：數(shù)據(jù)庫是4GL的基礎

2）與第三代語言的關系：依賴3GL,轉換成3GL

3）與圖形軟件的關系：有可視化4GL

4.面向對象編程語言（見6.3.3節(jié)）

習題1.1-1.9

第2章常用數(shù)據(jù)結構與算法

2.1概述

2.1.1什么是數(shù)據(jù)結構

作為一門課程，數(shù)據(jù)結構是研究非數(shù)值運算的程序設計問題。

2.1.2有關數(shù)據(jù)結構的基本概念和術語

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

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

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

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

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

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

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

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

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

4.數(shù)據(jù)結構

數(shù)據(jù)結構(datastructure)是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間

存在的關系。用集合論方法定義數(shù)據(jù)結構為

S=(D,R)

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

集合，R是定義在D上的關系的非空有限集合。

5.邏輯結構與物理結構

(1)數(shù)據(jù)的邏輯結構：研究數(shù)據(jù)元素及其關系的數(shù)學特性，簡稱

數(shù)據(jù)結構。

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

體實現(xiàn)，簡稱存儲結構。

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

(1)概念

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

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

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

不可再分的。

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

的，或者說它們是帶結構的數(shù)據(jù)。

7.數(shù)據(jù)結構與算法

(1)算法

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

(2)數(shù)據(jù)結構與算法的關系

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

算；數(shù)據(jù)結構是算法和程序設計的基本部分，它對程序設計的質量

影響很大。

2.1.3算法描述語言

1.自然語言

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

3.高級程序設計語言，如C語言

4.類高級程序設計語言，如類C語言

2.1.4算法分析技術初步

1.時間復雜度

⑴例

設對一個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)

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

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

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

T{n)-t山+tiii

當〃很大時，有

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

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

(2)頻度

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

例子中分別是語句3和5的頻度。

(3)時間復雜度

時間復雜度是以算法中頻度最大的語句的頻度來度量的，記作

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

(4)常見的時間復雜度

0(1)：常量型

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

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

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

(5)時間復雜度比較

2nn

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

2.空間復雜度

(1)概念

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

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

(2)表示

空間復雜度的表示與實踐復雜度類似。

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

=0(1)O

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

2.2線性表

2.2.1線性表的定義和運算

1,什么是線性表

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

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

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

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

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

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

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

3.線性表的結構特點

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

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

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

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

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

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為有序表，否則稱為無序表。

5.線性表的基本運算

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

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

(3)查找：按某種要求查找線性表的一個元素，需要時可以進行

更新；

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

6.線性表的存儲結構

(1)順序存儲結構：向量；

(2)鏈式存儲結構：鏈表。

2.2.2順序存儲線性表

1.順序存儲結構

(1)順序存儲結構的含義

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

性表的順序存儲結構，也稱為向量式存儲結構，又稱為隨機存儲結

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

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

設：已知線性表中每個元素占1個單元，且線性表在內存中的

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

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

2.順序存儲結構的插入、刪除運算

⑴插入

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

素之間插入一個新元素X0

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

將第n至第i個元素一次向后移動一個位置，原第i個元素的

位置被空出來了；

將x放入被空出的存儲單元；

將線性表的長度增10

2)插入算法

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

①INSERTLIST(V,n,i,x)

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

③forj=ntoistep(-1)

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

⑤end(j)

⑥V[i]-x

⑦n—n+1

return

3)插入算法說明

語句1是將異常情況作出錯處理。

語句2-4是將后移n-(i-1)個元素，即i-1個元素不用移動；

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

語句5是將元素x送入原第i個元素的位置。

語句6是將線性表的長度增加lo

⑵刪除

設長度為n的線性表⑸,a2,a”)，要求刪除第i個元素。

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

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

將線性表的長度減1。

2)刪除算法

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

①DELETELIST(V,n,i)

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

③forj=iton-1

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

⑤end(j)

⑥n*-n-l

return

3)刪除算法說明

語句1是將異常情況作出錯處理。

語句2-4是將前移n-(i-l)個元素，即i-1個元素不用移動。

語句5是將線性表的長度減少lo

3.順序存儲結構的插入、刪除運算的時間分析

運算的時間主要移動元素上，且移動元素的個數(shù)與線性表的程

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

用最少移動次數(shù)，最多移動次數(shù)，平均移動次數(shù)來分析。

(1)插入算法

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

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

(2)刪除算法

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

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

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

第2周

2.2.3線性鏈表

1.鏈式存儲結構

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

1)可能要移動大量的數(shù)據(jù)元素，當n很大的時候，花費很多時

間;

2)需要預留存儲單元，浪費資源；若預留資源不足，會溢出。

(2)鏈式存儲結構的含義

鏈式存儲結構不需要一組連續(xù)的存儲單元，它的數(shù)據(jù)元素可以

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

每個元素中存放其后繼元素的地址。這樣由n個結點組成的序列便

構成一個鏈表，稱為線性表的鏈式存儲結構。

(3)鏈式存儲結構的概念

鏈式存儲結構(又稱指針類型結構)示意圖如下：

datanext

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

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

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

示。

2)頭指針：指示鏈表中第一個結點地址的指針，稱為頭指針，

用“head”表示。

3)空指針：鏈表中最后一個結點的指針為空指針，用“nil”或

“A”表示。

2.線性鏈表的基本運算

(1)基本操作

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

設P、q、s均為指針型變量，指向數(shù)據(jù)域為data,指針域為next

的結點。

1)指針賦值

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

①s-p〃將指針變量p的內容賦給另一個指針變量s//

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

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

另一個指針變量s//

例：若p=2000,p指向的結點的指針域內容為1200,經(jīng)過語句

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

2)指針移動

當前指針指向鏈表的下一個結點的地址指針。

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

例：若p=2000,p指向的結點的指針域內容為1200,經(jīng)過語句

p-next⑹后，p=1200。

3)后插

在P指向的結點地址后插入一個新元素。

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

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

變量s的next域〃

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

例：若p=2000,p指向的結點的指針域內容為1200,s的地址

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

s的next域內容為1200。

注意：這兩條語句的次序不能換。

4)前插

在P指向的結點地址前插入一個新元素。

先要找到P指向的結點之前的結點指針q,然后利用3)的后插

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

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

②While(next(q)Wp)do

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

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

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

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

(2)結點的動態(tài)生成與回收

設存儲器中有一個空白鏈表，表示沒有使用的存儲單元，可供

用戶使用?？瞻祖湵淼念^指針為av。

1)從空白鏈表中獲得一個結點，地址指針是Po算法如下：

(將空白鏈表的第1個結點給用戶使用。)

GETNODE(P)

①p-av〃取走空白鏈表中的第1個結點，將av賦給p//

②av-next(av)〃將空白鏈表中原第2個結點置為頭結點〃

③return

2)回收一個由p指針指向的結點。算法如下：

(將回收的結點作為空白鏈表的第1個結點)

RET(P)

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

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

(3)return

(3)插入運算

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

個值為b的結點。

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

分析沒有找到包含指定元素a的結點的異常情況及解決方法：

①若鏈表為空表：b為鏈表的第1個結點。

②若鏈表中無值為a的結點：將b添加到鏈表的末尾。

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

算法如下：(排除了a包含在第1個結點及空表)

L00KF0R(head,a,q)

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

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

③{q—next(q)}〃如果q的下一個結點存在，同時它的data

域的值不等于a,則移動q指向下一個結點

退出循環(huán)時有兩種情況：q為最后一個結點，

或者q的下一個結點的data域的值為a//

④return

4)插入算法

INLINKST(head,a,b)

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

〃取一個空結點P，并將值b放入p的data域〃

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

〃處理空表情況，p為頭指針，p的指針域為空〃

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

〃處理第1個結點值為a的情況：p的指針域是

原來的頭指針head,再將?p置為頭指針head//

④L00KF0R(head,a,q)〃調用函數(shù),尋找元素a之前的結點q//

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

〃處理返回值的情況：①找到q,它的下一個結點的data

域的值為a：將q的指針域內容賦給新結點p的指針域，

再將新結點的地址指針賦給q的指針域。

②q為最后一個結點，將q的指針域內容(為空)賦給新

結點P的指針域，再將新結點的地址指針賦給q的指針域

//

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

⑥return

(4)刪除運算

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

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

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

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

②若鏈表中只有一個值為a的結點：刪除元素a的結點后，鏈

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

③在鏈表中找到值為a的結點，且不是第1個結點：刪除。

④若鏈表中無值為a的結點：不刪除。

4)刪除算法

DELINKS?(head,a)

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

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

head*-s;return)〃處理頭結點值為a的情況：

將第2個結點指針(在a結點的指針域中)先暫存在s

變量中，在刪除第1個結點(回I收)，最后修改頭指針〃

③LOOKFOR(head,a,q)〃調用函數(shù),找元素a之前的結點q〃

④if(next(q)=nil)then{無此結點return}

〃處理未找到a的情況〃

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

⑥RET(p)

⑦return

3.線性鏈表的其他形式

(1)具有頭結點的線性鏈表

在M靠的第二個結點之前附加一個頭結點，該結點的結構和鏈

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

的指針指向線性表的第一個元素。

具有頭結點的線性鏈表為空表時，只有一個頭結點，其指針域

為空。

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

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

循環(huán)鏈表是另一種鏈式存儲結構，它的特點是表中最后一個結

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

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

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

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

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

點，而不必從頭指針開始。

(3)雙向鏈表

1)雙向鏈表的定義

在線性鏈表中增加一個指針域，其指針指向直接前驅，稱為雙

向鏈表。

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

從表中某一給定的結點可以隨意向前或向后查看。

但在做插入、刪除運算時，需同時修改兩個方向上的指針。

4.線性鏈表的應用實例----元多項式相加(略)

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

1.線性表的長度是否固定

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

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

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

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

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

補充題：對具有頭結點的線性表，寫出插入算法。

2.3棧與隊

2.3.1棧的結構和運算

1.棧的定義

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

的線性表。又稱為后進先出的線性表。

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

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

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

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

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

2.順序棧

(1)順序棧的定義

1)順序棧：用向量作為棧的存儲結構。高級語言中用一維數(shù)組

來表示，其中m表示棧允許的最大容量。

2)棧頂指示器：設置一個簡單變量(top)用來指示棧頂位置，

稱為棧頂指示器。

3)?？眨寒敆ｍ斨甘酒鱰op=0時，表示?？铡?/p>

4)棧滿：當棧頂指示器top=m時，表示棧滿。

5)棧上溢：當棧頂指示器top=m時再有元素進棧，棧將溢出，

稱為上溢。

6)棧下溢：當?？諘r要作退棧操作，棧也將溢出，稱為下溢。

(2)順序棧的插入運算(進棧)

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

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

斷是否會“上溢”。

3)算法：

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

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

②top'-top+1

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

④return

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

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

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

判斷是否會“下溢二

3)算法：

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

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

②y*-s[top]

③top-topT〃處理正常出棧〃

④return

3.鏈棧(自學)

(1)鏈棧的定義：用鏈表作為棧的存儲結構，稱為鏈棧。若

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

在可用空間。

(2)鏈棧的插入運算

(3)鏈棧的刪除運算

4.棧的應用(自學)

5.棧的練習題(自學)

已知有四個元素，它們關鍵字分別是1,2,3,4。如果入棧的

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

過程？

作業(yè)：(P103)2.21

第3周

2.3.2隊的結構和運算

1.隊的定義

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

行刪除操作的線性表。又稱為先進先出的線性表。

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

⑶隊尾指示器（rear）：指向隊尾元素。

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

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

2.順序隊

（1）順序隊的定義

1）順序隊：用向量作為隊的存儲結構。高級語言中用一維數(shù)組

來表示，其中m表示隊允許的最大容量。

2）順序隊空:front=rear（初始時front=rear=0）。

3）入隊：rear增1,front不變。即初始時front=0,rear=l0

4）出隊：front增1,rear不變。

5）隊上溢：當隊中已有m個元素時再有元素入隊，隊將溢出，

稱為隊上溢。

6）隊下溢：當隊空時要作出隊操作，隊也將溢出，稱為隊下溢。

7）假溢出：當rear=m時，無法再繼續(xù)入隊，但隊不滿，這時稱

為隊假溢出。因為只有當rear-front=m時，才是真滿。

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

為循環(huán)隊列。

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

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

初始時front=rear=m-1。

注意front指向隊列第一個元素的前一個位置。

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

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

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

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

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

①rear—（rear+1）modm〃求模運算，找到應插入的位置〃

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

return}〃判斷，若隊滿，恢復原隊尾指示器，返回〃

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

④return

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

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

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

〃判斷，若隊滿，返回〃

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

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

④return

(3)循環(huán)隊列的刪除運算

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

設頭尾指示器初始時front=rear=m-10

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

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

3)算法：

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

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

〃判斷，若隊空，返回〃

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

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

④return

3.鏈隊

(1)鏈隊的定義：用鏈表作為隊的存儲結構，稱為鏈隊。頭指針

front固定指向頭結點，注意：頭結點不放數(shù)據(jù)；尾指針指向隊尾

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

中已不存在可用空間。

(2)鏈隊的插入運算

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

ADDLINK(front,rear,x)〃在鏈隊中插入x結點〃

①GETNODE(p)〃獲取一個空白結點p〃

②data(p)-x;next(p)-nil〃給空結點賦值〃

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

〃將結點P插入到隊尾，修改隊尾指示器〃

④return

(3)鏈隊的刪除運算

分析：由于是隊，故刪除鏈表的第一個元素。

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

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

〃判斷，若隊空，返回〃

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

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

//修改頭結點的指針域，它指向排頭結點〃

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

〃若刪除結束時鏈隊已成為空隊，修改隊尾指示器〃

④return

4.隊的應用(略)

2.4數(shù)組

2.4.1數(shù)組的定義

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

例：

aw6112???CLIn

Cl22Cl2n

A=???

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

Clm\dm2???Clinn

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

令B=(K,R)

其中K={1|IWiWm,IWjWn}

R由兩個關系組成

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

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

2.4.2數(shù)組的順序存儲結構

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

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

⑴二維數(shù)組

先第1行n個元素，再第2行n個元素，…。

設每個元素僅占一個單元地址，則此的地址為：

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

(IWiWm,IWjWn)

⑵三維數(shù)組

以左下標為主序的存儲方式。

設每個元素僅占一個單元地址，則a地的地址為：

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

(IWiWl,FWm,lWkWn)

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

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

(1)二維數(shù)組

先第1列m個元素，再第2列m個元素，…。

設每個元素僅占一個單元地址，則a”的地址為：

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

(IWiWm,IWjWn)

⑵三維數(shù)組

以左下標為主序的存儲方式。

設每個元素僅占一個單元地址，則ae的地址為：

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

(IWiWl,iWjWm,lWkWn)

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

3.特殊矩陣的存放方式

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

矩陣A是一個下三角矩陣。

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

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

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

設每個元素僅占一個單元地址，則非零元素aSj的地址為：

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

(1WjWiWn)

(2)三對角陣的存儲方式

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

0,這種矩陣稱為三對角陣。

非零元素按行優(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ù)組的鏈式存儲結構(略)

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

2.5樹與二叉樹

2.5.1樹的定義及其存儲結構

1.樹的定義和術語

(1)樹的遞歸定義

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

有一個結點稱為根結點(root),其余結點可以分為m(m20)個互不

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

稱為根結點的子樹。

當n=0時、稱為空樹。

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

用二元組關系定義樹為

Tree=(T,R)

數(shù)據(jù)結構樹(Tree)由數(shù)據(jù)元素集合T及關系R組成。其中

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

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

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

1)在T中存在唯一的稱為根的元素root,它在H關系下無前驅。

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

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

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

3)對應于Ti,T2,Tm,H-｛〈root,xD,…，〈root,x)｝劃分為m

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

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

稱為根root的子樹。

(3)常用術語

1)結點(node)：表示樹中的元素。

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

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

3)葉子(leaf)：度為零的結點，又稱端結點。

4)孩子(child)：除根結點外，每個結點都是其前驅結點的孩

子。又稱子女。

5)雙親(parents)：對應于孩子的上層結點，稱為這些結點的

雙親。

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

7)結點的層次(level)：從根結點開始，根為第一層，根的直

接后繼結點為第二層，其余各層依次類推。

8)深度(depth)；樹中結點的層次數(shù)。

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

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

換的，稱為有序樹。反之，稱為無序樹。

2.樹的存儲結構——鏈式結構

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

每個結點設有多個指針域，其中每一個指針指向一棵子樹的根

結點。根據(jù)每一個結點的子樹數(shù)設置相應的指針域，由于樹中每個

結點的度數(shù)不盡相同，則一棵樹中各結點的結構形式也不同，稱為

結構異構型。

好處：節(jié)省存儲空間。缺點：運算不方便。

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

每個結點的指針域個數(shù)均為樹的度數(shù)，一棵樹中各結點的結構

形式相同，稱為結構同構型。

好處：運算方便。缺點：出現(xiàn)很多空指針域，浪費空間。

空指針域的計算方法：設一棵有n個結點k叉樹，則共有nk個

指針域，有用的指針域為nT個?？罩羔樣虻膫€數(shù)是：nk-(nT)

對不同的k值，

isnk

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

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

nk3n3

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

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

nk2n2

當k=2時-，空指針域的比例最低，這就是二叉樹。

2.5.2二叉樹及其性質

1.二叉樹的定義

(1)二叉樹的遞歸定義

二叉樹是由n(n20)個結點的有限集合，它或為空樹(n=0),

或由一個根結點和兩棵分別稱為左子樹與右子樹的互不相交的二叉

樹構成。

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

用二元組關系定義二叉樹BT為

BT=(D,R)

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

①)，則R=①，稱為空二叉樹；若D#①，則R是D上某個二元關系

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

1)在D中存在唯一的稱為根的元素r,它在H關系下無前驅。

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

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

存在D上的關系MEHo

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

在DR上的關系O

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

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

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

二叉樹的結點的子樹有明確的左、右之分，而普通樹沒有。

(4)二叉樹的存儲結構

用具有兩個指針域的鏈表作為二叉樹的存儲結構，其中每個結

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

組成。

LchilddataRchild

2.二叉樹的基本性質

(1)二叉樹的第i層上至多有2i(i21)個結點。

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

i=l,則結點數(shù)為2一=1,只有一個根結點，結論成立。

按數(shù)學歸納法，假定第iT層上的結點數(shù)至多有2°-°-=2-2個。

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

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

(2)深度為h的二叉樹中至多含有-1個結點。

證明：利用性質⑴的結論。每一層上取最多的結點數(shù)，有

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

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

則必有n()=n2+1o

證明：增加幾個變量：度數(shù)為1的結點結點數(shù)為整棵樹的

結點數(shù)為n,連線(邊)數(shù)為b。

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

除根結點外，其他所有結點都有與其雙親的指針，n=b+1

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

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

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

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

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

(1)滿二叉樹

深度為h且含有2h-1個結點的二叉樹稱為滿二叉樹。圖2.1

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

可以對滿二叉樹的結點進行編號，其次序是自上至下，自左至

右。

圖2.1滿二叉樹

(2)完全二叉樹

如果一棵有n個結點的二叉樹，按與滿二叉樹相同的的編號方

式對結點進行編號,若樹中n個結點和滿二叉樹1?n編號完全一致,

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

(a)(b)

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

(3)平衡二叉樹

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

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

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

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

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

(a)(b)

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

4.一般樹轉為二叉樹

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

對應關系，而且是---對應的。

將一棵普通樹轉換為二叉樹的方法如下：

(1)將普通樹的兄弟結點之間加一連線；

(2)對每個結點，除了與它的第一個孩子保持聯(lián)系外，去除與其

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

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

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

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

這種轉換是唯一的。并且右子樹是空的。

圖2.4-一般樹轉換為二叉樹

2.5.3二叉樹的遍歷

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

構中的全部結點，而且每