1.简述线性表中顺序存储结构的含义及主要元素
描述顺序存储结构需要三个属性：
1. 存储空间的起始位置：数组 data , 它的存储位置就是存储空间的存储位置
2. 线性表的最大存储容量
3. 线性表的当前长度
数组长度 与 线性表长度区别
- 数组长度：
即存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表长度：
即线性表中数据元素的个数
在任意时刻，线性表的长度应该小于等于数组的长度。
2.顺序存储结构是如何实现插入与删除的
插入操作
插入算法的思路：
如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置
将要插入元素填入位置 i 处
表长加1
删除操作
删除算法的思路：
如果删除位置不合理，抛出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
表长减1
分析插入和删除的时间复杂度：
最好的情况：插入或删除的都是最后一个元素，时间复杂度 O（1）
最坏的情况：插入或删除的都是第一个元素，则所有其他元素都要进行移动，时间复杂度 O(n)
平均的情况：插入或删除第 i 个元素，需要移动 n - i 个元素，时间复杂度 O(n)
结论：
线性表的顺序存储结构，在存、取数据时，不管是哪个位置，时间复杂度都是O(1)，而插入和删除时，时间复杂度都是 O(n)。
适合元素个数不太变化，而更多是存储数据的应用。
3.顺序存储结构的优缺点有哪些
从优点开始说。当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素。接下来谈谈缺点。如我们所见，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。
优点：
具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出；
缺点：
顺序存储插入与删除一个元素，必须移动大了的数据元素，以此对大的线性表，特别是在元素的插入和删除很频繁的情况下，采取顺序存储很是不方便，效率低；
顺序存储空间容易满，出现上溢，程序访问容易出问题，顺序存储结构下，存储空间不便扩充；
顺序存储空间的分配问题，分多了浪费，分少了空间不足上溢。
4.如何理解线性表的链式存储结构
线性表的链式存储结构（简称 链表）
链表是一种常见的基础数据结构，是一种线性表，但是并不是按照线性的顺序存储数据，链表中的每一个元素，在数据结构中称之为节点，每一个节点中不只会存储这个节点的值，也会存储下一个节点的指针。
链表需要查找和修改值，是比较麻烦的，需要遍历整个链表，复杂度为O(n)，而顺序存储结构只需要O(1)，而链表在插入和删除的时候就相对于顺序存储结构来说就相对简单的多，只需要改变后继节点就可以了，时间复杂度为O(1)，而顺序存储结构则需要O(logn)，所以如果数据需要频繁的查找和修改就使用顺序存储结构，如果只是插入和删除那么使用链表会更好些。
5.链表中头指针和头结点的区别
关于头指针：
1.在线性表的链式存储结构中，头指针是指链表中指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
2.头指针具有标识作用，因此经常使用链表的名字作为头指针名
3.无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
关于头结点：
1.头结点是放在第一个元素结点之前的结点，头结点不是链表中的必须元素，其数据域一般无意义，(有些情况下会存放链表的长度，或用作监视哨等)
2.有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，这些操作与对其他结点的操作就相同了。
6.如何实现单链表的插入与删除
插入：
{ //在带有头结点的单链表L中的第i个结点前插入元素e
LinkList p,s;
int j;
p=L;j=0; //①声明一结点p指向链表头结点，初始化j从0开始；
while(p->next&&j<i-1){
p=p->next;
j++;
} //②寻找第i-1个结点并让p指向此结点
if(j!=i-1) return false; //③若i的位置不合理则报错
if((s=(LNode*)malloc(sizeof(LNode)))==NULL) exit(1); //④查找成功，在系统中生成一个空结点s；
s->data=e; //⑤将数据元素e复制给s->data；
s->next=p->next;p->next=s; //⑥插入操作（关键语句）
return true; //⑦返回成功；
}
删除
{ //删除带有头结点的单链表L中的第i个结点，并饶让e返回其值
LinkList p,q;
int j;
p=L;j=0; //①声明一结点p指向链表头结点，初始化j从0开始；
while(p->next->next&&j<i-1&&p->next){
p=p->next;
j++;
} //②寻找第i-1个结点并让p指向此结点
if(j!=i-1) return false; //③若i的位置不合理则报错
q=p->next; //④若查找成功,q指向其后继
p->next=p->next; //⑤结点q的后继成为结点p的后继
e=q->data;
free(q); //⑥将被删除的元素的值赋给e，释放被删除结点的空间
return true; //⑦返回成功；
} //LinkDelete_L
7.顺序存储与链式存储中插入删除操作的效率问题
1、无论是单链表的插入操作还是删除操作，都是由两部分组成的：一是遍历查找第i个元素，二是实现插入或删除操作。
就整个算法而言，他们的时间复杂度都是O(n)，这样来看的话，再不知道要找的第i个元素所处的位置时，单链表的插入删除操作和顺序存储是没有什么优越性的。
但是！如果知道要插入或者删除的元素的位置时，链式存储就表现出它的优越性了。假如我们要在a10与a11之间插入10个元素，那么顺序存储每插入一个元素后面的元素就要移动一次位置，每次都是O(n)。而链式存储，只需要第一次时找到要插入的那个位置，后面的就只是赋值移动指针而已，时间复杂度为O(1)。
因此，可以得出一个结论：对于插入或者删除操作越频繁的操作，单链表的效率优势就越是明显。
8.如何实现单链表的整体创建
9.顺序存储结构与链式存储结构的优缺点
（一）顺序存储结构和链式存储结构的优缺点比较，以及使用情况。
1 优缺点
① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
2 使用情况
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
3 比较
顺序表与链表的比较
基于空间的比较
存储分配的方式
顺序表的存储空间是静态分配的
链表的存储空间是动态分配的
存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量
顺序表的存储密度 = 1
链表的存储密度 < 1
基于时间的比较
存取方式
顺序表可以随机存取，也可以顺序存取
链表是顺序存取的
插入/删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针
10.如何理解静态链表、循环链表和双向链表
双向链表,也叫双链表
双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。第一个节点的"前连接"指向NULL，最后一个节点的"后连接"指向NULL。
这样可以从任何一个节点访问前一个节点，也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。
由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。
有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表。
循环链表
在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。循环链表可以被视为"无头无尾"。
循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大。
另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。
其它
链表中的节点不需要以特定的方式存储，但是集中存储也是可以的，主要分下面这几种具体的存储方法：
共用存储空间：链表的节点和其它的数据共用存储空间，优点是可以存储无限多的内容（不过要处理器支持这个大小，并且存储空间足够的情况下），不需要提前分配内存,存储一个申请一个，如C语言的MALLOC；缺点是由于内容分散，有时候可能不方便调试。
独立存储空间：一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号/索引，并且方便调试；缺点是不能动态的分配内存。当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是用数组实现的链表）。
链表用来构建许多其它数据结构，如堆栈，行列和他们的衍生。
节点的数据域也可以成为另一个链表。通过这种手段，我们可以用列表来构建许多链性数据结构；这个实例产生于Lisp编程语言，在Lisp中链表是初级数据结构，并且现在成为了常见的基础编程模式。 有时候，链表用来生成联合数组，在这种情况下我们称之为联合数列。这种情况下用链表会优于其它数据结构，如自平对分查找树（self-balancing binary search trees）甚至是一些小的数据集合。不管怎样，一些时候一个链表在这样一个树中建立一个节点子集，并且以此来更有效率地转换这个集合。
