从排序数组中移除元素的函数

Question

从排序数组中移除元素有一些问题（必须移除元素的所有实例）。当我运行我的程序时，出现分段错误。我不知道为什么会发生这种情况，因为函数remElem（int *，int *，int）其中1st arg是一个数组，第二个arg是数组的长度（当元素被移除时会改变），3rd arg是一个元素（int *，int）（用于洗牌数组的元素）和insElem（int *，int *，int）（用于插入一个元素）之前，成有序阵列。我不知道哪里出了问题，请帮助。我会提供意见的代码。也有提供意见其他一些小的问题。谢谢你提前:)

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define MAX_LEN 1000 


void initArray(int*, int); 
void printArray(int*, int); 
void swap(int*, int*); 
void insSort(int*, int); 
void insElem(int*, int*, int); 
void remElem(int*, int*, int); 
void shuffle(int*, int); 


int main() { 
    int array[MAX_LEN]; 
    int len, elem, comm; 

    srandom(time(NULL)); 

    printf("Number of elements? >> "); 
    scanf("%d", &len); 

    initArray(array, len); 

    do { 
     printf("Command? (6 for help) >> "); 
     scanf("%d", &comm); 
     switch (comm) { 
      case 1: 
       printArray(array, len); 
       break; 
      case 2: 
       shuffle(array, len); 
       break; 
      case 3: 
       insSort(array, len); 
       break; 
      case 4: 
       printf("Insert element? >> "); 
       scanf("%d", &elem); 
       insElem(array, &len, elem); 
       break; 
      case 5: 
       printf("Remove element? >> "); 
       scanf("%d", &elem); 
       remElem(array, &len, elem); 
       break; 
      case 6: 
       printf("Help:\n"); 
       printf("1 - Print\n"); 
       printf("2 - Shuffle\n"); 
       printf("3 - Sort\n"); 
       printf("4 - Insert element\n"); 
       printf("5 - Remove element\n"); 
       printf("6 - Help (this screen)\n"); 
       printf("0 - Quit\n"); 
       break; 
      case 0: 
       break; 
      default : 
       printf("Wrong input! Repeat!\n"); 
     } 
    } while (comm); 

    return EXIT_SUCCESS; 
} 


/*Initializes array with n random numbers from 0 to 9 (including)*/ 
void initArray(int a[], int n) { 
    int i; 

    for (i = 0; i < n; i++) 
     a[i] = random() % 10; 
} 


/*Prints n elements of an array*/ 
void printArray(int a[], int n) { 
    int i; 

    for (i = 0; i < n; i++) 
     printf("%d ", a[i]); 
    putchar('\n'); 
} 


/*Swaps the values of two variables*/ 
void swap(int *i, int *j) { 
    *i = *i + *j; 
    *j = *i - *j; 
    *i = *i - *j; 
    /*I saved up some memory yaaaaaaay :3 */ 
    /*I spent some processing time nooooo :| */ 
    /*Which is better... with or without tmp variable???*/ 
    /*I suppose it depends on application... clearly, this 
     method doesnt work with structures, for example*/ 
} 


/*Sorts the elements of an array using insertion sort algorythm*/ 
void insSort(int a[], int n) { 
    int i, j; 

    for (i = 1; i < n; i ++) 
     for (j = i; j > 0 && a[j] < a[j-1]; j--) 
      swap(&a[j], &a[j-1]); 
} 


/*Inserts an element into a sorted array*/ 
/*Wassn meant to be working with unsorted arrays 
    in that case unpreddictable results*/ 
void insElem(int a[], int *n, int e) { 
    int i, j; 

    (*n)++; 
    for (i = 0; a[i] < e && a[i+1] < e; i++); 

    for (j = *n; j > i + 1; j--) 
     a[j] = a[j-1]; 

    a[i+1] = e; 
} 


/*Removes an element from a sorted array*/ 
/*Wassn meant to be working with unsorted arrays 
    in that case unpreddictable results*/ 
void remElem(int a[], int *n, int e) { 
    int i, j; 

    for (i = 0; i < *n; i++) { 
     while (a[i] == e) { 
      for (j = i; j < *n; j++) 
       a[j] = a[j+1]; 
     (*n)--; 
     } 
    } 
} 


/*Shuffles the elements of an array*/ 
/*I just did this on the fly... 
    are there any known algorythms for doing this*/ 
void shuffle(int a[], int n) { 
    int i; 

    for (i = 0; i < n; i++) 
     swap(&a[rand()%n], &a[rand()%n]); 
} 

Answer 1

的以下情况可能导致出界限访问，导致未定义的行为：

 for (j = i; j < *n; j++) 
      a[j] = a[j+1]; 

请考虑a[j+1]发生什么情况j == (*n)-1。

至于swap()函数，您的聪明外观实现有整数溢出的风险，因此存在未定义的行为。只需使用一个临时变量，让编译器担心效率问题。

Answer 2

在这个循环中：

for (j = i; j < *n; j++) 
    a[j] = a[j+1]; 

当j = *n - 1，您将访问内存，数组的边界之外。这调用了未定义的行为，结果可能是任何事情，所以我相信它解释了你的崩溃。至于程序之前没有崩溃 - 以及这可以做任何事情，它也可能没有负面影响。