1、第部分 數據結構第一章 緒論 計算機應用相當普遍，計算機的應用已不再局限于科學計算，而更多用于控制、管理及數據處理等非數值計算的處理工作。與此相應，計算機加工處理的對象由純粹的數值發展到字符、表格和圖像等各種具有一定結構的數據，這就給程序設計帶來一些新的問題。為了編寫出一個好的程序，必須分析待處理的對象的特性以及各處理對象之間存在的關系。這就是數據結構學科形成和發展的背景。1.1 數據結構一般來說， 用計算機解決一個問題時，需要經過如下幾個步驟：首先要從具體問題中抽象出一個適當的數學模型，然后設計一個對此數學模型進行操作的算法，最后編寫出程序直至得到解答。 例l： 圖書館的書目檢索系統。當你想

2、借閱一本參考書時，你需要到圖書館去查閱圖書目錄卡片。如果利用計算機實現自動檢索，則計算機處理的對象便是這些目錄卡片上的書目信息，列在卡片上的一本書的書目信息可由登錄號、書名、作者名、分類號、出版單位和出版時間等各項組成。每一本書都有唯一的一個登錄號。在書目自動檢索系統中建立一張按登錄號順序排列的書目文件，如圖1.1，這個文件就是書目自動檢索系統中的數學模型。計算機的主要操作就是按照某個特定要求(如給定書名)對書目文件進行查詢。 001高等數學樊映川S01002理論力學羅遠祥L01003高等數學華羅庚S01004線性代數欒汝書S02圖1.11.2 基本概念1.2.1 數據 是對客觀事物的符號表示

3、，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數值、字符串、圖像、聲音都是數據。1.2.2 數據元素 是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理單位，通常個數據元素可由若干個數據項組成。如書目文件中一本書的書目信息就是一個數據元素。書目信息中的每一項(如書名、作者名)為一個數據項，數據項是不可分割的最小單位。 1.2.3 數據對象是性質相同的數據元素的集合，是數據的子集。1.2.4 數據結構 簡單的說，是相互之間存在一種或多種特定關系的數據元素的集合。數據結構沒有一個明確的定義，它包括三個要素： 1. 數據的邏輯結構 數據的邏輯結構抽象地反映數據

4、元素之間的邏輯關系，而不管這種邏輯關系在計算機中是如何表示的。數據的邏輯結構分為線性結構和非線性結構。若各個數據元素之間的邏輯關系可以用一個線性序列簡單的表示出來，則稱之為線性結構，否則稱為非線性結構。如書目文件中表示一個數據元素，書目文件可表示成（,），所以它是一個線性結構。如圖二：數據元素之間的邏輯關系不能用一個線性序列表示出來，所以數據的邏輯結構是非線性結構。 圖二2. 數據的存儲結構 數據的存儲結構是邏輯結構在計算機存儲器里的實現。數據的邏輯結構在存儲器中的映像應包括數據元素自身值和數據元素之間關系的表示。這樣在存儲器中，某個結點有兩個域，一個是存放自身值的域，用標識符info表示這個

5、域;另一個是存放該結點與其它結點關系的域，用標識符1ink表示這個域。3. 數據的運算 數據的運算是定義在數據的邏輯結構上的，但運算的具體實現要在存儲結構上進行。數據的各種邏輯結構都有相應的運算，常用的運算有檢索、插入、刪除、更新和排序等。 1.3 主要的數據存儲方式數據之間的邏輯關系在計算機中有兩種不同的表示方法：順序映像和非順序映像，相應的得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。 1.3.1 順序存儲結構把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里。特點：只有信息域，沒有指針域。可以通過計算直接確定第i個結點的存儲地址。，其中是第一個結點的存儲地址，m是每個結點所占用的存

6、儲單元數。插入操作和刪除操作不方便。 1.3.2 鏈式存儲結構 鏈式存儲結構就是每個結點至少包括一個指針域，用指針來體現數據元素之間的邏輯關系。特點：除了有信息域，還有指針域；邏輯上相鄰，物理上不必相鄰；插人操作和刪除操作方便。1. 4C語言簡介第二章 線性表2.1 線性表 1. 定義 線性表的邏輯結構是個數據元素的有限序列，()，其中，稱為空表，稱為始結點，稱為終結點，其余的結點有且僅有一個后繼結點，有且僅有一個前趨結點。 2. 線性表具有以下特性（1）線性表中所有數據元素，其性質是相同的，即數據類型是一致的。（2）數據元素之間的相對位置是線性的。3. 對線性表經常進行的一些操作 (l) 查

