數(shù)據(jù)結構與算法分析新視角（第2版） 課件 周幸妮 第1-4章 緒論-數(shù)組和串

數(shù)據(jù)結構與算法分析

新視角前言Chapter

0DatastructuresandAlgorithms從新視角來看待舊問題，需要有創(chuàng)造性的思維，這標志著科學的真正進步?！獝垡蛩固箶?shù)據(jù)結構與其他課程的關系4Web信息處理人工智能數(shù)據(jù)庫操作系統(tǒng)編譯原理圖形圖像算法分析與設計數(shù)據(jù)結構計算復雜性理論概率統(tǒng)計計算概論集合與圖論教學內(nèi)容1緒論3運算特殊的線性表——棧和隊列4內(nèi)容特殊的線性表——字符串和多維數(shù)組2結點邏輯關系為線性的結構——線性表5結點邏輯關系分層次的非線性結構——樹7數(shù)據(jù)的處理方法——排序技術8數(shù)據(jù)的處理方法——索引與查找技術6結點邏輯關系任意的非線性結構——圖9經(jīng)典算法緒論Chapter

1DataStructuresandAlgorithmAnalysis主要內(nèi)容數(shù)據(jù)結構的概念算法設計的基本要求從時間和空間角度分析算法效率的方法學習目標了解數(shù)據(jù)結構課程的意義掌握數(shù)據(jù)結構的概念掌握算法設計與程序設計的步驟掌握算法效率的分析評價方法1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.1從編程說起程序的公式表達12算法+數(shù)據(jù)結構

=程序尼古拉斯·沃斯NiklausWirth1934年2月15日——算法是處理問題的策略，數(shù)據(jù)結構是描述問題信息的數(shù)據(jù)模型，程序則是計算機按照處理問題的策略處理問題信息的一組指令集計算機解決問題的過程1314程序的開發(fā)程序解題軟件工程具體工作建模型需求分析階段提取問題要完成的功能；分析問題涉及的數(shù)據(jù)對象，找出數(shù)據(jù)對象之間的關系。設計設計階段數(shù)據(jù)結構設計、軟件的結構設計、算法設計

編程編碼階段編寫程序代碼驗證測試軟件測試與調(diào)試1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.2程序要處理的數(shù)據(jù)17數(shù)值與非數(shù)值問題數(shù)值計算非數(shù)值計算數(shù)值計算，具體地說就是有效利用計算機求解數(shù)學問題近似解的方法與過程，可以通過抽象出合適的數(shù)學模型，然后設計相應的算法來解決。數(shù)值計算問題，以浮點算術運算為主，算法成熟所謂“非數(shù)值計算”問題，是為了區(qū)分前面提到的“數(shù)值問題”而言。非數(shù)值問題涉及到的數(shù)據(jù)及數(shù)據(jù)間的相互關系，一般無法用數(shù)學公式、方程等來描述，如排序問題、檢索問題等，需要另外設計數(shù)據(jù)的描述方法和相應的算法來處理。18從下面的無限序列中計算出π的值。輸出一個表格，在該表格中顯示根據(jù)這個序列中的1項、2項、3項等等所得的近似π值。在第一次得到3.14之前，必須使用這個序列的多少項？如果是得到3.141呢？3.1415呢？3.14159呢？數(shù)值問題的例子通用公式數(shù)據(jù)對象數(shù)據(jù)間關系數(shù)據(jù)初始化建模型m=1;i=1-1偶數(shù)1奇數(shù)m取值i取值項數(shù)：當前已經(jīng)用到的項數(shù)i系數(shù)：控制序列項的正負號

m4+（-1）*m*4/(2*i+1)例19算法頂部偽代碼描述賦初值：累加和x=4;m=1;項數(shù)i=1；根據(jù)通用公式,x做循環(huán)累加直到x=3.14時中斷循環(huán)輸出x及i值；算法細化描述累加和x=4;m=1;i=1；dox=x+（-1）*m*4/(2*i+1)

i增加1；

m=m*(-1)直到x=3.14時中斷循環(huán)輸出x及i值；設計數(shù)值問題的例子20數(shù)值問題的例子voidmain(){floatx=4;inti=1,m=1;while(1){ x=x+(float)(-1)*m*4/(2*i+1); i++; m=m*(-1); if(x>=3.14-0.000001&&x<=3.14+0.000001)break;} printf("i=%d,x=%f\n",i,x);}編程要求對任意給出的一個姓名，查找電話號碼非數(shù)值問題例子1——電話號碼查詢客戶姓名電話身份證號地址張1138*****6101131980******李2152*****6101131981******王1139*****6101131990******張2139*****6101131972******李1188*****6101131976******………"表""關鍵字""數(shù)據(jù)項"關鍵字關鍵字是能唯一標識一個結點的那些數(shù)據(jù)項"數(shù)據(jù)元素"或"結點"例方法1客戶姓名電話身份證號地址張1138*****6101131980******李2152*****6101131981******王1139*****6101131990******張2139*****6101131972******李1188*****6101131976******王2138*****6101131986******………順序結構順序查找非數(shù)值問題例子1——電話號碼查詢問題涉及的對象每客戶及其相應的數(shù)據(jù)項；對象之間的關系數(shù)據(jù)元素順序排列；查找指定數(shù)據(jù)項，輸出相應數(shù)據(jù)項建模型設計非數(shù)值問題例子1——電話號碼查詢方法1順序結構順序查找有序結構折半查找方法2客戶姓名電話身份證號地址李1188*****6101131976******李2152*****6101131981******王1139*****6101131990******王2138*****6101131986******張1138*****6101131980******張2139*****6101131972******………非數(shù)值問題例子1——電話號碼查詢問題涉及的對象每客戶及其相應的數(shù)據(jù)項；對象之間的關系數(shù)據(jù)元素有序排列；折半查找指定數(shù)據(jù)項，輸出相應數(shù)據(jù)項建模型設計非數(shù)值問題例子1——電話號碼查詢有序結構折半查找方法2索引結構分級查找客戶姓名電話身份證號地址李1188*****6101131976***0x2000李2152*****6101131981******………張1138*****6101131980***0x4000張2139*****6101131972******………王1139*****6101131990***0x6000王2138*****6101131986******………姓氏表內(nèi)地址數(shù)量李0x2000***張0x4000***王0x6000***………索引表數(shù)據(jù)表方法3非數(shù)值問題例子1——電話號碼查詢問題涉及的對象索引表客戶姓氏、對應數(shù)據(jù)表中的地址數(shù)據(jù)表每個客戶及其相應的數(shù)據(jù)項；對象之間的關系索引表數(shù)據(jù)元素有序排列數(shù)據(jù)表數(shù)據(jù)元素順序排列；建模型先索引表，后數(shù)據(jù)表設計非數(shù)值問題例子1——電話號碼查詢索引結構分級查找方法328非數(shù)值問題例子1——電話號碼查詢數(shù)據(jù)的組織方式和數(shù)據(jù)的存儲方式，都會影響算法的效率結論29在十字路口，要設置幾種顏色的交通燈才可保持正常的交通秩序？BCDA十字路口交通燈管理問題非數(shù)值問題的例子2問題涉及的對象對象之間的關系表示AC、BD不能同時通行BDAC用表示AC間有一條通路AC建模型某方向通行時，另外某些方向不能通行四個路口ABCD，及相應的通路；例30ACABADBDBABCCACDCBDBDCDABCDA“圖”“數(shù)據(jù)元素”或“結點”對圖中的圓圈上色，同一連線上的兩個圓圈不同色且顏色種類最少設計非數(shù)值問題的例子231非數(shù)值問題的例子3rootbinlibuseretcmathdsswsunzhouzhaoStack.cppTree.cppQueue.cpp……"樹"“數(shù)據(jù)元素”或“結點”計算機文件系統(tǒng)結構的表示與管理例1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.3數(shù)據(jù)結構的引入問題解決信息表述信息處理計算機解題過程先找出問題中要處理的數(shù)據(jù)及數(shù)據(jù)間的聯(lián)系、組織形式、存儲方式、表示方法等，設計適合計算機解題的模型按要求有效地解決問題

