軟件工程算法課程第3章.ppt
《軟件工程算法課程第3章.ppt》由會員分享，可在線閱讀，更多相關(guān)《軟件工程算法課程第3章.ppt（79頁珍藏版）》請在裝配圖網(wǎng)上搜索。
Chapter3,List,Stacks,andQueue,,IntroducetheconceptofAbstractDataTypes(ADTS).showhowtoefficientlyperformoperationsonlists.IntroducethestackADTanditsuseinimplementingrecursion.IntroducethequeueADTanditsuseinoperatingsystemsandalgorithmdesign.,3.1AbstractDataTypes(ADTS),ADT-----asetofobjectstogetherwithasetofoperaions.Abstractdatatypesaremathematicalabstractions;nowhereinanADT’sdefinitionisthereanymentionofhowthesetofoperationsisimplemented.,3.1AbstractDataTypes(ADTS),2.dataobject---asetofinstancesorvaluesforexample:Boolean={false,true}Digit={0,1,2,3,4,5,6,7,8,9}Letter={A,B,……Z,a,b,……z}NaturalNumber={0,1,2,……}Integer={0,+1,-1,+2,-2,+3,-3,…}String={a,b,……,aa,ab,ac,……},3.1AbstractDataTypes(ADTS),3．datastructureisadataobjecttogetherwiththerelationshipsamongtheinstancesandamongtheindividualelementsthatcomposeaninstanceData_Structure={D,R}D---dataobject，R---asetofrelationshipsofallthedatamembersinD.,3.2TheListADT,L=(e1,e2,e3,…,en)listsizeisnifn=0:emptylistifn(finite)>0:e1isthefirstelementenisthelastelementeiprecedesei+1,3.2TheListADT,Example:Students=(Jack,Jill,Abe,Henry,Mary,…,Judy)Exams=(exam1,exam2,exam3)DaysofWeek=(S,M,T,W,Th,F,Sa)Months=(Jan,Feb,Mar,Apr,…,Nov,Dec),3.2TheListADT,Operations:Createalinearlistdeterminewhetherthelistisemptydeterminethelengthofthelistfindthekthoftheelementsearchforagivenelementdeletethekthelementinsertanewelementjustafterthekth,3.2TheListADT,ADTspecificationofalinearlistAbstractDateTypeLinearList{instancesorderedfinitecollectionsofzeroormoreelementsoperationsCreate();Destroy();IsEmpty();Length();Find(k,x);Search(x);Delete(k,x);Insert(k,x);Output(out);},3.2.1.SimpleArrayImplementationofLists,1.Useanarraytorepresenttheinstanceofanobject(e1,e2,………en),eachpositionofthearrayiscalledacelloranodemappingformula:location(i)=i-1O(1),3.2.1.SimpleArrayImplementationofLists,Classdefinition:program,templateclassLinearList{public:LinearList(intMaxListSize=10);~LinearList(){delete[]element;};boolIsEmpty()const{returnlength==0;}intLength()const{returnlength;}boolFind(intk,T},3.2.1.SimpleArrayImplementationofLists,Search(x)O(length),L=(a,b,d,b,e)Search(d)=3Search(a)=1Search(z)=0ACN=(1+2+……+n)/n=(1+n)*n/2n=(n+1)/2,3.2.1.SimpleArrayImplementationofLists,remove(k,x)deletethek’thelementandreturnitinxL=(a,b,c,d,e)delete(2,x)=>L=(a,c,d,e),x=b,andindexofc,d,edecreaseby1delete(0)=>errordelete(20)=>errorO(n),3.2.1.SimpleArrayImplementationofLists,AMN=∑(n-i-1)/n=(n-1+n-2+……+1+0)/n=(n-1)/2,,3.2.1.SimpleArrayImplementationofLists,insert(x,i),insertxafterthei’thelementL=(a,b,c,d,e,f,g)insert(0,h)=>L=(h,a,b,c,d,e,f,g)indexofa,b,c,d,e,f,andgincreaseby1insert(10,h)=>errorinsert(-6,h)=>errorO(n),3.2.1.SimpleArrayImplementationofLists,012n-1nAMN=∑(n-i)/(n+1)=(n+n-1+……+1+0)/(n+1)=n/2,,3.2.1.SimpleArrayImplementationofLists,2.UsearrayImplementationmerit:easySearch.shortcoming:InsertionandRemoving(Deletion)spendalotoftime.,3.2.2.LinkedLists,Inordertoavoidthelinearcostofinsertionanddeletion.1)EachnodeofadataobjectkeepsalinkorapointeraboutthelocationofotherrelevantnodesL=(e1,e2,………en),3.2.2.LinkedLists,Thefigureaboveiscalledasinglelinkedlist,andthestructureisalsocalledachainAchainisalinkedlistinwhicheachnoderepresentsoneelement.Thereisalinkorpointerfromoneelementtothenext.Thelastnodehasanullpointer.,3.2.2.LinkedLists,DeletionaelementofachainDelete(1,x),a,,b,c,d,,e,,,first=first.link;,p,,3.2.2.LinkedLists,firstgettonodejustbeforenodetoberemoved,before=first.link;,Delete(3,x),3.2.2.LinkedLists,nowchangepointerinbefore,before.link=before.link.link;,before,,,a,,,b,,,,c,,,d,,,,,e,,null,first,,,,p,,3.2.2.LinkedLists,Step1:getanode,setitsdataandlinkfields,ChainNodenewNode=newChainNode(‘f’,first);,,insertoperation----insert(0,’f’),3.2.2.LinkedLists,Step2:updatefirst,first=newNode;,,,insert(3,’f’),1.firstfindnodewhoseindexis3,,2.nextcreateanodeandsetitsdataandlinkfields,ChainNodenewNode=newChainNode(‘f’,before.link);,3.finallylinkbeforetonewNode,before.link=newNode;,Two-Stepinsert(3,’f’),before=first.link.link;newNode.link=before.link;before.link=newNode;,3.2.3ProgrammingDetails,1.Header(dummynode),3.2.2.LinkedLists,2.ClassdefinitionListNode代表結(jié)點的類LinkedListItr代表位置的類LinkedList代表表本身的類,3.2.2.LinkedLists,1)ListNodeclass,packageDataStructures;classListNode{ListNode(objecttheElement){this(theElement,null);}ListNode(objecttheElement,ListNoden){element=theElement;next=n;}objectelement;ListNodenext;},3.2.2.LinkedLists,2)Iteratorclassforlinkedlists,,packageDataStructurespublicclassLinkedListItr{LinkedListItr(ListNodetheNode){current=theNode;}publicbooleanisPastEnd(){returncurrent==null;}publicobjectretrieve(){returnisPastEnd()?Null:current.element;}publicvoidadvance(){if(!isPastEnd())current=current.next;}ListNodecurrent;},,3)LinkedListclass,,packageDataStructures;publicclassLinkedList{publicLinkedList(){header=newListNode(null);}publicbooleanisEmpty(){returnheader.next==null;}publicvoidmakeEmpty(){header.next=null;}publicLinkedListItrzeroth(){returnnewLinkedListItr(header);}publicLinkedListItrfirst(){returnnewLinkedListItr(header.next);}publicLinkedListItrfind(objectx)publicvoidremove(objectx)publicLinkedListItrfindPrevious(objectx)publicvoidinsert(objectx,LinkedListItrp)privateListNodeheader;},,MethodtoprintalistpublicstaticvoidprintList(LinkedListtheList){if(theList.isEmpty())System.out.print(“Emptylist”);else{LinkedListItritr=theList.first();for(;!Itr.isPastEnd();itr.Advance())System.out.print(itr.retrieve()+““);}System.out.println();},,Operation:ConstructorsisEmptymakeEmptyZerothandfirstreturniteratorscorrespondingtotheheaderandfirstelement.Find(x),,publicLinkedListItrfind(objectx){ListNodeitr=header.next;while(itr!=null}O(N),,Remove(x)publicvoidremove(objectx){LinkedListItrp=findprevious(x);if(p.current.next!=null)p.current.next=p.current.next.next;}O(1),,Findprevious(x)publicLinkedListItrfindPrevious(objectx){ListNodeitr=header;while(itr.next!=null}O(N),,Insert(x,p)publicvoidinsert(objectx,LinkedListItrp){if(p!=null}O(1),3.2.4.DoublyLinkedLists,,left,right,element,3.2.4.DoublyLinkedLists,operations:insertdelete,3.2.4.DoublyLinkedLists,Delete(1),P=firstNode;firstNode=p.right;firstNode.left=null;,p,,,,null,3.2.4.DoublyLinkedLists,Delete(3),p,,P.left.right=p.right;,P.right.left=p.left;,,,,,3.2.4.DoublyLinkedLists,insert(0,’f’),firstNode.left=newNode;,,newNode.left=null;newNode.right=firstNode;,firstNode=newNode,,,,3.2.4.DoublyLinkedLists,Insert(2,’f’),beforeNode,,newNode.left=beforeNode;newNode.right=beforeNode.right;,beforeNode.right.left=newNode;beforeNode.right=newNode;,,,,,3.2.4.DoublyLinkedCircularLists,,DoublyLinkedCircularListWithHeaderNode,,EmptyDoublyLinkedCircularListWithHeaderNode,headerNode,3.2.5.CircularLinkedLists,,3.2.5.CircularLinkedLists,,,,,,例子:用循環(huán)鏈表求解約瑟夫(josephus)問題約瑟夫問題：實際上是一個游戲。書中以旅行社從n個旅客中選出一名旅客，為他提供免費環(huán)球旅行服務(wù)。例，n=8,m=3（報數(shù)）從1號開始報數(shù)出列順序為：3,6,1,5,2,8,4。最后一個編號7的旅客將贏得環(huán)球旅游。,,,rear:每次指向要出隊列的前一個結(jié)點,出隊列的人也用鏈表來表示：head:指向出隊列結(jié)點鏈表的開頭結(jié)點p:指向出隊列結(jié)點鏈表的尾結(jié)點以上rear,head,p都是ListNode的一個對象。,,w=m;for(inti=1;i<=n-1;i++){1)for(intj=1;jMAX-DEGREE)thrownewoverflow();for(inti=0;i<=highPower;i++)for(intj=0;j<=rhs.highPower;j++)product.coeffArray[i+j]+=coeffArray[i]*rhs.coeffArray[j];returnproduct;},,2)ClassskeletonsforlinkedlistimplemetationofthePolynomialADT,,publicclassLiteral{//Vaviousconstractors(notshown)intcoefficient;intexponent;}publicclassPolynomial{publicPolynomial(){/*Exercise*/}publicvoidinsertTerm(intcoef,intexp){/*Exercise*/}publicvoidzeroPolynomial(){/*Exercise*/}publicPolynomialadd(Polynomialrhs){/*Exercise*/}publicPolynomialmultiply(Polynomialrhs){/*Exercise*/}publicvoidprint(){/*Exercise*/}privateListterms;/*AListofLiterals,sortedbyexponent*/},多項式相加：*問題：A(X)=2X100+3X14+2X8+1B(X)=-2X100+8X14-3X10+10X6-XA(X)+B(X)=11X14–3X10+2X8+10X6–X+1,存放非零指數(shù)的系數(shù)與指數(shù)，因此每個結(jié)點有三個域組成。,具體實現(xiàn)時，并不要再重新申請結(jié)點，完全利用原來兩個鏈表的結(jié)點。方法：設(shè)4個引用變量：pa,pb,pc,p(c++需要）1)初始化：pc,pa,pb;2)當(dāng)pa和pb都有項時,A(X)+B(X)==》A(X),pc永遠(yuǎn)指向相加時結(jié)果鏈表的最后一個結(jié)點。a)指數(shù)相等(pa.exp==pb.exp)對應(yīng)系數(shù)相加：pa.coef=pa.coef+pb.coef;p=pb(c++需要）;pb前進(jìn);if(系數(shù)相加結(jié)果為0){p=pa;pa前進(jìn);}else{pc.link=pa;pc=pa;pa前進(jìn)}b)指數(shù)不等pa.exppb.exp//pa要插入結(jié)果鏈表{pc.link=pa;pc=pa;pa前進(jìn)}3)當(dāng)兩鏈表中有一鏈表為空，則將另一鏈表鏈入結(jié)果鏈表就可以if(pb空了){pc.link=pa;}elsepc.link=pb;,算法分析：設(shè)兩個多項式的項數(shù)分別是m和n，則總的比較次數(shù)為O(m+n)最壞情況下：兩個多項式的指數(shù)項都不等且交叉遞增，如A(x):a5x5+a3x3+a1x+a0m=4比較m+n-1次B(x):b4x4+b2x2+b0n=3,3.2.6.Examples,2.RadixSort64,8,216,512,27,729,0,1,343,125288371260531287235562991823,260371531232355628728818299,3.2.6.Examples,,如何實現(xiàn)：原始要排序的數(shù)據(jù)、桶中的數(shù)據(jù)都用鏈表來實現(xiàn)。,3.2.7.CursorimplementationofLinkedLists,usearraytoimplementlinkedlist:,,P=p.nextp=cursorSpace[p].nextp.datacuesorSpace[p].data,3.2.7.CursorimplementationofLinkedLists,1)NodeanditeratorforcursorimplemetationoflinkedlistsclassCursorNode{CursorNode(objecttheElement){this(theElement,0);}CursorNode(objecttheElement,intn){element=theElement;next=n;}objectelement;intnext;},3.2.7.CursorimplementationofLinkedLists,publicclassCursorListItr{CursorListItr(inttheNode){current=theNode;}publicbooleanisPastEnd(){returncurrent==o;}publicobjectretrieve(){returnisPastEnd()?null:CursorList.cursorSpace[current].element;}publicvoidadvance(){if(!isPastEnd())current=CursorList.cursorSpace[current].next;}intcurrent;},3.2.7.CursorimplementationofLinkedLists,2)ClassskeletonforCursorListpublicclassCursorList{privatestaticintalloc()privatestaticvoidfree(intp)publicCursorList(){header=alloc();cursorSpace[header].next=0;}publicbooleanisEmpty(){returncursorSpace[header].next==0;}publicvoidmakeEmpty()publicCursorListItrzeroth(){returnnewCursorListItr(header);}publicCursorListItrfirst(){returnnewCursorListItr(cursorSpace[header].next);},,publicCursorListItrfind(objectx)publicvoidinsert(objectx,CursorListItrp)publicvoidremove(objectx)publicCursorListItrfindPrevious(objectx)privateintheader;staticCursorNode[]cursorSpace;privatestaticfinalintSPACE-SIZE=100;static{cursorSpace=newCursorNode[SPACE-SIZE];for(inti=0;i下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
14.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 軟件工程 算法 課程
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://www.hcyjhs8.com/p-3272862.html