Link List Problem(just a repost) 1

sedawk · Jun 30, 2004

Hi,

Oops, I used the wrong tags for codes. Just a repost.

After keyword searching, I decided to seek help from you guys.

I am working on a simple link list, not fancy link list functions yet. The code should be fine. However, when I test the list, something strange happened: it can't display the list contents. So I grabbed an example link list program by Salem from this forum. That example can't display the link list contents! Is it caused by my compiler? I am using VC++ 6. For your convenience, I paste Salem's code and my link list here, though it seems too long.

BTW, the "genlib.h" is the library I used for New() and FreeBlock() purposes, I test it and it should be fine.

Sorry if the problem ends up as the compiler but C issues.

================ My Link List =========================

Code:

#include <stdio.h>
#include <stdlib.h>
#include "genlib.h"

#define MAXSIZE 5

typedef struct cellT {
	char ch;
	struct cellT *link;
} cellT;

struct bufferCDT {
	cellT *start;
	cellT *cursor;
};

typedef struct bufferCDT *bufferADT;

bufferADT NewBuffer(void);
void FreeBuffer(bufferADT buff);
void MoveCursorForward(bufferADT buffer);
void MoveCursorBackward(bufferADT buffer);
void MoveCursorToStart(bufferADT buffer);
void MoveCursorToEnd(bufferADT buffer);
void DisplayBuffer(bufferADT buffer);
void InsertCharacter(bufferADT buffer,char ch);

int main()
{
	int i;
	char ch;
	bufferADT head;
	head = NewBuffer();

   // this part no problem
	for (i=0; i<MAXSIZE; i++){
		InsertCharacter(head,'a');
	}
	
  // VC6++ can't display but report program clashes
	DisplayBuffer(head);   

	FreeBuffer(head);
	printf("Now buffer cleared!\n");
	return 0;
}

bufferADT NewBuffer(void)
{
	bufferADT buffer;
	buffer = New(bufferADT);
	buffer->start = New(cellT *);
	buffer->cursor = New(cellT *);
	buffer->start->link = NULL;
	return buffer;
}

void FreeBuffer(bufferADT buffer)
{
	// Both FreeBuffer versions work!
	/*
	cellT *cp, *next;
	cellT *cp;
	cp = buffer->start;
	for (next=buffer->start; next->link != NULL; next=next->link)
		FreeBlock(next);
	FreeBlock(cp);
	FreeBlock(buffer);
	*/
	cellT *cp, *next;
	cp = buffer->start;
	while (cp!=NULL) {
		next = cp->link;
		FreeBlock(cp);
		cp = next;
	}
	FreeBlock(buffer);
}

void MoveCursorForward(bufferADT buffer)
{
	if(buffer->cursor != NULL)
		buffer->cursor = buffer->cursor->link;
}

void MoveCursorBackward(bufferADT buffer)
{
	cellT *cp;
	if (buffer->cursor != buffer->start)
		cp = buffer->start;
	while(cp->link != buffer->cursor){
		cp = cp->link;
	}
	buffer->cursor=cp;
}

void MoveCursorToStart(bufferADT buffer)
{
	buffer->cursor=buffer->start;
}

void MoveCursorToEnd(bufferADT buffer)
{
	while(buffer->cursor->link !=NULL)
		MoveCursorForward(buffer);
}

void DisplayBuffer(bufferADT buffer)
{
	cellT *cp;
	for (cp=buffer->start; cp!=NULL;cp=cp->link)
		printf(" %c",cp->ch);
	printf("\n");
//	for (cp=buffer->start;cp!=buffer->cursor;cp=cp->link) {
//		printf(" ");
//	}
//	printf("^\n");
}

void InsertCharacter(bufferADT buffer,char ch)
{
	cellT *cp;
	cp = New(cellT *);
	cp->ch = ch;
	cp->link = buffer->cursor->link;
	buffer->cursor->link = cp;
	buffer->cursor = cp;
}

