主题:读不懂的一个小问题
强人落草
[专家分:60] 发布于 2009-02-17 20:47:00
void delsame(Sqlist &L)
{
int i,j,k;
if(L.len>0)
{
j=0;
for(i=1;i<L.len;i++)
{
k=0;
while(k<=j&&L.data[k]!=L.data[i])
k++;
if(k==j+1)
L.data[j++]=L.data[i];
}
L.len=j;
}
}
这道程序是从顺序表L中删除重复元素的高效算法,但是小生怎么也看不懂,哪位能指点下,加些注释并详细讲解下,谢谢了。
回复列表 (共3个回复)
沙发
i_cplusplus [专家分:290] 发布于 2009-02-23 17:00:00
我觉得这个并不能有效的删除掉重复元素啊,比如一行数 4 5 6 3 3
经过此程序后得到的是5 6 3啊
板凳
我的天下 [专家分:20] 发布于 2009-02-26 00:44:00
这个程序应该没有错误,建议去看一下数组的最佳排序方法,感觉与此类似
3 楼
灯下野狐 [专家分:0] 发布于 2009-03-04 14:22:00
/*
楼主的那算法好像有一点小问题吧,会出现就像一楼说的那样的问题,
可以稍微改一下
*/
void delsame( Sqlist &L )
{
int i, j, k;
if ( L.len > 0 )
{
j = 0;//将j初始为0
for ( i = 0; i < L.len; i++ )//遍历数组
{
k = 0;
while ( k < j && L.data[k] != L.data[i] )//从头开始,若a[k]和a[i]不同,继续往后遍历
k++;
if ( k == j )//当数组的a[0]~a[j - 1]号元素都和a[i]不同
{
a[j++] = a[i];//将a[i]“接到”全部元素都不相同的数组的最后面
}
//假如k != j, 那就说明前a[0] ~ a[j - 1]有元素和a[i]相同,那么就继续在原数组遍历
}
L.len = j;
}
/*
例如:
若数组元素为 5 5 6 6 0
从for循环开始,易知while循环条件不满足,所以不做,因为开始k = 0, j = 0,
所以if成立,故a[0] = a[0](此时新数组为:5 5 6 6 0),j自增1变位1,然后for循环条件判断,i自增变为1,然后k赋值为0再从头开始判断,
易知while条件不满足,因为虽然(k = 0) < (j = 1)成立,但a[0]却等于a[1],所以k还是为0,所以if语句也不成立,
继续i自增变为2,k = 0再从头开始(注意此时j的值仍为1),可知while条件满足,因为有a[0] != a[2],故出来后k的值为
1,因为k == j,所以if条件成立,故a[1] = a[2]( 此时新数组为:5 6 6 6 0 ),j自增变为2,继续依次类推,i再变为3,
而在while语句中有a[1]==a[i],故出来后k的值为1,而k = 1 也和j = 2不等,
继续i自增变为4,( 注意此时j的值仍为2,故while语句k只能取 0, 1 ),现a[0], a[1] 都和a[4]不等,
则出来后 k = 2, 故 k == j,所以a[2] = a[4]( 此时数组变为:5 6 0 6 0 ),j自增1变为3,最后结束,
可知j的值即为新数组前面不同元素的长度
*/
可能有点赘述,不好意思文笔不大好
我来回复