2.3 线性结构

  前面在介绍线性结构的时候已经提到，常用的线性结构有线性表、栈和队列等。本节将简要介绍线性表、栈和队列的概念，并且采用面向接口编程的方式，使用Java语言确定这些逻辑结构的基本操作接口。

2.3.1 线性表的存储结构

  线性表的结构特点主要表现在两个方面：一是均匀性，虽然不同数据表的数据元素可以是各式各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。二是有序性，各数据元素在线性表中按序排列，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个外，其他元素前面均只有一个数据元素（直接前驱）且后面均只有一个数据元素（直接后继）。

  在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。栈、队列是线性表的特殊情况，是受限的线性结构，只是在数据结构的操作上有区别，在存储结构方面和线性表一样。

  线性表的顺序存储结构如图2.8所示。

2.3 线性结构 - 图1


图2.8 线性表的顺序存储结构

  线性表的链式存储有三种形式：单链表、循环链表和双向链表。

  • 单链表

  在单链表中，每个节点都包含指向下一个节点的指针，最后一个节点的指针为空，以标记是最后一个节点。之所以称为单链表是因为每个节点只存在一个节点指针，所以只能依次顺序访问下一个节点，访问完某节点之后再想往回查找是不可以的。为了记住单链表的第一个位置，可以定义一个头指针。单链表的链式存储结构如图2.7所示。

  • 循环链表

  在单链表的基础上，可以让最后一个节点的指针指向第一个节点，这样循环起来形成的链表即为循环链表。循环列表可以顺序访问下一个节点，访问完某节点之后可以通过下一个循环再次访问到该节点。为了记住单链表的第一个位置和最后一个位置，可以定义一个头指针和一个尾指针。循环链表的链式存储结构如图2.9所示。

2.3 线性结构 - 图2


图2.9 循环链表

  • 双向链表

  双向链表比单链表多出了一个节点指针，用来指向前一个节点的数据，这样做的好处是避免了寻找前面节点时发生的不便之举。双向链表的链式存储结构如图2.10所示。

2.3 线性结构 - 图3


图2.10 双向链表

