线性表

插入

  1. public void insert(int i, Object x) throws Exception {
  2.         if (curLen == listElem.length) // 判断顺序表是否已满
  3.             throw new Exception("顺序表已满");// 输出异常
  5.         if (i < 0 || i > curLen) // i小于0或者大于表长
  6.             throw new Exception("插入位置不合理");// 输出异常
  8.         for (int j = curLen; j > i; j--)
  9.             listElem[j] = listElem[j - 1];// 插入位置及之后的元素后移
  11.         listElem[i] = x; // 插入x
  12.         curLen++;// 表长度增1
  13.     }

删除

  1.     public void remove(int i) throws Exception {
  2.         if (i < 0 || i > curLen - 1) // i小于1或者大于表长减1
  3.             throw new Exception("删除位置不合理");// 输出异常
  5.         for (int j = i; j < curLen - 1; j++)
  6.             listElem[j] = listElem[j + 1];// 被删除元素之后的元素左移
  8.         curLen--; // 表长度减1
  9.     }

查找

  1.     public int indexOf(Object x) {
  2.         int j = 0;// j为计数器
  3.         while (j < curLen && !listElem[j].equals(x))
  4.             // 从顺序表中的首结点开始查找，直到listElem[j]指向元素x或到达顺序表的表尾
  5.             j++;
  6.         if (j < curLen)// 判断j的位置是否位于表中
  7.             return j; // 返回x元素在顺序表中的位置
  8.         else
  9.             return -1;// x元素不在顺序表中
  10.     }

逆置

  1.     public void reverse() {
  2.         for (int i = 0,j=curLen-1; i < j; i++,j--) {
  3.             Object temp = listElem[i];
  4.             listElem[i] = listElem[j];
  5.             listElem[j] = temp;
  6.         }
  7.     }

有序表插入

  1.    void insert(int x) throws Exception {
  2.         int i;
  3.         if (n>MaxSize)         //表满不能插入
  4.             throw new Exception("Overflow");
  5.         r[0]=x;
  6.         for(i=n;r[i]>x;i--)
  7.             r[i+1]=r[i];//将i位置元素后移
  8.         r[i+1]=x;//在位置i+1插入元素x
  9.         n++;//线性表长度增1
  10.     }

单链表

获取

  1. public Object get(int i) throws Exception {
  2.         Node p = head.next;// 初始化,p指向首结点,j为计数器
  3.         int j = 0;
  4.         while (p != null && j < i) {// 从首结点向后查找，直到p指向第i个元素或p为空
  5.             p = p.next;// 指向后继结点
  6.             ++j;// 计数器的值增1
  7.         }
  8.         if (j > i || p == null) { // i小于0或者大于表长减1
  9.             throw new Exception("第" + i + "个元素不存在");// 输出异常
  10.         }
  11.         return p.data;// 返回元素p
  12.     }

插入

  1.     public void insert(int i, Object x) throws Exception {
  2.         Node p = head;// 初始化p为头结点,j为计数器
  3.         int j = -1; // 第i个结点前驱的位置
  4.         while (p != null && j < i - 1) {// 寻找i个结点的前驱
  5.             p = p.next;
  6.             ++j;// 计数器的值增1
  7.         }
  8.         if (j > i - 1 || p == null) // i不合法
  9.             throw new Exception("插入位置不合理");// 输出异常
  11.         Node s = new Node(x); // 生成新结点
  12.         s.next=p.next;// 插入单链表中
  13.         p.next=s;
  14.     }

删除

  1. public void remove(int i) throws Exception {
  2.         Node p = head;// p指向要删除结点的前驱结点
  3.         int j = -1;
  4.         while (p.next != null && j < i - 1) {// 寻找i个结点的前驱
  5.             p = p.next;
  6.             ++j;// 计数器的值增1
  7.         }
  8.         if (j > i - 1 || p.next == null) { // i小于0或者大于表长减1
  9.             throw new Exception("删除位置不合理");// 输出异常
  10.         }
  11.         p.next=p.next.next;// 删除结点
  12.     }

查找

  1.     public int indexOf(Object x) {
  2.         Node p = head.next;// 初始化,p指向首结点,j为计数器
  3.         int j = 0;
  4.         while (p != null && !p.data.equals(x)) {// 从单链表中的首结点元素开始查找，直到p.data指向元素x或到达单链表的表尾
  5.             p = p.next;// 指向下一个元素
  6.             ++j;// 计数器的值增1
  7.         }
  8.         if (p != null)// 如果p指向表中的某一元素
  9.             return j;// 返回x元素在顺序表中的位置
  10.         else
  11.             return -1;// x元素不在顺序表中
  12.     }

逆置

  1.     public void reverse() {
  2.         if(head==null||head.next==null)
  3.             return;
  4.        Node pre = null;
  5.        Node cur = null;
  6.        Node next = null;
  7.        cur = head.next;
  8.        next = cur.next;
  9.        cur.next = null;
  10.        pre = cur;
  11.        cur = next;
  12.        while(cur.next != null){
  13.            next = cur.next;
  14.            cur.next = pre;
  15.            pre = cur;
  16.            cur = next;
  17.        }
  18.        cur.next = pre;
  19.        head.next = cur;
  20.     }

