欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

java線性表的存儲結(jié)構(gòu)及其代碼實(shí)現(xiàn)

 更新時間:2020年10月29日 13:12:47   作者:Angel_Kitty  
這篇文章主要為大家詳細(xì)介紹了Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記第一篇,線性表的存儲結(jié)構(gòu)及其代碼實(shí)現(xiàn),具有一定的參考價值,感興趣的小伙伴們可以參考一下

Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記第一篇:

用程序后在那個的數(shù)據(jù)大致有四種基本的邏輯結(jié)構(gòu):

集合:數(shù)據(jù)元素之間只有"同屬于一個集合"的關(guān)系
線性結(jié)構(gòu):數(shù)據(jù)元素之間存在一個對一個的關(guān)系
樹形結(jié)構(gòu):數(shù)據(jù)元素之間存在一個對多個關(guān)系
圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu):數(shù)據(jù)元素之間存在多個對多個的關(guān)系

對于數(shù)據(jù)不同的邏輯結(jié)構(gòu),計(jì)算機(jī)在物理磁盤上通常有兩種屋里存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)
鏈?zhǔn)酱鎯Y(jié)構(gòu)

本篇博文主要講的是線性結(jié)構(gòu),而線性結(jié)構(gòu)主要是線性表,非線性結(jié)構(gòu)主要是樹和圖。

線性表的基本特征:

總存在唯一的第一個數(shù)據(jù)元素
總存在唯一的最后一個數(shù)據(jù)元素
除第一個數(shù)據(jù)元素外,集合中的每一個數(shù)據(jù)元素都只有一個前驅(qū)的數(shù)據(jù)元素
除最后一個數(shù)據(jù)元素外,集合中的每一個數(shù)據(jù)元素都只有一個后繼的數(shù)據(jù)元素

1.線性表的順序存儲結(jié)構(gòu):是指用一組地址連續(xù)的存儲單元一次存放線性表的元素。為了使用順序結(jié)構(gòu)實(shí)現(xiàn)線性表,程序通常會采用數(shù)組來保存線性中的元素,是一種隨機(jī)存儲的數(shù)據(jù)結(jié)構(gòu),適合隨機(jī)訪問。java中ArrayList類是線性表的數(shù)組實(shí)現(xiàn)。

import java.util.Arrays;
public class SequenceList<T>
{
 private int DEFAULT_SIZE = 16;
 //保存數(shù)組的長度。
 private int capacity;
 //定義一個數(shù)組用于保存順序線性表的元素
 private Object[] elementData;
 //保存順序表中元素的當(dāng)前個數(shù)
 private int size = 0;
 //以默認(rèn)數(shù)組長度創(chuàng)建空順序線性表
 public SequenceList()
 {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 //以一個初始化元素來創(chuàng)建順序線性表
 public SequenceList(T element)
 {
  this();
  elementData[0] = element;
  size++;
 }
 /**
  * 以指定長度的數(shù)組來創(chuàng)建順序線性表
  * @param element 指定順序線性表中第一個元素
  * @param initSize 指定順序線性表底層數(shù)組的長度
  */
 public SequenceList(T element , int initSize)
 {
  capacity = 1;
  //把capacity設(shè)為大于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)
 {
  //如果數(shù)組的原有長度小于目前所需的長度
  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()
 {
  //將底層數(shù)組所有元素賦為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.線性表鏈?zhǔn)酱鎯Y(jié)構(gòu):將采用一組地址的任意的存儲單元存放線性表中的數(shù)據(jù)元素。
鏈表又可分為:

單鏈表:每個節(jié)點(diǎn)只保留一個引用,該引用指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn),沒有引用指向頭結(jié)點(diǎn),尾節(jié)點(diǎn)的next引用為null。
循環(huán)鏈表:一種首尾相連的鏈表。
雙向鏈表:每個節(jié)點(diǎn)有兩個引用,一個指向當(dāng)前節(jié)點(diǎn)的上一個節(jié)點(diǎn),另外一個指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)。

下面給出線性表雙向鏈表的實(shí)現(xiàn):java中LinkedList是線性表的鏈?zhǔn)綄?shí)現(xiàn),是一個雙向鏈表。

public class DuLinkList<T>
{
 //定義一個內(nèi)部類Node,Node實(shí)例代表鏈表的節(jié)點(diǎn)。
 private class Node
 {
  //保存節(jié)點(diǎn)的數(shù)據(jù)
  private T data;
  //指向上個節(jié)點(diǎn)的引用
  private Node prev;
  //指向下個節(jié)點(diǎn)的引用
  private Node next;
  //無參數(shù)的構(gòu)造器
  public Node()
  {
  }
  //初始化全部屬性的構(gòu)造器
  public Node(T data , Node prev , Node next)
  {
   this.data = data;
   this.prev = prev;
   this.next = next;
  }
 }
 //保存該鏈表的頭節(jié)點(diǎn)
 private Node header;
 //保存該鏈表的尾節(jié)點(diǎn)
 private Node tail;
 //保存該鏈表中已包含的節(jié)點(diǎn)數(shù)
 private int size;
 //創(chuàng)建空鏈表
 public DuLinkList()
 {
  //空鏈表,header和tail都是null
  header = null;
  tail = null;
 }
 //以指定數(shù)據(jù)元素來創(chuàng)建鏈表,該鏈表只有一個元素
 public DuLinkList(T element)
 {
  header = new Node(element , null , null);
  //只有一個節(jié)點(diǎn),header、tail都指向該節(jié)點(diǎn)
  tail = header;
  size++;
 }
 //返回鏈表的長度 
 public int length()
 {
  return size;
 }

