數(shù)據(jù)結(jié)構(gòu)課件

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

——C++語(yǔ)言描述

1第1章緒論數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用本課程討論的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念算法及算法分析本章的基本內(nèi)容是：1938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從31歲起，開(kāi)始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming，他計(jì)劃共寫(xiě)7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)——圖靈獎(jiǎng)，此時(shí)，他年僅36歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努思1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用程序設(shè)計(jì)的實(shí)質(zhì)是什么?數(shù)據(jù)表示：將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)（內(nèi)存）中數(shù)據(jù)處理：處理數(shù)據(jù)，設(shè)計(jì)方案（算法）數(shù)據(jù)結(jié)構(gòu)問(wèn)題起源于程序設(shè)計(jì)

1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用利用計(jì)算機(jī)求解問(wèn)題的一般過(guò)程?計(jì)算機(jī)不能分析問(wèn)題并產(chǎn)生問(wèn)題的解決方案，必須由人來(lái)分析問(wèn)題，確定問(wèn)題的解決方案，編寫(xiě)程序，然后讓計(jì)算機(jī)執(zhí)行程序最終獲得問(wèn)題的解。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.2本課程討論的主要內(nèi)容計(jì)算機(jī)求解問(wèn)題:

問(wèn)題→抽象出問(wèn)題的模型→求模型的解問(wèn)題——數(shù)值問(wèn)題、非數(shù)值問(wèn)題數(shù)值問(wèn)題→數(shù)學(xué)方程非數(shù)值問(wèn)題→數(shù)據(jù)結(jié)構(gòu)例1-2學(xué)籍管理問(wèn)題完成什么功能?各表項(xiàng)之間是什么關(guān)系？1.2本課程討論的主要內(nèi)容例1-3人——機(jī)對(duì)弈問(wèn)題如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？1.2本課程討論的主要內(nèi)容例1-4七巧板涂色問(wèn)題

如何表示區(qū)域之間的鄰接關(guān)系？1.2本課程討論的主要內(nèi)容本課程討論非數(shù)值問(wèn)題的數(shù)據(jù)組織和處理，主要內(nèi)容如下：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)，其核心是如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系；（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：如何將線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中，其核心是如何有效地存儲(chǔ)數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系；（3）算法：如何基于數(shù)據(jù)的某種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)插入、刪除、查找等基本操作，其核心是如何有效地處理數(shù)據(jù)；（4）常用數(shù)據(jù)處理技術(shù)：查找技術(shù)、排序技術(shù)、索引技術(shù)等。1.2本課程討論的主要內(nèi)容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ù)元素的不可分割的最小單位。數(shù)據(jù)結(jié)構(gòu)的基本概念學(xué)號(hào)姓名性別出生日期政治面貌0001陸宇男1986/09/02團(tuán)員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團(tuán)員數(shù)據(jù)項(xiàng)數(shù)據(jù)元素?cái)?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)一般不予考慮。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系數(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)系的整體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念關(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)系指的是什么？教學(xué)計(jì)劃編排問(wèn)題中，課程之間的邏輯關(guān)系指的是什么？數(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)系的整體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)在形式上可定義為一個(gè)二元組：Data_Structure=(D,R)其中D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的集合。數(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)系的整體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念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>}數(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ī)中的表示。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念內(nèi)存存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，在具體實(shí)現(xiàn)時(shí)依賴于計(jì)算機(jī)語(yǔ)言。數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”；1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”；⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系；1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(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)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(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)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲(chǔ)結(jié)構(gòu)：1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來(lái)表示?！璪atcateat…起始地址例：（bat,cat,eat）1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲(chǔ)結(jié)構(gòu)：1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來(lái)表示。2.鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來(lái)表示。例：（bat,cat,eat）1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念0200020803000325…………bat0200cat0325eat∧邏輯結(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ù)處理的效率往往是不同的。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型1.數(shù)據(jù)類型（DataType）：一組值的集合以及定義于這個(gè)值集上的一組操作的總稱。

例如：C++中的整型變量

2.抽象（Abstract）:抽出問(wèn)題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)。

例如：地圖、駕駛汽車3.抽象數(shù)據(jù)類型（AbstractDataType，ADT）:一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型在設(shè)計(jì)ADT時(shí)，把ADT的定義、設(shè)計(jì)和實(shí)現(xiàn)分開(kāi)來(lái)。定義部分只包含數(shù)據(jù)的邏輯結(jié)構(gòu)和所允許的操作集合，一方面，ADT的使用者依據(jù)這些定義來(lái)使用ADT，即通過(guò)操作集合對(duì)該ADT進(jìn)行操作；另一方面，ADT的實(shí)現(xiàn)者依據(jù)這些定義來(lái)完成該ADT各種操作的具體實(shí)現(xiàn)。ADT抽象數(shù)據(jù)類型名Data數(shù)據(jù)元素之間邏輯關(guān)系的定義Operation