二叉链表

  1. class BiTree {
  3.   private BiTreeNode root;// 树的根结点
  5.   public BiTree() {// 构造一棵空树
  6.     this.root = null;
  7.   }
  9.   public BiTree(BiTreeNode root) {// 构造一棵树
  10.     this.root = root;
  11.   }
  13.   // 由先根遍历的数组和中根遍历的数组建立一棵二叉树
  14.   // 其中参数preOrder是整棵树的 先根遍历，inOrder是整棵树的中根遍历，preIndex是
  15.   // 先根遍历从preOrder字符串中的开始位置，inIndex是中根遍历从字符串inOrder中的开始位置，count表示树结点的个数
  16.   public BiTree(String preOrder, String inOrder, int preIndex, int inIndex,
  17.       int count) {
  18.     if (count > 0) {// 先根和中根非空
  19.       char r = preOrder.charAt(preIndex);// 取先根字符串中的第一个元素作为根结点
  20.       int i = 0;
  21.       for (; i < count; i++)
  22.         // 寻找根结点在中根遍历字符串中的索引
  23.         if (r == inOrder.charAt(i + inIndex))
  24.           break;
  26.       root = new BiTreeNode(r);// 建立树的根结点
  27.       root.lchild=new BiTree(preOrder, inOrder, preIndex + 1, inIndex,
  28.           i).root;// 建立树的左子树
  29.       root.rchild=new BiTree(preOrder, inOrder, preIndex + i + 1,
  30.           inIndex + i + 1, count - i - 1).root;// 建立树的右子树
  31.     }
  32.   }
  34.   // 由标明空子树的先根遍历序列建立一棵二叉树
  35.   private static int index = 0;// 用于记录preStr的索引值
  37.   public BiTree(String[] preStr) {
  38.     String c = preStr[index++];// 取出字符串索引为index的字符，且index增1
  39.     if (!c.equals("#") ) {// 字符不为#
  40.       root = new BiTreeNode(c);// 建立树的根结点
  41.       root.lchild=new BiTree(preStr).root;// 建立树的左子树
  42.       root.rchild=new BiTree(preStr).root;// 建立树的右子树
  43.     } else
  44.       root = null;
  45.   }
  47.   // 先根遍历二叉树基本操作的递归算法
  48.   public void preRootTraverse(BiTreeNode T) {
  49.     if (T != null) {
  50.       System.out.print(T.data); // 访问根结点
  51.       preRootTraverse(T.lchild);// 访问左子树
  52.       preRootTraverse(T.rchild);// 访问右子树
  53.     }
  54.   }
  56.   // 先根遍历二叉树基本操作的非递归算法
  57.   public void preRootTraverse() {
  58.     BiTreeNode T = root;
  59.     if (T != null) {
  60.       LinkStack S = new LinkStack();// 构造栈
  61.       S.push(T);// 根结点入栈
  62.       while (!S.isEmpty()) {
  63.         T = (BiTreeNode) S.pop();// 移除栈顶结点，并返回其值
  64.         System.out.print(T.data +" "); // 访问结点
  65.         while (T != null) {
  66.           if (T.lchild != null) // 访问左孩子
  67.             System.out.print(T.lchild.data +" "); // 访问结点
  69.           if (T.rchild != null)// 右孩子非空入栈
  70.             S.push(T.rchild);
  72.           T = T.lchild;
  73.         }
  74.       }
  75.     }
  76.   }
  78.   // 中根遍历二叉树基本操作的递归算法
  79.   public void inRootTraverse(BiTreeNode T) {
  80.     if (T != null) {
  81.       inRootTraverse(T.lchild);// 访问左子树
  82.       System.out.print(T.data); // 访问根结点
  83.       inRootTraverse(T.rchild);// 访问右子树
  84.     }
  85.   }
  87.   // 中根遍历二叉树基本操作的非递归算法
  88.   public void inRootTraverse() {
  89.     BiTreeNode T = root;
  90.     if (T != null) {
  91.       LinkStack S = new LinkStack();// 构造链栈
  92.       S.push(T); // 根结点入栈
  93.       while (!S.isEmpty()) {
  94.         while (S.peek() != null)
  95.           // 将栈顶结点的所有左孩子结点入栈
  96.           S.push(((BiTreeNode) S.peek()).lchild);
  97.         S.pop(); // 空结点退栈
  98.         if (!S.isEmpty()) {
  99.           T = (BiTreeNode) S.pop();// 移除栈顶结点，并返回其值
  100.           System.out.print(T.data +" "); // 访问结点
  101.           S.push(T.rchild);// 结点的右孩子入栈
  102.         }
  103.       }
  104.     }
  105.   }
  107.   // 后根遍历二叉树基本操作的递归算法
  108.   public void postRootTraverse(BiTreeNode T) {
  109.     if (T != null) {
  110.       postRootTraverse(T.lchild);// 访问左子树
  111.       postRootTraverse(T.rchild);// 访问右子树
  112.       System.out.print(T.data); // 访问根结点
  113.     }
  114.   }
  116.   // 后根遍历二叉树基本操作的非递归算法
  117.   public void postRootTraverse() {
  118.     BiTreeNode T = root;
  119.     if (T != null) {
  120.       LinkStack S = new LinkStack();// 构造链栈
  121.       S.push(T); // 根结点进栈
  122.       Boolean flag;// 访问标记
  123.       BiTreeNode p = null;// p指向刚被访问的结点
  124.       while (!S.isEmpty()) {
  125.         while (S.peek() != null)
  126.           // 将栈顶结点的所有左孩子结点入栈
  127.           S.push(((BiTreeNode) S.peek()).lchild);
  128.         S.pop(); // 空结点退栈
  129.         while (!S.isEmpty()) {
  130.           T = (BiTreeNode) S.peek();// 查看栈顶元素
  131.           if (T.rchild == null || T.rchild == p) {
  132.             System.out.print(T.data +" "); // 访问结点
  133.             S.pop();// 移除栈顶元素
  134.             p = T;// p指向刚被访问的结点
  135.             flag = true;// 设置访问标记
  136.           } else {
  137.             S.push(T.rchild);// 右孩子结点入栈
  138.             flag = false;// 设置未被访问标记
  139.           }
  140.           if (!flag)
  141.             break;
  142.         }
  143.       }
  144.     }
  145.   }
  147.   // 层次遍历二叉树基本操作的算法(自左向右)
  148.   public void levelTraverse() {
  149.     BiTreeNode T = root;
  150.     if (T != null) {
  151.       LinkQueue L = new LinkQueue();// 构造队列
  152.       L.offer(T);// 根结点入队列
  153.       while (!L.isEmpty()) {
  154.         T = (BiTreeNode) L.poll();
  155.         System.out.print(T.data); // 访问结点
  156.         if (T.lchild != null)// 左孩子非空，入队列
  157.           L.offer(T.lchild);
  158.         if (T.rchild != null)// 右孩子非空，入队列
  159.           L.offer(T.rchild);
  160.       }
  161.     }
  163.   }
  165.   public BiTreeNode getRoot() {
  166.     return root;
  167.   }
  169.   public void setRoot(BiTreeNode root) {
  170.     this.root = root;
  171.   }
  173.   // 统计叶结点数目
  174.   public int countLeafNode(BiTreeNode T) {
  175.     int count = 0;
  176.     if (T != null) {
  177.       if (T.lchild == null && T.rchild == null) {
  178.         ++count;// 叶结点个数加1
  179.       } else {
  180.         count += countLeafNode(T.lchild); // 加上左子树上叶结点的个数
  181.         count += countLeafNode(T.rchild);// 加上右子树上叶结点的个数
  182.       }
  183.     }
  184.     return count;
  185.   }
  187.   // 统计结点的数目
  188.   public int countNode(BiTreeNode T) {
  189.     int count = 0;
  190.     if (T != null) {
  191.       ++count;// 结点的个数加1
  192.       count += countNode(T.lchild); // 加上左子树上结点的个数
  193.       count += countNode(T.rchild);// 加上右子树上结点的个数
  194.     }
  195.     return count;
  196.   }
  198.   public int getDepth(BiTreeNode T) {
  199.     if (T != null) {
  200.       int lDepth = getDepth(T.lchild);// 左子树的深度
  201.       int rDepth = getDepth(T.rchild);// 右子树的深度
  202.       return 1 + (lDepth > rDepth ? lDepth : rDepth);// 返回左子树的深度和右子树的深度中的最大值加1
  203.     }
  204.     return 0;
  205.   }
  207.   //  采用递归模型方法，计算二叉树的深度
  208.   public int getDepth1(BiTreeNode T) {
  209.     if (T==null) 
  210.       return 0;
  211.     else if (T.lchild==null&&T.rchild==null)
  212.       return 1;
  213.     else 
  214.       return 1 + (getDepth1(T.lchild)> getDepth1(T.rchild)? getDepth1(T.lchild) : getDepth1(T.rchild));
  215.   }
  217. }