2.3.2 线性表

  通过对线性结构的分析，可得到如下结论：对线性结构的主要操作有查找线性结构中某个信息、修改线性结构中某个信息、在固定的位置插入和删除相应的信息等，即查询、插入、删除、修改等相关操作。接下来以面向接口编程的方式，定义一个线性表接口，该接口具有如下基本操作。

  （1）插入数据元素。

  （2）删除数据元素。

  （3）替换数据元素。

  （4）获取数据元素。

  （5）获取线性表中数据元素个数。

  （6）判断线性表是否为空。

  下面是线性表接口的代码：

  1. public interface List {
  3.     //在指定下标位置插入数据元素
  5.     public void insert(int i, Object obj) throws Exception;
  7.     //删除指定下标位置的数据元素
  9.     public Object delete(int i) throws Exception;
  11.     //替换指定下标位置的数据元素
  13.     public void update(int i, Object obj) throws Exception;
  15.     //获取指定下标位置的数据元素
  17.     public Object getData(int i) throws Exception;
  19.     //获取线性表数据元素个数
  21.     public int size();
  23.     //判断线性表是否为空
  25.     public boolean isEmpty();
  27. }

  接下来用顺序存储结构的数组，来存储线性表的逻辑结构，同时实现上面定义的List接口。请认真阅读该段代码，细节部分已通过注释加以描述，具体代码如下：

  1. public class SeqList implements List{
  3.     final int defaultSize = 10;               //默认线性表长度       
  5.     int maxSize;                                    //线性表长度
  7.     int size;                                           //线性表中现有元素个数
  9.     Object[] listArray;                          //用对象数组存储线性表
  11.     //无参构造方法
  13.     SeqList(){
  15.         initiate(defaultSize);
  17.     }
  19.     //带线性表长度的构造方法
  21.     SeqList(int size){
  23.         initiate(size);
  25.     }
  27.     //初始化方法，设置线性表长度、现有元素个数和初始化对象数组（用线性表长度）
  29.     public void initiate(int sz){
  31.         maxSize = sz;
  33.         size = 0;
  35.         listArray = new Object[sz];
  37.     }
  39.     //实现在指定下标位置插入数据元素
  41.     public void insert(int i,Object obj) throws Exception{                 
  43.         if (size == maxSize){
  45.             throw new Exception("线性表已满，无法插入！");
  47.         }
  49.         //只允许在现有线性表数据元素之前或之后插入，不允许隔着一个空位置之后插入数据元素
  51.         if (i > size){
  53.             throw new Exception("插入下标位置错误！");
  55.         }
  57.         //将插入位置后的数据元素全部后移   
  59.         for(int j = size; j > i; j--){
  61.             listArray[j] = listArray[j-1];
  63.         }
  65.         //插入数据元素，并增加线性表中现有元素个数
  67.         listArray[i] = obj;
  69.         size++; 
  71.     }
  73.     //实现删除指定下标位置的数据元素
  75.     public Object delete(int i) throws Exception{            
  77.         if(size == 0){
  79.             throw new Exception("线性表已空，无法删除！");
  81.         }
  83.         if (i > size-1){
  85.             throw new Exception("删除下标位置错误！");
  87.         }
  89.         //获得被删除的数据元素
  91.         Object it = listArray[i];
  93.         //将删除位置后的数据元素全部前移
  95.         for(int j = i; j < size-1; j++){
  97.             listArray[j] = listArray[j+1]; 
  99.         }
  101.         //返回被删除数据元素，并减少线性表中现有元素个数        
  103.         size--;
  105.         return it;     
  107.     }
  109.     //实现替换指定下标位置的数据元素
  111.     public void update(int i, Object obj) throws Exception{              
  113.         if(size == 0){
  115.             throw new Exception("线性表已空，无法替换！");
  117.         }
  119.         if (i > size-1){
  121.             throw new Exception("替换下标位置错误！");
  123.         }
  125.         //替换指定下标的数据元素
  127.         listArray[i] = obj;         
  129.     }
  131.     //实现获取指定下标位置的数据元素
  133.     public Object getData(int i) throws Exception{                  
  135.         if(size == 0){
  137.             throw new Exception("线性表已空，无法获取！");
  139.         }
  141.         if(i >= size){
  143.             throw new Exception("获得下标位置错误！");
  145.         }
  147.         return listArray[i];
  149.     }
  151.     //实现获取线性表数据元素个数
  153.     public int size(){
  155.         return size;
  157.     }
  159.     //实现判断线性表是否为空
  161.     public boolean isEmpty(){
  163.         return size == 0;
  165.     }
  167. }

  上述代码中，关于插入位置i和线性表中现有元素个数size的比较非常细致，也正确体现了线性表的特性，需要认真理解。例如在实现在指定下标位置插入数据元素的代码中，if(i > size){…}这行判断语句，可以理解为如果线性表中现有3个数据元素，即size值为3，则只允许在下标为0、1、2、3这四个位置（其中下标为3的这个位置是第一个空着的位置）插入数据元素，不允许让下标为3的位置空着，在下标大于3的位置插入数据元素。

