图的创建、遍历及应用

《图的创建、遍历及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、结点类packagech06;publicclassNode{privateObjectdata;//存放结点值privateNodenext;//后继结点的引用//无参数时的构造函数publicNode(){this(null,null);}//带一个参数时的构造函数publicNode(Objectdata){//构造值为data的结点this(data,null);}//带两个参数时的构造函数publicNode(Objectdata,Nodenext){this.data=data;this.next=next;}publicObjectgetData(){return

2、data;}publicvoidsetData(Objectdata){this.data=data;}publicNodegetNext(){returnnext;}publicvoidsetNext(Nodenext){this.next=next;}}栈的抽象接口类packagech06;publicinterfaceIStack{publicvoidclear();publicbooleanisEmpty();publicintlength();publicObjectpeek();publicvoidpush(Objectx)throwsException;publi

3、cObjectpop();}链栈类packagech06;importch06.Node;publicclassLinkStackimplementsIStack{privateNodetop;//栈顶元素的应用//将栈置空publicvoidclear(){top=null;}//判断栈是否为空publicbooleanisEmpty(){returntop==null;}//求链栈的长度publicintlength(){Nodep=top;//初始化，p指向栈顶元素，length为计数器intlength=0;while(p!=null){//从栈顶元素开始向后查找，直到

4、p指向空p=p.getNext();//p指向后继结点++length;//长度增加1}returnlength;}//取栈顶元素并返回其值publicObjectpeek(){if(!isEmpty())//栈非空returntop.getData();//返回栈顶元素的值elsereturnnull;}//入栈publicvoidpush(Objectx){Nodep=newNode(x);//构造一个新结点p.setNext(top);top=p;//新结点成为当前的首结点}//出栈publicObjectpop(){if(isEmpty()){returnnull;}e

5、lse{Nodep=top;//p指向被删除的结点（栈顶结点）top=top.getNext();//修改链指针，使栈顶结点从链栈中移去returnp.getData();//返回栈顶结点的数据域的值}}//输出栈中所有数据元素（从栈顶元素到栈底元素）publicvoiddisplay(){Nodep=top;//初始化，p指向栈顶元素while(p!=null){//输出所有非空结点的数据元素值System.out.print((p.getData().toString()+""));p=p.getNext();//p指针向后移}}}队列的抽象接口类packagech06;p

6、ublicinterfaceIQueue{publicvoidclear();publicbooleanisEmpty();publicintlength();publicObjectpeek();publicvoidoffer(Objectx)throwsException;publicObjectpoll();}链队列类packagech06;importch06.Node;publicclassLinkQueueimplementsIQueue{privateNodefront;//队首指针privateNoderear;//队尾指针//链队列类的构造函数publicLi

7、nkQueue(){front=rear=null;}//队列置空publicvoidclear(){front=rear=null;}//队列判空publicbooleanisEmpty(){returnfront==null;}//求队列的长度publicintlength(){if(!isEmpty()){//队列非空Nodep=front;intlength=0;while(p!=null){p=p.getNext();//指针下移++length;//计数器+1}}returnle