蔡明志数据结构java 版第 4章.ppt

《蔡明志数据结构java 版第 4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章链表4.1单向链表4.2循环链表4.3双向链表4.4链表的应用4.5程序集锦4.6思考题14.1单向链表假设链表中每个结点（node）的数据结构有两栏，分别是数据（data）栏和链接（next）栏，，若将结点结构定义为Node_type数据类型，则表示如下：classNode_type{intdata;Node_typenext;};24.1单向链表4.1.1插入结点操作4.1.2删除结点操作4.1.3将两链表相连4.1.4将链表反转4.1.5计算链表长度34.1.1插入结点操作假设有一链表如图所示。插入在链表的前端有一结点x将插入到链表的前端，其步骤如下：（1）x=new

2、Node_type();（2）x.next=head.next;（3）head.next=x;44.1.1插入结点操作插入到链表的尾端有一结点x将插入到链表的尾端，其步骤如下：（1）x=newNode_type();（2）x.next=null;（3）执行下列语句current=head.next;while(current.next!=null)current=current.next;current.next=x;54.1.1插入结点操作随机插入某一结点假设有一单向的链表是依键值由大至小建立的，则一结点的程序如下：prev=head;current=head.next;whi

3、le((current!=null)&&(current.score>=ptr.score)){64.1.1插入结点操作prev=current;current=current.next;}ptr.next=current;prev.next=ptr;74.1.2删除结点操作假设有一链表如图所示。删除链表前端的结点只要3个步骤便可实现：（1）current=head.next;（2）head.next=current.next;（3）current=null;84.1.2删除结点操作删除链表尾端的结点（1）此时必须先找到链表的尾端结点，程序如下：current=head.next

4、;while(current.next!=null)//找出尾端结点{prev=current;current=current.next;}（2）prev.next=null;（3）current=null;94.1.2删除结点操作随机删除某一结点随机删除单向链表某一结点的程序如下：prev=head;current=head.next;while((current!=null)&&(!(del_name.equals(current.name)))){prev=current;current=current.next;}104.1.2删除结点操作if(current!=null

5、){prev.next=current.next;current=null;System.out.print("Student"+del_name+"recorddeleted");}elseSystem.out.print("Student"+del_name+"notfound");114.1.3将两链表相连链表相连的程序如下：publicvoidconcatenate(){if(x==null)z=y;elseif(y==null)z=x;124.1.3将两链表相连else{z=x;xtail=x.next;while(xtail.next!=null)xtail=

6、xtail.next;xtail.next=y.next;y=null;}}134.1.4将链表反转链表的反转（invert）顾名思义就是将链表的前端变为尾端，尾端变为前端。链表反转和程序如下：publicvoidinvert(){forward=head.next;current=null;while(forward!=null){144.1.4将链表反转prev=current;current=forward;forward=forward.next;current.next=prev;}tail=head;head=current;}154.1.5计算链表长度计算链表长度的

7、程序如下：publicintlength(){intleng=0;p=head.next;while(p!=null){leng++;p=p.next;}returnleng;}16练习题1.有一链表若只有head指针，并没有tail指针，试编写删除此链表的最后结点的程序。2.试说明下列两段程序最后current指针的指向位置。（1）structnode*current;current=head;while(current!=NULL)current=current→next;（