數(shù)據(jù)結(jié)構(gòu)(C語言版)：第1章 緒論

數(shù)據(jù)結(jié)構(gòu)(C語言版)

DataStructure

學(xué)分：3

總學(xué)時(shí)：教材：《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏、吳偉民-----清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版）嚴(yán)蔚敏、吳偉民-----清華大學(xué)出版社編程基礎(chǔ)考研課程計(jì)算機(jī)等級考試課程程序員考試課程課程重要性

本課程的體系結(jié)構(gòu)第一章緒論

介紹數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念。第二章~第七章基本數(shù)據(jù)結(jié)構(gòu)

從抽象數(shù)據(jù)類型的角度，

分別討論線性表、棧和隊(duì)列、串、數(shù)組和廣義表、

樹、圖等基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用。第八章動態(tài)存儲管理

介紹操作系統(tǒng)和編譯程序中涉及的

動態(tài)存儲管理的基本技術(shù)。第九章~第十一章查找和排序

介紹了各種實(shí)現(xiàn)方法，

并著重從時(shí)間上進(jìn)行定性或定量的分析和比較。第十二章文件結(jié)構(gòu)

介紹數(shù)據(jù)庫系統(tǒng)中組織文件的常用方法。內(nèi)容安排章內(nèi)容學(xué)時(shí)章內(nèi)容學(xué)時(shí)1序論27圖82線性表88動態(tài)存儲管理略3棧和隊(duì)列89查找84串810內(nèi)部排序85數(shù)組和廣義表811外部排序略6樹和二叉樹812文件略緒論1、數(shù)據(jù)結(jié)構(gòu)基本概念

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)

和抽象數(shù)據(jù)類型等概念。

2、算法及算法分析

性能分析與度量：算法的性能標(biāo)準(zhǔn)；

空間復(fù)雜度度量；

時(shí)間復(fù)雜度度量。教學(xué)內(nèi)容占據(jù)了當(dāng)今計(jì)算機(jī)應(yīng)用的絕大多數(shù)。數(shù)值計(jì)算：加工處理的對象——純粹的數(shù)值。非數(shù)值計(jì)算計(jì)算機(jī)應(yīng)用工業(yè)檢測過程控制管理系統(tǒng)文字處理……加工處理的對象字符表格圖象聲音……具有一定的結(jié)構(gòu)

邏輯結(jié)構(gòu)

存儲結(jié)構(gòu)

算法有效地組織計(jì)算機(jī)存儲研究對象的特性及其相互之間的關(guān)系有效地實(shí)現(xiàn)對象之間的“運(yùn)算”關(guān)系

《數(shù)據(jù)結(jié)構(gòu)》的研究內(nèi)容

為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？1.1什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)學(xué)模型計(jì)算機(jī)解題步驟設(shè)計(jì)算法編程、調(diào)試、運(yùn)行分析問題提取操作對象

找出操作對象之間的關(guān)系

用數(shù)學(xué)語言描述

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

例1：計(jì)算機(jī)電話號碼查詢系統(tǒng)。

法學(xué)系8523101國貿(mào)系8522105工商系8523150計(jì)算機(jī)系8521088會計(jì)系8525789統(tǒng)計(jì)系8528136

8521088計(jì)算機(jī)系8522105國貿(mào)系8523101法學(xué)系8523150工商系8525789會計(jì)系8528136統(tǒng)計(jì)系

算法：查詢、插入、修改、刪除……

線性結(jié)構(gòu)線性表操作對象：{單位名，號碼}關(guān)系：線性關(guān)系例2：計(jì)算機(jī)和人對弈問題。

非線性結(jié)構(gòu)樹操作對象：格局（棋盤狀態(tài)）關(guān)系：非線性關(guān)系（由比賽規(guī)則決定）例3、多叉路口交通燈的管理問題。

在多叉路口需設(shè)幾種顏色的交通燈才能使車輛相互之間不碰