數(shù)據(jù)結構研究的問題

經(jīng)典數(shù)據(jù)結構數(shù)據(jù)表示方法數(shù)據(jù)存儲形式數(shù)據(jù)運算1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.4數(shù)據(jù)結構的要素1.4.11.4.2數(shù)據(jù)結構基本術語數(shù)據(jù)結構的三個要素數(shù)據(jù)的基本單位可包含多個數(shù)據(jù)項38基本概念和術語數(shù)據(jù)元素由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關系組成數(shù)據(jù)元素中的不可分割的最小單位客觀對象在計算機中的符號表示數(shù)據(jù)結構數(shù)據(jù)項數(shù)據(jù)數(shù)據(jù)結構基本術語1.4數(shù)據(jù)結構的要素1.4.11.4.2數(shù)據(jù)結構基本術語數(shù)據(jù)結構的三個要素數(shù)據(jù)結構數(shù)據(jù)的邏輯結構體現(xiàn)各結點間的相鄰關系，由數(shù)據(jù)本身內(nèi)在特性所決定，獨立于計算機數(shù)據(jù)的存儲結構數(shù)據(jù)元素及其邏輯關系在計算機存儲器內(nèi)的表示數(shù)據(jù)的運算對數(shù)據(jù)施加的操作數(shù)據(jù)結構的三個要素數(shù)據(jù)結構的三個要素數(shù)據(jù)邏輯結構集合結點間無關系線性結構結點間一對一關系樹形結構結點間是一對多關系圖形結構結點間是多對多關系數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構數(shù)據(jù)的存儲結構42數(shù)據(jù)存儲結構順序存儲結點的邏輯關系由存儲單元的鄰接關系來體現(xiàn)鏈式存儲結點的邏輯關系由附加的指針字段表示索引存儲索引項：（關鍵字，地址）散列存儲結點地址＝F（關鍵字）數(shù)據(jù)的運算43數(shù)據(jù)運算運算的定義建立在數(shù)據(jù)的邏輯結構上運算的實現(xiàn)以數(shù)據(jù)的存儲結構為基礎常見運算：初始化

判空

求長度

查找

遍歷

取值

置值

插入

刪除

1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.5如何設計算法1.5.11.5.2算法的定義及表示方法算法設計與函數(shù)設計的關系1.5.31.5.4軟件設計描述算法設計的一般步驟1.5如何設計算法1.5.11.5.2算法的定義及表示方法算法設計與函數(shù)設計的關系1.5.31.5.4軟件設計描述算法設計的一般步驟47算法

在有限步驟內(nèi)求解某一問題所使用的一組定義明確的操作序列，能夠在有限時間內(nèi)，對一定的規(guī)范的輸入獲得所要求的輸出。算法算法特征1有窮性：一個算法必須保證在執(zhí)行有限步驟后結束，而不是無限的。3可行性：每一個操作步驟都必須在有限的時間內(nèi)完成。4輸入：一個算法可以有多個輸入，也可以沒有輸入。2確定性：算法中每一條指令必須有明確的含義，而不能是含糊不清的有歧義。5輸出：一個算法可以有一個或多個輸出，沒有輸出的算法是沒有實際意義的。算法的表示49可以幫助程序員開發(fā)算法的，由字符組成的非正式語言?？梢砸萌魏尉哂斜磉_力的方法來最清晰、最簡潔地表達算法。偽代碼本書對算法的描述采用偽代碼的方式1.5如何設計算法1.5.11.5.2算法的定義及表示方法算法設計與函數(shù)設計的關系1.5.31.5.4軟件設計描述算法設計的一般步驟longfactorial(intn);

有關函數(shù)的概念函數(shù)類型函數(shù)名（形參類型說明表）{

聲明部分； 語句部分；}函數(shù)的定義形式函數(shù)類型函數(shù)名（形參類型說明表）;函數(shù)的聲明形式函數(shù)名(實參表);函數(shù)的調(diào)用形式longfactorial(intn){

inti;

long

t=1;

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

t=t*i;

return(t);}intm;longc；scanf(“%d”,&m);c=factorial(m);輸入的數(shù)據(jù)輸出的結果輸出結果的類型實際參數(shù)C函數(shù)實際參數(shù)與形式參數(shù)的關系52函數(shù)類型函數(shù)名（形式參數(shù)表）

