软件基础课件

操作系統什麼是操作系統？操作系統的特性操作系統的功能操作系統的種類操作系統的結構操作系統的資源管理操作系統的發展什麼是操作系統？操作系統OS（OperatingSystem）連接用戶與電腦硬體的介面，管理電腦系統資源的集合。是配置在電腦硬體上的第一層軟體，是對硬體系統的第一次擴充。實質：電腦操作系統是一種軟體，屬於系統軟體，但又不同於其他系統軟體。作用：相當於電腦系統的“管家”，要管理的“家務”就是管理和控制電腦的軟硬體資源。使命：兩大使命是服務用戶和管理資源，使用戶方便地使用電腦，同時還要將電腦資源充分利用，特別是像CPU、記憶體、顯示器、印表機等“共用資源”。操作系統是加到電腦硬體上的第一層軟體，他是對電腦硬體的首次擴充。硬體的發展

操作系統更新換代兩種不同級別的用戶介面：最終用戶介面和程式員介面電腦硬體操作系統各種工具軟體應用軟體最終用戶程式員操作系統設計人員命令行式用戶介面、圖形用戶介面也稱作系統調用介面如：WindowsAPI（應用編程介面）操作系統的特性程式的併發執行（Concurrence）併發：指兩個或兩個以上的事件在同一時間間隔中發生。即指宏觀上在一段時間內多個進程在“同時”運行資源的共用（Sharing）共用：指電腦系統中的硬體資源和軟體資源不僅僅為某一程式或者某一用戶所獨享，多個擁有授權的程式或用戶都可以使用。為了提高電腦的利用率互斥訪問：系統中的許多資源（印表機）雖然多個程式都能使用，但在某一時間卻只能允許一個程式使用。這種在一段時間內只允許一個程式使用的資源稱作臨界資源同時訪問：允許多個進程在一段時間內同時訪問。虛擬性（Virtual）定義：把物理實體映射為一個或者多個邏輯實體。主要目的：就是向用戶提供一個方便、高效、易於使用的操作環境。非同步性（Asynchronism）也可稱作隨機性、不確定性（運算結果的不確定）進程的執行並非“一氣呵成”，而是以“走走停停”的方式運行。每道程式總共需要多少時間才能完成，都是不可預知的。我們說進程是以非同步方式運行的。實際存在的用戶的看法和感覺處理機管理（進程管理）：處理機管理的主要任務，是對處理機進行分配，並對其運行進行有效地控制和管理。在多任務環境中，處理機的分配和運行都是以進程為基本單位的。

進程管理的主要任務：為運行程式創建進程、進程調度、進程間通訊和程式運行完成後撤銷進程。

進程：又稱任務，是指在系統中能獨立運行並作為資源分配的基本單位，它是一個活動實體。操作系統的功能記憶體管理：主要是為每個進程分配記憶體、當進程被撤銷時回收分配出去的記憶體。映射功能：把應用程式的邏輯地址正確的映射到物理地址。邏輯地址：應用程式所限定的地址範圍叫做該程式的地址空間，即邏輯地址。物理地址：指在內存空間上。虛擬功能：提供比實際大得多的“記憶體”供應用程式使用設備管理：對設備進行分配、調度以提高整個電腦系統的運行效率，還遮罩各種設備的物理特性。完成用戶提出的I／O請求，為用戶分配I／O設備；提高CPU和I／O設備的利用率；提高I／O速度；檔管理：電腦所有資訊都以檔的形式保存在存儲介質上。功能：數據存儲空間的分配、回收，檔的讀寫、查找機制和安全機制。作業管理：作業就是用戶提交的任務。包括用戶應用程式所需要的數據以及控制應用程式執行的指令兩部分。作業調度功能。

