java实现顺序表数据结构

╰+哭是因爲堅強的太久メ 2022-06-04 09:39 189阅读 0赞

package com.irisian;  
  
public class Point \{  
  
    private int x;  
    private int y;  
  
    public Point() \{  
        super();  
        // TODO Auto-generated constructor stub  
    \}  
  
    public Point(int x, int y) \{  
        super();  
        this.x = x;  
        this.y = y;  
    \}  
  
    public int getX() \{  
        return x;  
    \}  
  
    public void setX(int x) \{  
        this.x = x;  
    \}  
  
    public int getY() \{  
        return y;  
    \}  
  
    public void setY(int y) \{  
        this.y = y;  
    \}  
  
    @Override  
    public String toString() \{  
        return "Point \[x=" + x + ", y=" + y + "\]";  
    \}

package com.irisian;  
  
import java.util.Arrays;  
  
public class SqList \{  
    private Point \[\] p;  
    private int length;  
    private int listsize;  
  
    public Point\[\] getP() \{  
        return p;  
    \}  
  
    public void setP(Point\[\] p) \{  
        this.p = p;  
    \}  
  
    public int getLength() \{  
        return length;  
    \}  
  
    public void setLength(int length) \{  
        this.length = length;  
    \}  
  
    public int getListsize() \{  
        return listsize;  
    \}  
  
    public void setListsize(int listsize) \{  
        this.listsize = listsize;  
    \}  
  
    @Override  
    public String toString() \{  
        return "SqList \[p=" + Arrays.toString(p) + ", length=" + length + ", listsize=" + listsize + "\]";  
    \}  
  
\}

package com.irisian;  
  
public class MyList \{  
  
    private static final int LIST\_INIT\_SIZE = 100; // 初始化长度  
    private static final int LISTINCREMENT = 50; // 增加长度  
    private static final int OVERFLOW = -2; //  
    private static final int OK = 1; //  
    private static final int ERROR = 0; //  
  
    /\*\*  
     \* 初始化线性表  
     \*/  
    @SuppressWarnings("unused")  
    public int initList(SqList l) \{  
        Point\[\] p = new Point\[LIST\_INIT\_SIZE\];  
        if (p == null) \{  
            // 如果p为空则表示分配失败,则退出程序  
            System.exit(OVERFLOW);  
        \}  
        // 分配成功则将SqList的长度给改变  
        l.setListsize(LIST\_INIT\_SIZE);  
        l.setLength(0);  
        l.setP(p);  
        return OK;  
    \}  
      
    /\*\*  
     \* 为线性表插入值  
     \* @param l  需要插入值的线性表  
     \* @param i  插入位置  
     \* @param p  插入的值  
     \* @return  返回是否成功  
     \*/  
    public int insertList(SqList l,int i,Point p)\{  
        //插入的位置为1=<i<=l.getLength()+1  
        if(i<1||i>(l.getLength()+1))\{  
            return ERROR;  
        \}  
        //如果数组的长度已经满了，此时就应该重新分配长度  
        if(l.getLength()>=l.getListsize())\{  
            //定义一个新的数组，然后将原来的数组的值给赋值到新的数组中  
            Point \[\] p1=new Point\[l.getListsize()+LISTINCREMENT\];  
            for (int j = 0; j < l.getP().length; j++) \{  
                p1\[j\]=l.getP()\[j\];  
            \}  
            //将新的数组赋值给线性表  
            l.setP(p1);  
            l.setListsize(l.getListsize()+LISTINCREMENT);  
        \}  
          
        //如果插入的位置是正确的且还没有满  
        //得到插入位置的引用  
        //从后面开始移动  
        for (int j = l.getLength()-1; j >= i-1; j--) \{  
            Point point = l.getP()\[j\];  
            l.getP()\[j+1\]=point;  
        \}  
        l.getP()\[i-1\]=p;  
        l.setLength(l.getLength()+1);  
        return OK;  
    \}  
      
    /\*\*  
     \* 删除顺序表中的值  
     \* @param l 顺序表  
     \* @param i 删除元素的位置  
     \* @param p 需要删除元素的元素(删除元素通过该引用给传递回来)  
     \* @return  
     \*/  
    int listDelete(SqList l,int i,Point p)\{  
        //i的合法范围  1=<i<=l.getLength();  
        if(i<1||i>l.getLength())\{  
            return ERROR;  
        \}  
        //如果数据合法就进行删除  
        //得到需要删除的元素的引用  
        p = l.getP()\[i-1\];  
        //将i后面的数给覆盖i  
        for (int j = i; j <= l.getLength(); j++) \{  
            Point point = l.getP()\[j\];  
            l.getP()\[j-1\]=point;  
        \}  
        l.setLength(l.getLength()-1);  
        return OK;  
    \}  
      
    /\*\*  
     \* 进行两个顺序表的合并  
     \* @param l1  
     \* @param l2  
     \* @param l3  
     \*/  
    void mergeList(SqList l1,SqList l2,SqList l3)\{  
        Point\[\] p1 = l1.getP();  
        Point\[\] p2 = l2.getP();  
          
          
        //将新的sqlList设置为两个线性表的总长度  
        l3.setLength(l1.getLength()+l2.getLength());  
        l3.setListsize(l1.getLength()+l2.getLength());  
        //分配内存空间  
        l3.setP(new Point\[l1.getLength()+l2.getLength()\]);  
        Point\[\] p3 = l3.getP();  
          
        int i=0,i1=0,i2=0;  
        System.err.println();  
          
        while(i<l1.getLength()&&i<l1.getLength())\{  
            if(p1\[i\].getX()>p2\[i\].getX())\{  
                p3\[i\]=p1\[i\];  
                i1++;  
            \}else if(p1\[i\].getX()<p2\[i\].getX())\{  
                p3\[i\]=p2\[i\];  
                i2++;  
            \}else\{  
                p3\[i\]=p2\[i\];  
                i1++;  
                i2++;  
            \}  
            i++;  
        \}  
        while(i1<l1.getLength())\{  
            p3\[i\]=p1\[i1\];  
            i1++;  
        \}  
          
        while(i2<l2.getLength())\{  
            p3\[i\]=p2\[i2\];  
            i2++;  
        \}  
    \}  
      
      
    public static void main(String\[\] args) \{  
        MyList MyList = new MyList();  
        SqList sqList = new SqList();  
        int initList = MyList.initList(sqList);  
        if(initList==OK)\{  
            System.out.println("顺序表初始化成功!");  
        \}  
        Point point = new Point(1, 2);  
        MyList.insertList(sqList, 1, point);  
        System.err.println(sqList);  
        //删除一个元素  
        System.err.println("删除一个元素");  
        MyList.listDelete(sqList, 1, point);  
        System.err.println(sqList);  
        System.err.println(point);  
        System.err.println("插入一个元素");  
        point=new Point(2,3);  
        MyList.insertList(sqList, 1, point);  
        System.err.println(sqList);  
        System.err.println("初始化另外一个顺序表");  
        SqList sqList2 = new SqList();  
        int initList2 = MyList.initList(sqList2);  
        System.out.println(initList2==OK?"顺序表初始化成功":"失败");  
        Point point2 = new Point(3, 4);  
        MyList.insertList(sqList2, 1, point);  
        MyList.insertList(sqList2, 2, point2);  
        System.err.println(sqList2);  
        System.err.println("合并");  
        SqList sqList3 = new SqList();  
        MyList.mergeList(sqList, sqList2, sqList3);  
        System.err.println(sqList3);  
          
          
          
    \}  
      
\}