撞，又能達(dá)到最大流通量。ABCDE非線性結(jié)構(gòu)圖操作對象：通路關(guān)系：非線性關(guān)系（由問題的要求決定）ABACADBADCEDBCBDDADBEAEBEC

程序設(shè)計(jì)的實(shí)質(zhì)是對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法。

瑞士著名的計(jì)算機(jī)科學(xué)家、Pascal語言發(fā)明者沃思(N.Wirth)教授提出：《數(shù)據(jù)結(jié)構(gòu)》是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。

數(shù)據(jù)結(jié)構(gòu)是問題的數(shù)學(xué)模型。

算法（解決問題的方法）處理的對象就是數(shù)據(jù)。算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。

要想有效地使用計(jì)算機(jī)，就必須學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的發(fā)展史“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國外是從1968

年才開始設(shè)立的，由美國唐·歐·克努特教授開創(chuàng)其最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。

我國于1978

年開設(shè)本課程。數(shù)據(jù)結(jié)構(gòu)的地位1、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。2、數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的

一門核心課程。3、數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)

值計(jì)算的程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、

操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和應(yīng)用程序的重要基

礎(chǔ)。是對信息的一種符號表示——人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實(shí)世界的事物及其活動所做的描述。數(shù)據(jù)(Data)

1.2基本概念和術(shù)語在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱——包括數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)

(包括文字、表格、圖象、聲音等，都稱為數(shù)據(jù))。它是計(jì)算機(jī)操作對象的總稱。數(shù)據(jù)是個(gè)集合，可用集合的表示方法來寫：

數(shù)據(jù)={x|x是計(jì)算機(jī)操作的對象}數(shù)據(jù)元素(DataElement)：(也稱結(jié)點(diǎn))

是數(shù)據(jù)(集合)中的一個(gè)“個(gè)體”，是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)(dataitem)：是數(shù)據(jù)結(jié)構(gòu)中討論的“最小單位”。兩類數(shù)據(jù)元素不可分割的“原子”型數(shù)據(jù)元素如：整數(shù)“5”，字符“N”等；由多個(gè)款項(xiàng)構(gòu)成的數(shù)據(jù)元素，其中每個(gè)款項(xiàng)被稱為一個(gè)“數(shù)據(jù)項(xiàng)”。如描述一個(gè)學(xué)生的信息的數(shù)據(jù)元素可由3個(gè)數(shù)據(jù)項(xiàng)組成。其中的出生日期又可以由三個(gè)數(shù)據(jù)項(xiàng)：“年”、“月”和“日”組成，則稱“出生日期”為“組合項(xiàng)”，而其它不可分割的數(shù)據(jù)項(xiàng)為“原子項(xiàng)”。

姓名出生日期成績年月日數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。例：整數(shù)數(shù)據(jù)對象的集合可表示為N={0,±1,±2,…}，

字母字符數(shù)據(jù)對象的集合可表示為C={‘A’,‘B’,…,‘Z’}。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。結(jié)構(gòu)：數(shù)據(jù)元素之間的相互關(guān)系。

<x,y>意為x

和y

之間存在“x領(lǐng)先于y”的次序關(guān)系。長整數(shù)“321465879”可用a1=321，a2=465和a3=879的集合表示，且三者之間的次序關(guān)系必須是，a1

表示最高3位，a3

表示最低的3位，a2

則是中間3位。例：假設(shè)以三個(gè)3位的十進(jìn)制數(shù)表示一個(gè)含9位十進(jìn)制數(shù)的“長整數(shù)”，則可用如下描述的數(shù)學(xué)模型表示：它是一個(gè)

含三個(gè)數(shù)據(jù)元素{a1,a2,a3}的集合，且在集合上存在下

列次序關(guān)系：{<a1,a2>，<a2,a3>}。四類基本結(jié)構(gòu)集合：數(shù)據(jù)元素除了同屬于一種類型