{聲明部分;語句部分;}函數(shù)定義格式函數(shù)名（實際參數(shù)表）函數(shù)調(diào)用格式形式參數(shù)表中放參數(shù)的定義形式如基本變量：intx如指針：int*ptr如數(shù)組：inta[]如結構：structnodestu實際參數(shù)表中放參數(shù)的使用形式如基本變量：x如指針：ptr如數(shù)組：a如結構：stuC函數(shù)實際參數(shù)與形式參數(shù)的關系算法設計與函數(shù)設計的關系功能描述輸入信息輸出信息函數(shù)名形參函數(shù)類型接口及功能描述此處輸出的含義，是指函數(shù)傳遞給調(diào)用者的，不是輸出到顯示器上的此處信息輸入方式是調(diào)用者傳遞給函數(shù)，不是通過鍵盤等方式輸入1.5如何設計算法1.5.11.5.2算法的定義及表示方法算法設計與函數(shù)設計的關系1.5.31.5.4軟件設計描述算法設計的一般步驟軟件設計方法55根據(jù)問題的功能要求，按照輸入數(shù)據(jù)的正常情形、邊界或特例情形、異常情形等各種情形，給出測試樣例。測試用例設計1給出問題包含信息與信息聯(lián)系的存儲結構，用C語言數(shù)據(jù)類型描述。數(shù)據(jù)結構描述2根據(jù)問題的功能、輸入、輸出，對應確定函數(shù)類型、形參、返回值。函數(shù)結構設計3按照自頂向下逐步求精的方法，描述問題的解決步驟。算法描述4按照細化的偽代碼給出代碼實現(xiàn)，必要時按照測試樣例給出測試結果。程序實現(xiàn)5分析問題的時間復雜度、空間復雜度。算法效率分析61.5如何設計算法1.5.11.5.2算法的定義及表示方法算法設計與函數(shù)設計的關系1.5.31.5.4軟件描述方法算法設計的一般步驟算法設計的一般步驟571設定算法初始條件3按問題的普遍規(guī)律給出算法處理的流程4考慮臨界點或特殊點的處理2確定算法的結束條件5考慮異常情況算法設計實例5858算法設計的例子——求n！遞推公式S=S*Tn!1n<=1n*(n-1)!n>1step11*2=>sstep2s*3=>sstep3s*4=>sstep4s*5=>sS：累乘之積T：乘數(shù)遞推法定義例59算法設計實例——

求n！功能描述輸入信息輸出信息factorialintnint值異常：-1正常：n！的結果測試用例設計1接口及功能描述2情形測試數(shù)據(jù)預期結果問題的一般情形n>1按照n！一般定義得出的值臨界點或特殊點n=0，n=1按照n！邊界定義得出的值異常情況n<0給出錯誤提示信息

60算法設計實例——

求n！頂部偽代碼描述輸入n求n！輸出結果第一步細化輸入n初始化S=1，T=1由1乘2開始結果放到乘積S中，乘數(shù)T每次增1當T>n結束輸出結果S第二步細化輸入n設S=1，乘數(shù)T=1

doS=S*TT增加1

Until(T>n)輸出：S算法描述3算法設計實例——求n！61

一般情形邊界值異常情形測試值51001-1測試結果120362880011-1floatfactorial(intn){inti;floatt=1;if(n<0)return(-1);for(i=1;i<=n;i++)

t=t*i;return(t);}函數(shù)實現(xiàn)4測試結果562偽代碼描述要點簡潔明晰按程序結構特點描述算法步驟，注意格式縮進。內(nèi)容完整算法開始階段初始化信息輸入信息算法處理階段循環(huán)要素、判斷條件等算法結束階段輸出信息程序結構：順序、循環(huán)、分支63n!的例子#include<stdio.h>floatfactorial(intn);floatfactorial(intn){inti;floatt=1;for(i=1;i<=n;i++)t=t*i;return(t);}main(){floatc;intm;printf(〞inputm〞);scanf(〞%d〞,&m);c=factorial(m);printf(〞The%d!is%8.1f〞,

m，c);}函數(shù)說明函數(shù)調(diào)用函數(shù)定義1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.6如何評價算法的優(yōu)劣1.6.11.6.2算法設計的要求算法效率的度量方法1.6如何評價算法的優(yōu)劣1.6.11.6.2算法設計的要求算法效率的度量方法67算法設計的要求正確性程序不含語法錯誤對輸入數(shù)據(jù)能得出滿足要求的結果隨意的數(shù)據(jù)精心選擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)一切合法的輸入數(shù)據(jù)可讀性程序員的效率第一健壯性算法對不合理數(shù)據(jù)輸入應該有反應能力和處理能力高效性時間效率高效率指的是算法執(zhí)行的時間（時間復雜性）；存儲空間少存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間（空間復雜性）空間和時間可以互相轉化1.6如何評價算法的優(yōu)劣1.6.11.6.2算法設計的要求算法效率的度量方法69算法性能的事后統(tǒng)計#include<time.h>longstart,stop;time(&start);

/*******************

此處放要測定運行時間的函數(shù)********************/time(&stop);

longrunTime=stop-start;printf("%ld\n",runTime);例

硬件的速度

程序選用語言目標代碼質量

問題的規(guī)模

算法選用的策略算法效率因素算法時間效率相關因素分析算法性能的事前分析71時間效率空間效率算法性能分析算法的時間效率分析——找出與算法運行時間相關的因素與特征函數(shù)，從時間角度來評價算法。算法的空間效率分析——找出算法運行所需的輔助存儲空間特征函數(shù)，從空間角度來評價算法。1.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量

硬件的速度

程序選用語言目標代碼質量

問題的規(guī)模