操作1

前置條件：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài)

輸入：執(zhí)行此操作所需要的輸入

功能：該操作將完成的功能

輸出：執(zhí)行該操作后產(chǎn)生的輸出

后置條件：執(zhí)行該操作后數(shù)據(jù)的狀態(tài)操作2

…………操作n……endADT

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(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ù)表示算法的相關(guān)概念1.算法（Algorithm）:是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。2.

算法的五大特性：⑴

輸入：一個(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算法及算法分析1.4算法及算法分析“好”算法的衡量指標(biāo)正確性能解決問(wèn)題，獲得正確結(jié)果健壯性（魯棒性）簡(jiǎn)單性容易理解和實(shí)現(xiàn)抽象分級(jí)：如將算法分成多個(gè)模塊，每個(gè)模塊又可細(xì)分方便好用和可讀性強(qiáng)：人類短期記憶的對(duì)象數(shù)=7±2個(gè)高效性時(shí)間和空間效率

歐幾里德算法（有窮性、確定性、可行性）mnr算法的例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m

和n

的最大公約數(shù)1.4算法及算法分析算法的描述方法——自然語(yǔ)言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想

注意事項(xiàng)：避免寫(xiě)成自然段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)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次。可按抽象層次分級(jí)描述算法的描述方法——流程圖1.4算法及算法分析N開(kāi)始輸入m和n

r=m%nr=0m=n；n=r輸出n結(jié)束Y流程圖例：歐幾里德算法1.4算法及算法分析優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫(xiě)成子函數(shù)。按抽象層次分級(jí)——算法函數(shù)用下一層的子函數(shù)描述算法的描述方法——程序設(shè)計(jì)語(yǔ)言1.4算法及算法分析#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}程序設(shè)計(jì)語(yǔ)言例：歐幾里德算法1.4算法及算法分析偽代碼（Pseudocode）：介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解使用方法：7±2——抽象分級(jí)算法的描述方法——偽代碼1.4算法及算法分析1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;偽代碼上述偽代碼再具體一些，用C++的函數(shù)來(lái)描述。例：歐幾里德算法1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}1.4算法及算法分析對(duì)C++語(yǔ)言進(jìn)行了如下簡(jiǎn)化：⑴局部變量可以不聲明；⑵寫(xiě)出子函數(shù)即可，子函數(shù)不用在主函數(shù)中調(diào)用，省略主函數(shù)；⑶所有的包含函數(shù)（頭函數(shù).h）可以省略；⑷交換兩個(gè)變量的語(yǔ)句可以簡(jiǎn)寫(xiě)為a←→b。算法分析度量算法效率的方法：

事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開(kāi)銷。

缺點(diǎn)：⑴編寫(xiě)程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；⑵所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素。

事前分析：對(duì)算法所消耗資源的一種估算方法。1.4算法及算法分析1.4算法及算法分析方法在算法中的某些部位插裝時(shí)間函數(shù)time()測(cè)定算法在一組已給輸入下完成某一功能所花費(fèi)的時(shí)間事后統(tǒng)計(jì)測(cè)定順序搜索算法seqsearch的效率

行

int

seqsearch(

inta[],

constintn,

constintx)

//a[0],…,a[n-1]

1

{

2

inti=0;

3

while(i<n

&&a[i]!=x)

4

i++;

5

if(i==n)return-1;

6

return

i;

7

}1.4算法及算法分析事后統(tǒng)計(jì)的例——順序搜索(SequenialSearch)插裝time()的計(jì)時(shí)程序

void

TimeSearch()

{//在1到1000中搜索0

inta[1001],n[20];//n[i]存放要搜索的元素個(gè)數(shù)

for

(

intj=1;j<=1000;j++)

a[j]=j;//a[1]=1,a[2]=2,…

for(j=0;j<10;j++)

{

n[j]=10*j;//n[0]=0,n[1]=10,n[2]=20

n[j+10]=100*(j+1);

}//n[10]=100,n[11]=200,n[12]=300...cout

<<"ntime"<<

endl;

for

(j=0;j<20;j++){

long

start,stop;

time(start);

int

k=seqsearch(a,n[j],0);

time(stop);

longrunTime=stop-start;

cout

<<""<<n[j]<<""<< runTime<<

endl;

}

cout

<<"Timesareinhundredthsofa second."<<

endl;}程序測(cè)試結(jié)果輸出測(cè)定順序搜索算法的效率

