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

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

主講人：孫挺博士

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)開辟一個(gè)新時(shí)代信息時(shí)代產(chǎn)生一門新學(xué)科計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科造就一種新文化計(jì)算機(jī)文化形成一個(gè)新產(chǎn)業(yè)信息產(chǎn)業(yè)60多年的發(fā)展，計(jì)算機(jī)對(duì)社會(huì)發(fā)展有著廣泛而深遠(yuǎn)的影響，其應(yīng)用要求也顯著提高開創(chuàng)一個(gè)新科研方法計(jì)算方法存儲(chǔ)程序輸入數(shù)據(jù)輸出結(jié)果數(shù)據(jù)處理計(jì)算機(jī)工作流程：計(jì)算機(jī)化的信息用計(jì)算機(jī)語(yǔ)言描述的算法控制信息素質(zhì)和創(chuàng)新能力培養(yǎng)培養(yǎng)模式程序設(shè)計(jì)教學(xué)模式基礎(chǔ)訓(xùn)練提高能力拓展層面

實(shí)踐應(yīng)用

計(jì)算機(jī)程序設(shè)計(jì)課程體系大學(xué)生信息素質(zhì)與創(chuàng)新能力培養(yǎng)模式基本思路基礎(chǔ)訓(xùn)練

提高能力

拓展層面

課程體系程序設(shè)計(jì)基礎(chǔ)訓(xùn)練課入門課程基本技能

程序設(shè)計(jì)能力提高課典型的程序設(shè)計(jì)方法構(gòu)造性思維的訓(xùn)練抽象能力的培養(yǎng)

實(shí)踐應(yīng)用訓(xùn)練

增設(shè)課程設(shè)計(jì)參加科研訓(xùn)練系統(tǒng)級(jí)深層次應(yīng)用

實(shí)踐應(yīng)用

工具與應(yīng)用環(huán)境拓展訓(xùn)練增強(qiáng)掌握新工具的能力提高適應(yīng)新環(huán)境程序設(shè)計(jì)能力

數(shù)據(jù)結(jié)構(gòu)課程的地位——針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作?！墙橛跀?shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。關(guān)系對(duì)象關(guān)系操作數(shù)學(xué)軟件硬件對(duì)象關(guān)系操作Data_Structure=（D,R）數(shù)據(jù)結(jié)構(gòu)教程－采用C#語(yǔ)言描述李春葆、尹為民、蔣晶玨、喻丹丹、安楊編著清華大學(xué)出版社2013第1章緒論

數(shù)據(jù)結(jié)構(gòu)課程通過介紹一些典型數(shù)據(jù)結(jié)構(gòu)的特性來討論基本的數(shù)據(jù)組織和數(shù)據(jù)處理方法。目的：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本概念和必要的基礎(chǔ)知識(shí)。理解邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算的關(guān)系。學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，掌握常用的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)并能正確地選擇數(shù)據(jù)結(jié)構(gòu)。為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，并能設(shè)計(jì)出較高質(zhì)量的算法。1.1什么是數(shù)據(jù)結(jié)構(gòu)1.1.1數(shù)據(jù)結(jié)構(gòu)的定義用計(jì)算機(jī)解決一個(gè)具體的問題時(shí)，大致需要經(jīng)過以下幾個(gè)步驟：（1）分析問題，確定數(shù)據(jù)模型。（2）設(shè)計(jì)相應(yīng)的算法。（3）編寫程序，運(yùn)行并調(diào)試程序直至得到正確的結(jié)果。

數(shù)據(jù)是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。例如，A班學(xué)生數(shù)據(jù)包含了該班全體學(xué)生記錄。通常以數(shù)據(jù)元素作為數(shù)據(jù)的基本單位（例如，A班中的每個(gè)學(xué)生記錄都是一個(gè)數(shù)據(jù)元素），也就是說數(shù)據(jù)元素是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理，有些情況下數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、記錄等。有時(shí)候，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)最小單位，也稱為字段或域（例如，A班中每個(gè)數(shù)據(jù)元素即學(xué)生記錄是由學(xué)號(hào)、姓名、性別和班號(hào)等數(shù)據(jù)項(xiàng)組成）。數(shù)據(jù)對(duì)象是性質(zhì)相同的有限個(gè)數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個(gè)子集，如：大寫字母數(shù)據(jù)對(duì)象是集合C={‘A’,’B’,’C’,…，’Z’}；

