顺序表的前驱算法

1. 请分别对顺序表和单链表写出求线性表中下标为i的（第i+1个）元素的前驱和后续的算法

顺序表：前驱a[i-1],后继a[i+1]
线性表：p=head;
int j=0;
while（j!=i）
{
j++;
p=p->next ;
}
前驱p->data，后继p->next->next->data

2. 顺序表的前驱和后继是指什么

顺序表的前驱与后继指的是当前元素前一个元素与后一个元素分别是什么。如图所示，a[i-1]与a[i+1]分别是a[i]的前驱与后继。

顺序表的实现一般都是使用数组完成，故而在顺序表上进行插入、删除与排序操作是都需要对整个顺序表进行操作；只有在访问第i个元素时，只需要将i-1或i+1就可以轻松访问到该元素的前驱和后继，耗时与n无关。

(2)顺序表的前驱算法扩展阅读：

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。其中，线性表是逻辑结构，顺序表是其一种存储结构。

顺序表具有按数据元素的序号随机存取的特点。

在顺序表中，逻辑关系相邻的两个元素在物理位置上也相邻。

顺序表用物理逻辑上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。

3. 顺序表、单链表的删除算法

单链表的删除操作是指删除第i个结点，返回被删除结点的值。删除操作也需要从头引用开始遍历单链表，直到找到第i个位置的结点。如果i为1，则要删除第一个结点，则需要把该结点的直接后继结点的地址赋给头引用。对于其它结点，由于要删除结点，所以在遍历过程中需要保存被遍历到的结点的直接前驱，找到第i个结点后，把该结点的直接后继作为该结点的直接前驱的直接后继。删除操作如图

单链表的删除操作示意图

删除操作的算法实现如下：
public T Delete(int i)
{
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
算法的时间复杂度分析：单链表上的删除操作与插入操作一样，时间主要消耗在结点的遍历上。如果表为空则不进行遍历。当表非空时，删除第i个位置的结点， i等于1遍历的结点数最少（1个），i等于n遍历的结点数最多（n个，n为单链表的长度），平均遍历的结点数为n/2。所以，删除操作的时间复杂度为O（n）。