數(shù)據(jù)構(gòu)C語言描述結(jié)數(shù)據(jù)結(jié)構(gòu)C語言戚爽主講課程信息課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱：DataStructure教材：數(shù)據(jù)結(jié)構(gòu)

鄒嵐主編上課教師：戚爽學(xué)時：64學(xué)時（4學(xué)時/周*16周）3數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容《數(shù)據(jù)結(jié)構(gòu)》課程是研究程序設(shè)計中非數(shù)值計算的數(shù)據(jù)以及它們之間的關(guān)系和操作等的一門學(xué)科。它以數(shù)學(xué)為基礎(chǔ)、涉及計算機硬件與計算機軟件的研究范圍，是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)軟件數(shù)學(xué)硬件為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)01計算機各相關(guān)專業(yè)重要的專業(yè)基礎(chǔ)課，處于核心地位。02各高校計算機相關(guān)專業(yè)考研/專升本必考的專業(yè)課。03為從事有關(guān)計算機的教學(xué)、科研、開發(fā)、管理等奠定重要的專業(yè)基礎(chǔ)?！稊?shù)據(jù)結(jié)構(gòu)》屬于武術(shù)中的“練功”科目“練武不練功，到頭一場空”前、后續(xù)課程關(guān)系C語言程序設(shè)計前導(dǎo)課程數(shù)據(jù)結(jié)構(gòu)專業(yè)核心數(shù)據(jù)庫原理操作系統(tǒng)軟件工程后續(xù)課程計算機網(wǎng)絡(luò)1課程目標(biāo)能夠分析研究計算機加工的對象的特性，獲得其邏輯結(jié)構(gòu)，根據(jù)需求，選擇合適存儲結(jié)構(gòu)及其相應(yīng)的算法；學(xué)習(xí)一些常用的算法；復(fù)雜程序設(shè)計的訓(xùn)練過程，要求編寫的程序結(jié)構(gòu)清楚和正確易讀；初步掌握算法的時間分析和空間分析技術(shù)。學(xué)編程的境界學(xué)會寫程序?qū)W會高效地寫程序?qū)W會寫高效的程序?qū)W會設(shè)計算法學(xué)會設(shè)計有用的算法寫作：學(xué)字，詞，文法，句法快速地寫文章寫簡潔明快的好文章選擇結(jié)構(gòu)，流程，方法寫人們喜歡看的文章學(xué)習(xí)要求123提前預(yù)習(xí)、認真聽課、按時完成書面及上機作業(yè)注意先修課程的知識準(zhǔn)備C語言程序設(shè)計注意循序漸進基本概念、基本思想、基本步驟、算法設(shè)計4注意培養(yǎng)算法設(shè)計的能力理解所講算法、對此多做思考：若問題要求不同，應(yīng)如何選擇數(shù)據(jù)結(jié)構(gòu)，設(shè)計有效的算法綜合成績構(gòu)成期末考試60%平時成績40%考核辦法出勤率上機作業(yè)隨堂測試課堂紀律無故遲到無故曠課玩游戲、手機第1章

緒論1.4算法及算法分析1.1

