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

非數(shù)值計算程序設(shè)計問題第一頁，共六十二頁，2022年，8月28日第一章緒論第二頁，共六十二頁，2022年，8月28日一、數(shù)據(jù)結(jié)構(gòu)討論的范疇二、基本概念三、算法和算法的度量第三頁，共六十二頁，2022年，8月28日一、數(shù)據(jù)結(jié)構(gòu)討論的范疇非數(shù)值計算程序設(shè)計問題數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)

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

或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。第八頁，共六十二頁，2022年，8月28日是研究數(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)：第九頁，共六十二頁，2022年，8月28日概括地說：

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

——

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

xy第十三頁，共六十二頁，2022年，8月28日鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個和x在一起的附加信息指示y的存儲位置yx第十四頁，共六十二頁，2022年，8月28日2.抽象數(shù)據(jù)類型

(AbstractDataType簡稱ADT)

是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。第十五頁，共六十二頁，2022年，8月28日三、算法和算法的衡量1.算法2.算法設(shè)計的原則3.算法效率的衡量方法和準(zhǔn)則4.算法的存儲空間需求第十六頁，共六十二頁，2022年，8月28日

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

漸近時間復(fù)雜度第十八頁，共六十二頁，2022年，8月28日第二章線性表第十九頁，共六十二頁，2022年，8月28日線性表的概念---基本操作算法實現(xiàn)---順序存儲---鏈?zhǔn)酱鎯Φ诙?，共六十二頁?022年，8月28日順序映象方法是：邏輯關(guān)系相鄰,

物理位置相鄰.

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

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

a1a2…ai-1ai…an基地址第二十一頁，共六十二頁，2022年，8月28日constintMaxSize=50;

struct

List

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

};線性表順序存儲結(jié)構(gòu)第二十二頁，共六十二頁，2022年，8月28日一、有關(guān)空表的操作

1.初始化操作2.清空操作3.判空操作*當(dāng)前線性表長度*第二十三頁，共六十二頁，2022年，8月28日二、有關(guān)查找的操作2.查找具有給定值的元素

1.遍歷線性表操作3.更新表中具有給定值的元素第二十四頁，共六十二頁，2022年，8月28日從表頭元素起依次訪問每一個元素，并且每個元素只被訪問一次

a1a2…ai-1ai…an基地址L.list[0]最后一個L.list[L.size-1]第二十五頁，共六十二頁，2022年，8月28日三、有關(guān)插入的操作

3.插在i位置操作2.

表頭插入一個元素1.末尾添加一個元素后移第二十六頁，共六十二頁，2022年，8月28日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第二十七頁，共六十二頁，2022年，8月28日四、有關(guān)刪除的操作

2.刪除i位置元素操作1.刪除表頭元素操作前移第二十八頁，共六十二頁，2022年，8月28日ai-1插入、刪除、建立等操作在單鏈表中的實現(xiàn)：

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

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

e>

和<e,ai>

eaiai-1第二十九頁，共六十二頁，2022年，8月28日s=newLNode;

s->data=e;

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

p->next=s;

//插入

eai-1aiai-1sp第三十頁，共六十二頁，2022年，8月28日ai-1aiai+1ai-1q=p->next;

p->next=q->next;

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

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

a1a2

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

rowcolvalnext第三十九頁，共六十二頁，2022年，8月28日1

2

141

5

-52

2

-731

3634

28三元組行指針向量22-73136342815-51214vector/\/\/\/\/\第四十頁，共六十二頁，2022年，8月28日三、十字鏈表cvrv30050-100200011314522-1312^^^^^^^第四十一頁，共六十二頁，2022年，8月28日廣義表的概念

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

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

2.求廣義表的深度1.求廣義表長度第四十五頁，共六十二頁，2022年，8月28日1.求廣義表長度的遞歸算法

int

Lenth(GLNode*GL)

{if(GL!=NULL)

return1+Lenth(GL->next); elsereturn0;}第四十六頁，共六十二頁，2022年，8月28日非遞歸算法如下：

intLenth(GLNode*GL)

{intlen=0;

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

returnlen;}第四十七頁，共六十二頁，2022年，8月28日深度=Max{子表的深度}+12.求廣義表的深度可以直接求解的兩種簡單情況為：

空表的深度=1

原子的深度=0

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

(遞歸)求得每個子表的深度，第四十八頁，共六十二頁，2022年，8月28日

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第四十九頁，共六十二頁，2022年，8月28日第四章棧和隊列第五十頁，共六十二頁，2022年，8月28日棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號匹配的檢驗表達式求值遞歸第五十一頁，共六十二頁，2022年，8月28日表達式求值后綴式:ab

cde/f+

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

實現(xiàn)遞歸函數(shù)，必須利用“?！?。一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函數(shù)；反之，一個用棧實現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。遞歸函數(shù)中的尾遞歸容易消除。第五十四頁，共六十二頁，2022年，8月28日隊列的定義鏈隊列——鏈?zhǔn)接诚笱h(huán)隊列——順序映象第五十五頁，共六十二頁，2022年，8月28日求余:X%QueueMaxSize

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

Q.front=(Q.front+1)%QueueMaxSize;1023456789QueueMaxSize-1...第五十六頁，共六十二頁，2022年，8月28日

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

voidQinsert(QueueType&Q,constElemType&item);

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

ElemTypeQdelete(QueueType&Q);

循環(huán)隊列的基本操作:第五十七頁，共六十二頁，2022年，8月28日

structLNode

{

ElemType

data;

LN