7、找操作 l 查找第i個結點l 查找值為x的結點(2) 插入操作l 在線性表的第i個結點前面插入一個新結點l 在線性表的第i個結點后面插入一個新結點l 在線性表的值為x的結點前面插入一個新結點l 在線性表的值為x的結點后面插入一個新結點(3) 修改操作l 用新結點替換線性表中的第i個結點l 用新結點替換線性表中值為x結點(4) 排列操作 l 按結點值遞增的順序重新排列線性表的結點l 按結點值遞減的順序重新排列線性表的結點這是常見的對線性表進行的幾種操作。2.2 線性表的順序存儲結構用一連續的存儲空間依次存儲線性表的所有元素。在C語言中順序存儲的線性表是一個一維數組，這樣，在C語言中用如下形式來說

8、明一個順序存儲的線性表。int nodemax; 對順序存儲的線性表進行的操作主要有查找、插入和刪除。1.下面是順序表的查找算法：int find(int x) int i,findi; int flag; findi=0； flag=0； i=0; WHILE( (i<=last-1) &&(!flag) IF (nodei= =x) findi=i； flag=1； ELSE i=i+1； IF (! flag ) findi=-1； RETURN(findi) ; 2.下面是順序表的插入算法：首先看一個例子如表，在第四個結點前面插人一個新結點。首先把單元3到6之間的

9、所有結點向后移動一個單元，空出一個位置，然后將x=100插入到該位置。035167288310041085125614072158910035167288310841255140621578910035167288341085125614072158910下面是在下標號為p的節點前插入一個新結點的算法：void insert(int p,int x) int i; IF ( last= =max) /*max是表的最大長度* printf(“list is full”)；ELSE FOR( i= last-1; i>=p;i- ) nodei+1:=nodei; nodep:=x; la

10、st:=last+1; 3.下面是順序表的刪除算法首先看一個例子如表，將3號單元結點刪除，把單元4到6之間的所有結點向前移動一個單元。035167283310841255140621578910035167288312541405215678910下面是刪除一個結點的算法：void delete (int p )上溢或者下溢int i; IF (p> last-1)| (p<0) printf (“position is wrong”); ELSE FOR( i= p+1; i<=last-1； i+) nodei-1:=nodei; last=last-l; 2.3 線性表

11、的鏈式存儲結構1. 單鏈表線性表的另外一種存儲結構是利用指針把線性表中的各個元素依次鏈接起來形成一個單向鏈接表。一個線性表由若干結點組成，信息域：它用來存放表中的一個元素；指針域：用來存放指向下一個結點的指針。在C語言中，結點的類型定義如下：自定義結構體struct node int data; struct node * next;單向鏈接表的主要運算有：插入和刪除。計算機存儲器中，設置一個空間稱為可利用空間，在獲得一個新結點時，從可利用空間中取結點，調用語句p=( struct node *)malloc (sizeof(struct node )來實現。在刪除一個結點時，將空結點歸還給可

12、利用空間，調用過程free(p)來實現。插入位置可能有四種情況（不設特殊表頭結點）。(1)原來的鏈表是空表，則插入的結點為表頭結點和表尾節點；(2)插入位置在表中第一個結點之前，則插入的結點為新的表頭結點；(3)插人的位置在表的中間；(4)如果鏈表中根本不存在所指定的結點，則把新結點作為新的表尾。下面是對單向鏈接表進行插人操作的算法：在單向鏈接表中，值為的結點前面插入一個新結點。 (struct node *) insertlink (struct node * head；int a, int b) struct node * q , *p ,* s（新節點）； s=( struct node

13、 *)malloc (sizeof(struct node )； s>data=b； IF （head= =NIL） head=s； s>next=NIL； ELSE（三種情況） IF （head>data= =a） s>next=head；head=s； ELSEp=head； WHILE(p>data！=a) && (p>next!=NIL) q=p； p=p>next； IF P>data=a q>next=s s>next=p； ELSE p>next=s； s>next=NIL； RETURN(h

14、ead)；下面是對單向鏈接表進行刪除操作的算法：從單向鏈接表head中刪去值為的結點；如果找不到，則打印出錯信息。 (struct node *) deletelink (struct node * head；int a) struct node * q , p ； IF （head= =NIL） printf(“this is a emptylist”) ELSE IF （head>data= =a） p=head；head= head>next；free(p); ELSEp=head； WHILE(p>data<>a) && (p>nex

15、t!=NIL) q=p； p=p>next； IF P>data=a q>next= p>next ； free(p)； ELSE printf(“no this node in the list”) RETURE(head)；2. 雙鏈表 在單鏈表中通過每一個結點的指針域只能查到該結點的后繼結點，不能查到該結點的前趨結點，這樣一些操作很不方便，如果采用雙鏈表，就可以克服上述缺點。在雙鏈表中，每一個結點有兩個指針域，有一個線性表()，它對應的雙鏈表的形式如下： 圖2.3在C語言中，結點的類型定義如下：struct node int data; struct node *

16、 llink;struct node * rlink;設某個結點的地址為p，它的前趨結點的地址是p>llink，它的后繼結點的地址是p>rlink，它的信息域的內容是p>data。對雙鏈表的操作有插入和刪除，在地址為p的結點后面插人一個新結點，算法如下： void insert(struct node *p , int x) struct node *r，*q； IF (p=nil) printf(void insert)； ELSE q=( struct node *)malloc (sizeof(struct node )； q>data=x； r=p>rli

17、nk； r>llink=q； q>rlink=r； q> llink=p； p>rignt=q； 刪除地址為p的結點算法如下：void delete(struct node *p) struct node *l,*r； IF （p=nil） printf(“void delete”)； ELSE 1=p>llink； r=p>rlink； l>rlink=r; r>llink=1； free(p)； 在雙鏈表上插人和刪除結點的操作如圖2.4和圖2.5。prq圖2.4p圖2.52.3 棧和隊列無論線性表的鏈式存儲結構還是線性表的順序存儲結構，插入和

18、刪除運算都比較麻煩。在順序結構中將導致數據元素的大量移動，在鏈式結構中要逐個結點查詢，把插入和刪除操作限制在一端進行。2.3.1 棧限定只能在一端進行插入和刪除操作的線性表為棧。進行插入和刪除的一端為棧頂，表的另一端為棧底。棧的操作在日常生活中經常見到。棧的存儲結構有兩種：棧的線性存儲結構：用stack n 表示棧，n是棧中允許最多的元素的個數，top指向棧頂元素所在的位置，stacktop表示棧頂元素，當top=-1時表示棧空，當top=n-1時表示棧滿，棧空時不能做出棧操作，棧滿時不能作入棧操作。棧的順序存儲的算法void instack(int top ,int x)if (top= =

19、n-1)printf (“overflow”)else top=top+1;stack top=xvoid outstack(int top,) int y;if (top= =-1)printf(“underflow”);elsey=stack top; top=top-1;棧的鏈式存儲結構：棧的入棧和出棧操作實際是對鏈表的表頭進行插入和刪除操作。用top表示一個棧的棧頂指針。struct node int data; struct node * next;下面給出兩個過程，其中inlinks的功能是將元素x插入到棧頂；outlinks的功能是刪除棧頂元素，并將此元素送給y。(struct

20、node *) inlinks(struct node *top ,int x) struct node *q;q=( struct node *)malloc (sizeof(struct node )；q>data=x;q>next=top; top=q; return(top); （struct node *）outlinks(struct node * top) int y;struct node *q;IF (top=nil) printf(“underfIow”); ELSE q=top;y=q>data;top=q>next；free(q);return(

21、top); 2.3.2 隊列 隊列是限定在一端進行插入操作，在另一端進行刪除操作的線性表。插入的一端為隊尾，刪除的一端為隊首。隊列的存儲結構有兩種：隊列的順序存儲結構，隊列的鏈式存儲結構。1. 隊列的線性存儲結構：隊列可以用一個向量qm表示，front、rear分別表示排頭指針和排尾指針；front指向實際排頭元素的前一個位置(表格中用指針F表示)，rear指向實際排尾元素所在的位置(表格中用指針R表示)。初始條件是F=R=-1。下面看一下隊列進排出排的情況。可以看出隊列上溢的條件是R=m-1，而下溢的條件是R=F。從圖2.6中看出，當R=4時若有需要加人隊列中，這時滿足上溢條件，拒絕進入隊列

22、，但此時隊列還有三個空額，這種現象稱為假溢出。如何避免假溢出現象呢?我們把隊列看成一個循環表，假設qm為循環數組，則視q0接在qm-1之后形成循環。如圖2.7假定循環隊列以順時針方向伸長，頭指針總是在順時針方向落后于隊列中的第一個元素的一個位置，尾指針指向最后加入的元素位置。初始狀態（隊列為空）時front=rear=m-1，每加入一個元素時，尾指針向順時針方向移動一個位置，即rear=rear+1;if rear=m;then rear=1;同樣，每刪除一個元素時，頭指針便向順時針方向移動一個位置。front=front+1;if front=m;then front=1;在循環隊列中如何判

23、別是空還是滿呢？當隊列為空或滿時，都有front=rear，一種辦法就是尾指針從后面追上頭指針，作為隊列滿的特征；另一種辦法設一個標志位以區別是空還是滿。在C語言中定義隊列類型：struct queue int itemmax; int front ; int rear ; struct queue q;其中數據項item定義一個容量為0max-1順序分配的隊列，隊列中結點的數據是整數，q.front和q.rear分別是排首和排尾的指針。 其中，itemmax: item0itemmax-1;初始有：q.front=q.rear=m-1，q.rear=-1；下面的兩個程序insersq和rem

24、ovesq，描述了在用數組表示的順序分配的隊列中，執行進排和出排操作算法。在insersq中它是把數據x添加到已知的隊列中去。在removesq中，它把當前隊列中的排首結點出排，并把出排結點的數據存人變量y中。設q.rear=-1表示棧空，初始時有q.rear=-1，q.front為0max-1之間的任意一個值。順序分配的隊列上的進排操作算法如下：void insertq (struct queue q ,int x) if(q.rear=q.front) printf(“queue is full”); else if(q.rear=-1)q.rear=q.front; if(q.rear=

25、max-1)q.rear=0;else q.rear=q.rear+1 q.itemq.rear=x; 順序分配的隊列上的出排操作算法如下：void removeq (struct queue q) int y; if (q.rear=-1)printf(“queue is empty”); else if(q.front=max-1) q.front=0; else q.front=q.front+1; y=q.itemq.front;if(q.front=q.rear) q.rear=-1;2. 隊列的鏈式存儲結構：在隊列的鏈接表示法中，每個結點由兩個域data和next組成，還有兩個指針

26、變量front和rear來指示隊列的排首和排尾，如圖2.8。在隊列上執行進排操作，實際上是在rear指向的鏈接表的表尾處插入一個結點，出排操作實際是在front指向的鏈接表的表首刪除一個結點，一旦front=nil，即發出隊列為空的信息。圖2.8鏈接分配隊列上的插入操作算法：void insertlq（struct node *front, struct node * rear, int x） struct node *p;p=( struct node *)malloc (sizeof(struct node )；p>data=x;p>next=nil;if(front= = n

27、il ) front=p;else rearànext=p;rear=p;鏈接分配隊列上的刪除操作算法：void removelp(struct node *front, struct node * rear) int y;struct node *p; if(front= =nil) printf(“queue is empty”); else p=front; front=pànext; y=pàdata;free(p); 第三章 樹樹形結構是一類重要的非線性結構3.l 樹及二叉樹3.1.1 樹的定義 樹是一個結點或多個結點有限集合，有一個特定的結點稱為根，其

28、余的結點分為個不相交集合，每個集合又是一棵樹，稱為子樹。如圖3.1：ABCDEFGHIJ圖3.1 子女：結點的各個子樹的根稱為該結點的子女； 雙親：該結點是其子女的雙親； 兄弟：具有相同雙親的結點稱為兄弟； 結點的度：一個結點子樹的個數； 葉：度為0的結點為葉結點； 分支結點：度不為0的結點為分支結點； 結點的層數：根結點的層數為0，其余結點的層數等于其雙親結點的層數加1；樹林或森林：0棵或多棵不相交的樹的集合。3.1.2 二叉樹的定義 二叉樹是結點的有限集合，這個集合或者為空，或者由一個根結點及兩棵不相交的稱為根的左子樹和右子樹的二叉樹組成，注意二叉樹不是樹的特殊情況，二叉樹的子樹有左右之分

29、，而樹沒有左右之分。如圖3.2：ABECFGDHIJ圖3.2完全二叉樹 如果一棵二叉樹最多只有最下兩層結點的度可以小于2，并且最下層結點都集中在該層的最左邊的若干位置上，則稱此二叉樹為完全二叉樹。3.1.3 樹的二叉樹表示 特點：每一棵樹都能唯一地轉換到它所對應的二叉樹。 轉換方式：凡是兄弟都用連線連起來。只留下雙親到第一個子女的連線，雙親到其余子女的連線都去掉。 意義：由于樹的二叉樹表示可以有利于樹的存儲和運算，所以把對樹的處理轉換成對二叉樹的處理。3.2 二叉樹和樹的周游 周游：周游一棵樹形結構就是按一定次序系統地訪問該結構中的所有結點，使每個結點恰好被訪問一次。3.2.1 二叉樹的周游

30、通常二叉樹的周游一般有三種算法：前序遍歷法、中序遍歷法、后序遍歷法。1. 中序遍歷法中序遍歷法的遞歸定義為： 若二叉樹為空，則退出，否則： （1）遍歷左子樹 （2) 訪問根結點 （3) 遍歷右子樹 （4) 返回 圖3.2是一棵二叉樹，按照中序法遍歷此二叉樹，得到如下的表達式：EFBGCHIJDA。2. 前序遍歷法 前序遍歷法的遞歸定義為： 若二叉樹為空，則退出，否則：（1） 訪問根結點； （2）遍歷左子樹； （3）遍歷右子樹； （4）返回。 圖3.2是一棵二叉樹，按照前序法遍歷此二叉樹，得到如下的表達式： ABEFCGDHIJ。 3. 后序遍歷法 后序遍歷法的遞歸定義為： 若二叉樹為空，則退出

31、，否則： （1） 遍歷左子樹 （2） 遍歷右子樹 （3）訪問根結點 （4） 返回圖3.2是一棵二叉樹，按照后序法遍歷此二叉樹，得到如下的表達FEGJIHDCBA。 3.2.2 樹和森林的周游 可以按深度優先方式，也可以按廣度優先方式周游樹和森林。 按深度優先方式有兩種主要的周游次序。 1. 先根次序周游： 訪問第一棵樹的根，按先根次序周游第一棵樹的子樹，按先根次序周游其他的樹。 2. 后根次序周游： 按后根次序周游第一棵樹的子樹，訪問第一棵樹的根，按先根次序周游其他的樹。 圖3.1是一棵樹，按先根次序周游，結點排列的次序是ABEFCGDHIJ。按后根次序周游，結點排列的次序是EFBGCHIJD

32、A。 值得一提的是圖3.2的二叉樹是圖3.1的樹轉換過來的，對樹的先根次序周游正好等同于對對應的二叉樹的前序法周游；對樹的后根次序周游正好等同于對對應的二叉樹的中序法周游。3.3樹、二叉樹的存儲1二叉樹的Rlink-Llink表示法二叉樹采用鏈式存儲方法來存儲，二叉樹結點三個域：Info信息域，Llink存放左子女的指針，Rlink存放右子女的指針，二叉樹這種表示方法稱為Rlink-Llink表示法,樹的存儲可以轉換成對二叉樹的存儲。2線索二叉樹有N個節點的二叉樹，共有2N個指針域，其中N-1個指針域利用上了，但還有N+1個指針域沒有利用上，把這樣的指針域利用起來，用以存放指向該結點前驅或后繼

33、的指針。設每個指針域有一個特征位tag,左指針域特征位為Ltag,右指針域的特征位為Rtag當Ltag=0，表示指向它的左子女。Ltag=1，表示指向它的前驅。當Rtag=0，表示指向它的右子女。Rtag=1，表示指向它的后繼。3完全二叉樹的順序存儲由于完全二叉樹結構上的特點，通常采用順序方式存儲。首先把完全二叉樹的所有結點按照從上到下，從左到右的次序，從1到n編號，得到一個線性序列，把此線性序列按順序方式存儲，即用一個一維數組來存儲。完全二叉樹的運算是周游：順次訪問向量中的各個數據元素，即從上到下，從左到右周游一棵完全二叉樹。知道某一結點的編號i,可以知道其雙親及左右子女的編號。雙親編號 i

34、/2 左子女 2i (2i<=n,i<=n/2,否則無左子女。)右子女 2i+1 (2i+1<=n,i<=(n-1)/2，否則無右子女。)3.4二叉樹前序遍歷非遞歸調用子程序 void preorder(struct node *t) struct node *p； struct node *smax; int top; top=-1; p=t;do WHILE (p!=nil) printf(“%d”,p->data)； IF ( p->rlink!=nil) top=top+1; stop=p->rlink; p=p->llink; IF(

35、top！= -1) p=stop; top=top+1; while(p！=nil)|(top！ = -1) 3.4二叉樹前序遍歷非遞歸調用子程序 void order(struct node *t) struct node *p； struct node *smax; int top; top=-1; p=t;do WHILE (p!=nil) top=top+1; stop=p； p=p->llink; IF( top！= -1) p=stop; top=top+1;printf(“%d”,p->data)； p=p->rlink; while(p！=nil)|(top！

36、 = -1) 3.5 樹結構的應用樹結構有著廣泛的應用。樹結構可以表示通信及數據傳送中的二進制編碼，還可用于信息檢索和排序。3.5.1 二叉排序樹定義 如果一棵二叉排序樹的每個結點對應于一個碼值，整個二叉樹各個結點對應的碼值組成一個碼值集合，此碼值集合中各個元素在二叉樹中是按一定次序排列的，則稱此二叉樹為二叉排序樹。其中的次序是這樣的：規定二叉排序樹里每個結點的左子樹中結點的碼值都小于該結點的碼值，而右子樹中結點的碼值都大于此結點的碼值。 按下列原則建立一棵二叉排序樹。 (1)令R1是二叉樹的根 (2)若R2<Rl，則令R2為R1的左子樹的根結點，否則令R2為Rl的右子樹的根結點。 (3

37、)對R3，R4Rm重復上述過程（2）。 對二叉排序樹進行的操作有查找、插入和刪除。 3.5.2 對二叉排序樹進行查找 查找一個結點的算法如下： 首先將被查找的值與根結點的值進行比較，如果被查找的值大于根結點的值，則查找根結點的右子樹，否則查找根結點的左子樹，直到找到給定值的結點。 二叉排序樹的查找算法 struct node *find(struct node *tree, int x) int f; struct node *p,*q; p=tree; f=0; while(!f)&&(p!=nil) if(p->data=x) f=1;else if(x<p-&

38、gt;data) p=p->llink; else p=p->rlink; if(f) q=p; else q=nil; return(q);3.5.3 在二叉排序樹中插人結點(1)在二叉排序樹中插入結點例子如圖3.3，在二叉排序樹中插入值為243和614兩個結點。插人的結點一定為二叉排序樹的葉結點。（2）給出二叉排序樹中插入一個值為x的新結點的算法 二叉排序樹中的插入結點的算法 在二叉排序樹中插入一個節點算法void insertree(struct node *tree, int x ) struct node *p,*q; if(tree=nil) p= (struct no

39、de *)malloc(sizeof(struct node); p->data=x; p->rlink=nil; p->llink=nil; tree=p; else p=tree; while(p!=nil) q=p; if (x<p->data) p=p->llink; else p=p->rlink; p=(struct node *)malloc(sizeof(struct node);p->data=x; p->rlink=nil; p->llink=nil;if (x<q->data) q->llink

40、=p;else q->rlink=p; 3.5.3 在二叉排序樹中刪除結點 在二叉排序樹中刪除結點是指刪除指定的結點，而不是把以這個結點為根的子樹都刪掉，刪除結點后還要保持二叉樹的性質。 設p為被刪除結點，f為p的雙親結點。 (1)被刪除的結點沒有左右孩子，則可直接刪去p； (2)被刪除的結點p沒有左子樹，則可用右子樹根結點s取代結點p的位置；(3)被刪除的結點沒有右子樹則可用左子樹的根結點取代結點的位置；(4)被刪除結點P有左右子樹，則要找出右子樹中碼值最小的結點s，用s取代p，如圖3.4。二叉排序樹結點p的刪除算法void detree(struct node *t, struct

41、node *f, struct node *p) struct node *q,*s; int bool; bool=0; if(p->llink=nil)|(p->rlink=nil) if(p->llink=nil) if(p= =t) t=p->rlink;else s=p->rlink; bool=1; else if(p= =t) t=p->llink;else s=p->llink; bool=1; (if) else q=p; s=q->rlink; while(s->llink!=null) q=s; s=s->lli

42、nk; s->llink=p->llink; if (q!=p) q->llink=s->rlink; s->rlink=p->rlink; if (p=t) t=s; else bool=1; if (bool=1) if(p=f->llink) f->rlink=s; else f->rlink=s; free(p);q=p; s=q->llink; while(s->rlink!=null) q=s; s=s->rlink; s->rlink=p->rlink; if (q!=p) q->rlink

43、=s->llink; s->llink=p->llink; 第二部分 操作系統第一章 緒論 計算機發展到今天，無論是個人計算機，還是巨型計算機系統，毫無例外都配置一種或多種操作系統。1.1 操作系統任何一個計算機系統都有由兩部分組成：計算機硬件和計算計算機軟件。計算機硬件通常由中央處理機、存儲器、輸入設備和輸出設備等組成，它是計算機系統的物質基礎。計算機軟件是為了方便用戶和充分發揮計算機效率的各種程序及有關的文檔的總稱，包括匯編程序、解釋程序、編譯程序、操作系統、診斷程序、數據庫管理系統及各種用戶應用程序。沒有任何軟件支持的計算機稱為裸機，它僅僅構成了計算機的物質基礎，而實際

44、呈現在用戶面前的計算機系統是經過若干層軟件改造的計算機。如圖1.1，裸機在最里層，它的外面是操作系統。圖1.1經過操作系統提供的資源管理功能和方便用戶的各種服務功能把裸機改造成功能更強、使用更為方便的機器，通常稱為虛擬機。1.1.1 操作系統定義 操作系統是控制、管理計算機的軟硬件資源，合理的組織計算機工作流程及方便用戶的程序集合。1.1.2 操作系統的功能操作系統所具有的功能從三個方面來看。1. 從資源管理角度來看 操作系統是用來控制管理計算機資源的，并調度對系統中各類資源的使用。資源包括軟件資源和硬件資源。硬件資源有中央處理機、內存儲器、外部設備。軟件資源包括系統程序、應用程序和數據文件。

45、操作系統對各種資源的管理如下：(1)處理機管理：對系統中的各臺處理機及其狀態進行登記、管理各作業(進程)對處理機的要求，并按一策略將系統中的各臺處理機分給要求的作業(進程)使用。(2)存儲器管理：用合理的數據結構形式記錄系統中主存儲器的使用情況，并按照一定策略在提出存儲請求的各作業之間分配主存空間，保護主存儲器中的信息不被其它作業(進程)有意或無意破壞(3)輸人輸出設備管理：記住系統中各類設備及其狀態，按各類設備的特點和不同的策略把設備分給要求的作業使用。許多系統還注意優化設備的調度，以提高設備的利用率。(4)信息管理：操作系統中的信息管理功能主要涉及文件的邏輯組織和物理組織、目錄的結構以及對文件的操作，近年來還特別注意對文件中信息的保護和保密措施。2. 從合理組織計算機流程的觀點來看操作系統首先看一個例子，設有A、B、C三個程序，Ai、Ac、Ao、Bi、Bc、Bo、Ci、Cc、Co分別表示各程序的輸入、計算和輸出程序段，則各程序段的執行順序如圖1.2。從例子可以看出各個程序段之間是相互制約的、又是相互推進的。如何組織協調好各程序段之間的執行是操作系統的又一大功能圖1.2 3 . 從用戶角度來看在計算機發展初期，是沒有操作系統的，每當用戶使用計算機處理它的作業，首先把用戶程序在內存中定位(直接參與內存的分配)，