外，別無其它關(guān)系。線性結(jié)構(gòu)：一對一。樹型結(jié)構(gòu)：一對多。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：多對多。數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：

Data-Structure=(D,S)其中：D

是數(shù)據(jù)元素的有限集，

S

是D

上關(guān)系的有限集。

例

1-4：復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)：Complex=(C,R)其中：C

是含兩個(gè)實(shí)數(shù)的集合{c1,c2}，分別表示復(fù)數(shù)的實(shí)部和虛部。R={P}，P

是定義在集合C上的一種關(guān)系{<c1,c2>}。

例1-5：科研課題小組的數(shù)據(jù)結(jié)構(gòu)：

Group=(D,R)

其中：D={T,G1,…,Gn,S11,…,Snm}1n3,1m2,

R={R1,R2}，R1={<T,Gi>|1in,1n3}R2={<Gi,

Sij>|1in,1jm,1n3,1m2}操作對象的數(shù)學(xué)模型邏輯結(jié)構(gòu)(logicalstructure)

指數(shù)據(jù)元素之間抽象化的相互關(guān)系。獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的。

TG1G2G3S11S12S21S22S31S32物理結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲形式(映象)。存儲結(jié)構(gòu)(StorageStructure)

必須依賴于計(jì)算機(jī)。位串：n

位的組合。位(bit)：二進(jìn)制數(shù)的一位。計(jì)算機(jī)中表示信息的最小單位。元素(element)：計(jì)算機(jī)中用來存儲數(shù)據(jù)元素的一個(gè)位串，結(jié)點(diǎn)(node)

即數(shù)據(jù)元素在計(jì)算機(jī)中的映象。數(shù)據(jù)域(datafield)：當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串。例：十進(jìn)制數(shù)值321可用位串101000001表示，

字母“A”可用位串01000001表示。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示方法順序映象非順序映象——順序存儲結(jié)構(gòu)——鏈?zhǔn)酱鎯Y(jié)構(gòu)用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針(pointer)，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。03003.00302-2.30632-0.706344.8

復(fù)數(shù)順序存儲結(jié)構(gòu)………0415-2.3

06113.006130415

復(fù)數(shù)鏈?zhǔn)酱鎯Y(jié)構(gòu)………▲作業(yè)：1.1選擇題部分

1、組成數(shù)據(jù)的基本單位是（）

（A）數(shù)據(jù)項(xiàng)（B）數(shù)據(jù)類型（C）數(shù)據(jù)元素（D）數(shù)據(jù)變量

2、數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。

（A）理想結(jié)構(gòu)，物理結(jié)構(gòu)（B）理想結(jié)構(gòu)，抽象結(jié)構(gòu)

（C）物理結(jié)構(gòu)，邏輯結(jié)構(gòu)（D）抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)

3、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）

（A）動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)（B）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

（C）線性結(jié)構(gòu)和非線性結(jié)構(gòu)（D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)填空題1.數(shù)據(jù)邏輯結(jié)構(gòu)包括（

）、（

）和（

）三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為（

）。2.線性結(jié)構(gòu)中元素之間存在（

）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（

）關(guān)系，圖形結(jié)構(gòu)中元素之間存在（

）關(guān)系。數(shù)據(jù)類型：(datatype)

數(shù)據(jù)類型是一組性質(zhì)相同的值的集合以及定義于這個(gè)值集合上的一組操作的總稱。值的集合+值集合上的一組操作

例如，C

語言中的int型變量，是指由-32768到32767范圍中的值構(gòu)成的集合及一組操作（加、減、乘、除、乘方等）的總稱。而Unsignedint型變量，則是指由0到65535范圍中的值構(gòu)成的集合及一組操作（加、減、乘、除、乘方等）的總稱。約束變量或常量的取值范圍，約束變量或常量的操作。在用高級程序設(shè)計(jì)語言編寫的程序中，必須對程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。例如，C語言中的基本數(shù)據(jù)類型有：整型、字符型、實(shí)型（包括單精度型和雙精度型）及枚舉型。數(shù)據(jù)類型的作用數(shù)據(jù)類型的作用是解釋計(jì)算機(jī)內(nèi)存中信息含義的一種手段。實(shí)現(xiàn)了信息的隱蔽，將用戶不必了解的細(xì)節(jié)封裝在類型中。抽象特性強(qiáng)調(diào)的是其所能完成的功能以及它和外部用戶的接口(即外界使用它的方法)。

