We help IT Professionals succeed at work.
Get Started

Re-ordering a linked list

GPicasso
GPicasso asked
on
405 Views
Last Modified: 2012-05-12
I think I'm screwing up something conceptually with structs and pointers
Ok so this should build a linked list and then print it..  then reverse it and print it again.
It doesn't do this for some reason.
I appear to be just destroying it or something,  posting relevant code sections

FYI:  The main file here is test.c

Also I'm just starting to learn C.. I always thought that header files were basically the same as C files, they just get included into your code... what's with the separate definitions like you see here?
/* list.c */
        #include "list.h"
        #include <stdlib.h>
        #include "fatal.h"

        /* Place in the interface file */
        struct Node
        {
            ElementType Element;
            Position    Next;
        };

        Position getPrevious(List list, Position end)
        { /*this code has been checked*/
        	Position r = list;
        	while (r->Next != end)
        	{
        		r = r->Next;

        	}
        	return r;

        }
        void
        swapValues(Position headPosition, Position tailPosition)
        { /*this code checks out ok*/
        	ElementType tempElement = 0;
        	tempElement = headPosition->Element;
        	headPosition->Element = tailPosition->Element;
        	tailPosition->Element = tempElement;

        }


        void reverseList( List currentNode)
        {
        	struct Node* previousNode = NULL;
        	struct Node* nextNode = NULL;
        	while (currentNode->Next != NULL)
        	{
        		nextNode = currentNode->Next;
        		currentNode-> Next = previousNode;
        		previousNode = currentNode;
        		currentNode = nextNode;

        	}

        }
        List
       MakeEmpty( List L )
        {
            if( L != NULL )
                DeleteList( L );
            L = malloc( sizeof( struct Node ) );
            if( L == NULL )
                FatalError( "Out of memory!" );
            L->Next = NULL;
            return L;
        }

/* START: fig3_8.txt */
        /* Return true if L is empty */

        int
        IsEmpty( List L )
        {
            return L->Next == NULL;
        }
/* END */

/* START: fig3_9.txt */
        /* Return true if P is the last position in list L */
        /* Parameter L is unused in this implementation */

        int IsLast( Position P, List L )
        {
            return P->Next == NULL;
        }
/* END */

/* START: fig3_10.txt */
        /* Return Position of X in L; NULL if not found */

        Position
        Find( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L->Next;
/* 2*/      while( P != NULL && P->Element != X )
/* 3*/          P = P->Next;

/* 4*/      return P;
        }
/* END */

/* START: fig3_11.txt */
        /* Delete from a list */
        /* Cell pointed to by P->Next is wiped out */
        /* Assume that the position is legal */
        /* Assume use of a header node */

        void
        Delete( ElementType X, List L )
        {
            Position P, TmpCell;

            P = FindPrevious( X, L );

            if( !IsLast( P, L ) )  /* Assumption of header use */
            {                      /* X is found; delete it */
                TmpCell = P->Next;
                P->Next = TmpCell->Next;  /* Bypass deleted cell */
                free( TmpCell );
            }
        }
/* END */

/* START: fig3_12.txt */
        /* If X is not found, then Next field of returned value is NULL */
        /* Assumes a header */

        Position
        FindPrevious( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L;
/* 2*/      while( P->Next != NULL && P->Next->Element != X )
/* 3*/          P = P->Next;

/* 4*/      return P;
        }
/* END */

/* START: fig3_13.txt */
        /* Insert (after legal position P) */
        /* Header implementation assumed */
        /* Parameter L is unused in this implementation */

        void
        Insert( ElementType X, List L, Position P )
        {
            Position TmpCell;

/* 1*/      TmpCell = malloc( sizeof( struct Node ) );
/* 2*/      if( TmpCell == NULL )
/* 3*/          FatalError( "Out of space!!!" );

/* 4*/      TmpCell->Element = X;
/* 5*/      TmpCell->Next = P->Next;
/* 6*/      P->Next = TmpCell;
        }
/* END */

#if 0
/* START: fig3_14.txt */
        /* Incorrect DeleteList algorithm */

        void
        DeleteList( List L )
        {
            Position P;

/* 1*/      P = L->Next;  /* Header assumed */
/* 2*/      L->Next = NULL;
/* 3*/      while( P != NULL )
            {
/* 4*/          free( P );
/* 5*/          P = P->Next;
            }
        }
/* END */
#endif

/* START: fig3_15.txt */
        /* Correct DeleteList algorithm */

        void
        DeleteList( List L )
        {
            Position P, Tmp;

/* 1*/      P = L->Next;  /* Header assumed */
/* 2*/      L->Next = NULL;
/* 3*/      while( P != NULL )
            {
/* 4*/          Tmp = P->Next;
/* 5*/          free( P );
/* 6*/          P = Tmp;
            }
        }
/* END */

        Position
        Header( List L )
        {
            return L;
        }

        Position
        First( List L )
        {
            return L->Next;
        }

        Position
        Advance( Position P )
        {
            return P->Next;
        }

        ElementType
        Retrieve( Position P )
        {
            return P->Element;
        }

Open in new window

/* test.c */
#define NULL 0
#include "list.h"
#include "fatal.h"
#include "stack.h"
#include <stdio.h>
int main()
{
	int i = 0 ;

	List list = MakeEmpty(NULL);


	for (i=1;i<=5; i++)
	{
		Insert(i, list, list);

	}
	printl(list);
	printf("REVERSING\n");


	reverseList(list);
	printl(list);
}
void printl( List list )
{
	while (!IsEmpty(list))
	{
		printf("List element: %d\n", Retrieve(First(list)));
		list = Advance(list);
	}
}

Open in new window

fatal.h
list.h
Comment
Watch Question
CERTIFIED EXPERT
Awarded 2010
Top Expert 2013
Commented:
This problem has been solved!
Unlock 1 Answer and 11 Comments.
See Answer
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE