《顺序表和单链表》由会员分享，可在线阅读，更多相关《顺序表和单链表（8页珍藏版）》请在金锄头文库上搜索。
1、顺序表public interface Ilist public void clear();public boolean isEmpty();public int length();public Object get(int i) throws Exception;public void insert(int i,Object x) throws Exception;public void remove(int i) throws Exception;public int indexOf(Object x);public void display();public void delete(in
2、t a)throws Exception;public void delsame()throws Exception;public class Sqlist implements Ilist private Object listElem;/线性表存储空间private int curLen;/线性表当前长度构造一个存储空间为 maxSize 的顺序表：public Sqlist(int maxSize)curLen=0;/置顺序表当前长度为 0listElem=new ObjectmaxSize;/为顺序表分配 maxSize 个存储单元将顺序表置空：public void clear()
3、curLen=0;判断顺序表是否非空public boolean isEmpty() return curLen=0;求顺序表中的数据元素的个数：public int length() return curLen;读取顺序表中的第 i 个数据元素：public Object get(int i) throws Exception if(icurLen-1)throw new Exception(第+i+个元素不存在);return listElemi;顺序表的插入操作算法：public void insert(int i, Object x) throws Exceptionif(curLen
4、=listElem.length)/判断顺序表是否已满throw new Exception(顺序表已满);if(icurLen)/i 不合法throw new Exception(插入位置不合法);for(int j=curLen;ji;j-)listElemj=listElemj-1;/插入位置及其之后的所有数据元素后移一位listElemi=x;/插入 xcurLen+;/表长加 1顺序表的删除操作算法：public void remove(int i) throws Exception if(icurLen-1)/i 不合法throw new Exception(删除位置不合法);fo
5、r(int j=i;ji|p=null) / i 小于 0 或者大于表长减 1 时，即 i 不合法throw new Exception(第+i+个元素不存在);/抛出异常System.out.println(第+i+元素的值为+p.data);return p.data;/返回结点 p 的数据域值在带头结点的单链表的第 i 个结点前插入一个值为 x 的新结点：public void insert(int i,Object x)throws ExceptionNode p=head; /初始化 p 为头结点，j 为计数器int j=-1;while(p!=null&ji-1|p=null)/i
6、 不合法throw new Exception(插入位置不合法);/抛出异常Node s=new Node(x);/生成新结点s.next=p.next;/修改链，使新结点插入单链表p.next=s;删除带头结点的单链表的第 i 个结点：public void remove(int i)throws ExceptionNode p=head; /初始化 p 为头结点，j 为计数器int j=-1;while(p.next!=null&ji-1|p.next=null)throw new Exception(删除位置不合法);p.next=p.next.next;/修改链指针，使待删除结点从单链
7、表中脱离在带头结点的单链表查找值为 x 的结点：public int indexOf(Object x)Node p=head.next; /初始化， p 指向首结点，j 为计数器int j=0;while(p!=null&!p.data.equals(x) /从首结点起查找，直到 p.data 的值为 x 或到达表尾p=p.next;/指向下一个结点+j;/计数器的值增 1if(p!=null)return j;/返回值为 x 的结点在单链表的位置elsereturn -1;/值为 x 的结点不在单链表，返回-1输出单链表的所有结点：public void display()Node nod
8、e=head.next;/取出带头结点的单链表的首结点while(node!=null)System.out.print(node.data+ );/输出结点的值node=node.next;/取下一个结点System.out.println();import java.util.*;public class LinkListTest extends LinkList public static void main(String args) throws Exception int n;Scanner reader=new Scanner(System.in);System.out.print
9、(请输入 n);n=reader.nextInt();LinkList L=new LinkList();L.create2(n);System.out.println(输出单链表中各元素的值为：);L.display();int i,y;System.out.println(执行插入请输入 i 的值：);i=new Scanner(System.in).nextInt();System.out.println(请输入 y 的值：);y=new Scanner(System.in).nextInt();L.insert(i, y);System.out.println(输出插入后的单链表中各元
10、素的值为：);L.display();System.out.println(执行删除操作请输入 i 的值：);i=new Scanner(System.in).nextInt();L.remove(i);System.out.println(输出删除之后的单链表中各元素的值为：);L.display();System.out.println(执行指定位置查找操作请输入 i 的值：);i=new Scanner(System.in).nextInt();L.get(i);System.out.println(执行查找操作请输入 y 的值：);y=new Scanner(System.in).ne
11、xtInt();int order=L.indexOf(y);if(order!=-1)System.out.println(单链表中第一次出现的值为+y+的数据元素的位置为：+order);elseSystem.out.println(此单链表中不包含值+y+的数据元素！);public class BiTreeNode public Object data;/结点的数据域public BiTreeNode lchild,rchild;/左右孩子域public BiTreeNode()/构造一个空结点this(null);public BiTreeNode(Object data)/创造一棵左右孩子域为空的二叉树this(data,null,null);public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild)/创造一棵数据域，左右孩子域都不为空的二叉树this.data=data;this.lchild=lchild;this.rchild=rchild;
