树德科技大学资讯管理系DataStructures一般化串列多项式相加多项.pptx
《树德科技大学资讯管理系DataStructures一般化串列多项式相加多项.pptx》由会员分享,可在线阅读,更多相关《树德科技大学资讯管理系DataStructures一般化串列多项式相加多项.pptx(44页珍藏版)》请在咨信网上搜索。
1、1 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures資料結構資料結構資料結構資料結構Chapter 4Chapter 42 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊堆疊(Stack)p定義定義資料有序存取而成的串列資料有序存取而成的串列資料存取的順序是後進先出資料存取的順序是後進先出(LIFO),如,如同玩積木同玩積木3 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures 意義意義p三種狀態三種狀態堆疊是空
2、的堆疊是空的(top=0)堆疊是滿的堆疊是滿的(top=n)介於前面兩者之間介於前面兩者之間p二種動作二種動作加入加入(add)動作動作刪除刪除(delete)動作動作p例題例題 ko4_1(堆疊程式堆疊程式)4 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresStack 類別類別pJava提供了一個與類別有關的提供了一個與類別有關的Stack 類別,主類別,主要用於執行後進先出的作業。要用於執行後進先出的作業。建構子建構子 Stack()方法方法add(object),clear(),clone(),copy(Stack),elem
3、ents(),equals(Object),equals(Stack),finish(),hashCode(),isEmpty(),maxSize(),pop(),push(),remove(),size(),start(),swap(Stack),top(),toString()p例題例題 ko4_1a(利用利用Stack 類別寫成的堆疊程式類別寫成的堆疊程式)pP.112例題、例題、P.113例題例題5 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法及傳回遞迴方法及傳回值值
4、的應用處理的應用處理p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算6 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用以副程式呼叫副程式的方式,先呼叫的副程以副程式呼叫副程式的方式,先呼叫的副程式被放入堆疊式被放入堆疊內內,先到放置於底層,後到放,先到放置於底層,後到放置於上層。置於上層。p遞迴方法及傳回遞迴方法及傳回值值的應用處理的應用處理遞迴方法
5、及傳回遞迴方法及傳回值值也是應用堆疊的方式處理也是應用堆疊的方式處理資料,資料,also see example ko2_1p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算7 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方法的應用遞迴方法的應用p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算由運算元由運算元(oper
6、ator)、運算子、運算子(operand)組成的組成的運算式,都是應用堆疊的方式處理。運算式,都是應用堆疊的方式處理。See next section for detailp二元樹的追蹤二元樹的追蹤二元樹的追蹤是拜訪二元樹的每一個節點,二元樹的追蹤是拜訪二元樹的每一個節點,是應用堆疊的方式處理。是應用堆疊的方式處理。See chapter 5p系統中斷處理系統中斷處理p使用暫存器堆疊指標執行堆疊運算使用暫存器堆疊指標執行堆疊運算8 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures堆疊的應用堆疊的應用p副程式的應用副程式的應用p遞迴方
7、法的應用遞迴方法的應用p運算式運算式(前序式、中序式、後序式前序式、中序式、後序式)的運算的運算p二元樹的追蹤二元樹的追蹤p系統中斷處理系統中斷處理系統中斷處理是由中斷的來源裝置送出一個中斷向量,系統中斷處理是由中斷的來源裝置送出一個中斷向量,CPU依據中斷向量跳到所指的位址之前,會先將傳回位垃依據中斷向量跳到所指的位址之前,會先將傳回位垃(return address)及狀態暫存器的資料儲存到堆疊中,等完成及狀態暫存器的資料儲存到堆疊中,等完成中斷處理後,再從堆疊中取出資料,繼續執行中斷前未完中斷處理後,再從堆疊中取出資料,繼續執行中斷前未完成的工作。成的工作。p使用暫存器堆疊指標執行堆疊運
8、算使用暫存器堆疊指標執行堆疊運算堆疊指標是一種持殊暫存器,程設師利用堆疊指標取得堆堆疊指標是一種持殊暫存器,程設師利用堆疊指標取得堆疊中最上層的資料;並利用疊中最上層的資料;並利用push將資料存放於堆疊中,利將資料存放於堆疊中,利用用pop將資料從堆疊中取出。將資料從堆疊中取出。9 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures運算式運算式p算術運算式由運算元算術運算式由運算元(operator)、運算子、運算子(operand)組成。組成。運算元:運算元:09,大小寫大小寫az運算子:運算子:算術運算子算術運算子關係運算子關係運
9、算子邏輯運算子邏輯運算子指定運算子指定運算子條件運算子條件運算子位元運算子位元運算子10 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures運算式運算式p算術運算式有三種型式:算術運算式有三種型式:中序式中序式(infix)習慣性的寫法習慣性的寫法將運算子放於兩個運算元的中間。如:將運算子放於兩個運算元的中間。如:x*y前序式前序式(prefix)將運算子放於兩個運算元之前。如:將運算子放於兩個運算元之前。如:*xy後序式後序式(postfix)將運算子放於兩個運算元之後。如:將運算子放於兩個運算元之後。如:xy*11 樹德科技大學樹德
10、科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp中序式轉換成前序式步驟如下:中序式轉換成前序式步驟如下:Step 1:將運算式依照運算子優先權全部加上小括號將運算式依照運算子優先權全部加上小括號()Step 2:將運算子取代左邊的小括號,直到左邊的小將運算子取代左邊的小括號,直到左邊的小括號完全消失為止括號完全消失為止Step 3:刪除所有右邊的小括號刪除所有右邊的小括號p如:如:a+b*c-d。1.(a+(b*c)-d)2.(a+*bc)-d)3.(+a*bc)-d)4.-+a*bc)d)5.-+a*bcd中序式轉換成前序式中序式轉換成前序式Pa
11、ge117例題例題*212 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp中序式轉換成後序式步驟如下:中序式轉換成後序式步驟如下:Step 1:將運算式依照運算子優先權全部加上小括號將運算式依照運算子優先權全部加上小括號()Step 2:將運算子取代右邊的小括號,直到右邊小括號完全消失為止將運算子取代右邊的小括號,直到右邊小括號完全消失為止Step 3:刪除所有左邊的小括號刪除所有左邊的小括號p如:如:a+b*c-d。1.(a+(b*c)-d)2.(a+(bc*)-d)3.(a(bc*+-d)4.(a(bc*+d-5.abc*+d
12、-pPage118&119例題例題pPage 119例題例題ko4_2中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式中序式轉換成後序式13 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp前序式轉換成中序式步驟如下:前序式轉換成中序式步驟如下:Step 1:由右至左讀取運算式。由右至左讀取運算式。Step 2:若讀取的是運算子,將右邊兩個運算元連同若讀取的是運算子,將右邊兩個運算元連同運算子以小括號圍起來,直到所有運算子都被圍起來運算子以小括號圍起來,直到所有運算子都被圍起來為止。為止。Step 3:將運算子移到兩個運算元之
13、間,最後整理,將運算子移到兩個運算元之間,最後整理,刪除不必要的小括號。刪除不必要的小括號。p例題:將例題:將前序式前序式+*/ab-cde 轉換成中序式轉換成中序式Step 1前序式前序式+*/ab-cde 987654321Step 2+*(/ab)(-cd)e +(*(/ab)(-cd)e (+(*(/ab)(-cd)e)Step 3(+(*(/ab)(-cd)e)(+(*(a/b)(c-d)e)(+(a/b)*(c-d)e)(a/b)*(c-d)+e)a/b*(c-d)+e 中序式中序式前序式轉換成中序式前序式轉換成中序式14 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data
14、StructuresData Structuresp例題:將例題:將前序式前序式+*a-bc/de 轉換成中序式轉換成中序式Step 1前序式前序式+*a-bc/de 987654321Step 2+*a(-bc)(/de)+(*a(-bc)(/de)(+(*a(-bc)(/de)Step 3(+(*a(-bc)(/de)(+(*a(b-c)(d/e)(+(a*(b-c)(d/e)(a*(b-c)+(d/e)a*(b-c)+d/e中序式中序式p例題:例題:前序式前序式+*a-bc/de,其,其值值為何?為何?(其中其中a=3,b=8,c=3,d=9,e=3)前序式前序式+*a-bc/de a*
15、(b-c)+d/e中序式中序式已知已知a=3,b=8,c=3,d=9,e=3代入中序式代入中序式 a*(b-c)+d/ea*(b-c)+d/e=3*(8-3)+9/3=18前序式轉換成中序式前序式轉換成中序式15 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp後序式轉換成中序式步驟如下:後序式轉換成中序式步驟如下:Step 1:由左至右讀取運算式。由左至右讀取運算式。Step 2:若讀取的是運算子,將左邊兩個運算元連同若讀取的是運算子,將左邊兩個運算元連同運算子以小括號圍起來,直到所有運算子都被圍起來運算子以小括號圍起來,直到所有
16、運算子都被圍起來為止。為止。Step 3:將運算子移到兩個運算元之間,最後整理,將運算子移到兩個運算元之間,最後整理,刪除不必要的小括號。刪除不必要的小括號。p例題:將例題:將後序式後序式 ab*cd+-a/轉換成中序式轉換成中序式Step 1前序式前序式 ab*cd+-a/123456789Step 2 ab*cd+-a/(ab*)(cd+)-a/(ab*)(cd+)-)a/)Step 3(ab*)(cd+)-)a/)(a*b)(c+d)-)a/)(a*b)-(c+d)a/)(a*b)-(c+d)/a)(a*b-(c+d)/a中序式中序式後序式轉換成中序式後序式轉換成中序式16 樹德科技大學
17、樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp例題:例題:若若a=2,b=3,c=4,d=5,計算後序式計算後序式 ab*cd+-a/的的值值為何為何後序式後序式 ab*cd+-a/(a*b-(c+d)/a中序式中序式已知已知a=2,b=3,c=4,d=5代入中序式代入中序式(a*b-(c+d)/a(a*b-(c+d)/a=(2*3-(4+5)/2=-3/2後序式轉換成中序式後序式轉換成中序式17 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures前序式轉換成後序式前序式轉換成後序式p
18、前序式轉換成後序式:前序式轉換成後序式:前序式轉換成中序式,中序式轉換成後序式。前序式轉換成中序式,中序式轉換成後序式。p例題:將例題:將前序式前序式=a+-bc/*de-fg 轉換成後序式轉換成後序式前序式轉換成中序式前序式轉換成中序式Step 1 前序式前序式=a+-bc/*de-fg 13 12 11 10 9 8 7 6 5 4 3 2 1Step 2 =a+-bc/*de-fg=a+-bc/(*de)(-fg)=a+(-bc)(/(*de)(-fg)=a(+(-bc)(/(*de)(-fg)(=a(+(-bc)(/(*de)(-fg)Step 3 a(+(-bc)(/(*de)(-f
19、g)(=a(+(-bc)(/(d*e)(f-g)(=a(+(b-c)(d*e)/(f-g)(=a(+(-bc)(/(*de)(-fg)a=b-c+d*e/(f-g)中序式中序式中序式轉換成後序式中序式轉換成後序式Step 1中序式中序式 a=b-c+d*e/(f-g)(a=(b-c)+(d*e/(f-g)Step 2(a=(b-c)+(d*e/(fg-)(a=(b-c)+(de*/(fg-)(a=(bc-+(de*(fg-/)(a=(bc-(de*(fg-/+)(a(bc-(de*(fg-/+=Step 3(a(bc-(de*(fg-/+=abc-de*fg-/+=18 樹德科技大學樹德科技大
20、學 資訊管理系資訊管理系 Data StructuresData Structures前序式轉換成後序式前序式轉換成後序式p直接由前序式轉換成後序式:直接由前序式轉換成後序式:p例題:將例題:將前序式前序式 a+-bc/*de-fg 轉換成後序式轉換成後序式Step 1由右至左讀取運算式由右至左讀取運算式前序式前序式=a+-bc/*de-fg 13 12 11 10 9 8 7 6 5 4 3 2 1Step 2若讀取的是運算子,將右邊兩個運算元連同運算子若讀取的是運算子,將右邊兩個運算元連同運算子以小括號圍起來,直到所有運算子都被圍起來為止。以小括號圍起來,直到所有運算子都被圍起來為止。=a
21、+-bc/*de-fg=a+-bc/(*de)(-fg)=a+(-bc)(/(*de)(-fg)=a(+(-bc)(/(*de)(-fg)(=a(+(-bc)(/(*de)(-fg)Step 3將運算子取代相對應的右邊小括號,直到右邊小括將運算子取代相對應的右邊小括號,直到右邊小括號都消失為止。號都消失為止。(=a(+(-bc)(/(*de)(-fg)(=a(+(-bc)(/(*de)(fg-)(=a(+(-bc)(de*(fg-/)(=a(+(bc-(de*(fg-/)(=a(bc-(de*(fg-/+)/)(a(bc-(de*(fg-/+=Step 4 刪除所有左小括號刪除所有左小括號(a
22、(bc-(de*(fg-/+=abc-de*fg-/+=p後序式轉換成前序式方法類似後序式轉換成前序式方法類似19 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列(Queue)p佇列是先進先出佇列是先進先出(First In First Out,FIFO),如:,如:排隊買票,先排隊者先買票排隊買票,先排隊者先買票排隊買票,先排隊者先買票排隊買票,先排隊者先買票 排隊上車,先到者先上車排隊上車,先到者先上車排隊上車,先到者先上車排隊上車,先到者先上車 列印文件列印文件列印文件列印文件 磁碟機讀取或寫入資料磁碟機讀取或寫入資料
23、磁碟機讀取或寫入資料磁碟機讀取或寫入資料pp先到者先處理,後到者後處理先到者先處理,後到者後處理先到者先處理,後到者後處理先到者先處理,後到者後處理購購票票口口1 2 3 4 5 加入加入(add)離開離開(刪除刪除 delete)前端前端(front)後端後端(rear)20 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures佇列佇列p佇列是一個資料有序的串列,資料加入與刪除佇列是一個資料有序的串列,資料加入與刪除的動作,發生在不同的位置。的動作,發生在不同的位置。p資料加入的一端稱為尾端資料加入的一端稱為尾端(rear),資料出來的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 树德 科技大学 资讯 管理 DataStructures 一般化 串列 多项式 相加 多项
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。