所有高級語言中都有“整型”數(shù)據(jù)類型，它們的實(shí)現(xiàn)方法可以各自不同，但對程序員而言，它們是“相同”的。程序員使用它們時(shí)僅需了解它們的數(shù)學(xué)特性，而不需要了解它們在語言中是如何實(shí)現(xiàn)的。換句話說，各種語言中實(shí)現(xiàn)的是同一個(gè)“整數(shù)類型”，而這個(gè)“整數(shù)類型”的定義僅對“整數(shù)的數(shù)學(xué)特性”有明確規(guī)定。01000001int：65（十進(jìn)制數(shù)）char：A抽象數(shù)據(jù)類型(AbstractDataType，簡稱ADT)：

數(shù)學(xué)模型+定義在該模型上的一組操作。

數(shù)據(jù)結(jié)構(gòu)+定義在此結(jié)構(gòu)上的一組操作。

ADT抽象數(shù)據(jù)類型名

{

數(shù)據(jù)對象:〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系:〈數(shù)據(jù)關(guān)系的定義〉

基本操作:〈基本操作的定義〉

}ADT

抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型(AbstractDataType)的描述方法：

抽象數(shù)據(jù)類型可用(D,S,P)三元組表示，其中，D

是數(shù)據(jù)對象，S是D

上的關(guān)系集，P

是對D

的基本操作集。用偽碼(不真正執(zhí)行的符號)描述基本操作的定義格式：賦值參數(shù)：只為操作提供輸入值；

引用參數(shù)：以&打頭，除了可提供輸入

值外，還將返回操作結(jié)果。

描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。說明操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果?；静僮髅▍?shù)表）初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉

例：抽象數(shù)據(jù)類型“復(fù)數(shù)”的定義ADTComplex{

數(shù)據(jù)對象：D={e1,e2|e1,e2∈RealSet}

基本操作：

InitComplex(&Z,v1,v2)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z，其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)

初始條件：復(fù)數(shù)Z已存在。操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)

初始條件：復(fù)數(shù)Z已存在。操作結(jié)果：用realPart返回Z的實(shí)部值。

GetImag(Z,&ImagPart)

初始條件：復(fù)數(shù)Z已存在。操作結(jié)果：用ImagPart返回Z的虛部值。

Add(Z1,Z2,&sum)

初始條件：Z1,Z2是復(fù)數(shù)。操作結(jié)果：用sum返回z1,z2的和值。

}ADTComplex

數(shù)據(jù)關(guān)系：R1={<e1,e2>|e1是復(fù)數(shù)的實(shí)部，e2是復(fù)數(shù)的虛部}用兩個(gè)實(shí)數(shù)來表示復(fù)數(shù)，將復(fù)數(shù)定義為兩個(gè)實(shí)數(shù)的有序?qū)Γ⒓s定實(shí)部是前驅(qū)，虛部是后繼。例1-6：抽象數(shù)據(jù)類型三元組的定義：

ADTTriplet{

數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3∈ElemSet}

數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T,v1,v2,v3)

操作結(jié)果：構(gòu)造了三元組T，元素e1，e2和e3分別被

賦以參數(shù)v1，v2和v3的值。

DestroyTriplet(&T)

操作結(jié)果：三元組T被銷毀。

Get(T,i,&e)

初始條件：三元組T已存在，1i3。

操作結(jié)果：用e返回T的第i元的值。

Put(&T,i,e)

初始條件：三元組T已存在，1i3。

操作結(jié)果：改變T的第i元的值為e。