——插裝時(shí)間函數(shù)time()后就行了？

改進(jìn)的計(jì)時(shí)程序void

TimeSearch()

{inta[1001],n[20];

constlongr[20]={300000,300000,200000,200000,100000,100000,100000,80000,80000,50000,50000,25000,15000,15000,10000,7500,7000,6000,5000,5000};

for(

intj=1;j<=1000;j++)

a[j]=j;

for(j=0;j<10;j++){

n[j]=10*j;n[j+10]=100*(j+1);

}cout<<"ntotalTimerunTime"<<

endl;for

(j=0;j<20;j++){

long

start,stop;

time(start);

//開(kāi)始計(jì)時(shí)

for(

longb=1;b<=r[j];b++)

intk=seqsearch(a,n[j],0

);

//執(zhí)行r[j]次

time(stop);

//停止計(jì)時(shí)

longtotalTime=stop-start;

float

runTime=

(float)(totalTime)/(float)(r[j]);

cout

<<""<<n[j]<<""<<totalTime<<""<<runTime<<

endl;

}}程序測(cè)試結(jié)果輸出算法分析算法分析（AlgorithmAnalysis）：對(duì)算法所需要的計(jì)算機(jī)資源——時(shí)間和空間進(jìn)行（事前）估算。時(shí)間復(fù)雜性（TimeComplexity）空間復(fù)雜性（SpaceComplexity）1.4算法及算法分析算法的時(shí)間復(fù)雜度分析1.4算法及算法分析算法分析算法的執(zhí)行時(shí)間＝每條語(yǔ)句執(zhí)行時(shí)間之和執(zhí)行次數(shù)×執(zhí)行一次的時(shí)間指令系統(tǒng)、編譯的代碼質(zhì)量單位時(shí)間每條語(yǔ)句執(zhí)行次數(shù)之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語(yǔ)句的執(zhí)行次數(shù)問(wèn)題規(guī)模：輸入量的多少?；菊Z(yǔ)句：是執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成正比的操作指令。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問(wèn)題規(guī)模：n基本語(yǔ)句：x++1.4算法及算法分析算法分析空間復(fù)雜度

當(dāng)問(wèn)題規(guī)模由1增至n時(shí)，算法所需空間也由S(1)增至S(n)（按某個(gè)單位計(jì)算），則S(n)稱為此算法的空間復(fù)雜度時(shí)間復(fù)雜度

當(dāng)問(wèn)題規(guī)模由1增至n時(shí)，算法所耗時(shí)間也由T(1)增至T(n)（按某個(gè)單位計(jì)算），則T(n)稱為此算法的時(shí)間復(fù)雜度問(wèn)題規(guī)模：輸入量的多少。1.4算法及算法分析算法分析空間復(fù)雜度估算存儲(chǔ)空間的固定部分

程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分(如數(shù)組元素、結(jié)構(gòu)成分、對(duì)象的數(shù)據(jù)成員等)變量所占的空間可變部分

尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用的空間、通過(guò)new和delete命令動(dòng)態(tài)使用的空間例：floatabc(floata,floatb,floatc){returna+b+b*c+(a+b-c)/(a+b)}

//占用的空間數(shù)為常數(shù)floatsum(floata[],constintn){floats=0.0;for(inti=0;i<n;i++)s+=a[i];returns;}

//占用的空間數(shù)為常數(shù);數(shù)組a[]在此函數(shù)中僅占用一個(gè)空間(首地址)floatrsum(floata[],constintn){if(n<=0)return0;elsereturnrsum(a,n-1)+a[n-1];}

//占用的空間數(shù)為4(n+1);此為遞歸函數(shù)，深度=n+1，每層保留兩個(gè)參數(shù)、函數(shù)返回值和返回地址共四個(gè)存儲(chǔ)單位時(shí)間復(fù)雜度估算算法指令的執(zhí)行時(shí)間程序步語(yǔ)法上或語(yǔ)義上有意義的一段指令序列執(zhí)行時(shí)間與實(shí)例特性無(wú)關(guān)例如：

注釋：程序步數(shù)為0

聲明語(yǔ)句：程序步數(shù)為0

表達(dá)式：程序步數(shù)為1程序步確定方法

1）插入計(jì)數(shù)全局變量count（稱為插樁）

2）建表，列出每個(gè)語(yǔ)句的程序步