數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用1.2本課程討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.5習(xí)題第一章緒論知識目標(biāo)：了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展理解數(shù)據(jù)結(jié)構(gòu)中的基本概念理解抽象數(shù)據(jù)類型的概念、記法和用法理解算法分析的目的掌握算法及其特性掌握算法時間復(fù)雜度的分析方法技能目標(biāo)：能分析一般算法的時間復(fù)雜度1.4算法及算法分析1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用1.2本課程討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.5習(xí)題1938年出生，從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming《計算機程序設(shè)計藝術(shù)》，他計劃共寫7卷，出版三卷之后，已震驚世界。1974年，他獲得計算機科學(xué)界的最高榮譽——圖靈獎，年僅36歲；1995年他又獲得了馮·諾依曼獎。獲獎作品至今才出到第四卷。其中第一卷《基本算法》中較系統(tǒng)地闡述了數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作，開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的課程體系。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——唐納德·克努特（高納德）DonaldKnuth數(shù)據(jù)表示：將數(shù)據(jù)存儲在計算機（內(nèi)存）中數(shù)據(jù)處理：處理數(shù)據(jù)，設(shè)計方案（算法）著名計算機科學(xué)家沃思提出：程序設(shè)計的實質(zhì)是什么?1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計程序=數(shù)據(jù)結(jié)構(gòu)+算法利用計算機求解問題的一般過程？數(shù)學(xué)模型解題思路數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)類型程序問題抽象設(shè)計編碼運行結(jié)果1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用計算機不能分析問題并產(chǎn)生問題的解決方案，必須由人來分析問題，確定問題的解決方案，編寫程序，然后讓計算機執(zhí)行程序最終獲得問題的解。程序設(shè)計的實質(zhì)：對具體問題選擇一種適合的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個優(yōu)秀的算法。操作對象對象間關(guān)系舉個栗子1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用例1-1手機電話號碼查詢問題將電話號碼集合組織成線性結(jié)構(gòu)和樹結(jié)構(gòu)，查找操作的效率不同，當(dāng)數(shù)據(jù)量較大時差別就更大。1.4算法及算法分析1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用1.2本課程討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.5習(xí)題例1-2學(xué)籍管理問題完成什么功能?各表項之間是什么關(guān)系？1.2本課程討論的主要內(nèi)容線性結(jié)構(gòu)中數(shù)據(jù)元素存在著由依次排列的先后次序決定的關(guān)系例1-3人—機對弈問題如何實現(xiàn)對弈？各格局（棋盤狀態(tài)）之間是什么關(guān)系？1.2本課程討論的主要內(nèi)容樹型結(jié)構(gòu)中，除樹根外，每個元素都有唯一的前驅(qū)（后繼個數(shù)不限）例1-4七巧板涂色問題如何表示區(qū)域之間的鄰接關(guān)系？1.2本課程討論的主要內(nèi)容在圖結(jié)構(gòu)中，任一數(shù)據(jù)元素，均可有多個前趨和多個后繼，也稱網(wǎng)狀結(jié)構(gòu)使用至多4種不同顏色對七巧板進行涂色（每塊涂一種顏色），要求相鄰區(qū)域的顏色互不相同，打印輸出所有可能的涂色方案。1.2本課程討論的主要內(nèi)容由以上三個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計中非數(shù)值計算的數(shù)據(jù)以及它們之間的關(guān)系和操作等的一門學(xué)科。重點分析數(shù)據(jù)之間抽象的相互關(guān)系，不涉及數(shù)據(jù)的具體內(nèi)容。1.2本課程討論的主要內(nèi)容存儲結(jié)構(gòu)邏輯結(jié)構(gòu)數(shù)據(jù)處理（算法）順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)集合樹型

結(jié)構(gòu)圖

結(jié)構(gòu)查找技術(shù)排序技術(shù)索引技術(shù)圖數(shù)據(jù)結(jié)構(gòu)的知識架構(gòu)線性

結(jié)構(gòu)如何實現(xiàn)插入、

刪除、查找等

基本操作，

