I am working on my reverse function, but still didn\'t work, somebody can look m

Question

I am working on my reverse function, but still didn't work, somebody can look my code and check it?

test without reverse function looks good, so I think my reverse function is incorrect. But I don't know how to fix it.

reverse code:

---------------------------------------------

void reverseListDeque(ListDeque *d)
{
   struct ListDeque *head;
   struct DLink *current,*prev, *next;
   head = d;
   current=head->head;
   prev=NULL;
   while(current!=NULL)
   {
       next=current->next;
       current->next=prev;
       prev=current;
       current=next;
   }
   head->head = prev;

}

full code:

---------------------------------------------

#include
#include
#include
#include "ListDeque.h"

/*   Create a link for a value.
   Use this function in your add operations to make it easier to allocate links

   param:    val       the value to store in the newy created link
   pre:   none
   post:   a link is allocated on the heap, storing the argument value
   ret:   the newly allocated link
*/
DLink* _createLink(TYPE val)
{
   DLink* lnk = (DLink*) malloc(sizeof(DLink));
    assert(lnk != 0);
  
   lnk->value = val;
   return lnk;
}

/* ************************************************************************
   Basic Operations
************************************************************************ */

/* Initializes a deque.

   param:    d       pointer to the deque
   pre:   d is not null
   post:   size, head, and tail are initialized
*/
void initListDeque(ListDeque* d)
{
   assert(d!=NULL);
  
   d->size = 0;
  
   d->head = (struct DLink *) malloc(sizeof(struct DLink));
   assert(d->head!=0);
   d->tail = (struct DLink *) malloc(sizeof(struct DLink));
   assert(d->tail!=0);
  
   d->head->prev = 0;
   d->head->next = d->tail;
   d->tail->next = 0;
   d->tail->prev = d->head;
}

/*   De-allocate all links of the deque.
   Write this function in terms of a remove function, such as removeBack.

   param:    d       pointer to the deque
   pre:   d is not null
   post:   All links are de-allocated
*/
void freeListDeque(ListDeque* d)
{  
assert(d!=NULL && !isEmptyListDeque(d));
   assert(d->size!=0);
  
   while(d->size>0)
   {
       removeFrontListDeque(d);
   }
   free(d->head);
   free(d->tail);
   d->head = d->tail =NULL;
      
   /*FIXME you will write this function */
}

/* Check whether the deque is empty.

   param:    d       pointer to the deque
   pre:   d is not null
   ret:    1 if the deque is empty. Otherwise, 0.
*/
int isEmptyListDeque(ListDeque *d) {

   /*FIXME you will write this function */
   return !(d->size) ;
}

/* Get the value stored in the link at the front of the deque

   param:    d       pointer to the deque
   pre:   d is not null
   pre:   d is not empty
   post:   none
   ret:    value of the front of the deque
*/
TYPE frontListDeque (ListDeque *d)
{
assert(!isEmptyListDeque(d));
assert(d!=NULL);
return d->head->next->value;
}

/* Get the value stored in the link at the back of the deque

   param:    d       pointer to the deque
   pre:   d is not null
   pre:   d is not empty
   post:   none
   ret:    value of the back of the deque
*/
TYPE backListDeque(ListDeque *d)
{
assert(d!=NULL);
assert(!isEmptyListDeque(d));
return d->tail->prev->value;
   /*FIXME you will write this function */
}

/*   Adds a link AFTER another link.
   Write your other add functions in terms of addAfter and addBefore when possible.

   param:    d           pointer to the deque
   param:    addAfter   pointer to the existing link in the deque
   param:    newLnk       pointer to the new link to add after the existing link
   pre:   d is not null
   pre:    newLnk has been properly initialized
   pre:   addAfter is in the deque if it is not a NULL pointer
   post:   newLnk is added into the deque AFTER the existing link
*/
void addLinkAfterListDeque(ListDeque* d, DLink* addAfter, DLink* newLnk)
{
   assert(d!=NULL);
   newLnk->prev= addAfter->prev;
   newLnk->next= addAfter;
  
   addAfter->prev->next=newLnk;
   addAfter->prev= newLnk;
  
   d->size++;
  
   /*FIXME you will write this function */
}