例以迭代方式求累加和的函數(shù)行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

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

4s+=a[i];

5

returns;

6

} 在求累加和程序中加入count語(yǔ)句

floatsum(

floata[],constintn){floats=0.0;count++; //count統(tǒng)計(jì)執(zhí)行語(yǔ)句條數(shù)

for(

inti=0;i<n;i++)

{

count++; //針對(duì)for語(yǔ)句

s+=a[i]; count++;//針對(duì)賦值語(yǔ)句

}

count++;//針對(duì)for的最后一次

count++;

//針對(duì)return語(yǔ)句

returns;}

//執(zhí)行結(jié)束得程序步數(shù)count=2*n+3注意：例如：賦值語(yǔ)句

x=sum(R,n);

本身的程序步數(shù)為1；

一次執(zhí)行對(duì)函數(shù)

sum(R,n)的調(diào)用需要的程序步數(shù)為2*n+3；

一次執(zhí)行的程序步數(shù)為 1+2*n+3=2*n+4■不同語(yǔ)句的執(zhí)行時(shí)間不同，但是如果它們的執(zhí)行時(shí)間差一個(gè)與實(shí)例特性無(wú)關(guān)(包括與問(wèn)題規(guī)模無(wú)關(guān))的常數(shù)時(shí)，仍將它們看成一樣的程序步。由此，最終結(jié)果也差常數(shù)倍。

■一個(gè)語(yǔ)句本身的程序步數(shù)可能不等于該語(yǔ)句一次執(zhí)行所具有的程序步數(shù)——可能與問(wèn)題規(guī)模有關(guān)。程序步數(shù)計(jì)算工作表格時(shí)間復(fù)雜度估算有時(shí)我們僅估算算法中某一種運(yùn)算(操作)的數(shù)目：加減法數(shù)目，乘除法數(shù)目數(shù)據(jù)交換或移動(dòng)的次數(shù)定義

若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有|T(n)|≤c×f(n)，則稱T(n)=O(f(n))。n0問(wèn)題規(guī)模n執(zhí)行次數(shù)n0之前的情況無(wú)關(guān)緊要T(n)c×f(n)當(dāng)問(wèn)題規(guī)模充分大時(shí)在漸近意義下的階。1.4算法及算法分析算法分析——大O符號(hào)（大O表示法

）加法規(guī)則

針對(duì)并列程序段

T(n,m)=T1(n)+T2(m)=O(f(n))+O(g(m)) =O(max(f(n),g(m)))

=O(f(n)+g(m))

乘法規(guī)則

針對(duì)嵌套程序段

T(n,m)=T1(n)*T2(m)=O(f(n))*O(g(m))

=O(f(n)*g(m))漸進(jìn)的空間復(fù)雜度(記號(hào)同時(shí)間)

S(n)=O(f(n))

算法分析——大O符號(hào)（大O表示法

）運(yùn)算規(guī)則1.4算法及算法分析定理：若A(n)=amnm+am-1nm-1++a1n+a0是一個(gè)m次多項(xiàng)式，且m是與n無(wú)關(guān)的常數(shù)，則A(n)=O(nm)。說(shuō)明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)。1.4算法及算法分析算法分析——大O符號(hào)例1-5

++x;例1-6

for(i=1;i<=n;++i)++x;例1-7for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;

例1-8for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;1.4算法及算法分析算法分析例1-9for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}例1-10for(i=1;i<=n;i=2*i) ++x;Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)1.4算法及算法分析算法分析各增長(zhǎng)率函數(shù)值的比較c<log2n<n<nlog2n<n2<n3<2n<3n<n!運(yùn)行時(shí)間估計(jì)的例?假設(shè)CPU每秒處理106個(gè)指令，對(duì)于輸入規(guī)模為=108的問(wèn)題，時(shí)間代價(jià)為T(mén)(n)=2n2的算法要運(yùn)行多長(zhǎng)時(shí)間？–操作次數(shù)為

T(n)=T(108)=2×(108)2=2×1016–運(yùn)行時(shí)間為

