用Java实现一个静态链表的方法步骤
什么是静态链表?
对于线性链表,也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。
用数组描述的链表,即称为静态链表。
在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标CUR。
静态链表的节点
数据域:用于存储数据元素的值
游标:即数组下标,表示直接后继元素所在数组中的位置
publicclassStaticLinkedListNode{ publicTdata;//数据 publicintcursor;//游标 ... }
注:通常静态链表会将第一个数据元素放到数组下标为1(即a[1])的位置中。
备用链表
静态链表中,除了数据本身通过游标组成链表外,还需要有一条连接各个空闲位置的链表,称为备用链表。
作用:回收数组中未使用或者之前使用过(现在不用)的存储空间,留待后期使用。即静态链表使用数组申请的物理空间中,存在两个链表,一条连接数据,另一条连接数组中为使用的空间。
注:通常备用链表的表头位于数组下标为0(a[0])的位置,而数据链表的表头位于数组下标为1(a[1])的位置。
静态链表中设置备用链表的好处是,可以清楚地知道数组中是否有空闲位置,以便数据链表添加新数据时使用。比如,若静态链表中数组下标为0的位置上存有数据,则证明数组已满。
完整代码
publicclassStaticLinkedListNode{ publicTdata; privateintcursor; publicStaticLinkedListNode(Tdata,intcursor){ this.cursor=cursor; } publicTgetData(){ returndata; } publicvoidsetData(Tdata){ this.data=data; } publicintgetCursor(){ returncursor; } publicvoidsetCursor(intcursor){ this.cursor=cursor; } }
publicclassStaticLinkedList{ StaticLinkedListNode[]nodes; privatestaticfinalintMAX_SIZE=100; privateintlength; publicStaticLinkedList(){ nodes=newStaticLinkedListNode[MAX_SIZE]; for(inti=0;i (null,i+1); } nodes[MAX_SIZE-1].setCursor(0); this.length=0; } //链表实际长度 publicintLength(){ returnlength; } //判断使用数组是否为空 publicbooleanisEmpty(){ returnlength==0; } //判断备用链表是否为空 publicbooleanisFull(){ returnlength==MAX_SIZE; } //插入一个节点 publicbooleanaddTo(Tdata,intindex){ if(isFull()||index>MAX_SIZE||index<-1||data==null) returnfalse; if(index==0){ insert(data); returntrue; } if(index>Length()){ index=Length(); } //获取第一个使用节点的下标 intfirstUse=nodes[MAX_SIZE-1].getCursor(); //获取备用数组第一个节点的下标 intfirstNull=nodes[0].getCursor(); for(inti=1;i list=newStaticLinkedList (); list.insert("A"); list.insert("B"); list.insert("C"); list.insert("D"); list.insert("E"); list.addTo("X",2); System.out.println(list.Length()); list.print(); //list.printAll(); //list.deleteAll(); } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。