算法選用的策略算法效率因素算法時間效率相關因素分析與算法執(zhí)行時間相關的因素中，哪些是關鍵因素？算法時間效率相關因素分析算法運行時間=算法中每條語句執(zhí)行時間之和每條語句執(zhí)行時間==>該語句的執(zhí)行次數(shù)74語句頻度將程序的運行時間表示為其輸入的函數(shù)若問題的規(guī)模為n，一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度，記為T(n)。1.7算法性能的事前分析方法1.7.11.7.2問題的規(guī)模與算法的策略算法時間效率的上限與下限1.7.31.7.4漸進的上限——算法的時間復雜度時間復雜度的綜合討論1.7.5算法的空間效率分析方法1.7算法性能的事前分析方法1.7.11.7.2問題的規(guī)模與算法的策略算法時間效率的上限與下限1.7.31.7.4漸進的上限——算法的時間復雜度時間復雜度的綜合討論1.7.5算法的空間效率分析方法77問題的規(guī)模與算法的策略每個卡片只看一次，共100次將數(shù)字1～100寫在卡片上，亂序后再按序排好。排序時所有卡片的查找次數(shù)是多少？先找1、再找2、找3、…最多要看(100+1)*100/2次法一法二問題規(guī)模為n時的比較次數(shù)f(n)=n2/2+n/2問題規(guī)模為n時的比較次數(shù)

f(n)=n例78問題的規(guī)模與算法的策略結論一般地，算法所需時間是和輸入規(guī)模n同步增長的：對于同一算法

輸入量小，速度快；

輸入量大，速度慢。對于不同的算法

有可能在n的某一區(qū)間，一個算法的速度高于另一個；

而在n的另一區(qū)間，情況可能就會相反。對于不同的算法

規(guī)模較小時，算法效率接近；

規(guī)模擴大，算法效率通常呈上升趨勢，各算法之間的差距就比較明顯了。791.7算法性能的事前分析方法1.7.11.7.2問題的規(guī)模與算法的策略算法時間效率的上限與下限1.7.31.7.4漸進的上限——算法的時間復雜度時間復雜度的綜合討論1.7.5算法的空間效率分析方法81算法分析規(guī)則1234596979899100…例將數(shù)字1～100寫在卡片上，亂序后再按序排好。排序時所有卡片的查找次數(shù)是多少？T(n)=n=1001009998979654321…23614578521627789310…最好情形最壞情形平均情形T(n)=(n+1)*n/2=5050T(n)=257582在n張卡片中找一個指定卡片i的平均查找次數(shù)ASLn（AverageSearchLength）Pi——查找表中第i個記錄的概率Ci——找到該記錄時已經(jīng)比較過的卡片數(shù)在n張卡片中找n個指定卡片i的平均查找次數(shù)ASLn=100時，T(n)=2575算法分析規(guī)則算法效率典型情形83最好效率：算法在最優(yōu)情況下的效率最差效率：算法在最壞情況下的效率平均效率：“典型”或“隨機”輸入的情況下，算法具有的效率算法效率典型情形84算法的上限&下限算法運行時間慢快算法運行的時間上限算法運行的時間下限O表示法Ω表示法Θ表示法同一算法算法分析是為了得知近似的執(zhí)行時間，一般考察的是當問題規(guī)模n增加時，運算所需時間的上下界。85漸進表示法記號記號定義含義O定義：f(n)＝O(g(n))若存在兩個正常數(shù)c和n0，使得當n≧n0時，f(n)≦c*g(n)f(n)的漸進上限為g(n)Ω定義：f(n)＝Ω(g(n))若存在兩個正常數(shù)c和n0，使得當n≧n0時，f（n）≧c*g(n)f(n)的漸進下限為g(n)Θ定義：f(n)＝Θ(g(n))若存在正常數(shù)c1，c2和n0，使得當n≧n0時，c1*g(n)≦f(n)≦c2*g(n)f(n)的漸進確界為g(n)o定義：f(n)＝o(g(n))對任意正常數(shù)c，若存在n0，使得當n≧n0時，f(n)<cg(n)g(n)為f(n)的非緊卻漸進上界ω定義：f(n)＝ω(g(n))對任意正常數(shù)c，若存在n0，使得當n≧n0時，f(n)>cg(n)g(n)為f(n)的非緊卻漸進下界說明：f(n)、g(n)均為非負函數(shù)

86cg(n)f(n)n0f(n)

O(g(n))cg(n)f(n)n0f(n)

Ω(g(n))f(n)

θ(g(n))BigO算法的漸進運行時間記號注：n0、c、c1、c2均為正數(shù)n0c2g(n)f(n)c1g(n)漸進上限漸進下限漸進確界大O符號（BigOnotation）是用于描述函數(shù)漸近行為的數(shù)學符號。它是用另一個（通常更簡單的）函數(shù)來描述一個函數(shù)數(shù)量級的漸近上界。87大O表示法的例子1f(n)=7*2n+n2+n=O(2n)，∵可以找到c=8,n0=4，使得7*2n+n2+n<8*2n

f(n)=10n2+5n+1=O(n2)，∵可以找到c=11,n0=6，使得10n2+5n+1<11n2

f(n)=3n+2=O(n)，∵可找到c=4，n0=2，使得3n+2<4n例88利用極限比較階數(shù)極限值f(n)與g(n)比較結果表示含義存在0f(n)是比g(n)低階的無窮大f(n)＝o(g(n))f(n)在數(shù)量級上嚴格小于g(n)c≤1f(n)與g(n)是同階的無窮大（稱f與g是同數(shù)量級的）f(n)＝O(g(n))f(n)在數(shù)量級上小于等于g(n)c=1f(n)=Θ(g(n))f(n)在數(shù)量級上等于g(n)c≥1f(n)=Ω(g(n))f(n)在數(shù)量級上大于等于g(n)不存在∞f是比g高階的無窮大f(n)=ω(g(n))f(n)在數(shù)量級上嚴格大于g(n)振蕩設f(n)、g(n)是在同一個自變量n的變化過程中的無窮大兩個函數(shù)的比率求極限c為常數(shù)89大O表示法的例子2（3）f(n)=7*2n+n2+n=O(2n)（2）f(n)=10n2+5n+1=O(n2)（1）f(n)=3n+2=O(n)當

n充分大時，該程序的運行時間和n成正比，用O(n)表示；稱f(n)和n是同階的（數(shù)量級相同）。當

n充分大時，該程序的運行時間和n2成正比，用O(n2)表示；稱f(n)和n2是同階的。當

