顺序表(java版).doc

第 5 页 共 5 页/线性表的抽象数据类型定义public interface ListIntfpublic int size(); /返回表长度public void clear(); /重置为空表public boolean isEmpty(); /若为空表返回true,否则返回falsepublic Object get(int i); /返回第i个数据元素(返回类型可不同)public int indexOf(Object obj); /第1个与obj满足关系equals()的数据元素位序,这样的数据元素不存在,则返回值为-1(obj的数据类型根据实际不同)public Object getPre(Object obj); /若obj是表中的元素,返回它的前驱public Object getNext(Object obj); /若obj是表中的元素,返回它的后继public void insertElementAt(Object obj,int i); /在第i个位置之前插入新的数据元素obj,表长度加1public Object remove(int i); /删除第i个数据元素,并返回其值,表长减1public Object remove(Object obj); /删除数据元素obj,并返回其值,表长减1public class SqList implements ListIntf public static final int MAXSIZE=100; /线性表最大长度Object elem=new ObjectMAXSIZE; /存放线性表元素的数组private int len=0; /线性表的长度,初值为0/取得表最大长度public int getMAXSIZE()return MAXSIZE;/* * 实现接口方法 */Override重置表为空表public void clear() len=0; /设置表长为0/Override返回第i个数据元素的值(返回类型可不同)public Object get(int i) if(len=0)return null; /表空,查找失败if(ilen)return null; /查找位置不合法,查找失败return elemi-1; /查找成功/Override若obj是表中的元素,返回它的后继public Object getNext(Object obj) int i=indexOf(obj);if(i=-1)return null; /指定元素不存在else if(i=len)return null; /指定元素位于最后一位,不存在后继元素return elemi; /查找后继成功,返回后继/Override若obj是表中的元素,返回它的前驱public Object getPre(Object obj) int i=indexOf(obj);if(i=-1)return null; /指定元素不存在else if(i=1)return null; /指定元素位于第一位,不存在前驱元素return elemi-2; /查找前驱成功,返回前驱 /Override第1个与obj满足关系equals()的数据元素的位序,若这样的数据元素不存在,则返回值为-1(obj的类型根据实际不同)public int indexOf(Object obj) for(int i=0;ilen;i+)if(elemi.equals(obj)return i+1; /查找成功,返回位序return -1; /查找失败/Override在第i个位置之前插入新的数据元素obj,表长度加1public void insertElementAt(Object obj, int i) if(len=MAXSIZE) /判断线性表的存储空间是否已满System.out.println(-溢出-);return;else if(ilen+1)System.out.println(-插入位置非法-);return; /插入位置非法for(int j=len-1;j=i-1;j-)elemj+1=elemj;elemi-1=obj; /插入元素len+; /表长加1return;/Override若为空表,则返回true,否则返回falsepublic boolean isEmpty() if(len=0)return true; /表空,返回truereturn false; /表非空,返回false/Override删除第i个数据元素,并返回其值,表长度减1public Object remove(int i) Object obj;if(ilen)System.out.println(-删除位置非法-);return null;obj=elemi-1; /被删除的值for(int j=i-1;j表中元素);for(int i=0;ilen;i+)System.out.println(elemi.toString();import java.util.*;public class SqListTest /* * param args */public static void main(String args) System.out.println(=Begin=);System.out.println(-构造顺序表-);Object obj;int n;Scanner input=new Scanner(System.in);SqList sl=new SqList();System.out.println(表长:+sl.size();/构造5个元素的顺序表for(int i=0;i5;i+)System.out.print(输入元素:);obj=input.next();sl.insertElementAt(obj, sl.size()+1);System.out.println(表长:+sl.size();sl.printList();System.out.println(-增加元素-);System.out.print(元素:);obj=input.next();System.out.print(位置:);n=Integer.parseInt(input.next();sl.insertElementAt(obj, n);System.out.println(表长:+sl.size();sl.printList();System.out.println(-查找元素-);System.out.print(元素:);obj=input.next();n=sl.indexOf(obj);if(n!=-1)System.out.println(.元素+obj+位于第+n+位.);System.out.print(位置:);n=Integer.parseInt(input.next();obj=sl.get(n);if(obj!=null)System.out.println(.第+n+位元素为+obj+.);System.out.println(-删除元素-);System.out.print(位置:);n=Integer.parseInt(input.next();obj=sl.remove(n);if(obj!=null)System.out.println(.删除的元素为+obj+.);System.out.println(表长:+sl.size();sl.printList();System.out.print(元素:);obj=input.next()