 //獲取鏈?zhǔn)骄€性表中索引為index處的元素
 public T get(int index)
 {
  return getNodeByIndex(index).data;
 }
 //根據(jù)索引index獲取指定位置的節(jié)點(diǎn)
 private Node getNodeByIndex(int index)
 {
  if (index < 0 || index > size - 1)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  if (index <= size / 2)
  {
   //從header節(jié)點(diǎn)開始
   Node current = header;
   for (int i = 0 ; i <= size / 2 && current != null
    ; i++ , current = current.next)
   {
    if (i == index)
    {
     return current;
    }
   }
  }
  else
  {
   //從tail節(jié)點(diǎn)開始搜索
   Node current = tail;
   for (int i = size - 1 ; i > size / 2 && current != null
    ; i++ , current = current.prev)
   {
    if (i == index)
    {
     return current;
    }
   }
  }
  return null;
 }
 //查找鏈?zhǔn)骄€性表中指定元素的索引
 public int locate(T element)
 {
  //從頭節(jié)點(diǎn)開始搜索
  Node current = header;
  for (int i = 0 ; i < size && current != null
   ; i++ , current = current.next)
  {
   if (current.data.equals(element))
   {
    return i;
   }
  }
  return -1;
 }
 //向線性鏈?zhǔn)奖淼闹付ㄎ恢貌迦胍粋€元素。
 public void insert(T element , int index)
 {
  if (index < 0 || index > size)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  //如果還是空鏈表
  if (header == null)
  {
   add(element);
  }
  else
  {
   //當(dāng)index為0時,也就是在鏈表頭處插入
   if (index == 0)
   {
    addAtHeader(element);
   }
   else
   {
    //獲取插入點(diǎn)的前一個節(jié)點(diǎn)
    Node prev = getNodeByIndex(index - 1);
    //獲取插入點(diǎn)的節(jié)點(diǎn)
    Node next = prev.next;
    //讓新節(jié)點(diǎn)的next引用指向next節(jié)點(diǎn),prev引用指向prev節(jié)點(diǎn)
    Node newNode = new Node(element , prev , next);
    //讓prev的next指向新節(jié)點(diǎn)。
    prev.next = newNode;
    //讓prev的下一個節(jié)點(diǎn)的prev指向新節(jié)點(diǎn)
    next.prev = newNode;
    size++;
   }
  }
 }
 //采用尾插法為鏈表添加新節(jié)點(diǎn)。
 public void add(T element)
 {
  //如果該鏈表還是空鏈表
  if (header == null)
  {
   header = new Node(element , null , null);
   //只有一個節(jié)點(diǎn),header、tail都指向該節(jié)點(diǎn)
   tail = header;
  }
  else
  {
   //創(chuàng)建新節(jié)點(diǎn),新節(jié)點(diǎn)的pre指向原tail節(jié)點(diǎn)
   Node newNode = new Node(element , tail , null);
   //讓尾節(jié)點(diǎn)的next指向新增的節(jié)點(diǎn)
   tail.next = newNode;
   //以新節(jié)點(diǎn)作為新的尾節(jié)點(diǎn)
   tail = newNode;
  }
  size++;
 }
 //采用頭插法為鏈表添加新節(jié)點(diǎn)。
 public void addAtHeader(T element)
 {
  //創(chuàng)建新節(jié)點(diǎn),讓新節(jié)點(diǎn)的next指向原來的header
  //并以新節(jié)點(diǎn)作為新的header
  header = new Node(element , null , header);
  //如果插入之前是空鏈表
  if (tail == null)
  {
   tail = header;
  }
  size++;
 }
 //刪除鏈?zhǔn)骄€性表中指定索引處的元素
 public T delete(int index)
 {
  if (index < 0 || index > size - 1)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  Node del = null;
  //如果被刪除的是header節(jié)點(diǎn)
  if (index == 0)
  {
   del = header;
   header = header.next;
   //釋放新的header節(jié)點(diǎn)的prev引用
   header.prev = null;
  }
  else
  {
   //獲取刪除點(diǎn)的前一個節(jié)點(diǎn)
   Node prev = getNodeByIndex(index - 1);
   //獲取將要被刪除的節(jié)點(diǎn)
   del = prev.next;
   //讓被刪除節(jié)點(diǎn)的next指向被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)。
   prev.next = del.next;
   //讓被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)的prev指向prev節(jié)點(diǎn)。
   if (del.next != null)
   {
    del.next.prev = prev;
   }  
   //將被刪除節(jié)點(diǎn)的prev、next引用賦為null.
   del.prev = null;
   del.next = null;
  }
  size--;
  return del.data;
 }
 //刪除鏈?zhǔn)骄€性表中最后一個元素
 public T remove()
 {
  return delete(size - 1);
 }
 //判斷鏈?zhǔn)骄€性表是否為空鏈表
 public boolean empty()
 {
  return size == 0;
 }
 //清空線性表
 public void clear()
 {
  //將底層數(shù)組所有元素賦為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();
  }
 }
}

