fork download

copy

Make whatever changes are necessary so that the running time of every operation except icopy and idelete is O(1). 
You may assume that the following restriction is added to the interface for
 
iappend_destroy(il1,il2):
 
   il1 and il2 must not be the same ilist.
 
You may not use recursion or arrays.
 
 
 
 
 
#include "ilist_destructive.h"
#include <stdlib.h>
 
 
 
// The ilist ADT is a pointer to this secret struct
struct ilist_ADT{
    struct ilist_ADT *rest;
    struct ilist_ADT *append;
    int first;    
    int length; 
}
;
 
 
 
// 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) {  
  if(iempty_huh(il)) {
      ilist temp = malloc(sizeof(struct ilist_ADT));
       temp->rest = iempty();
       temp->length = 1;
       temp->first = in;
       temp->append = temp;
       il = temp;       
       return il;
        }
   else{
    ilist temp2 = malloc(sizeof(struct ilist_ADT));
    temp2->length = il->length;
    temp2->first = il->first;
    temp2->rest = il->rest;
    temp2->append = il->append;
    il->length = ilength(il) + 1;
    il->rest = temp2;
    il->first = in;
    il->append = temp2->append;
    return il;
    }
}
 
 
// ifirst returns the first element of il
int ifirst(ilist il){
   return il->first;
}
 
 
ilist irest(ilist il){
   return il->rest;
   }
 
// irest returns il with first element removed
ilist irest_destroy(ilist il){
   ilist temp = il->rest;
   if(iempty_huh(temp)) {
                free(il); return temp;
   }
 
   il->first = temp->first;
   il->length = temp->length;  
   il->rest = temp->rest;
   free(temp);
   return il;
   }
 
 
 
 
 
// ilist returns an empty ilist
// we have to use a function because struct ilist_node is secret
ilist iempty(){
   return NULL;
}
 
// test for empty ilist
int iempty_huh(ilist il){
   return il == NULL;
}
 
 
ilist icopy(ilist il){
  ilist temp = iempty();
  ilist temp2 = iempty();
  ilist a;
  while (!iempty_huh(il)){
  temp = icons_destroy(ifirst(il), temp);
  il = il->rest;
  }
  a = temp;
  while (!iempty_huh(temp)){
  temp2 = icons_destroy(ifirst(temp), temp2);
  temp = temp->rest;
  }
  idelete(a);
  return temp2;
  }
 
 
 
// computes the number of elements in il
 int ilength(ilist il){
 if(iempty_huh(il)){
 return 0;
 }
 else{
 return il->length;
 }
 }
 
ilist iappend_destroy(ilist il1, ilist il2){
    if (iempty_huh(il1)&&iempty_huh(il2))
    return il1;
 
    if (il1 == il2)
    il2 = icopy(il2);     
 
    if(iempty_huh(il1))
    return il2;         
 
    ilist temp = il1;
    temp = temp->append;
    temp->length = temp->length + ilength(il2);
    temp->rest = il2;        
    temp = temp->rest;                
    return il1;
}
 
 
// free memory for entire ilist
void idelete(ilist il){
   while (il != NULL) { 
      ilist next = il->rest;
      free(il);
      il = next;
   }
}

prog.cpp:14:31: error: ilist_destructive.h: No such file or directory
prog.cpp:1: error: ‘Make’ does not name a type
In file included from prog.cpp:15:
/usr/include/stdlib.h:140: error: ‘size_t’ does not name a type
In file included from prog.cpp:15:
/usr/include/stdlib.h:337: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:367: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:471: error: ‘size_t’ was not declared in this scope
/usr/include/stdlib.h:471: error: expected ‘,’ or ‘;’ before ‘throw’
/usr/include/stdlib.h:473: error: ‘size_t’ was not declared in this scope
/usr/include/stdlib.h:473: error: ‘size_t’ was not declared in this scope
/usr/include/stdlib.h:473: error: initializer expression list treated as compound expression
/usr/include/stdlib.h:474: error: expected ‘,’ or ‘;’ before ‘throw’
/usr/include/stdlib.h:485: error: ‘size_t’ has not been declared
In file included from /usr/include/stdlib.h:497,
                 from prog.cpp:15:
/usr/include/alloca.h:33: error: ‘size_t’ was not declared in this scope
/usr/include/alloca.h:33: error: expected ‘,’ or ‘;’ before ‘throw’
In file included from prog.cpp:15:
/usr/include/stdlib.h:502: error: ‘size_t’ was not declared in this scope
/usr/include/stdlib.h:502: error: expected ‘,’ or ‘;’ before ‘throw’
/usr/include/stdlib.h:507: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:507: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:684: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:684: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:689: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:689: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:692: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:692: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:767: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:770: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:774: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:778: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:787: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:791: error: ‘size_t’ has not been declared
/usr/include/stdlib.h:798: error: ‘size_t’ does not name a type
/usr/include/stdlib.h:801: error: ‘size_t’ does not name a type
/usr/include/stdlib.h:864: error: ‘size_t’ has not been declared
In file included from /usr/include/stdlib.h:882,
                 from prog.cpp:15:
/usr/include/bits/stdlib.h:26: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h:30: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h: In function ‘char* realpath(const char*, char*)’:
/usr/include/bits/stdlib.h:40: error: ‘size_t’ was not declared in this scope
/usr/include/bits/stdlib.h: At global scope:
/usr/include/bits/stdlib.h:53: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h:54: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h:55: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h:58: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h:58: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h:65: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h: In function ‘int ptsname_r(int, char*, int)’:
/usr/include/bits/stdlib.h:67: error: ‘size_t’ was not declared in this scope
/usr/include/bits/stdlib.h: At global scope:
/usr/include/bits/stdlib.h:78: error: ‘size_t’ has not been declared
/usr/include/bits/stdlib.h: In function ‘int wctomb(char*, wchar_t)’:
/usr/include/bits/stdlib.h:93: error: ‘size_t’ was not declared in this scope
/usr/include/bits/stdlib.h: At global scope:
/usr/include/bits/stdlib.h:99: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:102: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:106: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:113: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:131: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:134: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:138: error: ‘size_t’ does not name a type
/usr/include/bits/stdlib.h:144: error: ‘size_t’ does not name a type
prog.cpp:32: error: ‘ilist’ does not name a type
prog.cpp:58: error: ‘ilist’ was not declared in this scope
prog.cpp:58: error: expected ‘,’ or ‘;’ before ‘{’ token
prog.cpp:63: error: ‘ilist’ does not name a type
prog.cpp:68: error: ‘ilist’ does not name a type
prog.cpp:87: error: ‘ilist’ does not name a type
prog.cpp:92: error: ‘ilist’ was not declared in this scope
prog.cpp:92: error: expected ‘,’ or ‘;’ before ‘{’ token
prog.cpp:97: error: ‘ilist’ does not name a type
prog.cpp:117: error: ‘ilist’ was not declared in this scope
prog.cpp:117: error: expected ‘,’ or ‘;’ before ‘{’ token

Standard output is empty