1. 绪论

2. 线性表

​ 线性表是一种最常用、最简单，也是一种最基本的数据结构，它是学习其他数据结构的基础。

线性表在计算机中可以用$\begin{cases}顺序存储 \\ 链式存储\end{cases}$两种存储结构来表示，其中，顺序存储的线性表成为顺序表，链式存储的线性表成为链表，链表又分为：$\begin{cases} 单链表 \\ 双向链表 \\ 循环链表\end{cases}$。

特点：

  • 对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型

  • 数据元素之间具有一种线性的或“一对一”的逻辑关系：开始结点没有前驱，末尾结点没有后继，除开始和末尾结点外，其余数据元素有且仅有一个前驱和一个后继

  • 几个基本操作：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

    ```clear()```:将已存在的线性表置为空表

    ```isEmpty()```:判空

    ```length()```:求线性表长度，即，元素个数

    ```get(i)```:读取线性表中第i个数据元素的值。$0 \leqslant i \leqslant length-1$

    ```insert(i,x)```:在线性表的第i个数据元素之前插入一个值为x的数据元素。

    ```remove(i)```:删除并返回线性表中第i个数据元素

     ```indexOf(x)```:返回线性表中首次出现指定数据元素的位序号，若不包含次数据元素，则返回-1

     ```desplay(0)```:输出线性表中的各个数据元素的值

2.1 顺序表

定义：

顺序表是用一组地址连续的存储单元依次存放线性表中各个数据元素的存储结构。

特点：

  • 在线性表中逻辑相邻的数据元素，在物理存储元素上也是相邻的
  • 存储密度高，但需要预先分配“足够应用的存储空间，这可能将会造成存储空间的浪费，其中，$存储密度=\frac{数据元素本身值所需的存储空间}{该数据元素实际所占用的空间}$
  • 便于随机存取
  • 不便于插入和删除操作没这事因为在顺序表上进行插入和删除操作会引起大量数据元素的移动

顺序表的局限性：

  • 若要为顺序表扩充存储空间，则需要重新创建一个地址连续的更大存储空间，并把原有的数据元素都复制到新的存储空间中
  • 因为顺序表存储要求逻辑上相邻的数据元素，在物理存储位置上也是相邻的，这就使得增删数据元素则会引起平均约一半的数据元素的移动

总结——查询快、增删慢！

顺序表代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package cn.dataStructure.SqList;

public class SqList {
    private Object[] listElem;
    private int curlen;

    //构造函数，构造一个存储空间容量为maxSize的线性表
    public SqList(int maxSize){
        curlen = 0; //置顺序表的当前长度为0
        listElem = new Object[maxSize];//给顺序表分配maxSize个存储单元
    }

    //置空表
    public void clear(){
        curlen = 0 ;  //置顺序表的当前长度为0
    }

    //判空
    public boolean isEmpty(){
        return curlen == 0;
    }

    //求线性表中数据元素个数，返回值
    public int length(){
        return curlen;
    }

    //读取到线性表第i个元素并返回其值
    public Object get(int i) throws Exception{
        if(i<0 || i> curlen-1)
            throw new Exception("第" + i + "个元素不存在");
        return listElem[i];
    }

    //在第i个元素之前插入一个值为x的数据元素
    public void insert(int i,Object x) throws Exception{
        if(curlen == listElem.length) //判断顺序表是否已经满
            throw new Exception("顺序表已满");//抛出异常
        if(i<0 || i>curlen)
            throw new Exception("插入位置不合法");
        for (int j = curlen; j < i ; j--)  //插入后的元素向后移一个存储单位
            listElem[j] = listElem[j-1];
        listElem[i] = x;
        curlen++;

    }

    //删除并返回线性表中第i个数据元素
    public void remove(int i) throws Exception{
        if(i<0 || i>curlen -1)
            throw new Exception("删除位置不合法");
        for (int j = i; j < curlen -1 ; j++)
            listElem[j] = listElem[j+1];//删除元素后的元素向前移一个单位
        curlen--;
    }

    //返回线性表中首次出现指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1
    public int indexOf(Object x){
        int j =0;
        while(j<curlen && !listElem[j].equals(x))
            j++;
        if(j<curlen)
            return j;
        else
            return -1;
    }