線性表的兩種實(shí)現(xiàn)比較

空間性能:

順序表:順序表的存儲空間是靜態(tài)分布的,需要一個長度固定的數(shù)組,因此總有部分?jǐn)?shù)組元素被浪費(fèi)。 

鏈表:鏈表的存儲空間是動態(tài)分布的,因此不會空間浪費(fèi)。但是由于鏈表需要而外的空間來為每個節(jié)點(diǎn)保存指針,因此要犧牲一部分空間。

時間性能:

順序表:順序表中元素的邏輯順序與物理存儲順序是保持一致的,而且支持隨機(jī)存取。因此順序表在查找、讀取時性能很好。 

鏈表:鏈表采用鏈?zhǔn)浇Y(jié)構(gòu)來保存表內(nèi)元素,因此在插入、刪除元素時性能要好

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • springboot整合rocketmq實(shí)現(xiàn)分布式事務(wù)

    springboot整合rocketmq實(shí)現(xiàn)分布式事務(wù)

    大多數(shù)情況下很多公司是使用消息隊(duì)列的方式實(shí)現(xiàn)分布式事務(wù)。 本篇文章重點(diǎn)講解springboot環(huán)境下整合rocketmq實(shí)現(xiàn)分布式事務(wù),感興趣的可以了解一下
    2021-05-05
  • Java關(guān)鍵字volatile知識點(diǎn)總結(jié)

    Java關(guān)鍵字volatile知識點(diǎn)總結(jié)

    在本篇文章里小編給大家整理的是一篇關(guān)于Java關(guān)鍵字volatile知識點(diǎn)總結(jié)內(nèi)容,有興趣的朋友們可以學(xué)習(xí)參考下。
    2021-01-01
  • Eclipse操作SVN時中斷鎖定,文件的解鎖方法

    Eclipse操作SVN時中斷鎖定,文件的解鎖方法

    這篇文章主要介紹了Eclipse操作SVN時中斷鎖定,文件的解鎖方法,需要的朋友可以參考下
    2014-08-08
  • spring boot 配置動態(tài)刷新實(shí)現(xiàn)詳解

    spring boot 配置動態(tài)刷新實(shí)現(xiàn)詳解

    這篇文章主要介紹了spring boot 配置動態(tài)刷新實(shí)現(xiàn)詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-09-09
  • 詳解springboot整合ueditor踩過的坑

    詳解springboot整合ueditor踩過的坑

    這篇文章主要介紹了詳解springboot整合ueditor踩過的坑,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-06-06
  • 一文解析Java中的方法重寫

    一文解析Java中的方法重寫

    子類繼承父類后,可以在子類中書寫一個與父類同名同參的方法,從而實(shí)現(xiàn)對父類中同名同參數(shù)的方法的覆蓋,我們把這一過程叫做方法的重寫。本文將分析一下Java中的方法重寫,感興趣的可以了解一下
    2022-07-07
  • Java中的Thread.join()詳解

    Java中的Thread.join()詳解

    這篇文章主要介紹了Thread.join()詳解?,join是Thread類的一個方法,啟動線程后直接調(diào)用,本文通過實(shí)例代碼介紹了join方法的作用及用法詳解,需要的朋友可以參考下
    2023-09-09
  • mybatis多對多查詢的實(shí)現(xiàn)(xml方式和注解方式)

    mybatis多對多查詢的實(shí)現(xiàn)(xml方式和注解方式)

    本文主要介紹了mybatis多對多查詢的實(shí)現(xiàn),有xml方式和注解方式兩種,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2024-08-08
  • 從log4j2到Disruptor詳解

    從log4j2到Disruptor詳解

    這篇文章主要介紹了從log4j2到Disruptor詳解,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-12-12
  • SpringBoot上傳文件大小受限問題的解決辦法

    SpringBoot上傳文件大小受限問題的解決辦法

    最近有一次由于項(xiàng)目升級發(fā)現(xiàn)了一個上傳方面的問題,下面這篇文章主要給大家介紹了關(guān)于SpringBoot上傳文件大小受限問題的解決辦法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-05-05

最新評論