这个是根据贤惠的白云大佬的《大话数据结构》用java来实现的.
线性表的顺序存储结构,就是用一段地址连续的存储单元依次存储线性表的数据元素
像这样的方式就是顺序存储方式.
在java里面,我们使用一维数组来实现顺序存储结构,用下标来充当指针.
在线性表的顺序存储的结构中,我们需要三个属性来描述:
????数组data(有存储控件的起始位置)
????线性表的最大存储容量(开辟空间的大小,就是数组的长度)
????线性表的当前长度(线性表数据的元素个数,是会随着元素的插入或删除动态变动)
对于顺序存储结构来说,我们就可以很快得到具体的位置,所以对于存入或取出操作,我们可以一次性完成,时间复杂度为O(1)
但是对于插入和删除操作
我们需要删除或插入某个元素的时候,后面的元素就要进行一系列的操作,数据量大的时候是非常费时的,时间复杂度为O(n)
所以,顺序结构在存入和读取占优势,在删除和插入是劣势的.
下面是代码的实现:
public class MyList<T> { public int m_Size; public int m_Length; public T[]data; public MyList(int m_Size) { this.m_Size = m_Size; data = (T[])new Object[m_Size]; m_Length = 0; } public void ClearList(){ data = null; m_Length = 0; } public boolean ListEmpty(){ if (m_Length ==0){ return true; }else { return false; } } public int ListLength(){ return m_Length; } public boolean GetElem(int i,T e){ if (i<0 || i>=m_Length) return false; else { e = data[i]; return true; } } public int LocateElem(T e){ for (int i = 0;i<m_Length;i++){ if (data[i] == e) return i; } return -1; } public boolean PriorElem(T currentElem,T preElem){ int i = LocateElem(currentElem); if (i == -1) return false; if (i ==0) return false; preElem = data[i-1]; return true; } public boolean NextElem(T currentElem,T nextElem){ int i = LocateElem(currentElem); if (i == -1) return false; if (i == m_Length-1) return false; nextElem = data[i+1]; return true; } public void ListTraverse(){ for (T i : data) { System.out.println(i); } } public boolean ListInsert(int i,T e){ if (m_Length == m_Size) return false; if (i<0 || i>m_Length) return false; for (int k=m_Length;k>=i;k–){ data[k+1] = data[k]; } data[i] = e; m_Length++; return true; } public boolean ListDelete(int i,T e){ e = data[i]; for (int k=i+1;k<m_Length;k++){ data[k-1] = data[k]; } m_Length–; return true; }}