有效地處理數(shù)據(jù)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系如何有效地存儲數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系索引結(jié)構(gòu)散列結(jié)構(gòu)1.4算法及算法分析1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用1.2本課程討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.5習(xí)題1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)：所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。數(shù)值數(shù)據(jù)：整數(shù)、實數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖像、聲音、文字等數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)項：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。學(xué)號姓名性別出生日期政治面貌0001陸宇男1996/09/02團員0002李明男1995/12/25黨員0003湯曉影女1996/03/26團員數(shù)據(jù)項數(shù)據(jù)元素1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項之間的關(guān)系包含關(guān)系：數(shù)據(jù)由數(shù)據(jù)元素組成，數(shù)據(jù)元素由數(shù)據(jù)項組成。數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項一般不予考慮。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。關(guān)聯(lián)方式或鄰接關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型學(xué)籍管理問題中，表項之間的邏輯關(guān)系指的是什么？人機對弈問題中，格局之間的邏輯關(guān)系指的是什么？七巧板涂色問題中，板塊之間的邏輯關(guān)系指的是什么？思維1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。數(shù)據(jù)的邏輯結(jié)構(gòu)在形式上可定義為一個二元組：Data_Structure=(D,R)其中D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的集合。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={<A,B>,<A,E>,<A,F>,<B,C>,<B,D>,<C,D>,<D,E>,<D,G>,<E,F>,<E,G>}1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。存儲結(jié)構(gòu)：又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示。內(nèi)存數(shù)據(jù)的運算:定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，

實現(xiàn)在數(shù)據(jù)的存儲結(jié)構(gòu)上。面向問題面向計算機1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對一的線性關(guān)系；數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對一的線性關(guān)系；樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的層次關(guān)系；1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對一的線性關(guān)系；樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的層次關(guān)系；圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示。…batcateat…起始地址例：（bat,cat,eat）邏輯上相鄰的數(shù)據(jù)元素的存儲位置也相鄰。例：（bat,cat,eat）0200020803000325…………bat0200cat0325eat∧1.3數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示。鏈?zhǔn)酱鎯Y(jié)構(gòu)：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。通常用高級程序語言中，用一維數(shù)組類型來表示順序存儲結(jié)構(gòu)；用指針類型來描述鏈?zhǔn)酱鎯Y(jié)構(gòu)。邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲結(jié)構(gòu)屬于具體實現(xiàn)的視圖，是面向計算機的。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲，而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。為了區(qū)別于存儲結(jié)構(gòu)，常常將數(shù)據(jù)的邏輯結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。數(shù)據(jù)類型指由系統(tǒng)定義的、用戶可直接使用且可構(gòu)造的類型。數(shù)據(jù)類型中定義了兩個集合：類型的取值范圍、可允許使用的一組運算集。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念C語言中的int型變量，是指由-32768到32767范圍中的值構(gòu)成的集合及一組操作（加、減、乘、除、乘方等）的總稱。長整型longC數(shù)據(jù)類型基本類型構(gòu)造類型指針類型空類型void字符類型char整型實型單精度型float雙精度型double數(shù)組結(jié)構(gòu)體struct共用體union短整型short整型int枚舉類型一般來說，高級語言中的數(shù)據(jù)類型可分為兩類：非結(jié)構(gòu)的原子類型原子類型的值是不可分解的。C語言中的標(biāo)準(zhǔn)類型（整型、實型、字符型、枚舉型）及指針和空類型。結(jié)構(gòu)類型結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是原子型或結(jié)構(gòu)型。C語言中的數(shù)組、結(jié)構(gòu)體、共用體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型（AbstractDataType，ADT）基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。抽象數(shù)據(jù)類型描述的是一組邏輯特性，與計算機內(nèi)部的表示和實現(xiàn)無關(guān)。抽象數(shù)據(jù)類型數(shù)據(jù)對象數(shù)據(jù)關(guān)系基本操作一個ADT定義了一個數(shù)據(jù)對象，數(shù)據(jù)對象中各元素間的結(jié)構(gòu)關(guān)系，以及一組處理數(shù)據(jù)的操作。ADT通常由用戶定義并且用以表示應(yīng)用問題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)服務(wù)操作。邏輯結(jié)構(gòu)操作集合抽象數(shù)據(jù)類型定義ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>基本操作名(參數(shù)表)初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>}ADT抽象數(shù)據(jù)類型名1.3數(shù)據(jù)結(jié)構(gòu)的基本概念例：P5隊列的抽象數(shù)據(jù)類型描述數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)

