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

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

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

或者說，數(shù)據(jù)結構是相互之間存在著某種邏輯關系的數(shù)據(jù)元素的集合。第八頁，共六十二頁，2022年，8月28日是研究數(shù)據(jù)的邏輯結構和物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的算法，而且確保經(jīng)過這些運算以后所得的新結構仍然是原來的結構類型數(shù)據(jù)結構：第九頁，共六十二頁，2022年，8月28日概括地說：

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

——

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

xy第十三頁，共六十二頁，2022年，8月28日鏈式映象以附加信息(指針)表示后繼關系需要用一個和x在一起的附加信息指示y的存儲位置yx第十四頁，共六十二頁，2022年，8月28日2.抽象數(shù)據(jù)類型

(AbstractDataType簡稱ADT)

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

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

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

物理位置相鄰.

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

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

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

struct

List

{ ElemTypelist[MaxSize]; intsize;//當前線性表長度

};線性表順序存儲結構第二十二頁，共六十二頁，2022年，8月28日一、有關空表的操作

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

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

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

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日四、有關刪除的操作

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

有序對<ai-1,ai>

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

e>

和<e,ai>

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

s->data=e;

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

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

a1a2

…an判別鏈表中最后一個結點的條件不再是“后繼是否為空”，而是“后繼是否為頭結點”。第三十三頁，共六十二頁，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日原矩陣轉置后矩陣一、三元組順序表用“三元組”表示實現(xiàn)矩陣轉置第三十八頁，共六十二頁，2022年，8月28日需要把具有相同行號的三元組結點按照列號從小到大的順序鏈接成一個單鏈表，每個三元組結點的類型可定義為：二、帶行指針向量的鏈接存儲

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日廣義表的概念

廣義表是遞歸定義的線性結構廣義表是多層次的線性結構第四十二頁，共六十二頁，2022年，8月28日廣義表結構的特點:數(shù)據(jù)元素有相對次序；2)長度為最外層包含元素個數(shù)；3)深度為所含括弧的重數(shù)；原子:深度為0;空表:深度為1;4)可以共享；5)可以是一個遞歸的表。第四十三頁，共六十二頁，2022年，8月28日廣義表的存儲結構采用頭、尾指針的鏈表結構表結點:原子結點：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日棧的應用舉例例一、數(shù)制轉換例二、括號匹配的檢驗表達式求值遞歸第五十一頁，共六十二頁，2022年，8月28日表達式求值后綴式:ab

cde/f+

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

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

結果在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