含头结点的单链表

1、 实习报告“含头结点的单链表”演示程序 （1） 、程序的功能和特点主要实现的功能有：1.查找给定关键字的结点； 2.在单链表第l个结点位置插入一个新结点； 3.删除第l个结点； 4.显示全部链表； 5.求链表的长度；（二）、程序的算法设计 “比较”算法：1. 【逻辑结构与存储结构设计】逻辑结构：每个元素之间是相邻的；存储结构：元素存储于任意的存储单元中，可以是连续的，也可以是不 连续的；2.【基本操作设计】元素存储域任意的存储单元中，这时需要在存储元素本身信息的同时，还要存储下一个元素的位置。由此构成一个链状结构，成为链表。将表示数据元素和下一个元素位置的结构，如下所示：数据元素 指针域称为链

2、表的结点指针域用来存放下一个元素的地址，这样就可以保证表的连续性3. 【算法设计】指向第一个结点查找给定关键字的结点 否不是当前所查找的结点并且没有到链尾null否是指针域！=null移动指针，使其指向下一个元素是返回结点在单链表第l个结点位置插入一个新结点第l个结点，新结点id 建立新结点指针p后移l个结点把p之后链表接到新结点的后面把新结点接在p所指结点的后面删除第l个结点是判断链表是否为空否null使指针p指向所要删结点的前驱指向要删结点指向要删结点的后驱4. 【高级语言代码】 查找给定关键字的结点，返回结点linknodenode p=first; /指向第一结点/不是当前结点并且没有

3、到链尾while(p.idata!=id&&p.next!=null)p=p.next;if(p.next!=null) return p;else return null; 在单链表第l个结点位置插入一个新结点linknodenode newlinknodenode= new linknodenode(id,fd); /诞生新结点newlinknodenodeint i=1;linknodenode p=first; /指向第一结点/p指针后移l个结点while(p.next!=null && i+<l) p=p.next;newlinknodenode

4、.next=p.next; /把p之后的链表接在新结点的后面p.next=newlinknodenode; /把新结点接在p所指结点的后面return true;删除第l个结点if(isempty() return null;linknodenode p=first; /指向第一个结点int i=1;while(p.next!=null && i+<l)p=p.next; /指向要删结点的前驱linknodenode q=p.next; /指向要删结点p.next=q.next; /p指向要删结点的后继return q; /返回已删结点（三）、程序中类的设计 “linkn

5、odelist”类：1. 【逻辑结构与存储结构】逻辑结构：每个元素之间是相邻的；存储结构：元素存储于任意的存储单元中，可以是连续的，也可以是不 连续的；2. 【主要成员变量说明】 public linknode first; /单链表的头指针【主要成员方法说明】 查找给定关键字的结点，返回结点 public linknode linknodefind(int id) 在单链表第l个结点位置插入一个新结点public boolean insertwhere(int l,int id) 删除第l个结点public linknode deletewhere(int l)显示全部链表public vo

6、id listdisplay()返回链表长度（结点数）public int listlength()4. 【高级语言代码】 链表的结点类class linknodepublic int idata; /数据域（结点关键字）public linknode next; /指针域（指向下一结点）public linknode() /头结点构造方法idata=-1;/数据域赋值/指针域自动初始化为nullpublic linknode(int id) /结点构造方法idata=id; /数据域赋值public void linknodedisplay() /显示自身的数据域system.out.pri

7、ntln(""+idata+""); 单链表类class linknodelist public linknode first; /单链表的头指针public linknodelist () /构造方法first=new linknode(); /空单链表，头指针指向头结点public boolean isempty() /单链表是否为空return (first.next=null); /头结点的指针为空/查找给定关键字的结点，返回结点public linknode linknodefind(int id) linknode p=first; /指向第

8、一结点/不是当前结点并且没有到链尾while(p.idata!=id&&p.next!=null)p=p.next;if(p.next!=null) return p;else return null; /在单链表第l个结点位置插入一个新结点public boolean insertwhere(int l,int id) linknode newlinknode= new linknode(id); /诞生新结点newlinknodeint i=1;linknode p=first; /指向第一结点/p指针后移l个结点while(p.next!=null &&

9、i+<l) p=p.next;newlinknode.next=p.next; /把p之后的链表接在新结点的后面p.next=newlinknode; /把新结点接在p所指结点的后面return true;/删除第l个结点public linknode deletewhere(int l) if(isempty() return null;linknode p=first; /指向第一个结点int i=1;while(p.next!=null && i+<l)p=p.next; /指向要删结点的前驱linknode q=p.next; /指向要删结点p.next=q

10、.next; /p指向要删结点的后继return q; /返回已删结点/显示全部链表public void listdisplay() linknode p=first.next; /指向第一个结点system.out.println("显示链表：从前到后");while(p!=null) p.linknodedisplay(); /显示结点p=p.next;system.out.println("*");/返回链表长度（结点数）public int listlength() linknode p=first.next; /指向头结点int i=0;wh

11、ile(p!=null)p=p.next;i+;return i;/置链表为空表public void makeempty() first.next=null; public static void main(string args) linknodelist s1=new linknodelist(); /空链表诞生s1.insertwhere(1,12); /从指定位置插入结点s1.insertwhere(2,34);s1.insertwhere(3,53);s1.insertwhere(4,32);s1.insertwhere(3,76);s1.listdisplay();s1.deletewhere(4); /删除第4个结点s1.listdi