IsAscending(T)

初始條件：三元組T已存在。

操作結(jié)果：如果T的三個(gè)元素按升序排列，則返回1，

否則返回0。

IsDescending(T)

初始條件：三元組T已存在。

操作結(jié)果：如果T的三個(gè)元素按降序排列，則返回1，

否則返回0。

Max(T,&e)

初始條件：三元組T已存在。

操作結(jié)果：用e返回T的三個(gè)元素中的最大值。

Min(T,&e)

初始條件：三元組T已存在。

操作結(jié)果：用e返回T的三個(gè)元素中的最小值。}ADTTriplet1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過高級編程語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型（通常稱之為固有數(shù)據(jù)類型）來表示和實(shí)現(xiàn)。

抽象數(shù)據(jù)類型的實(shí)現(xiàn)包括數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和操作的實(shí)現(xiàn)，因此不僅要借用高級語言中的數(shù)據(jù)類型來描述它的存儲結(jié)構(gòu)，也要利用高級語言中已經(jīng)實(shí)現(xiàn)的固有數(shù)據(jù)類型的操作來實(shí)現(xiàn)抽象數(shù)據(jù)類型的操作。例：利用C語言實(shí)現(xiàn)的“復(fù)數(shù)”類型如下描述：

數(shù)據(jù)對象：D={e1,e2|e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：R1={<e1,e2>|e1是復(fù)數(shù)的實(shí)部，e2是復(fù)數(shù)的虛部}//存儲結(jié)構(gòu)的定義

typedefstruct{

floatrealpart;

floatimagpart;

}complex;

基本操作：

InitComplex(&Z,v1,v2)

DestroyComplex(&Z)GetReal(Z,&realPart)

GetImag(Z,&ImagPart)

Add(Z1,Z2,&sum)//基本操作的函數(shù)原型說明

voidadd(complexz1,complexz2,complex&sum)

{

//以sum返回兩個(gè)復(fù)數(shù)z1，z2的和

//基本操作的實(shí)現(xiàn)

sum.realpart=z1.realpart+z2.realpart;

sum.imagpart=z1.imagpart+z2.imagpart;

}▲

本書采用類C語言作為抽象數(shù)據(jù)類型的描述工具。1.4算法和算法分析1.4.1算法通俗地講，算法就是一種解題的方法。

嚴(yán)格地講算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。(5)輸出:

一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。(4)

輸入:

一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對象集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。算法的五個(gè)特性：(1)

有窮性:

一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步

都在有窮時(shí)間內(nèi)完成。(2)

確定性:

算法中每一條指令必須有確切的含義，無二義性。并

且，在任何條件下，算法同時(shí)只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出。(3)可行性:

算法描述的所有操作都必須足夠基本，都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。

序列中的每個(gè)操作都是可以簡單完

成的，其本身不存在算法問題，例

如，“求x

和y

的和”就不夠基本。算法的含義與程序十分相似，但二者是有區(qū)別的。注1、一個(gè)程序不一定滿足有窮性（如一個(gè)操作系統(tǒng)在用戶未使用

前一直處于“等待”的循環(huán)中,直到出現(xiàn)新的用戶事件為止。

這樣的系統(tǒng)可以無休止地運(yùn)行，直到系統(tǒng)停工。）；2、程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此

限制。算法若用計(jì)算機(jī)語言來書寫，則它就可以是程序。

一個(gè)算法可以用自然語言、數(shù)學(xué)語言或約定的符號來描述，也可以用流程圖、計(jì)算機(jī)高級程序語言（如C語言）或偽代碼等來描述。1.4.2算法設(shè)計(jì)的要求

設(shè)計(jì)一個(gè)“好”的算法應(yīng)考慮以下幾個(gè)方面（評價(jià)標(biāo)準(zhǔn)）：(1)正確性：算法應(yīng)滿足具體問題的需求。

“正確”的含義在通常的用法中有很大的差別，大體可分為以下四個(gè)層次：1)、程序不含語法錯(cuò)誤；2)、程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；3)、程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；4)、程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。通常以第3)層意義的正確性作為衡量一個(gè)程序是否合格的標(biāo)準(zhǔn)。(3)健壯性：算法應(yīng)具有容錯(cuò)處理功能。