图的邻接矩阵

  1. class MGraph {
  3.     private int vexNum, arcNum;
  5.     private Object[] vexs;
  7.     private int[][] arcs;
  9.     private static boolean[] visited;
  11.     public MGraph() {
  13.         this(0, 0, null, null);
  15.     }
  17.     public MGraph(int vexNum, int arcNum, Object[] vexs,
  19.     int[][] arcs) {
  21.         this.vexNum = vexNum;
  23.         this.arcNum = arcNum;
  25.         this.vexs = vexs;
  27.         this.arcs = arcs;
  29.     }
  31.     public void createGraph(String[] str, int n, int e, int[][] arc){
  32.         vexNum = n;
  33.         arcNum =  e;
  34.         vexs = new Object[vexNum];
  35.         this.vexs = str;
  36.         arcs = new int[vexNum][vexNum];
  37.         for (int v = 0; v < vexNum; v++)
  38.             for (int u = 0; u < vexNum; u++)
  39.                 arcs[v][u] = 0;
  40.         for (int k = 0; k < arcNum; k++) {
  41.             int v = arc[k][0];
  42.             int u = arc[k][1];
  43.             arcs[v][u] = arcs[u][v] = 1;
  44.         }
  45.     }
  47.     public int getVexNum() {
  49.         return vexNum;
  51.     }
  53.     public int getArcNum() {
  55.         return arcNum;
  57.     }
  59.     public void setArcNum(int arcNum) {
  61.         this.arcNum = arcNum;
  63.     }
  65.     public void setArcs(int[][] arcs) {
  67.         this.arcs = arcs;
  69.     }
  71.     public void setVexNum(int vexNum) {
  73.         this.vexNum = vexNum;
  75.     }
  77.     public void setVexs(Object[] vexs) {
  79.         this.vexs = vexs;
  81.     }
  83.     public int[][] getArcs() {
  85.         return arcs;
  87.     }
  89.     public Object[] getVexs() {
  91.         return vexs;
  93.     }
  95.     public int locateVex(Object vex) {
  97.         for (int v = 0; v < vexNum; v++)
  99.             if (vexs[v].equals(vex))
  101.                 return v;
  103.         return -1;
  105.     }
  107.     public Object getVex(int v) throws Exception {
  109.         if (v < 0 && v >= vexNum)
  111.             throw new Exception("no position");
  113.         return vexs[v];
  115.     }
  117.     public int firstAdjVex(int v) throws Exception {
  119.         if (v < 0 && v >= vexNum)
  121.             throw new Exception("!");
  123.         for (int j = 0; j < vexNum; j++)
  125.             if (arcs[v][j] != 0 && arcs[v][j] < 9999)
  127.                 return j;
  129.         return -1;
  131.     }
  133.     public int nextAdjVex(int v, int w) throws Exception {
  135.         if (v < 0 && v >= vexNum)
  137.             throw new Exception("no position");
  139.         for (int j = w + 1; j < vexNum; j++)
  141.             if (arcs[v][j] != 0 && arcs[v][j] < 9999)
  143.                 return j;
  145.         return -1;
  147.     }
  149.     public void DFSTraverse(MGraph G) throws Exception {
  151.         visited = new boolean[G.getVexNum()];
  153.         for (int v = 0; v < G.getVexNum(); v++)
  155.             visited[v] = false;
  157.         for (int v = 0; v < G.getVexNum(); v++)
  159.             if (!visited[v])
  161.                 DFS(G, v);
  163.     }
  165.     private void DFS(MGraph G, int v) throws Exception {
  167.         visited[v] = true;
  169.         System.out.print(G.getVex(v).toString() + " ");
  171.         for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w))
  173.             if (!visited[w])
  175.                 DFS(G, w);
  177.     }
  179. }
  181. public class Main {
  183.     public static Scanner sc;
  185.     public static void main(String[] args) throws Exception {
  186.         Scanner sc = new Scanner(System.in);
  187.         String a[] = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K",
  188.                 "L", "M", "N" };
  189.         int i, n, e, j;
  190.         n = sc.nextInt();
  191.         e = sc.nextInt();
  192.         int[][] arc = new int[e][2];
  193.         for (i = 0; i < e; i++)
  194.             for (j = 0; j < 2; j++)
  195.                 arc[i][j] = sc.nextInt();
  196.         MGraph G = new MGraph();
  197.         G.createGraph(a, n, e, arc);
  198.         System.out.print("DFS:");
  199.         G.DFSTraverse(G);
  200.         System.out.println();
  201.     }
  202. }

