Java 數(shù)據(jù)結(jié)構(gòu)線性表之順序存儲詳解原理
線性表的定義
線性表的邏輯特征:
- ①有且僅有一個稱為開始元素的a1,她沒有前趨,僅有一個后繼結(jié)點a2;
- ②有且僅有一個稱為終端元素的an,他沒有后繼,只有一個直接前驅(qū)a(n-1);
- ③其余元素ai(2≤i≤n-1)稱為內(nèi)部元素,他們都有且僅有一個直接前驅(qū)a(i-1)和直接后繼a(i+1)。
線性表的圖像表示
線性表的基本運算
- 線性表初始化
- 求表長
- 按索引值查找元素
- 按值查找
- 插入元素
- 刪除
線性表的存儲之順序存儲
線性表順序存儲的定義:線性表的順序存儲指的是將線性表的數(shù)據(jù)元素按其邏輯次序依次存入一組連續(xù)的存儲單元里,用這種方式存儲的線性表稱為順序表。
定義線性表
定義線性表的默認(rèn)空間大小,定義一個數(shù)組,定義數(shù)組的長度,初始化一個size用來保存里面元素的個數(shù)。
/** 定義線性表默認(rèn)空間大小 */ private final Integer ListSize=100; /**定義數(shù)組長度*/ private Integer Len; /** 定義線性表保存的數(shù)據(jù)類型 * 使用泛型*/ private Object[] list; /**存一個當(dāng)前元素的個數(shù)*/ private Integer size=0; /**定義默認(rèn)線性表*/ public SeqList(){ Len = ListSize; this.list = new Object[Len]; size++; }
初始化線性表
把線性表里面的元素全部置空
/**清空線性表*/ public void clear(){ for (int i = 0; i < size; i++) { list[i]=null; } size=0; }
添加元素
這里采用尾插法,即每次默認(rèn)將元素放在最后面
/**添加元素到指定位置*/ public void insert(T element , int index){ if(index>=Len || index<0){ throw new IndexOutOfBoundsException("輸入的索引值超過了線性表的范圍"); } Capacity(size+1); //將添加元素的元素往后移一位 for (int i = size-2; i >= index-1; i--) { list[i+1]=list[i]; } list[index-1]=element; size++; } /**添加元素到末尾*/ public void add(T element){ insert(element,size); }
查找元素
這個模塊分為按索引值查找,和按元素值查找
/**線性表的查找 * 按索引值查找*/ public T getNode(int index){ return (T)list[index-1]; } /**按元素值查找返回索引值*/ public int LocateNode(T t){ for(int i=0;i<list.length;i++){ if(list[i].equals(t)){ return i+1; } } System.out.println("沒有找到該元素!"); return -1; }
刪除元素
刪除元素,又分為刪除指定元素,和刪除最后一個元素
/**刪除指定位置的元素*/ public T delete(int index){ if(!OutIndex(index)){ throw new IndexOutOfBoundsException("刪除位置不在線性表的索引范圍內(nèi)!"); } for (int i = index-1; i < size-1; i++) { list[i]=list[i+1]; } /*if(size - index >0){ System.arraycopy(list,index,list,index-1,size-index); }*/ list[size-1]=null; size--; return (T) list; } /**刪除最后一個元素*/ public T remove(){ return delete(size-1); }
打印線性表
打印線性表,其實就是重寫一個toString方法,將線性表打印出來
/**循環(huán)打印線性表*/ @Override public String toString(){ StringBuilder sb = new StringBuilder(); if(isEmpty()){ return "[]"; } else { sb.append("["); for (int i = 0; i < size-1; i++) { int a=0; if(list[i]!=null){ sb.append(list[ i ]); } else { break; } sb.append(","); } sb.append("]"); sb.deleteCharAt(sb.indexOf(",]")); } return sb.toString(); }
實現(xiàn)的完整代碼
class SeqList<T>{ /** 定義線性表默認(rèn)空間大小 */ private final Integer ListSize=100; /**定義數(shù)組長度*/ private Integer Len; /** 定義線性表保存的數(shù)據(jù)類型 * 使用泛型*/ private Object[] list; /**存一個當(dāng)前元素的個數(shù)*/ private Integer size=0; /**定義默認(rèn)線性表*/ public SeqList(){ Len = ListSize; this.list = new Object[Len]; size++; } /**定義自定義長度的線性表*/ public SeqList(int length){ Len = length; list = new Object[Len]; size++; } /**獲取當(dāng)前線性表的長度*/ public int getLen(){ return Len; } /**獲取當(dāng)前線性表元素的個數(shù)*/ public int getSize(){ return size; } /**根據(jù)元素查找在線性表中的位置,未找到返回-1*/ public int getIndex(T element){ for (int i = 0; i < size; i++) { if(list[i].equals(element)){ return i; } } return -1; } /**判斷是否表滿或表空*/ private boolean OutIndex(int index){ //return size==Len;//不擴(kuò)容的話,可以這樣寫,但是怕擴(kuò)容 if(index>size || index<0){ return false; } else { return true; } } /**根據(jù)索引值返回元素*/ private T getElement(int index){ if(!OutIndex(index)){ throw new IndexOutOfBoundsException("輸入的索引值超過了線性表的范圍"); /* System.out.println("輸入索引超過了線性的范圍"); return null; */ } return (T)list[index]; } /**擴(kuò)容*/ private T Capacity(int capacity){ if(capacity<Len){ Len = Len+(Len+1)/2; if(capacity<Len){ Capacity(Len); } else { list = Arrays.copyOf(list,Len); return (T) list; } } return (T)list; } /**添加元素到指定位置*/ public void insert(T element , int index){ if(index>=Len || index<0){ throw new IndexOutOfBoundsException("輸入的索引值超過了線性表的范圍"); } Capacity(size+1); //將添加元素的元素往后移一位 for (int i = size-2; i >= index-1; i--) { list[i+1]=list[i]; // System.out.println("i="+i); } list[index-1]=element; size++; } /**添加元素到末尾*/ public void add(T element){ insert(element,size); } /**判斷元素表是否為空*/ public boolean isEmpty(){ return size==0; } /**刪除指定位置的元素*/ public T delete(int index){ if(!OutIndex(index)){ throw new IndexOutOfBoundsException("刪除位置不在線性表的索引范圍內(nèi)!"); } for (int i = index-1; i < size-1; i++) { list[i]=list[i+1]; } /*if(size - index >0){ System.arraycopy(list,index,list,index-1,size-index); }*/ list[size-1]=null; size--; return (T) list; } /**刪除最后一個元素*/ public T remove(){ return delete(size-1); } /**清空線性表*/ public void clear(){ for (int i = 0; i < size; i++) { list[i]=null; } size=0; } /**線性表的查找 * 按索引值查找*/ public T getNode(int index){ return (T)list[index-1]; } /**按元素值查找返回索引值*/ public int LocateNode(T t){ for(int i=0;i<list.length;i++){ if(list[i].equals(t)){ return i+1; } } System.out.println("沒有找到該元素!"); return -1; } /**循環(huán)打印線性表*/ @Override public String toString(){ StringBuilder sb = new StringBuilder(); if(isEmpty()){ return "[]"; } else { sb.append("["); for (int i = 0; i < size-1; i++) { int a=0; if(list[i]!=null){ sb.append(list[ i ]); } else { break; } sb.append(","); } sb.append("]"); sb.deleteCharAt(sb.indexOf(",]")); } return sb.toString(); } }
測試一下
測試代碼
public static void main(String[] args) { SeqList<String> seqList = new SeqList<String>(); //添加一個元素 seqList.add("pier"); seqList.add("真好看"); seqList.add("90度點頭"); System.out.println("添加后的線性表為\n\t"+seqList.toString()); seqList.insert("pipi",1); System.out.println("在位置1的地方添加元素后的線性表為\n\t"+seqList.toString()); seqList.delete(1); System.out.println("刪除第二個元素后的線性表為\n\t"+seqList.toString()); System.out.println("pier時第"+seqList.LocateNode("pier")+"個元素"); System.out.println("第1個元素是"+seqList.getNode(1)+"。"); }
運行結(jié)果
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)線性表之順序存儲詳解原理的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu) 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Sonar編譯問題對應(yīng):File [...] can''t be indexed twice.
今天小編就為大家分享一篇關(guān)于Sonar編譯問題對應(yīng):File [...] can't be indexed twice.,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2018-12-12J2SE基礎(chǔ)之下載eclipse并創(chuàng)建項目
本文給大家介紹的是最流行的java 集成開發(fā)環(huán)境IDE eclipse的使用方法,非常的簡單,有需要的小伙伴可以參考下2016-05-05springboot mybatis-plus實現(xiàn)登錄接口
本文主要介紹了springboot mybatis-plus實現(xiàn)登錄接口,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-11-11