順序存儲鏈?zhǔn)酱鎯暇€性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)非數(shù)值問題數(shù)據(jù)表示加工型運算引用型運算1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（總結(jié)）1.4算法及算法分析1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用1.2本課程討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.5習(xí)題1.4算法及算法分析算法（Algorithm）：是對特定問題求解步驟的一種描述，是指令的有限序列。算法的五大特性：輸入：一個算法有零個或多個輸入。輸出：一個算法有一個或多個輸出。有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出?？尚行裕核惴枋龅牟僮骺梢酝ㄟ^已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。1.4算法及算法分析常用的描述方法有：用自然語言描述算法用流程圖描述算法用N-S流程圖描述算法用計算機語言描述算法用偽代碼描述算法歐幾里德算法——輾轉(zhuǎn)相除法求兩個自然數(shù)m和n的最大公約數(shù)1.4算法及算法分析mnr歐幾里德算法（有窮性、確定性、可行性）1.4算法及算法分析例：歐幾里德算法步驟1：將m除以n得到余數(shù)r；步驟2：若r等于0，則n為最大公約數(shù)，

算法結(jié)束；否則執(zhí)行步驟3；步驟3：將n的值放在m中，將r的值放在n中，

重新執(zhí)行步驟1；自然語言1.4算法及算法分析優(yōu)點：容易理解缺點：冗長、二義性使用方法：粗線條描述算法思想

注意事項：避免寫成自然段算法的描述方法——自然語言1.4算法及算法分析例：歐幾里德算法N開始輸入m和n

r=m%nr=0m=n；n=r輸出n結(jié)束Y流程圖1.4算法及算法分析優(yōu)點：流程直觀易懂缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次算法的描述方法——流程圖1.4算法及算法分析例：歐幾里德算法#include<stdio.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){printf(“%d\n”,CommonFactor(63,54));}程序設(shè)計語言1.4算法及算法分析優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，拘泥于具體細節(jié)而忽略算法邏輯的重要性，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數(shù)算法的描述方法——程序設(shè)計語言1.4算法及算法分析例：歐幾里德算法

1.r=m%n;

2.循環(huán)直到r等于0

2.1m=n;

2.2n=r;

2.3r=m%n;

3.輸出n;上述偽代碼再具體一些，用C語言的函數(shù)來描述。偽代碼1.4算法及算法分析偽代碼（Pseudocode）：介于自然語言和程序設(shè)計語言之間的方法，它采用某一程序設(shè)計語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計，被稱為“算法語言”或“第一語言”。優(yōu)點：表達能力強，抽象性強，容易理解算法的描述方法——偽代碼1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}對C語言進行了如下簡化：局部變量可以不聲明；寫出子函數(shù)即可，子函數(shù)不用在主函數(shù)中調(diào)用，省略主函數(shù)；所有的包含函數(shù)（頭函數(shù).h）可以省略；交換兩個變量的語句可以簡寫為a←→b。1.4算法及算法分析通常用以下幾個標(biāo)準(zhǔn)來評價其優(yōu)劣：正確性：算法必須能正確解決問題。易讀性：算法應(yīng)當(dāng)便于閱讀和理解，以利于修改和改寫成程序。健壯性：當(dāng)輸入非法數(shù)據(jù)時，算法也能做出特殊處理，不會繼續(xù)操作或死機。高效性：算法的效率主要從時間和空間兩個方面考慮。解決一個問題的算法如果使用時間少和占用空間少，則是算法高效率的體現(xiàn)。1.4算法及算法分析算法分析度量算法效率的方法：事后統(tǒng)計：將算法實現(xiàn)，測算其時間和空間開銷。缺點：編寫程序?qū)崿F(xiàn)算法將花費較多的時間和精力；所得實驗結(jié)果依賴于計算機的軟硬件等環(huán)境因素。事前分析：即漸進復(fù)雜度，對算法所消耗資源的一種估算方法。算法分析算法分析（AlgorithmAnalysis）：對算法所需要的計算機資源——時間和空間進行估算。時間復(fù)雜度（TimeComplexity）：一個算法所進行的計算次數(shù)的多少。T(n)空間復(fù)雜度（SpaceComplexity）：指在算法執(zhí)行過程中，需要的輔助空間（臨時開辟的存儲空間）數(shù)量。S(n)1.4算法及算法分析算法的時間復(fù)雜度的事前分析一個高級語言程序在計算機上運行所

