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

1、非數(shù)值計(jì)算程序設(shè)計(jì)問題第1頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四第一章 緒論第2頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四一、數(shù)據(jù)結(jié)構(gòu)討論的范疇二、基本概念三、算法和算法的度量第3頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四一、數(shù)據(jù)結(jié)構(gòu)討論的范疇非數(shù)值計(jì)算程序設(shè)計(jì)問題數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 第4頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四二、基本概念1. 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2. 抽象數(shù)據(jù)類型第5頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四1. 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu) 所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號的集合。數(shù)據(jù):是計(jì)算

2、機(jī)操作的對象的總稱。 是計(jì)算機(jī)處理的信息的某種特定的符號表示形式。第6頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位第7頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合 或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。第8頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算以后所得的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型數(shù)據(jù)結(jié)構(gòu)：第9頁，共62頁，20

3、22年，5月20日，3點(diǎn)26分，星期四概括地說： 數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。第10頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)第11頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四數(shù)據(jù)的存儲結(jié)構(gòu) 邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的映象 ？“關(guān)系”的映象 ？第12頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四關(guān)系的映象方法：順序映象用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素 x y第13頁，共62頁，2022年，5月20日

4、，3點(diǎn)26分，星期四鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和 x 在一起的附加信息指示 y 的存儲位置y x第14頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四2. 抽象數(shù)據(jù)類型 (Abstract Data Type 簡稱ADT) 是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。第15頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四三、算法和算法的衡量1.算法2. 算法設(shè)計(jì)的原則3. 算法效率的衡量方法和準(zhǔn)則4. 算法的存儲空間需求第16頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 算法是對解決某類問題的方法的一種描述。一個(gè)算法必須滿足以下五個(gè)重要特

5、性：1有窮性 2確定性 3可行性4有輸入 5有輸出第17頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 隨著問題規(guī)模 n 的增長，算法執(zhí)行時(shí)間的增長率和 f(n) 的增長率相同。T (n) = O(f(n) 漸近時(shí)間復(fù)雜度第18頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 第二章 線性表第19頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四線性表的概念-基本操作算法實(shí)現(xiàn)-順序存儲-鏈?zhǔn)酱鎯Φ?0頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四順序映象方法是： 邏輯關(guān)系相鄰, 物理位置相鄰. 用一組地址連續(xù)的存儲單元 依次存放線性表中的數(shù)據(jù)元素 a1 a2

6、ai-1 ai an基地址第21頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四const int MaxSize=50; struct List ElemType listMaxSize; int size; /當(dāng)前線性表長度 ;線性表順序存儲結(jié)構(gòu)第22頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四一、有關(guān)空表的操作 1.初始化操作2.清空操作3.判空操作*當(dāng)前線性表長度*第23頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四二、有關(guān)查找的操作2.查找具有給定值的元素 1.遍歷線性表操作3.更新表中具有給定值的元素第24頁，共62頁，2022年，5月20日，3點(diǎn)26

7、分，星期四 從表頭元素起依次訪問每一個(gè)元素，并且每個(gè)元素只被訪問一次 a1 a2 ai-1 ai an基地址L.list0最后一個(gè)L.listL.size-1第25頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四三 、有關(guān)插入的操作 3.插在i位置操作2. 表頭插入一個(gè)元素1.末尾添加一個(gè)元素后移第26頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的長度增1i位置for (int j=L.size; j=i; j-) L.listj=L.listj-1; 最后的位置 L.size第27頁，共62頁，2022年

8、，5月20日，3點(diǎn)26分，星期四四、有關(guān)刪除的操作 2.刪除i位置元素操作1.刪除表頭元素操作前移第28頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四ai-1 插入、刪除、建立等操作 在單鏈表中的實(shí)現(xiàn)： 有序?qū)?改變?yōu)?和 eaiai-1第29頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四s = new LNode; s-data = e; /生成新結(jié)點(diǎn)s-next = p-next; p-next = s; /插入 eai-1aiai-1sp第30頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四ai-1aiai+1ai-1q = p-next; p-next =

9、q-next; e = q-data; delete q;pq第31頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四逆位序輸入建立帶頭結(jié)點(diǎn)的單鏈表一、建立一個(gè)“空表”； 二、輸入數(shù)據(jù)元素an； 三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并前插；四、依次類推，直至輸入a1為止。L-next = p;p-next = L-next;第32頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)循環(huán)鏈表 a1 a2 an 判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。第33頁，共62頁，2022年，5月20日，3點(diǎn)26分，

10、星期四ai-1aies-right = p-right; p-right = s;s-right-left = s; s-left = p;psai-1ai插入雙向鏈表第34頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四ai-1刪除aiai+1p-right = p-right-right;p-right-left = p;pai-1第35頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四第三章 稀疏矩陣和廣義表第36頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四壓縮存儲方法:一、三元組順序表二、帶行指針向量的鏈接存儲三、十字鏈表稀疏矩陣的概念第37頁，共62頁，20