/* Adds a link BEFORE another link.
   Write your other add functions in terms of addAfter and addBefore when possible.

   param:    d           pointer to the deque
   param:    addBefore   pointer to the existing link in the deque
   param:    newLnk       pointer to the new link to add before the existing link
   pre:   d is not null
   pre:    newLnk has been properly initialized
   pre:   addBefore is in the deque if it is not a NULL pointer
   post:   newLnk is added into the deque BEFORE the existing link
*/
void addLinkBeforeListDeque(ListDeque* d, DLink* addBefore, DLink* newLnk)
{
   assert(d!=NULL);
   newLnk->next= addBefore;
   newLnk->prev= addBefore->prev;
  
   addBefore->prev->next = newLnk;
   addBefore->prev = newLnk;
  
   d->size++;
  
   /*FIXME you will write this function */
}

/*   Remove a link from the deque.
   Write our other remove functions in terms of this function when possible.
   Be careful not to use a pointer that you have already freed when returning.

   param:    d       pointer to the deque
   param:    lnk       pointer to the link to be removed
   pre:   d is not null
   pre:   d is not empty
   pre:   lnk is in the deque
   post:   lnk is removed from the deque
   ret:   The pointer which follows lnk
*/
DLink* removeLinkListDeque(ListDeque *d, DLink *lnk)
{
   assert(d!=NULL);
   assert(!isEmptyListDeque(d));
   assert(lnk!=NULL);
   lnk->prev->next = lnk->next;
   lnk->next->prev = lnk->prev;
   free(lnk);
   d->size--;
   return 0;
   /*FIXME you will write this function */
  
}

/* ************************************************************************
   Deque Interface
************************************************************************ */

/*   Adds a link to the back of the deque.
   Write this function in terms of addLinkAfter() when possible.

   param:    d       pointer to the deque
   param:    val       value for the link to be added
   pre:   d is not null
   post:   a link storing val is added to the back of the deque
*/
void addBackListDeque (ListDeque *d, TYPE val)
{
   struct DLink* newLnk = (struct DLink*) malloc(sizeof(struct DLink));
   assert(d!=NULL);
   newLnk->value = val;
   addLinkAfterListDeque(d, d->tail, newLnk);
  
   /*FIXME you will write this function */
}

/*   Adds a link to the front of the deque.
   Write this function in terms of addLinkBefore when possible.

   param:    d       pointer to the deque
   param:    val       value for the link to be added
   pre:   d is not null
   post:   a link storing val is added to the front of the deque
*/
void addFrontListDeque(ListDeque *d, TYPE val)
{
   struct DLink* newLnk = (struct DLink*) malloc(sizeof(struct DLink));
   assert(d!=NULL);
   newLnk->value = val;
   addLinkAfterListDeque(d, d->head->next, newLnk);
  

   /*FIXME you will write this function */
}

/*   Remove the front of the deque.
   Write this function in terms of removeLinkListDeque().

   param:    d       pointer to the deque
   pre:   d is not null
   pre:   d is not empty
   post:   the front is removed from the deque
*/
void removeFrontListDeque (ListDeque *d)
{
   assert(d!=NULL);
   assert(!isEmptyListDeque(d));
   removeLinkListDeque(d,d->head->next);
  
   /*FIXME you will write this function */
}

/* Remove the back of the deque.
   Write this function in terms of removeLinkListDeque().

   param:    d       pointer to the deque
   pre:   d is not null and q is not empty
   post:   the back is removed from the deque
*/
void removeBackListDeque(ListDeque *d)
{
   assert(d!=NULL);
   assert(!isEmptyListDeque(d));
   removeLinkListDeque(d,d->tail->prev);
   /*FIXME you will write this function */
}

/* ************************************************************************
   Bag Interface
************************************************************************ */
/*   Returns whether or not the given value is stored in the deque

   param:   d       pointer to the deque
   param:   val       value that we are looking for in the deque
   ret:   1 if val is contained in d, 0 otherwise
*/
int containsListDeque(ListDeque* d, TYPE val)
{
   struct DLink *n;

   assert(d != 0);
   assert(!isEmptyListDeque(d));
   n = d->head->next;
   while(n != d->tail)
   {
       if(n->value==val)
       {
           return 1;
       }
       n=n->next;
   }
   return 0;
}