邻接表

  1. class ALGraph implements IGraph {
  3.   private int vexNum, arcNum;
  5.   private VNode[] vexs;
  7.   private static boolean[] visited;// 访问标志数组
  9.   public ALGraph() {
  10.     this(0, 0, null);
  11.   }
  13.   public ALGraph(int vexNum, int arcNum, VNode[] vexs) {
  14.     this.vexNum = vexNum;
  15.     this.arcNum = arcNum;
  16.     this.vexs = vexs;
  17.   }
  19.   public void createGraph() {
  20.     Scanner sc = new Scanner(System.in);
  21.     vexNum = sc.nextInt();
  22.     arcNum = sc.nextInt();
  23.     vexs = new VNode[vexNum];
  24.     String Node[]={"A","B","C","D","E","F","G","H","I","J","K","L","M","N"}; //顶点信息
  25.     for (int v = 0; v < vexNum; v++)
  26.       vexs[v] = new VNode(Node[v]);
  27.     for (int k = 0; k < arcNum; k++) {
  28.       int v = sc.nextInt();// 弧尾
  29.       int u = sc.nextInt();// 弧头
  30.       int value = 1;
  31.       addArc(v, u, value);
  32.       addArc(u, v, value);
  33.     }
  36.   }
  37.   public void addArc(int v, int u, int value) {
  38.     ArcNode arc = new ArcNode(u, value);
  39.     arc.nextArc=vexs[v].firstArc;
  40.     vexs[v].firstArc=arc;
  41.   }
  43.   public int getVexNum() {
  44.     return vexNum;
  45.   }
  47.   public int getArcNum() {
  48.     return arcNum;
  49.   }
  51.   public int locateVex(Object vex) {
  52.     for (int v = 0; v < vexNum; v++)
  53.       if (vexs[v].data.equals(vex))
  54.         return v;
  55.     return -1;
  56.   }
  58.   public VNode[] getVexs() {
  59.     return vexs;
  60.   }
  62.   public Object getVex(int v) throws Exception {
  63.     if (v < 0 && v >= vexNum)
  64.       throw new Exception("第" + v + "个顶点不存在!");
  66.     return vexs[v].data;
  67.   }
  69.   public int firstAdjVex(int v) throws Exception {
  70.     if (v < 0 && v >= vexNum)
  71.       throw new Exception("第" + v + "个顶点不存在!");
  73.     VNode vex = vexs[v];
  74.     if (vex.firstArc != null)
  75.       return vex.firstArc.adjVex;
  76.     else
  77.       return -1;
  78.   }
  80.   public int nextAdjVex(int v, int w) throws Exception {
  81.     if (v < 0 && v >= vexNum)
  82.       throw new Exception("第" + v + "个顶点不存在!");
  83.     VNode vex = vexs[v];
  85.     ArcNode arcvw = null;
  86.     for (ArcNode arc = vex.firstArc; arc != null; arc = arc.nextArc)
  87.       if (arc.adjVex == w) {
  88.         arcvw = arc;
  89.         break;
  90.       }
  91.     if (arcvw != null && arcvw.nextArc != null)
  92.       return arcvw.nextArc.adjVex;
  93.     else
  94.       return -1;
  95.   }
  97.   public void setArcNum(int arcNum) {
  98.     this.arcNum = arcNum;
  99.   }
  101.   public void setVexNum(int vexNum) {
  102.     this.vexNum = vexNum;
  103.   }
  105.   public void setVexs(VNode[] vexs) {
  106.     this.vexs = vexs;
  107.   }
  109.   public void DFSTraverse() throws Exception {
  110.        visited = new boolean[getVexNum()];
  111.        for (int v = 0; v < getVexNum(); v++)
  112.     // 访问标志数组初始化
  113.     visited[v] = false;
  114.     System.out.print("DFS:");
  115.     for (int v = 0; v < getVexNum(); v++)
  116.           if (!visited[v])// 对尚未访问的顶点调用DFS
  117.       DFS(v);
  118.   }
  120.   private  void DFS(int v) throws Exception {
  121.        visited[v] = true;
  122.         // 访问第v个顶点
  123.        System.out.print(getVex(v).toString() + " "); 
  124.        for (int w = firstAdjVex(v); w >= 0; w = nextAdjVex(v, w))
  125.             if (!visited[w])// 对v的尚未访问的邻接顶点w递归调用DFS
  126.        DFS(w);
  127.   }
  129.   public void BFSTraverse() throws Exception {
  130.        visited = new boolean[getVexNum()];// 访问标志数组
  131.        for (int v = 0; v < getVexNum(); v++)
  132.              // 访问标志数组初始化
  133.             visited[v] = false;
  134.             System.out.print("BFS:");
  135.             for (int v = 0; v < getVexNum(); v++)
  136.     if (!visited[v]) // v尚未访问
  137.         BFS(v);
  138.   }
  140.   private void BFS(int v) throws Exception {
  141.        visited[v] = true;
  142.        System.out.print(getVex(v).toString() + " ");
  143.        CirQueue Q = new CirQueue();// 辅助队列Q
  144.        Q.EnQueue(v);// v入队列
  145.        while (!Q.isEmpty()) {
  146.             int u = (Integer) Q.DeQueue();// 队头元素出队列并赋值给u
  147.             for (int w = firstAdjVex(u); w >= 0; w = nextAdjVex(u, w))
  148.     if (!visited[w]) {// w为u的尚未访问的邻接顶点
  149.         visited[w] = true;
  150.         System.out.print(getVex(w).toString() + " "); 
  151.         Q.EnQueue(w);
  152.     }
  153.          }
  154.   }
  156.   void DispMGraph(){
  158.      int i;
  159.      ArcNode p;
  161.      System.out.println("Graph adjlist:");
  163.         for(i=0;i<vexNum;i++){
  164.            System.out.print(i + " " +vexs[i].data + " ");
  165.            p = vexs[i].firstArc;
  166.            while(p!=null){
  167.              System.out.print(p.adjVex + " ");
  168.              p=  p.nextArc;
  169.            }
  170.            System.out.println("");
  171.         }
  172.      }
  176. }

