Java 數(shù)據(jù)結(jié)構(gòu)線性表之順序存儲(chǔ)詳解原理
更新時(shí)間：2021年10月25日 12:00:17 作者：pier～呀
線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素、使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系
線性表的定義
線性表的邏輯特征：
- ①有且僅有一個(gè)稱為開始元素的a1，她沒有前趨，僅有一個(gè)后繼結(jié)點(diǎn)a2；
- ②有且僅有一個(gè)稱為終端元素的an,他沒有后繼，只有一個(gè)直接前驅(qū)a(n-1)；
- ③其余元素ai(2≤i≤n-1)稱為內(nèi)部元素，他們都有且僅有一個(gè)直接前驅(qū)a(i-1)和直接后繼a(i+1)。
線性表的圖像表示
線性表的基本運(yùn)算
- 線性表初始化
- 求表長
- 按索引值查找元素
- 按值查找
- 插入元素
- 刪除
線性表的存儲(chǔ)之順序存儲(chǔ)
線性表順序存儲(chǔ)的定義：線性表的順序存儲(chǔ)指的是將線性表的數(shù)據(jù)元素按其邏輯次序依次存入一組連續(xù)的存儲(chǔ)單元里，用這種方式存儲(chǔ)的線性表稱為順序表。
定義線性表
定義線性表的默認(rèn)空間大小，定義一個(gè)數(shù)組，定義數(shù)組的長度，初始化一個(gè)size用來保存里面元素的個(gè)數(shù)。
/** 定義線性表默認(rèn)空間大小 */
private final Integer ListSize=100;
/**定義數(shù)組長度*/
private Integer Len;
/** 定義線性表保存的數(shù)據(jù)類型
* 使用泛型*/
private Object[] list;
/**存一個(gè)當(dāng)前元素的個(gè)數(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);
}
查找元素
這個(gè)模塊分為按索引值查找，和按元素值查找
/**線性表的查找
* 按索引值查找*/
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;
}
刪除元素
刪除元素，又分為刪除指定元素，和刪除最后一個(gè)元素
/**刪除指定位置的元素*/
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;
}
/**刪除最后一個(gè)元素*/
public T remove(){
return delete(size-1);
}
打印線性表
打印線性表，其實(shí)就是重寫一個(gè)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();
}
實(shí)現(xiàn)的完整代碼
class SeqList<T>{
/** 定義線性表默認(rèn)空間大小 */
private final Integer ListSize=100;
/**定義數(shù)組長度*/
private Integer Len;
/** 定義線性表保存的數(shù)據(jù)類型
* 使用泛型*/
private Object[] list;
/**存一個(gè)當(dāng)前元素的個(gè)數(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)前線性表元素的個(gè)數(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;
}
/**刪除最后一個(gè)元素*/
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>();
//添加一個(gè)元素
seqList.add("pier");
seqList.add("真好看");
seqList.add("90度點(diǎn)頭");
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("刪除第二個(gè)元素后的線性表為\n\t"+seqList.toString());
System.out.println("pier時(shí)第"+seqList.LocateNode("pier")+"個(gè)元素");
System.out.println("第1個(gè)元素是"+seqList.getNode(1)+"。");
}
運(yùn)行結(jié)果
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)線性表之順序存儲(chǔ)詳解原理的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu) 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在日常的開發(fā)過程中,為了提高代碼的可靠性和健壯性,同時(shí)也是檢測代碼的質(zhì)量,減少測試環(huán)節(jié)的問題,會(huì)對完成的業(yè)務(wù)功能代碼編寫單元測試,在本文中,將分享一些單元測試的實(shí)踐和心得,需要的朋友可以參考下2023-11-11
字符串拼接問題應(yīng)該是每個(gè)Java程序員都熟知的事情了，幾乎每個(gè)Java程序員都讀過關(guān)于StringBuffer/StringBuilder來拼接字符串。下面這篇文章主要給大家介紹了關(guān)于JDK8中的字符串拼接的相關(guān)資料，需要的朋友可以參考下。2018-04-04
關(guān)于Lists.partition集合分組使用以及注意事項(xiàng)
這篇文章主要介紹了關(guān)于Lists.partition集合分組使用以及注意事項(xiàng),具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01
這篇文章主要介紹了Spring面向切面編程AOP詳情，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
java整數(shù)與byte數(shù)組的轉(zhuǎn)換實(shí)現(xiàn)代碼
這篇文章主要介紹了java整數(shù)與byte數(shù)組的轉(zhuǎn)換實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-07-07
SpringBoot下獲取resources目錄下文件的常用方法
本文詳細(xì)介紹了SpringBoot獲取resources目錄下文件的常用方法,包括使用this.getClass()方法、ClassPathResource獲取以及hutool工具類ResourceUtil獲取,感興趣的可以了解一下2024-10-10
用SpringBoot框架來接收multipart/form-data文件方式
這篇文章主要介紹了用SpringBoot框架來接收multipart/form-data文件方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
大家好，本篇文章主要講的是Java中的方法內(nèi)聯(lián)介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
SpringBoot如何IDEA中實(shí)現(xiàn)熱部署
這篇文章主要介紹了SpringBoot如何IDEA中實(shí)現(xiàn)熱部署,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
SpringDataRedis入門和序列化方式解決內(nèi)存占用問題小結(jié)
spring-data-redis是spring-data模塊的一部分,專門用來支持在spring管理項(xiàng)目對redis的操作，這篇文章主要介紹了SpringDataRedis入門和序列化方式解決內(nèi)存占用問題,需要的朋友可以參考下2022-12-12