2×1016/106=2×1010秒–每天有86,400秒，因此需要231,480天(634年)運(yùn)行時(shí)間估計(jì)的例（續(xù)）假設(shè)CPU每秒處理106個(gè)指令，對(duì)于輸入規(guī)模為n=108的問(wèn)題，時(shí)間代價(jià)為T(mén)(n)=nlogn的算法要運(yùn)行多長(zhǎng)時(shí)間？–操作次數(shù)為T(mén)(n)=T(108)=108×log108=2.66×109–運(yùn)行時(shí)間為2.66×109/106=2.66×103秒，即44.33分規(guī)定時(shí)間內(nèi)能解決的問(wèn)題規(guī)模.假設(shè)CPU每秒處理106個(gè)指令，則每小時(shí)能夠解決的最大問(wèn)題規(guī)模T(n)/106≤3600T(n)=2n2，即2n2≤3600×106n≤42,426T(n)=nlogn，即nlogn≤3600×106n≤133,000,000加快硬件速度設(shè)CPU每秒處理108個(gè)指令(快100倍)處理時(shí)間都降為原來(lái)的1/100解決問(wèn)題的規(guī)模T(n)=2n2，規(guī)模增加10倍T(n)=nlogn，規(guī)模增加75倍最好情況、最壞情況、平均情況例：在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為k）。

intFind(intA[],intn)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }1.4算法及算法分析基本語(yǔ)句的執(zhí)行次數(shù)是否只和問(wèn)題規(guī)模有關(guān)？——考慮輸入不同的情況！最好情況：出現(xiàn)概率較大時(shí)分析最差情況：實(shí)時(shí)系統(tǒng)平均情況：已知輸入數(shù)據(jù)是如何分布的，通常假設(shè)等概率分布結(jié)論：如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。1.4算法及算法分析最好情況、最壞情況、平均情況2.1線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？2.1線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么？現(xiàn)實(shí)生活中，許多問(wèn)題抽象出的數(shù)據(jù)模型是線性表，如何存儲(chǔ)這種線性結(jié)構(gòu)并實(shí)現(xiàn)插入、刪除、查找等基本操作呢？線性表的定義線性表：簡(jiǎn)稱表，是n（n≥0）個(gè)具有相同類型的數(shù)據(jù)元素的有限序列。線性表的長(zhǎng)度：線性表中數(shù)據(jù)元素的個(gè)數(shù)。空表：長(zhǎng)度等于零的線性表，記為：L=()。非空表記為：L＝（a1,a2,…,ai-1,ai,…,an)2.1線性表的邏輯結(jié)構(gòu)其中，ai（1≤i≤n）稱為數(shù)據(jù)元素；下角標(biāo)i表示該元素在線性表中的位置或序號(hào)。a1a3a4ana22.1線性表的邏輯結(jié)構(gòu)線性表的特性1.有限性：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1,ai)，即ai-1是ai的前驅(qū)，ai是ai-1的后繼；a1無(wú)前驅(qū)，an無(wú)后繼，其它每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。

線性表的抽象數(shù)據(jù)類型定義ADTListData

線性表中的數(shù)據(jù)元素具有相同類型，相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitList

前置條件：表不存在輸入：無(wú)

功能：表的初始化輸出：無(wú)

后置條件：建一個(gè)空表2.1線性表的邏輯結(jié)構(gòu)DestroyList

前置條件：表已存在

輸入：無(wú)

功能：銷毀表

輸出：無(wú)

后置條件：釋放表所占用的存儲(chǔ)空間Length

前置條件：表已存在

輸入：無(wú)

功能：求表的長(zhǎng)度

輸出：表中數(shù)據(jù)元素的個(gè)數(shù)

后置條件：表不變2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Get

前置條件：表已存在

輸入：元素的序號(hào)i

功能：在表中取序號(hào)為i的數(shù)據(jù)元素

輸出：若i合法，返回序號(hào)為i的元素值，否則拋出異常

后置條件：表不變Locate

前置條件：表已存在

輸入：數(shù)據(jù)元素x

功能：在線性表中查找值等于x的元素

輸出：若查找成功，返回x在表中的序號(hào)，否則返回0

后置條件：表不變2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義Insert

前置條件：表已存在

輸入：插入i；待插x

功能：在表的第i個(gè)位置處插入一個(gè)新元素x

輸出：若插入不成功，拋出異常

后置條件：若插入成功，表中增加一個(gè)新元素Delete

前置條件：表已存在

輸入：刪除位置i

功能：刪除表中的第i個(gè)元素

輸出：若刪除成功，返回被刪元素，否則拋出異常

后置條件：若刪除成功，表中減少一個(gè)元素2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Empty

前置條件：表已存在

輸入：無(wú)

功能：判斷表是否為空

輸出：若是空表，返回1，否則返回0

后置條件：表不變ADT進(jìn)一步說(shuō)明:（1）線性表的基本操作根據(jù)實(shí)際應(yīng)用是而定；（2）復(fù)雜的操作可以通過(guò)基本操作的組合來(lái)實(shí)現(xiàn)；（3）對(duì)不同的應(yīng)用，操作的接口可能不同。2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表——線性表的順序存儲(chǔ)結(jié)構(gòu)例：（34,23,67,43）342367434存儲(chǔ)要點(diǎn)用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表——線性表的順序存儲(chǔ)結(jié)構(gòu)例：（34,23,67,43）34236743存儲(chǔ)空間的起始位置4用什么屬性來(lái)描述順序表？順序表的容量（最大長(zhǎng)度）順序表的當(dāng)前長(zhǎng)度2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表——線性表的順序存儲(chǔ)結(jié)構(gòu)例：（34,23,67,43）342367434如何實(shí)現(xiàn)順序表的內(nèi)存分配？順序表一維數(shù)組0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長(zhǎng)度2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲(chǔ)：數(shù)組的長(zhǎng)度Max線性表的長(zhǎng)度Length數(shù)組的長(zhǎng)度大于等于當(dāng)前線性表的長(zhǎng)度如何求得任意元素的存儲(chǔ)地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長(zhǎng)度2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲(chǔ)：cLoc(ai)Loc(a1)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長(zhǎng)度Loc(ai)=Loc(a1)+(i-1)×c隨機(jī)存?。涸贠(1)時(shí)間內(nèi)存取數(shù)據(jù)元素2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲(chǔ)：cLoc(ai)Loc(a1)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示；存取結(jié)構(gòu)是在一個(gè)數(shù)據(jù)結(jié)構(gòu)上對(duì)訪問(wèn)操作的時(shí)間性能的一種描述。存儲(chǔ)結(jié)構(gòu)和存取結(jié)構(gòu)“順序表是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)”的含義為：在順序表這種存儲(chǔ)結(jié)構(gòu)上進(jìn)行的訪問(wèn)，其時(shí)間性能為O(1)。順序表類的聲明constintMaxSize=100;template<classDataType>//模板類classSeqList{public:SeqList();//構(gòu)造函數(shù)

SeqList(DataTypea[],intn);~SeqList();//析構(gòu)函數(shù)intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:DataTypedata[MaxSize];intlength;};2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)——無(wú)參構(gòu)造函數(shù)操作接口：SeqList()

算法描述：SeqList<DataType>

::SeqList(){length=0;}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

datalength0順序表的實(shí)現(xiàn)——有參構(gòu)造函數(shù)操作接口：SeqList(DataTypea[],intn)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表

數(shù)組a351224334253512243342順序表的實(shí)現(xiàn)——有參構(gòu)造函數(shù)template<classDataType>SeqList<DataType>

::SeqList(DataTypea[],intn){if(n>MaxSize)throw"參數(shù)非法";

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

data[i]=a[i];length=n;}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)算法描述：順序表的實(shí)現(xiàn)——插入操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x

,ai,…,an)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化33順序表的實(shí)現(xiàn)——插入例：（35，12，24，42），在i=2的位置上插入33。表滿：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序號(hào)）2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)435122442a1a2a3a401234422412335什么時(shí)候不能插入？注意邊界條件算法描述——偽代碼1.如果表滿了，則拋出上溢異常;2.如果元素的插入位置不合理，則拋出位置異常;3.將最后一個(gè)元素至第i個(gè)元素分別向后移動(dòng)一個(gè)位置；4.將元素x填入位置i處；5.表長(zhǎng)加1；2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)——插入順序表的實(shí)現(xiàn)——插入template<classDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length>=MaxSize)throw"上溢";

if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];data[i-1]=x;length++;}算法描述——C++描述2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)基本語(yǔ)句？順序表的實(shí)現(xiàn)——插入最好情況（i=n+1）：基本語(yǔ)句執(zhí)行0次，時(shí)間復(fù)雜度為O(1)。最壞情況（i=1）：基本語(yǔ)句執(zhí)行n+1次，時(shí)間復(fù)雜度為O(n)。平均情況（1≤i≤n+1）：時(shí)間復(fù)雜度為O(n)。時(shí)間性能分析2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)操作接口：DataTypeDelete(inti)刪除前：(a1,…,ai-1,ai,ai+1,…,an)刪除后：(a1,…,ai-1,ai+1,…,an)

順序表的實(shí)現(xiàn)——?jiǎng)h除2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出偽代碼和C++描述的算法；3.分析時(shí)間復(fù)雜度。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)——?jiǎng)h除535a1a2a3a401234422412334a5122442順序表的實(shí)現(xiàn)——按位查找操作接口：DataTypeGet(inti)

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑

n算法描述：template<classDataType>DataTypeSeqList<DataType>

::Get(inti){

if(i>=1&&i<=length)returndata[i-1];}時(shí)間復(fù)雜度？順序表的實(shí)現(xiàn)——按值查找操作接口：intLocate(DataTypex)

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值為12的元素，返回在表中的序號(hào)。iii注意序號(hào)和下標(biāo)之間的關(guān)系template<classDataType>intSeqList<DataType>

::Locate(DataTypex){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序表的實(shí)現(xiàn)——按值查找算法描述：時(shí)間復(fù)雜度？順序表類的聲明constintMaxSize=100;template<classDataType>//模板類classSeqList{public:SeqList(intmaxlen=MaxSize);//構(gòu)造函數(shù)

SeqList(DataTypea[],intn);~SeqList();//析構(gòu)函數(shù)intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:

DataType*data;intlength;intmaxsize;

booladdSpace(intsize=10);};2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)(動(dòng)態(tài)數(shù)組)順序表的實(shí)現(xiàn)——構(gòu)造函數(shù)操作接口：SeqList(int

maxlen=MaxSize)

算法描述：SeqList<DataType>

::SeqList(int

maxlen):length(0),maxsize(maxlen){if(maxlen<=0)throw“參數(shù)非法”; data=new

DataType[maxlen];}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)(動(dòng)態(tài)數(shù)組)

datalength0順序表的實(shí)現(xiàn)——分配空間操作接口：booladdSpace(int

size=10)

算法描述：boolSeqList<DataType>

::addSpace(int

size){if(size<=0)returnfalse;tmpdata=data;maxlen+=size;data=new

DataType[maxlen];for(i=0;i<length;i++)data[i]=tmpdata[i];delete[]tmpdata;returntrue;}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)(動(dòng)態(tài)數(shù)組)順序表的優(yōu)缺點(diǎn)順序表的優(yōu)點(diǎn)：⑴無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；⑵隨機(jī)存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑亍?/p>

順序表的缺點(diǎn)：⑴插入和刪除操作需要移動(dòng)大量元素；⑵表的容量難以確定，表的容量難以擴(kuò)充；⑶造成存儲(chǔ)空間的碎片。

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表：線性表的鏈接存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)思想：用一組任意的存儲(chǔ)單元存放線性表的元素。2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表靜態(tài)存儲(chǔ)分配順序表事先確定容量鏈表動(dòng)態(tài)存儲(chǔ)分配運(yùn)行時(shí)分配空間連續(xù)不連續(xù)零散分布0200020803000325…………存儲(chǔ)特點(diǎn)：邏輯次序和物理次序不一定相同。

2.元素之間的邏輯關(guān)系用指針表示。2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)例：(a1,a2

,a3,a4)的存儲(chǔ)示意圖單鏈表a10200a20325a30300a4∧2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧結(jié)點(diǎn)數(shù)據(jù)域指針域單鏈表是由若干結(jié)點(diǎn)構(gòu)成的；單鏈表的結(jié)點(diǎn)只有一個(gè)指針域。data：存儲(chǔ)數(shù)據(jù)元素next：存儲(chǔ)指向后繼結(jié)點(diǎn)的地址datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：數(shù)據(jù)域指針域template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：如何申請(qǐng)一個(gè)結(jié)點(diǎn)？s=newNode<int>;template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：……sNodes=newNode<int>;2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表datanext……sNode如何引用數(shù)據(jù)元素？s->data;*s.data;data如何引用指針域？nexts->next;2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表重點(diǎn)在數(shù)據(jù)元素之間的邏輯關(guān)系的表示，所以，將實(shí)際存儲(chǔ)地址抽象。什么是存儲(chǔ)結(jié)構(gòu)？2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表頭指針：指向第一個(gè)結(jié)點(diǎn)的地址。尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭铡?.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不統(tǒng)一，缺點(diǎn)？如何將空表與非空表統(tǒng)一？對(duì)第一個(gè)結(jié)點(diǎn)的操作與對(duì)其他結(jié)點(diǎn)的操作，使用語(yǔ)句可一致？頭結(jié)點(diǎn)：在單鏈表的第以一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)，以便空表和非空表處理統(tǒng)一，并且可統(tǒng)一對(duì)任意位置的結(jié)點(diǎn)的操作實(shí)現(xiàn)。

2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表非空表firsta1a2an∧空表first∧template<classDataType>classLinkList{public:LinkList()；LinkList(DataTypea[],intn);~LinkList();intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);voidPrintList();private:Node<DataType>*first;};單鏈表類的聲明2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)——遍歷操作操作接口：

voidPrintList();核心操作（關(guān)鍵操作）：工作指針后移。從頭結(jié)點(diǎn)（或開(kāi)始結(jié)點(diǎn)）出發(fā)，通過(guò)工作指針的反復(fù)后移而將整個(gè)單鏈表“審視”一遍的方法稱為掃描（或遍歷）。2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)firsta1pa2pan∧aippp單鏈表的實(shí)現(xiàn)——遍歷操作操作接口：

voidPrintList();2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template<classDataType>voidLinkList<DataType>::PrintList(){p=first->next;while(p!=NULL){cout<<p->data;p=p->next;}}p++能否完成指針后移？a1a2pp++p->next單鏈表的實(shí)現(xiàn)——按位查找操作接口：

DataTypeGet(inti);2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)firsta1a2an∧aipp查找失敗1.工作指針p初始化;累加器count初始化;2.重復(fù)執(zhí)行下述操作，直到p為空：

2.1工作指針p后移;2.2count++;3.返回p->data的值；pcount=1pcount=2p查找成功count=itemplate<classDataType>DataTypeLinkList<DataType>::Get(inti){p=first->next;count=1;while(p!=NULL){if(count==i)returnp->data;p=p->next;count++;}throw“參數(shù)錯(cuò)誤”;Node<DataType>tmp;returntmp.data;}2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)——按位查找算法描述——C++描述template<classDataType>intLinkList<DataType>::Length(){p=first->next;count=0;while(p!=NULL){p=p->next;count++;}returncount;//注意count的初始化和返回值之間的關(guān)系}2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)——按位查找——計(jì)算表長(zhǎng)算法描述——C++描述template<classDataType>intLinkList<DataType>::Locate(DataTypex){p=first->next;count=1;

while(p!=NULL){if(p->data==x)returncount;//查找成功，返回序號(hào)p=p->next;count++;}return0;//退出循環(huán)表明查找失敗}2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)——按值查找算法描述——C++描述單鏈表的實(shí)現(xiàn)———插入操作接口：

voidInsert(inti,DataTypex);

2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1、x和ai之間邏輯關(guān)系的變化？pxsfirsta1ai-1an∧ai算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;注意分析邊界情況——表頭、表尾。

單鏈表的實(shí)現(xiàn)———插入2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)firsta1an∧aipxs算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;pxs∧由于單鏈表帶頭結(jié)點(diǎn)，表頭、表中、表尾三種情況的操作語(yǔ)句一致。

算法描述——偽代碼

1.工作指針p初始化；

2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；

3.若查找不成功，則插入位置不合理，拋出插入位置異常；否則，3.1生成一個(gè)元素值為x的新結(jié)點(diǎn)s；

3.2將新結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后；2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)———插入

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;//工作指針p應(yīng)指向頭結(jié)點(diǎn)

while(p!=NULL&&count<i-1)//查找第i–1個(gè)結(jié)點(diǎn)

{p=p->next;

count++;}if(p==NULL)throw"位置";//沒(méi)有找到第i–1個(gè)結(jié)點(diǎn)

else{s=newNode;s->data=x;//申請(qǐng)一個(gè)結(jié)點(diǎn)ss->next=p->next;p->next=s;//結(jié)點(diǎn)s插入結(jié)點(diǎn)p之后

}}2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)單鏈表的實(shí)現(xiàn)———插入基本語(yǔ)句？時(shí)間復(fù)雜度？單鏈表的實(shí)現(xiàn)———無(wú)參構(gòu)造函數(shù)操作接口：LinkList()構(gòu)造空表，即僅構(gòu)造頭結(jié)點(diǎn)。算法描述：first=newNode<DataType>;first->next=NULL;2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)初始化first∧template<classDataType>LinkList<DataType>::LinkList(){ first=newNode<DataType>; first->next=NULL;}單鏈表的實(shí)現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面。算法描述：first=newNode<DataType>;first->next=NULL;2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)組a3512243342初始化first∧單鏈表的實(shí)現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面。2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)組a3512243342算法描述：s=newNode<DataType>;s->data=a[0];s->next=first->next;first->next=s;插入第一個(gè)元素結(jié)點(diǎn)first∧35s∧單鏈表的實(shí)現(xiàn)———構(gòu)造函數(shù)操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結(jié)點(diǎn)插在頭結(jié)點(diǎn)的后面。2.3線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)數(shù)組a3512243342算法描述：s=newNode<DataType>;s->d