回 帖 发 新 帖 刷新版面

主题:读不懂的一个小问题

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个回复)

沙发

我觉得这个并不能有效的删除掉重复元素啊,比如一行数 4 5 6 3 3
经过此程序后得到的是5 6 3啊

板凳

这个程序应该没有错误,建议去看一下数组的最佳排序方法,感觉与此类似

3 楼

/*
楼主的那算法好像有一点小问题吧,会出现就像一楼说的那样的问题,
可以稍微改一下
*/
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的值即为新数组前面不同元素的长度
        
    */

    可能有点赘述,不好意思文笔不大好

我来回复

您尚未登录,请登录后再回复。点此登录或注册