n充分大時，該程序的運行時間和2n成正比，用O(2n)表示；稱f(n)和2n是同階的。例1.7算法性能的事前分析方法1.7.11.7.2問題的規(guī)模與算法的策略算法時間效率的上限與下限1.7.31.7.4漸進的上限——算法的時間復雜度時間復雜度的綜合討論1.7.5算法的空間效率分析方法91時間復雜度

如果O(f(n))是某個算法的語句執(zhí)行次數(shù)f(n)的上限，那么我們可以說此算法的漸進時間復雜度（簡稱時間復雜度)或是執(zhí)行時間為O(f(n))定義92矩陣相乘算法時間復雜度f(n)=O(n3)程序語句頻度f(n)1for(i=1;i<=n;i++)2for(j=1;j<=n;j++)3{c[i][j]=0;4for(k=1;k<=n;k++)5c[i][j]+=a[i][k]*b[k][j]}

n階矩陣相乘算法的時間復雜度分析（C=A*B）例算法的時間復雜度的例子1n+1n(n+1)n2n2(n+1)n3

頻度和

f(n)=2n3+3n2+2n+193時間復雜度結論

算法的漸進分析，關心的是數(shù)據(jù)規(guī)模n逐步增大時資源開銷T(n)的增長趨勢，具體是考察數(shù)量級大小的比較。如果一個算法的最壞情況運行時間的階要比另外一個算法的低，我們就常常認為前者更為有效。結論94例程序段頻度f(n)與規(guī)模n時間復雜度O(f(n))1x=x+1;y=x+2234分析下面各程序段的時間復雜度算法的時間復雜度的例子2for(i=0;i<n;i++)x++;f(n)123…k…f(n)i12222k-12f(n)-1i=i*2222232k2f(n)i=1;while(i<=n)i=i*2;for(i=0;i<n;i++)for(j=0;j<n;j++)x++;O(log2n)2f(n)=nO(n2)f(n)=(n+1)+n*(n+1)+n2O(n)f(n)=2n+1O(1)f(n)=2語句i=i*2執(zhí)行次數(shù)最后一次執(zhí)行：i=n時

2f(n)-1

=

n1.7算法性能的事前分析方法1.7.11.7.2問題的規(guī)模與算法的策略算法時間效率的上限與下限1.7.31.7.4漸進的上限——算法的時間復雜度時間復雜度的綜合討論1.7.5算法的空間效率分析方法算法時間復雜度的實際意義96查找的效率問題對于一組有序的數(shù)列（5,13,19,21,37,56,64,75,80,88,92），如何查找效率更高？數(shù)據(jù)513192137566475808892順序查找次數(shù)1234567891011折半查找次數(shù)34234134234可能的概率pi1/n1*202*213*22i*2i-1561952113^h=1h=2h=3h=[log2n]+1層37^80648875^92^每層查找次數(shù)例一個結點查找成功的平均次數(shù)查找的平均時間復雜度算法時間復雜度的實際意義98算法時間復雜度的實際意義小規(guī)模的輸入在運行時間上的差別不足以將高效的算法和低效的算法區(qū)分開。時間復雜度并不表示一個程序解決問題具體需要花多少時間，而是表示當問題規(guī)模擴大后程序運行需要的時間長度增長得有多快。99對于算法分析具有重要意義的函數(shù)值c<log2n<n<nlog2n<n2<n3<2n<3n<n!從漸進意義上說更有效的算法是基于大規(guī)模輸入的比較對于算法分析具有重要意義的函數(shù)值常數(shù)階對數(shù)階線性階線性對數(shù)階平方階立方階指數(shù)階階乘階O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)O(2n)O(n!)高效算法不可計算多項式級的復雜度非多項式級1001加法準則T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))2乘法準則T(n)=T1(n)*T2(n)=O(f1(n))*O(f2(n))=O(f1(n)×f2(n))3特例情形

算法平均時間復雜度

算法在最壞情況下的時間復雜度時間復雜度的計算規(guī)則設程序段1和程序段2的時間分別為T1(n)和T2(n)，總的運行時間為T(n)——針對并列程序段——針對嵌套程序段——基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關時對于復雜算法，可分成幾個容易估算的部分。102問題的輸入數(shù)據(jù)影響算法效率的情形在數(shù)組A[N]中查找給定值k的算法intsearch（intk）{inti=N-1;//i為要查找的下標

while(i>=0&&A[i]!=k)i--;

returni;}平均情形最壞情形f(n)=nO(f(n))=O(n)f(n)=(1/n)*(1+n)*n/2=(1+n)/2O(f(n))=O(n)時間復雜度的例子基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關？例103算法效率一般性分析方法非遞歸算法決定用哪個(些)參數(shù)作為輸入規(guī)模的度量找出算法的基本操作(作為一個規(guī)律，它總是位于算法的最內(nèi)層循環(huán))檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。如它還依賴一些其他的特性，如輸入順序等，則最差效率、平均效率以及最優(yōu)效率需要分別研究。建立一個算法基本操作執(zhí)行次數(shù)的求和表達式遞歸算法用遞推式的形式來表達基本操作次數(shù)決定用哪些參數(shù)作為輸入規(guī)模的度量找出算法的基本操作檢查一下，對于相同規(guī)模的不同輸入，基本操作的執(zhí)行次數(shù)是否不同。如果不同，則必須對最差效率、平均效率以及最優(yōu)效率作單獨研究對于算法基本操作的執(zhí)行次數(shù)，建立一個遞推關系以及相應的初始條件解這個遞推式，或者至少確定它的解的增長次數(shù)1.7算法性能的事前分析方法1.7.11.7.2問題的規(guī)模與算法的策略算法時間效率的上限與下限1.7.31.7.4漸進的上限——算法的時間復雜度時間復雜度的綜合討論1.7.5算法的空間效率分析方法從空間角度來評價算法——找出算法運行所需的輔助存儲空間特征函數(shù)。105算法的空間效率分析算法空間存儲空間代碼空間：算法本身的存儲空間數(shù)據(jù)空間：輸入／輸出數(shù)據(jù)的存儲空間運行空間算法在運行過程中臨時占用的存儲空間106計算多項式的值算法存儲空間分析的例子1-12函數(shù)結構設計功能描述輸入輸出計算多項式的值evaluate系數(shù)floatcoef[]floatf(x)變量floatx規(guī)模intn函數(shù)名形參函數(shù)類型例107算法存儲空間分析的例子1-12頂部偽代碼描述計算函數(shù)值第一步細化先計算x的冪,存于數(shù)組中,再分別乘以相應的系數(shù)第二步細化intA[N]放x的冪floatcoef[N]放系數(shù)A[0]=1，i=1當i<nA[i]=x*A[i-1];

