数据结构与算法（二）线性表
一、线性表
线性表是一种简单的线性结构，是零个或者多个数据元素的有限序列，零个元素的线性表叫做空表，首先线性表是一个序列，也就是说各个元素之间是有先来后到顺序的，特点是若元素存在多个，在非空的有限集合中，且第一个元素没有之间前驱元素，而最后一个元素没有直接后继元素，其他的元素都有唯一的前驱和后继元素；线性表强调的是有限的，事实上无论计算机发展到多强大，它所处理的元素都是有限的；在较为复杂的线性表中，一个数据元素可以由若干个数据项组成；线性表有顺序存储结构和链式存储结构。
二、顺序存储结构
线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素，说直观一些，就是在内存中找了一块内存地址，通过占位的形式，把一定的内存空间给占用了，然后把相同数据类型的数据元素依次存放在这块空地中，顺序表逻辑上相邻的元素在物理上也是相邻的，每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数，只要确定了第一个元素的起始位置，线性表中的任意一个元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构；数组即为这种顺序存储结构，数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
顺序表的优缺点：
1）优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任一位置的元素；
2）缺点：插入和删除操作需要移动大量的元素；当线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的“碎片”；
三、链式存储结构
在解决实际问题时，有时候并不适合采用线性表的顺序存储结构，例如两个一元多项式的相加、相乘，这就需要另一种存储结构来表示，链式存储它是采用一组任意的连续或非连续存储单元存储线性表的元素；为了表示每个元素ai与其直接后继ai+1的逻辑关系，链式存储不仅需要存储元素本身，还要存储一个指向其直接后继元素的地址，这种存储结构被称之为结点（node），存储元素的叫数据域，存储地址的叫指针域，结点元素的逻辑顺序称之为线性链表或单链表，因为第一个结点没有直接前驱结点，因此需要一个头指针指向它，为了方便操作放在第一个元素结点之前一个结点称之为头结点，头指针变为指向头结点，其数据域可以存放如线性表长度等信息，而指针域则存放第一个元素结点的地址信息，若该链表为空，则头结点指针域为空；因为，最后一个元素没有直接后继元素，所以将其指针域设置为“Null”空，对于插入或删除数据越频繁的操作，单链表的效率就越明显。
单链表结构和顺序存储结构对比：
存储分配方式：
1）顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
2）单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
1）在查找上，顺序存储结构的时间复杂度为O(1)，单恋表的时间复杂度为O(n)；
2）在插入和删除上，顺序存储需要平均移动表长一半的元素，时间复杂度为O(n)；单链表在线出某位置的指针后，插入和删除时间复杂度仅为O(1)；
空间性能：
1）顺序存储结构需要预先分配存储空间，分大了，浪费，分小了容易发生上溢；
2）单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制；
静态链表：
我们让数组的元素都由两个数据域组成，data和cur；也就是说，数组的每个下标都对应一个data和一个cur，数据域data，用来存放数据元素，也就是我们通常要处理的数据；而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标；我们把这种用数组描述的链表叫做静态链表，这种描述方法起名叫做游标实现法。
另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据；我们通常把未使用的数组元素称为备用链表，而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0^2。
静态链表的优缺点：
优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插
入和删除操作需要移动大量的元素的缺点；
缺点：没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储随机存取的特性；
循环链表：
对于单链表来说，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一个结点就无法找到它的前驱结点了，就像不能回到从前一样；将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表；最后一个结点称为尾指针：rear，判断单链表为空的条件是head -> next == NULL，而判断循环单链表为空的条件是head -> next == head，访问第一个结点即为rear -> next -> next，其时间复杂度也为O(1)。
双向（循环）链表：
双向链表（double linked list）就是链表中的每个节点有两个指针域，一个指向直接前驱结点，另一个指向直接后继结点；双向链表的每个结点有data域、prior域、next域，一共三个域。其中，data为数据域，存放数据元素；prior域为前驱结点指针域；next域为后继结点指针域。双向链表为了方便操作也可以增加一个头结点，同时也像单链表一样也具有循环结构，称为双向循环链表。
总结：
1）线性表中的元素之间是一对一的关系，除了第一个元素外，其他元素只有唯一的直接前驱，除了最后一个元素外，其他元素只有唯一的直接后继；
2）线性表有顺序存储结构和链式存储结构两种，采用顺序存储结构的线性表称为顺序表，采用链式存储结构的线性表称为链表；
3）顺序表中数据元素的逻辑顺序与物理顺序一致，因此可以随机存取，链表是靠指针域表示元素之间的逻辑关系；
4）链表又分为单链表和双向链表，这两种链表又可以构成单循环链表、双向循环链表，单链表只有一个指针域，指针域指向直接后继结点，双向链表的一个指针域指向直接前驱结点，另外一个指针域指向直接后继结点；
5）顺序表的优点是可以随机存取任意一个元素，算法实现比较简单，存储空间利用率高，缺点是需要预先分配存储空间，存储规模不好确定，插入和删除操作需要移动大量的元素；链表的优点是不需要事先确定存储空间的大小，插入和删除不需要移动大量元素，缺点是只能从第一个结点开始顺序存取元素，存储单元利用率不高，算法实现比较复杂，因涉及指针操作，操作不当会产生无法预料的内存错误；