作業管理與進程管理：都需要進行調度和資源分配；作業調度是由用戶來完成的，也叫高級調度；進程管理是操作系統的任務，對用戶都是透明的。OS的形成迄今已有約50年的時間。50年代中期出現第一個簡單的批處理操作系統。60年代中期產生了多道程序批處理系統，不久又出現了基於多道程序的分時系統。80年代是電腦局域網發展的年代，也是OS（即時系統）和LANOS（網路操作系統）形成和發展的年代。操作系統的種類單道批處理系統它只能是OS的前身而並非是現在人們所理解的OS。自動性：順利的情況下，在磁帶上的一批作業能自動逐個作業一次運行，而無需人工干預。順序性：磁帶上各道作業是順序進入記憶體，先調入記憶體的作業先完成。單道性：記憶體中僅有一道程式運行，即監督程式每次從磁帶上只調入一道程式進入記憶體運行。僅當程式完成或發生異常情況時，才調入其後繼程式進入記憶體運行。把記憶體分為若干部分，把屬於同一批次的若干個作業調入記憶體，存放在記憶體高的不同部分。資源利用率高：CPU的利用率可接近100％。系統吞吐量大：系統吞吐量是指系統在單位時間內所完成的總工作量。缺點：多道批處理系統無交互能力：整個處理過程中，用戶不能進行任何干預，發現錯誤，不能中斷進行處理。周轉時間長：作業的周轉時間是指從作業進入系統開始，直至其完成並退出系統為止所經歷的時間。由於作業要排隊依次進行處理，因而作業的周轉時間較長，通常需幾個小時、甚至幾天。分時與批處理的區別：批處理：一個作業可長時間佔用CPU直至執行完；分時系統：一個作業只能在一個時間片（一般取100ms）時間內使用CPU，時間一到，系統將剝奪其CPU使用權，把CPU分配個其他作業使用。多路性：多個用戶終端通過多路卡連接到一臺主機。獨佔性：通過一臺終端使用系統，彼此獨立操作互不干擾及時性：終端用戶的請求在較短時間間隔內可獲得回應。交互性：用戶可通過終端與系統進行廣泛的人機對話。其廣泛性表現在：用戶可請求系統提供多方面的服務，如檔編輯、數據處理、資源共用等分時操作系統對於特定的輸入，系統能夠在極短的時間內作出回應並完成對該輸入請求的處理。是一種特殊的分時系統。具有同樣的特性。區別：即時操作系統比較系統用處交互權限回應時間即時系統專用的比較差只允許訪問數量有限的專用程式一般是毫秒級，甚至微妙級分時系統通用性強很強允許運行或修改自己的應用程式2～3s之間根據應用領域不同，把即時操作系統分為兩類：即時控制系統：就是以電腦為中心的控制系統。特點：採集現場數據並進行即時處理，根據處理結果自動控制相應的執行機構以實現預期目標。如：應用與武器系統中的火炮控制系統、導彈控制系統、交通領域中的飛機自動駕駛系統等。即時資訊處理系統：電腦即時接收從遠程終端發來的服務請求，根據遠程請求對資訊進行檢索和處理，並在極短的時間內對用戶的請求作出正確的答復。如機票訂購系統、聯機情報檢索系統。一臺電腦通過一個網路介面控制器（網卡）連接到網路上。與單機上的操作系統不同的是，網路操作系統可以對網路上的共用資源進行管理和使用。如：WindowsNTServer、UNIX網路通信功能：網路操作系統必須內在的支持某種網路協議，如TCP／IP協議網路資源的管理和使用：電腦網絡的主要目的就是要實現資源的共用，對共用資源進行統一、有效地管理是必要的。還應提供一些網路服務，如網路列印服務。網路操作系統整體式：其實就是“無結構”。整個操作系統就是許多個過程的集合，其中每個過程都可調用其他過程,每個過程都有一個定義良好的過程介面，過程之間的相互調用不受任何約束。該組織形式的系統可維護性、可讀性較差。Dos、UNIX層次式：就是把模組按功能劃分為若干層，然後把他們一層一層的疊加起來，形成一個整體。處於上一層的模組可以調用下一層的過程。客戶機／伺服器式儘量把一些非基本的操作移到內核外，把更多的代碼移到高層，而操作系統的核心只保留一些最基本的功能，把內核變得小巧精悍。WindowsNT的內核結合以上兩種操作系統的結構資源管理是操作系統最主要的任務。進程管理（處理器管理）＊＊存儲管理（主要針對記憶體）＊＊設備管理檔管理操作系統的資源管理)進程管理進程特徵：四個特徵（比較進程和程式、進程和線程的區別）進程狀態：主要有三個狀態進程控制：操作系統是通過什麼來管理進程的？進程同步：怎樣達到進程同步？進程通信：三種通信進程調度：三種調度演算法進程：程式的一次執行，又稱任務，是指在系統中能獨立運行並作為資源分配的基本單位。一位有一手好廚藝的電腦科學家正為他女兒烘制生日蛋糕。他有做蛋糕的食譜，廚房有所需的原料：麵粉、雞蛋、糖、香草汁等。該比喻中，食譜就是程式(即用適當形式描述的演算法)，電腦科學家就是處理機，而各種原料就是輸入數據。進程就是廚師閱讀食譜、取來原料、烘制蛋糕一系列動作的總和。現假設科學家的兒子哭著跑進來，說他被一只蜜蜂蟄了。科學家記錄下他照著食譜做到哪兒了(保存進程的當前狀態)，然後拿出一本急救手冊，按其中的指示用藥品處理蟄傷。此時處理機從一個進程(做蛋糕)切換到另一個高優先順序的進程(實施醫療救治)，每個(進程)擁有各自的程式(食譜和急救手冊)。當蜜蜂蟄傷處理完後，電腦科學家又回來做蛋糕．從他離開時的那一步繼續做下去。進程的特徵（進程和程式的區別）科學家制蛋糕科學家食譜原料處理機程序輸入數據閱讀添加製作蛋糕處理兒子蟄傷科學家急救手冊藥品處理機程序輸入數據參照使用處理蟄傷保存當前狀態繼續製作進程切換進程就是廚師閱讀食譜、取來原料、烘制蛋糕一系列動作的總和進程就是廚師閱讀食譜、取來原料、烘制蛋糕一系列動作的總和1、進程是動態的，而程式是靜態的。2、程式可寫在紙上、保存在磁片中進行長期保存，它的生命期是長久的；而進程是程式的執行，因此生命期是短暫的，在執行初期被創建，在執行完成後被撤銷。3、對程式來說，除了存儲介質之外不需要任何資源；而對於進程來說，被執行才是其存在的意義，因此進程需要處理機資源，需要記憶體資源，也許還需要其他輸入輸出資源。進程和程式的區別進程的特性：動態性：進程是程式的執行過程。運行程式，系統創建進程，分配資源調度執行，程式結束，回收資源撤銷原創建的進程。併發性：併發執行提高了電腦系統資源的利用率。獨立性：進程是能獨立運行的基本單位，也是系統資源分配和運行調度的基本單位。非同步性：線程：輕量進程。是進程內的一個可調度的執行單元。獨立的最小調度單位，但不是資源分配單位。同一進程可擁有多個線程，他們被獨立調度但共用所屬進程的資源。區別：1、線程是最小調度單位，線程比進程切換快2、線程提高系統併發性，使進程內部也可併發執行3、進程擁有資源而線程不擁有資源4、線程的系統開銷小於進程進程的狀態就緒狀態：進程已獲得除處理機外的所有資源，已做好運行準備。執行狀態：進程已獲得CPU使用權，正在執行。阻塞狀態：正運行的進程，由於某個事件的發生而放棄處理機。執行就緒阻塞調度時間片完等原因放棄處理器等待資源或I/O獲得資源或I/O完進程的狀態轉換並非都是可逆的；進程間的狀態多是“被動的”。只有“運行阻塞”的轉換是進程的主動行為，其他都是被動的。進程控制一個描述進程的數據結構應記錄三方面資訊：進程狀態方面、記憶體方面、檔管理方面。用進程控制塊P

C

B（ProcessControlBlock）描述和記錄進程必需的資訊。操作系統是通過管理PCB來管理進程的創建、撤銷、阻塞、喚醒和掛起及啟動

開始申請空PCB有空PCB?分配資源初始化控制資訊結束NY開始檢索PCB狀態結束子進程釋放資源結束執行？釋放PCB中止執行YNCreat()Destroy()進程的同步進程同步:操作系統必須提供一種機制對共用臨界資源的進程進行協調,以保證這些進程能夠“有序”執行。採用信號燈亮機制實現進程同步（UNIX）；提供了線程機制實現進程同步（WindowsNT）。進程同步由操作系統自己完成，對用戶是透明的。典型的同步問題：生產者－消費者問題

所有生產者和消費者進程都以非同步方式運行，但它們之間必須保持同步：不允許消費者進程到空緩衝區取消息，也不允許生產者進程向已有消息且尚未被取走的緩衝區投消息。生產消息消息1消費消息消息2消息n……生產者進程消費者進程緩衝池1～n進程同步例2：哲學家進餐問題有五個哲學家,他們的生活方式是交替進行思考和進餐.哲學家們共用一張圓桌,分別坐在周圍的五張椅子上.在圓桌上有五個碗和五支筷子,平時哲學家進行思考,饑餓時便試圖取用其左、右最靠近他的筷子,只有在他拿到兩只筷子時才能進餐.進餐畢,放下筷子又繼續思考.措施：對這種不能共用的資源我們要求一次只有一個進程能使用資源，其他進程只有在該進程釋放資源後才能使用，即進程要互斥的使用資源。只能同時由一個進程使用的資源叫臨界資源使用臨界資源的進程部分叫臨界區使用臨界資源的準則：任何兩個進程不能同時處於臨界區。不應對CPU的速度和數目作任何假設。臨界區外的進程不得阻塞其他進程。不得使進程在臨界區外無休止地等待。進程的通信基於共用數據結構或共用記憶體進行通信：利用某些共用數據結構或者共用存儲區來實現通信。利用消息進行通信：操作系統自己維護一消息佇列，所有消息放到消息佇列中，系統定期檢查消息佇列並把其中的消息傳送給相應進程處理。分直接通信和間接通信兩種方式。利用共用檔進行通信：即管道通信。系統使用一個已打開的共用檔來連接兩個相互通信的進程，該共用檔被稱作“管道”。須注意幾個問題：互斥、同步、雙方是否存在。發送進程共用檔接收進程進程調度進程調度：低級調度.功能：按一定原則把CPU動態分配給某一就緒進程。非搶佔方式和搶佔方式。進程調度必須完成以下任務：記錄進程的狀態、分配處理機、回收處理機進程調度演算法：根據一定的原則從就緒佇列中選擇一個就緒進程，把CPU分配給它。應公平、高效優先順序調度策略：把CPU分給就緒進程佇列中優先順序最高的進程時間片輪轉法：按先進現出原則把CPU分給就緒佇列首位的進程多重時間片迴圈調度：設有多個時間片不同的就緒佇列，各隊列按時間片從小到大順序排列。如何更好的管理和合理的使用電腦記憶體？管理對象：內記憶體、外存儲器（輔存）管理目標：為程式設計人員提供方便、安全和充分大的存儲空間。)存儲管理輔存主存Cache容量速度高高解決的問題：存儲空間的分配回收、地址映射、記憶體保護專業術語：邏輯空間：程式設計人員的編程空間。邏輯地址的總體稱為地址空間，可一維，也可二維。

