文章目錄
- 線性表的定義
- 線性表的基本運算
- 線性表的存盤之順序存盤
- 定義線性表
- 添加元素
- 查找元素
- 洗掉元素
- 列印線性表
- 實作的完整代碼
- 測驗一下
線性表的定義
- 線性表的邏輯特征：
- ①有且僅有一個稱為開始元素的a1，她沒有前趨，僅有一個后繼結點a2；
- ②有且僅有一個稱為終端元素的an,他沒有后繼，只有一個直接前驅a(n-1)；
- ③其余元素ai(2≤i≤n-1)稱為內部元素，他們都有且僅有一個直接前驅a(i-1)和直接后繼a(i+1)，
線性表的基本運算
- 線性表初始化
- 求表長
- 按索引值查找元素
- 按值查找
- 插入元素
- 洗掉
線性表的存盤之順序存盤
線性表順序存盤的定義：線性表的順序存盤指的是將線性表的資料元素按其邏輯次序依次存入一組連續的存盤單元里，用這種方式存盤的線性表稱為順序表，
定義線性表
- 定義線性表的默認空間大小，定義一個陣列，定義陣列的長度，初始化一個size用來保存里面元素的個數，
/** 定義線性表默認空間大小 */
private final Integer ListSize=100;
/**定義陣列長度*/
private Integer Len;
/** 定義線性表保存的資料型別
* 使用泛型*/
private Object[] list;
/**存一個當前元素的個數*/
private Integer size=0;
/**定義默認線性表*/
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;
}
添加元素
- 這里采用尾插法，即每次默認將元素放在最后面
/**添加元素到指定位置*/
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("洗掉位置不在線性表的索引范圍內！");
}
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方法，將線性表列印出來
/**回圈列印線性表*/
@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();
}
實作的完整代碼
class SeqList<T>{
/** 定義線性表默認空間大小 */
private final Integer ListSize=100;
/**定義陣列長度*/
private Integer Len;
/** 定義線性表保存的資料型別
* 使用泛型*/
private Object[] list;
/**存一個當前元素的個數*/
private Integer size=0;
/**定義默認線性表*/
public SeqList(){
Len = ListSize;
this.list = new Object[Len];
size++;
}
/**定義自定義長度的線性表*/
public SeqList(int length){
Len = length;
list = new Object[Len];
size++;
}
/**獲取當前線性表的長度*/
public int getLen(){
return Len;
}
/**獲取當前線性表元素的個數*/
public int getSize(){
return size;
}
/**根據元素查找在線性表中的位置，未找到回傳-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;//不擴容的話，可以這樣寫，但是怕擴容
if(index>size || index<0){
return false;
}
else {
return true;
}
}
/**根據索引值回傳元素*/
private T getElement(int index){
if(!OutIndex(index)){
throw new IndexOutOfBoundsException("輸入的索引值超過了線性表的范圍");
/* System.out.println("輸入索引超過了線性的范圍");
return null; */
}
return (T)list[index];
}
/**擴容*/
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("洗掉位置不在線性表的索引范圍內！");
}
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;
}
/**回圈列印線性表*/
@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)+"，");
}
- 運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/333774.html
標籤：java