Thread: Problem with linked list ADT and incomplete structure

  1. #1
    Prawntoast
    Join Date
    Apr 2005
    Posts
    3

    Problem with linked list ADT and incomplete structure

    Hi,

    I am having trouble with a linked list ADT implemtation that uses incomplete structures ie pointers to structures. The code for this ADT was provided for us and I can't get it to work/compile. The assignment was to use the provided ADT to manipulate linked lists. I have created another linked list ADT's that works but doesn't use incomplete structures. It is being very difficult to explore this usage when the provided code doesn't work.

    Below is the code that was provided to us as a working example but it doesn't

    Any help with what is wrong with the code or other examples of similar implementaions would be greatly appreciated.


    Code:
    // list.h - Linked List ADT
    
    #ifndef _LIST_H_
    #define _LIST_H_
    struct List;
    typedef struct ListNode *Position;
    List *ListConstruct();  // NULL if fails
    void ListDestroy(List *l);
    bool ListEmpty(const List *l);
    Position ListHead(const List *l);
    Position ListFirst(const List *l);
    Position ListLast(const List *l);
    Position ListAdvance(const List *l, Position p);
    Position ListPrevious(const List *l, Position p);
    void *ListRetrieve(const List *l, Position p);
    bool ListInsert(List *l, Position p, void *item);
    void ListDelete(List *l, Position p);
    typedef void ListCallback(const void *);
    void ListTraverse(const List *l, ListCallback *fn, bool fwd);
    #endif

    Code:
    // list.cpp - Linked List ADT
    
    #include <stdlib.h>
    #include "list.h"
    
    struct List {
        ListNode *head;
    };
    
    struct ListNode {
        void *item;
        ListNode *next;
    };
    
    static void reverse(Position p, ListCallback fn);
    
    List *ListConstruct() {
        List *l;
    
        l = (List *)malloc(sizeof(List));
        if (l == NULL) {
            return NULL;  // No memory
        }
        l->head = NULL;
        return l;
    }
    
    void ListDestroy(List *l) {
        while (!ListEmpty(l)) {
            ListDelete(l, ListFirst(l));
        }
        free(l); 
    }
    
    bool ListEmpty(const List *l) {
        return l->head == NULL;
    }
    
    Position ListHead(const List *l) {
        return NULL;
    }
    
    Position ListFirst(const List *l) {
        return l->head;
    }
    
    Position ListLast(const List *l) {
        Position p;
    
        p = l->head;
        if (p == NULL) {
           return NULL;
        }
        while (p->next != NULL) {
            p = p->next;
        }
        return p;
    }
    
    Position ListAdvance(const List *l, Position p) {
        if (p == NULL) {
    		p = l->head;
    	}
    	else {
            p = p->next;
        }
        return p;
    }
    
    Position ListPrevious(const List *l, Position p) {
        ListNode *tmp;
    
        if (p == NULL || l->head == p) {
            return NULL;
        }
        tmp = l->head;
        while (tmp != NULL && tmp->next != p) {
            tmp = tmp->next;
        }
        return tmp;
    }
    
    void *ListRetrieve(const List *l, Position p) {
        if (p == NULL ) {
            return NULL;
        }
        return p->item;
    }
    
    bool ListInsert(List *l, Position p, void *item) {
        ListNode *tmp;
    
        tmp = (ListNode *)malloc(sizeof(ListNode));
        if (tmp == NULL) {
            return false;  // No memory
        }
        tmp->item = item;
        if (p == NULL) { // insert at head
            tmp->next = l->head;
            l->head = tmp;
        }
        else {
            tmp->next = p->next;
            p->next = tmp;
        }
        return true;
    }
    
    void ListDelete(List *l, Position p) {
        ListNode *prev;
    
        if (p == NULL) {
            return;  // For safety
        }
        prev = ListPrevious(l, p);
        if (prev == NULL) {  // must be head node
            l->head = p->next;
        }
        else {
            prev->next = p->next;
        }
        free(p);
    }
    
    void ListTraverse(const List *l, ListCallback fn, bool fwd) {
        ListNode *p;
    
        if (fwd) {
            for (p = l->head; p != NULL; p = p->next) {
                fn(p->item);
            }
        }
        else { 
            reverse(l->head, fn);
        }
    }
    
    static void reverse(Position p, ListCallback fn) {
        if (p != NULL) {
            reverse(p->next, fn);
            fn(p->item);
        }
    }


    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include "list.h"
    
    //the callback function
    void printname(void *ptr) {
    	printf("%s\n", (char *)ptr);
    }
    
    int main() {
    	List *l;
    		position p;
    
    		if  ((l = ListConstruct()) == NULL) {
    		exit(EXIT_FAILURE); 	//unable to create list
    	}
    	p = ListHead(l); // start at front of enpty list
    	
    	//insert an item at the front
    	if (!ListInsert(l,p, "Freddy")) {
    		exit(EXIT_FAILURE);
    	}
    	//insert another item after that - move position first
    
    	p = ListNext(l,p);
    	if (!ListInsert(l, p, "Billy")) {
    		exit(EXIT_FAILURE);
    	}
    
    	//now insert a third one before the last
    	if (!ListInsert(l, p, "Johnny")) {
    		exit(EXIT_FAILURE);
    	}
    
    	//Finally the last one at the end
    	p=ListLast(l);
    	if (!ListInsert(l, p, "Mickey")) {
    		exit(EXIT_FAILURE);
    	}
    
    	// Now print out the list in the forward direction
    
    	ListTraverse(l, printname, true);
    
    	//destroy the list before finishing
    	ListDestroy(l);
    	return 0;
    }
    Thanks for your help

    PT

  2. #2
    ---
    Join Date
    May 2004
    Posts
    1,379
    Could you possibly narrow it down a little?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM