1、第一講：數(shù)據(jù)結構及其研究的內容Data Structure Curriculum int age; bool sex; char position20; char pos_rank20; char department20; RecordType ;,數(shù)據(jù)在計算機中表示方式： 順序映像（順序存儲結構）：以相 對的存儲位置表示后繼 關系。如前述的職工檔案管理程序，所有職工的紀錄組成一張表，這張表就使一個順序存儲結構。計算機在為這張表分配存儲空間時分配一個連續(xù)的存儲空間。 非順序映像（鏈式存儲結構）：,鏈式存儲結構里相鄰節(jié)點間的具體存儲位置不是一個順序關系，查詢節(jié)點需要借助于指針。 在不同的編程環(huán)

2、境中， 存儲結構可有不同的描 述方法。當用高級程序 設計語言進行編程時， 通常可用高級編程語言 中提供的數(shù)據(jù)類型描述 之。,5、數(shù)據(jù)類型： 在程序設計時，我們必須先對變量進行聲明，不同的數(shù)據(jù)類型他的取值范圍不同，施加其上的操作也不同： 如：整型 （int） 取值范圍：-32768 32767 可行的操作：+，-，*，/，% 對于浮點型來說，不可以進行% 操作。,數(shù)據(jù)類型 是一個值的集合和定義在此集合上的一組操作的總稱。 盡管同一個數(shù)據(jù)類型在不同的CPU上處理的方法不同，對程序原來說他們是相同的，程序員可以不考慮具體機器的實現(xiàn)方法。也就是說這些數(shù)據(jù)類型僅僅取決于它的邏輯特性，與在計算機內的實現(xiàn)無

3、關。在數(shù)學抽象的角度上看可以稱之為抽象數(shù)據(jù)類型。,抽象數(shù)據(jù)類型： （Abstract Data Type ：ADT） 抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定義在該模型上的一組操作。 抽象數(shù)據(jù)類型可以用一個三元組來表示：（D，S，P） D是數(shù)據(jù)對象，S是D上的關系集，P是D的基本的操作集 。,ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關系：數(shù)據(jù)關系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名 如：定義復數(shù)的抽象數(shù)據(jù)類型,ADT Complex 數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)關系： R1 | e1是復數(shù)的實數(shù)部分, e2 是復 數(shù)的虛數(shù)部分 基本操作：

4、AssignComplex( for(int i=0;in;i+) s+=i; 問題的規(guī)模是n,程序的運算工作量和n成線性的增長關系 ，或者說它可以看作是n的函數(shù)f(n)。,隨著規(guī)模的增大，算法執(zhí)行所需要的時間的增長率和f(n)的增長率是相同的。用時間復雜度來表示算法的時間效率， T (n) = O(f(n) 稱T (n) 為算法的(漸近)時間復雜度,如何估算時間復雜度？ 算法 = 控制結構 + 原操作 （固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時間 = 原操作的執(zhí)行次數(shù)原操作的執(zhí)行時間,算法的實行時間和原操作的執(zhí)行次數(shù)是成正比的。從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在

5、算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則。,如上例中，時間復雜度為O(n) 例： （a） +x;s+=x; （b）for (i=1;i=n;+i) +x;s+=x; （c）for (j=1;j=n;+j) for (k=1;k=n;k+)+x;s+=x; 基本操作： +x;s+=x; a的執(zhí)行次數(shù)：1 時間復雜度O(1) b的實行次數(shù)：n 時間復雜度O(n) c的執(zhí)行次數(shù)：n2 時間復雜度O(n2),例：兩矩陣相乘 #define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i=n;+i) n+1 for (j=1;j=n;+j) n*(n+1) Cij=0; n2 for (k=1;k=n,k+) n2(