物理空間：記憶體空間,由物理存儲單元組成,大小取決於實際的容量。

重定位：1、程式裝入記憶體運行時，會將其邏輯地址映射成相應物理地址，以便在獲得的物理空間定位程式；

2、程式執行中，若系統移動其在內存的位置，需將程式邏輯地址重新映射成新的物理地址。地址映射：靜態重定位（事先知道程式將放記憶體的什麼地方）和動態重定位（地址映射在程式執行時進行）

虛擬記憶體：一種由內、外存連接成的記憶體.當前使用的部分保留在內存，其他暫時不用的保留在外存存儲管理方式：分區式：把記憶體空間靜態的或動態的分割成若干大小不等的區域，每個作業分配一片連續的存儲空間，程式一次整體裝入。固定式、可變式、可重定位式。缺點：會產生不可利用的記憶體零頭(碎片)。分頁式：用戶程式的地址空間被劃分成若干個固定大小的區域，稱為“頁”，典型大小為1KB，並用0、1、2標號，叫虛頁面；把記憶體空間也按同樣大小分為若干個相等的頁面，標號，叫實頁面。碎片大小不超過一頁分段式：一個用戶程式通常由一個主程序、若干個子程式和數據區組成，每一個邏輯資訊組稱為“段”。一個作業最多有64K個段，每個段最大長度為64KB段頁式：在分段的基礎上，對各段進行分頁。二維的“分頁”管理方法與“分段”管理方法比較需要考慮的因素分頁式記憶體管理分段式記憶體管理程式員需知道此技術嗎不需要需要線性地址空間的維數1維2維邏輯地址空間可以比實際的物理空間大嗎?可以可以數據和代碼可以被分開並被分別保護嗎?不行不行有助於用戶間過程共用不是為什麼發明這種技術?為了能向用戶提供很大的邏輯地址空間而又不需購買很多的物理記憶體為了允許把程式和數據劃分為獨立的邏輯地址空間以實現共用和保護設備管理的體系結構：實現設備無關性,採用分層思想，逐層抽象。一般分為兩層：I／O控制系統，設備驅動程式。邏輯設備與物理設備緩衝技術：緩衝器實際就是由幾個存儲單元構成的記憶體。緩衝是由輸入輸出控制系統管理的。緩衝技術可明顯改善系統內資訊流動的狀況，提高CPU與輸入輸出設備之間的並行性，顯著提高系統性能。設備的分配與調度：可在為程式創建進程時分配；也可在進程運行時提出自願申請時分配。)設備管理檔的命名：不能同名、有擴展名檔的結構：位元組流式檔、記錄式檔檔的存取：順序存取到隨機存取檔的屬性檔的操作：create、delete、open、close、read、write、seek、set／getattribute等目錄：檔用來記錄資訊，目錄用來記錄檔檔的存取控制：檔的存儲：連續分配、鏈表方式、索引鏈表、I-結點)檔管理時空觀電腦發展特點：速度加快、容量增大電腦工作：在特定的時刻、特定的地點建立“0”和“1”靜動觀：優勝劣態，軟硬體新產品不斷更新陰陽觀（對立統一）：電腦人才和行業的劇烈競爭用戶需求和產品的矛盾操作系統的發展DOS系統Windows95/98UNIX系統Linux系統NetWare系統WindowsNT系統第九章幾種常見的操作系統Dos：DiskOperatingSystem。在磁片操作系統基礎上開發的單任務單用戶微機操作系統。主要特徵：簡單、實用、高效、對硬體要求極低缺點：只能運行於微機上、不支持多任務操作（不支持併發）、無多用戶處理能力、不支持多媒體、介面不友好、沒有提供安全子系統（系統極易受到攻擊和破壞）等Windows系統彌補了其不足：友好的圖形用戶介面、支持多任務、資訊可共用、支持DOS、提供API及其規範DOS系統Windows95：單用戶多任務32位操作系統。主要特徵：用戶介面直觀形象、安裝簡單方便、功能強大、相容性良好、網路支持良好Windows98與95的區別：應用程式的啟動速度提高了36％；訪問因特網、觀看圖片和關機的速度比Windows95提高2～5倍；硬碟存儲效率比Windows95提高了28％。Windows95／981969～1970年，美國電報電話公司（AT&T）Bell實驗室在PDP-7上實現了UNIX系統。最初的系統是用組合語言寫的，後又用B語言、C語言重寫。特性：多用戶多任務環境、C語言編寫（易讀、易修改、易移植）、採用樹形檔系統（有良好的安全性、保密性和可維護性）、提供多種通信機制、實現虛存管理（提高了記憶體的使用效率）、開放性、功能強大、實現高效、豐富的網路功能UNIX系統Linux由MINIX發展而來，秉承了UNIX系統的優良傳統，公開源代碼並歡迎全世界的電腦愛好者進行研究和改進。特徵：技術優秀、內核較小、性能優越、穩定可靠、對硬體要求不高、免費獲取等與WindowsNT4.0的區別：對遠程連接的支持、實際的多用戶、不同分區的啟動、伺服器端JAVA支持等等。Linux系統Novell公司為PC機設計的網路伺服器操作系統，可完成局域網伺服器所能完成的各種任務。優勢：多任務操作系統，可同時為多個連接提供服務；極好的安全機制：用戶和組的安全認證、檔和文件卷級的安全約束機制、目錄管理等。與WindowsNT的域目錄服務的比較：P270NetWare系統WindowsNT的產生正是由於Windows95的簡陋：提供服務太少、網路支持不夠、系統安全性差、不夠穩定、不支持多處理器和分佈式計算等。WindowsNT的特點：良好的可靠性、穩定性、安全性、可擴展性、可移植性、高度相容性、可管理性。WindowsNT類型：工作站（NTWorkstation）和伺服器（NTServer）。伺服器擁有工作站的所有功能。結構：對象式操作系統。採用層次式與客戶機／伺服器模式相結合的系統結構。安全性：網路資源的安全性、域管理模型（用戶管理）、NT（NTFS）檔系統的安全性WindowsNT系統DOS以簡單、可靠贏得用戶青睞,Windows3.x是其基礎上的擴展,後被Windows95/98代替.UNIX近30年的錘煉,有強大的功能,Linux秉承其優秀特性,在未來世界將占重要地位,NetWare以獨特結構、強大的目錄管理服務成為PC最主要的網路操作系統,WindowsNT以其靈活和穩定的性能成為目前最為重要的操作系統之一小結DOSWindows3.xWindows95/98UNIXLinuxNetWareWindowsNT操作系統作業：P256頁6、7、8