1～100的整數(shù)數(shù)據(jù)對(duì)象是集合N={1,2,…,100}。默認(rèn)情況下，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)都指的是數(shù)據(jù)對(duì)象。

數(shù)據(jù)結(jié)構(gòu)是指所有數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系，可以看作是相互之間存在著特定關(guān)系的數(shù)據(jù)元素的集合，因此，可時(shí)把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)方面：（1）數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)，它是數(shù)據(jù)結(jié)構(gòu)在用戶面前呈現(xiàn)的形式。（2）數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。（3）施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算。1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是用戶根據(jù)需要建立起來的數(shù)據(jù)組織形式，它反映數(shù)據(jù)元素之間的邏輯關(guān)系而不是物理關(guān)系，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)中數(shù)據(jù)元素之間可以有不同的邏輯關(guān)系。

【例1.1】

一個(gè)學(xué)生高等數(shù)學(xué)成績(jī)單如表1.1所示。這個(gè)表中的數(shù)據(jù)元素是學(xué)生成績(jī)記錄，每個(gè)數(shù)據(jù)元素由3個(gè)數(shù)據(jù)項(xiàng)（即學(xué)號(hào)、姓名和分?jǐn)?shù)）組成。討論其邏輯結(jié)構(gòu)特性。學(xué)號(hào)姓名分?jǐn)?shù)2011001王華902011010劉麗622011006陳明542011009張強(qiáng)952011007許兵762011012李萍882011005李英82表1.1高等數(shù)學(xué)成績(jī)單

解：該表中的每一行稱為一個(gè)記錄，其邏輯結(jié)構(gòu)特性是，只有一個(gè)開始記錄（即姓名為王華的記錄）和一個(gè)終端記錄（也稱為尾記錄，即姓名為李英的記錄），其余每個(gè)記錄只一個(gè)前驅(qū)記錄和一個(gè)后繼記錄，也就是說，記錄之間存在一對(duì)一的關(guān)系。將具有這種邏輯特性的邏輯結(jié)構(gòu)稱為線性結(jié)構(gòu)。

【例1.2】

某高校組織結(jié)構(gòu)示意圖如圖1.1所示。高校下設(shè)若干個(gè)學(xué)院和若干個(gè)處，每個(gè)學(xué)院下設(shè)若干個(gè)系，每個(gè)處下設(shè)若干個(gè)科或辦公室。討論其邏輯結(jié)構(gòu)特性。圖1.1某高校組織結(jié)構(gòu)示意圖

解：該圖中每個(gè)長(zhǎng)方形框表示一個(gè)結(jié)點(diǎn)，其邏輯結(jié)構(gòu)特性是，只有一個(gè)開始結(jié)點(diǎn)（即大學(xué)名稱結(jié)點(diǎn)），有若干個(gè)終端結(jié)點(diǎn)（如科學(xué)系等），每個(gè)結(jié)點(diǎn)對(duì)應(yīng)零個(gè)或多個(gè)結(jié)點(diǎn)（終端結(jié)點(diǎn)對(duì)應(yīng)零個(gè)結(jié)點(diǎn)），也就是說，結(jié)點(diǎn)之間存在一對(duì)多的關(guān)系。將具有這種邏輯特性的邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。

【例1.3】

全國(guó)部分城市交通線路圖如圖1.2所示。討論其邏輯結(jié)構(gòu)特性。圖1.2全國(guó)部分城市交通線路圖

解：該圖中每個(gè)城市表示一個(gè)結(jié)點(diǎn)，其邏輯結(jié)構(gòu)特性是，每個(gè)結(jié)點(diǎn)和一個(gè)或多個(gè)結(jié)點(diǎn)相聯(lián)。也就是說，結(jié)點(diǎn)之間存在多對(duì)多的關(guān)系。將具有這種邏輯特性的邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。歸納起來，數(shù)據(jù)的邏輯結(jié)構(gòu)有4種：集合：數(shù)據(jù)元素沒有任何相鄰關(guān)系。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)為了更通用地描述數(shù)據(jù)的邏輯結(jié)構(gòu)，通常采用二元組表示數(shù)據(jù)的邏輯結(jié)構(gòu)，一個(gè)二元組如下：

