① 顺序存储结构与链式存储结构
概念官方一点来说可以使用 网络 的介绍：顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
简单来说就是： 用一段连续的地址存放数据元素，数据间的逻辑关系和物理关系相同。
优点1：存储密度大，空间利用度高，比链式存储节约空间
优点2：存储操作上方便操作，顺序支持随机存取，查找会比较容易
缺点1：插入或者删除元素时不方便，花费的时间更多
概念：链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点
优点1：插入或删除时方便些，空间使用灵活
缺点1：存储密度小，空间利用度低
缺点2：查找会相较顺序存储方式复杂一些，花费的时间会更多
这里我们先看图，其实就是将想要插入的元素往链表的尾部插入，然后更新一下为节点tail的位置即可。
今天我们的老师将这个内容的时候提到怎么一句话“谁想进来，谁就去找组织”看这个图我想你应该可以理解这句话，首先第一步需要我们的“C”去找组织中的A，第二步是头结点接到新元素C上。
要想移除单向链表中的一个元素，首先我们得找到被移除结点的前驱的位置，比如是pre“A”。当前移除的元素是remove“B”，让pre->next = remove->next, 然后再执行remove->next = nil。经过上面这些步骤，B就与链表脱离关系了。
但是在网络上面看到怎么一句话
链式的要比顺序的方便（这句话是不能这么说的，因为插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）
② 顺序表的插入与删除的时间主要花在什么操作上
顺序表的插入和删除操作的时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。
最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)。
最坏情况：查找的元素在表尾（或不存在）时，需要比较n次，时间复杂度为O(n)。
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。
即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
顺序表简介：
将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。
采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。
③ 顺序存储结构线性表的插入与删除
顺序表的插入与删除，其实都是一个查找和移动的过程。插入与删除分为 按位置和按值插入和删除。1）按位置比较简单，插入时，从表尾开始到要插入的位置，每个元素向后面移动一个位置，最后将要插入的值放入即可。删除的话，直接从要删除的后一个开始，所有元素向前移动一个位置即可。
2）按值删除，先需要查找，可以选择顺序查找，二分查找（有序表）等。找到后，记录位置，后面的操作与第一种情况一样。
插入算法：
void inert(int i,int data,List L)//要插入的位置,插入的数据,
{
int start=i;
int end=L.length-1;
for(int i=end;i--;i>start)
L.data[i+1]=L.data[i]
L.data[i]=data;
L.length++;
}
④ 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好
该说法错误。在顺序存储方式中如果元素的插入或者删除不牵扯到元素的移动的话，链式的优势体现不出来。另外，在链式存储中，元素的存取机制是顺序；顺序存储中，元素的存取机制是随机的。从元素访问方面来讲，要想访问某个位置的元素时，在顺序存储要比链式存储好很多，在顺序存储可以直接访问，链式存储则需要从链头开始访问，一直到目标点。
⑤ 顺序存储结构线性表的插入与删除
顺序表的插入与删除，其实都是一个查找和移动的过程。插入与删除分为
按位置和按值插入和删除。1)按位置比较简单，插入时，从表尾开始到要插入的位置，每个元素向后面移动一个位置，最后将要插入的值放入即可。删除的话，直接从要删除的后一个开始，所有元素向前移动一个位置即可。
2)按值删除，先需要查找，可以选择顺序查找，二分查找(有序表)等。找到后，记录位置，后面的操作与第一种情况一样。
插入算法:
void
inert(int
i,int
data,List
L)//要插入的位置,插入的数据,
{
int
start=i;
int
end=L.length-1;
for(int
i=end;i--;i>start)
L.data[i+1]=L.data[i]
L.data[i]=data;
L.length++;
}
⑥ 假设线性表采用顺序表为存储结构，其插入与删除在什么位置最快
都是在末尾插入和删除最快
如果插入在中间甚至在表头，那样要后移插入位置后面的所有结点一个单位，而如果是在表尾插入的话，只需要直接添加一个结点即可。
删除同理，如果我们是在中间删除，要将删除位置后面的结点都前移一个单位，而如果是在表尾删除的话，只需要将最后一个删除点即可。
顺序存储结构最耗时的是移动结点的操作。
⑦ 如何建立一个顺序存储的线性表，实现线性表的插入、删除操作
顺序存储结构线性表基本操作 C语言实现
#include<stdio.h>
//以下为函数运行结果状态代码
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量
#defineLISTINCREMENT10//线性表存储空间分配增量
typedefintStatus;//函数类型，其值为为函数结果状态代码
typedefintElemType;//假设数据元素为整型
typedefstruct
{
ElemType*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量
}SqList;
//实现线性表的顺序存储结构的类型定义
//函数声明开始
StatusInitList_Sq(SqList&L);
voidDestroyList_Sq(SqList&L);
voidClearList_Sq(SqList&L);
voidListEmpty_Sq(SqListL);
StatusGetElem_Sq(SqListL,i,&e);
intLocateElem_Sq(SqListL,e,compare());
StatusPriorElem_Sq(SqListL,cur_e,&pre_e);
StatusNextElem_Sq(SqListL,cur_e,&next_e);
StatusListInsert_Sq(SqList&L,i,e);
StatusListDelete_Sq(SqList&L,i,&e);
ListTravel_Sq(SqListL,visit());
//函数声明结束
intmain(void)
{
return0;
}
//函数定义开始
///////////////////////////////////////
//函数名：InitList_Sq()
//参数：SqList*L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
//存储分配成功：OK
///////////////////////////////////////
StatusInitList_Sq(SqList*L)
{
L.elem=(ElemType*)malloc((LIST_INIT_SIZE*sizeof(ElemType));//分配空间
if(!L.elem)
exit(OVERFLOW);//若存储分配失败，返回OVERFLOW
L.length=0;//空表，长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}
///////////////////////////////////////
//函数名：DestroyList_Sq()
//参数：SqList*L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：无
///////////////////////////////////////
voidDestroyList_Sq(SqList*L)
{
if(L->elem)
free(L->elem);//释放线性表占据的所有存储空间
}
///////////////////////////////////////
//函数名：ClearList_Sq()
//参数：SqList*L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：无
///////////////////////////////////////
voidClearList_Sq(SqList*L)
{
L->length=0;//将线性表的长度置为0
}
///////////////////////////////////////
//函数名：ListEmpty_Sq()
//参数：SqListL
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
//非空：FALSE
///////////////////////////////////////
StatusListEmpty_Sq(SqListL)
{
if(L.length==0)
returnTRUE;
else
returnFALSE;
}
///////////////////////////////////////
//函数名：ListLength_Sq()
//参数：SqListL
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(L.length)
///////////////////////////////////////
StatusListLength_Sq(SqListL)
{
return(L.length);
}
///////////////////////////////////////
//函数名：GetElem_Sq()
//参数：SqListL,inti,ElemType*e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：用e返回线性表中第i个元素的值
//返回值：(i<1)||(i>ListLength(L))：ERROR
//1<=i<=ListLength(L)：OK
///////////////////////////////////////
StatusGetElem_Sq(SqListL,inti,ElemType*e)
{
if(i<1||i>L.length)
returnERROR;//判断i值是否合理，若不合理，返回ERROR
*e=L.elem[i-1];//数组中第i-1的单元存储着线性表中第i个数据元素的内容
returnOK;
}
///////////////////////////////////////
//函数名：LocateElem_Sq()
//参数：L,e,compare(ElemType1,ElemType2)
//初始条件：线性表L已存在，compare()为数据元素判定函数
//功能：返回顺序表L中第1个与e满足关系compare()的数据元素的位序
//返回值：若在L中存在于e满足关系compare()的元素：其位序
//若在L中不存在于e满足关系compare()的元素：0
///////////////////////////////////////
intLocateElem_Sq(SqListL,e,compare(ElemType1,ElemType2))
{
inti=1;//i的初值为第1元素的位序
intp=L.elem;//p的初值为第1元素的存储位置
while(i<=L.length&&!(*compare)(*p++,e))
++i;//依次进行判定
if(i<=L.length)
returni;//找到满足判定条件的数据元素为第i个元素
else
return0;//该线性表中不存在满足判定的数据元素
}
StatusPriorElem_Sq(SqListL,cur_e,&pre_e);
//见StatusNextElem_Sq(SqListL,cur_e,&next_e);
StatusNextElem_Sq(SqListL,cur_e,&next_e);
//我的思路是先用LocateElem_Sq()搜索cur_e的位序，
//再看是否大于等于length，
//若是，则返回OVERFLOW；否则返回后继
//这样也许有点麻烦？所以希望大家能够补充方案
//bywangweinoo1
///////////////////////////////////////
//函数名：ListInsert_Sq()
//参数：SqList*L,inti,ElemTypee
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
//成功：OK
///////////////////////////////////////
StatusListInsert_Sq(SqList*L,inti,ElemTypee)
{
ElemType*j;
if(L->length==LIST_MAX_LENGTH)
returnERROR;//检查是否有剩余空间
if(i<1||i>L->length+1)
returnERROR;//检查i值是否合理
//将线性表第i个元素之后的所有元素向后移动
for(j=L->length-1;j>=i-1;i++)
L->elem[j+1]=L->elem[j];
L->elem[i-1]=e;//将新元素的内容放入线性表的第i个位置，
L->length++;
returnOK;
}
///////////////////////////////////////
//函数名：ListDelete_Sq()
//参数：SqList*L,inti,Elemtype*e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
//成功：OK
///////////////////////////////////////
intListDelete_Sq(SqList*L,inti,Elemtype*e)
{
if(IsEmpty(L))
returnERROR;//检测线性表是否为空
if(i<1||i>L->length)
returnERROR;//检查i值是否合理
*e=L->elem[i-1];//将欲删除的数据元素内容保留在e所指示的存储单元中
//将线性表第i+1个元素之后的所有元素向前移动
for(j=i;j<=L->length-1;j++)L->elem[j-1]=L->elem[j];
L->length--;
returnOK;
}
//函数定义结束
⑧ 为什么在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他数据元素，如果在链式存储结构下会怎样
栈也被叫做"先进后出表",正是由于这种性质,让它可以不需要移动元素实现插入和删除.
栈的插入,其实就是压栈,它是被严格限制在栈顶进行的.由于栈顶也是表中最后一个元素,所以压栈也就相当于是在顺序表的最后追加一个元素,这显然不影响前面的元素,也就无需移动其他元素了.
删除也是同样的道理,弹栈(删除操作)也是被严格限制在栈顶进行,这时候删除一个元素只需要在顺序表中去除最后一个元素,自然也不影响之前的元素.
链式结构对于栈来说,同样不需要作任何其他元素的移动.事实上,链式结构的删除和插入操作本身就不需要移动其他元素,无论是对于栈来说还是对于一般的链表.
⑨ 为什么说在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素
栈的插入(入栈)和删除（出栈）运算，都是在栈的同一端进行。所以在顺序存储结构下，栈的入栈与出栈只需移动栈顶指针即可。
如用数组表示栈时，设a[]表示栈，top表示栈顶，x表示欲入（出）栈的元素，则入栈只需：a[top]=x;；top++，出栈只需：top--；x=a[top]。
如用链表表示栈，对于不使用头结点的情形，入栈和出栈时也不需要移动表中其他数据元素；对于使用头结点的情形，入栈和出栈时需要修改头结点的指针。
⑩ 链式存储插入和删除的时间复杂度
计算机的线性表中有两种基本的存储方式： 顺序存储 和 链式存储 。顺序存储指的是用一段地址连续的存储单元依次存储数据；而链式存储中数据元素可以散乱的存储到存储单元中，每一个数据元素中包含数据项和下一个元素的存储地址。
通过二者的定义不难看出，顺序存储在查找时的时间复杂度为 O(1) ，因为它的地址是连续的，只要知道首元素的地址，根据下标可以很快找到指定位置的元素，而对与插入和删除操作由于可能要在插入前或删除后对元素进行移动，所以顺序存储的时间复杂度为 O(n) 。链式存储的特性则正好相反，在查找时需要从头元素逐个寻找，因此查找的时间复杂度为 O(n) ,而对于插入和删除操作，由于只需要变更数据元素中下一元素的存储地址即可，因此时间复杂度为 O(1) 。
表面上看上面的说法没有什么问题，但其实在日常的使用中，比如要在数据集合的第i个位置插入或删除一个元素，要完成这样一个动作，使用顺序存储需要查找到元素然后执行插入或删除，时间复杂度为 O(1)+O(n)=O(n) ;而链式存储同样需要先查找到元素然后在插入或删除，时间复杂度为 O(n)+O(1)=O(n) 。
所以说链式存储插入和删除的时间复杂度为O(1)的前提应该是已知元素当前的位置，否则实现在第i个位置插入或删除一个元素，顺序存储和链式存储的时间复杂度是一样的， 都是O(n) .