操作系統總結第二章程式設計語言編制程式的工作就是程式設計程式的表達手段就是程式設計語言程式設計語言的特點：

嚴格小巧沒有二義性2.1高級程式設計語言概述2、組合語言：面向機器，需直接安排存儲。規定寄存器、運算器的動作次序，須知道電腦對數據約定的表示；不同的電腦在指令長度、尋址方式、寄存器數目、指令表示都不一樣。組合語言程式不可移植，閱讀困難。

1、機器語言

數據區：存放數據

指令區：存放指令2.2高級程式語言高級程式語言翻譯成機器語言程式編譯編譯器解釋解釋器1、編譯過程（編譯型語言：如C語言）逐行掃描根源程式詞法分析語法分析語義分析中間代碼生成代碼優化目標代碼生成目標代碼符號表管理程序出錯處理程序2、解釋過程（解釋型語言：Java語言）逐句讀入源代碼詞法分析語法分析語義分析中間代碼生成建立內部符號表做類型檢查壓入執行堆棧立即解釋執行3、編譯和解釋的大致區別

類型內容編譯程式解釋程式執行效率很高較低佔用空間不大較小優化性能較好難於優化執行方式生成目標代碼入棧解釋執行2.3高級程式設計語言基本特徵1、變數、運算式、賦值

變數：在整個程式運行的過程中，其值可以發生改變的量。運算式：是常量、變數、函數調用或者由它們和運算符組成的序列。

區分字面量和常量的區別。常量在整個程式執行過程中值不改動。用常量賦初值的優勢：程式修改比較方便。賦值和函數調用是程式語言改變變數的值的基本手段。2、程式的控制結構條件分支語句

if(E1)thenS1elseif(E2)thenS2elseS3endifendif迭代語句

除了判斷，程式語言還有進行重複計算的迭代結構。

SUM=0I=1While(I<=10000)doSUM=SUM+1I=I+1enddowrite(…)SUM重複10000次While(e)doSUnddo

運算式E為‘真’執行S,直至E為‘假’（a）當迴圈迭代結構的一般形式doSUntile(E)

先執行S再查看E，E為‘真’不重複（b）直到迴圈For(i=E0;E1;E2)doSenddoI的初值E0，判斷i<=E2，執行S後I增量E1，判斷若i>E2，出for-do（c）計數迴圈結構化程式控制（三種基本控制結構）

順序條件分支迭代其他控制結構:三種基本結構的變體如：Case語句的使用,Case是if的簡化s1s2…snESESESTSFTF3、數據類型常用的基本類型

int、float、double、boolean、char、string數組

第一個元素，下標從0開始；數組的特徵：所有元素均為同一類型；二維數組可看作是數組的數組；

純量變量：變數代表單個數據值

結構型數據變數：變數代表多個（數組）或多種（記錄）值記錄：相同或不同類型的數據組成的結構叫“記錄”元組：記錄類型的變數的一組值（或一行值）。

C語言中，記錄被稱作結構指針類型

a.取地址操作：獲取一個變數的記憶體地址。“&”b.取值操作：取的是指針所指的變數的值，即指針指向的記憶體單元中保存的數據。“*”

intI,*p1;/*p1是一個整數指針*/char*p2;/*p2是一個字元指針*/constintI,*p=&I;/*定義一常量指針，指向變數I*/structstudent*pStudent;/*定義一指向結構的指針*/

