Списки - C (Домашнее задание)

Question

Итак, я пытаюсь реализовать следующее:

  // Destructive Abstract data type ilist

   struct ilist_ADT;
   typedef struct ilist_ADT *ilist;
   // prototype for secret implementation
   // do not rely on ilist being a pointer

   ilist iempty();
   //    returns an empty ilist

   int iempty_huh(ilist il);
   //    returns 1 (true) if il is empty
   //    returns 0 (false) if il is not empty

   int ifirst(ilist il);
   //    returns the first element in il
   //    il must not be empty

   ilist icons_destroy(int in, ilist il);
   // returns an ilist with in added as the first element of il
   // references to il cease to be valid ilists
   // the result must eventually be consumed by one of:
   //     icons_destroy, irest_destroy, idelete

   ilist irest_destroy(ilist il);
   // modifies il to remove the first element, and returns the modified ilist
   // frees the memory associated with the first element
   // references to il cease to be valid ilists
   // the result (if non-empty) must eventually be consumed by one of:
   //     icons_destroy, irest_destroy, idelete

   ilist icopy(ilist il);
   // returns a new copy of il that continues to be a valid
   // ilist with the same elements even when il is destroyed
   // the result must eventually be consumed by one of:
   //     icons_destroy, irest_destroy, idelete

   int ilength(ilist il);
   // computes the number of elements in il

   void idelete(ilist il);
   //    frees the storage for ilist
   //    all further references to il become invalid
   //    NOTE: every ilist created by icons_destroy or
   //          irest_destroy or icopy  must eventually be destroyed
   //          by being consumed by icons_destroy or
   //          irest_destroy or idelete

Сначала я фокусируюсь на значках, и у меня есть неразрушающие значки, такие как:

ilist icons(int in, ilist il) {      
   ilist r = malloc(sizeof(struct ilist_ADT));
   r->first = in;
   r->rest = il;
   r->length = 1 + ilength(il);  
   return r;

}

Какточно я сделаю это, чтобы удовлетворить реализацию?другими словами, как я могу сделать это разрушительным?

Answer 1

«Разрушительный» означает, что аргументы функции (или получателя в методе oop) могут быть изменены.Неразрушающая функция означает, что она не изменяет свои аргументы, а вместо этого возвращает измененную copy .Преимущество использования деструктивной функции заключается в том, что вам не нужно создавать эту копию, и, таким образом, вам обычно требуется меньше mallocs (в этом примере, однако, число одинаковое).

В реализации icons, которую вы предоставили, вы можете видеть, что постоянная запись сохраняет исходный ilist il действительный неизмененный список !: Любой, кто использует ilist il, не заметит, что вы что-то сделали (этоконечно, работает только с односвязными списками).

Сначала деструктивная реализация позволяет вам изменять аргументы, но также подразумевает , что вы должны изменитьаргументы в значимой форме: вы должны изменить его так, чтобы кто-то, у кого еще есть ссылка на оригинал ilist il, должен увидеть вашу модификацию.Вы можете сделать это следующим образом:

// observation: the names are not the best, i would call it destructiveICons
//   (and ->first should be called ->value)
ilist icons_destroy(int in, ilist il) {  
    ilist second = malloc(sizeof(struct ilist_ADT));
    second->length = il->length
    second->first = il->first
    second->rest = il->rest;
    il->length += 1;
    il->rest = second;
    il->first = in;
    return il;
}

Теперь кто-то другой, имеющий ссылку на ilist il, увидит элемент new-first, за которым следует элемент old-ранее-first.

Answer 2

Я думаю, что эту реализацию можно рассматривать как деструктивную (хотя я на самом деле не понимаю значение «деструктивной»).Вопрос в том, кто несет ответственность за публикацию данных.С вашей реализацией icons релиз должен быть выполнен с использованием нового дескриптора, но никогда не с использованием старого дескриптора.В этом смысле старый дескриптор больше не действителен.

Вы можете что-то изменить, поэтому старый дескриптор действительно будет непригодным для использования.Вы можете добавить поле, указывающее, является ли ilist первым в цепочке, и поддерживать его при добавлении / удалении элементов.Тогда все ваши API могут отказаться работать, если данный дескриптор не первый.