顺序表和单链表.docx

顺序表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(int 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() 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=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(删除位置不合法);for(int j=i;jcurLen-1;j+)listElemj=listElemj+1;/被删除元素之后的所有数据元素左移一个存储位置curLen-;/表长减1顺序表的查找操作算法：public int indexOf(Object x) int j=0;/j指示顺序表中待比较数据元素，初始值指向顺序表第0个数据元素while(jcurLen&!listElemj.equals(x)/依次比较j+;if(jcurLen)/判断j的位置是否位于顺序表return j;/返回值为x的数据元素在顺序表的位置elsereturn -1;/值为x的数据元素在顺序表中不存在顺序表数据元素的输出：public void display() for(int j=0;jcurLen;j+)System.out.print(listElemj+ );System.out.println();public void delete(int a)throws Exception for(int i=a;icurLen;i+) listElemi=listElemi+1; curLen-; 删除顺序表中相同的数据元素:public void delsame()throws Exception for(int i=0;icurLen;i+) for(int j=0;jcurLen&j!=i;j+) if(listElemi.equals(listElemj) delete(j); import java.util.Scanner;public class SqlistTest public static void main(String args) throws Exception Sqlist L=new Sqlist(20); L.insert(0,1 ); L.insert(1, 3); L.insert(2, 5); L.insert(3, 2); L.insert(4, 4); L.insert(5, 6); L.insert(6, -1); L.insert(7,-21 ); L.insert(8, 54); L.insert(9,100 );System.out.println(输出顺序表中各元素的值为：);L.display();int i,x;System.out.println(执行插入请输入i的值：); i=new Scanner(System.in).nextInt(); System.out.println(请输入x的值：); x=new Scanner(System.in).nextInt(); L.insert(i,x);System.out.println(输出插入后的顺序表中各元素的值为：);L.display();System.out.println(执行删除操作请输入i的值：); i=new Scanner(System.in).nextInt(); L.remove(i);System.out.println(输出删除之后的顺序表中各元素的值为：);L.display();System.out.println(执行查找操作请输入x的值：);x=new Scanner(System.in).nextInt(); int order=L.indexOf(x); if(order!=-1) System.out.println(顺序表中第一次出现的值为+x+的数据元素的位置为：+order); else System.out.println(此顺序表中不包含值+x+的数据元素！); System.out.println(删除相同元素操作后顺序表的各元素为:); L.delsame(); L.display(); 单链表：public interface Ilist public void create1(int n)throws Exception;public void create2(int n)throws Exception;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 class Node public Object data;/存放结点值public Node next;/后继结点的引用无参数的构造函数：public Node()this(null,null); 带一个参数的构造函数：public Node(Object data)this(data,null);带两个参数的构造函数：public Node(Object data,Node next)this.data=data;this.next=next;import java.util.Scanner;public class LinkList implements Ilistpublic Node head;/单链表的头指针单链表的构造函数public LinkList()head=new Node();/初始化头指针构造一个长度为n的单链表：public LinkList(int n,boolean Order)throws Exceptionthis();/初始化头结点if(Order)create1(n);/用尾插法顺序建立单链表elsecreate2(n);/用头插法逆序建立单链表用尾插法顺序建立单链表：public void create1(int n)throws ExceptionScanner sc=new Scanner(System.in);/构造用于输入的对象for(int j=0;jn;j+)/输入n个结点的数据域值System.out.println(请输入第+j+个元素);insert(length(),sc.next();/生成新结点，插入到表尾 用头插法逆序建立单链表：public void create2(int n)throws ExceptionScanner sc=new Scanner(System.in); /构造用于输入的对象for(int j=0;jn;j+)/逆序输入n个结点的数据域值System.out.println(请输入第+j+个元素);insert(0,sc.nextInt();/生成新结点，插入到表头将一个带头结点的单链表置空：public void clear()head.data=null;head.next=null;判断带头结点的单链表是否非空：public boolean isEmpty()return head.next=null;求带头结点的单链表的长度： public int length()Node p=head.next;/初始化，p指向首结点，length为计数器int length=0;while(p!=null)/从首结点开始向后查找，直到p为空p=p.next;/指向后继结点+length;/长度增1return length;读取单链表第i个结点：public Object get(int i)throws ExceptionNode p=head.next;/初始化，p指向首结点，j为计数器int j=0;while(p!=null&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不合法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;/修改链指针，使待删除结点从单链表中脱离在带头结点的单链表查找值为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 node=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(请输入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(输出插入后的单链表中各元素的值为：);L.display();System.out.println(执行删除操作请输入i的值：);i=new Scanner(System.in).nextInt();L.remove(i);System.