B=(D,R)其中，B是一種數(shù)據(jù)結(jié)構(gòu)，D是數(shù)據(jù)元素的集合，在D上數(shù)據(jù)元素之間可能存在多種關(guān)系，R是所有關(guān)系的集合。即：

D={di|1≤i≤n，n≥0}

R={rj|1≤j≤m，m≥0}其中di表示集合D中的第i（1≤i≤n）個(gè)數(shù)據(jù)元素（或結(jié)點(diǎn)），n為D中數(shù)據(jù)元素的個(gè)數(shù)，特別地，若n=0，則D是一個(gè)空集，此時(shí)B也就無結(jié)構(gòu)可言。rj（1≤j≤m）表示集合R中的第j個(gè)關(guān)系，m為R中關(guān)系的個(gè)數(shù)，特別地，若m=0，則R是一個(gè)空集，表明集合D中的數(shù)據(jù)元素間不存在任何關(guān)系，彼此是獨(dú)立的，這和數(shù)學(xué)中集合的概念是一致的。

R中的某個(gè)關(guān)系rj（1≤j≤m）是序偶的集合，對(duì)于rj中的任一序偶<x,y>（x，y∈D），把x叫做序偶的第一結(jié)點(diǎn)，把y叫做序偶的第二結(jié)點(diǎn)，又稱序偶的第一結(jié)點(diǎn)為第二結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，稱第二結(jié)點(diǎn)為第一結(jié)點(diǎn)的后繼結(jié)點(diǎn)。如在<x,y>的序偶中，x為y的前驅(qū)結(jié)點(diǎn)，而y為x的后繼結(jié)點(diǎn)。若某個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，則稱該結(jié)點(diǎn)為開始結(jié)點(diǎn)；若某個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，則稱該結(jié)點(diǎn)為終端結(jié)點(diǎn)。對(duì)于對(duì)稱序偶，即滿足這樣的條件：若<x,y>∈r（r∈R），則<y,x>∈r（x，y∈D），可用圓括號(hào)代替尖括號(hào)，即(x,y)∈r。

【例1.4】

采用二元組表示前面三個(gè)例子的邏輯結(jié)構(gòu)。

解：高等數(shù)學(xué)成績(jī)單（假設(shè)學(xué)號(hào)為關(guān)鍵字）的二元組表示如下：學(xué)號(hào)姓名分?jǐn)?shù)2011001王華902011010劉麗622011006陳明542011009張強(qiáng)952011007許兵762011012李萍882011005李英82B1=(D,R)D={2011001,2011010,2011006,2011009,2011007,2011012,2011005}R={r1} //表示只有一種邏輯關(guān)系r1={<2011001,2011010>,<2011010,2011006>,<2011006,2011009>,

<2011009,2011007>,<2011007,2011012>,<2011012,2011005>}等價(jià)表示某高校組織結(jié)構(gòu)（假設(shè)單位名為關(guān)鍵字）的二元組表示如下：B2=(D,R)D={XX大學(xué),計(jì)算機(jī)學(xué)院,電子信息學(xué)院,…,教務(wù)處,學(xué)生處,…,科學(xué)系,工程系,應(yīng)用系,…, 招生辦,就業(yè)辦}R={r1}r1={<XX大學(xué),計(jì)算機(jī)學(xué)院>,<XX大學(xué),電子信息學(xué)院>,…,

<XX大學(xué),教務(wù)處>,<XX大學(xué),學(xué)生處>,…,<計(jì)算機(jī)學(xué)院,科學(xué)系>,<計(jì)算機(jī)學(xué)院,工程系>,<計(jì)算機(jī)學(xué)院,應(yīng)用系>,…,<學(xué)生處,招生邊>,<學(xué)生處,就業(yè)邊>}等價(jià)表示

全國(guó)部分城市交通圖（假設(shè)城市名為關(guān)鍵字）的二元組表示如下：B3=(D,R)D={北京,鄭州,武漢,長(zhǎng)沙,南京,南昌,杭州,上海}R={r1}r1={(北京,鄭州),(北京,南京),(鄭州,武漢),(武漢,南京),(武漢,長(zhǎng)沙),(南京,南昌),(南京,上海),(南京,杭州),(南昌,杭州),(南昌,上海)}等價(jià)表示1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)應(yīng)正確地反映數(shù)據(jù)元素之間的邏輯關(guān)系，也就是說，在設(shè)計(jì)某種邏輯結(jié)構(gòu)對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)時(shí)，不僅要存儲(chǔ)所有的數(shù)據(jù)元素，還要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。所以將數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)的映像，設(shè)計(jì)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)稱為從邏輯結(jié)構(gòu)到存儲(chǔ)器的映射，如圖1.4所示。

