线性表理解为将数据结点用一根“线”连接起来存储在物理空间，线性表的数据元素一般具有相同的数据类型。大部分线性表中除了第一个元素（没有前驱）和最后一个元素（没有后继）其他元素都有前驱和后继（也就是各元素之间是一对一的关系）。

  • 顺序存储结构（顺序表）

顺序存储结构就是数据是用一块完整的物理空间来连续存储数据，一般它的大小是固定的。
优点：物理空间利用率高，增查效率高。
缺点：插入和删除效率低，每次都需要移动目标元素后面的所有数据元素，由于它的length是提前分配固定好不能扩容，会发生存储溢出。

  • 链式存储结构

    链式存储结构中数据元素的存储方式在物理空间中是随机的，数据结点氛围数据域和指针域，数据域存储数据元素，指针域来关联起来数据结点形成链。链式存储结构一般有单链表、双向链表和循环链表。
    1. 单链表

题目：找到单链表倒数第n个节点，保证链表中节点的最少数量为n。

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
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */
 
public class Solution {
    /*
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: Nth to last node of a singly linked list. 
     */
    public ListNode nthToLast(ListNode head, int n) {
        // write your code here
        ArrayList<ListNode> list=new ArrayList<>();
        if (head!=null){
            list.add(head);
        } else{
            return head;
        }
        
        while(head.next!=null){
            list.add(0,head.next);
            head=head.next;
        }
        
        ListNode targetNode=list.get(n-1);
        return targetNode;
        
    }
}

  1. 双向链表
    双向链表是每个数据结点都有两个指针，分别指向相邻的前驱结点和后继结点，可以方便的访问某个结点的前驱结点和后继结点，存储上会相对多占用一些空间。

    代码实现

    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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
public class StaticList {
    public static void main(String[] args) {
        run();
    }

    private static void run() {
        StcList list = new StcList<CharSequence>();
        System.out.println("顺序新增前：");
        list.printAll();
        System.out.println("顺序新增后：");
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("E");
        list.insert("D", 3);
        list.delete(2);
        list.printAll();
    }

    //存储结构
    public static class StaticListNode<E> {

        private E data;
        private int cursor;

        public StaticListNode(E data, int cursor) {
            this.data = data;
            this.cursor = cursor;
        }

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public int getCursor() {
            return cursor;
        }

        public void setCursor(int cursor) {
            this.cursor = cursor;
        }
    }

    static class StcList<E> {

        private static final int MAX_SIZE = 10;
        StaticListNode<E>[] nodes = new StaticListNode[MAX_SIZE];

        public StcList() {
            initList(nodes, nodes.length);
        }

        //初始化备用链表
        private void initList(StaticListNode[] nodes, int maxSize) {
            for (int i = 0; i < maxSize; i++) {
                nodes[i] = new StaticListNode(null, i + 1);
            }
            //将最后一个数据元素的游标指向第一个有值元素
            nodes[maxSize - 1] = new StaticListNode(null, 0);
        }

        public void printAll() {
            for (int i = 0; i < nodes.length; i++) {
                System.out.print(nodes[i].getCursor());
                System.out.print(":");
                System.out.print(nodes[i].getData());
                System.out.print(":");
                System.out.print(i);
                System.out.print("|");
            }
            System.out.println();
        }

        /**
         * 查找当前备用链表的头的
         */
        private void findHead() {

        }

        /**
         * 分配空间 分配空间的元素下标
         *
         * @return 0分配失败
         */
        private int mallocArry() {
            int index = 0;
            if (nodes[0].cursor > 0) {
                index = nodes[0].cursor;
                nodes[0].cursor = nodes[index].cursor;
            }
            return index;
        }

        //顺序新增元素
        public boolean add(E e) {
            if (e == null) {
                System.out.println("新增失败");
                return false;
            }

            //不等于零说明链表容量没用完，可以新增
            int currentIndex = nodes[0].getCursor();
            if (currentIndex > 0) {
                //当前空元素下标
                nodes[currentIndex].setData(e);
                nodes[0].setCursor(nodes[currentIndex].getCursor());
//                nodes[currentIndex].setCursor(0);


                return true;
            }

            System.out.println("新增失败");
            return false;
        }