(利用指向符號“->”直接使用結構指針來訪問結構）

pStudent->name=“李四”4、過程一般把沒有返回值的函數稱作“過程”

函數過程是參數化（更抽象）的程式過程的定義：從過程關鍵字開始到過程結束之間的一段封閉的程式就是過程定義，它由型構（signature）（型構也叫介面：Interface）和過程體（body）組成過程中聲明的變數是局部變數，作用域（scope）僅限於本過程；過程調用：是把過程體的代碼調回到主程序的環境下執行，形參實參匹配。5、過程的數據傳遞無參過程

過程的型構中無形參表定義，調用時也不需實參。有參過程（傳遞變元）

變元：形參表中的變數傳值和引用（主程序向過程傳遞數據）6、變數的生命期和Static變數變數持續作用的時間和範圍主程序變數壽命>過程變數壽命Static：局部靜態變數和全局靜態變數

Staticsasinteger7、輸入和輸出2.4面向對象語言類的引入：把不同的汽車部件和汽車能做的各種事情捆綁在一個集合中，用於描述汽車的共同屬性。對象的引入：能用於指定一個特定的汽車。應用類：定義模型汽車應用對象：在類的基礎上制定屬於某一型號汽車的某一輛特定的汽車。

類是對對象的抽象和描述，對象是類的實例類封裝了屬性和方法對象是封裝了屬性和方法的實體一、類與對象二、面向對象特點面向對象程式設計的本質：是把數據和處理數據的過程抽象成一個具有特定身份和某些屬性的自包含實體——對象。數據叫做對象的屬性（Attribute）操作則改稱為方法（Method），即改變屬性的方法。

突出特點：封裝性、繼承性、多態性封裝：是一種數據隱藏技術，它通過把一組數據和與數據有關的操作集合放在一起，形成對象來實現。繼承：每個類都可以派生許多子類，子類繼承父類的屬性和方法。多態：同一名字執行的內容不同。由於繼承、屬性和方法可能重名，而產生了多態性。復習及習題：復習本章內容P44習題第六章VB環境下的應用程式開發作業中出現的問題上次作業中的問題打開、保存中的問題如何生成.exe檔VB的多媒體程式設計Timer控件的使用蝶戀花程式如何播放視頻檔總結我們所學習的VB程式設計總結所學的VB程式設計VB概述VB：VisualBasic:基於Basic的可視化的程式設計語言。1991年Microsoft公司推出的Windows應用程式開發工具。VB的三個版本：學習版、專業版、企業版VB6.0的軟硬體要求：硬體要求：一般在486以上的處理器、16MB以上記憶體、100MB以上的硬碟等軟體要求：Windows95／98或WindowsNT3.51以上的版本VB程式設計的特點：可視化的介面設計

VB可直接進行可視化的設計用戶介面，開發人員不必為介面設計編寫大量程式代碼。基於對象的程式設計思想

VB中應用面向對象的程式設計方法（OOP），把程式和數據封裝起來是為一個對象，每個對象都是可視的。程式員只需直接在螢幕上“畫”出所需對象，設計的效率提高許多。事件驅動的編程機制程式員只要編寫回應用戶動作的代碼，各個動作之間不一定有聯繫。應用程式代碼較短，易編寫易維護。方便易用結構化的程式結構、更接近於人類的語言和邏輯思維方式、語句簡單易懂。生成.exe的可執行檔可脫離VB環境，直接在Windows環境下運行。基於構件的程式開發可通過構件的重用和共用，迅速建立起應用系統。對象的鏈接與嵌入（OLE）

VB的核心技術就是其對OLE的支持，利用OLE，VB能夠開發集聲音、圖像、動畫、字處理、Web等對象於一體的應用程式資料庫訪問功能

VB利用數據控件或ODBC（開放資料庫連接）能夠訪問很多資料庫系統：Access、FoxPro、dBASE、FoxBase等，還可使用和操縱外部資料庫功能強大的輔助開發工具

VB中還有報表生成器，可用來制做各種報表。消息和事件驅動（P160）消息處理

Windows應用程式設計的核心就是傳送消息、讀入消息、處理消息。程式有消息要處理，就佔用CPU以處理消息，；如不再有消息需處理，系統就詢問其他正在運行的程式是否有消息要處理，並把控制權交給要處理消息的應用程式。事件驅動該種消息機制就是所謂的事件驅動。創建VB應用程式的步驟創建用戶介面設置介面對象的屬性編寫事件代碼保存專案測試和調試應用程式創建可執行代碼創建安裝應用程式VB程式設計最後要交的大作業涵蓋我們所介紹的幾種基本控件；至少含有以下內容：菜單的設計、簡易計算器、單選複選設計、timer控制、播放多媒體檔等；要求：程式完全可調試通、介面美觀、含有一個工程、多個窗體、生成可執行檔一人一份作業（不可抄襲）時間：第十三周（11月17日）上課時交。新疆石油學院電腦系左俊一多媒體的基本概念二多媒體技術的應用三多媒體電腦系統四多媒體技術與設備五多媒體應用開發六多媒體技術的發展方向七VB的多媒體程式設計目錄一、多媒體的基本概念“多媒體”一詞譯自英文“Multimedia”

即“Multiple”（複合的）和

”Media”（介質）的合成其核心詞是媒體何謂多媒體呢？媒質：存儲資訊的實體，如磁片、光碟、磁帶、半導體記憶體等媒介：傳遞資訊的載體，如數字、文字、聲音、圖形和圖像等。媒體（medium）在電腦領域有兩種含義：即媒質和媒介。媒體:人們表達資訊、傳播資訊和存儲資訊的手段和方式如：報紙、雜誌、電視、廣播、光碟、電腦網絡基本概念1音頻動畫視頻文本圖形圖像animationvideoaudioStillimagegraphicstext多媒體:通過電腦技術綜合處理多種媒體資訊，使文字、圖形、圖像、動畫、音頻、視頻等資訊建立邏輯連接，集成一種新的具有交互性的數位化資訊表示媒體。基本概念2多媒體電腦技術的三個主要特性資訊載體的數位化交互性集成性多媒體的特性：集成性數位化交互性時間相關性數據量大

集成性：以電腦為中心綜合處理多種資訊媒體

數位化：通過電腦來進行處理、存儲和網路傳輸

交互性：用戶可以與電腦的多種資訊媒體進行交互操作,從而為用戶提供了更加有效地控制和使用資訊的手段。基本概念3二、多媒體技術的應用

就目前而言，多媒體技術已在商業、教育、培訓、電視會議、聲像演示等方面得到了充分應用。在教育與培訓方面的應用在通信方面的應用在其他方面的應用

多媒體技術使教材不僅有文字、靜態圖像,還具有動態圖像和語音等。使教育的表現形式多樣化，可以進行互動式遠程教學。 利用多媒體電腦的文本、圖形、視頻、音頻和其互動式的特點,可以編制出電腦輔助教學

CAI(ComputerAssistedInstruction)軟體，即課件。在教育與培訓方面的應用

多媒體技術在通信方面的應用主要有： 可視電話 視頻會議 資訊點播（InformationDemand） 電腦協同工作CSCW

（ComputerSupported CooperativeWork）在通信方面的應用

多媒體技術給出版業帶來了巨大的影響，其中近年來出現的電子圖書和電子報刊就是應用多媒體技術的產物。利用多媒體技術可為各類諮詢提供服務，如旅遊、郵電、交通、商業、金融、賓館等。多媒體技術還將改變未來的家庭生活，多媒體技術在家庭中的應用將使人們在家中上班成為現實。在其他方面的應用三、多媒體電腦系統多媒體系統：就是可以互動式處理多媒體資訊的電腦系統一個完整的多媒體系統包括：多媒體硬體：普通硬體＋音、視、圖處理等硬體多媒體I／O控制介面：各驅動程式多媒體操作系統：提供多個媒體之間的同步多媒體創作系統：用來開發多媒體應用軟體多媒體應用系統：面向最終用戶的應用程式多媒體電腦MPC:集成性、交互性、數位化四、多媒體技術與設備音頻技術及其設備視頻技術及其設備動畫存儲光碟音頻技術及其設備數字音頻（Audio）可分為波形聲音、語音和音樂WAV或VOC檔MID或CMF檔聲卡就是根據音頻數位化技術而設計的，其主要功能是實現:模擬音頻數字音頻轉換以固定的時間間隔對波形進行採樣音頻採樣的三個重要參數:採樣頻率、採樣數據位數、記錄的聲道數採樣頻率：指每秒鐘的採樣次數，單位HZ（赫茲）。頻率越高，聲音品質越高，要求的存儲量也越大。採樣數據位數：每個採樣點的數據表示範圍，即採樣點的測量精度。目前常用的有8位（每個採樣劃分為256等份）、12位、16位。聲音通道數：記錄聲音時，如果每次生成一個聲波數據，稱為單聲道；每次生成兩個聲波數據，稱為身歷聲（雙聲道）。雙聲道需要成倍的存儲空間。音頻檔的存儲空間：位元組／秒＝（採樣頻率＊每個採樣的位數＊通道數）／8

例如，數字鐳射唱盤（CD-DA）的標准採樣頻率為44.1kHz，採樣位數為16

位，身歷聲。一分鐘

CD-DA音樂所需的存儲量為

44.1K×16×2÷8=176.4KB/sec176.4*60=10584KB/min視頻是由一幅幅單獨的畫面序列（幀frame）組成，這些畫面以一定的速率連續地投射在螢幕上，使觀察者具有圖像連續運動的感覺。視頻檔的存儲格式有AVI、MPG、MOV等。視頻設備：顯示卡、顯示器顯示卡決定顯示器的顯示模式顯示器的性能參數：點距：是影響顯示器顯示清晰程度的主要因素解析度：螢幕上像素點的數目垂直掃描頻率：單位時間內畫面的刷新次數視頻技術及其設備寬度：271高度：300顏色：2解析度：800*600大小：9.9KB寬度：271高度：300顏色：真彩色（32位）解析度：1024*768大小：238.2KBComparison:動畫

動畫(animation)是活動的畫面，實質是一幅幅靜態圖像的連續播放。動畫的連續播放既指時間上的連續，也指圖像內容上的連續。

電腦設計動畫有兩種：一種是幀動畫，一種是造型動畫。光碟種類存儲光碟只讀光碟可讀寫光碟一次寫多次讀光碟可多次讀寫光碟光碟標準紅皮書標準：採用音軌來記錄資訊黃皮書標準：定義數據編碼、解碼和存儲橘皮書標準：不同時間可多次寫入白皮書標準：數據以MPEG1方式壓縮存儲DVD標準：對視頻、音頻數據進行壓縮CD-ROM和CD-R多媒體應用軟體的制做過程多媒體數據的準備多媒體開發工具與平臺五、多媒體應用開發六、多媒體技術的發展方向目前，多媒體主要從以下幾個方向發展：

多媒體通信網絡環境的研究，在世界範圍內建立了一個可全球自由交互的通信網。對該網路及其設備的研究和網上分佈應用與資訊服務研究將是熱點。1

多媒體技術與相鄰技術相結合，提供了完善的人機交互環境。多媒體仿真智能多媒體等新技術層出不窮，擴大了原有技術領域的內涵，並創造新的概念。

23

多媒體技術與週邊技術構造的虛擬現實研究仍在繼續進展。多媒體虛擬現實與可視化技術需要相互補充，並與語音、圖像識別、智能介面等技術相結合，建立高層次虛擬現實系統。七、VB的多媒體程式設計作業:1：P2131、2、62：利用VB開發一個多媒體課件第三章演算法與數據結構解決具體問題時：從具體問題中抽象出一個適當的數學模型；設計一個解此數學模型的演算法；編出程式進行測試、調整直至得到最終解答。根據實例來看看什麼是演算法，什麼是數據結構例1.圖書館檢索書簽（線性數據模型）查閱圖書目錄卡片：按書名編排的、按作者編排的、按分類編排的…電腦檢索時，處理的對象便是這些目錄卡片上的書目資訊：登錄號、書名、作者名、分類號、出版單位、出版時間等。登錄號唯一，但不同書目之間可能有相同的書名、或有相同的作者名。001高等數學樊映川S01……002理論力學羅遠祥L01……003高等數學華羅庚S01……004線性代數｀欒汝書S02…………………高等數學001，003…理論力學002，…線性代數004，……樊映川S01……華羅庚S01……欒汝書S02……………L002，…S001，003…

電腦之所以能和人對奕，策略事先存入電腦。對奕過程在一定規則下隨機進行，為使電腦靈活對奕，就必須對所有可能發生的情況以及相應的對策都考慮周全，還應能預測發展趨勢，甚至最後結局。井字棋對奕“樹”例2.人機對奕（樹狀數據模型）例3.多叉路口交通燈（圖狀數據模型）

以下為五岔路口，其中C和E為單行道。有的可同時通行，如AB和EC；有的不能同時通行，如EB和AD。BAEDC3.1演算法演算法：通俗而言，就是解決給定問題的方法。處理對象：該問題涉及到的相關數據。數據結構：是一門研究非數值計算的程式設計問題中，電腦操作對象及其之間關係和操作等的學科。演算法與數據結構的關係：程式的問題是加工數據，而如何加工數據是演算法的問題。

程式＝演算法＋數據結構一、演算法的兩要素

(1)邏輯運算：&&、||、!1.操作(2)算術運算：+、-、*、／

(3)數據比較：>、<、=、!=(4)數據傳送：=、scanf()、printf()(1)順序結構2.演算法的控制結構(2)選擇結構P47圖

(3)迴圈結構二、演算法的特徵1、演算法是由一套計算規則組成的一個過程。2、組成演算法的規則是確定的、可執行的。3、每種演算法必須有確定的結果，產生一個或多個輸出。4、與此對應，每個演算法過程必須有0個（自動生成初始數）或多個輸入。5、解答必須在有限步內得到。三、演算法的表示自然語言：易產生歧義、繁瑣、不被機器識別專用工具：流程圖、PAD圖、N-S圖

(1)橢圓：表示起始、終止

(2)平行四邊形：輸入輸出

(3)菱形：判斷

(4)矩形：執行運算式和賦值

(5)開口矩形：注釋框

(6)箭頭：數據流向

描述語言：類C、類VB等開始輸入n值n>0N=n+1N=n-1輸出N值結束N為正整數四、常用演算法枚舉法（窮舉法）：依據條件確定答案大致範圍，在此範圍內對所有可能情況逐一驗證，到全部情況驗證完。演算法簡單，但有時運算量大。百雞問題P53迭代法（逼近迭代）：數值近似求解。確定一合適迭代公式，選一初始近似值以及解的誤差，迴圈處理實現迭代過程，終止條件：前後兩次得到的近似值之差的絕對值<=預先給定的誤差。如求某方程的根遞歸法：直接或間接調用它自身。從函數本身出發，逐次上溯調用其本身求解過程，至遞歸出口，再從裏向外倒推回來，得到最終的值。漢諾塔問題遞推法：從已知的初始條件出發，逐次遞推出最後所求的值分治法：複雜問題分解為小問題，找出各小問題的解，組合成整個問題的解。回溯法：P583.2數據結構一、概述：數據（Data）：是對客觀事物的符號表示，在電腦中是指所有能輸入到電腦中並被電腦程式處理的符號總稱。數據元素（DataElement）：是數據的基本單位，通常我們也稱之為結點，在電腦程式中通常作為一個整體進行考慮和處理。資料項目是數據不可分割的最小單位。有時一個數據元素由若干個資料項目組成，此時稱數據元素為記錄。

個人書庫數據對象（DataObject）：是性質相同的數據元素的集合，是數據的一個子集。數據結構（DataStructure）：是相互之間存在一種或多種特定關係的數據元素的集合。數據元素相互之間的關係稱為結構（structure）。四類基本結構：

(1).集合

(2).線性結構

(3).樹形結構

(4).圖狀結構或網狀結構二、研究內容數據結構

主要研究程式設計中電腦所操作的對象以及它們之間的關係和運算。包括以下三方面：（1）數據的邏輯結構：結點、結點(數據元素)之間的邏輯關係

Data-Structure=(D,R)D：數據元素的集合；R：D上關係的集合（2）數據的存儲結構（物理結構）：數據結構在電腦中的存儲表示（映象）。順序存儲結構、鏈式存儲結構任何一個演算法的設計取決於選定的數據（邏輯）結構，而演算法的實現依賴於採用的存儲結構。（3）數據的運算

線性數據結構：線性表、棧、佇列、數據串、數組、檔結構

非線性數據結構：樹和圖三、線性表（Liner-List）定義：n個數據元素的有限序列一個數據元素可以由若干個資料項目（Item）組成，此時，常把數據元素稱為記錄（Record），含有大量記錄的線性表又稱為檔（File）。（a1,a2,a3,…,an）表中元素的個數n定義為線性表的長度(n>=0)，n=0的表稱為空表。姓名學號性別年齡班級健康狀況王曉林02001男18管02健康程紅02002女20管02一般劉建平02006男21管02神經衰弱線性結構的特點：數據元素呈線性關係在數據元素的非空有限集中，（1）存在唯一的一個被稱作“第一個”的數據元素（2）存在唯一的一個被稱作“最後一個”的數據元素（3）除第一個之外，集合中的每個數據元素均只有一個前驅（4）除最後一個之外，集合中每個數據元素均只有一個後繼所有數據元素ai在同一個線性表中必須是相同的數據類型。a1a2a3a4an……線性表的存儲結構：順序存儲、鏈式存儲順序表：順序分配存儲方式線上性表的順序存儲結構中，其前後兩個元素在存儲空間中是緊鄰的，且前驅元素一定存儲在後繼元素的前面。由於線性表的所有數據元素屬於同一數據類型，所以每個元素在記憶體中佔用的空間大小相同，因此，要在該線性表中查找某一個元素是很方便的。假設線性表中的第一個數據元素的存儲地址為Loc(a0)，每一個數據元素占d位元組，則線性表中第i個元素ai在電腦存儲空間中的存儲地址為：

Loc（ai）=Loc（a0）+id

通常利用數組來表示線性表的順序存儲結構。這是因為數組具有如下特點：（1）數據中的元素間的地址是連續的；（2）數組中所有元素的數據類型是相同的。而這與線性表的順序存儲空間結構是類似的。鏈表：用一組任意的存儲單元（可以是不連續的）存儲線性表的數據元素。若定義數組A[n]={a0，a1，a2，…，an-1}，假設每一個數組元素佔用d個位元組，則數組元素A[0]，A[1]，A[2]，…，A[n-1]的地址分別為Loc(A[0])，Loc(A[0])+d，Loc(A[0])+2d，…，Loc(A[0])+（n-1）d。其結構如圖2-2所示。

順序結構中的運算：在數組中插入元素

0

a01a12a2┇┇i-1ai-1i

aii+1ai+1i+2

ai+2┇┇numanum

0a01a12a2

┇┇i-1ai-1ixi+1aii+2ai+1

┇┇numAnum

插入x插入（移動結點個數為n/2）、刪除（移動結點個數為(n-1)/2）、查找、更新（P65）鏈表（鏈式存儲方式可表示線性結構，也可表示非線性結構）：數據域：用於存放數據元素值；指針域：用於存放直接前驅或直接後繼結點的地址（指針）。單鏈表（線性鏈表）迴圈鏈表：鏈表最後一個結點的指針域不為Null，而指向第一個結點。（P67）雙向鏈表：含兩個指針域。分別指向前驅節點和後繼結點數據元素數據域：存值指針域：存地址a0a1an-1

head

head…(a)(b)數據域指針域四、棧（Stack）棧：一種特殊的線性表。“後進先出”，運算規則受到一些約束和限定，又稱“限定性數據結構”。棧的結構和特點：棧頂、棧底、空棧、LIFO表a1a2a3…an棧頂Top棧底Bottom入棧Push出棧Pop棧（Stack）：是限定僅在表尾進行插入或刪除操作的線性表。表尾端稱棧頂(Top)表頭端稱棧底(Bottom)不含元素的空表稱為空棧五、佇列（Queue）佇列：也是一種特殊的線性表。“先進先出”＝“先來先解決”。不允許插隊，不允許中途離隊。佇列的結構特點：隊尾、隊頭、空佇列、FIFO限定所有的插入只能在表的一端進行（隊尾Rear），而所有的刪除都在表的另一端進行（隊頭Front）。a1a2a3a4…an出佇列入隊列隊頭隊尾佇列的物理存儲：順序存儲結構、鏈式存儲結構佇列的運算：設置一個空佇列、判定佇列是否是空佇列、插入一個新的隊尾元素（入隊列）、刪除隊頭元素（出佇列）、讀取隊頭元素。(P70)

串(String):一維字元數組,長度不恒定.樹和二叉樹(P71)定義和基本術語樹（Tree）：n（n>=0）個結點組成的有限集合，其中有一個特定的稱為根（Boot）的結點。二叉樹（BinaryTree）：每個結點至多只有兩棵子樹（即二叉樹中不存在度大於2的結點），二叉樹的子樹有左右之分，其次序不能任意顛倒。度(Degree)：結點擁有的子樹稱為結點的度；樹中各結點的度的最大值被定義為該樹的度。根、葉子二者主要區別：二叉樹的結點的子樹要區分左子樹和右子樹，即使在結點只有一棵子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。（P72）樹和二叉樹的存儲結構樹的存儲結構：多重鏈表存儲樹的結構要求：結點中指針域的個數應有樹的度來決定（圖）P73二叉樹的存儲結構：順序存儲和鏈式存儲

DATA、左指針域（LC，指向結點的左子樹）、右指針域（RC，指向右子樹）書的二叉樹表示：P73

ABCEDABCDE樹對應的二叉樹樹和二叉樹的遍曆樹的遍曆：先根（次序）遍曆：先訪問根結點遍曆每棵子樹後根（次序）遍曆：後根遍曆每棵子樹，在訪問根結點二叉樹的遍曆：前序遍曆二叉樹：

a.訪問根結點；b.前序遍曆左子樹；c.前序遍曆右子樹中序遍曆二叉樹：

a.中序遍曆左子樹；b.訪問根結點；c.中序遍曆右子樹後序遍曆二叉樹：

a.後序遍曆左子樹；b.後序遍曆右子樹；c.訪問根結點棧的物理存儲：順序存儲結構、鏈式存儲結構

順序棧：利用一組地址連續的存儲單元依次存放自棧底倒棧頂的數據元素，同時附設指針top指示棧頂元素在順序棧中的位置。top＝0表棧空。鏈棧：棧的運算：設置控棧、判定是否為空棧、進棧、退棧操作、讀取棧頂元素··^……Top棧頂棧底例題：右圖二叉樹表示運算式：a+b*(c-d)-e/f1).前序遍曆序列：-+a*b–cd/ef2).中序遍曆序列：a+b*c–d–e/f3).後序遍曆序列：abcd-*+ef/-－＋／－ab＊cdfe圖（Graphic）概念和基本術語G(V,E)代表一個圖，圖中的結點稱為頂點，V是結點的有窮集合（非空），相關的結點偶對稱為邊（或弧），E是邊的有窮集合（E為空集，對應的圖中只有頂點沒有邊）。無向圖：圖中代表一條邊的結點偶對如果是無序的，則稱此圖為無向圖。否則，稱為有向圖。v1v2v3v4v4v1v2v3G1(v1、v2、v3、v4)G2(v1、v2、v3、v4)G1:<v1,v2><v1,v3><v1,v4><v2,v3><v2,v4>G2:<v1,v2><v1,v3><v2,v4><v4,v1>圖的存儲相鄰矩陣表示法鄰接表示法圖的遍曆

