第1章 程序設(shè)計(jì)概述

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