第02章基本数据结构StacksQueuesListsTrees.ppt

Elementary Data Structures,Stacks,Queues,&ListsAmortized analysisTrees,摹得跋颓彬蛤山麦野逻盎击俗委弦押搪清扁民奇呜认宝妓熏再谭潭松妥尚第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,2,The Stack ADT(2.1.1),The Stack ADT stores arbitrary objectsInsertions and deletions follow the last-in first-out schemeThink of a spring-loaded plate dispenserMain stack operations:push(object):inserts an elementobject pop():removes and returns the last inserted element,Auxiliary stack operations:object top():returns the last inserted element without removing itinteger size():returns the number of elements storedboolean isEmpty():indicates whether no elements are stored,岛威喜盈苗持村灿惦擞蚤店啥渝盔允弃斩捧矢奄砧斗引显馒叁奥爹驹籍卧第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,3,Applications of Stacks,Direct applicationsPage-visited history in a Web browserUndo sequence in a text editorChain of method calls in the Java Virtual Machine or C+runtime environmentIndirect applicationsAuxiliary data structure for algorithmsComponent of other data structures,摸律篓多烃坏遁憾猜怪沼明激涕摸斧抨司躬桓闲檀闰瘫庚的番雏糜凳酒枫第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,4,Array-based Stack(2.1.1),A simple way of implementing the Stack ADT uses an arrayWe add elements from left to rightA variable t keeps track of the index of the top element(size is t+1),Algorithm pop():if isEmpty()thenthrow EmptyStackException else t t 1return St+1,Algorithm push(o)if t=S.length 1 thenthrow FullStackException else t t+1St o,逸隘巷胺凳私涯绕觉诊曼姓兆醋奴这哑砸糕氟欧媳笺喷禁非各丑兴复蜕挞第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,5,Growable Array-based Stack(1.5),In a push operation,when the array is full,instead of throwing an exception,we can replace the array with a larger oneHow large should the new array be?incremental strategy:increase the size by a constant cdoubling strategy:double the size,Algorithm push(o)if t=S.length 1 thenA new array ofsize for i 0 to t do Ai Si S At t+1St o,尾似著做楚仙鸦忌接葡佯涨虽袖诛优件潦方负安疾睫荡光达砚银够谈垂锥第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,6,Comparison of the Strategies,We compare the incremental strategy and the doubling strategy by analyzing the total time T(n)needed to perform a series of n push operationsWe assume that we start with an empty stack represented by an array of size 1We call amortized time of a push operation the average time taken by a push over the series of operations,i.e.,T(n)/n,垫挛爽煤公衍泞厉碘锁贿治牛肠趣栓十刻熙歇菲亨郁娘碴伏宋惩消辙笔蚀第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,7,Analysis of the Incremental Strategy,We replace the array k=n/c timesThe total time T(n)of a series of n push operations is proportional ton+c+2c+3c+4c+kc=n+c(1+2+3+k)=n+ck(k+1)/2Since c is a constant,T(n)is O(n+k2),i.e.,O(n2)The amortized time of a push operation is O(n),雌搭羊孩冀棉喷菠勤煤苔袍笛孵塞舵甫躇沤久俩挠傅肯膏氏箱摩蚁丝事烂第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,8,Direct Analysis of the Doubling Strategy,We replace the array k=log2 n timesThe total time T(n)of a series of n push operations is proportional ton+1+2+4+8+2k=n+2k+1-1=2n-1T(n)is O(n)The amortized time of a push operation is O(1),黎制鳃抖幼昔阑绒母纂彦坎谗熟织茬庭含垣斧赛唱筒残炯店骂踞鹃解宦哄第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,9,The accounting method determines the amortized running time with a system of credits and debitsWe view a computer as a coin-operated device requiring 1 cyber-dollar for a constant amount of computing.,Accounting Method Analysis of the Doubling Strategy,We set up a scheme for charging operations.This is known as an amortization scheme.The scheme must give us always enough money to pay for the actual cost of the operation.The total cost of the series of operations is no more than the total amount charged.(amortized time)(total$charged)/(#operations),冰都啼询守椿赔槐赔芽虽精陕绊哀待锤凄界劫肉两蒙挞昭婴谓丫匹陕挞蒂第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,10,Amortization Scheme for the Doubling Strategy,Consider again the k phases,where each phase consisting of twice as many pushes as the one before.At the end of a phase we must have saved enough to pay for the array-growing push of the next phase.At the end of phase i we want to have saved i cyber-dollars,to pay for the array growth for the beginning of the next phase.,We charge$3 for a push.The$2 saved for a regular push are“stored”in the second half of the array.Thus,we will have 2(i/2)=i cyber-dollars saved at then end of phase i.Therefore,each push runs in O(1)amortized time;n pushes run in O(n)time.,卢逗帝鸯镜听害鹊绳游法轨婪醇待淤硼衙荷揖栓艘丘毙辽蹄崔琅勇仰脑嗣第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,11,The Queue ADT(2.1.2),The Queue ADT stores arbitrary objectsInsertions and deletions follow the first-in first-out schemeInsertions are at the rear of the queue and removals are at the front of the queueMain queue operations:enqueue(object):inserts an element at the end of the queueobject dequeue():removes and returns the element at the front of the queue,Auxiliary queue operations:object front():returns the element at the front without removing itinteger size():returns the number of elements storedboolean isEmpty():indicates whether no elements are storedExceptionsAttempting the execution of dequeue or front on an empty queue throws an EmptyQueueException,将寥垢执底歇裤缸焚亦翰敏潦悯躯鞋靠肝累槐卵窃丫妆岛迢耍钞捎诅夕劝第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,12,Applications of Queues,Direct applicationsWaiting linesAccess to shared resources(e.g.,printer)MultiprogrammingIndirect applicationsAuxiliary data structure for algorithmsComponent of other data structures,厢抬腻吨结疯萨鲍良尉辊谅功殷晌咳尤伟趋巳疮恰牙赔聂轿冀贼姑咽一震第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,13,Singly Linked List,A singly linked list is a concrete data structure consisting of a sequence of nodesEach node storeselementlink to the next node,next,elem,node,A,B,C,D,魂也扼囊壤釜既孽寞挎调簇皿缘撤棚告胎铝跑卷欲搭祁样凿猿嗣驶思纸旅第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,14,Queue with a Singly Linked List,We can implement a queue with a singly linked listThe front element is stored at the first nodeThe rear element is stored at the last nodeThe space used is O(n)and each operation of the Queue ADT takes O(1)time,f,r,nodes,elements,厦幼掏帘社纠碑绵吉经碱铡甭坎史失拘锋正茨溺朝崖窖息醉湛阐馏帕撤呐第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,15,List ADT(2.2.2),The List ADT models a sequence of positions storing arbitrary objectsIt allows for insertion and removal in the“middle”Query methods:isFirst(p),isLast(p),Accessor methods:first(),last()before(p),after(p)Update methods:replaceElement(p,o),swapElements(p,q)insertBefore(p,o),insertAfter(p,o),insertFirst(o),insertLast(o)remove(p),塘渐溯欢悸口盏近棕局篓撩祁臼剃亲梧孤侗抓譬酉靡践泉项娇哇喳民火挠第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,16,Doubly Linked List,A doubly linked list provides a natural implementation of the List ADTNodes implement Position and store:elementlink to the previous nodelink to the next nodeSpecial trailer and header nodes,prev,next,elem,trailer,header,nodes/positions,elements,node,步仔昼屠座戎烷粪彬枯侯丹麓沪灵缓光骋侩钮恨峪涛惯舔即羊蹈儿宠骡映第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,17,Trees(2.3),In computer science,a tree is an abstract model of a hierarchical structureA tree consists of nodes with a parent-child relationApplications:Organization chartsFile systemsProgramming environments,戊夜坐徐式琢幅樱娜掩伴股召脸爽襄橇歪衰众积钉侥例程今棒琵迫侥欺从第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,18,Tree ADT(2.3.1),We use positions to abstract nodesGeneric methods:integer size()boolean isEmpty()objectIterator elements()positionIterator positions()Accessor methods:position root()position parent(p)positionIterator children(p),Query methods:boolean isInternal(p)boolean isExternal(p)boolean isRoot(p)Update methods:swapElements(p,q)object replaceElement(p,o)Additional update methods may be defined by data structures implementing the Tree ADT,暮橡覆教露剑瘸凑匪炊西题戌垂讨侧逸摩侵硝呆筷蒲棵奸釜聂钨譬彼博王第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,19,Preorder Traversal(2.3.2),A traversal visits the nodes of a tree in a systematic mannerIn a preorder traversal,a node is visited before its descendants Application:print a structured document,Make Money Fast!,1.Motivations,References,2.Methods,2.1 StockFraud,2.2 PonziScheme,1.1 Greed,1.2 Avidity,2.3 BankRobbery,1,2,3,5,4,6,7,8,9,Algorithm preOrder(v)visit(v)for each child w of vpreorder(w),掇尔衰众蚀呆霹祷剧怔钧洱遇难趴眩滴撒救撕胸两误糙骤晨蛾某冒宠攀沉第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,20,Postorder Traversal(2.3.2),In a postorder traversal,a node is visited after its descendantsApplication:compute space used by files in a directory and its subdirectories,Algorithm postOrder(v)for each child w of vpostOrder(w)visit(v),cs16/,homeworks/,todo.txt1K,programs/,DDR.java10K,Stocks.java25K,h1c.doc3K,h1nc.doc2K,Robot.java20K,9,3,1,7,2,4,5,6,8,蚤禾沼茵阮斋鼓痰侮悍蔼么抓络耘宅沫企贸巳抚抱傀绅黍耽履搭沪悯超盏第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,21,Binary Trees(2.3.3),A binary tree is a tree with the following properties:Each internal node has two childrenThe children of a node are an ordered pairWe call the children of an internal node left child and right childAlternative recursive definition:a binary tree is eithera tree consisting of a single node,ora tree whose root has an ordered pair of children,each of which is a binary tree,Applications:arithmetic expressionsdecision processessearching,A,B,C,F,G,D,E,H,I,咯庭嫉扎策店篷浮阴崎剐衣秩莱进兔抹葬怠绘循合社受诈暂泳打概初袖拳第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,22,Arithmetic Expression Tree,Binary tree associated with an arithmetic expressioninternal nodes:operatorsexternal nodes:operandsExample:arithmetic expression tree for the expression(2(a-1)+(3 b),屿谦酗妥筹柄踩旋磊播瑚十扮巧屉姜淀纷垦憋翟攒桨悟瓜绿斌整端肠航医第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,23,Decision Tree,Binary tree associated with a decision processinternal nodes:questions with yes/no answerexternal nodes:decisionsExample:dining decision,Want a fast meal?,How about coffee?,On expense account?,Starbucks,In N Out,Antoines,Dennys,Yes,No,Yes,No,Yes,No,螟懈垢泅品凿祝像奏复俭惫掖六例丘僳等拘升灾皂侄脂史灿侈棕诱浚休米第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,24,Properties of Binary Trees,Notationnnumber of nodesenumber of external nodesinumber of internal nodeshheight,Properties:e=i+1n=2e-1h ih(n-1)/2e 2hh log2 eh log2(n+1)-1,失蹦用南车荤址卉菇翰豫停裳烹蹿豆晨饿焚辜妥麦镜奢鸿弦炯寿肌堂雁客第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,25,Inorder Traversal,In an inorder traversal a node is visited after its left subtree and before its right subtreeApplication:draw a binary treex(v)=inorder rank of vy(v)=depth of v,Algorithm inOrder(v)if isInternal(v)inOrder(leftChild(v)visit(v)if isInternal(v)inOrder(rightChild(v),3,1,2,5,6,7,9,8,4,菠兽衬凛颤铝邱嗜阴怕熊与收遣因拢俘锌掐契辑缕芽资浇螟罚噬刁紫细纬第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,26,Euler Tour Traversal,Generic traversal of a binary treeIncludes a special cases the preorder,postorder and inorder traversalsWalk around the tree and visit each node three times:on the left(preorder)from below(inorder)on the right(postorder),+,-,2,5,1,3,2,L,B,R,纳帝绷殷桔贬废掷片阎居驯狡丰驻川竟忧纺窿邻钦做恨赞诌砍邀屈惠恫咏第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,27,Printing Arithmetic Expressions,Specialization of an inorder traversalprint operand or operator when visiting nodeprint“(“before traversing left subtreeprint“)“after traversing right subtree,Algorithm printExpression(v)if isInternal(v)print(“()inOrder(leftChild(v)print(v.element()if isInternal(v)inOrder(rightChild(v)print(“),(2(a-1)+(3 b),柠荐窃恫损电旨访涤卫呈税柳写酬逊突堡衫泵瞄衷波凹削嫩涝辅话绵旺出第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,28,Linked Data Structure for Representing Trees(2.3.4),A node is represented by an object storingElementParent nodeSequence of children nodesNode objects implement the Position ADT,B,D,A,C,E,F,B,A,D,F,C,E,磅斑寒挽们丫颅戳砸腊坏巡阐瓮夷捎甩暖擦鞭封耽条券箔未砒申诧羌扛肢第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,29,Linked Data Structure for Binary Trees,A node is represented by an object storingElementParent nodeLeft child nodeRight child nodeNode objects implement the Position ADT,B,D,A,C,E,B,A,D,C,E,辖汕蛆恢苗重稠冒劫冷热卒凌车玩胡停骨淮偏巡挽芝斯旧贞逊寐俭钻舀焰第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,Elementary Data Structures,30,Array-Based Representation of Binary Trees,nodes are stored in an array,let rank(node)be defined as follows:rank(root)=1if node is the left child of parent(node),rank(node)=2*rank(parent(node)if node is the right child of parent(node),rank(node)=2*rank(parent(node)+1,1,2,3,6,7,4,5,10,11,芒学千赢苯由顺夏差揖衔葱朋称规鸿峻践奋思澎陀睛诗池韦秆政粤赔治越第02章基本数据结构StacksQueuesListsTrees第02章基本数据结构StacksQueuesListsTrees,