06.从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。
算法思想:注意是有序顺序表,值相同的元素一定在连续的位置上,用类似于直接插入排序的思想,初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同,若相同,则继续向后判断,若不同,则插入前面的非重复有序表的最后,直至判断到表尾为止。
本题代码如下:
bool Delete_Same(SqList &L)
{
if(L.length==0)
{
return false;
}
int i,j;//i存储第一个不相同的元素,j为工作指针
for(i=0,j=1;j<L.length;j++)
{
if(L.data[i]!=L.data[j])//查找下一个与上个元素值不同的元素
{
L.data[++i]=L.data[j];//找到后,将元素前移
}
}
L.length=i+1;
return 0;
}
对于本题的算法,请读者用序列1,2,2,2,2,3,3,3,4,4,5来手动模拟算法的执行过程,在模拟过程中要标注 i 和 j 所指示的元素。
思考:如果将本题的有序表改为无序表,你能想到时间复杂度为O(n)的方法吗?(提示:使用散列表。)
标签:06,线性表,重复,元素,算法,有序,本题 From: https://www.cnblogs.com/bujidao1128/p/17255763.html