消耗的時間取決于：依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機器代碼質(zhì)量機器執(zhí)行指令速度1.4算法及算法分析同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，——使用絕對時間單位衡量算法效率不合適算法的時間復(fù)雜度事前分析算法的執(zhí)行時間＝每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間指令系統(tǒng)、編譯的代碼質(zhì)量單位時間每條語句執(zhí)行次數(shù)之和基本語句的執(zhí)行次數(shù)1.4算法及算法分析for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問題規(guī)模n基本語句1.4算法及算法分析一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)稱為語句頻度或時間頻度，它是問題規(guī)模n的某個函數(shù)，用T(n)表示。若有某個輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度（TimeComplexity）。n越大算法的執(zhí)行時間越長排序：n為記錄數(shù)矩陣：n為矩陣的階數(shù)多項式：n為多項式的項數(shù)集合：n為元素個數(shù)樹：n為樹的結(jié)點個數(shù)圖：n為圖的頂點數(shù)或邊數(shù)1.4算法及算法分析時間復(fù)雜度可以估算出當(dāng)問題規(guī)模變大時，算法運行時間增長的速度。估算算法運行時間的基本前提是：確定問題的“規(guī)模”和確定算法執(zhí)行“基本語句”的次數(shù)的關(guān)系。問題規(guī)模：一般是指輸入數(shù)據(jù)量的數(shù)目?；菊Z句：一般是指執(zhí)行次數(shù)最多的語句，比如，最內(nèi)層循環(huán)的循環(huán)體。1.4算法及算法分析求解算法時間復(fù)雜度的具體步驟是：找出算法中的基本語句算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。計算基本語句的執(zhí)行次數(shù)的數(shù)量級保留基本語句執(zhí)行次數(shù)的最高次冪，忽略所有低次冪和最高次冪的系數(shù)。用大O記號表示算法的時間復(fù)雜度稱為算法的漸進時間復(fù)雜度（時間復(fù)雜度）：T(n)=O(f(n))例：求下面程序段的時間復(fù)雜度。intx=0;for(i=0;i<n;i++)for(j=0;j<n;j++) x++;1.4算法及算法分析基本語句是x++，其執(zhí)行次數(shù)是n2，用大O記號表示為T(n)=O(n2)從好到壞表示時間復(fù)雜度的函數(shù)依次是：常量階O(1)；//算法執(zhí)行時間恒定，不隨問題規(guī)模的擴大而擴大對數(shù)階O(log2

n)；線性階O(n)；平方階O(n2)；多項式階O(nk)；指數(shù)階O(2n)

算法的時間復(fù)雜度越大，其執(zhí)行效率就越低。1.4算法及算法分析算法復(fù)雜度，舉例：①{x++;s=x+2;} ②for(k=1;k<=n;k++)s=k+2； ③for(k=1;k<=n;k++)for(j=1;j<=n;j++)s=k+j；1.4算法及算法分析時間復(fù)雜度為O(1)時間復(fù)雜度為O(n)時間復(fù)雜度為O(n2)1.4算法及算法分析最好情況、最壞情況、平均情況例：在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素（假設(shè)該數(shù)組中有且僅有一個元素值為k）。

intFind(intA[],intn){for(i=0;i<n;i++)if(A[i]==k)break;returni; }基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關(guān)？1.4算法及算法分析最好情況、最壞情況、平均情況結(jié)論：如果問題規(guī)模相同，時間代價與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。最好情況：出現(xiàn)概率較大時分析最差情況：實時系統(tǒng)平均情況：已知輸入數(shù)據(jù)是如何分布的，通常假設(shè)等概率分布空間復(fù)雜度關(guān)于算法的存儲空間需求，類似于算法的時間復(fù)雜度，我們采用空間復(fù)雜度作為算法所需存儲空間的量度，記作：S(n)=O(f(n))