當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。(4)

效率與低存儲量需求：效率指的是算法執(zhí)行的時(shí)間（時(shí)間復(fù)雜性）；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間（空間復(fù)雜性）。一般這兩者與問題的規(guī)模有關(guān)。(2)可讀性：算法在正確的前提下，可讀性是擺在第一位的，這在當(dāng)今大型軟件需要多人合作完成的環(huán)境下是至關(guān)重要的，另一方面，晦澀難讀的程序易于隱藏錯(cuò)誤而難以調(diào)試。1.4.3算法效率的度量

一個(gè)算法執(zhí)行時(shí)間，從理論上是不能算出來的，必須通過依據(jù)該算法編制的程序上機(jī)運(yùn)行測試才能知道。

度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法：(1)、事后統(tǒng)計(jì)的方法

此方法有兩個(gè)缺陷：一是必須先運(yùn)行程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。(2)、事前分析估算的方法

事后統(tǒng)計(jì)容易陷入盲目境地，例如，當(dāng)程序執(zhí)行很長時(shí)間仍未結(jié)束時(shí)，不易判別是程序錯(cuò)了還是確實(shí)需要那么長的時(shí)間。

顯然，后三條受著計(jì)算機(jī)硬件和軟件的制約，既然是“估算”僅需考慮前兩條。

與算法執(zhí)行時(shí)間相關(guān)的因素有：

1)、算法選用的策略2)、問題的規(guī)模3)、編寫程序的語言4)、編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5)、計(jì)算機(jī)執(zhí)行指令的速度

一般認(rèn)為算法的效率只依賴于問題的規(guī)模。

問題的規(guī)模如何計(jì)算？

例：考慮計(jì)算三次多項(xiàng)式ax3+bx2+cx+d方法1：s=axxx+bxx+cx+d

(6次乘法，3次加法)計(jì)算量大方法2：s=a;s=s

x+b;s=s

x+c;s=s

x+d;(3次乘法，3次加法)計(jì)算量小

方法2的原理：

axxx+bxx+cx+d=(a

x+b)x2+cx+d

=((a

x+b)x+c)x+d問題的規(guī)模一般根據(jù)問題本身的性質(zhì)合理地確定：例1：對n

個(gè)電話號碼進(jìn)行排序，這里n

即可作為問題的規(guī)模。

顯然對1000個(gè)電話號碼進(jìn)行排序比對10個(gè)電話號碼進(jìn)行排序規(guī)模要大。例2：求n

階矩陣的轉(zhuǎn)置，這里n

即可作為問題的規(guī)模。(2)、事前分析估算的方法

如何估算算法的時(shí)間效率？▲填空題1.算法的五個(gè)重要特性是（）、（）、（）、（）、（）。2.算法的四個(gè)衡量標(biāo)準(zhǔn)是（）、（）、（）、（）。作業(yè)分析：任何一個(gè)算法都是由一個(gè)控制結(jié)構(gòu)和若干原操作組成的。

控制結(jié)構(gòu)：順序、分支和循環(huán)3種。

原操作：指對固有數(shù)據(jù)類型（高級語言中的數(shù)據(jù)類型）的操作（如賦值操作、轉(zhuǎn)向操作、比較操作等等），顯然每個(gè)原操作的執(zhí)行時(shí)間和算法無關(guān)，相對于問題的規(guī)模是常量。結(jié)論：算法的執(zhí)行時(shí)間可看成是所有原操作的執(zhí)行時(shí)間之和：

既然執(zhí)行一種原操作所需的時(shí)間與算法無關(guān)，那么我們只討論影響運(yùn)行時(shí)間的另一個(gè)因素——算法中進(jìn)行原操作的次數(shù)。