類似樹的遍曆，從某個頂點出發，沿某條路徑對圖中其餘頂點進行搜索的過程。深度優先遍曆:1-2-4-8-5-3-6-7廣度優先遍曆:1-2-3-4-5-6-7-812345678總結線性表棧佇列樹二叉樹圖3.3查找（Searching）基本概念：根據給定的某個值，在查找表中確定一個其關鍵字等於給定值的記錄或數據元素。若表中存在這樣的一個記錄，則稱查找是成功的，查找結果為給出整個記錄的資訊，或指示該記錄在查找表中的位置；若表中不存在關鍵字等於給定值的記錄，則稱查找不成功，查找結果給出一個“空”記錄或“空”指針。查找演算法：順序查找二分法查找分塊查找查找的演算法種類很多。衡量一個查找演算法的主要標準是查找過程中對關鍵字進行的平均比較次數，或稱平均檢索長度，以n的函數形式表示，n是數據結構中的結點個數（或檔記錄個數）。順序查找方法：用待查關鍵字值與線性表中各結點的關鍵字值逐個比較，直到找出相等的關鍵字值若找遍所有結點都找不到符合要求的項，即查找失敗。優點：對線性表結點邏輯次序無要求，對其存儲結構亦無要求。缺點：平均檢索長度長為n／2。演算法：P82二分法查找對關鍵字排好序的線性表，效率較高。用要查找的關鍵碼值X與線性表中間位置結點的關鍵碼值W比較，這是有三種可能：X＝W，此時已經查找成功，查找結束X>W，表明X只能在表的後半部分，取表的後半部分進行查找。X<W，表明X只能在表的前半部分，取表的前半部分進行查找。優點：平均檢索長度小。P83缺點：要求檔必須按關鍵字有序，只是用於順序方式存儲的順序表。分塊查找又稱索引順序查找。性能介於順序查找和二分查找之間。適用於順序方式存儲的順序表，也適用於線性鏈表方式存儲的檔。3.4排序基本概念：排序就是將一個元素（或記錄）的任意序列重新排列成一個按關鍵字排列的有序序列。內排序：當檔的數據量不太大時，排序過程中的全部資訊放在記憶體中處理的排序方法。（基礎）分為：插入排序、選擇排序、交換排序外排序：當檔的數據量較大，以至於記憶體不足以存放全部資訊時，排序過程中需要在內、外存之間不斷地進行數據交換才能達到排序的目的，這種排序稱為外排序。一、插入排序基本思想：P85直接插入排序：R(49),R(38),R(65),R(97),R(76),R(13),R(27)……{R(38),R(49),R(65),R(97)}現插入R(76){R(38),R(49),R(65),R(76),R(97)}二分法插入排序（折半插入排序）二、選擇排序基本思想：每次從待排序的記錄中選出關鍵字最小（或最大）的記錄，順序放在已排序的記錄序列的最後，直到全部排完為止。演算法：P85三、交換排序基本思想：兩兩比較待排序記錄的關鍵碼，並交換不滿足順序要求的那些偶對，直至全部滿足為止。起泡排序（冒泡排序）：快速排序（分區交換排序）：是對起泡排序的一種改進。在待排序列中任取一個記錄，以它為基準用交換的方法將所有記錄分成兩部分，關鍵碼值比它小的在一部分，關鍵碼值比它大的在另一部分。在分別對這兩部分實施上述過程，一直重複到排序完成。3.5檔（File）檔：是有大量性質相同的記錄組成的集合。可按其記錄的類型不同而分成兩類：操作系統的檔和數據庫檔。對檔的操作（運算）可分為：檢索和修改兩大類。檢索是指按記錄的邏輯號或關鍵字值查找某個記錄；修改包括對記錄的插入、刪除和對記錄某些資料項目的更新。檔的結構順序檔：檔記錄的邏輯次序是按關鍵碼遞增（減）的次序定義的，且在外記憶體上是按同樣的次序排列的。索引檔倒排檔直接檔、相對檔、位元組流檔檔的操作檢索：查找一定條件的記錄插入：檔中增加一個新紀錄刪除：刪去檔中的一個記錄修改：對記錄中某些字段的值更新排序：按照條件對指定字段的值進行排序檔外部看，還實現檔的建立、打開、關閉、撤銷、複製、改名等許多面向用戶的操作。作業：P92：