【例1.5】

對(duì)于表1.1所示高等數(shù)學(xué)成績(jī)單，設(shè)計(jì)多種存儲(chǔ)結(jié)構(gòu)，并討論各種存儲(chǔ)結(jié)構(gòu)的特性。

解：這里設(shè)計(jì)高等數(shù)學(xué)成績(jī)單的兩種存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)1：用C#語(yǔ)言中的數(shù)組來存儲(chǔ)高等數(shù)學(xué)成績(jī)單，設(shè)計(jì)存放學(xué)生成績(jī)記錄的數(shù)組類型如下：structStud1 //學(xué)生成績(jī)記錄類型{ publicintno; //存放學(xué)號(hào)

publicstringname; //存放姓名

publicdoublescore; //存放分?jǐn)?shù)}constintMaxSize=100; //存放最多記錄個(gè)數(shù)Stud1[]st=newStud1[MaxSize]; //存放記錄的數(shù)組st[0].no=2011001;st[0].name="王華";st[0].score=90;st[1].no=2011010;st[1].name="劉麗";st[1].score=62;st[2].no=2011006;st[2].name="陳明";st[2].score=54;st[3].no=2011009;st[3].name="張強(qiáng)";st[3].score=95;st[4].no=2011007;st[4].name="許兵";st[4].score=76;st[5].no=2011012;st[5].name="李萍";st[5].score=88;st[6].no=2011005;st[6].name="李英";st[6].score=82;順序存儲(chǔ)結(jié)構(gòu)定義一個(gè)數(shù)組st用于存放高等數(shù)學(xué)成績(jī)單如下：

存儲(chǔ)結(jié)構(gòu)2：用C#語(yǔ)言中的單鏈表來存儲(chǔ)高等數(shù)學(xué)成績(jī)單，設(shè)計(jì)存放學(xué)生成績(jī)記錄的結(jié)點(diǎn)類型如下：classStud2 //學(xué)生成績(jī)單鏈表結(jié)點(diǎn)類{ publicintno; //存放學(xué)號(hào)

publicstringname; //存放姓名

publicdoublescore; //存放分?jǐn)?shù)

publicStud2next; //存放下一個(gè)結(jié)點(diǎn)指針}Stud2head; //學(xué)生單鏈表開始結(jié)點(diǎn)Stud2p1,p2,p3,p4,p5,p6,p7;p1=newStud2();p1.no=2011001;="王華";p1.score=90;p2=newStud2();p2.no=2011010;="劉麗";p2.score=62;p3=newStud2();p3.no=2011006;="陳明";p3.score=54;p4=newStud2();p4.no=2011009;="張強(qiáng)";p4.score=95;p5=newStud2();p5.no=2011007;="許兵";p5.score=76;p6=newStud2();p6.no=2011012;="李萍";p6.score=88;p7=newStud2();p7.no=2011005;="李英";p7.score=82;head=p1; //建立結(jié)點(diǎn)之間的關(guān)系p1.next=p2; p2.next=p3; p3.next=p4;p4.next=p5; p5.next=p6; p6.next=p7; p7.next=null;建立一個(gè)用于存放高等數(shù)學(xué)成績(jī)單的單鏈表（開始結(jié)點(diǎn)為head）如下：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

