CODEWITHSUNDEEP
carrayssegmentation-fault
joansky
joansky

Reputation: 11

Help: Insert elements into array in C!

Here is my code for merging unique elements from array B into array A.

For example:

Input: A={1, 3, 5, 7, 9}, B={2, 4, 6, 9}

Output: A={1, 2, 3, 4, 5, 6, 7, 9}

But I got segmentation fault in line 46. I am assuming it's the array bound problem, but could not figure it out. Any ideas? 

#include <stdio.h>
#define MAXSIZE 100
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
int length;
}SqList;

void CreateList(SqList *L, int n){
L->length=n;
printf("\ninput %d data: ", n);
int i;
for(i=0;i<n;i++)
    scanf("%d", &L->data[i]);
}   

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


ElemType GetElem(SqList *L,int i){
return L->data[i];
}

int LocateElem(SqList *L, ElemType e){
int i;
for(i=1;i<=L->length;i++){
    if(L->data[i]==e){
       return i;
       break;
    }
    else return 0;
}
}

void ListInsert(SqList *L, ElemType e){
int n = L->length;
n++;
L->length=n;     
L->data[n]=e;                        // Segmentation Fault Here !
}


void merge(SqList *La, SqList *Lb){
int i;
ElemType e;
for(i=0;i<Lb->length;i++){
    e=GetElem(&Lb,i);   
    if(!LocateElem(&La,e))
        ListInsert(&La,e);
}
}

int main(){
SqList La,Lb;
int n1,n2;
printf("\nInput number for La: ");
scanf("%d",&n1);
CreateList(&La,n1);
printf("\nInput number for Lb: ");
scanf("%d",&n2);
CreateList(&Lb,n2);
printf("Here is La:\n");
PrintList(&La);
printf("Here is Lb:\n");
PrintList(&Lb);
merge(&La,&Lb);
printf("Here is merged list:\n");
PrintList(&La);

return 0;
}

Upvotes: 0

Views: 1421

Answers (5)

ShinTakezou
ShinTakezou

Reputation: 9671

You are using some & too much in the merge code

void merge(SqList *La, SqList *Lb){
  int i;
  ElemType e;
  for(i=0;i<Lb->length;i++){
    e=GetElem(Lb,i);   
    if(!LocateElem(La,e))
      ListInsert(La,e);
  }
}

then it does not segfault, but I have no checked if the "logic" is right (I suppose it is)

Add

Also, the ListInsert needs to be fixed:

void ListInsert(SqList *L, ElemType e){
  int n = L->length;
  L->data[n]=e;
  L->length++;
}

Your version skip an array element, since you use the "incremented size" to index the new element, while a new inserted value must be put at index L->length, and then you need incrementing the length of the array (last element of an array of size N is N-1, so incrementing size to N+1, the last element will have index N).

Of course you do not check array bounds, so you can get trouble if you insert more than MAXSIZE elements.

Add 2

Your LocateElem needs fixing too:

int LocateElem(SqList *L, ElemType e){
  int i;
  for(i=1;i<=L->length;i++){
    if(L->data[i]==e){
      return i;
    }
  }
  return 0;
}

(I've kept your idea of using 0 as special value for not found, though read the comment about it and the MAXSIZE speach; moreover, more of your code need fixing to use this consistently). Here the fix is about the fact that you returned when you found the first element not equal to e, while (I imagine) you want to return 0 iff you do not find the element, or anything not-0 if you find it. This fixed code explores the whole array (starting from 1, if you reserve the 0 index for special meaning)

Upvotes: 2

Jens
Jens

Reputation: 72697

The LocateElem function looks buggy to me. Why does it return 0 if the first test in the loop fails? And why a break after the return statement? A few lines have been shuffled it appears... the break should go and the return 0 moved after the for block.

Upvotes: 0

Tugrul Ates
Tugrul Ates

Reputation: 9687

Here are a few errors which may be the cause of your problem:

int LocateElem(SqList *L, ElemType e){
int i;
for(i=1;i<=L->length;i++){
    if(L->data[i]==e){           // <-- You need to check data[i-1]
       return i;                 //     since you span [1,length] (off by one)
       break;
    }
    else return 0;               // <-- This goes to outside of the loop,
}                                //     otherwise only the first item is queried
}

void ListInsert(SqList *L, ElemType e){
int n = L->length;
n++;
L->length=n;     
L->data[n]=e;                    // <-- You want to modify data[n-1]
}                                //     since n is already incremented here

Upvotes: 0

Rudy Velthuis
Rudy Velthuis

Reputation: 28826

if length is n, then only elements 0 up to n-1 should be used. Of course you could also be writing past MAXLIST-1. You should add code to check than L->length <= MAXLIST at all times.

I do wonder why you chose this rather complex approach. And I would rename ListInsert to ListAppend, since you only add to the end of a list.

Upvotes: 1

Doa
Doa

Reputation: 2015

You have to check that n does not exceed MAXSIZE. The segmentation fault is most likely caused by a buffer overflow.

Upvotes: 1

Related Questions