非數(shù)值計算程序設(shè)計問題

非數(shù)值計算程序設(shè)計問題第1頁，共62頁，2023年，2月20日，星期四第一章緒論第2頁，共62頁，2023年，2月20日，星期四一、數(shù)據(jù)結(jié)構(gòu)討論的范疇二、基本概念三、算法和算法的度量第3頁，共62頁，2023年，2月20日，星期四一、數(shù)據(jù)結(jié)構(gòu)討論的范疇非數(shù)值計算程序設(shè)計問題數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)

第4頁，共62頁，2023年，2月20日，星期四二、基本概念1.數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2.抽象數(shù)據(jù)類型第5頁，共62頁，2023年，2月20日，星期四1.數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計算機中，且能被計算機處理的符號的集合。數(shù)據(jù):是計算機操作的對象的總稱。是計算機處理的信息的某種特定的符號表示形式。第6頁，共62頁，2023年，2月20日，星期四是數(shù)據(jù)（集合）中的一個“個體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位第7頁，共62頁，2023年，2月20日，星期四數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合

或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。第8頁，共62頁，2023年，2月20日，星期四是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，而且確保經(jīng)過這些運算以后所得的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型數(shù)據(jù)結(jié)構(gòu)：第9頁，共62頁，2023年，2月20日，星期四概括地說：

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學(xué)模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學(xué)科。第10頁，共62頁，2023年，2月20日，星期四數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)第11頁，共62頁，2023年，2月20日，星期四數(shù)據(jù)的存儲結(jié)構(gòu)

——

邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？第12頁，共62頁，2023年，2月20日，星期四關(guān)系的映象方法：順序映象用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素

xy第13頁，共62頁，2023年，2月20日，星期四鏈式映象以附加信息(指針)表示后繼關(guān)系需要用一個和x在一起的附加信息指示y的存儲位置yx第14頁，共62頁，2023年，2月20日，星期四2.抽象數(shù)據(jù)類型

(AbstractDataType簡稱ADT)

是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。第15頁，共62頁，2023年，2月20日，星期四三、算法和算法的衡量1.算法2.算法設(shè)計的原則3.算法效率的衡量方法和準則4.算法的存儲空間需求第16頁，共62頁，2023年，2月20日，星期四

算法是對解決某類問題的方法的一種描述。一個算法必須滿足以下五個重要特性：1．有窮性2．確定性3．可行性4．有輸入5．有輸出第17頁，共62頁，2023年，2月20日，星期四隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同。T(n)=O(f(n))

漸近時間復(fù)雜度第18頁，共62頁，2023年，2月20日，星期四第二章線性表第19頁，共62頁，2023年，2月20日，星期四線性表的概念---基本操作算法實現(xiàn)---順序存儲---鏈式存儲第20頁，共62頁，2023年，2月20日，星期四順序映象方法是：邏輯關(guān)系相鄰,

物理位置相鄰.

用一組地址連續(xù)的存儲單元

依次存放線性表中的數(shù)據(jù)元素

a1a2…ai-1ai…an基地址第21頁，共62頁，2023年，2月20日，星期四constintMaxSize=50;

struct

List

{ ElemTypelist[MaxSize]; intsize;//當(dāng)前線性表長度

};線性表順序存儲結(jié)構(gòu)第22頁，共62頁，2023年，2月20日，星期四一、有關(guān)空表的操作

1.初始化操作2.清空操作3.判空操作*當(dāng)前線性表長度*第23頁，共62頁，2023年，2月20日，星期四二、有關(guān)查找的操作2.查找具有給定值的元素

1.遍歷線性表操作3.更新表中具有給定值的元素第24頁，共62頁，2023年，2月20日，星期四從表頭元素起依次訪問每一個元素，并且每個元素只被訪問一次

a1a2…ai-1ai…an基地址L.list[0]最后一個L.list[L.size-1]第25頁，共62頁，2023年，2月20日，星期四三、有關(guān)插入的操作

3.插在i位置操作2.

表頭插入一個元素1.末尾添加一個元素后移第26頁，共62頁，2023年，2月20日，星期四a1a2…ai-1ai

…ana1a2…ai-1

…ai

ean表的長度增1i位置for(intj=L.size;j<=i;j--)

{L.list[j]=L.list[j-1];}最后的位置L.size第27頁，共62頁，2023年，2月20日，星期四四、有關(guān)刪除的操作

2.刪除i位置元素操作1.刪除表頭元素操作前移第28頁，共62頁，2023年，2月20日，星期四ai-1插入、刪除、建立等操作在單鏈表中的實現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,

e>

和<e,ai>

eaiai-1第29頁，共62頁，2023年，2月20日，星期四s=newLNode;

s->data=e;

//生成新結(jié)點s->next=p->next;

p->next=s;

//插入

eai-1aiai-1sp第30頁，共62頁，2023年，2月20日，星期四ai-1aiai+1ai-1q=p->next;

p->next=q->next;

e=q->data;deleteq;pq第31頁，共62頁，2023年，2月20日，星期四逆位序輸入建立帶頭結(jié)點的單鏈表一、建立一個“空表”；二、輸入數(shù)據(jù)元素an；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并前插；四、依次類推，直至輸入a1為止。L->next=p;p->next=L->next;第32頁，共62頁，2023年，2月20日，星期四