說明：C/C++語(yǔ)言中具有指針類型，嚴(yán)格上講C#語(yǔ)言中沒有指針類型，但C#中有對(duì)象引用機(jī)制，可以間接地實(shí)現(xiàn)指針的某些作用。為了和采用C/C++描述數(shù)據(jù)結(jié)構(gòu)相一致，本書也將對(duì)象引用稱為指針。Stud2head，p1;headp1p1=newStud2();對(duì)象實(shí)例head=p1;歸納起來有以下4種常用的存儲(chǔ)結(jié)構(gòu)類型：（1）順序存儲(chǔ)結(jié)構(gòu)（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（3）索引存儲(chǔ)結(jié)構(gòu)（4）哈希（或散列）存儲(chǔ)結(jié)構(gòu)1.1.4數(shù)據(jù)的運(yùn)算將數(shù)據(jù)存放在計(jì)算機(jī)中的目的是為了實(shí)現(xiàn)一種或多種運(yùn)算。運(yùn)算包括功能描述和功能實(shí)現(xiàn)，前者是基于邏輯結(jié)構(gòu)的，是用戶定義的，是抽象的；后者是基于存儲(chǔ)結(jié)構(gòu)的，是程序員用計(jì)算機(jī)語(yǔ)言或偽碼表示的，是詳細(xì)的過程。例如，對(duì)于高等數(shù)學(xué)成績(jī)單這種數(shù)據(jù)結(jié)構(gòu)，可以進(jìn)行一系列的運(yùn)算，如增加一個(gè)學(xué)生成績(jī)記錄、刪除一個(gè)學(xué)生成績(jī)記錄、求所有學(xué)生的平均分，查找序號(hào)為i的學(xué)生姓名和分?jǐn)?shù)等等。同一運(yùn)算，在不同存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)過程是不同的。例如，查找序號(hào)為i的學(xué)生姓名和分?jǐn)?shù)，其運(yùn)算功能描述是：查找邏輯序號(hào)為i的學(xué)生成績(jī)記錄，若找到了，輸出其姓名和分?jǐn)?shù)，并返回true；否則返回false。但在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)過程不同的。在順序存儲(chǔ)結(jié)構(gòu)中對(duì)應(yīng)的代碼如下：publicboolFindi(inti,refstringna,refdoublesc) //i為邏輯序號(hào){ if(i<=0||i>n) //i錯(cuò)誤時(shí)返回false,n為數(shù)據(jù)元素個(gè)數(shù)

returnfalse; else //i正確時(shí)返回true { na=st[i-1].name; sc=st[i-1].score; returntrue; }}在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中對(duì)應(yīng)的代碼如下：publicboolFindi(inti,refstringna,refdoublesc) //i為邏輯序號(hào){ intj=1; Stud2p=head; while(j<i&&p!=null) { j++; p=p.next; } if(i<=0||p==null) //i錯(cuò)誤時(shí)返回false returnfalse; else //i正確時(shí)返回true { na=; sc=p.score; returntrue; }}歸納起來，對(duì)于一種數(shù)據(jù)結(jié)構(gòu)，其邏輯結(jié)構(gòu)是唯一的（盡管邏輯結(jié)構(gòu)的表示形式有多種），但它可能對(duì)應(yīng)多種存儲(chǔ)結(jié)構(gòu)，并且在不同的存儲(chǔ)結(jié)構(gòu)中，同一運(yùn)算的實(shí)現(xiàn)過程可能不同。1.1.5數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型1.數(shù)據(jù)類型在用高級(jí)程序語(yǔ)言（如C#語(yǔ)言）編寫的程序中，通常需要對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。數(shù)據(jù)類型是一組性質(zhì)相同的值的集合和定義在此集合上的一組操作的總稱。C#數(shù)據(jù)類型主要分為值類型和引用類型兩大類。2.抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（AbstractDataType簡(jiǎn)寫為ADT）指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算，而不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。抽象數(shù)據(jù)類型中的數(shù)據(jù)對(duì)象和數(shù)據(jù)運(yùn)算的聲明與數(shù)據(jù)對(duì)象的表示和數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)相互分離。抽象數(shù)據(jù)類型可用（D,S,P）三元組表示。其中D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是D中數(shù)據(jù)運(yùn)算的基本運(yùn)算集。其基本格式如下：ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的聲明 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的聲明 基本運(yùn)算：基本運(yùn)算的聲明}ADT抽象數(shù)據(jù)類型名

【例1.6】

構(gòu)造集合ADTSet，假設(shè)其中元素為字符串類型，遵循標(biāo)準(zhǔn)數(shù)學(xué)定義，成員包括Create（創(chuàng)建一個(gè)空集合）、Insert（插入一個(gè)元素）、Remove（刪除一個(gè)元素）、IsIn（一個(gè)元素是否屬于集合）。另外定義一個(gè)實(shí)現(xiàn)集合運(yùn)算的ADTTwoSet，成員包括Union（集合并）、IIntersection（集合交）和Difference（集合差）。解：抽象數(shù)據(jù)類型Set和TwoSet的定義如下：ADTSet //集合的抽象數(shù)據(jù)類型{數(shù)據(jù)對(duì)象：