折半查找

插入

  1. oid insert(int x) throws Exception {
  2.         int i;
  3.         if (n>MaxSize)         //表满不能插入
  4.             throw new Exception("Overflow");
  5.         r[0]=x;
  6.         for(i=n;r[i]>x;i--)
  7.             r[i+1]=r[i];//将i位置元素后移
  8.         r[i+1]=x;//在位置i+1插入元素x
  9.         n++;//线性表长度增1
  10.     }

查找

  1. int Bin_Search(int key){
  2.         if(n>0){
  3.             int low = 0,high = n;
  4.             while(low<=high){
  5.                 int mid = (low+high)/2;
  6.                 if(r[mid]==key){
  7.                     return mid;
  8.                 }else if(r[mid]>key){
  9.                     high = mid - 1;
  10.                 }else{
  11.                     low = mid + 1;
  12.                 }
  13.             }
  14.         }
  15.         return -1;
  16.     }

查找(递归)

  1.     int Bin_Search(int key){
  3.         return Bin_Search(1,n,key);
  4.     }
  5.     int Bin_Search(int low,int high,int key){
  6.         if(low>high)
  7.             return -1;
  8.         int mid = (low + high) >> 1;
  9.         if(r[mid] > key)
  10.             return Bin_Search(low, mid - 1, key);
  11.         else if(r[mid] < key)
  12.             return Bin_Search(mid + 1, high, key);
  13.         return mid;
  14.     }

