第1章第1节练习题6 删除重复值

问题描述

从有序表中删除所有其值重复的元素，使表中所有的元素的值均不同。

算法思想

注意此题中所提到的线性表是有序顺序表，那么值相同的元素一定在连续的位置上，既然这样，那么我们可以使用类似与练习题5的方法。对顺序表进行一次遍历，使用k记录元素值不相同的元素的下标。这样以来当有若干个值相同的元素时，我们只保留第一个相同值元素，若不相同时，略过便可，最后对顺序表的表长重置即可解决此问题。
因为这里只考虑算法的思想，对具体细节并不做讨论，因此假定所有的元素都是正整数。

算法描述

void Delrept(SqList *L){
    int k=0;
    ElemType temp=-1;
    for(int i=0;i<L->length;i++){
        if(L->data[i]!=temp){
            temp=L->data[i];
            L->data[k++]=L->data[i];
        }
    }
    L->length=k;
}

具体代码见附件

附件

#include<stdio.h>
#define MaxSize 100
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

int Delrept(SqList *);
void print(SqList *);

int main(int argc, char* argv[]){
    SqList SL;
    SL.length=10;
    SL.data[0]=1;SL.data[1]=1;SL.data[2]=2;SL.data[3]=2;SL.data[4]=2;
    SL.data[5]=3;SL.data[6]=3;SL.data[7]=3;SL.data[8]=3;SL.data[9]=4;

    int flag;
    print(&SL);
    flag=Delrept(&SL);
    print(&SL);

    if(flag==0){
        printf("Delete success!
");
    }else{
        printf("Dlelet illegal!
");
    }
    return 0;
}

int Delrept(SqList *L){
    int k=0;
    ElemType temp=-1;
    if(L->length==0){
        return -1;
    }
    for(int i=0;i<L->length;i++){
        if(L->data[i]!=temp){
            temp=L->data[i];
            L->data[k++]=L->data[i];
        }
    }
    L->length=k;
    return 0;
}

void print(SqList *L)
{
    for(int i=0;i<L->length;i++){
        printf("%d	",L->data[i]);
    }
    printf("
");
}