=================== Salem's Sample Code ===================

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node_tag {
    char            *string;
    struct node_tag *next;
} node;

/* allocate and free list nodes */
/* Add NULL checks to suit */
node *newnode ( char *string ) {
    node    *result = malloc( sizeof(*result) );
    if ( result ) {
        result->string = malloc( strlen(string)+1 );
        if ( result->string ) {
            strcpy( result->string, string );
        }
    }
    return result;
}
void delnode ( node *node ) {
    free( node->string );
    free( node );
}

/* list append */
node *append ( node *head, char *string ) {
    node    *new = newnode( string );
    if ( head == NULL ) {
        head = new;
    } else {
        node    *temp = head;
        while ( temp->next != NULL ) temp = temp->next;
        temp->next = new;
    }
    return head;
}

/* delete duplicates from a sub-list
 * return the shortened list
 */
node *del_sublist_dups ( node *head, char *match ) {
    node *this = head;  /* runs down the list */
    node *prev = NULL;  /* trails behind this by one node */
    while ( this != NULL ) {
        node *next = this->next;    /* the next node to link to and goto */
        if ( strcmp( this->string, match ) == 0 ) {
            /* delete the node */
            if ( prev == NULL ) {
                /* the first node being a special case */
                head = next;
            } else {
                /* otherwise make the list skip the current node */
                prev->next = next;
            }
            delnode( this );
        } else {
            prev = this;
        }
        this = next;
    }
    return head;
}

/* delete dups in a list
 * NB: the head element cannot change
 */
void del_dups ( node *head ) {
    while ( head != NULL ) {
        head->next = del_sublist_dups( head->next, head->string );
        head = head->next;
    }
}

void print_list ( node *list ) {
    while ( list != NULL ) {
        printf( "%s ", list->string );
        list = list->next;
    }
    printf( "\n" );
}

void free_list ( node *list ) {
    while ( list != NULL ) {
        node *next = list->next;
        delnode( list );
        list = next;
    }
}

int main (void) {
    node *list = NULL;
    list = append( list, "the" );
    list = append( list, "the" );   /* example at the head of a sub-list */
    list = append( list, "cat" );
    list = append( list, "sat" );
    list = append( list, "on" );
    list = append( list, "the" );   /* example in the middle of a sub-list */
    list = append( list, "mat" );
    print_list( list );
    del_dups( list );
    print_list( list );
    free_list( list );
    return 0;
}

ArkM · Jun 30, 2004

Obviously, it's not a C (may be C++) program: you have New() functions with different signatures (or New() uses void* type and accepts uninitialized args - what for?). It's very interesting to read New() code...

NewBuffer(): why cursor member points to a new cell (not to start cell)?.. Now cursor's link member is unitialized...

Let's go step by step: correct this problem then continue...

Salem · Jul 1, 2004

> That example can't display the link list contents! Is it caused by my compiler?
Well it is very much a 'C' program and not a C++ program.
If you save it as prog.cpp, then you will have problems with it.

Save it as prog.c and see how you get on.

--

sedawk · Jul 1, 2004

Yes, they are both *.c programs. The New() is esstentially a wrapup function of malloc(), nothing special, just like Salem's newnode(). The problem is as I described in my first post: no display. Did you use gcc as compiler?

Salem · Jul 1, 2004

Yes, I use gcc

Code:

$ gcc hello.c
$ ./a.out
the the cat sat on the mat
the cat sat on mat

Made some mods to your code

Code:

#include <stdio.h>
#include <stdlib.h>

#define New(x) malloc(sizeof(x))
#define FreeBlock(x) free(x)

#define MAXSIZE 5

typedef struct cellT {
    char ch;
    struct cellT *link;
} cellT;

struct bufferCDT {
    cellT *start;
    cellT *cursor;
};

typedef struct bufferCDT *bufferADT;

