第1章 程序設計概述

程序設計基礎 C 導言1 程序設計語言概述 計算機 指令 程序 程序設計語言 C語言 導言2 C語言概述C語言是國際流行的 很有發(fā)展前途的計算機高級語言 既可用于編寫系統(tǒng)軟件 又可用于編寫應用軟件 既有高級語言特性 又有低級語言特性 應用領域 系統(tǒng) 網絡 單片機 手機 游戲 導言3 C語言的學科地位C語言是計算機專業(yè)基礎課 它為以后的面向對象技術的學習以及C可視化軟件的學習奠定了基礎 同時C語言也是數(shù)據(jù)結構和操作系統(tǒng)等計算機專業(yè)主干課程的上機工具 要求學生充分重視 導言4 如何學好C語言 僅供參考 勤學 課內 課外 中文 英文 多練 實踐是檢驗真知的唯一標準好問 不 知 下問善于思考 學而不思則罔 教學要求 通過課堂授課與上機實驗相結合的方式 使學生能夠深刻理解結構化程序設計的思想與方法掌握C語言的基礎知識能夠在計算機上熟練使用C語言的編輯環(huán)境來編寫 調試 運行程序具有一定實踐體會和相關的編程能力 能編寫超過1000行的C語言應用程序 主要參考書目 譚浩強 C語言程序設計 清華大學出版社 1999 全國計算機等級考試二級C教材 C語言教學網站 集思廣益 考核辦法 出勤 作業(yè) 上機 20 30 考試成績 70 80 1 0計算機簡介 一 計算機的組成 1 中央處理器 CPU 運算器控制器寄存器組 對數(shù)據(jù)進行運算 控制計算機各部分協(xié)調工作 存放指令和數(shù)據(jù)等 1 0計算機簡介 2 存儲器 內存 存放程序代碼及數(shù)據(jù) 3 外部設備輸入設備 輸入程序和數(shù)據(jù) 如鍵盤 鼠標 輸出設備 輸出計算結果 如顯示器 打印機 外部存貯器 外存 儲存各種數(shù)據(jù) 如硬盤 軟盤 U盤 二 計算機基本結構 外部設備 中央處理器 CPU 存儲器 輸入 輸出接口電路 數(shù)據(jù)總線 控制總線 地址總線 1 0計算機簡介 操作系統(tǒng) OperatingSystem OS是各種軟件的核心與基礎功能 cpu管理 存儲管理 文件管理設備管理 作業(yè)管理等常用的OS MS DOS Windows Unix Linux 用戶源程序 裸機 由計算機的各種硬件組成CPU 主板 內存 硬盤 聲卡 顯卡 網卡 光驅 電源 機箱 顯示器 鍵盤 鼠標 音響等 裸機 編譯系統(tǒng)和高級語言環(huán)境 用戶源程序 1 0計算機簡介 1 1 1程序設計語言 一 程序的概念 二 計算機軟件 程序是計算任務的處理對象和處理規(guī)則的描述 計算機軟件 程序 文檔 1 計算機處理的任務都是計算任務 2 處理對象是數(shù)據(jù) 3 處理規(guī)則是指處理的動作和步驟 三 軟件語言 軟件語言是書寫計算機軟件的語言 1 1 1程序設計語言 四 程序設計語言 程序設計語言是用于書寫計算機程序的語言 基本成分 1 數(shù)據(jù)成分 描述程序所涉及的數(shù)據(jù) 2 運算成分 描述程序所包含的運算 3 控制成分 表達程序的控制構造 4 傳輸成分 表達程序的數(shù)據(jù)傳輸 判斷 程序設計語言 軟件語言 1 1 1程序設計語言 五 程序設計語言的發(fā)展 機器語言二進制代碼表示的計算機能直接識別和執(zhí)行的一種機器指令集合 執(zhí)行速度快 但較難掌握 不同型號的計算機語言不同 根據(jù)語言與硬件的關聯(lián)程度 程序設計語言分為 低級語言和高級語言 發(fā)展過程是從低級到高級 1 1 1程序設計語言 2 匯編語言用助記符號描述的指令系統(tǒng) 如 ADDa b機器不能直接執(zhí)行 必須翻譯成機器碼 較難掌握 匯編語言 機器語言 不能直接執(zhí)行 較為簡單 一一對應替換 1 1 2程序設計 3 高級語言接近于自然語言的計算機程序設計語言 不能直接運行 需要轉換為機器語言 通常有解釋和編譯兩種 使用較普遍的高級語言 FORTRAIN ALGOL BASIC PASCAL C C JAVA Delphi等 高級語言 機器語言 類似于自然語言 需要專門的編譯器 解釋器 過程較為復雜 1 1 2程序設計 三種語言的比較 高級語言 匯編語言 機器語言 1 1 2程序設計 六 程序設計的具體步驟 方案確定 建立問題的數(shù)學模型算法描述 描述處理規(guī)則數(shù)據(jù)描述 描述處理對象編寫程序 編碼 轉換為程序語言程序測試 檢測程序的正確性 注 編寫程序只是程序設計的一個步驟 不等于程序設計 1 1 3數(shù)據(jù)結構 數(shù)據(jù)結構 DataStructure 計算機存儲 組織數(shù)據(jù)的方式 數(shù)據(jù)結構一般包括三個方面的內容 數(shù)據(jù)之間的邏輯關系 也稱數(shù)據(jù)的邏輯結構 LogicalStructure 數(shù)據(jù)元素及其關系在計算機存儲器內的表示 稱為數(shù)據(jù)的存儲結構 StorageStructure 數(shù)據(jù)的運算 即對數(shù)據(jù)施加的操作 數(shù)據(jù)結構 邏輯結構 存儲結構 運算 1 1 4算法概述 一 算法的概念及特性 1 算法的概念廣義上講 算法就是為解決一個問題而采取的方法和步驟 對同一個問題可能有不同的解決方法和步驟 即不同的算法為了快速有效的解決問題 在保證算法正確的基礎上 還要考慮算法的質量 選擇較優(yōu)的算法 方法簡單 運算步驟少 運算快 內存開銷小的算法 數(shù)據(jù)結構 算法 程序 對數(shù)據(jù)的描述 對操作的描述 2 計算機算法的分類 1 數(shù)值運算算法 用于求數(shù)值解 如求解一個多元方程 2 非數(shù)值運算算法 多用于管理領域 如圖書管理 著名計算機科學家沃思提出的一個公式 1 1 4算法概述 有窮性 空間有窮 一個算法包含有限的操作步驟 時間有窮 算法可以在合理的時間內運行完 確切性 算法中的每一個步驟是確定的 含義是唯一的可行性 算法中每一個步驟是可行的 有零個或多個輸入有一個或多個輸出 3 算法的五大特性 1 1 4算法概述 例1 1 對于給定的有序數(shù)列 3 5 11 17 21 23 28 30 32 50 如何查找30這個數(shù)據(jù)元素 1 1 4算法概述 算法一 將30按順序與給定數(shù)列逐一比較直到找到為止 這種算法在最壞的情況可能需要比較整個序列 算法二 查找過程中采用跳躍式方式查找 即先以有序數(shù)列的中點位置為比較對象 如果要找的元素值小于該中點元素 則將待查序列縮小為左半部分 否則為右半部分 通過一次比較 將查找區(qū)間縮小一半 遞推法遞歸法窮舉搜索法貪婪法分治法動態(tài)規(guī)劃法迭代法 4 算法設計與分析常用的方法 1 1 4算法概述 一 算法的表示方法 常用的算法表示方法 自然語言 流程圖 N S圖 偽代碼 程序語言等 1 自然語言表示法用自然語言描述的算法 例1 2 用自然語言表示求兩個數(shù)的和 如2 3 1 2算法表示方法 Step1 將輸入的第一個數(shù)2存入xStep2 將輸入的第二個數(shù)3存入yStep3 將x和y相加的結果存入zStep4 輸出結果z 通俗易懂 比較冗余 容易出現(xiàn)歧義 2 流程圖表示法用圖框表示各種操作 用箭頭表示算法流程 1 2算法表示方法 2 流程圖表示法用圖框表示各種操作 用箭頭表示算法流程 用流程圖表示求兩個數(shù)的和 1 2算法表示方法 直觀形象 易于理解 流程線沒有嚴格限制 C語言是一種結構化程序設計語言 結構化程序設計主要采用自上而下 逐步細化的方法 結構化程序有三種基本結構 順序結構 選擇結構 循環(huán)結構 當型 循環(huán) 直到型 循環(huán) 1 2 2流程圖表示法 傳統(tǒng)的程序流程圖例圖 結束 輸入a b c a b b c a c 輸出c 輸出b 輸出c 輸出a 開始 Y N Y Y N N 即結構化程序設計流程圖 提供了描述三種基本邏輯結構的圖形工具 與傳統(tǒng)的程序流程圖對照描述如下 1 順序結構 1 2 3N S圖表示法 b N S圖表示 a 流程圖表示 2 選擇結構 分支結構 1 2 3N S圖表示法 b N S圖表示 a 流程圖表示 由分支結構派生出來的多分支結構 1 2 3N S圖表示法 b N S圖表示 a 流程圖表示 3 循環(huán)結構 a 當型循環(huán)結構 先判斷循環(huán)條件是否滿足 當條件滿足 執(zhí)行一遍循環(huán)體 再判斷循環(huán)條件 仍滿足再執(zhí)行一遍循環(huán)體 直到不滿足條件 則退出循環(huán) 執(zhí)行循環(huán)體后的下一語句 若第一次判斷條件就不滿足 則一次也不執(zhí)行循環(huán)體 1 2 3N S圖表示法 b N S圖表示 a 流程圖表示 b N S圖表示 b 直到型循環(huán)結構 先執(zhí)行一遍循環(huán)體 再判斷循環(huán)條件是否滿足 如不滿足再執(zhí)行一遍循環(huán)體 直到條件滿足 則退出循環(huán) 執(zhí)行循環(huán)體后的下一語句 這種循環(huán)結構至少要執(zhí)行一遍循環(huán)體 1 2 3N S圖表示法 a 流程圖表示 2 N S流程圖表示法 順序結構 選擇結構 循環(huán)結構 當型 循環(huán) 直到型 循環(huán) 1 2 3N S圖表示法 例描述求n 的值的算法 1 2 3N S圖表示法 F 1 i 1 開始 輸入n i n F F i 輸出F 結束 i i 1 1 3程序設計方法 一 結構化程序設計 SP方法 程序的基本單元是函數(shù) SP方法主張使用順序 選擇 循環(huán)三種基本結構來嵌套連結成具有復雜層次的 結構化程序 嚴格控制GOTO語句 無條件轉移 的使用 自頂而下 逐步求精 的設計思想 獨立功能 單出 入口 的模塊僅用3種 順序 分支 循環(huán) 基本控制結構的編碼原則 C語言就是結構化設計語言 程序結構圖 1 3程序設