11、22年，5月20日，3點(diǎn)26分，星期四原矩陣轉(zhuǎn)置后矩陣一、三元組順序表用“三元組”表示實(shí)現(xiàn)矩陣轉(zhuǎn)置第38頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 需要把具有相同行號的三元組結(jié)點(diǎn)按照列號從小到大的順序鏈接成一個(gè)單鏈表，每個(gè)三元組結(jié)點(diǎn)的類型可定義為：二、帶行指針向量的鏈接存儲 row col val next第39頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四1 2 141 5 -52 2 -73 1 363 4 28 三元組行指針向量2 2 -7 3 1 36 3 4 28 1 5 -5 1 2 14 vector/第40頁，共62頁，2022年，5月20日，3點(diǎn)26分

12、，星期四三、 十字鏈表cvrv3 0 0 50 -1 0 02 0 0 011314522-1312第41頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四廣義表的概念 廣義表是遞歸定義的線性結(jié)構(gòu)廣義表是多層次的線性結(jié)構(gòu)第42頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四廣義表結(jié)構(gòu)的特點(diǎn):數(shù)據(jù)元素有相對次序； 2)長度為最外層包含元素個(gè)數(shù)；3)深度為所含括弧的重?cái)?shù)； 原子:深度為 0;空表:深度為 1; 4)可以共享；5)可以是一個(gè)遞歸的表。第43頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 廣義表的存儲結(jié)構(gòu)采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn):原子結(jié)點(diǎn)：tag=1 su

13、blist nexttag=0 data next第44頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四廣義表的運(yùn)算 遞歸函數(shù) 含直接或間接調(diào)用本函數(shù)語句的函數(shù) 2.求廣義表的深度1.求廣義表長度第45頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四1.求廣義表長度的遞歸算法 int Lenth(GLNode* GL) if(GL!=NULL) return 1+Lenth(GL-next); else return 0; 第46頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 非遞歸算法如下： int Lenth(GLNode* GL) int len=0; whil

14、e(GL!=NULL) len+; GL=GL-next; return len; 第47頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四深度=Max 子表的深度 +12.求廣義表的深度可以直接求解的兩種簡單情況為： 空表的深度 = 1 原子的深度 = 0 將廣義表分解成 n 個(gè)子表，分別 (遞歸)求得每個(gè)子表的深度，第48頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 1 1 1 L while(L!=NULL) if(L-tag=true) int dep=Depth(L-sublist); if(depmax) max=dep; L=L-next; LL-sublist

15、LLL-sublistL-sublist第49頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四第四章 棧和隊(duì)列第50頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四棧的應(yīng)用舉例例一、 數(shù)制轉(zhuǎn)換例二、 括號匹配的檢驗(yàn)表達(dá)式求值遞歸第51頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四表達(dá)式求值后綴式: a b c d e / f + 后綴式算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。第52頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)設(shè)立操作數(shù)棧 如何從中綴式轉(zhuǎn)

16、換成后綴式？設(shè)立操作符棧第53頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四棧與遞歸 實(shí)現(xiàn)遞歸函數(shù)，必須利用“?！?。一個(gè)遞歸函數(shù)必定能改寫為利用棧實(shí)現(xiàn)的非遞歸函數(shù)；反之，一個(gè)用棧實(shí)現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。遞歸函數(shù)中的尾遞歸容易消除。第54頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四隊(duì)列的定義鏈隊(duì)列鏈?zhǔn)接诚笱h(huán)隊(duì)列順序映象第55頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四求余:X %QueueMaxSize 結(jié)果在0 QueueMaxSize-1之間Q.rear=(Q.rear+1)%QueueMaxSize; Q.front=(Q.front+1)%

17、QueueMaxSize;1023456789QueueMaxSize-1.第56頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 將新元素item的值插入到隊(duì)尾 void Qinsert(QueueType& Q, const ElemType& item); 從隊(duì)列Q中刪除隊(duì)首元素并返回之 ElemType Qdelete (QueueType& Q); 循環(huán)隊(duì)列的基本操作:第57頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 struct LNode ElemType data; LNode *next; ; 隊(duì)列的鏈接存儲結(jié)構(gòu)第58頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四 鏈隊(duì)列類型 struct LinkQueue LNode *front; /隊(duì)頭指針 LNode *rear; /隊(duì)尾指針 ;a1anQ.frontQ.reara2第59頁，共62頁，2022年，5月20日，3點(diǎn)26分，星期四a1anQ.frontQ.reara2進(jìn)隊(duì) ( 向鏈隊(duì)中插入一個(gè)元素)an+1 / Q.rear-next=newptr;Q.rear=