順序表的前驅演算法

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）。