《微觀經(jīng)濟學(xué)》緒論

1第1章

緒

論1.1為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1.2有關(guān)概念和術(shù)語

1.3算法和算法分析1.3.1算法特性1.3.2算法效率的度量方法和準(zhǔn)則2【重點掌握】：1．?dāng)?shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)等術(shù)語及其含義2．計算原操作的語句頻度、估算算法漸近時間復(fù)雜度【掌

握】：1．為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)2．?dāng)?shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素等術(shù)語及其含義3．?dāng)?shù)據(jù)結(jié)構(gòu)與算法之間的關(guān)系4．算法5個特性、設(shè)計算法的基本要求5．常見算法的漸近時間復(fù)雜度主要問題：信息的表示信息的處理3

1.1為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)計算機科學(xué)是一門研究用計算機進行信息表示和處理的科學(xué)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的主要目的：

使學(xué)生了解數(shù)據(jù)對象的特征，學(xué)會數(shù)據(jù)組織的方法，能夠把現(xiàn)實世界中的問題在計算機內(nèi)部進行表示，以及培育基本的、良好的程序設(shè)計技能。計算機解決問題的步驟：實際問題－數(shù)學(xué)模型－算法－程序－結(jié)果4【例1】圖書信息檢索系統(tǒng)。登錄號：書名：作者名：分類號：價格：書目卡片書目文件線性表按書名按作者名按分類號索引表5【例2】教學(xué)計劃編排問題。C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3,C5C3,C6無C9C9C1,C9,C10課程代號

課程名稱

先修課程序設(shè)計基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析圖C1C2C3C4C5C6C7C8C9C10C11C12姓名項目1項目2項目3丁一跳高跳遠100米馬二標(biāo)槍鉛球張三標(biāo)槍100米200米李四鉛球200米跳高王五跳遠200米例3、田徑賽的時間安排問題跳高跳遠200米鉛球標(biāo)槍100米比賽項目和選手如表所示，（共有5名選手，6個項目）要求在最短的時間內(nèi)安排完比賽。一種顏色代表一個比賽時間ABCDEF檔案學(xué)專業(yè)研究的數(shù)據(jù)對象

信息管理與信息系統(tǒng)專業(yè)的培養(yǎng)目標(biāo)：“培養(yǎng)具備現(xiàn)代管理學(xué)理論基礎(chǔ)、計算機科學(xué)技術(shù)知識及應(yīng)用能力、掌握系統(tǒng)思想和信息系統(tǒng)分析與設(shè)計方法以及信息管理等方面的知識和能力,能在國家各級管理部門、工商企業(yè)、金融機構(gòu)、科研單位等部門從事信息管理以及信息系統(tǒng)分析、設(shè)計、實施、管理和評價等方面的高級專門人才”。91.2有關(guān)概念和術(shù)語1.數(shù)據(jù)(data)：是對客觀信息的描述，它是由能夠被計算機識別與處理的數(shù)值、字符等符號構(gòu)成的集合。2.數(shù)據(jù)元素(dataelement):數(shù)據(jù)的基本單位，也稱結(jié)點（node）或記錄（record）?？捎啥鄠€數(shù)據(jù)項組成。3.數(shù)據(jù)項(dataitem):有獨立含義的數(shù)據(jù)最小單位。4.關(guān)鍵碼（key）：數(shù)據(jù)元素中具有標(biāo)識作用的數(shù)據(jù)項。5.數(shù)據(jù)類型（datatype）：具有相同性質(zhì)的計算機數(shù)據(jù)的集合及在這個數(shù)據(jù)集合上的一組操作。6.數(shù)據(jù)結(jié)構(gòu)(datastructure)：數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合。10根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有3種基本數(shù)據(jù)結(jié)構(gòu)：線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)——一個對多個，如樹圖狀結(jié)構(gòu)——多個對多個，如圖117.數(shù)據(jù)的邏輯結(jié)構(gòu)：抽象反映數(shù)據(jù)元素的邏輯關(guān)系。8.數(shù)據(jù)的存儲(物理)結(jié)構(gòu)：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示或?qū)崿F(xiàn)。存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)——借助元素在存儲器中的相對位置表示

數(shù)據(jù)元素間的邏輯關(guān)系。鏈?zhǔn)酱鎯Y(jié)構(gòu)——借助指示元素存儲地址的指針表示數(shù)據(jù)

