?
?本文根據《大話數據結構》一書，實現了Java版的順序存儲結構。
順序存儲結構指的是用一段地址連續的存儲單元一次存儲線性表的數據元素，一般用一維數組來實現。
書中的線性表抽象數據類型定義如下（第45頁）：
實現程序：
package SqList;/*** * 幾個注意點：* 1.初始化時，應考慮數組大小為負的情況* 2.在各操作中，當涉及到位置i時，都應考慮i位置不合理的情況* 3.插入操作中，需考慮線性表已滿的情況* 刪除、獲取操作中，需考慮線性表為空的情況* 4.插入刪除操作中，均應考慮插入或刪除位置為表尾情況（似乎沒必要）* 5.插入刪除操作中，別忘了最后要改變表長* * 幾點困惑：* 1.插入刪除位置為表尾時，沒有判斷語句，循環部分也不會執行，判斷是否在表尾會不會顯得畫蛇添足？* （《大話》一書中進行了該判斷）* 2.RuntimeException類型在邏輯異常時使用，因為異常暫時還沒學很好，用法是否正確？* 3.查找元素時，是否使用equals()方法比較合適？* * 拓展* 1.可進一步添加add方法，直接在表尾添加新的元素* 2.可添加整表打印輸出的方法* @author Yongh** @param <E>*/
public class SqList<E> {private Object[] data; //存儲數據元素private int length; //線性表當前長度private int maxSize;//數組長度，即最大儲存空間/** * 若初始化時未聲明大小，則默認設置為20 */ public SqList(){//data=new Object[20];//length=0;/*直接利用this()更方便*/this(20);}/** * 初始化線性表 */ public SqList(int initialSize){if(initialSize<0) {throw new RuntimeException("數組大小為負，初始化失敗！"); }else {this.maxSize =initialSize;this.data=new Object[initialSize];this.length=0;System.out.println("初始化成功！");}}/*** 判斷線性表是否為空*/public boolean IsEmpty(){if (this.length==0) {System.out.println("表為空");return true;}System.out.println("表不為空");return false; //return this.length==0 也可以直接這樣}/*** 清空線性表*/public void ClearList() {this.length=0;System.out.println("線性表已清空！");}/***獲取第i個位置的元素值*/public E GetElem(int i) {if(this.length==0) {throw new RuntimeException("空表，無法獲取數據！"); }if(i<1||i>this.length) {throw new RuntimeException("數據位置錯誤！");}System.out.println("數據獲取成功！");return (E) data[i-1];}/*** 查找元素,返回值為該元素位置，0代表查找失敗*/public int LocateElem(E e) {for(int i=1;i<=this.length;i++) {if(e==data[i-1]) { System.out.println("查找成功！");return i; }}System.out.println("查找失敗！");return 0;}/*** 在第i個位置插入新元素*/public boolean ListInsert(int i,E e) {if(i<1||i>this.length+1) {throw new RuntimeException("插入位置錯誤:"+i);}if(this.length==this.maxSize) {/*1.無法繼續插入*///System.out.println("表已滿，無法繼續插入！");//return false;/*2.增加容量*/maxSize=maxSize+10;Object[] newdata=new Object[maxSize];for (int k=1;k<=this.length;k++)newdata[k-1]=this.data[k-1];this.data=newdata;}if (i<=this.length) { //插入數據不在表尾 **這個判斷是否有必要呢？for(int j=this.length+1;j>i;j--) this.data[j-1]=this.data[j-2]; }this.data[i-1]=e; this.length++; //表長改變勿忘System.out.println("插入成功！");return true;}/*** 刪除第i個位置的元素，并用e返回其值*/public E ListDelete(int i) {if(this.length==0) {throw new RuntimeException("空表，無法執行刪除操作！");} if(i<1||i>this.length) {throw new RuntimeException("刪除位置錯誤！");}E e=(E) this.data[i-1]; if(i<this.length) { //刪除數據不在表尾 **這個判斷是否有必要呢？for(int j=i;j<this.length;j++) {this.data[j-1]=this.data[j];}}this.length--;System.out.println("刪除成功！");return e;}/*** 返回線性表的元素個數*/public int ListLength() {return this.length;}
}
測試代碼：
基本數據類型和引用類型各寫了一個測試代碼。
package SqList;public class SqListTest {public static void main(String[] args) {//SqList<Integer> nums =new SqList<Integer>(-1);SqList<Integer> nums =new SqList<Integer>(5);nums.IsEmpty();//System.out.println("——————————插入幾個位置錯誤的情況——————————");//nums.ListInsert(6, 6);//nums.ListInsert(3, 3);//nums.ListInsert(0, 0);System.out.println("——————————插入1到5,并讀取內容——————————");for(int i=1;i<=5;i++)nums.ListInsert(i, i);nums.IsEmpty();int num;for(int i=1;i<=5;i++) {num=nums.GetElem(i);System.out.println("第"+i+"個位置的值為："+num);}System.out.println("——————————查找0、5、8是否在表中——————————");System.out.print("0的位置：");System.out.println(nums.LocateElem(0)); System.out.print("1的位置：");System.out.println(nums.LocateElem(1)); System.out.print("5的位置：");System.out.println(nums.LocateElem(5)); System.out.println("——————————刪除2、5——————————");num=nums.ListDelete(2);System.out.println("已刪除："+num);num=nums.ListDelete(4);System.out.println("已刪除："+num);System.out.println("當前表長："+nums.ListLength());for(int i=1;i<=nums.ListLength();i++) {num=nums.GetElem(i);System.out.println("第"+i+"個位置的值為："+num);}nums.ClearList();nums.IsEmpty(); }
}
初始化成功！ 表為空 ——————————插入1到5,并讀取內容—————————— 插入成功！ 插入成功！ 插入成功！ 插入成功！ 插入成功！ 表不為空 數據獲取成功！ 第1個位置的值為：1 數據獲取成功！ 第2個位置的值為：2 數據獲取成功！ 第3個位置的值為：3 數據獲取成功！ 第4個位置的值為：4 數據獲取成功！ 第5個位置的值為：5 ——————————查找0、5、8是否在表中—————————— 0的位置：查找失敗！ 0 1的位置：查找成功！ 1 5的位置：查找成功！ 5 ——————————刪除2、5—————————— 刪除成功！ 已刪除：2 刪除成功！ 已刪除：5 當前表長：3 數據獲取成功！ 第1個位置的值為：1 數據獲取成功！ 第2個位置的值為：3 數據獲取成功！ 第3個位置的值為：4 線性表已清空！ 表為空
?
package SqList;public class SqListTest2 {public static void main(String[] args) {SqList<Student> students =new SqList<Student>();students .IsEmpty();System.out.println("——————————插入1到5,并讀取內容——————————");Student[] stus= {new Student("小A",11),new Student("小B",12),new Student("小C",13),new Student("小D",14),new Student("小E",151)};for(int i=1;i<=5;i++)students .ListInsert(i, stus[i-1]);students .IsEmpty();Student stu;for(int i=1;i<=5;i++) {stu=students .GetElem(i);System.out.println("第"+i+"個位置為："+stu.name);}System.out.println("——————————查找小A、小E、小龍是否在表中——————————");System.out.print("小A的位置：");stu=stus[0];System.out.println(students .LocateElem(stu)); System.out.print("小E的位置：");stu=stus[4];System.out.println(students .LocateElem(stu)); System.out.print("小龍的位置：");stu=new Student("小龍",11);System.out.println(students .LocateElem(stu)); System.out.println("——————————刪除小E、小B——————————");stu=students .ListDelete(2);System.out.println("已刪除："+stu.name);stu=students .ListDelete(4);System.out.println("已刪除："+stu.name);System.out.println("當前表長："+students .ListLength());for(int i=1;i<=students .ListLength();i++) {stu=students .GetElem(i);System.out.println("第"+i+"個位置為："+stu.name);}students .ClearList();students .IsEmpty(); }
}class Student{public Student(String name, int age) {this.name=name;this.age=age;}String name;int age;
}
初始化成功！ 表為空 ——————————插入1到5,并讀取內容—————————— 插入成功！ 插入成功！ 插入成功！ 插入成功！ 插入成功！ 表不為空 數據獲取成功！ 第1個位置為：小A 數據獲取成功！ 第2個位置為：小B 數據獲取成功！ 第3個位置為：小C 數據獲取成功！ 第4個位置為：小D 數據獲取成功！ 第5個位置為：小E ——————————查找小A、小E、小龍是否在表中—————————— 小A的位置：查找成功！ 1 小E的位置：查找成功！ 5 小龍的位置：查找失敗！ 0 ——————————刪除小E、小B—————————— 刪除成功！ 已刪除：小B 刪除成功！ 已刪除：小E 當前表長：3 數據獲取成功！ 第1個位置為：小A 數據獲取成功！ 第2個位置為：小C 數據獲取成功！ 第3個位置為：小D 線性表已清空！ 表為空
?
?
