数据结构：线性表（Java实现）

线性表是最基本的数据结构，可用顺序存储和链式存储结构来表示。 首先创建一个接口，包含线性表的操作。

public interface Ilist { // 线性表置空操作 public void clear(); // 判断线性表是否为空操作 public boolean isEmpty(); // 获取线性表中元素的长度操作 public int length(); // 获取指定位置上面的元素操作 public Object get(int i); // 在指定位置上面插入元素的操作 public void insert(int i, Object x); // 删除指定位置上面的元素的操作 public void remove(int i); // 查找指定元素的位置首次出现的位置操作 public int indexOf(Object x); // 显示线性表中的内容操作 public void display(); };

首先介绍其顺序实现 代码如下

package Linear_table; public class Sqlist implements Ilist //线性表顺序存储 { private Object[] listElem; //存储线性表元素 private int curlen; //记录表的长度 public Sqlist(int maxsize) { listElem = new Object[maxsize]; curlen = 0; } @Override public void clear() { // 清零就是直接将表的长度置为0 curlen = 0; } @Override public boolean isEmpty() { return curlen==0; } @Override public int length() { // 直接返回表的长度 return curlen; } @Override public Object get(int i) { // 首先要判断索引是否合法 if(i<0 || i>=curlen) //线性表的的元素为 listElem[0] 到 listElem[curlen-1] { System.out.println("超出索引"); return null; } else return listElem[i]; } @Override public void insert(int i, Object x) { // 先判断是否有地方插入（表是否有空位） if(curlen == listElem.length) { System.out.println("表已满"); return; } //再判断插入位置是否合理，i==curlen 时代表插入表尾，是合法的 if(i<0||i>curlen) { System.out.println("插入位置不合法"); return; } //将元素依次后移，为插入的元素留出位置 for(int j = curlen;j>i;j--) { listElem[j] = listElem[j-1]; } //插入元素 listElem[i] = x; //插入元素后，线性表长度加1 curlen++; } @Override public void remove(int i) { //线性表的元素为listElem[0] 到listElem[curlen-1] if(i<0 || i>curlen-1) System.out.println("删除位置不合法"); //将元素依次向前覆盖 for(int j = i;j<curlen-1;j++) { listElem[j] = listElem[j+1]; } //删除后长度减1 curlen--; } @Override public int indexOf(Object x) { // 用j来记录元素所在位置,从0开始找 int j=0; //比较用equals(),不能用== while(j<curlen && !listElem[j].equals(x)) { j++; } if(j<curlen) return j; else return -1; } @Override public void display() { for(int i = 0;i < curlen; i++) { System.out.println(listElem[i]); } } }

接下来是其链式实现，首先要创建一个节点类来表示每个节点

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; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }

下面是实现类