bufferADT NewBuffer(void);
void FreeBuffer(bufferADT buff);
void MoveCursorForward(bufferADT buffer);
void MoveCursorBackward(bufferADT buffer);
void MoveCursorToStart(bufferADT buffer);
void MoveCursorToEnd(bufferADT buffer);
void DisplayBuffer(bufferADT buffer);
void InsertCharacter(bufferADT buffer,char ch);

int main()
{
    int i;
    char ch;
    bufferADT head;
    head = NewBuffer();

    // this part no problem
    for (i=0; i<MAXSIZE; i++){
        InsertCharacter(head,'a'+i);
    }

    // VC6++ can't display but report program clashes
    DisplayBuffer(head);

    FreeBuffer(head);
    printf("Now buffer cleared!\n");
    return 0;
}

bufferADT NewBuffer(void)
{
    bufferADT buffer;
    buffer = New(bufferADT);
    buffer->start = NULL;   // the list is empty!
    buffer->cursor = NULL;  // bogus or dummy nodes will usually bite you
    return buffer;
}

void FreeBuffer(bufferADT buffer)
{
    cellT *cp, *next;
    for (cp=buffer->start; cp != NULL; cp = next) {
        next = cp->link;    // record next, before it's deleted
        FreeBlock(next);
    }
    FreeBlock(buffer);
}

void DisplayBuffer(bufferADT buffer)
{
    cellT *cp;
    for (cp=buffer->start; cp!=NULL;cp=cp->link)
        printf(" '%c'",cp->ch);
    printf("\n");
}

void InsertCharacter(bufferADT buffer,char ch)
{
    cellT *cp;
    cp = New(cellT);
    cp->ch = ch;
    cp->link = NULL;
    if ( buffer->start == NULL ) {
        buffer->start = cp;
        buffer->cursor = cp;
    } else {
        buffer->cursor->link = cp;
        buffer->cursor = cp;
    }
}

--

sedawk · Jul 1, 2004

Thanks for your modification, Salem. I tried your code and found some typo(I guess). Now it works on VC6++. The key problem is on the FreeBuffer() function. If I include FreeBlock(buffer) in FreeBuffer(), VC6++ clashes. So I just freed the bookkeeping cp instead of freeing the buffer. I think VC6++ has differet interpretation on free(): it can't access buffer as a whole anymore after FreeBlock(cp) in the while loop of FreeBlock().

Code:

#include <stdio.h>
#include <stdlib.h>

#define New(x) malloc(sizeof(x))
#define FreeBlock(x) free(x)

#define MAXSIZE 5

typedef struct cellT {
    char ch;
    struct cellT *link;
} cellT;

struct bufferCDT {
    cellT *start;
    cellT *cursor;
};

typedef struct bufferCDT *bufferADT;

bufferADT NewBuffer(void);
void FreeBuffer(bufferADT buff);
void MoveCursorForward(bufferADT buffer);
void MoveCursorBackward(bufferADT buffer);
void MoveCursorToStart(bufferADT buffer);
void MoveCursorToEnd(bufferADT buffer);
void DisplayBuffer(bufferADT buffer);
void InsertCharacter(bufferADT buffer,char ch);

int main()
{
    int i;
    char ch='a';
    bufferADT head;
    head = NewBuffer();

    // this part no problem
    for (i=0; i<MAXSIZE; i++){
        InsertCharacter(head,ch); //some typo in Salem's mod
    }

    // VC6++ can't display but report program clashes
    DisplayBuffer(head);

    FreeBuffer(head);
    printf("Now buffer cleared!\n");
    return 0;
}

bufferADT NewBuffer(void)
{
    bufferADT buffer;
    buffer = New(bufferADT);
    buffer->start = NULL;   // the list is empty!
    buffer->cursor = NULL;  // bogus or dummy nodes will usually bite you
    return buffer;
}