算法中包含原操作次數(shù)的多少叫做算法的時(shí)間復(fù)雜度，用它來衡量一個(gè)算法的運(yùn)行時(shí)間性能。算法的執(zhí)行時(shí)間如何計(jì)算？

算法的時(shí)間復(fù)雜度通常是問題的規(guī)模n

的某個(gè)函數(shù)T(n)。例：累加求和

intSum(intb[n],intn){inti,s=0;for(i=0;i<n;i++)s+=b[i];returns;}各執(zhí)行1次原操作。for循環(huán)語句所包含的原操作：i=0;//1次m1:if(i>=n)gotom2;//n+1次

s+=b[i];//n次i++;//n次gotom1;//n次m2:returns;時(shí)間復(fù)雜度為：T(n)=4n+4例：矩陣相加

voidMA(inta[ms][ms],intb[ms][ms],intc[ms][ms],intn)//實(shí)現(xiàn)矩陣a[n,n]和b[n,n]的加法，其和存入c[n,n]中//ms為大于等于n的常量{inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)c[i][j]=a[i][j]+b[i][j];}雙重for循環(huán)語句所包含的原操作：i=0;//1次m1:if(i>=n)gotom4;//n+1次j=0;//n次m2:if(j>=n)gotom3;//n(n+1)次

c[i][j]=a[i][j]+b[i][j];//nn次時(shí)間復(fù)雜度為：T(n)=4n2+5n+2j++;//nn次gotom2;//nn次m3:i++;//n次gotom1;//n次m4:

從上述分析可知，一個(gè)算法的時(shí)間復(fù)雜度的計(jì)算相當(dāng)煩瑣。實(shí)際上，一般沒必要精確地計(jì)算出算法的時(shí)間復(fù)雜度，只要大致計(jì)算出相應(yīng)的數(shù)量級(Order)即可。時(shí)間復(fù)雜度T(n)的數(shù)量級表示：定義

如果存在兩個(gè)正常數(shù)c

和n0，對于所有的nn0，有|f(n)|c|T(n)|則稱f(n)是T(n)的同數(shù)量級函數(shù)。把T(n)表示成數(shù)量級的形式為：T(n)=O(f(n))。稱Ｏ(f(n))為算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。O

是Order的首字母，意為f(n)與T(n)只差一個(gè)常數(shù)倍。

算法效率的度量：采用漸進(jìn)時(shí)間復(fù)雜度例：for(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];}

由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則原操作重復(fù)執(zhí)行的總次數(shù)為：n×n×n=n3，時(shí)間復(fù)雜度為T(n)=O(n3)。

在“累加求和”例中，當(dāng)n1（即n0=1）時(shí)，|n|c|4n+4|均成立，則f(n)=n，T(n)=O(n)；在“矩陣相加”例子中，當(dāng)n2（即n0=2）時(shí)，|n2|c|4n2

+5n+2|均成立，則f(n)=n2。T(n)=O(n2)。

原操作應(yīng)是：重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的原操作。

原操作的重復(fù)執(zhí)行次數(shù)和包含它的語句被執(zhí)行的次數(shù)相同。

語句頻度：語句被重復(fù)執(zhí)行的次數(shù)。

例：{++x;s=0;}

包含“x增1”基本操作的語句的頻度為１，即時(shí)間復(fù)雜度為O(1)。O(1)表示算法的運(yùn)行時(shí)間為常量。即：常量階。例：for(i=1;i<=n;++i){++x;

s+=x;}

包含“x增1”基本操作的語句的頻度為：n，其時(shí)間復(fù)雜度為：O(n)，即：線性階。例：for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;

s+=x;}

包含“x增1”基本操作的語句的頻度為：n2，其時(shí)間復(fù)雜度為：O(n2)，即：平方階。例：for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;

a[i,j]=x;}

包含“x增1”基本操作的語句的頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2