package Linear_table; import java.util.Scanner; public class LinkList implements Ilist { //单链表的头指针作为单链表的唯一标识 public Node head; public LinkList() { head = new Node(); } public LinkList(int n,boolean Order) //构造一个长度为n的单链表，order确定插入建表方法 { this(); //初始化头节点，无数据，无指向 if(Order) create1(n); //尾插法 else create2(n); //头插法 } public void create1(int n) //尾插法，一直在尾部插入 { Scanner sc = new Scanner(System.in); for(int i=0;i<n;i++) { insert(length(),sc.next()); } } public void create2(int n) //头插法，一直在头部插入 { Scanner sc = new Scanner(System.in); for(int i=0;i<n;i++) { insert(0,sc.next()); } } @Override public void clear() { //置空操作 head.setData(null); head.setNext(null); } @Override public boolean isEmpty() { //判空操作，注意头指针，头节点，首节点的意义 //head指向的是头节点（虚加的节点），head.next指向的是首节点（真正属于链表的第一个节点元素） return head.getNext()==null; } @Override public int length() { // p指向首节点 Node p = head.getNext(); int length = 0; while(p!=null) { p = p.getNext(); length++; } return length; } @Override //按位序号查找，i的限制条件为：0 <= i <= n-1,n为当前单链表的长度 public Object get(int i) { Node p = head.getNext(); //p指向首节点 int j=0; //j为计数器 while(j<i && p!=null) { p = p.getNext(); j++; } //判断所给i是否合法，因为在单链表中长度是隐藏的，没有显式值，所以要用此方法来判断 //j>i说明i<0;p=null说明i>length-1,i不合法 if(j>i || p==null) { return new String("查询错误"); } return p.getData(); } @Override //按值查找 public int indexOf(Object x) { //p指向首节点，一个一个往后找 Node p = head.getNext(); int j = 0; while(p!=null && !p.getData().equals(x)) { p = p.getNext(); j++; } if(p != null) return j; else return -1; //不存在，返回-1 } @Override public void insert(int i, Object x) { // p为头节点，插入首先要找到i节点的前驱 Node p = head; int j = -1; while(p!=null && j<i-1) //要先找到i的前驱 { p = p.getNext(); //j = i-2时，p.getNext()正好到i-1的位置，即i的前驱 j++; } if(j>i-1 || p == null) { System.out.println("插入位置不合法"); return; } //在带有头节点的单链表中用以下语句插入 Node s = new Node(x); s.setNext(p.getNext()); p.setNext(s); // 若是不带头节点则要讨论插入位置是否为表头 // if(i==0) // { // s.next = head; // head = s; // }else // { // s.setNext(p.getNext()); // p.setNext(s); // } } @Override public void remove(int i) { //移除第i个节点，也要先找到第i个节点的前驱 Node p = head; int j = -1; while (p.getNext() != null && j < i - 1) { //想想为什么这里是p.getNext()!=null，而插入是p!=null p = p.getNext(); j++; } if (j > i - 1 || p.getNext() == null) { throw new RuntimeException("删除位置不合法"); } // 修改链指针，使待删除结点从单链表中脱离 p.setNext(p.getNext().getNext()); } public void remove(Object x) { //按值删除，也要先找到第i个节点的前驱 Node p = head; while (p.getNext() != null && !(p.getNext().data).equals(x) ) { p = p.getNext(); } if (p.getNext() == null) { throw new RuntimeException("待删除节点不存在"); } // 修改链指针，使待删除结点从单链表中脱离 p.setNext(p.getNext().getNext()); } @Override public void display() { Node p = head.getNext(); while (p != null) { // 输出结点的值 System.out.print(p.getData() + " "); // 取下一个结点 p = p.getNext(); System.out.println(); } } public void reverse() //将带头结点的单链表就地逆置 { Node p = head.next; //p指向首节点 head.next = null; //断开头节点与首节点 Node q; while(p!= null) { q = p.next; //将p插入头节点后面 p.next = head.next; head.next = p; p = q; } } public int removeAll(Object x) //删除值为x的所有节点 { Node p = head.getNext(); Node q = head; int j=0; while(p!= null) { if((p.getData()).equals(x)) { q.setNext(p.getNext()); j++; }else { q = p; p = p.getNext(); } } return j; } }

下面再拓展下双向链表

package Linear_table; import java.util.Scanner; class DuLNode { public Object data; public DuLNode prior; public DuLNode next; public DuLNode() { this(null); } public DuLNode(Object data) { this.data = data; this.prior = null; this.next = null; } } public class DuLinkList implements Ilist { public DuLNode head; public DuLinkList() { head = new DuLNode(); head.prior = head; head.next = head; } public DuLinkList(int n) { this(); Scanner sc = new Scanner(System.in); for(int j = 0;j<n;j++) insert(0,sc.next()); } @Override public void clear() { head.prior = head; head.next = head; } @Override public boolean isEmpty() { return (head.prior==head && head.next==head); } @Override public int length() { DuLNode p = head.next; int length = 0; while(p!=null) { p = p.next; length++; } return length; } @Override public Object get(int i) { DuLNode p = head.next; int j=0; while(j<i && p!=null) { p = p.next; j++; } if(j>i || p==null) { return new String("查询错误"); } return p.data; } @Override public void insert(int i, Object x) { DuLNode p = head.next; int j =0; while(!p.equals(head)&&j<i) { p = p.next; j++; } if(j != i && !p.equals(head)) { System.out.println("插入位置错误"); return; } DuLNode s = new DuLNode(x); p.prior.next = s; s.prior = p.prior; s.next = p; p.prior = s; } @Override public void remove(int i) { // TODO Auto-generated method stub DuLNode p = head.next; int j =0; while(!p.equals(head) && j<i) { p = p.next; j++; } if(j!=i) { System.out.println("删除位置不合理"); } p.prior.next = p.next; p.next.prior = p.prior; } @Override public int indexOf(Object x) { DuLNode p = head.next; int j = 0; while(p!=null && !p.data.equals(x)) { p = p.next; j++; } if(p != null) return j; else return -1; } @Override public void display() { DuLNode node = head.next; while(!node.equals(head)) { System.out.println(node.data + " "); node = node.next; } System.out.println(); //换行 } }