void FreeBuffer(bufferADT buffer)
{
    cellT *cp, *next;
    cp = buffer->start;
    while (cp!=NULL) {
        next = cp->link;
        FreeBlock(cp);
        cp = next;
    }
	FreeBlock(cp);
//    FreeBlock(buffer);  // can't turn this line on, otherwise, same problem occurs.
}

void DisplayBuffer(bufferADT buffer)
{
    cellT *cp;
    for (cp=buffer->start; cp!=NULL;cp=cp->link)
        printf(" '%c'",cp->ch);
    printf("\n");
}

void InsertCharacter(bufferADT buffer,char ch)
{
    cellT *cp;
    cp = New(cellT);
    cp->ch = ch;
    cp->link = NULL;
    if ( buffer->start == NULL ) {
        buffer->start = cp;
        buffer->cursor = cp;
    } else {
        buffer->cursor->link = cp;
        buffer->cursor = cp;
    }
}

Salem · Jul 2, 2004

This is better

Code:

#include <stdio.h>
#include <stdlib.h>

#define New(x) malloc(sizeof(x))
#define FreeBlock(x) free(x)

#define MAXSIZE 5

typedef struct cellT {
    char ch;
    struct cellT *link;
} cellT;

struct bufferCDT {
    cellT *start;
    cellT *cursor;
};

typedef struct bufferCDT *bufferADT;

bufferADT NewBuffer(void);
void FreeBuffer(bufferADT buff);
void MoveCursorForward(bufferADT buffer);
void MoveCursorBackward(bufferADT buffer);
void MoveCursorToStart(bufferADT buffer);
void MoveCursorToEnd(bufferADT buffer);
void DisplayBuffer(bufferADT buffer);
void InsertCharacter(bufferADT buffer,char ch);

int main()
{
    int i;
    char ch='a';
    bufferADT head;
    head = NewBuffer();

    // this part no problem
    for (i=0; i<MAXSIZE; i++){
        InsertCharacter(head,ch); //some typo in Salem's mod
    }

    // VC6++ can't display but report program clashes
    DisplayBuffer(head);

    FreeBuffer(head);
    printf("Now buffer cleared!\n");
    return 0;
}

bufferADT NewBuffer(void)
{
    bufferADT buffer;
    buffer = New(*buffer);  // wrong size!!! sizeof(bufferADT) not sizeof(bufferCDT)
    buffer->start = NULL;   // the list is empty!
    buffer->cursor = NULL;  // bogus or dummy nodes will usually bite you
    return buffer;
}

void FreeBuffer(bufferADT buffer)
{
    cellT *cp, *next;
    cp = buffer->start;
    while (cp!=NULL) {
        next = cp->link;
        FreeBlock(cp);
        cp = next;
    }
    //FreeBlock(cp);
    FreeBlock(buffer);  // can't turn this line on, otherwise, same problem occurs.
}

void DisplayBuffer(bufferADT buffer)
{
    cellT *cp;
    for (cp=buffer->start; cp!=NULL;cp=cp->link)
        printf(" '%c'",cp->ch);
    printf("\n");
}

void InsertCharacter(bufferADT buffer,char ch)
{
    cellT *cp;
    cp = New(*cp);
    cp->ch = ch;
    cp->link = NULL;
    if ( buffer->start == NULL ) {
        buffer->start = cp;
        buffer->cursor = cp;
    } else {
        buffer->cursor->link = cp;
        buffer->cursor = cp;
    }
}

--

sedawk · Jul 2, 2004

Code:

 buffer = New(*buffer);  // wrong size!!! sizeof(bufferADT) not sizeof(bufferCDT)

This one works too. I think this one is easier to read too. Thanks.

Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Link List Problem(just a repost) 1

sedawk

Programmer

ArkM

IS-IT--Management

Salem

Programmer

sedawk

Programmer

Salem

Programmer

sedawk

Programmer

Salem

Programmer

sedawk

Programmer

Similar threads

Part and Inventory Search

Sponsor