全國計(jì)算機(jī)等級考試--二級公共基礎(chǔ)知識(ppt-100)-文庫吧資料
2025-08-11 02:45本頁面
【正文】 考慮全局目標(biāo)，后考慮局部目標(biāo)。良好的程序設(shè)計(jì)風(fēng)格概括起來包括以下及格方面： ? 源程序文檔化 ? 數(shù)據(jù)說明的方法 ? 語句的結(jié)構(gòu) ? 輸入和輸出 程序設(shè)計(jì)風(fēng)格 ? 源程序文檔化 ? 標(biāo)識符的命名 ? 程序的注釋 ? 序言性注釋 ? 功能性注釋 ? 程序的視覺組織 ? 數(shù)據(jù)的說明 ? 數(shù)據(jù)說明的次序應(yīng)該規(guī)范化 ? 說明語句中變量的安排有序化 ? 使用注釋說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)風(fēng)格 ? 語句結(jié)構(gòu) ? 在一行內(nèi)只寫一條語句 ? 程序編寫應(yīng)優(yōu)先考慮清晰性 ? 除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二 ? 首先要保證程序正確，然后才要求提高速度 ? 避免使用臨時(shí)變量而使程序的可讀性下降 ? 避免不必要的轉(zhuǎn)移 ? 盡可能使用庫函數(shù) ? 避免使用復(fù)雜的條件語句 ? 盡量減少使用 “ 否定 ” 條件的條件語句 ? 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化 ? 要模塊化，使模塊功能盡可能單一化 ? 利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性 ? 從數(shù)據(jù)出發(fā)構(gòu)造程序 ? 不要修補(bǔ)不好的程序，要重寫編寫 程序設(shè)計(jì)風(fēng)格 ? 輸入和輸出 ? 對所有輸入數(shù)據(jù)檢驗(yàn)合法性 ? 檢查輸入項(xiàng)的各種重要組合的合法性 ? 輸入格式要簡單，以使輸入的步驟和操作盡可能簡單 ? 輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式 ? 應(yīng)允許缺省值 ? 輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志 ? 在以交互式輸入 /輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息 ? 當(dāng)程序設(shè)計(jì)語言對輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。 ? 在程序設(shè)計(jì)中，通常采用 “ 自頂向下，逐步求精 ” 的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語言編寫的程序。 知識點(diǎn)歸納 ? 程序設(shè)計(jì)方法 ? 程序設(shè)計(jì)是一門技術(shù)，需要相應(yīng)的理論、方法和工具來支持。 2. 結(jié)構(gòu)化程序設(shè)計(jì)。 ? 一個(gè)包含 n個(gè)元素的列表需要進(jìn)行 n1次掃描完成排序。經(jīng)過一次選擇和交換，列表中已排序部分增加一個(gè)元素，未排序部分減少一個(gè)元素。 ? 增量序列一般取 ht=n/2k(k=1,2… [log2n]) 希爾排序 7 1 9 2 4 1 3 3 1 8 8 2 1 8 4 4 6 3 5 2 97 1 8 2 4 1 3 5 8 8 2 1 9 4 4 6 3 3 1 2 97 5 8 1 3 1 8 2 4 6 3 1 9 2 9 8 2 3 1 4 45 7 8 1 3 1 8 1 9 2 4 2 9 3 1 4 4 6 3 8 2h=6 h=1 h=3 完成 選擇類排序 ? 簡單選擇排序 ? 基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。 簡單插入排序示例 原始序列 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 希爾排序 ? 基本思想：將整個(gè)無序序列分割成若干個(gè)小的子序列分別進(jìn)行插入排序。每次掃描將未排序列表中的第一個(gè)元素取出并插入到已排序列表中的合適位置。 ? 上述兩步操作交替進(jìn)行，直到 i和 j指向同一個(gè)位置，再將T移動(dòng)到 P(i)的位置上，完成一次分割。設(shè)兩個(gè)指針 i， j分別指向表的起始和最后位置，反復(fù)操作以下兩步： ① 將 j逐漸減小，并逐次比較 P(j)和 T，直到發(fā)現(xiàn)一個(gè) P(j)T為止，并將 P(j)移到 P(i)的位置上。按照上述原則對子表繼續(xù)進(jìn)行分割，直到子表為空，則整個(gè)線性表有序。 ? 對剩下的線性表重復(fù)上述過程，直到剩余線性表為空為止，此時(shí)線性表變?yōu)橛行颉? ? 然后，從后向前掃描剩下的線性表，同樣在掃描的過程中依次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則交換位置。 交換類排序 ? 冒泡排序 ? 基本思想：從表頭開始掃描線性表，在掃描的過程中依次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則交換它們的位置。 ? 排序可以在各種不同的存儲結(jié)構(gòu)上實(shí)現(xiàn)，本章所介紹的算法以順序存儲的線性表為排序?qū)ο?，在程序設(shè)計(jì)語言中就是一維數(shù)組。 ? 查找過程中，給定值首先和處于待查區(qū)間 中間位置 的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到 前半個(gè)區(qū)間 或 后半個(gè)區(qū)間 之后繼續(xù)進(jìn)行查找。 查找 ? 二分查找 (折半查找 ) ? 二分查找法只適用于順序存儲的有序表。 ? 如果線性表為無序表，即表中元素的排列是無序的，則不管線性表采用順序存儲還是鏈?zhǔn)酱鎯?，都必須使用順序查找? 二叉樹的遍歷 先序遍歷： ABDEGHCFIJ 中序遍歷： DBGEHACIJF 后序遍歷： DGHEBJIFCA 查找 ? 查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。 若二叉樹為空，則空操作； 否則 (1) 中序遍歷左子樹； (2) 訪問根結(jié)點(diǎn)； (3) 中序遍歷右子樹。從二叉樹的結(jié)構(gòu)定義得知，二叉樹是由 根結(jié)點(diǎn) 、 左子樹 和 右子樹 三部分構(gòu)成，則遍歷二叉樹的操作可分解為 訪問根結(jié)點(diǎn) 、 遍歷左子樹和 遍歷右子樹 三個(gè)子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣 遞歸 進(jìn)行。 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域，即數(shù)據(jù)域，左指針域和右指針域，兩個(gè)指針域分別存儲左右子樹根節(jié)點(diǎn)的存儲位置，即指針。 (2) 如果 2in，則編號為 i 的結(jié)點(diǎn)無左孩子（編號為 i 的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn) lChild(i) 的編號是 2i 。 ? 從以上定義可知，滿二叉樹也是完全二叉樹，反之則不然。 ? 完全二叉樹 除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 ? 二叉樹是另一種樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有左右之分，其順序不能任意顛倒。 ? 深度：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。同一個(gè)雙親結(jié)點(diǎn)的孩子互稱為兄弟。 ? 葉節(jié)點(diǎn) (終端結(jié)點(diǎn) )：度為 0的結(jié)點(diǎn)。 ? 集合為空的樹簡稱為空樹；樹中的元素稱為結(jié)點(diǎn)。 ? 樹是 (n≥0) 個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中： (1)有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其指針域指向第一個(gè)元素結(jié)點(diǎn)，頭指針則指向頭結(jié)點(diǎn)。 ? 循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)。最后一個(gè)數(shù)據(jù)元素沒有直接后繼，其指針域?yàn)榭铡? 單鏈表 ? 通常以單鏈表中第一個(gè)數(shù)據(jù)元素的存儲地址作為作為單鏈表的地址，稱為頭指針。 ? 指針域中存儲的信息稱為指針或鏈， N個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 ? 在循環(huán)隊(duì)列為空或?yàn)闈M時(shí)，均有 front=rear，因此需要設(shè)置標(biāo)志 s進(jìn)行區(qū)分，定義 s=0表示隊(duì)列為空， s=1表示隊(duì)列非空。 ? 循環(huán)隊(duì)列初始狀態(tài)為空，即 front=rear=m。 ? 向隊(duì)尾插入一個(gè)元素的操作稱為入隊(duì)，從隊(duì)頭刪除一個(gè)元素的操作稱為退隊(duì)。通常定義頭指針front指向隊(duì)頭元素的前一個(gè)位置，定義尾指針 rear指向隊(duì)尾元素的位置。 ? 取棧頂元素：將棧頂元素的值賦給一個(gè)指定的變量，不刪除棧頂元素，棧頂指針不變。 ? 棧的操作 ? 入棧：在棧頂位置插入一個(gè)新元素，棧頂指針 top加1。 ? ?a2a1an棧 頂 t o p棧 底 b o t t o m入 棧 出 棧棧的順序存儲及運(yùn)算 ? 用一維數(shù)組 S(1:m)作為棧的順序存儲空間， m為棧的最大容量。因此，棧是一種后進(jìn)先出 的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 ? 一般情況，要?jiǎng)h除第 i(1≤i≤n) 個(gè)元素，要從第i+1個(gè)元素開始，直到第 n個(gè)元素，共 ni個(gè)元素依次向前移動(dòng)一個(gè)位置。 ? 一般情況下，要在第 i(1≤i≤n) 個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)元素開始
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1