891013第四章程式開發與軟體工程程式開發是軟體開發的核心。程式開發的過程：建立計算模型、設計程式、編寫代碼、測試程式、交付使用。一、程式開發程式設計：建立計算模型、設計程式、編寫代碼、測試程式程式設計過程：需求分析、程式設計、編碼、測試、排錯1、程式設計過程需求分析

問題的提出只是用戶的需要，把需要變為需求是需求分析的工作，即有沒有可能用軟體來滿足這個需要。如果可行，這個程式應是什麼樣的（需求定義）。

規格說明書的內容：P94軟體設計是後續開發步驟及軟體維護工作的基礎。如果沒有設計，只能建立一個不穩定的系統結構程式設計程式設計並不等於用某種程式設計語言編寫代碼。流程圖清楚的看出執行邏輯（做設計）。流程圖逐步細化後，寫出對應源代碼叫編碼（Coding）。設計先於編碼。開始輸入n值n>0N=n+1N=n-1輸出N值結束程式設計要滿足規格說明對性能的要求可靠性：交付時規格說明均滿足，用一段時間就不正確了。安全性：使用不當能否導致所在系統崩潰。可維護性：修改一個小錯，引發多個大錯。可移植性：軟體、硬體(會影響程式的使用性能)適應性：平臺、軟體、硬體設施可測試性：測試數據能否切中要害；除了使用現場，其他環境能否做有意義的測試。設計準則模組化：降低程式的複雜性，有利於閱讀、測試、修改。但模組之間相互影響，修改、刪除時要注意。模組大小不超過66行為宜。儘量少用全局變數。

