请设计算法求顺序表中第一个值为x的元素的前驱和后继的存储位置。

Question

如题所述

Answer 1

【答案】：(1)数据结构
采用顺序表定义。
(2)思路
遍历整个表，找到符合条件的元素x，求出其前驱和后继的下标。注意第一个和最后一个元素。
(3)算法
int SearchxPN_seq(PSeqList palist,DataType x,int*pprev,int*pnext){
/*算法结束后，*pprev和*pnext中分别存放顺序表中第一个值为x的元素的前驱和后继的下标值(当不存在时用-1表示)。当x在顺序表中出现时返回TRUE，否则返回FALSE*/
int index;
for(index=0;index＜palist-＞n;index++) {/*寻找值为x的元素*/
if(palist-＞elelnent[index]==x){ /*找到值为x的元素*/
*pprev=index-1;
*pnext=index+1;
if(index==palist-＞n-1)*pnext=-1;
/*最后一个元素无后继*/
return TRUE;
}
}
*pprev=-1;/*执行到此，说明顺序表中不存在值为x的元素*/
*pnext=-1;
return FALSE;
}
(4)代价分析
算法访问顺序表中每个结点最多一次，时间代价为O(n)。