元素間的邏輯關(guān)系。學(xué)生成績表姓名數(shù)學(xué)分析物理代數(shù)平均成績王小林90859590陳紅80859085劉建平95919995張立立70848680……..……..…….…….（結(jié)點、直接前趨、直接后繼、開始結(jié)點、終端結(jié)點）邏輯結(jié)構(gòu)（１）線性結(jié)構(gòu)：有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點最多只有一個直接前趨和一個直接后繼。 例如：線形表（２）非線形結(jié)構(gòu)：一個結(jié)點可能有多個直接前趨和直接后繼。 例如：樹、圖（1）順序存儲方法： 把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。存儲方法ABCDEF::123456:（2）鏈接存儲方法： 不要求邏輯上相鄰的結(jié)點在物理位置上也相鄰，結(jié)點間的邏輯關(guān)系由附加的指針字段來表示。A5D6C2B4::::DataPointer123456:161、數(shù)據(jù)的邏輯結(jié)構(gòu)

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

*[3]數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)順序存儲

鏈?zhǔn)酱鎯?/p>

線性表棧隊列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(物理結(jié)構(gòu))171.3算法和算法分析

1.3.1算法性能1.算法(algorithm)：解決某一特定問題的具體步驟的描述，是指令的有限序列。2.算法特性有窮性：一個算法必須在執(zhí)行有限步驟之后結(jié)束。確定性：算法的每一步必須是確切定義的，不能產(chǎn)生二義性可行性：每條指令的執(zhí)行時間是有限的。輸入：一個算法有零個或多個輸入。輸出：一個算法有一個或多個輸出。3.算法的評價（衡量算法優(yōu)劣的標(biāo)準(zhǔn)）

正確性

可讀性

健壯性

效率與低存儲量18

算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）

即：算法的執(zhí)行時間與原操作執(zhí)行次數(shù)之和成正比。1.3.2算法效率的衡量方法和準(zhǔn)則執(zhí)行算法所耗費的時間=算法中每條語句的執(zhí)行時間之和每條語句的執(zhí)行時間＝該語句的執(zhí)行次數(shù)（頻度）與該語句執(zhí)行一次所需時間的乘積。假設(shè)執(zhí)行每條語句所需的時間均是單位時間，則一個算法的時間耗費是所有語句的頻度之和。時間復(fù)雜度20估算算法的時間復(fù)雜度的具體方法及步驟從算法中選取一種對于所研究的問題來說是基本操作的原操作;計算該原操作在算法中重復(fù)執(zhí)行的次數(shù)(語句頻度)，以它做為算法運行時間的衡量準(zhǔn)則，它通常只依賴于問題的規(guī)模(通常用整數(shù)量n表示)，或者說，它是問題規(guī)模的函數(shù)，通常記為f(n);一般沒有必要精確地計算出算法的時間復(fù)雜度，只要大致計算出相應(yīng)的數(shù)量級即可;如果隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))，稱T(n)為算法的漸近時間復(fù)雜度。

例：時間復(fù)雜度T(n)＝f(n)=2n3+3n2+2n+1漸進時間復(fù)雜度T(n)＝O(f(n))=n3常見的漸進時間復(fù)雜度：O(1) 常量階 O(n) 線性階O(n2) 平方階O(logn) 對數(shù)階O(2n) 指數(shù)階例２{x++;s=s+x;}時間復(fù)雜度:Ｏ(1)，常量階。例３、for(I=1;I<=n;I++){x++; s=s+x;}時間復(fù)雜度:O(n),線性階。例４、for(I=1;I<=n;++I)

for(j=1;j<=n;++j){++x;s+=x;}時間復(fù)雜度為：O(n2),平方階。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，則A(n)=O(nm)例5 i=1;while(i<=n) i=i*2解：語句頻度為f(n)

則2f(n)<=n

得到f(n)=log2n24例6估算“順序查找”的算法的時間復(fù)雜度。i=1;while(i<=n&&a[i]!=key)i++;if(i<=n)pos=i;elsepos=0;123456789101151319213756647580889225(3)平均時間復(fù)雜度:O(n)

假設(shè)每一個元素為key的概率是相等的(1/n)，則第i個元素查找成功時需要比較的次數(shù)為i，n個元素的平均比較次數(shù)為:(1+2+……+n)/n=(n+1)/2。(1)最好時間復(fù)雜度:O(1)a[0]=key的情況。一個復(fù)雜度為O(1)的算法，它的原操作的執(zhí)行次數(shù)是固定的，與規(guī)模n無關(guān)。(2)最壞時間復(fù)雜度:O(n)a[n-1]=key的情況。263.常見時間復(fù)雜度(1)多項式時間的上限

以下6種