    //输出线性表中的数据元素
    public void  display(){
        for (int j = 0; j < curlen; j++) {
            System.out.println(listElem[j] + "");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package cn.dataStructure.SqList;

public class SqListTest {
    public static void main(String[] args) throws Exception{
        SqList L = new SqList(10);
        L.insert(0,"a");
        L.insert(1,"z");
        L.insert(2,"d");
        L.insert(3,"z");
        System.out.println("此顺序表为：");
        L.display();

        int order = L.indexOf("z");
        if(order !=-1)
            System.out.println("顺序表中第一次出现的值为'z'的数据元素位置为："+order);
        else
            System.out.println("此顺序表中不包含值为z的属于元素");
    }

}

2.2 链表

定义：

顺序表适合表示静态线性表，一旦形成以后，就很少进行插入和删除操作，对于需要频繁插入和删除的动态线性表，通常采用链式存储结构。

特点：

  • 链式结构不要求逻辑上相邻的数据元素在物理上也相邻，它是用一组地址任意的存储单元来存放数据元素的值，故它没有顺序结构某些操作上的局限性，但却失去了随机存取的特点，在链式结构上只能进行顺序存取

单链表代码实现：

Node类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package cn.dataStructure.LinkList;

public class Node{
    //存储元素
    public Object data;   //存放结点值
    public Node next;    //后继结点的引用

    //无参数时的构造函数
    public Node() {
        this(null,null);
    }

    //有一个参数时的构造函数
    public Node(Object data) {
        this.data = data;
    }

    //有两个参数时的构造函数
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}

LinkList类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package cn.dataStructure.LinkList;

import java.util.Scanner;
public class LinkList {
    public Node head;  //单链表的头指针

    //无参构造
    public LinkList() {
        head = new Node();//初始化头结点
    }
    //构造一个长度为n的单链表
    public LinkList(int n, boolean Order)throws Exception{
        this(); //初始化头结点，相当于无参构造
        if(Order)
            create1(n); //用尾插法顺序建立单链表
        else
            create2(n); //用头插法逆位序建立单链表
    }

    //用尾插法顺序建立单链表，其中n为单链表的结点个数  先要编写insert
    public void create1(int n) throws Exception{
        Scanner sc = new Scanner(System.in);//构造输入对象
        for(int j = 0; j<n; j++)
            insert(length(),sc.next());
    }
    //用头插法逆位序建立单链表，其中n为单链表的结点个数
    public void create2(int n) throws Exception{
        Scanner sc = new Scanner(System.in);//构造输入对象
        for(int j = 0; j<n; j++)
            insert(0,sc.next());
    }

    //将一个已经存在的带头结点单链表置成空表
    public void clear(){
        head.data = null;
        head.next = null;
    }

    //判断带头结点的单链表是否为空
    public boolean isEmpty(){
        return head.next == null;
    }

    //求带头结点的单链表的长度
    public int length(){
        //新建一个p指针指向head
        Node p = head;
        int length = 0;
        while(p != null){
            p = p.next;
            ++ length;
        }
        return length-1;
    }

    //求取带头结点的单链表中的第i个结点
    public Object get(int i) throws Exception{
        Node p = head; //定义一个p指针指向head，利用其遍历
        int j = -1;
        while(p!=null && j<i){
            p = p.next;
            ++j;
        }
        //判断是否合法
        if(i<0 || p == null){
            throw new Exception("get的第" + i + "个元素不存在");
        }
        return p.data;
    }

    //在带头结点的单链表中的第i个结点之前插入一个值为x的新结点
    public void insert(int i, Object x) throws Exception{
        Node p = head; //定义一个p指针先指向head，利用它遍历到i-1处
        int j = -1;
        while(p != null && j< i-1){
            p = p.next;
            ++j;
        }
//        判断i是否合法
        if(j>i-1 || p == null)
            throw new Exception("插入位置不合法hh");

        Node s = new Node(x);
        s.next = p.next;
        p.next = s;
    }

    //删除带头结点的单链表中的第i个结点
    public void remove(int i) throws Exception{
        Node p = head;
        int j = -1;
        while(p != null && j <i){
            p = p.next;
            ++j;
        }

        //判断i是否合法
        if(i<0 || p ==null){
            throw new Exception("删除的第" + i + "个元素不存在");
        }

    }

    //在带头结点的单链表中查找值为x的结点，返回位置
    public int indexOf(Object x) throws Exception{
        Node p = head;
        int j = -1;
        while(p!=null && !p.data.equals(x)){
            p = p.next;
            ++j;
        }
        //判断是否含有x这个值
        if(p==null){
            throw new Exception("不存在值为" + x + "的结点");
        }
        else
            return j;
    }

    //输出单链表中的所有结点
    public void display(){
        Node node = head.next;  //取出带头结点的单链表中的首结点 node作为指针来遍历
        while(node!=null){
            System.out.println(node.data + "");
            node = node.next;
        }
        System.out.println();  //换行
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package cn.dataStructure.LinkList;

public class LinkListTest {
    public static void main(String[] args) throws Exception{
        LinkList L = new LinkList();
        L.display();
        L.insert(0,0);
        L.insert(1,1);
        L.display();
        System.out.println("链表长度为"+ L.length());
        LinkList L2 = new LinkList(3,false);//头插法
        L2.display();
        System.out.println("链表长度为"+ L2.length());
        LinkList L3 = new LinkList(3,true);//尾插法
        L3.display();
        System.out.println("链表长度为"+ L3.length());
    }
}

输出结果：

2.3 链表VS顺序表

  • 与顺序表相比较,链表比灵活，它既不要求在预先分配的一块连续的存储空间中存储
    线性表的所有数据元素,也不要求按其逻辑顺序来分配存储单元,可根据需要进行存储空间
    的动态分配!因此,当线性表的长度变化较大或长度难以估计时,用链表。但在线性表的
    长度基本可预计且变化较小的情况下,宜用顺序表,因为链表的存储密度较顺序表的低,且
    顺序表具有随机存取的优势!
  • 在顺序表中按序号访问第i个数据元素时的时间复杂度为O(1),而在链表中做同样操
    作的时间复杂度为O(n)所以若要经常对线性表按序号访问数据元素时,顺序表要优先
    链表;但在顺序表上做插入和删除操作时,需要平均移动一半的数据元素,而在链表上做插
    入和删除操作,不需要移动任何数据元素,虽然也要查找插入或删除数据元素的位置,但由
    于主要是比较操作,所以从这个角度考虑,链表要优先于顺序表
  • 总之,链表比较灵活,**插入和删除操作的效率较高,但链表的空间利用率较低,适合于实
    现动态的线性表;顺序表实现比较简单,因为任何高级程序语言中都有数组类型,并且空间
    利用率也较高,可高效地进行随机存取,但顺序表不易扩充,插入和删除操作的效率较低,适
    合于实现相对“稳定”的静态线性表。两种存储结构各有所长,各种实现方法也不是一成不
    变的。在实际应用时,必须以这些基本方法和思想为基础,抓住两者各自的特点并结合具体
    情况,加以创造性地灵活应用和改造,用最合适的方法来解决问题。

3.栈与队列

定义：

栈和队列可被看成是两种操作受限的特殊线性表，其特殊性体现在它们的插入和删除操作都是控制在线性表的一端或两端进行。

3.1 栈

栈是一种特殊的线性表，栈中的元素以及数据元素间的逻辑关系和线性表相同，区别在于：

  • 线性表的插入和删除操作可以在表的任意位置进行，而栈只允许在表的尾端进行

特点：

  • 先进后出(First In Last Out)

  • 几个基本操作：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

    ```clear()```：置空

    ```isEmpty()```：判空

    ```length()```：返回栈中元素个数

    ```peek()```：读取栈项元素并返回其值，若栈为空，则返回null

    ```push()```：入栈——将数据元素x压入栈顶

    ```pop()```：出栈——删除并返回栈顶元素

3.1.1 顺序栈

类的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package cn.dataStructure.SqStack;

public class SqStack {
    private Object[] stackElem;
    private int top;//在非空栈中，top始终指向栈顶元素的下一个存储位置，栈为空时，top=0

    //构造函数，构造一个存储空间容量为maxSize的空站

    public SqStack(int maxSize) {
        top = 0;
        stackElem = new Object[maxSize];//为栈分配maxSize个存储单元
    }
    //栈置空
    public void clear(){
        top = 0;
    }

    //判空
    public boolean isEmpty(){
        return top == 0;
    }

    //求栈中数据元素个数
    public int length(){
        return top;
    }

    //取栈顶元素
    public Object peek(){
        if(!isEmpty())
            return stackElem[top-1];
        else
            return null;
    }

    //入栈
    public void push(Object x) throws Exception{
        if(top == stackElem.length)//这里判断一下Object数组的长度和top是否相等，与sqStack的length()区别开
            throw new Exception("栈已满");//跑出异常
        else
            stackElem[top++] = x;
    }
    //出栈
    public Object pop() {
        if (isEmpty())
            return null;
        else
            return stackElem[--top];
    }
    //输出栈中所有数据元素，从栈顶元素到栈底
    public void display() {
        for (int i = top-1; i >=0 ; i--) {
            System.out.print(stackElem[i].toString() + " ");
        }
    }
}

测试类：

1
2
3
4
5
6
7
8
9
10
11
12
package cn.dataStructure.SqStack;

public class sqStackTest {
    public static void main(String[] args) throws Exception{
        SqStack sqStack = new SqStack(10);
        //循环压入栈
        for (int i = 0; i < 10; i++) {
            sqStack.push(i);
        }
        sqStack.display();
    }
}

3.1.2 链栈

定义结点类，与之前一致：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package cn.dataStructure.LinkStack;

public class Node{
    //存储元素
    public Object data;   //存放结点值
    public Node next;    //后继结点的引用

    //无参数时的构造函数
    public Node() {
        this(null,null);
    }

    //有一个参数时的构造函数
    public Node(Object data) {
        this.data = data;
}

    //有两个参数时的构造函数
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}

定义链栈类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package cn.dataStructure.LinkStack;

public class LinkStack {
    private Node top; //栈顶元素的引用
    //置空
    public void clear() {
        top = null;
    }
    //判空
    public boolean isEmpty() {
        return top == null;
    }
    //求长度
    public int length() {
        Node p = top;
        int length = 0;
        while(p!=null) {
            p = p.next;
            length++;
        }
        return length;
    }

    //取栈顶元素并返回值
    public Object peek() {
        if (!isEmpty())
            return top.data;
        else
            return null;
    }

    //入栈
    public void push(Object x) {
        Node p = new Node(x);
        p.next = top;
        top = p;
    }

    //出栈
    public Object pop() {
        if (isEmpty()) {
            return null;
        }
        else {
            Node p = top; //p指向被删结点，引用p是因为要返回被删结点值
            top = top.next;
            return p.data;
        }
    }
    //输出
    public  void display() {
        Node p = top;
        while (p!=null) {
            System.out.print(p.data.toString() + " ");
            p = p.next;
        }
    }
}

测试类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package cn.dataStructure.LinkStack;

public class LinkStackTest {
    public static void main(String[] args) {
        LinkStack LS = new LinkStack();
        //批量压入栈
        for (int i = 0; i < 10; i++) {
            LS.push(i);
        }
        //输出
        LS.display();
        System.out.println("\n" + "被删除元素为：" + LS.pop());
        LS.display();
    }

}

3.2 队列

定义：

队列是另一种特殊的线性表，它的特殊性体现在队列只允许在表尾插入数据元素，在表头删除数据元素，所以队列也是一种操作受限的特殊线性表

特点：

  • 先进先出

  • 几个基本操作：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    ```isEmpty()```：置空

    ```length()```：求取队列数据元素个数

    ```peek()```：读取队首元素并返回其值。

    ```offer()```：入队操作，将数据元素x插入到队列中使其成为新的队尾元素。

    ```poll()```：出队操作，删除队首元素并返回其值，若队列为空，则返回null。

    ```java
    public interface IQueue {
      public void clear();
      public boolean isEmpty();
      public int length();
      public Object peek();
      public void offer(Object x) throws Exception;
      public Object poll()
    }

3.2.1 顺序队列

​ 与顺序栈类似，在顺序队列的存储结构中，需要分配一块地址连续的存储区域来一次存放队列中从队首到队尾的所有元素。这样也可以用一维数组来表示，假设数组名为queueElem，数组最大容量为maxSize，由于队列的入队操作只能在当前队列的队尾进行，而出队操作只能在当前队列的队首进行，所以需加上变量front和rear来分别指示队首队尾元素在数组中的位置，其初始值都为0，在非空队列中，front指向队首元素，rear指向队尾元素的下一个存储位置

假溢出：

​ 从图3.16(d)可以看出,若此时还需要将数据元素H入队,H应该存放于rear=6的位
置处,顺序队列则会因数组下标越界而引起“溢出”,但此时顺序队列的首部还空出了两个数
据元素的存储空间。因此,这时的“溢出”并不是由于数组空间不够而产生的溢出。这种因
顺序队列的多次人队和出队操作后出现有存储空间,但不能进行人队操作的溢出现象称为
”假溢出”。
​ 要解决“假溢出”问题,最好的办法就是把顺序队列所使用的存储空间看成是一个逻辑
上首尾相连的循环队列。当rear或 front到达 maxSize-1后,再加1就自动到0。这种转
换可利用Java语言中对整型数据求模(或取余)运算来实现,即令rear=(rear+1)%
maxSize。显然,当rear= maxSize-1时,rear加1后,rear的值就为0。这样,就不会出现
顺序队列数组的头部有空的存储空间,而队尾却因数组下标越界而引起的假溢出现象。

循环顺序队列类：

图中会发现一个问题：即循环顺序队列的判空和判满条件都是front==rear

解决循环顺序队列的队空和队满的判断问题常采用以下3种方法：

  1. 少用一个存储单元

  1. 设置一个标志变量

    ​ 在程序设计过程中引进一个标志变量fag,其初始值置为0,每当入队操作成功后就置
    flag=1;每当出队操作成功后就置fag=0,则此时队空的判断条件为: front==rear&& flag==0,而队满的判断条件为:front==rear&&flag==1。

  2. 设置一个计数器

    ​ 在程序设计过程中引进一个计数变量num,其初始值置为0,每当入队操作成功后就将
    计数变量num的值加1;每当出队操作成功后就将计数变量num的值减1,则此时队空的
    判断条件为:num==0,而队满的判断条件为:num>0&&front==rear

循环队列实现：

接口

1
2
3
4
5
6
7
8
9
10
package cn.dataStructure.SqQueue;

public interface IQueue {
    public void clear();
    public boolean isEmpty();
    public int length();
    public Object peek();
    public void offer(Object x) throws Exception;
    public Object poll();
}

实现类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package cn.dataStructure.SqQueue;

public class CircleSqQueueimpl implements IQueue {
    private Object[] queueElem;
    private int front,rear;

    //构造函数
    public CircleSqQueueimpl(int maxSize) {
        front = rear = 0; //队首、队尾初始化为0
        queueElem = new Object[maxSize];//为队列分配maxSize个存储单元
    }

    @Override
    public void clear() {
        front = rear = 0;
    }

    @Override
    public boolean isEmpty() {
        return front == rear; //判空采用第一种方式
    }

    @Override
    public int length() {
        return (rear - front + queueElem.length) % queueElem.length;
    }

    @Override
    public Object peek() {
        if (front ==rear)
            return null;
        else
            return queueElem[front];
    }


    @Override
    public void offer(Object x) throws Exception {
        if ((rear+1) % queueElem.length == front) {
            throw new Exception("队列已满");
        }
        else {
            queueElem[rear] = x;
            rear = (rear+1) % queueElem.length;//以免假溢出
        }
    }

    @Override
    public Object poll() {
        if (front == rear) {
            return null;
        }
        else {
            Object t = queueElem[front];
            front = (front + 1) % queueElem.length;
            return t;
        }
    }

    public void display() {
        if(!isEmpty()) {
            for (int i = front; i != rear; i= (i+1)%queueElem.length) {
                System.out.print(queueElem[i].toString() + " ");
            }
        }else {
            System.out.println("此队列为空");
        }
    }
}

测试类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package cn.dataStructure.SqQueue;

public class CircleSqQueueTest {
    public static void main(String[] args) throws Exception{
        CircleSqQueueimpl circleSQ= new CircleSqQueueimpl(6);
        System.out.println("长度为：" + circleSQ.length() + "判空" + circleSQ.isEmpty());
        circleSQ.display();
        //批量导入数据元素
        for (int i = 0; i < 5; i++) {
            circleSQ.offer(i);
        }
        circleSQ.display();
    }
}