java 线性表的表示和实现_线性表中顺序表的的理解和实现(java)
線性表的順序表示指的是用一組地址連續的存儲單元以此存儲線性表的數據元素，這種表示也稱作線性表的順序存儲結構或順序映像。通常，稱這種存儲結構的線性表為順序表。特點是：邏輯上相鄰的數據元素，其物理次序上也是相鄰的。
順序表的存儲示意圖
假設線性表的每個元素與占用l個存儲單元，并以所占的第一個單元的存儲地址作為數據元素的存儲起始位置。則線性表中地i+1個數據元素的存儲位置LOC(a i+1)和第i個數據元素的存儲位置LOC(a i)之間有如下關系：
通常的，線性表的地i個數據元素ai的存儲位置為：
每一個數據元素的存儲位置都和線性表中的起始位置相差一個常數，這個常熟和數據元素在線性表中的位序成正比。所以，只要確定了存儲線性表的起始位置，線性表中任意數據元素都可以隨機存取。所以，線性表的順序存儲結構是一種隨機存取的存儲結構。
實現順序表(java)
首先建立一個List接口，用來定義順序表的一些操作
package 線性表的順序結構;
public interface List {
//返回順序表的大小
public int size();
//判斷線性表中是否為空
public boolean isEmpty();
//向線性表中插入數據元素
public boolean insert(int index, Object obj) throws Exception;
//刪除線性表中指定元素
public boolean delete(int index) throws Exception;
//獲取線性表的指定元素
public Object getElem(int index);
//判斷數據元素是否在鏈表中
public int searchList(Object obj);
//銷毀線性表
public void destroyList();
//將線性表置為空表
public void clearList();
//返回線性表中第一個值與obj相同的元素在線性表中的位置
public Object locateElem(Object obj);
}
實現順序表的操作方法：
package 線性表的順序結構;
public class SqList implements List {
//默認的順序表的最大長度
final int DefaultSizs = 10;
//順序表的長度最大值
int MaxSize;
//順序表的當前長度
int size;
//用于存儲順序表的數據元素
Object[] listArray;
public SqList() {
this.init(this.DefaultSizs);
}
public SqList(int size) {
this.init(size);
}
/**
* 初始化順序表
* @param size
*/
public void init(int size) {
this.MaxSize = size;
this.size = 0;
this.listArray = new Object[size];
}
@Override
/**
* 獲得順序表的長度
*/
public int size() {
// TODO Auto-generated method stub
return size;
}
@Override
/**
* 判斷順便表是否為空
*/
public boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
@Override
/**
* 在指定位置插入數據元素到順序表
*/
public boolean insert(int index, Object obj) throws Exception {
// TODO Auto-generated method stub
if(index < 1 || index > size + 1) return false;
if(size >= MaxSize) return false;
for(int j = size - 1; j >= index; j--) {
this.listArray[j + 1] = this.listArray[j];
}
this.listArray[index - 1] = obj;
++size;
return true;
}
@Override
/**
* 刪除順序表中指定位置的數據元素
*/
public boolean delete(int index) throws Exception {
// TODO Auto-generated method stub
if(index < 1 || index > size) return false;
for(int j = index; j <= size - 1; j++) {
this.listArray[j - 1] = this.listArray[j];
}
--size;
return true;
}
@Override
/**
* 獲得指定數據元素
*/
public Object getElem(int index) {
// TODO Auto-generated method stub
if(index < 1 || index > size) return null;
return this.listArray[index - 1];
}
@Override
/**
* 查找數據元素是否在順序表中
* 若在表中，返回該數據元素在順序表的序號
*/
public int searchList(Object obj) {
// TODO Auto-generated method stub
for(int j = 0; j < size; j++) {
if(this.listArray[j] == obj) return j + 1;
}
return 0;
}
public static void main(String[] args) {
SqList list = new SqList(2);
try {
list.insert(1, 100);
list.insert(2, 50);
list.insert(3, 20);
list.insert(4, 90);
for (int i = 1; i <= list.size; i++) {
System.out.println("第" + i + "個數為" + list.getElem(i));
}
} catch (Exception e) {
e.printStackTrace();
}
}
@Override
/**
* 銷毀順序表
*/
public void destroyList() {
// TODO Auto-generated method stub
this.listArray = null;
this.size = 0;
}
@Override
/**
* 清空順序表
*/
public void clearList() {
// TODO Auto-generated method stub
if(this.listArray != null && this.listArray.length != 0) {
this.listArray = new Object[this.MaxSize];
}
}
@Override
public Object locateElem(Object obj) {
// TODO Auto-generated method stub
for(int j = 0; j < size; j++) {
if(this.listArray[j] == obj) return j + 1;
}
return null;
}
}
但是在上面的代碼中我們和容易的看到一個缺點，那就是存放數據元素的數組是定長的，即，上面實現的順序表是靜態順序表。那么當數據量很大的時候，我們需要進行擴容，否則無法存儲下所有數據。
修改SqList類，增加一個判斷是否需要擴容的方法：
//進行擴容
public void seqListDempty() {
if(size == MaxSize) {
MaxSize *= 2;
Object[] newArr = new Object[MaxSize];
for (int i = 0; i < size; i++) {
newArr[i] = this.listArray[i];
}
this.listArray = newArr;
}
}
同時修改insert()方法：
@Override
/**
* 在指定位置插入數據元素到順序表
*/
public boolean insert(int index, Object obj) throws Exception {
// TODO Auto-generated method stub
if(index < 1 || index > size + 1) return false;
if(size >= MaxSize) seqListDempty();
for(int j = size - 1; j >= index; j--) {
this.listArray[j + 1] = this.listArray[j];
}
this.listArray[index - 1] = obj;
++size;
return true;
}
這樣我們就實現了動態順序表。
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的java 线性表的表示和实现_线性表中顺序表的的理解和实现(java)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java8 filter return_
- 下一篇： java socket 判断断网_jav