数据结构和算法 （二）数据结构基础、线性表、栈和队列、数组和字符串

Java面试宝典之数据结构基础 —— 线性表篇

 

一、数据结构概念

用我的理解，数据结构包含数据和结构，通俗一点就是将数据按照一定的结构组合起来，不同的组合方式会有不同的效率，使用不同的场景，如此而已。比 如我们*常用的数组，就是一种数据结构，有独特的承载数据的方式，按顺序排列，其特点就是你可以根据下标快速查找元素，但是因为在数组中插入和删除元素会 有其它元素较大幅度的便宜，所以会带来较多的消耗，所以因为这种特点，使得数组适合：查询比较频繁，增、删比较少的情况，这就是数据结构的概念。数据结构 包括两大类：线性结构和非线性结构，线性结构包括：数组、链表、队列、栈等，非线性结构包括树、图、表等及衍生类结构。本章我们先讲解线性结构，主要从数 组、链表、队列、栈方面进行讨论，非线性数据结构在后面会继续讲解。

 

二、线性表

线 性表是*基本、*简单、也是*常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了*个和*后一个数据元素之外，其它数据元素都是首 尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。其基本操作主要有：

1）MakeEmpty(L) 这是一个将L变为空表的方法
2）Length（L） 返回表L的长度，即表中元素个数
3）Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
4）Prev（L，i） 取i的前驱元素
5）Next（L，i） 取i的后继元素
6）Locate（L，x） 这是一个函数，函数值为元素x在L中的位置
7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
8）Delete（L，p） 从表L中删除位置p处的元素
9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
10）Clear（L）清除所有元素
11）Init（L）同*个，初始化线性表为空
12）Traverse（L）遍历输出所有元素
13）Find（L，x）查找并返回元素
14）Update（L，x）修改元素
15）Sort（L）对所有元素重新按给定的条件排序
16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址

不管采用哪种方式实现线性表，至少都应该具有上述这些基本方法，下面我会将下数据结构的基本实现方式。

 

三、基础数据结构

数 据结构是一种抽象的数据类型（ADT），可以这么说，我们可以采用任意的方式实现某种数据结构，只要符合将要实现的数据结构的特点，数据结构就是一种标 准，我们可以采用不同的方式去实现，*常用的两种就是数组和链表（包括单链表、双向链表等）。数组是非常常见的数据类型，在任何一种语言里都有它的实现， 我们这里采用Java来简单实现一下数组。
数组是一种引用类型的对象，我们可以像下面这样的方式来声明数组：

 

  1. int a[];  
  2. int[] b;  
  3. int []c;  

 

  1. a = new int[10];  

总结起来，声明一个数组有基本的三个因素：类型、名称、下标，Java里，数组在格式上相对灵活，下标和名称可以互换位置，前三种情况我们可以理解为声明一个变量，后一种为其赋值。或者像下面这样，在声明的时候赋值：

  1. int c[] = {2,3,6,10,99};  
  2. int []d = new int[10];  

 

我 稍微解释一下，其实如果只执行：int[] b,只是在栈上创建一个引用变量，并未赋值，只有当执行d = new int[10]才会在堆上真正的分配空间。上述*行为静态初始化，就是说用户指定数组的内容，有系统计算数组的大小，第二行恰恰相反，用户指定数组的大 小，由系统分配初始值，我们打印一下数组的初始值：

 

  1. int []d = new int[10];  
  2. System.out.println(d[2]);  

结果输出0，对于int类型的数组，默认的初始值为0.

但是，*对不可以像下面这样：

  1. int e[10] = new int[10];  

无法通过编译，至于为什么，语法就是这样，这是一种规范，不用去想它。
我们可以通过下标来检索数组。下面我举个简单的例子，来说明下数组的用法。

  1. public static void main(String[] args) {  
  3.     String name[];
  5.     name = new String[5];  
  6.     name[0] = “egg”;  
  7.     name[1] = “erqing”;  
  8.     name[2] = “baby”;  
  10.     for (int i = 0; i < name.length; i++) {  
  11.         System.out.println(name[i]);
  12.     }
  13. }