        /**
         * @param e     要插入的数据
         * @param index 表示要插入的链中的位置
         * @return true插入成功
         */
        //新增元素
        public boolean insert(E e, int index) {
            if (e == null || index < 0 || index > MAX_SIZE - 1) {
                System.out.println("插入元素失败");
                return false;
            }

            //不等于零说明链表容量没用完，可以新增
            int currentIndex = nodes[0].getCursor();
            if (currentIndex > 0) {

                //查找对应的位置
                int k = 1;
                for (int i = 0; i < index - 1; i++) {
                    k = nodes[k].cursor;
                }

                //要插入位置记录的游标
                int insertCursor = nodes[k].getCursor();

                //申请分配的空间的下标
                int i = mallocArry();

                //插入位置的游标连接到新插入元素
                nodes[k].setCursor(i);
                //新插入元素的游标连接之前插入位置记录的游标
                nodes[i].cursor = insertCursor;
                nodes[i].data = e;

                return true;
            }

            System.out.println("插入元素失败");
            return false;
        }

        public boolean delete(int index) {

            //不等于零说明链表容量没用完，可以新增
            int currentEmptyIndex = nodes[0].getCursor();
            if (currentEmptyIndex > 0) {
                //查找前一个的位置
                int k = 1;
                for (int i = 1; i < index - 1; i++) {
                    k = nodes[k].cursor;
                }

                int currentIndex = nodes[k].cursor;
                int nextIndex = nodes[currentIndex].cursor;
                nodes[k].cursor = nextIndex;

                //将删除的结点连接到备用链表
                free(currentIndex);

                return true;
            } else {
                System.out.println("删除元素失败");
                return false;
            }
        }

        private void free(int i) {
            nodes[i].cursor=nodes[0].cursor;
            nodes[0].cursor=i;
            nodes[i].data = null;
        }

    }

}
  1. 循环链表 有环

循环链表的特点是最后一个结点的指针指向头结点，使整个链表形成环。

空链的判断条件：head==head->next;rear==rear->next;

  • 约瑟夫问题

问题描述：
N个人围成一个圈，从第一个开始报数，第M个人将被杀掉，最后只剩一个，其他都被杀掉。

循环链表的实现方式就是通过遍历元素，指针移动M位删除该元素，知道剩余一个元素。
数学推导方式是发现最终获胜的元素下标是在每一轮“杀人”过程中移动M位从而得到公式：f(N,M)=(f(N−1,M)+M)。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main()
{
    int n, m, i, winner = 0;
    printf ("N M = ");
    scanf("%d%d", &n, &m);
    for (i = 2; i <= n; i++)
    {
       //i是每阶约瑟夫环的人数
        winner = (winner + m) % i;
     }
     
    //编号是从零开始，这里加1变成符合习惯的计数
    printf ("\nThe winner is %d\n", (winner +1));
    
}

  • 魔术师发牌问题

问题描述：
魔术师手中有A到K十三张黑桃扑克牌，表演前魔术师已经按照一定的顺序叠放好，表演过程：开始，魔术师数1将最上面的那张翻过来，是黑桃A，将其放在桌面上；第二次，魔术师数1、2，将第一张牌放在所有牌最下面，将第二张牌翻转过来，第二张牌正好是黑桃2；第三次，魔术师数1、2、3，将第一、二张牌按照顺序放在所有牌最下面，将第三张牌翻转过来，第三张牌正好是黑桃3；…知道所有牌都翻转过来，顺序刚好是A、2、3…K，现在要知道魔术师在翻牌前叠放的13张牌的顺序。

代码实现

1

  • 拉丁方阵问题

问题描述：
拉丁方阵是一种n×n的方阵，方阵中恰有n种不同的元素，每种元素恰有n个，并且每种元素在一行和一列中 恰好出现一次。

特点：
每一行除了开始的数递进一位外，其余的数都是按照顺序排列，递进的数排在后面，因此使用循环链表解决。

代码实现

1