深拷貝 - 一個無效**的元素 - 結構

Question

下面的成員是代碼，

/****** list.h **********/ 
#include<stddef.h> 
#include<stdlib.h> 
#include<string.h> 
#include<stdio.h> 

/***************** Usage-start ************/ 
typedef enum{false, true}bool; 
typedef enum {CREATE_NEW_LIST, DOUBLE_THE_LIST, HALF_THE_LIST}Op; 

#if defined(ARRAY) 

    /* To ensure Encapsulation(i.e., maintain invariants of array) */ 
    typedef struct List List; 

#elif defined(LINKED_LIST) 

    /* To ensure Encapsulation(i.e., maintain invariants of linked list) */ 
    /* User will not get access to node*/ 
    typedef struct List List; 


#else 
    #error "Wrong list implementation macro name !!!" 
#endif 


void insertItem(List *, void *newItem); 
void *deleteItem(List *, int listIndex); 
List* createList(List *, Op opType); 

---

/************* arrayImpl.c ***********/ 


#include"list.h" 


/************ Representation - start ************/ 
typedef struct List{ 
    void **array; 

    /* Following members for Housekeeping - Array enhancement*/ 
    int lastItemPosition; 
    int size; 
}List; 

#define INITIAL_LIST_SIZE 50 
List *createList(List *list, Op opType){ 
    if(opType == CREATE_NEW_LIST){ 
    list = malloc(sizeof(List)); 
    list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*)); 


    /* Is it safe to initialise zero to array of pointers? */ 
    list->array = memset(list->array, 0, INITIAL_LIST_SIZE*sizeof(void *)); 

    list->lastItemPosition = -1; 
    list->size = INITIAL_LIST_SIZE; 
    }else if(opType == DOUBLE_THE_LIST){ 

    list->array = realloc(list->array, 2*(list->size)*sizeof(void *)); 

    list->lastItemPosition = list->lastItemPosition;; 
    list->size = 2*(list->size); 
    }else if(opType == HALF_THE_LIST){ 

    list->array = realloc(list->array, ((list->size)/2)*sizeof(void *)); 

    list->lastItemPosition = list->lastItemPosition; 
    list->size = (list->size)/2; 
    } 

    return list; 

} 

---

/********** arrayImpl.c*********/ 
void *deleteItem(List *arrayList, int listIndex){ 
    void *returnElement; //Deep copy before freeing the object 
    free(arrayList->array[listIndex]); 

    /* Delete operation - O(n) operation */ 
    for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){ 
    arrayList->array[accumulator] = arrayList->array[++accumulator]; 
    } 
    arrayList->lastItemPosition--; 


    /* House keeping - Half the list */ 
    if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */ 
    if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){ 
     arrayList = createList(arrayList, HALF_THE_LIST); 
    } 
    } 
    return returnElement; 

} 

---

/***************arrayImpl.c***************/ 
void insertItem(List *arrayList, void *newItem){ 

    /* House keeping - Enhance the array */ 
    if(arrayList->lastItemPosition + 1 == arrayList->size){ 
    arrayList = createList(arrayList, DOUBLE_THE_LIST); 
    } 


    /* Insert new element - O(1) operation */ 
    arrayList->array[++(arrayList->lastItemPosition)] = newItem; 


    return; 
} 

---

用戶代碼，

#include"list.h" 

int main(void){ 

    List *arrayList = createList((List *)NULL, CREATE_NEW_LIST); 


    if (arrayList == (List *)0){ 
    fprintf(stderr, "Unable to create list \n"); 
    exit(1); //Nothing else to do without arrayList 
    } 

    // Objects should only be on heap 
    int *object1 = malloc(sizeof(int)); 
    *object1 = 777; 
    insertItem(arrayList, object1); 

    int *object2 = malloc(sizeof(int)); 
    *object2 = 888; 
    insertItem(arrayList, object2); 

    object1 = deleteItem(arrayList, 0); 
} 

---

我想重新使用List抽象寫Stack抽象，與push()/pop()

#include"../list/list.h" 
typedef struct Stack{ 
    List *stack; 
}Stack; 

問題如下：

在deleteItem()功能，如何深度複製arrayList->array[listIndex]並返回returnElement從deleteItem()功能？

pop()將調用deleteItem()

注：編譯>gcc -DARRAY main.c arrayImpl.c

Answer 1

insertItem沒有分配的項目 - 所以deleteItem不應該free它。

void *deleteItem(List *arrayList, int listIndex){ 
    void *returnElement = arrayList->array[listIndex]; 

    /* Delete operation - O(n) operation */ 
    .... 

    /* House keeping - Half the list */ 
    .... 

    return returnElement; 
}