data={di|1≤i≤n,di∈string}; //存放集合中元素

intn; //集合中元素個(gè)數(shù)數(shù)據(jù)關(guān)系：無基本運(yùn)算：

publicvoidCreate(); //創(chuàng)建一個(gè)空的集合

publicboolIsIn(stringe); //判斷e是否在集合中publicboolInsert(stringe); //將元素e插入到集合中

publicboolRemove(stringe); //從集合中刪除元素e}ADTSetADTTwoSet //兩個(gè)集合運(yùn)算的抽象數(shù)據(jù)類型{數(shù)據(jù)對(duì)象：

Setset1; //集合set1 Setset2; //集合set2

數(shù)據(jù)關(guān)系： 無基本運(yùn)算：

publicSetUnion() //求兩集合的并集

publicSetIIntersection() //求兩集合的交集

publicSetDifference() //求兩集合的差集}抽象數(shù)據(jù)類型有兩個(gè)重要特征：數(shù)據(jù)抽象和數(shù)據(jù)封裝。所謂數(shù)據(jù)抽象，是指用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。所謂數(shù)據(jù)封裝，是指將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。1.2算法及其描述1.2.1什么是算法數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系，對(duì)應(yīng)的運(yùn)算有邏輯結(jié)構(gòu)上的運(yùn)算（抽象運(yùn)算）和具體存儲(chǔ)結(jié)構(gòu)上的運(yùn)算（運(yùn)算實(shí)現(xiàn)）。算法是在具體存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)某個(gè)抽象運(yùn)算。確切地說，算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示計(jì)算機(jī)的一個(gè)或多個(gè)操作。算法具有以下五個(gè)重要的特性：有窮性。指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成。確定性。對(duì)于每種情況下執(zhí)行的操作，在算法中都有確定的含義，不會(huì)出現(xiàn)二義性。并且在任何條件下，算法都只有一條執(zhí)行路徑?？尚行浴Ｋ惴ǖ拿織l指令都是基本可執(zhí)行的，意指借助紙、筆或計(jì)算機(jī)可以完成。有輸入。算法有零個(gè)或多個(gè)輸入。有輸出。算法至少有一個(gè)或多個(gè)輸出。【例1.7】

考慮下列兩段描述：（1）描述一

voidexam1()

{ intn=2; while(n%2==0) n=n+2; Console.WriteLine("n={0}",n);

}（2）描述二

voidexam2() { intx,y=0; x=5/y; Console.WriteLine("x={0},y={1}",x,y); }這兩段描述均不能滿足算法的特征，試問它們違反了哪些特性？

解：（1）其中while循環(huán)語(yǔ)句是一個(gè)死循環(huán)，違反了算法的有窮性特性，所以它不是算法。（2）其中包含除零操作，這違反了算法的可行性特性，所以它不是算法。1.2.2算法描述下面介紹C#語(yǔ)言中描述算法的相關(guān)內(nèi)容。1.數(shù)據(jù)表示（1）字段為了提高封裝性，通常將類字段設(shè)計(jì)成私有的，再設(shè)計(jì)對(duì)私有字段進(jìn)行訪問的屬性。例如，以下類中定義了私有變量n的訪問屬性pn：classA{privateintn; //私有字段

publicintpn //訪問n的屬性pn

{ get{returnn;} //get訪問器，使pn可以進(jìn)行讀操作

set{x=value;} //set訪問器，使pn可以進(jìn)行寫操作

}

…}當(dāng)使用語(yǔ)句Aobj=newA();定義了類A的對(duì)象obj后，通過obj.pn對(duì)私有變量n進(jìn)行讀（取n的值）寫（修改n的值）操作。但為了和C/C++語(yǔ)言比較接近，本書中描述算法時(shí)沒有采用屬性，而是將n設(shè)計(jì)為公有字段（publicintn），如上面的類A設(shè)計(jì)如下：

classA

