非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題

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

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

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

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

——

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

xy第13頁(yè)，共62頁(yè)，2023年，2月20日，星期四鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置yx第14頁(yè)，共62頁(yè)，2023年，2月20日，星期四2.抽象數(shù)據(jù)類型

(AbstractDataType簡(jiǎn)稱ADT)

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

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

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

物理位置相鄰.

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

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

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

struct

List

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

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

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

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

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

3.插在i位置操作2.

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

…ana1a2…ai-1

…ai

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

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

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

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

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

e>

和<e,ai>

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

s->data=e;

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

p->next=s;

//插入

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

p->next=q->next;

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

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

a1a2

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

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

2

141

5

-52

2

-731

3634

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

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

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

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

int

Lenth(GLNode*GL)

{if(GL!=NULL)

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

intLenth(GLNode*GL)

{intlen=0;

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

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

空表的深度=1

原子的深度=0

將廣義表分解成n個(gè)子表，分別

(遞歸)求得每個(gè)子表的深度，第48頁(yè)，共62頁(yè)，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頁(yè)，共62頁(yè)，2023年，2月20日，星期四第四章棧和隊(duì)列第50頁(yè)，共62頁(yè)，2023年，2月20日，星期四棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)表達(dá)式求值遞歸第51頁(yè)，共62頁(yè)，2023年，2月20日，星期四表達(dá)式求值后綴式:ab

cde/f+

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

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

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

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

將新元素item的值插入到隊(duì)尾

voidQinsert(QueueType&Q,constElemType&item);

從隊(duì)列Q中刪除隊(duì)首元素并返回之

ElemTypeQdelete(QueueType&Q);

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

structLNode

{

ElemType

data;