最后一個結(jié)點的指針域的指針又指回第一個結(jié)點循環(huán)鏈表

a1a2

…an判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。第33頁，共62頁，2023年，2月20日，星期四ai-1aies->right=p->right;p->right=s;s->right->left=s;s->left=p;psai-1ai插入雙向鏈表第34頁，共62頁，2023年，2月20日，星期四ai-1刪除aiai+1p->right=p->right->right;p->right->left=p;pai-1第35頁，共62頁，2023年，2月20日，星期四第三章稀疏矩陣和廣義表第36頁，共62頁，2023年，2月20日，星期四壓縮存儲方法:一、三元組順序表二、帶行指針向量的鏈接存儲三、十字鏈表稀疏矩陣的概念第37頁，共62頁，2023年，2月20日，星期四原矩陣轉(zhuǎn)置后矩陣一、三元組順序表用“三元組”表示實現(xiàn)矩陣轉(zhuǎn)置第38頁，共62頁，2023年，2月20日，星期四需要把具有相同行號的三元組結(jié)點按照列號從小到大的順序鏈接成一個單鏈表，每個三元組結(jié)點的類型可定義為：二、帶行指針向量的鏈接存儲

rowcolvalnext第39頁，共62頁，2023年，2月20日，星期四1

2

141

5

-52

2

-731

3634

28三元組行指針向量22-73136342815-51214vector/\/\/\/\/\第40頁，共62頁，2023年，2月20日，星期四三、十字鏈表cvrv30050-100200011314522-1312^^^^^^^第41頁，共62頁，2023年，2月20日，星期四廣義表的概念

廣義表是遞歸定義的線性結(jié)構(gòu)廣義表是多層次的線性結(jié)構(gòu)第42頁，共62頁，2023年，2月20日，星期四廣義表結(jié)構(gòu)的特點:數(shù)據(jù)元素有相對次序；2)長度為最外層包含元素個數(shù)；3)深度為所含括弧的重數(shù)；原子:深度為0;空表:深度為1;4)可以共享；5)可以是一個遞歸的表。第43頁，共62頁，2023年，2月20日，星期四廣義表的存儲結(jié)構(gòu)采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點:原子結(jié)點：tag=1sublistnexttag=0datanext第44頁，共62頁，2023年，2月20日，星期四廣義表的運算遞歸函數(shù)

含直接或間接調(diào)用本函數(shù)語句的函數(shù)

2.求廣義表的深度1.求廣義表長度第45頁，共62頁，2023年，2月20日，星期四1.求廣義表長度的遞歸算法

int

Lenth(GLNode*GL)

{if(GL!=NULL)

return1+Lenth(GL->next); elsereturn0;}第46頁，共62頁，2023年，2月20日，星期四非遞歸算法如下：

intLenth(GLNode*GL)

{intlen=0;

while(GL!=NULL){len++;GL=GL->next;}

returnlen;}第47頁，共62頁，2023年，2月20日，星期四深度=Max{子表的深度}+12.求廣義表的深度可以直接求解的兩種簡單情況為：

空表的深度=1

原子的深度=0

將廣義表分解成n個子表，分別

(遞歸)求得每個子表的深度，第48頁，共62頁，2023年，2月20日，星期四

1

1

1L…

while(L!=NULL)

{if(L->tag==true){

intdep=Depth(L->sublist);

if(dep>max)max=dep;}L=L->next;}LL->sublistLLL->sublistL->sublist第49頁，共62頁，2023年，2月20日，星期四第四章棧和隊列第50頁，共62頁，2023年，2月20日，星期四棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號匹配的檢驗表達式求值遞歸第51頁，共62頁，2023年，2月20日，星期四表達式求值后綴式:ab

cde/f+

后綴式算符在式中出現(xiàn)的順序恰為表達式的運算順序;每個運算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式。第52頁，共62頁，2023年，2月20日，星期四如何從后綴式求值？先找運算符，再找操作數(shù)設(shè)立操作數(shù)棧如何從中綴式轉(zhuǎn)換成后綴式？設(shè)立操作符棧第53頁，共62頁，2023年，2月20日，星期四棧與遞歸

實現(xiàn)遞歸函數(shù)，必須利用“?！?。一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函數(shù)；反之，一個用棧實現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。遞歸函數(shù)中的尾遞歸容易消除。第54頁，共62頁，2023年，2月20日，星期四隊列的定義鏈隊列——鏈式映象循環(huán)隊列——順序映象第55頁，共62頁，2023年，2月20日，星期四求余:X%QueueMaxSize

結(jié)果在0~QueueMaxSize-1之間Q.rear=(Q.rear+1)%QueueMaxSize;

Q.front=(Q.front+1)%QueueMaxSize;1023456789QueueMaxSize-1...第56頁，共62頁，2023年，2月20日，星期四

將新元素item的值插入到隊尾

voidQinsert(QueueType&Q,constElemType&item);

從隊列Q中刪除隊首元素并返回之

ElemTypeQdelete(QueueType&Q);

循環(huán)隊列的基本操作:第57頁，共62頁，2023年，2月20日，星期四

structLNode

{

ElemType

data;