i++;f=0,i=0;當i<nf=f+coef[i]*A[i];i++;法一108算法存儲空間分析的例子1-12算法一#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;intA[N],i;for(A[0]=1,i=1;i<=n;i++)A[i]=x*A[i-1];/*A[

]放x的冪*/for(f=0,i=0;i<=n;i++)f=f+coef[i]*A[i];return(f);}coef[]屬輸入輸出，為數(shù)據(jù)空間；A[N]為局部量，是輔助空間算法時間復雜度:O(n)空間復雜度：O(n)109算法存儲空間分析的例子1-12頂部偽代碼描述計算函數(shù)值第一步細化從f()最后一項系數(shù)開始逐步乘x，反向處理第二步細化floatcoef[]放系數(shù)n為項數(shù)f=coef[n],i=n-1;當

i>0

f=f*x+coef[i];i--；法二算法存儲空間分析的例子1-12110算法時間復雜度:O(n)空間復雜度：O(1)算法二#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;inti;for(f=coef[n],i=n-1;i>=0;i--)f=f*x+coef[i];return(f);}111算法的空間復雜度定義

S(n)=O(g(n))

其中

n————問題規(guī)模

g(n)————執(zhí)行算法所需的輔助空間算法空間復雜度S(n)空間復雜度含義O(n)表示每個輸入元素都分配到固定的儲存空間。O(1)代表算法需要固定的儲存空間，與輸入量無關若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。例112給出fibonacci數(shù)列前n項的遞歸與非遞歸的算法，試分析它們的算法復雜度。(費氏數(shù)列——fibonacci數(shù)列)fibonacci數(shù)列定義

