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

非數(shù)值計算程序設(shè)計問題,NiklausWirth：Programs=Algorithm+DataStructures,用抽象數(shù)據(jù)類型的觀點來解決數(shù)據(jù)結(jié)構(gòu)的問題，越來越得到人們的重視。,百家樂百家樂整理發(fā)布,第一章緒論,一、數(shù)據(jù)結(jié)構(gòu)討論的范疇,二、基本概念,三、算法和算法的度量,一、數(shù)據(jù)結(jié)構(gòu)討論的范疇,非數(shù)值計算程序設(shè)計問題,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu),二、基本概念,1.數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu),2.抽象數(shù)據(jù)類型,1.數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu),所有能被輸入到計算機中，且能被計算機處理的符號的集合。,數(shù)據(jù):,是計算機操作的對象的總稱。,是計算機處理的信息的某種特定的符號表示形式。,是數(shù)據(jù)（集合）中的一個“個體”,數(shù)據(jù)元素:,是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位,數(shù)據(jù)結(jié)構(gòu)：,帶結(jié)構(gòu)的數(shù)據(jù)元素的集合,或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。,是研究數(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)：,概括地說：,數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學(xué)模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學(xué)科。,數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:,線性結(jié)構(gòu),樹形結(jié)構(gòu),圖狀結(jié)構(gòu),集合結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu),邏輯結(jié)構(gòu)在存儲器中的映象,“數(shù)據(jù)元素”的映象？,“關(guān)系”的映象？,關(guān)系的映象方法：,順序映象,用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素,鏈?zhǔn)接诚?以附加信息(指針)表示后繼關(guān)系,需要用一個和x在一起的附加信息指示y的存儲位置,yx,2.抽象數(shù)據(jù)類型(AbstractDataType簡稱ADT),是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。,三、算法和算法的衡量,1.算法,2.算法設(shè)計的原則,3.算法效率的衡量方法和準(zhǔn)則,4.算法的存儲空間需求,算法是對解決某類問題的方法的一種描述。一個算法必須滿足以下五個重要特性：,1有窮性2確定性3可行性4有輸入5有輸出,隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同。,T(n)=O(f(n),漸近時間復(fù)雜度,第二章線性表,線性表的概念,-基本操作算法實現(xiàn),-順序存儲,-鏈?zhǔn)酱鎯?順序映象方法是：邏輯關(guān)系相鄰,物理位置相鄰.,用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素,constintMaxSize=50;,structListElemTypelistMaxSize;intsize;/當(dāng)前線性表長度;,線性表順序存儲結(jié)構(gòu),一、有關(guān)空表的操作,1.初始化操作,2.清空操作,3.判空操作,*當(dāng)前線性表長度*,二、有關(guān)查找的操作,2.查找具有給定值的元素,1.遍歷線性表操作,3.更新表中具有給定值的元素,從表頭元素起依次訪問每一個元素，并且每個元素只被訪問一次,L.list0,最后一個,L.listL.size-1,三、有關(guān)插入的操作,3.插在i位置操作,2.表頭插入一個元素,1.末尾添加一個元素,后移,for(intj=L.size;jdata=e;/生成新結(jié)點s-next=p-next;p-next=s;/插入,s,p,q=p-next;p-next=q-next;e=q-data;deleteq;,p,q,逆位序輸入建立帶頭結(jié)點的單鏈表,一、建立一個“空表”；,二、輸入數(shù)據(jù)元素an；,三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并前插；,四、依次類推，直至輸入a1為止。,L-next=p;,p-next=L-next;,最后一個結(jié)點的指針域的指針又指回第一個結(jié)點,循環(huán)鏈表,a1a2an,判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。,s-right=p-right;p-right=s;s-right-left=s;s-left=p;,p,s,插入,雙向鏈表,刪除,p-right=p-right-right;p-right-left=p;,p,第三章稀疏矩陣和廣義表,壓縮存儲方法:,一、三元組順序表,二、帶行指針向量的鏈接存儲,三、十字鏈表,稀疏矩陣的概念,原矩陣,轉(zhuǎn)置后矩陣,一、三元組順序表用“三元組”表示實現(xiàn)矩陣轉(zhuǎn)置,需要把具有相同行號的三元組結(jié)點按照列號從小到大的順序鏈接成一個單鏈表，每個三元組結(jié)點的類型可定義為：,二、帶行指針向量的鏈接存儲,rowcolvalnext,三元組,三、十字鏈表,cv,rv,1,1,3,1,4,5,2,2,-1,3,1,2,廣義表的概念,廣義表是遞歸定義的線性結(jié)構(gòu),廣義表是多層次的線性結(jié)構(gòu),廣義表結(jié)構(gòu)的特點:,數(shù)據(jù)元素有相對次序；2)長度為最外層包含元素個數(shù)；3)深度為所含括弧的重數(shù)；原子:深度為0;空表:深度為1;4)可以共享；5)可以是一個遞歸的表。,廣義表的存儲結(jié)構(gòu),采用頭、尾指針的鏈表結(jié)構(gòu),表結(jié)點:原子結(jié)點：,廣義表的運算,遞歸函數(shù)含直接或間接調(diào)用本函數(shù)語句的函數(shù),2.求廣義表的深度,1.求廣義表長度,1.求廣義表長度的遞歸算法intLenth(GLNode*GL)if(GL!=NULL)return1+Lenth(GL-next);elsereturn0;,非遞歸算法如下：intLenth(GLNode*GL)intlen=0;while(GL!=NULL)len+;GL=GL-next;returnlen;,深度=Max子表的深度+1,2.求廣義表的深度,可以直接求解的兩種簡單情況為：空表的深度=1原子的深度=0,將廣義表分解成n個子表，分別(遞歸)求得每個子表的深度，,1,1,1,L,while(L!=NULL)if(L-tag=true)intdep=Depth(L-sublist);if(depmax)max=dep;L=L-next;,L,L-sublist,L,L,L-sublist,L-sublist,第四章棧和隊列,棧的應(yīng)用舉例,例一、數(shù)制轉(zhuǎn)換例二、括號匹配的檢驗,表達(dá)式求值,遞歸,表達(dá)式求值,后綴式:abcde/f+,后綴式算符在式中出現(xiàn)的順序恰為表達(dá)式的運算順序;每個運算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達(dá)式。,如何從后綴式求值？,先找運算符，再找操作數(shù),設(shè)立操作數(shù)棧,如何從中綴式轉(zhuǎn)換成后綴式？,設(shè)立操作符棧,棧與遞歸,實現(xiàn)遞歸函數(shù)，必須利用“棧”。一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函數(shù)；反之，一個用棧實現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。,遞歸函數(shù)中的尾遞歸容易消除。,隊列的定義,鏈隊列鏈?zhǔn)接诚?循環(huán)隊列順序映象,求余:X%QueueMaxSize結(jié)果在0QueueMaxSize-1之間,Q.rear=(Q.rear+1)%QueueMaxSize;,Q.front=(Q.front+1)%QueueMaxSize;,1,0,2,3,4,5,6,7,8,9,QueueMaxSize-1,.,將新元素item的值插入到隊尾voidQinsert(QueueType,循環(huán)隊列的基本操作:,structLNodeElemTypedata;LNode*next;,隊列的鏈接存儲結(jié)構(gòu),鏈隊列類型structLinkQueueLNode*front;/隊頭指針LNode*rear;/隊尾指針;,a1,an,Q.frontQ.rear,a2,a1,an,Q.frontQ.rear,a2,進(jìn)隊(向鏈隊中插入一個元素),an+1/,Q.rear-next=newptr;Q.rear=newptr;,newptr,a1,an,