在當今社會，計算機技術已經滲透到生產和生活的方方面面，掌握基本的計算機軟硬件技術已經成為工科非計算機專業大學生求職的必備要求。本書針對工科非計算機專業本科生的需要，是一本有關計算機軟件知識及開發技術的基礎教材，主要講授計算機軟件的基本概念、方法及實用技術，書中內容涉及數據結構、數據庫技術、操作系統和軟件工程。本書除了理論知識的介紹外，還注重讀者實際編程和動手能力的提高，注重理論和實踐的聯系，主要特色如下。
(1)在算法理論之后附帶可運行的程序示例。本書中的大部分程序都經過作者親自在C語言編程環境下運行調試。學生可以在學習理論知識之后直接上機運行相應程序，獲得直觀感受，從而鞏固學習效果，提高學習興趣。
(2)理論聯系實際。書中附有精選的課后習題作為補充，這些習題很多是實際中可能會遇到的情況，在數據庫章節也給出了實際數據庫的示例，這些都能夠使學生更好地把學到的理論與實際結合起來。
本書共分7章，各章安排如下。
第1章主要介紹計算機系統及計算機軟件的概念及發展。
第2章主要介紹數據結構和線性數據結構的基本概念，包括線性表、棧、隊列和數組等線性數據結構的邏輯概念和存儲結構，以及在相應存儲結構下的查找、刪除、插入等算法，并給出了算法運行的結果示例。
第3章主要介紹非線性數據結構樹和圖的基本概念和存儲結構，以及在相應存儲結構下的算法，重點介紹了二叉樹的存儲結構與算法。
第4章介紹幾種常用的查找和排序算法，給出了各種算法的設計思想和實際例程，并對各種查找和排序算法進行了比較。
第5章介紹數據庫設計的基本概念、基本原理、方法及技術，并簡要介紹實體聯系模型(ER模型)、關系模型、關系運算、關系數據庫設計理論、數據庫語言SQL和數據庫的設計流程等知識，為開發數據庫應用系統打下一定的基礎。
第6章主要介紹系統軟件中*靠近硬件的一層軟件——操作系統，給出了操作系統的基本概念、發展歷程以及操作系統的基本功能：中央處理器管理、存儲管理、設備管理、文件管理，*后介紹了幾種常見的操作系統。
第7章介紹軟件工程的基本概念以及軟件開發過程中的系統分析方法與設計方法。
本書在編寫過程中參考了計算機軟件技術和數據結構方面的經典教材，取長補短，力爭做到深入淺出，注重實踐。本書由北京信息科技大學楊飛主編，北京信息科技大學許曉飛、王軍茹副主編。書中第1~4章由楊飛編寫，第5、7章由許曉飛編寫，第6章由王軍茹編寫。
由于編者水平有限，書中難免存在疏漏和不妥之處，懇請廣大讀者批評指正。
作者
2016年9月
第3章
非線性數據結構
在計算機科學中，除了前面章節介紹的線性數據結構之外，還存在許多線性數據結構描述不了的問題，如數據元素之間的層次關系、分支關系等，這些復雜關系需要靠非線性數據結構來進行描述。樹和圖就是兩種*廣泛使用的非線性結構，本章將介紹樹和圖的定義以及基本操作。
3.1樹與二叉樹
〖*2〗3.1.1樹的基本概念
1. 樹的定義
在數據結構中，樹的定義*常用的方式是一種遞歸定義。樹(Tree)是包含n(n≥0)個結點的有窮集合。N=0時稱為空樹，否則任何一個非空樹都滿足如下條件：
（1） 有且僅有一個特定結點被稱為根結點(Root)；
（2） 除根結點之外的其余數據元素被分為m(m≥0)個互不相交的集合T1，T2，…,Tm-1，其中每一個集合本身也是一棵樹，被稱作子樹。
很顯然，在上面樹的定義當中又用到了樹的概念，因此這是一個遞歸定義，它顯示了樹的固有特性，這在本章后續的算法當中會有充分的體現。
圖31樹形結構示意圖
圖31是包含了9個結點的樹，即T{A, B, C ,…, H, I}，其中A為樹T的根結點，除根結點A之外的其余結點分為兩個不相交的集合： T1{B, D, E, F, H, I}和T2{C, G}，T1和T2本身也是一棵樹，分別稱為根結點A的兩棵子樹，而兩棵子樹T1和T2的根結點分別為B和C。其余結點又分為三個不相交的集合： T11{D}，T12{E, H, I}和T13{F}。T11，T12和T13又構成了T1子樹的三棵子樹。如此繼續向下分為更小的子樹，直到每棵子樹只有一個根結點為止。
下面結合圖31給出樹的一些基本術語，通過這些術語能夠更好的理解樹形結構。
2. 樹的基本術語
（1） 結點的度： 一個結點具有的子樹的個數稱為該結點的度。圖31中，該樹根結點A的度是2，結點B的度是3，而結點D沒有子樹，因此結點D的度為0。
（2） 葉子： 度為0的結點稱為葉子或終端結點。圖31中樹的葉子結點是D、H、I、F、G。
（3） 樹的度： 樹中所有結點度的*大值稱為樹的度。圖31中樹的度為3。
（4） 分支結點： 與葉子相對應，樹中度大于0的結點稱為分支結點，分支結點有時也稱非終端結點。一棵樹的結點除葉子結點外，其余的都是分支結點。
（5） 孩子結點： 樹中某結點子樹的根稱為該結點的孩子結點。
（6） 雙親結點： 與孩子相對應，如果一個結點存在孩子結點，則這個結點就稱為孩子結點的雙親。雙親結點有時也稱父親結點，圖31中A結點的孩子結點是B和C，同時結點A又是B和C的雙親結點。
（7） 兄弟結點： 具有同一雙親的結點互稱為兄弟結點。圖31中結點D、E、F是兄弟結點。
（8） 堂兄弟結點： 雙親在同一層的結點互稱為堂兄弟結點。圖31中結點D和G是堂兄弟結點。
（9） 子孫結點： 一個結點的所有子樹中的結點稱為該結點的子孫結點。
（10） 結點層數： 規定樹的根結點層數為1，其孩子結點為第2層。以此類推，結點層數等于其雙親結點加1，由此可得到每個結點的層數。
（11） 樹的深度： 樹中所有結點的*大層數稱為樹的深度。如圖31所示，該樹的深度為4。
（12） 有序樹： 如果一棵樹中結點的各子樹從左到右是有次序的，即若交換了某結點各子樹的相對位置，則構成不同的樹，則稱這棵樹為有序樹。
（13） 森林： 有限棵不相交的樹的集合稱為森林。
通常情況下，在計算機中表示一棵樹時，本身就隱含了一種確定的相對次序，因此后面本書中所討論的樹默認都是有序樹。
3.1.2二叉樹及其性質
在介紹樹形結構的算法之前，先來學習一種特殊形態的樹——二叉樹。二叉樹是樹形結構的一個重要類型，許多實際問題可以抽象出來的數據結構往往滿足二叉樹的形式，且二叉樹和普通樹之間也存在相互轉換的關系。
1. 二叉樹的定義
二叉樹是特殊形態的樹，因此其定義可以參照普通樹的定義，顧名思義與普通樹的*主要區別在于二叉樹中每個結點的兒子至多有兩個，即每個結點*多有兩個向下的分叉，并由此而得名，其定義如下。
二叉樹(Binary Tree)是個有限元素的集合，該集合或者為空，或由一個根結點和兩棵互不相交的、分別被稱為左子樹和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹。
很顯然這也是一個遞歸定義，由定義可得到二叉樹的兩個基本特點，具體如下。
(1) 二叉樹中不存在度大于2的結點，即每個結點至多有兩個孩子。
(2) 二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結點只有一棵子樹，也要區分它是左子樹還是右子樹。因此二叉樹具有五種基本形態，如圖32所示。
圖32二叉樹的5種基本形態
思考： 根據樹和二叉樹的定義，讀者可以自己試著畫出具有3個結點的樹和二叉樹的形態。
2. 二叉樹的性質
【性質3.1】一棵非空二叉樹的第i層結點數*多為2i－1(i≥1)。
證明： 該性質可由數學歸納法，根據二叉樹的定義來證明。
【性質3.2】一棵深度為k的二叉樹中，*多具有2k－1(k≥1)個結點。
證明： 在深度為k的二叉樹中，只有當每層的結點數都為*大值時，樹的總結點數才為*大值，因此根據性質3.1可以得到深度為k的二叉樹中結點數*多為：
20+21…+2k－1=2k－1
【性質3.3】在一棵非空二叉樹中，如果其葉子結點數為n0，度數為2的結點為n2，則有：
n0=n2+1
證明：
(1) 設M為二叉樹的結點總數，n1為二叉樹中度為1的結點數，則有： M=n0+n1+n2；
(2) 此外，根據二叉樹的定義，度為1的結點有1個孩子，度為2的結點有2個孩子，因此二叉樹中的孩子結點數為n1 +2n2；
(3) 而在二叉樹中，只有根結點不是任何結點的孩子，所以二叉樹的總結點樹又可表示為M=n1+2n2+1。
由此得到M=n0+n1+n2=n1+2n2+1，*終推導出n0=n2+1。
【性質3.4】具有n個結點的完全二叉樹的深度為lbn+1。
在證明性質3.4之前先來介紹兩種特殊形態的二叉樹——完全二叉樹和滿二叉樹。
一棵深度為k且有2k－1個結點的二叉樹稱為滿二叉樹，即該滿二叉樹中的結點數為*大值。圖33(a)給出了一棵深度為4的滿二叉樹，這種二叉樹的特點是所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上。
圖33深度為4的滿二叉樹
可以對滿二叉樹的結點自上而下、自左而右進行連續編號，約定編號從根結點起，編號結果如圖33(b)所示。由此可引出完全二叉樹的定義如下： 深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹。圖34給出了一個深度為4的完全二叉樹。
圖34深度為4的完全二叉樹
由此可以總結出完全二叉樹和滿二叉樹的特點如下。
（1） 完全二叉樹的葉子結點只能出現在*下層和次下層，且*下層的葉子結點集中在樹的左部。
（2） 一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。
下面證明性質3.4： 設一棵完全二叉樹的深度為k，結點個數為n，則根據完全二叉樹的定義和性質3.2可知，結點的個數n要位于深度為k-1層和k層的*大結點數之間，即
2k－1≤n<2k
對不等式兩邊同取對數可得
k－1≤lbn
又因為k-1和k是相鄰的兩個整數，所以
k－1=lbn
由此性質3.4得證，即k=lbn+1。
【性質3.5】對于具有n個結點的完全二叉樹，如果按照從上至下，同一層按照從左到右的順序對二叉樹的所有結點從1開始順序編號，則對于任意的序號為i的結點，有如下性質。
(1) 如果i=1，則結點i是二叉樹的根，該結點無雙親； 如果i>1，則序號為i的結點的雙親結點序號為i/2。
(2) 如果2i>n，則結點i無左孩子，否則其左孩子結點的序號為2i。
(3) 如果2i+1>n，則結點i無右孩子，否則其右孩子結點序號為2i+1。
此性質可采用數學歸納法證明。
3.1.3二叉樹的存儲結構
二叉樹的存儲方式主要有順序存儲和鏈式存儲兩種方式，下面進行詳細介紹。
1. 二叉樹的順序存儲
所謂二叉樹的順序存儲，就是用一組連續的存儲單元，按照從上至下、從左到右的順序依次存放二叉樹中的結點。因此，依據二叉樹的性質，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結點的序號可以*地反映出結點之間的邏輯關系。圖34中的完全二叉樹的順序存儲結構如圖35所示。
……
新書資訊