二叉排序树（1）-递归方式

  1. public class BSTree { //二叉排序树类
  3.     public BiTreeNode root;   //根结点
  5.     public BSTree() {  //构造空二叉排序树
  6.         root = null;
  7.     }
  8. /*
  9.     public BiTreeNode getRoot() {
  10.         return root;
  11.     }
  13.     public void setRoot(BiTreeNode root) {
  14.         this.root = root;
  15.     }
  16. */
  18.     public boolean isEmpty() { //判断是否空二叉树
  19.         return this.root == null;
  20.     }
  22.     public void inOrderTraverse(BiTreeNode p) { //中根次序遍历以p结点为根的二叉树
  23.         if (p != null) {
  24.             inOrderTraverse(p.lchild);
  25.             System.out.print(((RecordNode) p.data).toString() + "");
  26.             inOrderTraverse(p.rchild);
  27.         }
  28.     }
  30.     //查找关键字值为key的结点,若查找成功返回结点值，否则返回null
  31.     public Object searchBST(Comparable key) {
  32.         if (key == null || !(key instanceof Comparable)) {
  33.             return null;
  34.         }
  35.         return searchBST(root, key);
  36.     }
  38.     //二叉排序树查找的递归算法
  39.     //在二叉排序树中查找关键字为key的结点。若查找成功则返回结点值，否则返回null
  40.     private Object searchBST(BiTreeNode p, Comparable key) {
  41.         if (p != null) {
  42.             if (key.compareTo(((RecordNode) p.data).key) == 0) //查找成功
  43.             {
  44.                 return p.data;
  45.             }
  46.             //     System.out.print(((RecordNode) p.data).key + "? ");
  47.             if (key.compareTo(((RecordNode) p.data).key) < 0) {
  48.                 return searchBST(p.lchild, key);     //在左子树中查找
  49.             } else {
  50.                 return searchBST(p.rchild, key);    //在右子树中查找
  51.             }
  52.         }
  53.         return null;
  54.     }
  56.     //在二叉排序树中插入关键字为Key,数据项为theElement的结点,若插入成功返回true,否则返回false
  57.     public boolean insertBST(Comparable key, Object theElement) {
  58.         if (key == null || !(key instanceof Comparable)) {//不能插入空对象或不可比较大小的对象
  59.             return false;
  60.         }
  61.         if (root == null) {
  62.             root = new BiTreeNode(new RecordNode(key, theElement)); //建立根结点
  63.             return true;
  64.         }
  65.         return insertBST(root, key, theElement);
  66.     }
  68.     //将关键字为key,数据项为theElement的结点插入到以p为根的二叉排序树中的递归算法
  69.     private boolean insertBST(BiTreeNode p, Comparable key, Object theElement) {
  70.         if (key.compareTo(((RecordNode) p.data).key) == 0) {
  71.             return false;             //不插入关键字重复的结点
  72.         }
  73.         if (key.compareTo(((RecordNode) p.data).key) < 0) {
  74.             if (p.lchild == null) {        //若p的左子树为空
  75.                 p.lchild=new BiTreeNode(new RecordNode(key, theElement));  //建立叶子结点作为p的左孩子
  76.                 return true;
  77.             } else {                      //若p的左子树非空
  78.                 return insertBST(p.lchild, key, theElement);   //插入到p的左子树中
  79.             }
  80.         } else if (p.rchild == null) {    //若p的右子树为空
  81.             p.rchild=new BiTreeNode(new RecordNode(key, theElement));    //建立叶子结点作为p的右孩子
  82.             return true;
  83.         } else {                          //若p的右子树非空
  84.             return insertBST(p.rchild, key, theElement);   //插入到p的右子树中
  85.         }
  86.     }
  88.     //二叉排序树中删除结点算法。若删除成功返回删除结点值，否则返回null
  89.     public Object removeBST(Comparable key) {
  90.         if (root == null || key == null || !(key instanceof Comparable)) {
  91.             return null;
  92.         }
  93.         //在以root为根的二叉排序树中删除关键字为elemKey的结点
  94.         return removeBST(root, key, null);
  95.     }
  97.     //在以p为根的二叉排序树中删除关键字为elemKey的结点。parent是p的父结点，递归算法
  98.     private Object removeBST(BiTreeNode p, Comparable elemKey, BiTreeNode parent) {
  99.         if (p != null) {
  100.             if (elemKey.compareTo(((RecordNode) p.data).key) < 0) { //在左子树中删除
  101.                 return removeBST(p.lchild, elemKey, p);    //在左子树中递归搜索
  102.             } else if (elemKey.compareTo(((RecordNode) p.data).key) > 0) { //在右子树中删除
  103.                 return removeBST(p.rchild, elemKey, p);    //在右子树中递归搜索
  104.             } else if (p.lchild != null && p.rchild != null) {
  105.                 //相等且该结点有左右子树
  106.                 BiTreeNode innext = p.rchild;    //寻找p在中根次序下的后继结点innext
  107.                 while (innext.lchild != null) { //即寻找右子树中的最左孩子
  108.                     innext = innext.lchild;
  109.                 }
  110.                 p.data=innext.data;              //以后继结点值替换p
  111.                 return removeBST(p.rchild, ((RecordNode) p.data).key, p); //递归删除结点p
  112.             } else {//p是1度和叶子结点
  113.                 if (parent == null) {  //删除根结点，即p==root
  114.                     if (p.lchild != null) {
  115.                         root = p.lchild;
  116.                     } else {
  117.                         root = p.rchild;
  118.                     }
  119.                     return p.data;       //返回删除结点p值
  120.                 }
  121.                 if (p == parent.lchild) { //p是parent的左孩子
  122.                     if (p.lchild != null) {
  123.                         parent.lchild=p.lchild;  //以p的左子树填补
  124.                     } else {
  125.                         parent.lchild=p.rchild;
  126.                     }
  127.                 } else if (p.lchild != null) { //p是parent的右孩子且p的左子树非空
  128.                     parent.rchild=p.lchild;
  129.                 } else {
  130.                     parent.rchild=p.rchild;
  131.                 }
  132.                 return p.data;
  133.             }
  134.         }
  135.         return null;
  136.     }
  137. }

排序

不带监视哨的直接插入排序算法

  1. public void insertSort() {
  2.         RecordNode temp;
  3.         int i, j;
  4.         for (i = 1; i < this.curlen; i++) {//n-1趟扫描
  5.             temp = r[i];  //将待插入的第i条记录暂存在temp中
  6.             for (j = i - 1; j >= 0 && temp.key.compareTo(r[j].key) < 0; j--) { //将前面比r[i]大的记录向后移动
  7.                 r[j + 1] = r[j];
  8.             }
  9.             r[j + 1] = temp;          //r[i]插入到第j+1个位置
  10.             display();
  11.         }
  12.     }

