《數(shù)據(jù)結(jié)構(gòu)》課件-第1章 數(shù)據(jù)結(jié)構(gòu)與算法概述

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

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

緒論1.4算法及算法分析1.1

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

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

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

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

刪除、查找等

基本操作，

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

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

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

順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)集合線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)圖結(jié)構(gòu)非數(shù)值問(wèn)題數(shù)據(jù)表示加工型運(yùn)算引用型運(yùn)算1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（總結(jié)）1.4算法及算法分析1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用1.2本課程討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.5習(xí)題1.4算法及算法分析算法（Algorithm）：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。算法的五大特性：輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出?？尚行裕核惴枋龅牟僮骺梢酝ㄟ^(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。1.4算法及算法分析常用的描述方法有：用自然語(yǔ)言描述算法用流程圖描述算法用N-S流程圖描述算法用計(jì)算機(jī)語(yǔ)言描述算法用偽代碼描述算法歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(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；自然語(yǔ)言1.4算法及算法分析優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想

注意事項(xiàng)：避免寫(xiě)成自然段算法的描述方法——自然語(yǔ)言1.4算法及算法分析例：歐幾里德算法N開(kāi)始輸入m和n

r=m%nr=0m=n；n=r輸出n結(jié)束Y流程圖1.4算法及算法分析優(yōu)點(diǎn)：流程直觀易懂缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次算法的描述方法——流程圖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è)計(jì)語(yǔ)言1.4算法及算法分析優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，拘泥于具體細(xì)節(jié)而忽略算法邏輯的重要性，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫(xiě)成子函數(shù)算法的描述方法——程序設(shè)計(jì)語(yǔ)言1.4算法及算法分析例：歐幾里德算法

1.r=m%n;

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

2.1m=n;

2.2n=r;

2.3r=m%n;

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

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

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

算法的時(shí)間復(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算法及算法分析時(shí)間復(fù)雜度為O(1)時(shí)間復(fù)雜度為O(n)時(shí)間復(fù)雜度為O(n2)1.4算法及算法分析最好情況、最壞情況、平均情況例：在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為k）。

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

其中，n為問(wèn)題的規(guī)模，O表示數(shù)量級(jí)。算法占據(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個(gè)數(shù)逆序存放到原數(shù)組中。S(n)=O(n)S(n)=O(1)原地工作1.5習(xí)題(1)從數(shù)據(jù)結(jié)構(gòu)S中找出滿足條件的結(jié)點(diǎn)在S中位置的運(yùn)算是_____________型運(yùn)算。(2)從數(shù)據(jù)結(jié)構(gòu)S中讀出結(jié)構(gòu)中指定位置上內(nèi)容運(yùn)算是_____________型運(yùn)算。(3)從數(shù)據(jù)結(jié)構(gòu)S中的某指定位置上增加一個(gè)新結(jié)點(diǎn)的運(yùn)算是_____________型運(yùn)算。(4)從數(shù)據(jù)結(jié)構(gòu)S中撤消結(jié)構(gòu)中指定位置上結(jié)點(diǎn)的運(yùn)算是_____________型運(yùn)算。(5)從數(shù)據(jù)結(jié)構(gòu)S中修改結(jié)構(gòu)中某指定結(jié)點(diǎn)內(nèi)容的運(yùn)算是_____________型運(yùn)算。1.5.1習(xí)題——填空題(1)數(shù)據(jù)表示是指數(shù)據(jù)_____________。

A.書(shū)寫(xiě)在紙上 B.從機(jī)外轉(zhuǎn)為機(jī)內(nèi)

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

A.只能包括一個(gè) B.不包含

C.可以包含多個(gè)

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

A.類(lèi)型 B.存儲(chǔ)方式

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

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

C.數(shù)據(jù)類(lèi)型之間 D.存儲(chǔ)結(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.樹(shù)形結(jié)構(gòu) D.圖狀結(jié)構(gòu)1.5.2習(xí)題——選擇題(7)一個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)_____________。

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

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

A.可以直接在計(jì)算機(jī)上運(yùn)行

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

C.不能改寫(xiě)成C語(yǔ)言程序

D.與C語(yǔ)言無(wú)關(guān)(9)算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為_(kāi)__________。

A.正確性 B.易讀性

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

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

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

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