java线性表的存储结构及其代码实现
Java数据结构学习笔记第一篇:
用程序后在那个的数据大致有四种基本的逻辑结构:
集合:数据元素之间只有"同属于一个集合"的关系
线性结构:数据元素之间存在一个对一个的关系
树形结构:数据元素之间存在一个对多个关系
图形结构或网状结构:数据元素之间存在多个对多个的关系
对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构
顺序存储结构
链式存储结构
本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图。
线性表的基本特征:
总存在唯一的第一个数据元素
总存在唯一的最后一个数据元素
除第一个数据元素外,集合中的每一个数据元素都只有一个前驱的数据元素
除最后一个数据元素外,集合中的每一个数据元素都只有一个后继的数据元素
1.线性表的顺序存储结构:是指用一组地址连续的存储单元一次存放线性表的元素。为了使用顺序结构实现线性表,程序通常会采用数组来保存线性中的元素,是一种随机存储的数据结构,适合随机访问。java中ArrayList类是线性表的数组实现。
importjava.util.Arrays; publicclassSequenceList{ privateintDEFAULT_SIZE=16; //保存数组的长度。 privateintcapacity; //定义一个数组用于保存顺序线性表的元素 privateObject[]elementData; //保存顺序表中元素的当前个数 privateintsize=0; //以默认数组长度创建空顺序线性表 publicSequenceList() { capacity=DEFAULT_SIZE; elementData=newObject[capacity]; } //以一个初始化元素来创建顺序线性表 publicSequenceList(Telement) { this(); elementData[0]=element; size++; } /** *以指定长度的数组来创建顺序线性表 *@paramelement指定顺序线性表中第一个元素 *@paraminitSize指定顺序线性表底层数组的长度 */ publicSequenceList(Telement,intinitSize) { capacity=1; //把capacity设为大于initSize的最小的2的n次方 while(capacity size-1) { thrownewIndexOutOfBoundsException("线性表索引越界"); } return(T)elementData[i]; } //查找顺序线性表中指定元素的索引 publicintlocate(Telement) { for(inti=0;i size) { thrownewIndexOutOfBoundsException("线性表索引越界"); } ensureCapacity(size+1); //将index处以后所有元素向后移动一格。 System.arraycopy(elementData,index,elementData ,index+1,size-index); elementData[index]=element; size++; } //在线性顺序表的开始处添加一个元素。 publicvoidadd(Telement) { insert(element,size); } //很麻烦,而且性能很差 privatevoidensureCapacity(intminCapacity) { //如果数组的原有长度小于目前所需的长度 if(minCapacity>capacity) { //不断地将capacity*2,直到capacity大于minCapacity为止 while(capacity size-1) { thrownewIndexOutOfBoundsException("线性表索引越界"); } ToldValue=(T)elementData[index]; intnumMoved=size-index-1; if(numMoved>0) { System.arraycopy(elementData,index+1 ,elementData,index,numMoved); } //清空最后一个元素 elementData[--size]=null; returnoldValue; } //删除顺序线性表中最后一个元素 publicTremove() { returndelete(size-1); } //判断顺序线性表是否为空表 publicbooleanempty() { returnsize==0; } //清空线性表 publicvoidclear() { //将底层数组所有元素赋为null Arrays.fill(elementData,null); size=0; } publicStringtoString() { if(size==0) { return"[]"; } else { StringBuildersb=newStringBuilder("["); for(inti=0;i 2.线性表链式存储结构:将采用一组地址的任意的存储单元存放线性表中的数据元素。
链表又可分为:单链表:每个节点只保留一个引用,该引用指向当前节点的下一个节点,没有引用指向头结点,尾节点的next引用为null。
循环链表:一种首尾相连的链表。
双向链表:每个节点有两个引用,一个指向当前节点的上一个节点,另外一个指向当前节点的下一个节点。下面给出线性表双向链表的实现:java中LinkedList是线性表的链式实现,是一个双向链表。
publicclassDuLinkList{ //定义一个内部类Node,Node实例代表链表的节点。 privateclassNode { //保存节点的数据 privateTdata; //指向上个节点的引用 privateNodeprev; //指向下个节点的引用 privateNodenext; //无参数的构造器 publicNode() { } //初始化全部属性的构造器 publicNode(Tdata,Nodeprev,Nodenext) { this.data=data; this.prev=prev; this.next=next; } } //保存该链表的头节点 privateNodeheader; //保存该链表的尾节点 privateNodetail; //保存该链表中已包含的节点数 privateintsize; //创建空链表 publicDuLinkList() { //空链表,header和tail都是null header=null; tail=null; } //以指定数据元素来创建链表,该链表只有一个元素 publicDuLinkList(Telement) { header=newNode(element,null,null); //只有一个节点,header、tail都指向该节点 tail=header; size++; } //返回链表的长度 publicintlength() { returnsize; } //获取链式线性表中索引为index处的元素 publicTget(intindex) { returngetNodeByIndex(index).data; } //根据索引index获取指定位置的节点 privateNodegetNodeByIndex(intindex) { if(index<0||index>size-1) { thrownewIndexOutOfBoundsException("线性表索引越界"); } if(index<=size/2) { //从header节点开始 Nodecurrent=header; for(inti=0;i<=size/2&¤t!=null ;i++,current=current.next) { if(i==index) { returncurrent; } } } else { //从tail节点开始搜索 Nodecurrent=tail; for(inti=size-1;i>size/2&¤t!=null ;i++,current=current.prev) { if(i==index) { returncurrent; } } } returnnull; } //查找链式线性表中指定元素的索引 publicintlocate(Telement) { //从头节点开始搜索 Nodecurrent=header; for(inti=0;i size) { thrownewIndexOutOfBoundsException("线性表索引越界"); } //如果还是空链表 if(header==null) { add(element); } else { //当index为0时,也就是在链表头处插入 if(index==0) { addAtHeader(element); } else { //获取插入点的前一个节点 Nodeprev=getNodeByIndex(index-1); //获取插入点的节点 Nodenext=prev.next; //让新节点的next引用指向next节点,prev引用指向prev节点 NodenewNode=newNode(element,prev,next); //让prev的next指向新节点。 prev.next=newNode; //让prev的下一个节点的prev指向新节点 next.prev=newNode; size++; } } } //采用尾插法为链表添加新节点。 publicvoidadd(Telement) { //如果该链表还是空链表 if(header==null) { header=newNode(element,null,null); //只有一个节点,header、tail都指向该节点 tail=header; } else { //创建新节点,新节点的pre指向原tail节点 NodenewNode=newNode(element,tail,null); //让尾节点的next指向新增的节点 tail.next=newNode; //以新节点作为新的尾节点 tail=newNode; } size++; } //采用头插法为链表添加新节点。 publicvoidaddAtHeader(Telement) { //创建新节点,让新节点的next指向原来的header //并以新节点作为新的header header=newNode(element,null,header); //如果插入之前是空链表 if(tail==null) { tail=header; } size++; } //删除链式线性表中指定索引处的元素 publicTdelete(intindex) { if(index<0||index>size-1) { thrownewIndexOutOfBoundsException("线性表索引越界"); } Nodedel=null; //如果被删除的是header节点 if(index==0) { del=header; header=header.next; //释放新的header节点的prev引用 header.prev=null; } else { //获取删除点的前一个节点 Nodeprev=getNodeByIndex(index-1); //获取将要被删除的节点 del=prev.next; //让被删除节点的next指向被删除节点的下一个节点。 prev.next=del.next; //让被删除节点的下一个节点的prev指向prev节点。 if(del.next!=null) { del.next.prev=prev; } //将被删除节点的prev、next引用赋为null. del.prev=null; del.next=null; } size--; returndel.data; } //删除链式线性表中最后一个元素 publicTremove() { returndelete(size-1); } //判断链式线性表是否为空链表 publicbooleanempty() { returnsize==0; } //清空线性表 publicvoidclear() { //将底层数组所有元素赋为null header=null; tail=null; size=0; } publicStringtoString() { //链表为空链表时 if(empty()) { return"[]"; } else { StringBuildersb=newStringBuilder("["); for(Nodecurrent=header;current!=null ;current=current.next) { sb.append(current.data.toString()+","); } intlen=sb.length(); returnsb.delete(len-2,len).append("]").toString(); } } publicStringreverseToString() { //链表为空链表时 if(empty()) { return"[]"; } else { StringBuildersb=newStringBuilder("["); for(Nodecurrent=tail;current!=null ;current=current.prev) { sb.append(current.data.toString()+","); } intlen=sb.length(); returnsb.delete(len-2,len).append("]").toString(); } } } 线性表的两种实现比较
空间性能:
顺序表:顺序表的存储空间是静态分布的,需要一个长度固定的数组,因此总有部分数组元素被浪费。
链表:链表的存储空间是动态分布的,因此不会空间浪费。但是由于链表需要而外的空间来为每个节点保存指针,因此要牺牲一部分空间。
时间性能:
顺序表:顺序表中元素的逻辑顺序与物理存储顺序是保持一致的,而且支持随机存取。因此顺序表在查找、读取时性能很好。
链表:链表采用链式结构来保存表内元素,因此在插入、删除元素时性能要好
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。