结构之美学习一《顺序表和链表》

对于数据结构，主要分两种：

1.逻辑结构，指的是数据对象中元素之间的相互关系。

2.物理结构，指的是元素的存储当物理内存空间中的结构。

逻辑结构其实就是我们常说的表，树，图。即是来定义这个数据集中元素之间的关系。

物理结构的话指的是元素在内存（当然也可以是磁盘）的存储方式，以我们所知，内存其实就是一组存储单元，将元素存储到内存单元中，最常用的就是两种方式，

1>顺序的存储，即开辟一组连续的存储单元来存储我们需要放入的元素（比图数组） 。 2>链式存储，元素可能并不是存储在一组连续的内存单元中，

我们有指针联系两个相邻元素的存储位置（即我们常说的链表）。

一.线性表

1.定义
零个或多个数据元素的有限序列。序列，首先是元素间是有顺序的，既如果有多个元素，第一个元素无前驱，最后一个元素无后继，

其他中间元素都有且只有一个前驱和后继。序列说白了就是一个队伍一样。

线性表这个概念是按数据额逻辑结构来定义的。即这样的数据集中，每个元素都是像个队伍一样，顺序排列着。

2.线性表的存储方式：

那么我们要将这样的数据集进行一些操作（增删改查），就得存储到计算机内存里。对于将线性表的数据集存储到内存里来操作，

我们最快能想到的就是，直接顺序存储进去，一段连续的内存单元存储。

这就是线性表的顺序存储。最常见的例子就是我们用到的数组。用一段地址连续的存储单元依次存储线性表中的元素。

C code线性表的顺序存储的结构代码
#define MAXSIZE 20
typedef int ElemType；
typedef struct
{
ElemType data[MAXSIZE]；
int length；
}SQList;

线性表顺序存储结构的优缺点：
优点，无需为表示表中元素之间的逻辑关系而增加额外的存储空间；

可以快速的存取表中的任意位置的元素。

缺点，插入后删除操作需要移动大量元素；

当线性表长度不稳定时，存储空间难确定，容易造成存储空间碎片。

因此由上我们就引出了线性表的存储方式，链式存储，也可以叫链表存储，这也是真正的在工作学习面试中最常问到用到一种数据结构。

线性表的链式存储结构

C code 单链表的实现：结构指针
typedef struct Node
{
ElemTpye data；
struct Node *next;

}Node;
typedef struct Node * Linklist；

链式存储即元素存储的内存单元可以是不连续，分散的。对于元素间如何来维护他们的关系（即逻辑结构，每个元素的前驱和后继。）

即用到一个指针域来存储他和前驱或是后继直接的关系。

如上面的是一个单链表的指针结构，即每个元素中存储了他的后继元素的内存空间地址。

应用场景选择

由上图可以简单的知道数据的常见的操作，增，删，改，查时。

对于数据操作偏向于查和改时，顺序存储的速度是非常快的，而链表的话，则必须从头节点开始遍历查找。

但是涉及到插入或是删除元素时，顺序存储每次操作为了维护顺序，必须移动元素，而对于链表来说，只需新增一个存储单元后，对其中几个指针域中指针的指向做下改变就行。

tips1. 但是我们要注意的是， 表的插入和删除操作其实有两部分组成：遍历找到第i个元素，然后删除或插入。那其实顺序表这步的时间复杂度为 O（1），

而单链表的时间复杂度为O（n），虽然后面的话顺序表需要将i后面的元素都往后移动一位，话费的时间相对来说就是O(n),而单链表无需移动元素，

时间就为O（1）。看上去其实貌似扯平啊，这样单链表相对于线性表的顺序存储结构来说没什么大的优势。但是如果在第i点插入k个元素时，

那么相对于链表来说只要第一遍历查找到了第i个元素后，之后的操作基本是是O（1），而顺序的操作的话，是每次都要移动n-i个元素，O（n），

效果就出来了。

tips2.而对于顺序表，如果我们的插入和删除操作，在不考虑存储空间额分配这个死角的话（即存储空间可以动态的申请，不考虑溢出），

都是在对最后的一个元素进行操作，那不是也很好，即删除和插入都是在表尾进行，那么就不用移动大量元素了。这也算是栈概念的一个雏形吧。

对于顺序表的讨论其实不多。

但是对于链表这种数据结构的涉及的问题就比较多了。

链表又可以根据操作的需要衍生出，循环链表（即，表的尾元素的指向头节点），双向链表（元素可以快速定位的找到他的前驱和后继）。

对于链表常见的操作

1.单链表的反转。

//Ccode: 单链表的实现：结构指针
typedef struct Node
{
	ElemTpye data；
	struct Node *next;

}Node;

typedef struct Node * Linklist；

