数据结构——线性表（1）

  今天复习数据结构中最常用和最简单的一种结构，线性表。   线性表，从名字上你就能感觉到，是具有像线一样的性质的表。在广场上,有很多人分散在各处，当中有些是小朋友，可也有很多大人，甚至还有不少宠物，这些小朋友的数据对于整个广场人群来说，不能算是线性表的结构。但像刚才提到的那样，一个班级的小朋友，一个跟着一个排着队，有一个打头，有一个收尾，当中的小朋友每一个都知道他前面一个是谁，他后面一个是谁，这样如同有一根线把他们串联起来了。就可以称之为线性表。

线性表( List):零个或多个数据元素的有限序列。

  首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。如果一个小朋友去拉两个小朋友后面的衣服，那就不可以排成一队了;同样，如果一个小朋友后面的衣服,被两个甚至多个小朋友拉扯，这其实是在打架，而不是有序排队。   然后，线性表强调是有限的，小朋友班级人数是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

  公司的组织架构，总经理管理几个总监，每个总监管理几个经理，每个经理都有各自的下属和员工。这样的组织架构是不是线性关系呢?   不是，为什么不是呢?哦，因为每一个元素，都有不只一个后继，所以它不是线性表。那种让一个总经理只管一个总监，一个总监只管一个经理，一个经理只管一个员工的公司,俗称皮包公司,岗位设置等于就是在忽悠外人。   班级同学之间的友谊关系，是不是线性关系?哈哈，不是，因为每个人都可以和多个同学建立友谊，不满足线性的定义。嗯?有人说爱情关系就是了。胡扯，难道每个人都要有一个爱的人和一个被爱的人，而且他们还都不可以重复爱同一个人这样的情况出现，最终形成一个班级情感人物串联?这怎么可能，也许网络小说里可能出现,但现实中是不可能的。   班级同学的点名册，是不是线性表?是，这和刚才的友谊关系是完全不同了，因为它是有限序列，也满足类型相同的特点。这个点名册（如表3-2-1所示）中，每一个元素除学生的学号外，还可以有同学的姓名、性别、出生年月什么的，这其实就是我们之前讲的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的顺序存储结构

  说这么多的线性表，我们来看看线性表的两种物理结构的第一种——顺序存储结构。

  线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

  线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用Java语言(其他语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

这里,我们就发现描述顺序存储结构需要三个属性:

• 存储空间的起始位置:数组data，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量:数组长度MaxSize。
• 线性表的当前长度:length。

顺序存储结构的插入与删除

插入

插入思路:

1. 如果插入位置不合理，抛出异常
2. 如果插入表的长度大于等于数组长度，则抛出异常或动态增容
3. 从最后一位元素开始向前遍历到第i个位置，分别把它们都向后移动一个位置
4. 将要插入元素填入位置i处
5. 表长度加1

在这里我们可以用一个数组[a0,a1,a2,a…n]来模拟一个顺序存储结构，那么倘若一个元素m，要插入到数组元素ai的位置，那么首先， ai及以后的所有元素都要向后挪动一个位置，最后m这个元素才能插入到ai的位置。

删除

而对于插入操作，不难看出待删除元素去掉以后，之后的元素依次向前挪动一个位置。

删除的思路:

1. 如果删除位置不合理,抛出异常;
2. 取出删除元素;
3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
4. 表长减1。

线性表顺序存储结构插入和删除的java实现

package test1;
 
public class SeqList<T> {
 
	public static final int MAXSIZE = 20;//存储空间的初始化分配量
	private T[] data;//数组存储数据元素
	private int Length;//线性表当前的长度
	
	//插入元素
	public boolean insertElem(int i,T t){//i表示要插入的位置,并不是数组的下标.t表示待插入的元素
		if (Length==MAXSIZE) {
			System.out.println("线性表已经满");
			return false;
		}
		if (i<1 || i>Length+1) {//i不在范围内
			return false;
		}
		if (i<=Length) {//插入的位置不在表尾
			for(int j=Length-1;j>=i-1;j--){
				data[j+1] = data[j];//前面的值赋值到后面
			}
		}
		
		data[i-1] = t;//将新元素插入
		Length++;
		return true;
		
	}
	
	//删除元素
	public boolean deleteElem(int i){
		if(Length==0){//此线性表为空表
			System.out.println("此线性表为空");
			return false;
		}
		
		if (i<1 || i>Length) {
			System.out.println("删除的位置不在范围内");
			return false;
		}
		
		@SuppressWarnings("unused")
		T t = data[i-1];
		if (i<Length) {//删除的位置不在表尾
			for (int j = i-1; j < Length; j++) {
				data[j] = data[j+1];//后面的值赋值到前面			}
		}
		return true;
	}
	
 
}

数组长度和线性表的长度

  数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。有个别同学可能会问，数组的大小一定不可以变吗?我怎么看到有书中谈到可以动态分配的一维数组。是的，一般高级语言，比如 C、VB、C++都可以用编程手段实现动态分配数组，不过这会带来性能上的损耗。   线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。 在任意时刻，线性表的长度应该小于等于数组的长度。

线性表顺序存储结构的优缺点

  现在我们来分析一下，插入和删除的时间复杂度。   先来看最好的情况，如果元素要插入到最后一个位置,或者删除最后一个元素，此时时间复杂度为0(1)，因为不需要移动元素的，就如同来了一个新人要正常排队，当然是排在最后，如果此时他又不想排了，那么他一个人离开就好了，不影响任何人。   最坏的情况呢，如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度是多少呢?那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为o(n)。   至于平均的情况，由于元素插入到第主个位置，或删除第i个元素，需要移动n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为n-1/2   我们前面讨论过时间复杂度的推导，可以得出，平均时间复杂度还是O(n).   这说明什么?线性表的顺序存储结构，在存、读数据时，不管是哪个位置,时间复杂度都是0[1);而插入或删除时，时间复杂度都是0(n)。这就说明，它比较适合元素个数不太变化,而更多是存取数据的应用。当然，它的优缺点还不只这些……

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时,难以确定存储空间的容量
• 造成存储空间的“碎片”

线性表的链式存储结构

  前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?   要解决这个问题，我们就得考虑一下导致这个问题的原因。   为什么当插入和删除时，就要移动大量元素,仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1，2,3，…,n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

  线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。   以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

  因此，为了表示每个数据元素ai与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。   n个结点(an的存储映像）链结成一个链表，即为线性表（a1，a2,…，an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。   对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?   最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”(通常用 NULL或“^”符号表示)。   有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有，这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

单链表的插入与删除

不带头节点

个结点，它的指针指向哪里?   上图中，是不带头结点的单链表的插入操作。如果我们在非第一个结点前进行插入操作，只需要a(i-1)的指针域指向s，然后将s的指针域指向ai)就行了;如果我们在第一个结点前进行插入操作，头指针head就要等于新插入结点s，这和在非第一个数据元素结点前插入结点时的情况不同。另外，还有一些不同情况需要考虑。 个结点，它的指针指向哪里?   因此，算法对这两种情况就要分别设计实现方法。 带头节点

  上图中，如果采用带头结点的单链表结构，算法实现时，p指向头结点，改变的是p指针的next指针的值(改变头结点的指针域)，而头指针head的值不变。   因此，算法实现方法比较简单，其操作与对其它结点的操作统—。   问题1:头结点的好处:

头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

  问题2:如何表示空表:

无头结点时，当头指针的值为空时表示空表; 有头结点时，当头结点的指针域为空时表示空表。

  问题3:头结点的数据域内装的是什么?

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

单向链表的代码实现

代码过长，另起一篇文章介绍

链接: 数据结构——单链表的代码实现.

单链表结构与顺序存储结构优缺点对比

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素

时间性能

• 查找
• • 顺序存储结构O(1)
• • 单链表On)
• 插入和删除
• • 顺序存储结构需要平均移动表长一半的元素,时间为OKn)
• • 单链表在线出某位置的指针后,插入和删除时间仅为O(1)

空间性能

• 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢
• 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制

通过上面的对比，我们可以得出一些经验性的结论:

• 若线性表需要频繁查找，很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中,对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比,现实中的软件开发,要考虑的问题会复杂得多。
• 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天,这种用顺序存储结构效率会高很多。

总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。