{ publicintn; //公有字段

…

}這樣做的目的是可以通過類對(duì)象obj直接訪問字段n（obj.n），從而提高了算法的可讀性。（2）靜態(tài)字段靜態(tài)字段（前面加上static關(guān)鍵詞定義的字段）是類中所有對(duì)象共享的成員，而不是某個(gè)對(duì)象的成員，也就是說靜態(tài)字段的存儲(chǔ)空間不是放在每個(gè)對(duì)象中，而是放在類公共區(qū)中?？梢酝ㄟ^“類名.靜態(tài)字段名”來訪問靜態(tài)字段。本書中主要使用靜態(tài)字段在不同的模塊之間傳遞數(shù)據(jù)。2.幾種特殊類型的方法（1）構(gòu)造函數(shù)和析構(gòu)函數(shù)構(gòu)造函數(shù)和析構(gòu)函數(shù)是類的兩種public成員方法，但普通的方法相比，它們有各自的特殊性，也就是說它們都是自動(dòng)被調(diào)用的。（2）靜態(tài)方法靜態(tài)方法屬于類，是類的靜態(tài)成員。只要類存在，靜態(tài)方法就可以使用，靜態(tài)方法的定義是在一般方法定義前加上static關(guān)鍵字。靜態(tài)方法具有如下性質(zhì)：通過“類名.靜態(tài)方法名(參數(shù)表)”來調(diào)用靜態(tài)方法；靜態(tài)方法只能訪問靜態(tài)字段、其他靜態(tài)方法和類以外的函數(shù)及數(shù)據(jù)，不能訪問類中的非靜態(tài)成員。3.方法的定義通常采用普通的方法來實(shí)現(xiàn)算法。定義普通方法時(shí)需要指定訪問級(jí)別、返回值、方法名稱以及方法的形參。4.方法的參數(shù)（1）值參數(shù)不含任何修飾符，當(dāng)利用值參向方法傳遞參數(shù)時(shí)，編譯系統(tǒng)給實(shí)參的值做一份拷貝，并且將此拷貝傳遞給該方法，被調(diào)用的方法不會(huì)修改內(nèi)存中實(shí)參的值，所以使用值參時(shí)可以保證實(shí)際值的安全性，此時(shí)只是實(shí)參到形參的單向值傳遞。（2）引用參數(shù)以ref修飾符聲明的參數(shù)屬引用參數(shù)。引用參數(shù)本身并不創(chuàng)建新的存儲(chǔ)空間，而是將實(shí)參的存儲(chǔ)地址傳遞給形參，所以對(duì)形參的修改會(huì)影響原來實(shí)參的值，此時(shí)實(shí)參和形參是雙向值傳遞。1.3算法分析1.3.1算法的特性和算法設(shè)計(jì)的目標(biāo)（1）正確性。（2）可使用性。（3）可讀性。（4）健壯性。（5）高效率與低存儲(chǔ)量需求。1.3.2算法時(shí)間效率分析求解同一問題可能對(duì)應(yīng)多種算法，例如求s=1+2+…+n，其中n為正整數(shù)，通常有以下兩種算法fun1(n)和fin2(n)，顯然前者算法的時(shí)間效率不如后者。一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，算法的運(yùn)行時(shí)間取決于兩者的綜合效果。例如，如下所示是在某個(gè)類中定義的Solve方法，其中形參a是一個(gè)m行n列的數(shù)組，當(dāng)是一個(gè)方陣（m=n）時(shí)求主對(duì)角線所有元素之和并返回true，否則返回false，從中看到該算法由4部分組成，包含兩個(gè)順序結(jié)構(gòu)、一個(gè)分支結(jié)構(gòu)和一個(gè)循環(huán)結(jié)構(gòu)。為了便于比較求解同一問題的不同算法，通常的做法是，從算法中選取一種對(duì)于所討論的問題來說是基本運(yùn)算的原操作，算法執(zhí)行時(shí)間大致為這種原操作所需的時(shí)間與其運(yùn)算次數(shù)（一個(gè)語(yǔ)句的運(yùn)行次數(shù)稱為語(yǔ)句頻度）的乘積。被視為算法基本運(yùn)算的原操作一般是最深層循環(huán)內(nèi)的語(yǔ)句（Solve算法中的基本運(yùn)算為s+=a[i,i]）。顯然，在一個(gè)算法中，執(zhí)行基本運(yùn)算的原操作的次數(shù)越少，其運(yùn)行時(shí)間也就相對(duì)地越少；反之其運(yùn)行時(shí)間也就相對(duì)地越多。也就是說，一個(gè)算法的執(zhí)行時(shí)間可以看成是其中基本運(yùn)算的原操作的執(zhí)行次數(shù)。一個(gè)算法的執(zhí)行基本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：