Linklist * reveral(Linklist * ls)
{
	//链表为空或是单节点表
	if(ls == NULL || ls->next == NULL)
	{
		return ls;
	}

	Node *pre  * cur,*nex;

	pre = ls;
	cur= head->next;
	while(cur !=null)//如果节点存在，继续遍历
	{
		nex = cur->next;//保存后继节点
		cur->next = pre;//翻转
		pre = cur;
		cur= nex;
	}

	ls->next = NULL;
	ls = pre;
	return ls;
}

（额，代码格式可能很不规范，我没正儿八经写个c和c++代码。）

代码分析：比如三个节点 A->B->C;要翻转成C->B->A;

那么我就遍历的每个点将其反转，比如上面，pre = A，cur = B；

在遍历是判断我要反转的当前节点是是否存在，如果存在，那要操作把B->A后，原本B->C，信息我需要用一个辅助的指针来指向C；

最后当cur =null，即遍历结束了。此刻的链表形式我们可以模拟的看成这样子：
A—><—B<—C;
需要将A即原本的头节点变成尾节点，指向为null；
于是执行了 ls->next = null;
再将链表的头指针指向pre节点，因为在while循环中就可知，cur ==null，即当时pre->next = null，也就是遍历到了链表的尾节点了。

2.查找链表的中间元素
这个比较好玩。
首先，按照思路来说，要查找中间的元素，我们的先知道整个链表的长度。那就先遍历一遍记录链表的长度。
然后再从头遍历到第 n/2个节点。
然后看到一个好巧妙一很好玩的方法就是
定义两个指针，*A ，*B，A每次循环就指向下一个元素，B每次指向下下个元素，即遍历的速度B是A的两倍，当B遍历到尾元素时，

A其实正好指向的是链表的中间元素。
而这个方法简单来说，只需要 遍历n个节点。

Node * findMid(LinkLis * ls)
{
		//链表为空或是单节点表
	if(ls == NULL || ls->next == NULL)
	{
		return ls;
	}

	Node * i , * j;
	i = j = ls;//从头节点开始
	while( i->next != NULL && j->next->next != NULL)//判断是否遍历到尾节点
	{
		i = i->next;
		j = j->next->next;
	}

	return i;
}

3.判断一个链表是否有环。
如果一个链表有环的话，那么如果遍历这个链表就会出现死循环。
那么如何来判断一个链表是否有环。
最常规的思路就是跟走迷宫一样，我遍历时给他做个标记。简单的可以将遍历过的点放在放在一个Set中（Set可以保证唯一性，不好意思，我这纯粹的java思路）。
如果不能借助辅助元素，那么，同样的可以运用上面查找中的思路，即，如果存在环，一直在里面以不同步调遍历的两个指针总会有相遇的一刻。

Node * i , * j;
	i = j = ls;//从头节点开始
	while( i->next != NULL && j->next->next != NULL)//判断是否遍历到尾节点
	{
		i = i->next;
		j = j->next->next;
                if( i == j){

                  return true
                 }
	}

然后扩展的时候是找到这环的入口点。
对于这个找入口的问题，因为传统上我们给两个指针设置的每步长为1,2.
对于在环中遇到问题，一开始想，会不会跳过啊，即A追上B时，下一个事件后，A在B前面。
这也正是上面为什么步长设置为1,2的原因，这样就不会出现上面的这种情景。
在环内，A和B相遇的时候，必定是A追上了B，并且第一次相遇时，B必定还未走完一环。而A可能走了n个环了。

引用之百度文库。


4.判断两个链表是否相交。

最简单的想法就是看A链表中的每个节点是否在B链表中。这样的每次取A表中的一个节点，然后扫描一遍B链表的元素，

整个算法复杂度就是A长度 * B长度。

第二种的想法是用计数的方式，扫描一遍A链表将其以键值对形式存入一个hashmap中，然后去B链表中额节点来查询。

此刻的的算法复杂度为A长度 + B长度。但是需要辅助空间的申请。

第三种方法，如果两个链表相交，根据链表的特性可知，在相交节点之后的节点都是相同的，也就是我们可以直接取两个链表的尾节点来比较，

如果相同，即他们相交。此刻的算法复杂度还是两个链表的长度和，但是不需要额外的空间了。

bool isCrossing (Linklist * A , Linklist * B)
{
	Node *aTail, bTail;
	//规范点先可以判断链表 A，B是否为Null
	aTail = A;
	bTail = b;

	while(A->next !=null)
	{
		A = A->next;
	}

		while(B->next !=null)
	{
		B = B->next;
	}

		if( A == B)
		{
			return true;
		}

		return false;

}

相对于顺序表，链表的可玩性来说比较高，也是大家在工作或是面试中常会遇到的问题。

over