java线性表的存储结构及其代码实现
java数据结构学习笔记第一篇:
用程序后在那个的数据大致有四种基本的逻辑结构:
集合:数据元素之间只有"同属于一个集合"的关系
线性结构:数据元素之间存在一个对一个的关系
树形结构:数据元素之间存在一个对多个关系
图形结构或网状结构:数据元素之间存在多个对多个的关系
对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构
顺序存储结构
链式存储结构
本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图。
线性表的基本特征:
总存在唯一的第一个数据元素
总存在唯一的最后一个数据元素
除第一个数据元素外,集合中的每一个数据元素都只有一个前驱的数据元素
除最后一个数据元素外,集合中的每一个数据元素都只有一个后继的数据元素
1.线性表的顺序存储结构:是指用一组地址连续的存储单元一次存放线性表的元素。为了使用顺序结构实现线性表,程序通常会采用数组来保存线性中的元素,是一种随机存储的数据结构,适合随机访问。java中arraylist类是线性表的数组实现。
import java.util.arrays; public class sequencelist<t> { private int default_size = 16; //保存数组的长度。 private int capacity; //定义一个数组用于保存顺序线性表的元素 private object[] elementdata; //保存顺序表中元素的当前个数 private int size = 0; //以默认数组长度创建空顺序线性表 public sequencelist() { capacity = default_size; elementdata = new object[capacity]; } //以一个初始化元素来创建顺序线性表 public sequencelist(t element) { this(); elementdata[0] = element; size++; } /** * 以指定长度的数组来创建顺序线性表 * @param element 指定顺序线性表中第一个元素 * @param initsize 指定顺序线性表底层数组的长度 */ public sequencelist(t element , int initsize) { capacity = 1; //把capacity设为大于initsize的最小的2的n次方 while (capacity < initsize) { capacity <<= 1; } elementdata = new object[capacity]; elementdata[0] = element; size++; } //获取顺序线性表的大小 public int length() { return size; } //获取顺序线性表中索引为i处的元素 public t get(int i) { if (i < 0 || i > size - 1) { throw new indexoutofboundsexception("线性表索引越界"); } return (t)elementdata[i]; } //查找顺序线性表中指定元素的索引 public int locate(t element) { for (int i = 0 ; i < size ; i++) { if (elementdata[i].equals(element)) { return i; } } return -1; } //向顺序线性表的指定位置插入一个元素。 public void insert(t element , int index) { if (index < 0 || index > size) { throw new indexoutofboundsexception("线性表索引越界"); } ensurecapacity(size + 1); //将index处以后所有元素向后移动一格。 system.arraycopy(elementdata , index , elementdata , index + 1 , size - index); elementdata[index] = element; size++; } //在线性顺序表的开始处添加一个元素。 public void add(t element) { insert(element , size); } //很麻烦,而且性能很差 private void ensurecapacity(int mincapacity) { //如果数组的原有长度小于目前所需的长度 if (mincapacity > capacity) { //不断地将capacity * 2,直到capacity大于mincapacity为止 while (capacity < mincapacity) { capacity <<= 1; } elementdata = arrays.copyof(elementdata , capacity); } } //删除顺序线性表中指定索引处的元素 public t delete(int index) { if (index < 0 || index > size - 1) { throw new indexoutofboundsexception("线性表索引越界"); } t oldvalue = (t)elementdata[index]; int nummoved = size - index - 1; if (nummoved > 0) { system.arraycopy(elementdata , index+1 , elementdata, index , nummoved); } //清空最后一个元素 elementdata[--size] = null; return oldvalue; } //删除顺序线性表中最后一个元素 public t remove() { return delete(size - 1); } //判断顺序线性表是否为空表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //将底层数组所有元素赋为null arrays.fill(elementdata , null); size = 0; } public string tostring() { if (size == 0) { return "[]"; } else { stringbuilder sb = new stringbuilder("["); for (int i = 0 ; i < size ; i++ ) { sb.append(elementdata[i].tostring() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").tostring(); } } }
2.线性表链式存储结构:将采用一组地址的任意的存储单元存放线性表中的数据元素。
链表又可分为:
单链表:每个节点只保留一个引用,该引用指向当前节点的下一个节点,没有引用指向头结点,尾节点的next引用为null。
循环链表:一种首尾相连的链表。
双向链表:每个节点有两个引用,一个指向当前节点的上一个节点,另外一个指向当前节点的下一个节点。
下面给出线性表双向链表的实现:java中linkedlist是线性表的链式实现,是一个双向链表。
public class dulinklist<t> { //定义一个内部类node,node实例代表链表的节点。 private class node { //保存节点的数据 private t data; //指向上个节点的引用 private node prev; //指向下个节点的引用 private node next; //无参数的构造器 public node() { } //初始化全部属性的构造器 public node(t data , node prev , node next) { this.data = data; this.prev = prev; this.next = next; } } //保存该链表的头节点 private node header; //保存该链表的尾节点 private node tail; //保存该链表中已包含的节点数 private int size; //创建空链表 public dulinklist() { //空链表,header和tail都是null header = null; tail = null; } //以指定数据元素来创建链表,该链表只有一个元素 public dulinklist(t element) { header = new node(element , null , null); //只有一个节点,header、tail都指向该节点 tail = header; size++; } //返回链表的长度 public int length() { return size; } //获取链式线性表中索引为index处的元素 public t get(int index) { return getnodebyindex(index).data; } //根据索引index获取指定位置的节点 private node getnodebyindex(int index) { if (index < 0 || index > size - 1) { throw new indexoutofboundsexception("线性表索引越界"); } if (index <= size / 2) { //从header节点开始 node current = header; for (int i = 0 ; i <= size / 2 && current != null ; i++ , current = current.next) { if (i == index) { return current; } } } else { //从tail节点开始搜索 node current = tail; for (int i = size - 1 ; i > size / 2 && current != null ; i++ , current = current.prev) { if (i == index) { return current; } } } return null; } //查找链式线性表中指定元素的索引 public int locate(t element) { //从头节点开始搜索 node current = header; for (int i = 0 ; i < size && current != null ; i++ , current = current.next) { if (current.data.equals(element)) { return i; } } return -1; } //向线性链式表的指定位置插入一个元素。 public void insert(t element , int index) { if (index < 0 || index > size) { throw new indexoutofboundsexception("线性表索引越界"); } //如果还是空链表 if (header == null) { add(element); } else { //当index为0时,也就是在链表头处插入 if (index == 0) { addatheader(element); } else { //获取插入点的前一个节点 node prev = getnodebyindex(index - 1); //获取插入点的节点 node next = prev.next; //让新节点的next引用指向next节点,prev引用指向prev节点 node newnode = new node(element , prev , next); //让prev的next指向新节点。 prev.next = newnode; //让prev的下一个节点的prev指向新节点 next.prev = newnode; size++; } } } //采用尾插法为链表添加新节点。 public void add(t element) { //如果该链表还是空链表 if (header == null) { header = new node(element , null , null); //只有一个节点,header、tail都指向该节点 tail = header; } else { //创建新节点,新节点的pre指向原tail节点 node newnode = new node(element , tail , null); //让尾节点的next指向新增的节点 tail.next = newnode; //以新节点作为新的尾节点 tail = newnode; } size++; } //采用头插法为链表添加新节点。 public void addatheader(t element) { //创建新节点,让新节点的next指向原来的header //并以新节点作为新的header header = new node(element , null , header); //如果插入之前是空链表 if (tail == null) { tail = header; } size++; } //删除链式线性表中指定索引处的元素 public t delete(int index) { if (index < 0 || index > size - 1) { throw new indexoutofboundsexception("线性表索引越界"); } node del = null; //如果被删除的是header节点 if (index == 0) { del = header; header = header.next; //释放新的header节点的prev引用 header.prev = null; } else { //获取删除点的前一个节点 node prev = 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--; return del.data; } //删除链式线性表中最后一个元素 public t remove() { return delete(size - 1); } //判断链式线性表是否为空链表 public boolean empty() { return size == 0; } //清空线性表 public void clear() { //将底层数组所有元素赋为null header = null; tail = null; size = 0; } public string tostring() { //链表为空链表时 if (empty()) { return "[]"; } else { stringbuilder sb = new stringbuilder("["); for (node current = header ; current != null ; current = current.next ) { sb.append(current.data.tostring() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").tostring(); } } public string reversetostring() { //链表为空链表时 if (empty()) { return "[]"; } else { stringbuilder sb = new stringbuilder("["); for (node current = tail ; current != null ; current = current.prev ) { sb.append(current.data.tostring() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").tostring(); } } }
线性表的两种实现比较
空间性能:
顺序表:顺序表的存储空间是静态分布的,需要一个长度固定的数组,因此总有部分数组元素被浪费。
链表:链表的存储空间是动态分布的,因此不会空间浪费。但是由于链表需要而外的空间来为每个节点保存指针,因此要牺牲一部分空间。
时间性能:
顺序表:顺序表中元素的逻辑顺序与物理存储顺序是保持一致的,而且支持随机存取。因此顺序表在查找、读取时性能很好。
链表:链表采用链式结构来保存表内元素,因此在插入、删除元素时性能要好
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
上一篇: 推荐一篇利用th,colgroup,col定义表格样式
下一篇: 【项目介绍】搜索引擎