1 - 线性表的本质
线性表的定义
线性表是具有相同类型的n(>=0)个数据元素的有限序列（a1, a2, ..., an）。
线性表的性质
a0为线性表的第一个元素，只有一个后继
an为线性表的最后一个元素，只有一个前驱
除a0和an外的其他元素ai，既有前驱，又有后继
线性表能够逐项访问和顺序存取
小结
线性表是数据元素的有序并且有限的集合
线性表中的数据元素必须是类型相同的
线性表可用来描述“队列类型”关系的问题（例如一年的12个月构成了一种线性表）
2 - 线性表的相关操作
线性表的讨论
讨论中....
学生A：线性表可以说是生活“队列关系”的总结。
学生B：对，我们学习之后就可以在程序中使用了。
学生A：可是怎么使用一个线性表呢？
学生B：确实！还有就是程序中怎么生成一个线性表呢？
表达和使用一个线性表。
线性表只是一个单纯的概念吗？不，可以用程序实现。
线性表的操作
一些常用操作
创建线性表
销毁线性表
清空线性表
将元素插入线性表
将元素从线性表中删除
获取线性表中某个位置的元素
获取线性表的长度
小结
线性表的表达在程序中表现为一种特殊的数据类型
线性表的操作在程序中的表现为一组函数
问题
1. 线性表的各个函数如何实现呢？
2. 有几种线性表的实现方式呢？
3. 每种实现方式的优缺点是什么？
3 - 线性表的顺序存储结构
顺序存储结构
顺序存储定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
在C语言中可以用一维数组来实现顺序存储结构
存储空间的其实位置：数组node
线性表的最大容量：数组长度MAXSIZE
线性表的当前长度：length
#define MAXSIZE 20
typedef struct _tag_List {
char node[MAXSIZE];
int length;
} List;
获取元素操作
判断线性表是否合法
判断位置是否合法
直接通过数组下标的方式获取元素
删除元素算法
判断线性表是否合法
判断删除位置是否合法
将元素取出
将删除位置后的元素分别向前移动一个位置
线性表长度减一
小结
优点
无需为线性表中的逻辑关系额外增加额外的空间
可以快速的获取表中合法位置的元素
缺点
插入和删除操作需要移动大量元素
当线性表长度变化较大时难以确定存储空间的容量
4 - 线性表的链式存储结构
顺序表的思考
讨论中。。。
顺序表的最大问题是插入和删除需要移动大量的元素！
如何解决？
学生A：在线性表数据元素之间空出位置，为以后插入使用。
学生B：这样不行！中间无论空多少都有可能用完！
学生A：那不是无解了吗？
学生B：我觉得让每个元素都知道他的下个元素就行了，哪有空插哪。
链式存储定义
为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息
链式存储逻辑结构
n个结点链接成一个链式线性表的结构叫做链表，当每个结点中只包含一个指针域时，叫做单链表。
链表的基本概念
表头结点
链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
数据结点
链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
尾结点
链表中的最后一个数据结点，其下一个数据指针为空，表示无后继
在C语言中可以用结构体来定义链表中的指针域
链表中的表头结点也可以用结构体实现
小结
优点：
无需一次性定制链表的容量
插入和删除操作无需移动数据元素
缺点：
数据元素必须保存后继元素的信息位置
获取指定数据的元素操作需要顺序访问之前的元素
5 - 无招胜有招－静态链表
我们的单链表是怎么出来的呢，是首先我们用最基本的方法实现了线性表，顺序表之后呢，我们发现顺序表，它天生有不足，我们想出了单链表方法，解决了这个不足，我们的单链表就足够强大到取代单链表。
学习完单链表之后呢，假设小A、B、C进行讨论，首先单链表完全解决了顺序表的问题，那为什么还需要讨论呢，就是大家还想知道还有没有其它方法改进顺序表。首先小A觉得单链表很完美，我觉得顺序表可以退休了。小B反问到老师为什么还要教我们顺序表？为什么不直接教单链表？小A说到老师是为了展现单链表的强大！小B我们可以彻底抛弃顺序表了。
牛人小C登场，小C说：单链表虽然综合起来胜过了顺序表，但也有不足。小B说到：什么不足之处呢，Linux内核都用的单链表哦！学生A说：就是，一般的大型项目都能找到单链表的身影！小C说：我想你们会明白的。。。。在我们第二个专题的时候，我们发现实现单链表的时候，单链表的实现严重依赖指针！数据元素中必须包含一个额外的指针域！没有指针的程序设计语言无法实现！比方说basic，比方说forturn，一些在数学领域专门实现的工具，一些语言，它们是没有指针的概念，那是不是单链表就不能在这些程序设计语言中应用了啊，这样子看的话，顺序表还是应该继续应用的，不管它是什么样的缺点，我们无法实现单链表的时候，那我们软件程序，需要一个线性表，那么首选是顺序表，那顺序表，挪动是如何优化呢。
为什么
我们来看一下今天要介绍的静态链表，我们的静态链表本质呢，还是静态数组，那现在我们不需要指针，不利用指针，只用数组来实现线性表，当然顺序表已经做到了，顺序表也是用数组的，但顺序表有天生的不足，在插入，在删除，要做大量的挪动。那我们的静态链表就是为了解决这个问题而设计出来的，我们来看一下它呢是怎么解决顺序表这个问题的呢。我们就要想啊，我们能不能在数组的内部来模拟一下我们单链表那样子的链接呢。我们想一想next指针域保存的是什么？本质上next指针域保存的是下一个元素的地址，那我们的静态链表呢就抓住了这一点，既然说我们可以把一个数据元素放在一个数组里面，那么大家想想看，放在数组里面后，那么这个元素就有了一个唯一的下标我们换一种观点来看，数据元素的下标呢就是数据元素的地址，准确的来说这个数据元素在我们数组里面的地址，那这样子我们就可以用数组的方式模拟单链表了吗。
怎么做
首先的话我们定义的数组元素必须由两个域组成，第一个是data，第二个是next，顾名思义，data是用来保存我们真正的数据元素，那next要模拟单链表，显然是要保存下一个数据元素的地址的，那这个地址呢，并不是我们单链表里面所保存的地址，而是下一个元素在我们数组里面的下标，首先呢，我们把数组里面的零做为表头，那我们不就是模拟了单链表里面的表头，从1到n都可以用来存储线性表里面的元素。
静态链表是在顺序表的基础上，利用数组实现的单链表！
和顺序表、单链表类似，我们静态链表在实现有一些相关的定义的，第一个定义是什么呢，就是我们结点结构体的定义，我们其实是用一个数组来实现单链表，那这个数组里面的元素是什么样子的呢？那就是这个样子了，第一个保存我们真正数据元素的数据，那么还有一个next，这个next就是保存我们的下一个元素在数组里面的下标，是不是非常类似我们单链表里面的指针呢。有了结点的结构体之后呢，我们想想看还差什么呢，就是我们链表的结构体，静态链表的结构体是什么样子的呢？
看完了结构体的定义后，我们静态链表的操作是怎样子的呢？第一个我们获取第pos个元素的操作，第一点第二点还是一样的，合法性的判断。首先呢，我们要看一下目前我们要操作的静态链表是不是合法的，它怎么样才合法呢？最起码静态链表要代表实际存在的东西啊。判断位置是否合法。由表头开始通过next域移动pos次后，当前元素的next域即要获取元素在数组中的下标。
小结
静态链表其实是单链表的另一种实现方式
静态链表的实现“媒介”不是指针而是数组
静态链表主要用于不支持指针的程序设计语言中
静态链表的实现是一种内存管理的简易方法
思考
为什么静态链表结构体中要再定义个header成员，而不直接使用node[0]?
6 - 气宗门道－循环链表
单链表的局限
单链表可以用于表示任意的线性关系
有些线性关系是循环的，即没有队尾元素
单链表的改进
循环链表的定义
将单链表中最后一个数据元素的next指针指向第一个元素
循环链表的操作
循环链表拥有单链表的所有操作
创建链表
销毁链表
获取链表长度
清空链表
获取第pos个元素操作
插入元素到位置pos
删除位置pos处的元素
问题
约瑟夫环问题求解
小结
循环链表只是在单链表的基础上做了一个加强
循环链表可以完全取代单链表的使用
循环链表的Next和Current操作可以高效的遍历链表中的所有元素
7 - 剑宗门道－双向链表
单链表的局限
单链表的结点都只有一个指向下一个结点的指针
单链表的数据元素无法直接访问其前驱元素
逆序访问单链表中的元素是极其耗时的操作！！
单链表的改进
双向链表的定义
在单链表的结点中增加一个指向其前驱的pre指针
双向链表有单链表的所有操作
小结 双向链表在单链表的基础上 增加了指向前驱的指针
功能上双向链表可以取代单链表的使用
双向链表的 Next，pre和Current操作可以高效的遍历链表中的所有元素
![POJ 1284 Primitive Roots (欧拉函数&原根定理)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)