/* Removes the first occurrence of the given value from the list.

   param:   d       pointer to the deque
   param:   val       value that we are looking for in the deque
   post:   first occurrence of val is removed from the list
*/
void removeListDeque(ListDeque* d, TYPE val)
{
   assert(d!=NULL);
   assert(!isEmptyListDeque(d));
   struct DLink* n = d->head->next;
   assert(n!=0);
   while(n!=d->tail)
   {
      
   if(n->value == val)
       {
           removeLinkListDeque(d,n);
       break;
       }
       n =n->next;
   }
  
  
   /*FIXME you will write this function */
}

/* Reverse the deque. Note that careful swapping of the pointers inside each link
   (next and prev) will cause a reverse, provided head and tail are updated properly.

param: d pointer to the deque
pre: d is not null
post: the deque is reversed
*/
void reverseListDeque(ListDeque *d)
{
   struct ListDeque *head;
   struct DLink *current,*prev, *next;
   head = d;
   current=head->head;
   prev=NULL;
   while(current!=NULL)
   {
       next=current->next;
       current->next=prev;
       prev=current;
       current=next;
   }
   head->head = prev;

}
   /*FIXME you will write this function */

/*   Print the links in the deque from front to back

   param:    d       pointer to the deque
   pre:   d is not null
   post:    the links in the deque are printed from front to back
*/
void printListDeque(ListDeque *q)
{
   DLink* lnk;
   lnk = q->head;
   printf("Size = %d [ ", q->size);
   while(lnk != NULL)
   {
       printf("%c ", lnk->value);
       lnk = lnk->next;
   }
   printf("] ");
}

test code main.c :

---------------------------------------------

#include
#include
#include "ListDeque.h"

int main (int argc, const char * argv[])
{
   ListDeque testDeque;
   TYPE val1 = 'A';
   TYPE val2 = 'B';
   TYPE val3 = 'C';
   int i;

   initListDeque(&testDeque);
   printListDeque(&testDeque);
  
   addBackListDeque(&testDeque, val1); printListDeque(&testDeque);  
   addBackListDeque(&testDeque, val2); printListDeque(&testDeque);
   addBackListDeque(&testDeque, val3); printListDeque(&testDeque);
  
   printf("contains('A') = %d, contains('D') = %d ", containsListDeque(&testDeque, 'A'), containsListDeque(&testDeque, 'D'));
   printf("front() = %c, back() = %c ", frontListDeque(&testDeque), backListDeque(&testDeque));
  
   removeBackListDeque(&testDeque); printListDeque(&testDeque);
   removeBackListDeque(&testDeque); printListDeque(&testDeque);
   removeBackListDeque(&testDeque); printListDeque(&testDeque);

   for(i = 0; i < 2; ++i)
   {
       addFrontListDeque(&testDeque, val3); printListDeque(&testDeque);
       addFrontListDeque(&testDeque, val2); printListDeque(&testDeque);
       addFrontListDeque(&testDeque, val1); printListDeque(&testDeque);
   }
  
   printf("contains('B') = %d, contains('R') = %d ", containsListDeque(&testDeque, 'B'), containsListDeque(&testDeque, 'R'));
   printf("front() = %c, back() = %c ", frontListDeque(&testDeque), backListDeque(&testDeque));
  
   reverseListDeque(&testDeque); printListDeque(&testDeque);
  
   removeListDeque(&testDeque, 'B'); printListDeque(&testDeque);
   removeListDeque(&testDeque, 'D'); printListDeque(&testDeque);
  
   removeFrontListDeque(&testDeque); printListDeque(&testDeque);
   removeFrontListDeque(&testDeque); printListDeque(&testDeque);
   removeFrontListDeque(&testDeque); printListDeque(&testDeque);
   removeFrontListDeque(&testDeque); printListDeque(&testDeque);
  
   freeListDeque(&testDeque);
  
   return 0;
}

---------------------------------------------

test without reverse function:

Explanation / Answer

Answer:

void reverseListDeque(ListDeque *d)

{

DLink *temp1 = d->head;

DLink *temp2 = temp1->next;

d->head = d->tail;

d->tail = temp1;

while (temp1 != NULL)

{

DLink *t = temp1->prev;

temp1->prev = temp1->next;

temp1->next = t;

temp1 = temp2;

if (temp2)

temp2 = temp2->next;

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.