设 a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
Loc(ai)=Loc(a１)+(i-1)*d 1≤I≤n 顺序表插入运算时间主要消耗：数据的移动。
一般情况下，在第i（1<=i<=n）个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。 （在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 n－i＋1个元素。）
一般情况下，删除第i（1<=i<=n）个元素时，需从第i+1至第n（共n-i）个元素向前移动一个位置
i 的取值范围为 ：1≤ i≤ n+1（即有 n＋1个位置可以插入）。 设在第i个位置上作插入的概率为Pi： Ein??pi(n?i?1)i?1n?1在等概率情况下：
P=1/ (n+1) ，则平均移动数据元素的次数则为：E in ?i
?n?1i?11pi(n?i?1)?n?1?n?1(n?i?1)?i?1n2这说明：在顺序表上做插入操作需移动表中一半的数据元素。 显然顺序表上插入时间复杂度为Ｏ(n)。 int SeqlistInsert(A[],n,i，x) {
if(i<1 || i>n) //检查插入位置的正确性 {
Printf(“参数非法”);
return 0; //插入位置参数错，返回错误代码0 }
else {
for(k=n;k>=i;k--)
A[k-1]<=A[k]; //结点移动 A[i]<=x; //新元素插入
n<=n+1; // n指向新的最后元素
return n; //插入成功，返回成功代码 } }
线性表的删除运算是指将表中第 i 个元素从线性表中去掉。 SeqlistDelete(A[],n,i) {
if(i<1 OR i>n) //检查空表及删除位置的合法性 {
Printf(“参数非法”);
return 0; //不存在第i个元素，返回错误代码0 } else {
for(k=i+1;k A[k-1]<=A[k]; //数据元素向前移动 n<=n -1; // n指向新的最后元素 return n; //删除成功，返回成功代码 } 删除算法的时间性能分析 与插入运算相同，其时间主要消耗在了移动元素上。 计算数据移动的次数：某次删除数据的移动次数与具体位置有关。求平均性能。 删除第i个元素时，其后面的元素 ai+1～an 都要向上移动一个位置，共移动了 n-i 个元素。 i 的取值范围为 ：1≤ i≤ n（即有 n个位置可以删除）。 设在第i个位置上作删除的概率为Pi，平均移动数据元素的次数： 在等概率情况下：Pi=1/ n ，则平均移动数据元素的次数则为： Ede??npi(n?i)i?11nn?1Ede???pi(n?i)??(n?i)?ni?12i?1n这说明顺序表上作删除运算时大约需要移动表中一半的元素。 显然该算法的时间复杂度为Ｏ(n)。 线性表链式存储结构，不要求逻辑上相邻的两个数据元素物理上也相邻，因此不需要用地址连续的存储单元来实现。 链表是通过一组任意的存储单元来存储线性表中的数据元素的，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”。 存放数据元素信息的称为数据域，存放其后继地址的称为指针域。 链表的表示： 链表是由一个个结点构成的。 结点的申请：p=new LNode; 结点的释放：delete p； 在某结点后面插入新结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。 操作如下： ①s->next=p->next; ②p->next=s; 注意：两个指针的操作顺序不能交换。 在某结点前面插入新结点： 设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s。 设单链表头指针为L，操作如下： q=L; while (q->next!=p) q=q->next; //找*p的直接前驱 s->next=q->next; q->next=s; 删除结点：设p指向单链表中某结点，删除*p。 作业1：线性表中元素为整型，以50为界，小于50在左，大于50在右。 作业讲解：x<=A[i];