T(n)=O(f(n))記號(hào)“O”讀作“大O”（是Order的簡(jiǎn)寫，意指數(shù)量級(jí)），它表示隨問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。

“O”的形式定義為：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則T(n)=O(f(n))表示存在一個(gè)正的常數(shù)c和n0，使得當(dāng)n≥n0時(shí)都滿足T(n)≤cf(n)，也就是只求出T(n)的最高階，忽略其低階項(xiàng)和常系數(shù)，這樣既可簡(jiǎn)化T(n)的計(jì)算，又能比較客觀地反映出當(dāng)n很大時(shí)，算法的時(shí)間性能，例如：

T(n)=3n2-5n+100=O(n2)一個(gè)沒有循環(huán)的算法中基本運(yùn)算次數(shù)與問題規(guī)模n無關(guān)，記作O(1)，也稱作常數(shù)階。一個(gè)只有一重循環(huán)的算法中基本運(yùn)算次數(shù)與問題規(guī)模n的增長(zhǎng)呈線性增大關(guān)系，記作O(n)，也稱線性階。其余常用的還有平方階O(n2)、立方階O(n3)、對(duì)數(shù)階O(log2n)、指數(shù)階O(2n)等等。各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)【例1.8】

求兩個(gè)n階方陣的相加C=A+B的算法如下，分析其時(shí)間復(fù)雜度。publicvoidmatrixadd(intn,int[,]A,int[,]B,int[,]C){

inti,j;

for(i=0;i<n;i++) //語(yǔ)句①

for(j=0;j<n;j++) //語(yǔ)句②

C[i,j]=A[i,j]+B[i,j]; //語(yǔ)句③}

解法1：累計(jì)算法中所有語(yǔ)句的執(zhí)行次數(shù)T(n)，再來求算法的時(shí)間復(fù)雜度。該算法包括3個(gè)可執(zhí)行語(yǔ)句①、②和③。其中語(yǔ)句①循環(huán)控制變量i要從0增加到n，測(cè)試i=n時(shí)才會(huì)終止，故它的頻度是n+1，但它的循環(huán)體卻只能執(zhí)行n次。語(yǔ)句②作為語(yǔ)句①循環(huán)體內(nèi)的語(yǔ)句應(yīng)該只執(zhí)行n次，但語(yǔ)句②本身也要執(zhí)行n+1次，所以語(yǔ)句②頻度是n(n+1)。同理可得語(yǔ)句③的頻度為n2。因此，該算法中所有語(yǔ)句頻度之和為：

T(n)=n+1+n(n+1)+n2=2n2+2n+1=O(n2)

解法2：僅考慮算法中最深層循環(huán)內(nèi)語(yǔ)句（基本運(yùn)算）的執(zhí)行次數(shù)T(n)，再來求算法的時(shí)間復(fù)雜度。該算法中的基本運(yùn)算是兩重循環(huán)中最深層的語(yǔ)句③，分析它的頻度，即：

T(n)=n2=O(n2)從兩種解法得出算法的時(shí)間復(fù)雜度均為O(n2)，而后者計(jì)算過程簡(jiǎn)單得多，所以后面總是采用后者解法來分析算法的時(shí)間復(fù)雜度。【例1.9】

分析以下算法的時(shí)間復(fù)雜度。publicvoidfun(intn){ ints=0,i,j,k; for(i=0;i<=n;i++) for(j=0;j<=i;j++) for(k=0;k<j;k++) s++;}解：該算法的基本運(yùn)算是語(yǔ)句s++，其頻度：T(n)=

=

==

=

+)==O(n3)有些情況下，一個(gè)算法的執(zhí)行時(shí)間不僅與問題規(guī)規(guī)n有關(guān)，還與初始實(shí)例有關(guān)，上例不屬于這種情況，下面看一個(gè)這樣的示例?！纠?.10】

分析以下算法的時(shí)間復(fù)雜度。intfun(int[]a,intn,intk){

inti;

i=0; //語(yǔ)句①

while(i<n&&a[i]!=k) //語(yǔ)句②

i++;