數(shù)據(jù)結(jié)構(gòu)?？齐娮咏贪敢徽n件

1、數(shù) 據(jù) 結(jié) 構(gòu)數(shù) 據(jù) 結(jié) 構(gòu) 第一章 緒論 第一章 緒論數(shù)據(jù)結(jié)構(gòu)討論的范疇 :非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題算法數(shù)據(jù)結(jié)構(gòu)討論的范疇 :非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題算法 數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。數(shù)據(jù)結(jié)構(gòu)課程介紹和研究數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)和處理的方法。 數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非1.1 常用術(shù)語(yǔ)數(shù)據(jù)(Data): 人們利用文字符號(hào),數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的抽象描述. 是能夠被計(jì)算機(jī)輸入，存儲(chǔ)，處理和輸出的信息。1.1 常用術(shù)語(yǔ)數(shù)據(jù)(Data): 人們利用文字符號(hào), 簡(jiǎn)稱元素,

2、它是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位. 即:數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位數(shù)據(jù)元素（Data Element): 簡(jiǎn)稱元素,它是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位.數(shù)據(jù)元素（D 數(shù)據(jù)紀(jì)錄(Data Record) 簡(jiǎn)稱記錄,它是數(shù)據(jù)處理領(lǐng)域組織數(shù)據(jù)的基本單位。 數(shù)據(jù)項(xiàng)(Item) 關(guān)鍵項(xiàng)(Key Item) 關(guān)鍵字(Key Word , Key) 數(shù)據(jù)紀(jì)錄(Data Record) 數(shù)據(jù)結(jié)構(gòu) ( Data Structure) ： 是指數(shù)據(jù)及其相互之間的聯(lián)系或者說(shuō)，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu) ( Data Structure) ： 數(shù)據(jù)之間的相

3、互聯(lián)系，被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，一種數(shù)據(jù)結(jié)構(gòu)在存儲(chǔ)器中的存儲(chǔ)方式稱為數(shù)據(jù)的物理結(jié)構(gòu)（順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)）。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)： 數(shù)據(jù)之間的相互聯(lián)系，被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，一種數(shù)順序存儲(chǔ) : 用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素 x1 x2 x3 順序存儲(chǔ) : 用一組地址連續(xù)的存儲(chǔ)單元 x1 x2 鏈?zhǔn)酱鎯?chǔ): 以附加信息(指針)表示后繼關(guān)系需要用一個(gè)和 x 在一起的附加信息指示 y 的存儲(chǔ)位置。a1a2a3鏈?zhǔn)酱鎯?chǔ): 以附加信息(指針)表示后繼關(guān)系需要用一個(gè)和 數(shù)據(jù)結(jié)構(gòu)的描述： 二元組表示: 數(shù)據(jù)結(jié)構(gòu) B= ( K , R ) R = | ku , kvK 對(duì)于R中的