这是*简单的数组声明、创建、赋值、遍历的例子，下面写个增删的例子。

  1. package com.xtfggef.algo.array;  
  3. public class Array {  
  5.     public static void main(String[] args) {  
  7.         int value[] = new int[10];  
  8.         for (int i = 0; i < 10; i++) {  
  9.             value[i] = i;
  10.         }
  12.         // traverse(value);  
  13.         // insert(value, 666, 5);  
  14.         delete(value, 3);  
  15.         traverse(value);
  16.     }
  18.     public static int[] insert(int[] old, int value, int index) {  
  19.         for (int k = old.length – 1; k > index; k–)  
  20.             old[k] = old[k – 1];  
  21.         old[index] = value;
  22.         return old;  
  23.     }
  25.     public static void traverse(int data[]) {  
  26.         for (int j = 0; j < data.length; j++)  
  27.             System.out.print(data[j] + ” “);  
  28.     }
  30.     public static int[] delete(int[] old, int index) {  
  31.         for (int h = index; h < old.length – 1; h++) {  
  32.             old[h] = old[h + 1];  
  33.         }
  34.         old[old.length – 1] = 0;  
  35.         return old;  
  36.     }
  37. }

简单写一下，主要想说明数组中删除和增加元素的原理：增加元素，需要将index后面的依次向后移动，然后将值插入index位置，删除则将后面的值依次向前移动，较简单。

要记住：数组是表示相同类型的一类数据的集合，下标从0开始，就行了。

数组实现的线下表可以参考ArrayList，在JDK中附有源码，感兴趣的同学可以读读。下面我简单介绍下单链表。

单链表是*简单的链表，有节点之间首尾连接而成，简单示意如下：

%title插图%num