其中，n為問題的規(guī)模，O表示數(shù)量級。算法占據(jù)的空間：算法本身要占據(jù)的空間，輸入/輸出，指令，常數(shù)，變量等；算法要使用的輔助空間1.4算法及算法分析空間復(fù)雜度1.4算法及算法分析【算法1】

for(i=0;i<n/2;i++){t=a[i];a[i]=a[n-i-1];a[n-i-1]=t;}

【算法2】

for(i=0;i<n;i++)b[i]=a[n-i-1];for(i=0;i<n;i++)a[i]=b[i];

例：將一維數(shù)組a中的n個數(shù)逆序存放到原數(shù)組中。S(n)=O(n)S(n)=O(1)原地工作1.5習(xí)題(1)從數(shù)據(jù)結(jié)構(gòu)S中找出滿足條件的結(jié)點在S中位置的運算是_____________型運算。(2)從數(shù)據(jù)結(jié)構(gòu)S中讀出結(jié)構(gòu)中指定位置上內(nèi)容運算是_____________型運算。(3)從數(shù)據(jù)結(jié)構(gòu)S中的某指定位置上增加一個新結(jié)點的運算是_____________型運算。(4)從數(shù)據(jù)結(jié)構(gòu)S中撤消結(jié)構(gòu)中指定位置上結(jié)點的運算是_____________型運算。(5)從數(shù)據(jù)結(jié)構(gòu)S中修改結(jié)構(gòu)中某指定結(jié)點內(nèi)容的運算是_____________型運算。1.5.1習(xí)題——填空題(1)數(shù)據(jù)表示是指數(shù)據(jù)_____________。

A.書寫在紙上 B.從機外轉(zhuǎn)為機內(nèi)

C.磁盤中的數(shù)據(jù) D.光盤中的數(shù)據(jù)(2)數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其內(nèi)_____________數(shù)據(jù)項。

A.只能包括一個 B.不包含

C.可以包含多個

D.必須包含多個(3)邏輯關(guān)系是指數(shù)據(jù)元素間的_____________。

A.類型 B.存儲方式

C.結(jié)構(gòu) D.數(shù)據(jù)項1.5.2習(xí)題——選擇題(4)邏輯結(jié)構(gòu)是_____________關(guān)系的整體。

A.數(shù)據(jù)元素之間邏輯 B.數(shù)據(jù)項之間邏輯

C.數(shù)據(jù)類型之間 D.存儲結(jié)構(gòu)之間(5)數(shù)據(jù)結(jié)構(gòu)有_____________種基本邏輯結(jié)構(gòu)。

A.1 B.2C.3 D.4(6)下列四種基本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是_______。

A.集合 B.線性結(jié)構(gòu)

C.樹形結(jié)構(gòu) D.圖狀結(jié)構(gòu)1.5.2習(xí)題——選擇題(7)一個存儲結(jié)點存放一個_____________。

A.數(shù)據(jù)項 B.數(shù)據(jù)元素

C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)類型(8)用類C語言描寫的算法_____________。

A.可以直接在計算機上運行

B.可以描述解題思想和基本框架

C.不能改寫成C語言程序

D.與C語言無關(guān)(9)算法能正確地實現(xiàn)預(yù)定功能的特性稱為___________。

A.正確性 B.易讀性

C.健壯 D.高效率1.5.2習(xí)題——選擇題(10)下列時間復(fù)雜度中最壞的是_____________。

A.O(1) B.O(n) C.O(log2n) D.O(n2)(11)下列時間復(fù)雜度中最好的是_____________。

A.O(1) B.O(n) C.O(log2n) D.O(n2)(12)下列算法的時間復(fù)雜度是_____________。

for(i=0;i<n;i++)for(j=0;j<n;