f0=0；f1=1；fn=fn-1+fn-2(n>=2)遞歸的算法/*遞歸計算斐波那契數(shù)列的第n項*/longFib(longn){ if(n<=1)returnn;//遞歸邊界

elsereturnFib(n-1)+Fib(n-2);//遞歸條件}0,1,1,2,3,5,8,13,21,……算法分析的綜合例子1-13例Fibonacci函數(shù)的遞歸調(diào)用樹Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(2)Fib(1)Fib(1)Fib(1)Fib(0)Fib(0)Fib(1)Fib(0)Fib(1)nT(n)遞歸的運算次數(shù)T(n-1)+T(n-2)+141251595311n…76543210114∴T(n)

Ω(2n/2)∴T(n)

O(2n)∴T(n)>2*T(n-2)又∵T(n-1)>T(n-2)∴T(n)<2*T(n-1)∵T(n-1)>T(n-2)T(n)=T(n-1)+T(n-2)+1<2*2*T(n-2)<2*2*2*T(n-3)<…<2n-1T(n-n+1)=2n-1T(1)=2n-1>2*2*T(n-4)>2*2*2*T(n-6)>…>2n/2T(n-n)=2n/2大O：漸進上限Ω：漸進下限算法分析的綜合例子1-13115Fibonacci數(shù)列通項公式fibonacci數(shù)列定義

f0=0；f1=1；fn=fn-1+fn-2(n>=2)二階線性遞推數(shù)列的特征方程二階線性遞推數(shù)列的通項公式a=1；b=-1；c=-1二階線性遞推數(shù)列的一般形式求得數(shù)列第n項與n的關系Fibonacci數(shù)列通項公式116fibonacci數(shù)列定義

f0=0；f1=1；fn=fn-1+fn-2(n>=2)

∵T(n)=T(n-1)+T(n-2)+1117Fib函數(shù)遞歸算法時間復雜度分析結論T(n)

Ω(2n/2)=Ω(1.414n)T(n)

O(2n)大O：漸進上限Ω：漸進下限Θ

漸進確界T(n)

Θ(1.618n)Fib函數(shù)遞歸算法時間復雜度分析曲線1181.1CONTENTS從編程說起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結構的引入1.4數(shù)據(jù)結構的要素1.5如何設計算法如何評價算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量算法性能的綜合考量120若待解決的問題數(shù)據(jù)量極大，機器的存儲空間較小，則相應算法主要考慮如何節(jié)省空間時間復雜度空間復雜度邏輯復雜度若該程序使用次數(shù)較少，則力求算法簡明易懂；對于反復多次使用的程序，應盡可能選用快速的算法；算法評價角度相互制約時空轉換問題數(shù)據(jù)數(shù)據(jù)處理功能測試：測試樣例設計數(shù)據(jù)引用：數(shù)據(jù)結構描述模塊設計：函數(shù)結構設計算法設計：自頂向下逐步細化程序設計：編碼算法分析：空間時間復雜度分析含義：數(shù)據(jù)元素的連接關系種類：集合、線性、非線性邏輯結構存儲結構運算含義：數(shù)據(jù)存儲到計算機中種類：順序、鏈式、索引、散列存儲原則：存數(shù)值存聯(lián)系；存得進取得出含義：數(shù)據(jù)處理定義：基于數(shù)據(jù)的邏輯結構實現(xiàn)：基于數(shù)據(jù)的存儲結構本章小結本章小結本章小結

數(shù)據(jù)結構三要素是邏輯、存儲與運算：

邏輯結構說的是問題中的數(shù)據(jù)元素如何點點相關聯(lián)；

存儲結構把數(shù)據(jù)值與邏輯關系存放到內(nèi)存的單元；

運算是由算法描述數(shù)據(jù)處理的方案。

一種邏輯關系可以用多種方式來存儲，

“存數(shù)值且存聯(lián)系”，“存得進并取得出”，

存儲兩規(guī)則，設計存的結構時必遵循的法門無二般，

存儲結構不同，則算法效率有快有慢。

算法效率從時間和空間兩個方面看，

復雜度用“大歐”的方法來估算，

用的是算法的漸進上限，和運算規(guī)模n相關。122結點邏輯關系為線性的結構線性表Chapter

2DataStructuresandAlgorithmAnalysis主要內(nèi)容

線性表的邏輯結構定義各種存儲結構的描述方法

在線性表的兩類存儲結構上實現(xiàn)基本操作學習目標掌握線性表的兩類存儲結構及基本操作掌握線性表兩種存儲結構的不同特點及適用場合2.1CONTENTS從邏輯結構角度看線性表線性表的存儲結構方法之一

——順序表線性表的存儲結構方法之二

——鏈表線性表的應用舉例2.22.32.42.52.6順序表和鏈表的比較本章小結2.1CONTENTS從邏輯結構角度看線性表線性表的存儲結構方法之一

——順序表線性表的存儲結構方法之二

——鏈表線性表的應用舉例2.22.32.42.52.6順序表和鏈表的比較本章小結2.1從邏輯結構角度看線性表2.1.12.1.2實際問題中的線性關系線性表的邏輯結構2.1從邏輯結構角度看線性表2.1.12.1.2實際問題中的線性關系線性表的邏輯結構實際問題中的線性關系130排隊中的一對一關系實際問題中的線性關系131密碼表jkhammotmoyznkvxuikyyulxksubotmyulzcgxkhamycharcode[27]="baefkilcjgdmqzhyoptxvrnwus";明碼ABCDEFGHIJKLMNOPQRSTUVWXYZ密碼BAEFKILCJGDMQZHYOPTXVRNWUSEBKTBPCAESAR截獲敵方情報一份字符串——各字符先后有特定順序凱撒實際問題中的線性關系132客戶姓名電話身份證號地址張1138*****6101131980******李2152*****6101131981******王1139*****6101131990******張2139*****6101131972******李1188*****6101131976******………一個數(shù)據(jù)元素或一個結點電話號碼表結構2.1從邏輯結構角度看線性表2.1.12.1.2實際問題中的線性關系線性表的邏輯結構線性表的邏輯結構134一個線性表是n(n≥0)個同類型結點的有限序列。記作：(a1

a2…ai…an)其中：ai————表示一個結點（1≤i≤n）。

n——線性表長度。n=0時為空表。定義線性表的邏輯結構135a1a2a3a4an……開始結點終端結點線性表結點之間具有先后的、線性的、一維的關系中間結點只有一個前趨和一個后繼結點線性表的主要操作136初始化

給線性表相關參數(shù)賦初值求長度

求線性表的元素個數(shù)取元素

取給定位置的元素值定位

查找給定元素值的位置插入

在指定位置插入給定的值刪除

刪除指定位置的值或給定的值遍歷

從頭到尾掃描線性表，做指定的操作2.1CONTENTS從邏輯結構角度看線性表線性表的存儲結構方法之一

——順序表線性表的存儲結構方法之二

——鏈表線性表的應用舉例2.22.32.42.52.6順序表和鏈表的比較本章小結138線性表中的元素相依次放在一個連續(xù)的存儲空間中順序表2.2線性表的存儲結構方法之一——順序表2.2.12.2.2順序表的存儲結構設計順序表的運算2.2.3順序表運算的討論2.2線性表的存儲結構方法之一——順序表2.2.12.2.2順序表的存儲結構設計順序表的運算2.2.3順序表運算的討論順序表的存儲結構設計141012345a0a1a2a3a4a5存數(shù)值存聯(lián)系Ba1a2a0a3a4a5數(shù)值存儲了，聯(lián)系存儲了嗎？線性表結點邏輯特征：一一順序對應物理地址相鄰體現(xiàn)邏輯關系相鄰用數(shù)組存儲線性表，稱作線性表的順序存儲結構或順序映像，用這種方法存儲的線性表稱作順序表。142線性表的順序存儲結構——順序表定義

無論位于數(shù)組的什么位置，都能用相等的常量時間訪問存儲區(qū)中的任何元素。隨機存取下標01...k-1kk+1...n-1元素a1a2...ai-1aiai+1...an邏輯上相鄰對應物理地址相鄰任一元素均可隨機存取順序表存儲結構的設計143數(shù)組下標a1

a2

an

01n-112n內(nèi)存元素序號LIST_SIZE-1備用空間last怎樣設計順序表的結構，才能完整描述整個順序表信息？思考&討論考慮線性表所有可能的情形順序表存儲結構的設計144數(shù)組下標a1

a2

an

01n-112n內(nèi)存元素序號LIST_SIZE-1備用空間last怎樣設計順序表的結構，才能完整描述整個順序表信息？思考&討論考慮線性表所有可能的情形順序表存儲結構的設計145typedefintElemType;

//假定線性表元素的類型為整型#defineLIST_SIZE1024

//假定線性表的最大長度為1024typedefstruct{ElemTypedata[LIST_SIZE];

intlast;//指向最后結點的位置}SequenList;sequential:[si‘kwin??l]a.連續(xù)的(序貫的)list:[list]n.目錄,名單,明細表數(shù)組下標a1

a2

an

01n-112n內(nèi)存元素序號LIST_SIZE-1備用空間lastSequenList*LPtr；

//指向SequenList結構的指針結構描述

146例：typedefintElemType;【知識ABC】typedef————為類型取一個新名稱typedef是C語言的關鍵字，用于在原有數(shù)據(jù)類型（包括基本類型、構造類型和指針等）的基礎上，由用戶自定義新的類型名稱。typedef已有類型名

新命名的類型別名;簡化類型聲明提高程序可移植性關于結構類型應用的思考與討論typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;147這樣的結構描述，系統(tǒng)會分配空間嗎？Q1148SequenListL；SequenList*L；二者有什么區(qū)別？系統(tǒng)怎樣分空間？結構類型的定義——類型是存儲空間尺寸的描述結構變量的定義——按類型尺寸大小分配存儲空間結構指針——指向單元放的是結構類型的數(shù)據(jù)，指針變量本身占一個int的空間Q2typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;149定義了結構變量L后，順序表中的結點如何表示？SequenListL；L.data[0]=a1;X=L.last;

結構成員引用方法1：結構變量

結構成員a1

a2

an

01n-1內(nèi)存lastQ3用指針p指向結構空間后，其中的結點怎么用p表示？typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;150SequenListL；Sequenlist*p=&L；p->data[0]=a1;X=p->last;

結構成員引用方法2：結構指針

結構成員a1

a2

an

01n-1內(nèi)存lastQ4

typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}ElemType;編號書名作者出版社價格151