带监视哨的直接插入排序算法

  1.   public void insertSortWithGuard() {
  2.         int i, j;
  3.         for (i = 2; i <this.curlen; i++) {      //n-1趟扫描
  4.             r[0] = r[i]; //将待插入的第i条记录暂存在r[0]中，同时r[0]为监视哨
  5.             for (j = i - 1; r[0].key.compareTo(r[j].key) < 0; j--) { //将前面较大元素向后移动
  6.                 r[j + 1] = r[j];
  7.             }
  8.             r[j + 1] = r[0];          // r[i]插入到第j+1个位置
  9.             display();
  10.         }
  11.     }

冒泡排序算法

  1. public void bubbleSort() {
  2.         //    System.out.println("冒泡排序");
  3.         RecordNode temp;       //辅助结点
  4.         boolean flag = true;   //是否交换的标记
  5.         for (int i = 1; i < this.curlen && flag; i++) { //有交换时再进行下一趟，最多n-1趟
  6.             flag = false;                              //假定元素未交换
  7.             for (int j = 0; j < this.curlen - i; j++) { //一次比较、交换
  8.                 if (r[j].key.compareTo(r[j + 1].key) > 0) {     //逆序时，交换
  9.                     temp = r[j];
  10.                     r[j] = r[j + 1];
  11.                     r[j + 1] = temp;
  12.                     flag = true;
  13.                 }
  14.             }
  15.             display();
  16.         }
  17.     }

快速排序算法

  1.     //交换排序表r[i..j]的记录，使支点记录到位，并返回其所在位置
  2.     //此时，在支点之前(后)的记录关键字均不大于(小于)它
  3.     public int Partition(int i, int j) {
  4.         RecordNode pivot = r[i];          //第一个记录作为支点记录
  5.         //    System.out.print(i + ".." + j + ",  pivot=" + pivot.key + "  ");
  6.         while (i < j) {    //从表的两端交替地向中间扫描
  7.             while (i < j && pivot.key.compareTo(r[j].key) <= 0) {
  8.                 j--;
  9.             }
  10.             if (i < j) {
  11.                 r[i] = r[j];   //将比支点记录关键字小的记录向前移动
  12.                 i++;
  13.             }
  14.             while (i < j && pivot.key.compareTo(r[i].key) > 0) {
  15.                 i++;
  16.             }
  17.             if (i < j) {
  18.                 r[j] = r[i];   //将比支点记录关键字大的记录向后移动
  19.                 j--;
  20.             }
  21.         }
  22.         r[i] = pivot;         //支点记录到位
  23.         //    display();
  24.         return i;             //返回支点位置
  25.     }
  27.     //对子表r[low..high]快速排序
  28.     public void qSort(int low, int high) {
  29.         if (low < high) {
  30.             int pivotloc = Partition(low, high);  //一趟排序，将排序表分为两部分
  31.             qSort(low, pivotloc - 1);   //低子表递归排序
  32.             qSort(pivotloc + 1, high);  //高子表递归排序
  33.         }
  34.     }
  37.     public void quickSort() {
  38.         qSort(0, this.curlen - 1);
  39.     }

直接选择排序

  1.     public void selectSort() {
  2.         RecordNode temp; //辅助结点
  3.         for (int i = 0; i < this.curlen - 1; i++) {//n-1趟排序
  4.             //每趟在从r[i]开始的子序列中寻找最小元素
  5.             int min = i;               //设第i条记录的关键字最小
  6.             for (int j = i + 1; j < this.curlen; j++) {//在子序列中选择关键字最小的记录
  7.                 if (r[j].key.compareTo(r[min].key) < 0) {
  8.                     min = j;             //记住关键字最小记录的下标
  9.                 }
  10.             }
  11.             if (min != i) {    //将本趟关键字最小的记录与第i条记录交换
  12.                 temp = r[i];
  13.                 r[i] = r[min];
  14.                 r[min] = temp;
  15.             }
  16.         }
  17.     }

扩展

散列表

  1. class HashList{
  2.     int MaxSize = 11;
  3.     int[] ht = new int[MaxSize];
  5.     int HashFunc(int k) {
  6.         return k%MaxSize;
  7.     }
  8.     public HashList() {
  9.         for(int i=0;i<MaxSize;i++)
  10.             ht[i]=-1;
  11.     }
  13.     void Display(){
  14.         for (int i=0;i<MaxSize;i++)
  15.             System.out.print(ht[i]+" ");
  16.         System.out.println();
  17.     }
  19.     int HashSearch(int k) throws Exception {
  20.         int j = HashFunc(k);
  21.         if (ht[j] == k)
  22.             return 1;
  23.         else if (ht[j] == -1)
  24.             ht[j] = k;
  25.         else {
  26.             int i = (j + 1) % MaxSize;
  27.             int cnt = 1;
  28.             while (ht[i] != -1 && i != j) {
  29.                 cnt++;
  30.                 if (ht[i] == k) {
  31.                     return cnt;
  32.                 } else
  33.                     i = (i + 1) % MaxSize;
  34.             }
  35.             if(i == j) throw new Exception("Overflow");
  36.             else {
  37.                 ht[i] = k;
  38.             }
  39.         }
  40.         return -1;
  41.     }
  43.     double HashASL() throws Exception {
  44.         double ASL=0;
  45.         int n=0;
  46.         for(int i=0;i<MaxSize;i++)
  47.             if(ht[i]!=-1) {
  48.                 ASL+=HashSearch(ht[i]);
  49.                 System.out.println(ht[i] + " " + HashSearch(ht[i]));
  50.                 n++;
  51.             }
  52.         return (double)Math.round(ASL/n*100000)/100000;
  53.     }
  54. }
  59. class LinkHash{
  60.     int MaxSize = 11;
  61.     Node[] ht = new Node[MaxSize];
  62.     public LinkHash() {
  63.         for (int i = 0; i < MaxSize; i++)
  64.             ht[i] = null;  //NULL is empty
  65.     }
  68.     void Display() {
  69.         for (int i = 0; i < MaxSize; i++) {
  70.             System.out.print("Hash address:" + i + ",value:");
  71.             for (Node p = ht[i]; p != null; p = p.next)
  72.                 System.out.print(p.data + " ");
  73.             System.out.println();
  74.         }
  75.     }
  77.     int HashFunc(int k){
  78.         return k % 11;   //hash函数，假设为除余法，余数为11
  79.     }
  80.     int HashSearch(int k){
  81.         int j = HashFunc(k);
  82.         Node p = ht[j];
  83.         while(p!=null && p.data != k) {
  84.             p = p.next;
  85.         }
  86.         if(p!=null && p.data == k) return 1;
  87.         else {
  88.             Node s = new Node();
  89.             s.data = k;
  90.             s.next = ht[j];
  91.             ht[j] = s;
  92.         }
  93.         return 0;
  94.     }
  95. }