“模組”，又稱“組件”。它一般具有如下三個基本屬性:功能：描述該模組實現什麼功能邏輯：描述模組內部怎麼做狀態：該模組使用時的環境和條件結構化：只有三種基本控制結構並層層前套，這樣有利於測試、查錯、修改。數據隱藏：凡與其他模組無關的數據盡可能作為局部量放在自己的模組內。可測試性：設計階段雖不是重點，但還是應該要考慮，以免最後變得不可追蹤。一致性：行文風格、表達方法儘量一致。（各層模組分解數、形參個數、本程式系統與外界介面數，均不要超過７個）設計方法自頂向下逐步求精 把一個模組的功能逐步分解，細化為一系列具體的步驟，進而翻譯成一系列用某種程式設計語言寫成的程式。 將軟體的體系結構按自頂向下方式，對各個層次的過程細節和數據細節逐層細化，直到用程式設計語言的語句能夠實現為止，從而最後確立整個的體系結構。

P97面向對象設計

編碼模組最後重組將功能相差不多或不夠規範的模組以規範的庫模組取代，使程式乾淨、不冗餘。一致性完善根源程式級的程式優化 優化（Optimization）：儘量減少時空開銷。 一些常見的優化：盡可能用符號常量減少重複計算將迴圈次數多的作為內迴圈減少迴圈內的重複減少不必要的計算測試與排錯測試技術

測試：為了發現程式中的錯誤而執行程式的過程。

測試用例（TestCase）：一組測試數據。黑箱技術（黑盒測試） 把程式看成一個黑盒子，完全不考慮程式的內部結構和處理過程。黑盒測試是在程式介面進行的測試，他只檢查程式功能是否能按照規格說明書的規定正常使用，程式是否能適當的接收輸入數據產生正確的輸出資訊，並且保持外部資訊（資料庫或檔）的完整性。所以又稱功能測試。白箱技術（白盒測試） 可以把程式看成裝在一個透明的白盒子裏，也就是完全瞭解程式的結構和處理過程。這種方法按照程式內部的邏輯測試程式，檢驗程式中的每條通路是否都能按預定要求正確工作。所以又稱為結構測試。測試的經濟性要求達到的測試目的：沒有語法錯誤運行應當有結果典型用例結果正確典型有效數據結果正確，無效數據有預防措施對一切可能想得到的數據不出錯排錯（Debugging）調試，是消除程式中缺陷（Bug）的過程。步驟如下：通過測試發現程式有錯找出出錯的位置分析出錯原因並改正之再測試消除找出的缺陷二、軟體工程背景：1968年由NATO(北大西洋公約組織)在德國Garmish召開學術會議上，FeitzBauer首先提出了“軟體