除了头节点，每个节点包含一个数据域一个指针域，除了头、尾节点，每个节点的指针指向下一个节点，下面我们写个例子操作一下单链表。

  1. package com.xtfggef.algo.linkedlist;  
  3. public class LinkedList<T> {  
  5.     /** 
  6.      * class node 
  7.      * @author egg 
  8.      * @param <T> 
  9.      */  
  10.     private static class Node<T> {  
  11.         T data;
  12.         Node<T> next;
  14.         Node(T data, Node<T> next) {
  15.             this.data = data;  
  16.             this.next = next;  
  17.         }
  19.         Node(T data) {
  20.             this(data, null);  
  21.         }
  22.     }
  24.     // data  
  25.     private Node<T> head, tail;  
  27.     public LinkedList() {  
  28.         head = tail = null;  
  29.     }
  31.     /** 
  32.      * judge the list is empty 
  33.      */  
  34.     public boolean isEmpty() {  
  35.         return head == null;  
  36.     }
  38.     /** 
  39.      * add head node 
  40.      */  
  41.     public void addHead(T item) {  
  42.         head = new Node<T>(item);  
  43.         if (tail == null)  
  44.             tail = head;
  45.     }
  47.     /** 
  48.      * add the tail pointer 
  49.      */  
  50.     public void addTail(T item) {  
  51.         if (!isEmpty()) {   
  52.             tail.next = new Node<T>(item);  
  53.             tail = tail.next;
  54.         } else {   
  55.             head = tail = new Node<T>(item);  
  56.         }
  57.     }
  59.     /** 
  60.      * print the list 
  61.      */  
  62.     public void traverse() {  
  63.         if (isEmpty()) {  
  64.             System.out.println(“null”);  
  65.         } else {  
  66.             for (Node<T> p = head; p != null; p = p.next)  
  67.                 System.out.println(p.data);
  68.         }
  69.     }
  71.     /** 
  72.      * insert node from head 
  73.      */  
  74.     public void addFromHead(T item) {  
  75.         Node<T> newNode = new Node<T>(item);  
  76.         newNode.next = head;
  77.         head = newNode;
  78.     }
  80.     /** 
  81.      * insert node from tail 
  82.      */  
  83.     public void addFromTail(T item) {  
  84.         Node<T> newNode = new Node<T>(item);  
  85.         Node<T> p = head;
  86.         while (p.next != null)  
  87.             p = p.next;
  88.         p.next = newNode;
  89.         newNode.next = null;  
  90.     }
  92.     /** 
  93.      * delete node from head 
  94.      */  
  95.     public void removeFromHead() {  
  96.         if (!isEmpty())  
  97.             head = head.next;
  98.         else  
  99.             System.out.println(“The list have been emptied!”);  
  100.     }
  102.     /** 
  103.      * delete frem tail, lower effect 
  104.      */  
  105.     public void removeFromTail() {  
  106.         Node<T> prev = null, curr = head;  
  107.         while (curr.next != null) {  
  108.             prev = curr;
  109.             curr = curr.next;
  110.             if (curr.next == null)  
  111.                 prev.next = null;  
  112.         }
  113.     }
  115.     /** 
  116.      * insert a new node 
  117.      * @param appointedItem 
  118.      * @param item 
  119.      * @return 
  120.      */  
  121.     public boolean insert(T appointedItem, T item) {  
  122.         Node<T> prev = head, curr = head.next, newNode;
  123.         newNode = new Node<T>(item);  
  124.         if (!isEmpty()) {  
  125.             while ((curr != null) && (!appointedItem.equals(curr.data))) {  
  126.                 prev = curr;
  127.                 curr = curr.next;
  128.             }
  129.             newNode.next = curr;
  130.             prev.next = newNode;
  131.             return true;  
  132.         }
  133.         return false;   
  134.     }
  136.     public void remove(T item) {  
  137.         Node<T> curr = head, prev = null;  
  138.         boolean found = false;  
  139.         while (curr != null && !found) {  
  140.             if (item.equals(curr.data)) {  
  141.                 if (prev == null)  
  142.                     removeFromHead();
  143.                 else  
  144.                     prev.next = curr.next;
  145.                 found = true;  
  146.             } else {  
  147.                 prev = curr;
  148.                 curr = curr.next;
  149.             }
  150.         }
  151.     }
  154.     public int indexOf(T item) {  
  155.         int index = 0;  
  156.         Node<T> p;
  157.         for (p = head; p != null; p = p.next) {  
  158.             if (item.equals(p.data))  
  159.                 return index;  
  160.             index++;
  162.         }
  163.         return –1;  
  164.     }
  166.     /** 
  167.      * judge the list contains one data 
  168.      */  
  169.     public boolean contains(T item) {  
  170.         return indexOf(item) != –1;  
  171.     }
  172. }

单链表*好玩儿的也就是增加和删除节点，下面的两个图分别是用图来表示单链表增、删节点示意，看着图学习，理解起来更加容易！

%title插图%num

接下来的队列和栈，我们分别用不同的结构来实现，队列用数组，栈用单列表，读者朋友对此感兴趣，可以分别再用不同的方法实现。

