广州商城建站北京网站优化实战
读《大话数据结构》学习笔记
线性表
线性表是零个或多个数据元素的有限序列。
线性表的顺序存储结构
定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
优点：
无须为标识表中元素之间的逻辑关系而增加额外的存储空间
可以快速地读取表中任一位置的元素(时间复杂度为O(1))
缺点：
插入和删除操作需要移动大量元素(时间复杂度为O(n))
当线性表长度变化较大时，难以确定存储空间的容量(容易造成溢出或者空间浪费)
造成存储空间的“碎片”
线性表的链式存储结构
链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是联系的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。
单链表：
头指针
头结点
结点：
在链式存储结构中，我们把一个同时拥有存储有数据元素信息(数据域)和存储直接后继位置的数据元素(指针域)称为结。
单链表定义：
n个结点链结成一个链表，即为线性表的链式结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
头指针
我们把链表中第一个结点的存储位置叫做头指针，整个链表的存取必须是从头指针开始进行的。
头结点
有时，为了更加方便的对链表进行操作，我们会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。
头指针与头结点的异同
空链表
头结点的指针域为“空”，则线性表为空。
单链表的读取，获取链表第i个数据的算法思路(时间复杂度O(n))：
1、声明一个结点p指向链表第一个结点，初始化j从1开始。
2、当j
3、若到链表末尾p为空，则说明第i个元素不存在。
4、否则查找成功，返回结点p的数据。
单链表的插入，单链表第i个数据插入e结点的算法思路(时间复杂度O(n))：
1、声明一个结点p指向链表第一个结点，初始化j从1开始。
2、当j
3、若到链表末尾p为空，则说明第i个元素不存在。
4、否则查找成功，在系统中生成一个空节点s。
5、将数据元素e赋值给s->data。
6、单链表的插入标准语句s->next=p->next; p->next=s。
7、返回成功。
单链表的删除，删除单链表中第i个数据(q)的算法思路(时间复杂度O(n))：
1、声明一个结点p指向链表第一个结点，初始化j从1开始。
2、当j
3、若到链表末尾p为空，则说明第i个元素不存在。
4、否则查找成功，将欲删除的结点p->next赋值给q。
5、单链表的删除标准语句p->next=q->next。
6、将q结点中的数据赋值给e，作为返回。
7、释放q结点。
8、返回成功。
单链表的优点
综上可以看出，单链表常规的查找、插入、删除的时间复杂度都为O(n)。但是如果我们希望在第i个位置，插入10个元素，在顺序存储结构中我们需要进行10次O(n)的操作。而在单链表中我们只需要在第一次查找时进行O(n)的操作，而后只需要移动指针(时间复杂度为O(n))就可以了。所以，对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
头指针具有标识作用，所以常用头指针冠以链表的名字
无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头结点是为了操作的统一和方便设立的，放在第一元素的节点之前，且数据域一般无意义(也可以存放链表的长度)
有了头结点，对在第一个元素结点前插入结点和删除第一个结点，其操作与其他结点的操作就统一了
头结点不一定是链表的必须要素
静态链表：
在一些语言中，没有指针，所以有人就想出来用数组来代替指正。如下图所示，这种用数组描述的链表叫做静态链表
其中cur为游标，data为数据，下图为有存放数据时的状态
静态链表的插入操作(在第i个元素之前插入元素)
1、获得空闲分量的下标(也就是数组第一个元素的cur值)
2、将要插入的数据赋值给此分量的data
3、找到第i个元素之前的位置(这一步循环里面对k变量的使用得认真看且理解)。
4、将第i个元素之前的cur赋值给新元素的cur
5、将新元素的下标赋值给第i个元素之前元素的cur
图示如下：
静态链表的删除操作(删除第一个元素)
1、在链表中找到要删除的元素
2、将要删除元素的cur值赋给前一个元素的cur
3、将第一个元素cur值赋值给要删除的分量cur(也就是将之前记录空余位置的cur分配给要删除的分量cur)
4、将要删除的分量下标赋值给第一个元素的cur(也就是将删除之后空余的空间记录下来)
如下图所示
静态链表的优缺点
优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点：1、没有解决连续存储分配带来的表长难以确定的问题。2、失去了顺序存储结构随机存取的特征
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
尾指针：为了更方便的找到最后一个结点，我们将最后一个结点的尾指针来表示循环链表，如下图所示
双向链表
双向链表是在单链表的每个结点中，在设置一个指向起前驱结点的指针域。如下图所示
双向链表的插入操作
双向链表的删除操作
总结