栈

  1. class SeqStack{
  2.     int stackMax = 5;
  3.     Object[] data;
  4.     int top = 0;
  5.     public SeqStack() {
  6.         data = new Object[stackMax];
  7.         top = 0;
  8.     }
  10.     public void push(Object x) throws Exception {
  11.         if(top==stackMax){
  12.             throw new Exception("Overflow");
  13.         }else{
  14.             data[top++] = x;
  15.         }
  16.     }
  18.     public Object pop() throws Exception {
  19.         if(top==0){
  20.             throw new Exception("Downflow");
  21.         }else {
  22.             return data[--top];
  23.         }
  24.     }
  26.     public Object getTop() throws Exception {
  27.         if(top==0){
  28.             throw new Exception("Downflow");
  29.         }else {
  30.             return data[top - 1];
  31.         }
  32.     }
  34.     public boolean isEmpty(){
  35.         return top==0;
  36.     }
  37. }
  40. class LinkStack{
  41.     Node top;
  43.     public LinkStack() {
  44.         top = null;
  45.     }
  47.     public void push(Object x){
  48.         top = new Node(x,top);
  49.     }
  51.     public Object pop() throws Exception {
  52.         if(isEmpty()){
  53.             throw new Exception("Downflow");
  54.         }else {
  55.             Node p = top;
  56.             top = top.next;
  57.             return p.data;
  58.         }
  59.     }
  61.     public Object getTop() throws Exception {
  62.         if(isEmpty()){
  63.             throw new Exception("Downflow");
  64.         }else {
  65.             return top.data;
  66.         }
  67.     }
  69.     public boolean isEmpty(){
  70.         return top==null;
  71.     }
  72. }

队列

  1. class LinkQueue{
  2.     Node front;
  3.     Node rear;
  5.     public LinkQueue(){
  6.         rear = front = null;
  7.     }
  10.     void EnQueue(Object data){
  11.         Node p =new Node(data);
  12.         if(front != null){
  13.             rear.next = p;
  14.             rear = p;
  15.         }else{
  16.             front = rear = p;
  17.         }
  18.     }
  20.     Object DeQueue() throws Exception{
  21.         if(front != null){
  22.             Node p = front;
  23.             front = front.next;
  24.             if(p==rear){
  25.                 rear = null;
  26.             }
  27.             return p.data;
  28.         }else{
  29.             throw new Exception("Downflow");
  30.         }
  32.     }
  34.     Object GetQueue() throws Exception{
  35.         if(front != null){
  36.             return front.data;
  37.         }else{
  38.             throw new Exception("Downflow");
  39.         }
  41.     }
  43.     boolean isEmpty(){
  44.         return front == null;
  45.     }
  47. }
  50. class CirQueue{
  51.     Object[] queueElem;
  52.     int front;
  53.     int rear;
  54.     int QueueSize=5;
  55.     public CirQueue(){
  56.         front = rear = 0;
  57.         queueElem = new Object[QueueSize];
  58.     }
  60.     public void clear(){
  61.         front = rear = 0;
  62.     }
  64.     public boolean isEmpty(){
  65.         return front == rear;
  66.     }
  68.     public int length(){
  69.         return (rear-front+queueElem.length)% queueElem.length;
  70.     }
  72.     public boolean isFull(){
  73.         return (rear+1) % QueueSize ==front;
  74.     }
  76.     public void EnQueue(Object x) throws Exception{
  77.         if((rear+1)%queueElem.length==front){
  78.             throw new Exception(" Overflow");
  79.         }else{
  80.             queueElem[rear] = x;
  81.             rear = (rear+1)%queueElem.length;
  82.         }
  83.     }
  85.     public Object DeQueue() throws Exception {
  86.         if(front==rear){
  87.             throw new Exception("Downflow");
  88.         }else{
  89.             Object t = queueElem[front];
  90.             front = (front+1)%queueElem.length;
  91.             return t;
  92.         }
  93.     }
  95.     public Object GetQueue() throws Exception {
  96.         if(front==rear){
  97.             throw new Exception("Downflow");
  98.         }else{
  99.             Object t = queueElem[front];
  100.             return t;
  101.         }
  102.     }
  104. }