四、队列
队列是一个常用的数据结构，是一种先进先出（First In First Out, FIFO）的结构，也就是说只能在表头进行删除，在表尾进行添加，下面我们实现一个简单的队列。

 

  1. package com.xtfggef.algo.queue;  
  3. import java.util.Arrays;  
  5. public class Queue<T> {  
  7.     private int DEFAULT_SIZE = 10;  
  9.     private int capacity;  
  11.     private Object[] elementData;  
  13.     private int front = 0;  
  14.     private int rear = 0;  
  16.     public Queue()  
  17.     {
  18.         capacity = DEFAULT_SIZE;
  19.         elementData = new Object[capacity];  
  20.     }
  22.     public Queue(T element)  
  23.     {
  24.         this();  
  25.         elementData[0] = element;  
  26.         rear++;
  27.     }
  29.     public Queue(T element , int initSize)  
  30.     {
  31.         this.capacity = initSize;  
  32.         elementData = new Object[capacity];  
  33.         elementData[0] = element;  
  34.         rear++;
  35.     }
  37.     public int size()  
  38.     {
  39.         return rear – front;  
  40.     }
  42.     public void add(T element)  
  43.     {
  44.         if (rear > capacity – 1)  
  45.         {
  46.             throw new IndexOutOfBoundsException(“the queue is full!”);  
  47.         }
  48.         elementData[rear++] = element;
  49.     }
  51.     public T remove()  
  52.     {
  53.         if (empty())  
  54.         {
  55.             throw new IndexOutOfBoundsException(“queue is empty”);  
  56.         }
  58.         @SuppressWarnings(“unchecked”)  
  59.         T oldValue = (T)elementData[front];
  61.         elementData[front++] = null;   
  62.         return oldValue;  
  63.     }
  65.     @SuppressWarnings(“unchecked”)  
  66.     public T element()    
  67.     {
  68.         if (empty())    
  69.         {
  70.             throw new IndexOutOfBoundsException(“queue is empty”);    
  71.         }
  72.         return (T)elementData[front];    
  73.     }
  75.     public boolean empty()  
  76.     {
  77.         return rear == front;  
  78.     }
  80.     public void clear()  
  81.     {
  83.         Arrays.fill(elementData , null);  
  84.         front = 0;  
  85.         rear = 0;  
  86.     }
  87.     public String toString()  
  88.     {
  89.         if (empty())  
  90.         {
  91.             return “[]”;  
  92.         }
  93.         else  
  94.         {
  95.             StringBuilder sb = new StringBuilder(“[“);  
  96.             for (int i = front  ; i < rear ; i++ )  
  97.             {
  98.                 sb.append(elementData[i].toString() + “, “);  
  99.             }
  100.             int len = sb.length();  
  101.             return sb.delete(len – 2 , len).append(“]”).toString();  
  102.         }
  103.     }
  104.     public static void main(String[] args){  
  105.         Queue<String> queue = new Queue<String>(“ABC”, 20);  
  106.         queue.add(“DEF”);  
  107.         queue.add(“egg”);  
  108.         System.out.println(queue.empty());
  109.         System.out.println(queue.size());
  110.         System.out.println(queue.element());
  111.         queue.clear();
  112.         System.out.println(queue.empty());
  113.         System.out.println(queue.size());
  114.     }
  115. }

队列只能在表头进行删除，在表尾进行增加，这种结构的特点，适用于排队系统。

五、栈

栈是一种后进先出（Last In First Out，LIFO）的数据结构，我们采用单链表实现一个栈。

  1. package com.xtfggef.algo.stack;  
  3. import com.xtfggef.algo.linkedlist.LinkedList;  
  5. public class Stack<T> {  
  7.     static class Node<T> {  
  8.         T data;
  9.         Node<T> next;
  11.         Node(T data, Node<T> next) {
  12.             this.data = data;  
  13.             this.next = next;  
  14.         }
  16.         Node(T data) {
  17.             this(data, null);  
  18.         }
  19.     }
  21.     @SuppressWarnings(“rawtypes”)  
  22.     static LinkedList list = new LinkedList();  
  24.     @SuppressWarnings(“unchecked”)  
  25.     public T push(T item) {  
  26.         list.addFromHead(item);
  27.         return item;  
  28.     }
  30.     public void pop() {  
  31.         list.removeFromHead();
  32.     }
  34.     public boolean empty() {  
  35.         return list.isEmpty();  
  36.     }
  38.     public int search(T t) {  
  39.         return list.indexOf(t);  
  40.     }
  42.     public static void main(String[] args) {  
  43.         Stack<String> stack = new Stack<String>();  
  44.         System.out.println(stack.empty());
  45.         stack.push(“abc”);  
  46.         stack.push(“def”);  
  47.         stack.push(“egg”);  
  48.         stack.pop();
  49.         System.out.println(stack.search(“def”));  
  50.     }
  51. }

本章的内容都是很基础的，重在让读者朋友们理解数据结构的概念，下章开始，我们会介绍树、二叉树等Java中的实现，敬请读者朋友们持续关注！