logo标签列表

使用C语言从数组中去除重复项

calgorithm
4

我希望在C语言中了解数组的概念。这是我的数组：

int a[11]={1,2,3,4,5,11,11,11,11,16,16};

我希望你能够提供以下结果：

我想要这样的结果：

{1,2,3,4,5,11,16}

我的意思是要删除重复项。 如何做到呢？

1
什么是问题？您是想要删除重复项吗？您尝试了什么？ - Mysticial
1
这个数组是否保证已经排序？ - flight
2
你尝试过什么？(http://mattgemmell.com/2008/12/08/what-have-you-tried/) - Some programmer dude
看看这个，然后尝试解决你的问题/作业（这将使你受益）：https://dev59.com/-HI_5IYBdhLWcg3wFu7L。 - Yavar
9个回答
9
您无法轻松地调整C语言中的数组大小，至少不是像您声明的那个数组。显然，如果数据按排序顺序排列，则将数据复制到分配的数组前面并将其视为正确的较小大小就很简单（这是一个线性O（n）算法）。如果数据未排序，则情况会变得更加混乱；平凡的算法是二次的，因此可能最好先进行排序（O（N lg N）），然后再使用线性算法。
您可以使用动态分配的内存来管理数组。尽管如此，这可能超出了您学习的范围。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static int intcmp(const void *pa, const void *pb)
{
    int a = *(int *)pa;
    int b = *(int *)pb;
    if (a > b)
        return +1;
    else if (a < b)
        return -1;
    else
        return 0;
}

static int compact(int *array, int size)
{
    int i;
    int last = 0;
    assert(size >= 0);
    if (size <= 0)
        return size;
    for (i = 1; i < size; i++)
    {
        if (array[i] != array[last])
            array[++last] = array[i];
    }
    return(last + 1);
}

static void print(int *array, int size, const char *tag, const char *name)
{
   int i;
   printf("%s\n", tag);
   for (i = 0; i < size; i++)
       printf("%s[%d] = %d\n", name, i, array[i]);
}

int main(void)
{
   int a[11] = {1,2,3,4,5,11,11,11,11,16,16};
   int a_size = sizeof(a) / sizeof(a[0]);

   print(a, a_size, "Before", "a");
   a_size = compact(a, a_size);
   print(a, a_size, "After", "a");

   int b[11] = {11,1,11,3,16,2,5,11,4,11,16};
   int b_size = sizeof(b) / sizeof(b[0]);

   print(b, b_size, "Before", "b");
   qsort(b, b_size, sizeof(b[0]), intcmp);
   print(b, b_size, "Sorted", "b");
   b_size = compact(b, b_size);
   print(b, b_size, "After", "b");

   return 0;
}
就像紧凑函数一样，它很紧凑 - 比我的努力更好 - bph
作为旁注，将函数指定为静态的规范是一种“最佳实践”风格，例如，限制函数的可见性应该是您的“默认”选择，除非您特别需要它们更广泛地可见。 - bph
1
一般来说，是的。我经常使用静态变量，部分原因是我使用GCC选项-Wmissing-prototypes -Wstrict-prototypes进行编译，这意味着在定义或使用每个非静态函数之前都需要声明。我将每个函数标记为静态，直到我知道它将在编写它的源文件之外使用时，就会有一个头文件添加到声明中。有时我会将静态声明和main()函数放在文件顶部；通常，我会将main()放在文件底部，辅助函数放在上面，就像Pascal一样。 - Jonathan Leffler
只是一个快速修复：static int compact(int *array, int size) 应该检查 if size == 0，然后返回 0。现在它返回 1。 - Thomas Walther
@ThomasWalther：鉴于size是有符号的int，它应该是assert(size >= 0);，并且支持if (size <= 0) return size;。开发人员会收到有关其代码滥用的通知；最终用户不会因此代码的不良行为而看到崩溃 - 但是调用代码可能会做一些奇怪的事情，因为它一开始就不够小心。 - Jonathan Leffler
@JonathanLeffler：应该支持 size == 0；算法在空列表上应该能正常工作。编辑：抱歉，刚看到您对代码的修改，是的，这很好。 - Thomas Walther
1
#define arraysize(x)  (sizeof(x) / sizeof(x[0])) // put this before main

int main() {
    bool duplicate = false; 
    int a[11] = {1,2,3,4,5,11,11,11,11,16,16}; // doesnt have to be sorted
    int b[11];
    int index = 0;

    for(int i = 0; i < arraysize(a); i++) { // looping through the main array
        for(int j = 0; j < index; j++) { // looping through the target array where we know we have data. if we haven't found anything yet, this wont loop
            if(a[i] == b[j]) { // if the target array contains the object, no need to continue further. 
                duplicate = true;
                break; // break from this loop
            }
        }
        if(!duplicate) { // if our value wasn't found in 'b' we will add this non-dublicate at index
           b[index] = a[i];
           index++;
        }
        duplicate = false; // restart
    }
    // optional 
    int c[index]; // index will be the number of objects we have in b

    for(int k = 0; k < index; k++) {
        c[k] = b[k];
    }
}

如果你真的必须这样做，你可以创建一个新的数组，使其大小正确，并将其复制到其中。

正如你所看到的，C语言是一种非常基础（但强大）的语言，如果可以的话，最好使用向量来存储对象（例如c++的std::vector），它可以根据需要轻松增加大小。

但只要你只使用少量的整数，你就不会失去太多。如果你有大量的数据，你可以使用"malloc()"在堆上分配数组，并选择一个较小的大小（可能是原始源数组大小的一半），然后随着添加更多对象而增加（使用realloc()）。重新分配内存也有一些缺点，但这是你必须做出的决定——快速但分配比你需要的更多的数据？还是慢一些，分配你需要的确切数量的元素（由于malloc()在某些情况下可能分配比你需要的更多的数据，因此你无法控制）。

1
//gcc -Wall q2.cc -o q2 && q2                                                                             

//Write a program to remove duplicates from a sorted array.                                               

/*                                                                                                        
  The basic idea of our algorithm is to compare 2 adjacent values and determine if they                   
are the same.  If they are not the same and we weren't already looking previusly at adjacent pairs        
that were the same, then we output the value at the current index.  The algorithm does everything         
in-place and doesn't allocate any new memory.  It outputs the unique values into the input array.         
 */                                                                                                       

#include <stdio.h>                                                                                        
#include <assert.h>                                                                                       

int remove_dups(int *arr, int n)                                                                          
{                                                                                                         
        int idx = 0, odx = -1;                                                                            
        bool dup = false;                                                                                 
        while (idx < n)                                                                                   
        {                                                                                                 
                if (arr[idx] != arr[idx+1])                                                               
                {                                                                                         
                        if (dup)                                                                          
                                dup = false;                                                              
                        else                                                                              
                        {                                                                                 
                                arr[++odx] = arr[idx];                                                    
                        }                                                                                 
                } else                                                                                    
                        dup = true;                                                                       

                idx++;                                                                                    
        }                                                                                                 

        return (odx == -1) ? -1 : ++odx;                                                                  
}                                                                                                         

int main(int argc, char *argv[])                                                                          
{                                                                                                         
        int a[] = {31,44,44,67,67,99,99,100,101};                                                         
        int k = remove_dups(a,9);                                                                         
        assert(k == 3);                                                                                   
        for (int i = 0;i<k;i++)                                                                           
                printf("%d ",a[i]);                                                                       

        printf("\n\n");                                                                                   
        int b[] = {-5,-3,-2,-2,-2,-2,1,3,5,5,18,18};                                                      
        k = remove_dups(b,12);                                                                            
        assert(k == 4);                                                                                   
        for (int i = 0;i<k;i++)                                                                           
                printf("%d ",b[i]);                                                                       

        printf("\n\n");                                                                                   
        int c[] = {1,2,3,4,5,6,7,8,9};                                                                    
        k = remove_dups(c,9);                                                                             
        assert(k == 9);                                                                                   
        for (int i = 0;i<k;i++)                                                                           
                printf("%d ",c[i]);                                                                       

        return 0;                                                                                         
}
0

int a[11]={1,2,3,4,5,11,11,11,11,16,16};

由于这个数组是有序数组，您可以通过以下代码轻松实现。

int LengthofArray = 11;

//First elemnt can not be a duplicate so exclude the same and start from i = 1 than 0.

for(int i = 1; i < LengthofArray; i++);
{
   if(a[i] == a[i-1])
      RemoveArrayElementatIndex(i);
}

//function is used to remove the elements in the same as index passed to remove.

RemoveArrayElementatIndex(int i)
{
   int k  = 0;

   if(i <=0)
   return;


   k = i;
   int j =1; // variable is used to next item(offset) in the array from k.

   //Move the next items to the array    
   //if its last item then the length of the array is updated directly, eg. incase i = 10.

   while((k+j) < LengthofArray)
   { 
     if(a[k] == a[k+j])
     {
         //increment only j , as another duplicate in this array
         j = j +1 ;
     }
     else
     {
         a[k] = a[k+j];
         //increment only k , as offset remains same
         k = k + 1;   
     }

   }   

   //set the new length of the array . 
   LengthofArray = k; 

}
0
你可以利用stdlib.h中的qsort来确保你的数组按升序排序，从而消除嵌套循环的需要。
请注意，qsort需要一个指向函数的指针（在这个例子中是int_cmp），我已经在下面包含了它。
这个函数int_array_unique返回不带重复项的数组，即“原地”覆盖原始数组，并通过pn指针返回不带重复项的数组的长度。
/**
 * Return unique version of int array (duplicates removed)
 */
int int_array_unique(int *array, size_t *pn)
{
    size_t n = *pn;

    /* return err code 1 if a zero length array is passed in */
    if (n == 0) return 1;

    int i;
    /* count the no. of unique array values */
    int c=0;

    /* sort input array so any duplicate values will be positioned next to each
     * other */
    qsort(array, n, sizeof(int), int_cmp);

    /* size of the unique array is unknown at this point, but the output array
     * can be no larger than the input array. Note, the correct length of the
     * data is returned via pn */
    int *tmp_array = calloc(n, sizeof(int));

    tmp_array[c] = array[0];
    c++;

    for (i=1; i<n; i++) {
        /* true if consecutive values are not equal */
        if ( array[i] != array[i-1]) {
            tmp_array[c] = array[i];
            c++;
        }
    }

    memmove(array, tmp_array, n*sizeof(int));

    free(tmp_array);

    /* set return parameter to length of data (e.g. no. of valid integers not
     * actual allocated array length) of the uniqe array */
    *pn = c;

    return 0;
}

/* qsort int comparison function */
int int_cmp(const void *a, const void *b)
{
    const int *ia = (const int *)a; // casting pointer types
    const int *ib = (const int *)b;

    /* integer comparison: returns negative if b > a
    and positive if a > b */
    return *ia  - *ib;
}
实际上，只需使用Jonathan的答案-它更好。 - bph
0
你应该创建一个新数组，并在插入新元素之前检查数组是否包含你要插入的元素。
0
问题不太清楚。但是，如果您想要删除重复项，可以使用嵌套的“for”循环，并删除所有出现超过一次的值。
看看我的回答，可能是 @K_K 想表达的意思。 - chikuba
0

C语言没有内置的数据类型支持您想要的 -- 您需要创建自己的数据类型。

0

将满足小条件的数组元素存储到新数组中 **只需运行一次，100%有效 !)将第一个值存储到数组中

II)存储另一个元素并检查之前存储的值..

III)如果存在，则跳过该元素--并检查下一个元素并存储

以下代码可以运行，您将更好地理解

int main()
{

    int a[10],b[10],i,n,j=0,pos=0;
    printf("\n enter a n value ");
    scanf("%d",&n);
    printf("\n enter a array value");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);//gets the arry value
    }

   for(i=0;i<n;i++)

   {
    if(check(a[i],pos,b)==0)//checks array each value its exits or not
    {
        b[j]=a[i];
        j++;
        pos++;//count the size of new storing element
    }
   }
    printf("\n after updating array");

    for(j=0;j<pos;j++)
    {
        printf("\n %d",b[j]);
    }   return 0;

    }
   int check(int x,int pos,int b[])
{    int m=0,i;
    for(i=0;i<pos;i++)//checking the already only stored element
    {
        if(b[i]==x)
        {
           m++; //already exists increment the m value
        }
    }
    return m;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接