當結點內(nèi)容有多個數(shù)據(jù)項，而不是基本類型int時，怎么辦？typedefintElemType;typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;a1

a2

an

01n-1內(nèi)存lastQ52.2線性表的存儲結構方法之一——順序表2.2.12.2.2順序表的存儲結構設計順序表的運算2.2.3順序表運算的討論順序表的主要操作153初始化

給線性表相關參數(shù)賦初值求長度

求線性表的元素個數(shù)取元素

取給定位置的元素值定位

查找給定元素值的位置插入

在指定位置插入給定的值刪除

刪除指定位置的值或給定的值遍歷

從頭到尾掃描線性表，做指定的操作順序表插入運算——定義在線性表第i個（1

i

n+1）元素之前插入一個結點x，使長度為n的線性表

(a1，…ai-1，ai，…，an)變成長度為n+1的線性表

(a1，…ai-1，x，ai，…，an)154定義需將第i至第n共（n-i+1)個元素后移插入的位置，可以是指定的下標位置，也可以是指定的值之前，我們在此按前一種要求設計算法。順序表插入運算——定義1550a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

data[LIST_SIZE]移動元素的個數(shù)：last-k+10a11a2……k-1ai-1kXk+1ai…ai+1…an-1lastan…LIST_SIZE-1

插入前插入后數(shù)組下標特地用k表示，以與元素標號i區(qū)別順序表插入運算——測試樣例設計156

一般情形邊界值異常情形插入的下標位置k0≤k≤nk=0,n!(0≤k≤n)順序表未滿未滿已滿或未滿預期結果插入成功插入成功插入失敗

順序表插入運算——函數(shù)結構設計157功能描述輸入輸出順序表元素的插入Insert_SqList順序表地址(SequenList*)完成標志(int)0：異常插入值(ElemType)1：正常插入位置(int)函數(shù)名形參函數(shù)類型順序表插入運算——數(shù)據(jù)結構描述158SequenList結構ElemTypedata[LIST_SIZE]intlast順序表的地址：

SequenList*LPtr要插入的結點值x：ElemTypex插入的位置i：intiLPtrtypedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;0a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

data[LIST_SIZE]LPtr結構描述

159順序表插入運算——算法描述在順序表中第i個位置插入新元素x第一步細化異常情形處理，返回不成功處理標志在順序表中移動元素，空出下標為k的位置插入新元素x修改元素最后位置指針返回成功處理標志頂部偽代碼描述在順序表中第i個位置插入新元素x問題順序表插入運算——算法描述160第一步細化第二步細化異常情形處理返回不成功處理標志若順序表溢出，則return0;若k是非法位置，則return0;在順序表中移動元素，空出下標為k的位置從順序表的最后一個元素起向后移動(last–k+1)個元素插入新元素x將x放入表的k位置修改元素最后位置指針Last+1返回成功處理標志return1在順序表中第i個位置插入新元素x問題161第二步細化若k是非法位置，則return0;若順序表溢出，則return0;從順序表的最后一個元素起向后移動(last–k+1)個元素將x放入表的k位置Last+1return1第三步細化if(LPtr->last>=LIST_SIZE－1)return0;if(k<0||k>(LPtr->last＋1))return0;j=LPtr->last;當

j>=kLPtr->data[j+1]=LPtr->data[j];j--;LPtr->data[k]=x;LPtr->last=LPtr->last+1;return10a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

順序表插入運算——程序實現(xiàn)162/*===========================================函數(shù)功能：順序表運算——元素的插入函數(shù)輸入：順序表地址，插入值，插入位置函數(shù)輸出：完成標志——0：異常1：正常=============================================*/intInsert_SqList(SeqList*LPtr,ElemTypex,intk){intj;if(LPtr->last>=LIST_SIZE-1)returnFALSE; //溢出

elseif(k<0||k>(LPtr->last+1))returnFALSE; //非法位置

else{for(j=LPtr->last;j>=k;j--) //從順序表的最后一個元素起

{LPtr->data[j+1]=LPtr->data[j];//向后移動(last-k)個元素}LPtr->data[k]=x; //將x放入表的k位置

LPtr->last=LPtr->last+1; //修改最后結點指針last}returnTRUE;}順序表插入運算——算法效率分析a1a2…aia1a2…xa1a2…ai+1…aiai+1…xaiai+1…an…anx…a1a2…aiai+1…an…a1a2…aiai+1…an…a1a2…aiai+1…an…an…O(1)O(n)O(?)最好情況最壞情況一般情況順序表插入運算——算法效率分析164在第k個位置上插入一個結點的移動次數(shù)每一點插入概率Pk均等=1/(n+1)插入下標位置k012...k...n-1n移動次數(shù)nn-1n-2...n-k...10算法的平均時間復雜度為O(n)移動元素的平均次數(shù)在順序表上做插入運算，平均要移動表上一半元素順序表刪除運算——定義165將線性表的第i(1≦i≦n)個結點刪除，使長度為n的線性表：

(a1，…ai-1，ai，ai+1…，an)

變成長度為n-1的線性表

(a1，…ai-1，ai+1，…，an)定義設第i個結點對應下標為k，則需將第k+1至last共last-k個元素前移。順序表刪除運算——定義166刪除前刪除后0a11a2……k-1ai-1kaik+1ai+1k+2ai+2…an-1lastan…

data[LIST_SIZE]0a11a2……k-1ai-1kai+1k+1ai+2…an-2lastan-1…

移動元素的個數(shù)：last-(k+1)+1=last-kLIST_SIZE-1LIST_SIZE-1順序表刪除運算——測試樣例設計

一般情形邊界值異常情形刪除下標位置k0≤k≤n-1k=0,n-1!(0≤k≤n-1)順序表非空空非空空非空空預期結果刪除成功刪除失敗刪除成功刪除失敗刪除失敗刪除失敗輸入：順序表的地址，要刪除的結點下標位置k輸出：操作是否成功標志順序表刪除運算