4、任一序偶,x叫做序偶第一 元素(前驅(qū)),y叫做序偶的第二元素(后繼)。 圖表示 : 數(shù)據(jù)結(jié)構(gòu)的描述：例 畫(huà)出二元組 (K，R)的圖形表示 其中K=01,02,03,04,05,06,07,08,09,10R=,01040602050703080910例 畫(huà)出二元組 (K，R)的圖形表示 010406020典型的數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類(lèi):線性結(jié)構(gòu)( 1:1聯(lián)系）樹(shù)形結(jié)構(gòu)( 1:N聯(lián)系）圖狀結(jié)構(gòu) ( M:N聯(lián)系） 集合結(jié)構(gòu)(關(guān)系R= ）典型的數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類(lèi):線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu) ( 數(shù)據(jù)類(lèi)型( Data Type) 是對(duì)數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)以及允許施加操作的一種描述?？煞譃?/p>

5、簡(jiǎn)單類(lèi)型和結(jié)構(gòu)類(lèi)型兩種.簡(jiǎn)單類(lèi)型：整數(shù)、實(shí)數(shù)、字符、指針、枚舉量等。結(jié)構(gòu)類(lèi)型：數(shù)組、記錄、字符串、文件等。 數(shù)據(jù)類(lèi)型( Data Type)簡(jiǎn)單類(lèi)型：整數(shù)、實(shí)數(shù)、一維和二維數(shù)組的元素地址計(jì)算： 一維數(shù)組 an:元素 ai的存儲(chǔ)位置為： Address (ai)=a+i*L （0in-1） 二維數(shù)組 bmn : 行元素 bi的存儲(chǔ)位置為： Address(bi)=b+i*n*L (0im-1)元素 bij的存儲(chǔ)位置為： Address (bij)=b+i*n*L+j*L (0im-1,0jn-1) 其中L表示數(shù)組中元素類(lèi)型的大小一維和二維數(shù)組的元素地址計(jì)算：抽象數(shù)據(jù)類(lèi)型( Abstract Da

6、ta Type 簡(jiǎn)稱 ADT ) 由一組數(shù)據(jù)結(jié)構(gòu)和在該組數(shù)據(jù)結(jié)構(gòu)上的一組操作所組成。也可以被定義為由一組數(shù)據(jù)和在該數(shù)據(jù)上的一組操作所組成。抽象數(shù)據(jù)類(lèi)型 由一組數(shù)據(jù)結(jié)構(gòu)和在該組數(shù)據(jù)結(jié)構(gòu)上的一組操 本課程中，為了便于敘述和分析數(shù)據(jù)結(jié)構(gòu)與算法，在實(shí)現(xiàn)所定義的抽象數(shù)據(jù)類(lèi)型時(shí)，把數(shù)據(jù)部分用 struct 結(jié)構(gòu)類(lèi)型來(lái)描述，把操作部分中的每個(gè)操作用外部函數(shù)（即普通函數(shù)）來(lái)描述。注： 本課程中，為了便于敘述和分析數(shù)據(jù)結(jié)構(gòu)與算 在本課程中，定義一種抽象數(shù)據(jù)類(lèi)型采用如下書(shū)寫(xiě)格式： ADT is Data: Operations: end 在本課程中，定義一種抽象數(shù)據(jù)類(lèi)ADT RECtangle is Data:

7、float length , width ； Operations: void InitRectangle (Rectangle& r , float len , float wid ); float Circumference (Rectangle& r ); float Area (Rectangle& r );end RECtangle例：對(duì)于矩形定義一種抽象數(shù)據(jù)類(lèi)型，其數(shù)據(jù)部分包括矩形的長(zhǎng)度和寬度，操作部分包括初始化矩形的尺寸，求矩形的周長(zhǎng)和求矩形的面積。 struct Rectangle float length , width ; ;ADT RECtangle is例：對(duì)于矩形定義

8、一種抽void Initrectangle (Rectangle& r, float len, float wid) r.length=len; r.width=wid; /初始化矩形數(shù)據(jù)函數(shù)float Circumference (Rectangle& r) returm 2 * (r.length+r.Width); /求矩形周長(zhǎng)函數(shù)float Area (Rectangle& r) return r.length * r.width; /求矩形面積函數(shù)void Initrectangle (Rectangle 數(shù)據(jù)對(duì)象（Data Object)：簡(jiǎn)稱對(duì)象，它屬于一種數(shù)據(jù)類(lèi)型中的特定實(shí)例。

9、 算法（Algorithm) ：是對(duì)解決某類(lèi)問(wèn)題的方法的一種描述。 一個(gè)算法必須具備以下五個(gè)特性：（1）有窮性 （2）確定性 （3）可行性（4）有輸入（5）有輸出 數(shù)據(jù)對(duì)象（Data Object)：簡(jiǎn)稱對(duì)象，它1.2 算法描述1.2.1 包含文件語(yǔ)句1. # include 標(biāo)準(zhǔn)輸入設(shè)備（鍵盤(pán)）流對(duì)象 cin ;標(biāo)準(zhǔn)輸出設(shè)備（屏幕）流對(duì)象 cout ;標(biāo)準(zhǔn)錯(cuò)誤輸出設(shè)備（屏幕）流對(duì)象 cerr ;用于輸入的提取操作符 ;用于輸出的插入操作符 和 (istream& istr, struct_type& x) istr x.成員1 x.成員2 x.成員n ; return istr;ostrea

10、m& operater (ostream& istr, struct_type& x) ostr x.成員1 “ ” x.成員2 “ ” x.成員n x1cout 和2. # include void exit(int) ； int rand(void) ； void srand(unsigned) ；3. # include 輸入文件流類(lèi) ifstream； 輸出文件流類(lèi) ofstream； 輸入輸出文件流類(lèi) fstream。 例如： ifstream input 1(“a1.dat” , ios: in | ios: nocreate)；2. # include vo4. # includ

11、e int strlen(const char* s); /求串長(zhǎng)度 char* strcpy(char* dest,const char* src); /串拷貝 char* strcat(char* dest,const char* src); /串連接 int strcmp(const char* s1,const char* s2); /串比較 char* strchr(const char* s , int c); /串定位 char* strchr(const char* s , int c); /串右定位 char* strstr(const char* s1,const char

12、* s2);/查找子串ofstream input 2(“a2.dat” , ios: out )；ofstream input 3(“a3.dat” , ios: app )；fstream input 4(“a4.dat” , ios: in | ios: out )；4. # include i1.2.2 函 數(shù)例：不同返回類(lèi)型的三個(gè)重載函數(shù)引用參數(shù)與值參數(shù)： 值參數(shù)：具有自己的存儲(chǔ)空間，內(nèi)容的改變不會(huì)影響到對(duì)應(yīng)的實(shí)在參數(shù)。 引用參數(shù)：和實(shí)在變量參數(shù)具有同一存儲(chǔ)位置，對(duì)引用參數(shù)的讀寫(xiě)操作實(shí)際上就是對(duì)相應(yīng)實(shí)參變量的讀寫(xiě)操作，對(duì)引用參數(shù)的改變將反映給對(duì)應(yīng)的實(shí)參變量。1.2.2 函 數(shù)例：不同

13、返回類(lèi)型的三個(gè)重載函數(shù)引用參數(shù)與例：void swap1(int a,int b) int t; t = a; a = b; b = t;void swap2 (int& a,int& b) int t ; t = a; a = b; b = t; 設(shè)x,y是兩個(gè)整數(shù)變量，那么調(diào)用函數(shù)swap1(x,y)將不改變x,y的值，而調(diào)用函數(shù)swap2(x,y)將交換x,y的數(shù)值。例：void swap1(int a,int b)void1.23 運(yùn)算符重載 對(duì)于自定義的結(jié)構(gòu)類(lèi)型，需要對(duì)關(guān)系運(yùn)算符進(jìn)行重載，使得記錄同記錄之間、記錄同其中一個(gè)域類(lèi)型的數(shù)據(jù)之間也能夠進(jìn)行比較。 如下例所示：1.23 運(yùn)算符

14、重載 對(duì)于自定義的結(jié)構(gòu)類(lèi)型，需struct pupil char pnum 8; int grade;bool operator = =(pupil& r1 ,pupil& r2) if (strcmp(r1.pnum ,r2.pnum)= =0) return true; else return false;bool operator = =(pupil& r ,char* key) if (strcmp(r.pnum ,r2.key)= =0) return true; else return false;bool operator (pupil& r1 ,pupil& r2) retur

15、n r1.grade r2.grade;bool operator (pupil& r,int key) return r.grade key;struct pupil char 1.3 算法評(píng)價(jià)1.正確性 ( Correctness )2. 健壯性 ( Robustness )3. 可讀性 ( Readability )4. 時(shí)間復(fù)雜度 ( Time Complexity ) 又稱計(jì)算復(fù)雜度( Computational Complexity )5.空間復(fù)雜度 ( Space Complexity )1.3 算法評(píng)價(jià)1.正確性 ( Correctness ) 隨著問(wèn)題規(guī)模 n 的增長(zhǎng)，算法執(zhí)

16、行時(shí)間 f(n) 的增長(zhǎng)率和 g(n)的增長(zhǎng)率相同。 即：存在n0，當(dāng)n n0時(shí)，存在兩個(gè)正的常數(shù)A和B,使得 Af(n)/g(n) B均成立。f (n) = O(g(n) 時(shí)間復(fù)雜度的數(shù)量級(jí)形式表示 : 隨著問(wèn)題規(guī)模 n 的增長(zhǎng)，算法執(zhí)行時(shí)間 f(n例：算法1:（累加求和）int Sum ( int b ,int n ) int s=0; for ( int i=0 ; in ; i+) s+=bi ; 算法 1的時(shí)間復(fù)雜度為O(n)算法2:(矩陣相加）void MatrixAdd ( int aMSMS ,int bMSMS , int cMSMS ,int n ) int i, j; f

17、or ( int i=0 ; in ; i+) for (j=0 ; jn ; j+) cij = aij+bij ; 算法 2 的時(shí)間復(fù)雜度為O(n2)算法3:（簡(jiǎn)單選擇排序）Void SelectSort ( int b , int n ) int i , j , k , x ; for ( int i=0 ; in -1 ; i+) k=i ; for (j=i+1 ; j n ; j+) if ( bi bk ) k = j ; x=bi ; bi = bk ; bk = x ; 算法 3的時(shí)間復(fù)雜度的數(shù)量級(jí)為O(n2)例：算法1:（累加求和）算法2:(矩陣相加）算法3:（簡(jiǎn)單選如：某程序的時(shí)間復(fù)雜度為：10log2n+ nlog2n+100則數(shù)量級(jí)表示為 O(nlog2n) O(log2n) O(n) O(n*log2n) O(n2) O(n3) O(2n) O(n!) 時(shí)間復(fù)雜度的各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在如下關(guān)系：如：某程序的時(shí)間復(fù)雜度為：O(log2n) O(n) int SequenceSearch( int a , int