2.3.3 栈

  栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读取数据的时候是从栈顶开始弹出数据（最后一个进入的数据被第一个读出来）。

  仍然以面向接口编程的方式，定义一个栈接口，该接口具有如下基本操作。

  （1）把数据元素压入栈—进栈。

  （2）获取并删除栈顶数据元素—退栈。

  （3）获取但不删除栈顶数据元素。

  （4）判断栈是否为空。

  下面是栈接口的代码：

  1. public interface Stack{
  3.     //把数据元素压入栈—进栈
  5.     public void push(Object obj) throws Exception;
  7.     //获取并删除栈顶数据元素—退栈
  9.     public Object pop() throws Exception;
  11.     //获取但不删除栈顶数据元素
  13.     public Object getTop() throws Exception;
  15.     //判断栈是否为空
  17.     public boolean notEmpty();
  19. }

  接下来仍然用顺序存储结构的数组来存储栈的逻辑结构，同时实现上面定义的Stack接口，具体代码如下：

  1. public class SeqStack implements Stack{
  3.     final int defaultSize = 10;
  5.     int top;//标记栈内元素个数，即栈顶元素
  7.     Object[] stack;
  9.     int maxStackSize;
  11.     public SeqStack(){
  13.         initiate(defaultSize);
  15.     }       
  17.     public SeqStack(int sz){
  19.         initiate(sz);
  21.     }       
  23.     private void initiate(int sz){
  25.         maxStackSize = sz;
  27.         top = 0;
  29.         stack = new Object[sz];
  31.     }
  33.     //实现把数据元素压入栈—进栈       
  35.     public void push(Object obj) throws Exception{
  37.         if(top == maxStackSize){
  39.             throw new Exception("堆栈已满！");
  41.         }
  43.         //进栈，栈顶标记加1
  45.         stack[top] = obj;
  47.         top++;
  49.     }
  51.     //实现获取并删除栈顶数据元素—退栈
  53.     public Object pop() throws Exception{
  55.         if(top == 0){
  57.             throw new Exception("堆栈已空！");
  59.         }
  61.         //返回退栈数据元素，栈顶标记减1实现删除（实际并未删除）
  63.         top--;
  65.         return stack[top];
  67.     }
  69.     //实现获取但不删除栈顶数据元素
  71.     public Object getTop() throws Exception{
  73.         if(top == 0){
  75.             throw new Exception("堆栈已空！");
  77.         }
  79.         return stack[top - 1];
  81.     }
  83.     //实现判断栈是否为空
  85.     public boolean notEmpty(){
  87.         return (top > 0);
  89.     }
  91. }

  该段代码比较简单，唯一需要注意的是在实现获取并删除栈顶数据元素—退栈的操作时，并没有真正删除该数据元素，而是通过top栈顶标记减1实现删除的。

  接下来的程序演示了如何使用栈这样的数据结构，具体代码如下：

  1. public class TestSeqStack{    
  3.     public static void main(String[] args){
  5.         //创建一个空栈
  7.         SeqStack myStack = new SeqStack();              
  9.         int test[] = {1, 3, 5, 7, 9};
  11.         int n = 5;             
  13.         try{
  15.             //依次将长度为5的整型数组中的数转换为Integer类型入栈
  17.             for(int i = 0; i < n; i++){
  19.                 myStack.push(new Integer(test[i]));
  21.             }
  23.             //获取栈顶元素
  25.             System.out.println("当前栈顶元素为：" + myStack.getTop());                    
  27.             System.out.println("元素出栈序列为：");
  29.             while(myStack.notEmpty()){                                      //判断栈是否为空
  31.                 System.out.println(myStack.pop());                  //逐个出栈
  33.             }
  35.         }catch(Exception e){
  37.             System.out.println(e.getMessage());
  39.         }
  41.     }
  43. }

  编译、运行程序，程序运行结果如图2.11所示。

2.3 线性结构 - 图4


图2.11 栈结构的使用

2.3.4 队列

  队列也是一种特殊的线性结构，它只允许在该结构的前端进行删除操作，在后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

  在队列这种数据结构中，最先插入的元素将是最先被删除的元素，反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”的线性结构。

  接下来定义一个队列接口，该接口具有如下基本操作。

  （1）把数据元素插入队列尾部—入队。

  （2）获取并删除队列头部数据元素—出队。

  （3）获取但不删除队列头部数据元素。

  （4）判断队列是否为空。

  下面是队列接口的代码：

  1. public interface Queue{
  3.     //把数据元素插入队列尾部—入队
  5.     public void EnQueue(Object obj) throws Exception;
  7.     //获取并删除队列头部数据元素—出队
  9.     public Object DeQueue() throws Exception;
  11.     //获取但不删除队列头部数据元素
  13.     public Object QueueFront() throws Exception;
  15.     //判断队列是否为空
  17.     public boolean notEmpty();
  19. }

  关于如何使用数组来存储队列的逻辑结构，同时实现上面定义的Queue接口，将是留给大家的上机任务。