【正文】 狀空間，供隊(duì)列循環(huán)使用。 ? 從排頭指針 front指向的后一個(gè)位置直到隊(duì)尾指針 rear指向的位置之間所有的元素均為隊(duì)列中的元素。圖 b是在圖 a的循環(huán)隊(duì)列中又加入了 2個(gè)元素后狀態(tài)，圖 c是在圖 b的循環(huán)隊(duì)列中退出了 1個(gè)元素后的狀態(tài)。 ? 循環(huán)隊(duì)列的初始狀態(tài)為空，即 rear=front=m ? 循環(huán)隊(duì)列有兩種運(yùn)算：入隊(duì)與退隊(duì) ? 入隊(duì)：在循環(huán)隊(duì)的隊(duì)尾加入一個(gè)新元素。 ? 上溢：當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于排頭指針，說明隊(duì)列滿，不能進(jìn)行入隊(duì)運(yùn)算。 ? 有兩個(gè)基本操作：首先將排頭指針進(jìn)一（即 front=front+1），并當(dāng) front=m+1時(shí)置 front=1，然后將排頭指針指向的元素賦給指定的變量。 2022/2/9 26 線性鏈表 ? 對于大的線性表，特別是元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。 ? 線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 數(shù)據(jù) 1 數(shù)據(jù) 2 數(shù)據(jù) n NULL HEAD … 2022/2/9 27 線性鏈表 ? 當(dāng) HEAD=NULL（或 0）時(shí)稱為空表。 ? 線性單鏈表：每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針域只能找到后件結(jié)點(diǎn)。 ? 帶鏈的棧：可以用來收集計(jì)算機(jī)存儲(chǔ)空間的所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。由這種方法找到的結(jié)點(diǎn) p有兩種可能：當(dāng)線性鏈表中存在包含元素 x的結(jié)點(diǎn)時(shí)，則找到的 p為第一次遇到的包含元素 x的前一個(gè)結(jié)點(diǎn)序號；當(dāng)線性鏈表中不存在包含元素 x的結(jié)點(diǎn)時(shí)，則找到的 p為線性鏈表中的最后一個(gè)結(jié)點(diǎn)號。新結(jié)點(diǎn)可以從可利用棧中取得。 2022/2/9 30 循環(huán)鏈表 ? 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向頭結(jié)點(diǎn)。 ? 循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域任意，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。 2022/2/9 31 樹與二叉樹 ? 樹是一種簡單的非線性結(jié)構(gòu)，所有數(shù)據(jù)元素之間具有明顯的層次特性。 書 第一章 第二章 第三章 第四章 2022/2/9 32 樹與二叉樹 ? 結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為 父結(jié)點(diǎn) 。 ? 結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 ? 一個(gè)結(jié)點(diǎn)所擁有的后件結(jié)點(diǎn)的個(gè)數(shù)，稱為該 結(jié)點(diǎn)的度 。樹的最大層次稱為 樹的度 。葉子結(jié)點(diǎn)沒有子樹。多重鏈表中的每個(gè)結(jié)點(diǎn)描述了樹中的對應(yīng)結(jié)點(diǎn)的信息，而每個(gè)結(jié)點(diǎn)中的鏈域（即指針域）個(gè)數(shù)將隨樹中該結(jié)點(diǎn)的度而定。 ? 二叉樹具有如下特點(diǎn)： ? 非空二叉樹只有一個(gè)根結(jié)點(diǎn)。 ? 二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為 2；一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。 2022/2/9 34 二叉樹的基本性質(zhì) ? 在二叉樹的第 k層上，最多有 2k1(k≥1)個(gè)結(jié)點(diǎn)。 211+221+… +2m1=2m1 ? 在任意一棵二叉樹中，度為 0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為 2的結(jié)點(diǎn)多一個(gè)。 2022/2/9 35 滿二叉樹 ? 滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 ? 深度為 m的滿二叉樹有 2m1個(gè)結(jié)點(diǎn)。 ? 如果從根結(jié)點(diǎn)起，對二叉樹的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行連續(xù)編號，則深度為 m、且有 n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度為 m的滿二叉樹中編號從 1到 n的結(jié)點(diǎn)一一對應(yīng)，稱之為完全二叉樹。 ? 滿二叉樹一定是完全二叉樹，但完全二叉樹一般不是滿二叉樹。如果從根結(jié)點(diǎn)開始，按層序（每一層從左至右）用自然數(shù) 1,2,… ,n給結(jié)點(diǎn)編號，則對于編號為 k(k=1,2,… ,n)的結(jié)點(diǎn)有以下結(jié)論： ? 若 k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)；若 k1，則該結(jié)點(diǎn)父結(jié)點(diǎn)編號為 INT(k/2)。否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)。 2022/2/9 38 二叉樹的存儲(chǔ)結(jié)構(gòu) ? 計(jì)算機(jī)中，二叉樹常采用 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 ? 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表。 ? 二叉樹的遍歷分為： 前序遍歷、中序遍歷、后序遍歷 ? 前序遍歷：首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。 ? 后序遍歷：先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。 ? 順序查找的基本方法： 從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到；若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素。 2022/2/9 42 二分法查找 ? 只適用于順序存儲(chǔ)的有序表。這個(gè)過程一直進(jìn)行到查找成功或子表長度為 0（說明線性表中沒有該元素）為止。 ? 對于長度為 n的有序線性表，在最壞情況下，二分法查找只需要比較 log2n次。 【 二分查找要求 】 ： 。 【 優(yōu)缺點(diǎn) 】 折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好 。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。 重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。 while(low=high) { mid=(low+high)/2。 else if(xa[mid]) high=mid1。 } return 0。 printf(請輸入查詢數(shù)據(jù)： \n)。x)。 if(y) printf(數(shù)據(jù)已經(jīng)找到，序號為： %d\n,y)。 } 排序技術(shù) ? 排序：指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。 ? 冒泡排序：通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。 ? 快速排序：從線性表中選取一個(gè)元素，設(shè)為 T，將線性表后面小于 T的元素移到前面，而前面大 T的元素移到后面，結(jié)果就將線性表分成了兩部分， T插入到分界線的位置處，這個(gè)過程稱為線性表的分隔。 2022/2/9 47 冒泡排序的 C語言程序 2022/2/9 48 分析說明： 1）相鄰兩數(shù)比較： a[j]＞ a[j+1] 2）第一輪： 6個(gè)數(shù)， j=1~5；循環(huán) 5次，找出最大數(shù)，放在最后。 4）余此類推，經(jīng)過 5輪，將 6個(gè)數(shù)排序輸出。 i＜ 5 。 j＜ 5– i。 for(i=0。i++) { for ( j=0。 j++) if (a[j]a[j+1]) { k=a[j]。a[j+1]=k。 popsort(b,N)。 for(i=0。i++) printf(%d ,b[i])。 ?從線性表的第 2個(gè)元素開始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面已經(jīng)有序的子表中。 ?在最壞情況下，簡單插入排序需要 n(n1)/2次比較。 ?在最壞情況下，希爾排序所需的比較次數(shù)為 2022/2/9 51 簡單插入排序的 C語言程序 2022/2/9 52 插入排序算法思路 假定這個(gè)數(shù)組的序是排好的 ,然后從頭往后 ,如果有數(shù)比當(dāng)前外層元素的值大 ,則將這個(gè)數(shù)的位置往后挪 ,直到當(dāng)前外層元素的值大于或等于它前面的位置為止 .這具算法在排完前 k個(gè)數(shù)之后 ,可以保證 a[1…k] 是局部有序的 ,保證了插入過程的正確性 . 編輯本段算法描述 一般來說，插入排序都采用 inplace在數(shù)組上實(shí)現(xiàn)。 int temp。in。//存儲(chǔ)臨時(shí)數(shù)據(jù) for(j=i 。amp。 j) { array[j]=array[j1]。//找到插入位置，插入數(shù)據(jù) } } 程序： 2022/2/9 54 void main() { int i,b[N]={123,7,9,12,7,89,93,97,103,18}。 printf(排序結(jié)果為： \n)。iN。 } 排序技術(shù) ? 選擇類排序 ? 簡單選擇排序法：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面，然后對剩下的子表采用同樣的方法，直到子表空為止。 ? 堆排序 ?在最壞情況下，堆排序需要比較的次數(shù)為 nlog2n 2022/2/9 55 簡單選擇排序的 C語言程序 2022/2/9 56 簡單選擇排序的基本思想 n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n1趟直接選擇排序得到有序結(jié)果： ①初始狀態(tài)：無序區(qū)為 R[1..n]，有序區(qū)為空。 …… 2022/2/9 57 ③ 第 i趟排序 第 i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為 R[1..i1]和 R[i..n](1≤i≤n1)。 這樣， n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n1趟直接選擇排序得到有序結(jié)果。 for(i=0。i++) { k=i。j=n1。 if(k!=i) { temp=a[i]。 a[k]=temp。 selectionsort(b,N)。 for(i=0。i++) printf(%d ,b[i])。 ? 要形成良好的設(shè)計(jì)風(fēng)格，主要應(yīng)注意和考慮下述一些因素： ? 源程序文檔化 ?符號的命名：符號名應(yīng)具有一定的實(shí)際含義，以便于對程序功能的理解。 ? 輸入和輸出 2022/2/9 60 結(jié)構(gòu)化程序設(shè)計(jì) ? 設(shè)計(jì)的主要原則： 自頂向下、逐步求精、模塊化、限制使用 goto語句。 逐步求精：對復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。 2022/2/9 61 結(jié)構(gòu)化程序設(shè)計(jì) ? 結(jié)構(gòu)化程序的基本結(jié)構(gòu) ? 順序結(jié)構(gòu)、選擇結(jié)構(gòu)（分支結(jié)構(gòu)）、重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)） ? 采用結(jié)構(gòu)化程序設(shè)計(jì)方法編寫程序，可使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。 ? 結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用 ? 使用程序設(shè)計(jì)語言的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。 ? 程序語句組成容易識(shí)別的塊，每塊只有一個(gè)入口和一個(gè)出口。 ? 語言種所沒有的控制結(jié)構(gòu)，應(yīng)采用前后一致的方法來模擬。 2022/2/9 62 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn) 與人類習(xí)慣的思維方式一致，穩(wěn)定性好，可重用性好，易于開發(fā)大型軟件產(chǎn)品，可維護(hù)性好。一般只能通過執(zhí)行對象的操作來改變其屬性。 2022/2/9 63 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 對象有如下一些基本特點(diǎn)： ? 標(biāo)識(shí)惟一性。 ? 分類性。 ? 多態(tài)性。 ? 封裝性。 ? 模塊獨(dú)立性好。 2022/2/9 64 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 類 是具有共同屬性、共同方法的對象的集合。 ? 對象 對象是其對應(yīng)類的一個(gè)實(shí)例。 ? 繼承 是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。 單繼承指一個(gè)類只允許有一個(gè)父類；多繼承指一個(gè)類允許有多個(gè)父 類。 2022/2/9 65 軟件工程基礎(chǔ) ? 軟件工程基本概念 ? 結(jié)構(gòu)化分析方法 ? 結(jié)構(gòu)化設(shè)計(jì)方法 ? 軟件測試方法和技術(shù) ? 程序調(diào)試 2022/2/9 66 軟件工程基本概念 ? 軟件：是 程序、數(shù)據(jù)及相關(guān)文檔 的完整集合。 ? 軟件工程學(xué)：用工程、科學(xué)和數(shù)學(xué)的原理與方法研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法的一門工程科學(xué)。 工具：支持軟件的開發(fā)、管理、文檔生成。 2022/2/9 67 軟件生命周期 ? 軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。確定待開發(fā)軟件系統(tǒng)的開發(fā)目標(biāo)和總的要求，給出它的功能、性能、可靠性及接口等方面的可能方案，制定完成開發(fā)任務(wù)的實(shí)施計(jì)劃。對待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義。 ? 軟件設(shè)計(jì)。可分為 概要設(shè)計(jì)和詳細(xì)設(shè)計(jì) 。 ? 軟件實(shí)現(xiàn)。 ? 軟件測試。 ? 運(yùn)行和維護(hù)。 2022/2/9 68 開發(fā)工具與開發(fā)環(huán)境 ? 軟件開發(fā)工具與軟件開發(fā)環(huán)境的使用提高了軟件的開發(fā)效率、維護(hù)效率和軟件質(zhì)量。 ? 軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。 ? 基于軟件工程的目標(biāo)，軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括： 軟件開發(fā)技術(shù)和軟件工程管理 。這些原則適用于所有的軟件項(xiàng)目。 2022/2/9 70 結(jié)構(gòu)化分析方法 ? 需求分析階段的工作有： ? 需求獲取 ? 需求分析 ? 編寫需求規(guī)格說明書 ? 需求評審 ? 常見的需求分析方法有： 結(jié)構(gòu)化分析方法、面向?qū)ο蟮姆治龇椒?。 ? 它著眼于 數(shù)據(jù)流 ，自頂向下，逐層分解，