




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Chapter3List, Stacks, and Queue Introduce the concept of Abstract Data Types(ADTS). show how to efficiently perform operations on lists. Introduce the stack ADT and its use in implementingrecursion. Introduce the queue ADT and its use in operatingsystems and algorithm design.3.1 Abstract Data Types(
2、ADTS)1. ADT-a set of objects together with a set of operaions. Abstract data types are mathematical abstractions;nowhere in an ADTs definition is there any mention of how the set of operations is implemented.3.1 Abstract Data Types(ADTS)2. data object-a setof instances or values for example:Boolean=
3、false,trueDigit=0,1,2,3,4,5,6,7,8,9Letter=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.1 Abstract Data Types(ADTS)3. data structureis a data object together with the relationships among the instances and among the individual elements that compose an in
4、stance Data_Structure=D,R D-data object, R -a set of relationships of all the data members in D.3.2 The List ADTL = (e1, e2, e3, , en) list size is nif n=0:empty list if n(finite)0:e1 is the first elementen is the last element eiprecedesei+1Example:3.2 The List ADTStudents=(Jack, Jill, Abe, Henry, M
5、ary, , Judy) Exams =(exam1, exam2, exam3)Days of Week = (S, M, T, W, Th, F, Sa)Months = (Jan, Feb, Mar, Apr, , Nov, Dec)3.2The List ADTOperations:Create a linear listdetermine whether the list is empty determine the length of the list find the kth of the elementsearch for a given element delete the
6、kth elementinsert a new element just after the kth3.2The List ADTADT specification of a linear listAbstractDateType LinearListinstancesordered finite collections of zero or more elements operationsCreate();Destroy();IsEmpty();Length();Find(k,x);Search(x);Delete(k,x);Insert(k,x); Output(out);3.2.1. S
7、imple Array Implementation of Lists1. Use an array to represent the instance of an object(e1,e2,en)element012n-1MaxSize-1e1e2e3enlength=neach position of the array is called a cell or a node mapping formula:location(i)=i-1O(1)3.2.1.Simple Array Implementation of Lists Search( x)O(length)L = (a,b,d,b
8、,e)Search(d) = 3Search(a) = 1Search(z) = 0ACN=(1+2+n)/n=(1+n)*n/(2n)=(n+1)/23.2.1.Simple Array Implementation of Lists remove( k,x)deletethe kth element and return it in xL = (a,b,c,d,e) remove(2,x)=L=(a,c,d,e),x=b,and index of c,d,e decrease by 1 remove(0,x) = errorremove(20,x) = error3.2.1.Simple
9、Array Implementation of Listse1e2enn-1AMN=(n-i-1)/n=(n-1+n-2+1+0)/n=(n-1)/2i=0O( n)3.2.1.Simple Array Implementation of Lists insert (i,x )insert x after the ith elementL = (a,b,c,d,e,f,g) insert(0,h) =L = (h,a,b,c,d,e,f,g)index of a,b,c,d,e,f, and g increase by 1 insert(10,h) = errorinsert(-6,h) =
10、error3.2.1.Simple Array Implementation of Listse1e2en012n-1nnAMN=(n-i)/(n+1)=(n+n-1+1+0)/(n+1)=n/2i=0O( n)3.2.1. Simple Array Implementation of Lists2. Use array Implementation merit : easy Search.short coming :Insertion and Removing(Deletion) spend a lot of time.3.2.2. Linked ListsIn order to avoid
11、 the linear cost of insertion and deletion.1) Each node of a data object keeps a link or a pointer about the location of other relevant nodesL=(e1,e2,en)firste3e2e1ennullLink fieldData field3.2.2.Linked Lists The figure above is called a single linked list,and the structure is also called a chain A
12、chain is a linked list in which each node represents one element. There is a link or pointer from one element to the next. The last node has a null pointer.3.2.2.Linked Lists Deletiona elementof a chainDelete(1,x)firstnullabcdefirst = first.link;first3.2.2.Linked ListsDelete(3,x)ccbenulldcbabeforefi
13、rst get to node just before node to be removed before= first .link;3.2.2.Linked Listsnow change pointer in beforeenulldcabfirstpbeforebefore .link = before .link .link;3.2.2.Linked Lists insert operationinsert(0,f)firstl enuldcbafnewNodeStep 1: get a node, set its data and link fields ChainNode newN
14、ode =new ChainNode(f, first);first3.2.2. Linked ListsfenulldcbanewNodeStep 2: updatefirstfirst = newNode;newNodeenulldcbaffirstinsert(3,f)cbefore1. first find node whose index is 32. next create a node and set its data and link fields ChainNode newNode = new ChainNode(f,before .link);3. finally link
15、 before to newNode before .link = newNode;newNodeenulldcbaffirstTwo-Step insert(3,f)cbeforebefore = first .link .link; newNode .link = before .link; before .link = newNode;3.2.3 Programming Detailse1e21. Header (dummy node)headerenLLheader3.2.2.Linked Lists2. Class definitionListNode代表结点的类LinkedList
16、代表表本身的类LinkedListItr代表位置的类都是包DataStructures的一部分3.2.2.Linked Lists1) ListNode classelement nextpackage DataStructures; class ListNodeListNode( object theElement)this( theElement, null);ListNode( object theElement, ListNode n)element = theElement; next = n;object element; ListNode next;3.2.2.Linked Li
17、sts2) Iterator class for linked listscurrentLpackage DataStructures public class LinkedListItrLinkedListItr( ListNode theNode)current = theNode;public boolean isPastEnd( )return current = = null;public object retrieve( )return isPastEnd( ) ? Null : current.element;public void advance( )if( ! isPastE
18、nd( ) ) current = current.next;ListNode current;e2e1Len3) LinkedList classheaderpackage DataStructures; public class LinkedListpublic LinkedList( )header = new ListNode( null ) ; public boolean isEmpty( )return header.next = = null ; public void makeEmpty( )header.next = null; public LinkedListItr z
19、eroth( ) return new LinkedListItr( header ) ; public LinkedListItr first( ) return new LinkedListItr( header.next ) ; public LinkedListItr find( object x )public void remove( object x )public LinkedListItr findPrevious( object x ) public void insert( object x, LinkedListItr p )private ListNode heade
20、r;Method to print a listpublic static void printList( LinkedList theList )if ( theList.isEmpty( ) ) System.out.print( “Empty list” ) ;elseLinkedListItr itr = theList.first( );for( ; ! Itr.isPastEnd( ); itr. Advance( ) ) System.out.print( itr.retrieve( ) + “ “ ) ;System.out.println( );Operation: Cons
21、tructors isEmpty makeEmpty Zeroth and first return iterators corresponding to the header and first element. Find(x)publicLinkedListItrfind (object x)ListNode itr = header.next;while ( itr != null & !itr.element.equals( x ) ) itr = itr.next;return new LinkedListItr( itr );O(N) Remove( x )public void
22、remove( object x )LinkedListItr p = findprevious( x ); if( p.current.next != null )p.current.next = p.current.next.next;O(1) Findprevious ( x )publicLinkedListItr findPrevious( object x )ListNode itr = header;while( itr.next !=null & !itr.next.element.equals( x ) itr = itr.next;return new LinkedList
23、Itr( itr );O(N) Insert(x, p)publicvoid insert( object x, LinkedListItr p)if( p!=null & p.current != null )p.current.next = new ListNode( x, p.current.next );O(1)3.2.4.Doubly Linked ListsfirstNodelastNodeenulldcbanullleft rightelement3.2.4.Doubly Linked Lists operations:insertdelete3.2.4.Doubly Linke
24、d ListsDelete(1)firstNodelastNodeenulldcbnullanullpP=firstNode;firstNode=p .right;firstNode .left=null;3.2.4.Doubly Linked ListsDelete(3)firstNodelastNodeenulldcbanullpP .left .right=p .right;P .right .left=p .left;3.2.4.Doubly Linked Listsinsert(0,f)firstNodelastNodeenulldcbanullfnullnewNodefirstNo
25、de .left=newNode;newNode .left=null;newNode .right=firstNode;firstNode=newNode3.2.4.Doubly Linked ListsInsert(2,f)firstNodenewNodelastNodenullnullabcdebeforeNodenewNode .left=beforeNode;newNode .right=beforeNode .right; beforeNode .right .left=newNode;beforeNode .right=newNode;3.2.4. Doubly Linked C
26、ircular ListsfirstNodeeadcbDoubly Linked Circular List With Header NodeheaderNodeedcbaEmpty Doubly Linked Circular List With HeaderNodeheaderNode3.2.5. Circular Linked Listsaedcb3.2.5. Circular Linked ListsheaderabcdeheadNodeheaderheadNode例子:用循环链表求解约瑟夫(josephus)问题约瑟夫问题:实际上是一个游戏。书中以旅行社从n个旅客中选出一名旅客,为他
27、提供免费旅行服务。例,n=8, m=3(报数)从1号开始报数出列顺序为:3, 6, 1, 5, 2,8, 4。最后一个编号7的旅客将赢得旅游。81273654可由两种方法来解决:用数组来实现用循环链表来实现nnolinkn-121rearrear: 每次指向要出队列的前一个结点出队列的人也用链表来表示:head:指向出队列结点链表的开头结点p:指向出队列结点链表的尾结点以上rear, head, p都是ListNode的一个对象。1.w = m;2.for( int i = 1; i= n-1; i+)1) for (int j =1; j=w-1; j+)rear = rear.link;
28、2) if (i = = 1)head = rear.link ; p = head; elsep.link = rear.link; p = rear.link; 3) rear.link = p.link;3.P.link = rear; rear.link = null;实现该算法如果用数组来实现, 考虑一下如何做?3.2.6. Examples1. Polynomial ADTpn(x) = a0xe0+a1xe1+a2xe2+.+anxen Array implementationexample: p(x) = 3x4-5x3+8x2+2x-13-582-1coeffArrayp(x
29、) = 2x1000+8x50-23.2.6.Examples Linked list representations p1(x) = 10x1000+5x14+1 p2(x) = 3x1990-2x1492+11x+510001014510Lcoefexpp150L1111492-219903p2polynomialoperations: addition , multiplication, and so on.1) Array implementation of the polynomial ADT012MAX-DEGREEcoeffArrayhighPowerpublic class P
30、olynomialpublic Polynomial( ) zeroPolynomial( ); public void insertTerm( int coef, int exp ) public void zeroPolynomial( )public Polynomial add( Polynomial rhs )public Polynomial multiply( Polynomial rhs ) throws Overflowpublic void print( )public static final int MAX-DEGREE = 100;private int coeffA
31、rray = new int MAX-DEGREE + 1; private int highPower = 0;public void zeroPolynomial( )for( int i = 0; i=0; i-)sum.coeffArrayi = coeffArrayi + rhs.coeffArrayi ; return sum;-130500003202000400Example:0 1 2345 6 78 p1(x) = 3x8 5x3 + 3x 1p2(x) = 4x6 + 2x2 + 2Public Polynomial multiply( Polynomial rhs )
32、throws overflowPolynomial product = new Polynomial( ); product.highPower = highPower + rhs.highPower; if( product.highPower MAX-DEGREE )throw new overflow( );for( int i = 0; i= highPower; i+ )for( int j = 0; j= rhs.highPower; j+ )product.coeffArray i + j += coeffArrayi * rhs.coeffArrayj; return prod
33、uct;2) Class skeletons for linked list implemetation of the Polynomial ADT100010145L01coefexp1111492-219903p150Lp2public class Literal/Vavious constractors(not shown) int coefficient;int exponent;public class Polynomialpublic Polynomial( ) /* Exercise */ public void insertTerm( int coef, int exp ) /
34、* Exercise */ public void zeroPolynomial( ) /* Exercise */ public Polynomial add( Polynomial rhs ) /* Exercise */ public Polynomial multiply( Polynomial rhs ) /* Exercise */ public void print( ) /* Exercise */ private List terms; /* A List of Literals, sorted by exponent */多项式相加:*问题: A(X)=2X 100+3X1
35、4+2X8+1B(X)= -2X100+8X14-3X10+10X6-XA(X) + B(X) = 11X14 3X10 + 2X8 + 10X6 X + 1存放非零指数的系数与指数,因此每个结点有三个域组成。coefexplinkitem82143100210A:61010-3148100-2-11B:datalinkA(X)+B(X)=A(X)具体实现时,并不要再重新申请结点,完全利用原来两个链表的结点。方法:设4个引用变量:pa,pb,pc,p(c+需要) 1)初始化:pc , pa , pb ;pc永远指向相加时结果链表的最后一个结点。2) 当pa和pb都有项时a) 指数相等( pa.
36、 exp= =pb. exp )对应系数相加:pa. coef=pa. coef + pb. coef ; p= pb;pb前进 ; 删除p所指节点;if (系数相加结果为0)p=pa;pa前进; 删除p所指节点; else pc. link=pa; pc=pa; pa前进b) 指数不等pa. exp pb. exp/pa要插入结果链表pc. link=pa ; pc=pa ; pa前进3) 当两链表中有一链表为空,则将另一链表链入结果链表就可以if (pb空了) pc. link=pa;elsepc. link=pb;算法分析:设两个多项式的项数分别是m和n,则总的比较次数为O(m+n)最坏
37、情况下:两个多项式的指数项都不等且交叉递增,如A(x):a5x5+a3x3+a1x+a0m=4比较m+n-1次B(x):b4x4+b2x2+b0n=33.2.6.Cursor implementation of Linked Listsuse array to implement linked list:cursorSpaceelementnext12340123headerpelementnext0630250367815781010420178512345678P = p.nextp = cursorSpacep.nextp.datacuesorSpacep.data3.2.6.Curso
38、r implementation of Linked Lists1) Node and iterator for cursor implemetation of linked listsclass CursorNodeCursorNode( object theElement )this( theElement, 0 ); CursorNode( object theElement, int n )element = theElement; next = n;object element; int next;3.2.6.Cursor implementation of Linked Lists
39、public class CursorListItrCursorListItr( int theNode ) current = theNode; public boolean isPastEnd( ) return current = = 0; public object retrieve( ) return isPastEnd( ) ? null:CursorList.cursorSpace current .element;public void advance( )if( !isPastEnd( )current = CursorList.cursorSpace current .ne
40、xt;int current;3.2.6.Cursor implementation of Linked Lists2) Class skeleton for CursorList public class CursorListprivate static int alloc( ) private static void free( int p) public CursorList( ) header = alloc( );cursorSpace header .next = 0; public boolean isEmpty( ) return cursorSpace header .nex
41、t = = 0; public void makeEmpty( )public CursorListItr zeroth( )return new CursorListItr( header ); public CursorListItr first( )return new CursorListItr( cursorSpace header .next ); public CursorListItr find( object x )public void insert( object x, CursorListItr p) public void remove( object x )publ
42、ic CursorListItr findPrevious( object x )private int header;static CursorNode cursorSpace;private static final int SPACE-SIZE = 100; staticcursorSpace = new CursorNode SPACE-SIZE ;for( int i = 0; iSPACE-SIZE; i+)cursorSpace i = new CursorNode( null, i + 1 ); cursorSpace SPACE-SIZE-1.next = 0;3.2.6.C
43、ursor implementation of Linked ListsSome Routines: Alloc and freeprivate static int alloc( )/用于分配出去一个当前空闲的数组单元(节点)int p = cursorSpace 0 .next; cursorSpace0.next = cursorSpacep.next; if( p = = 0 )throw new OutOfMemoryError( ); return p;private static void free( int p )/用于回收一个不再使用的数组单元(节点)cursorSpacep
44、.element = null; cursorSpacep.next = cursorSpace0.next; cursorSpace0.next = p;3.2.6.Cursor implementation of Linked Lists Find routine-cursor implementation public CursorListItr find( object x )int itr = cursorSpace header .next;while( itr !=0 & !cursorSpace itr .element.equals( x ) ) itr = cursorSp
45、ace itr .next;return new CursorListItr( itr );3.2.6.Cursor implementation of Linked Lists Insertion routine for linked lists-cursor implementation public void insert( object x, CursorListItr p )if( p != null & p.current != 0)int pos = p.current; int tmp = alloc( );cursorSpace tmp .element = x;cursorSpace tmp .next = cursorSpace pos .next; curso
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 农业文化遗产可视化知识图谱构建
- 煤气化渣二氧化硅对聚丙烯除味性能的研究与应用
- 公园生活垃圾管理办法
- 十年职场经验分享与职业规划
- 江西涉密采购管理办法
- 通信工程技术规范
- 积极心理学应用:心理健康教育长效机制构建
- 利率市场化改革对中小企业融资效率的影响机制研究
- 基于乘客决策行为的城市轨道交通系统韧性评估研究
- 2025年 重大安全事故
- 中职《接触器联锁正反转控制线路》公开课PPT
- 05-衣之镖-辅行诀汤液经法用药图释义
- LS/T 3240-2012汤圆用水磨白糯米粉
- GB/T 15298-1994电子设备用电位器第一部分:总规范
- 新教科版六下科学4-6《生命体中的化学变化》教案
- 2023高中学业水平合格性考试历史重点知识点归纳总结(复习必背)
- 自然指数NatureIndex(NI)收录的68种自然科学类期刊
- 手术报告审批单
- 《专业导论光电信息科学与工程》教学大纲
- 广东省湛江市各县区乡镇行政村村庄村名明细
- 少儿美术国画- 少儿希望 《紫藤课件》
评论
0/150
提交评论