!!! linked list problem !!!!

Discussion in 'C Programming' started by sugaray, Oct 1, 2003.

  1. sugaray

    sugaray Guest

    i'm learning data structure in advance by myself, here's my linked
    list code, i don't know what's wrong with my code or just my
    understanding not right.

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

    typedef struct link {
    int data;
    struct link *next;
    }Link;

    typedef enum {SUCCESS,ERROR,FAILURE,FATAL} Status;

    void error(const char *msg) {
    fprintf(stderr,"%s\n",msg);
    exit(ERROR);
    }

    void usage(void) {
    fprintf(stderr,"usage:\n\t%s n\n");
    exit(FAILURE);
    }

    Link *CreateLink(Link *head,int data) {
    head->data=data;
    head->next=NULL;

    return head;
    }

    Link *AppendLink(Link *head,int data) {

    Link *p=head;
    Link *pNew=(Link *)malloc(sizeof(Link));
    pNew->data=data;
    pNew->next=NULL;
    p->next=pNew;
    p=pNew;

    return p;
    }

    size_t LinkSize(Link *head) {
    size_t size=0;
    Link *p=head;
    while(p!=NULL) {
    p=p->next;
    size++;
    }
    return size;
    }

    Status InsertLink(Link *head,size_t index,int data) {
    Link *p=head;
    Link *pNew;
    size_t r=0;

    while(p && r<index-1) {
    p=p->next;
    r++;
    }

    if(!p || r>index-1) return FAILURE;

    pNew=(Link *)malloc(sizeof(Link));
    pNew->data=data;
    pNew->next=p->next;
    p->next=pNew;

    return SUCCESS;
    }

    void DisplayLink(Link *head) {
    Link *p=head;
    while(p!=NULL) {
    printf("%d\n",p->data);
    p=p->next;
    }
    }

    Status DeleteLink(Link *head,size_t index) {
    Link *p=head;
    Link *tmp;
    size_t r=0;

    while(p && r<index-1) {
    p=p->next;
    r++;
    }

    if(!(p->next) || r>index-1) return FAILURE;

    tmp=p->next;
    p->next=tmp->next;

    free(tmp);

    return SUCCESS;
    }

    size_t LocateElement(Link *head,int data) {
    Link *p=head;
    size_t location=0;

    while(p!=NULL && (p->data)!=data) {
    p=p->next;
    location++;
    }

    return location;
    }

    void FreeLink(Link *head) {
    Link *p;
    while(head!=NULL) {
    p=head;
    head=head->next;
    free(p);
    }
    }

    int main(int argc,char *argv[])
    {
    int data,n,i;
    Link *head,*pHead;
    pHead=head=(Link *)malloc(sizeof(Link));

    if(argc<2) error("oops!");

    n=atoi(argv[1]);

    scanf("%d",&data);
    pHead=CreateLink(head,data);

    for(i=0;i<n-1;++i) {
    scanf("%d",&data);
    AppendLink(pHead,data);
    }

    printf("#################\n");
    DisplayLink(pHead);

    FreeLink(pHead);

    return 0;
    }
    sugaray, Oct 1, 2003
    #1
    1. Advertising

  2. sugaray

    Martijn Guest

    sugaray wrote:
    > i'm learning data structure in advance by myself, here's my linked
    > list code, i don't know what's wrong with my code


    Neither do I - what _is_ wrong with the code?? (what behaviour are you
    getting?)

    BTW, indentation helps people understand the code.

    > or just my
    > understanding not right.
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > typedef struct link {
    > int data;
    > struct link *next;
    > }Link;


    I think this way (capitalizing the first letter) of distinguishing between
    the typedef and the actual defenition is error-prone at best.

    > typedef enum {SUCCESS,ERROR,FAILURE,FATAL} Status;
    >
    > void error(const char *msg) {
    > fprintf(stderr,"%s\n",msg);
    > exit(ERROR);
    > }
    >
    > void usage(void) {
    > fprintf(stderr,"usage:\n\t%s n\n");
    > exit(FAILURE);
    > }
    >
    > Link *CreateLink(Link *head,int data) {
    > head->data=data;
    > head->next=NULL;
    >
    > return head;
    > }


    I would call this InitLink or something of the sort, because it creates
    nothing.

    > Link *AppendLink(Link *head,int data) {
    >
    > Link *p=head;
    > Link *pNew=(Link *)malloc(sizeof(Link));


    Check for errors here.

    > pNew->data=data;
    > pNew->next=NULL;
    > p->next=pNew;
    > p=pNew;
    >
    > return p;


    Why not:

    head->next = pNew;
    head = pNew;

    return ( head );

    This saves you a pee (pun intended)

    > }


    <nitpick>Append sounds to me like you are adding something to the end, but
    alas</nitpick>

    You are not assigning you next pointer to anything. That means the original
    head pointer is lost. Assigning the original head pointer to the next
    attribute of the new node will solve this. But the user has to be aware
    that the pointer passed to the function no longer represents the entire list
    (just it's tail - being all elements after the head).

    >
    > size_t LinkSize(Link *head) {
    > size_t size=0;
    > Link *p=head;
    > while(p!=NULL) {
    > p=p->next;
    > size++;
    > }
    > return size;
    > }
    >
    > Status InsertLink(Link *head,size_t index,int data) {
    > Link *p=head;
    > Link *pNew;
    > size_t r=0;
    >
    > while(p && r<index-1) {
    > p=p->next;
    > r++;
    > }
    >
    > if(!p || r>index-1) return FAILURE;


    You are not using index anywhere else and as you are passing it by value,
    you might as well use that instead of r:

    while (p != NULL && index > 0) {
    p = p->next;
    --index;
    }

    if ( index != 0 ) return FAILURE;

    >
    > pNew=(Link *)malloc(sizeof(Link));
    > pNew->data=data;
    > pNew->next=p->next;
    > p->next=pNew;
    >
    > return SUCCESS;
    > }
    >
    > void DisplayLink(Link *head) {
    > Link *p=head;
    > while(p!=NULL) {
    > printf("%d\n",p->data);
    > p=p->next;
    > }
    > }
    >
    > Status DeleteLink(Link *head,size_t index) {
    > Link *p=head;
    > Link *tmp;
    > size_t r=0;
    >
    > while(p && r<index-1) {
    > p=p->next;
    > r++;
    > }
    >
    > if(!(p->next) || r>index-1) return FAILURE;
    >
    > tmp=p->next;
    > p->next=tmp->next;
    >
    > free(tmp);
    >
    > return SUCCESS;
    > }


    same as above

    >
    > size_t LocateElement(Link *head,int data) {
    > Link *p=head;
    > size_t location=0;
    >
    > while(p!=NULL && (p->data)!=data) {
    > p=p->next;
    > location++;
    > }
    >
    > return location;
    > }


    This doesn't return an error if the data isn't found, just an index outside
    of the list.

    >
    > void FreeLink(Link *head) {
    > Link *p;
    > while(head!=NULL) {
    > p=head;
    > head=head->next;
    > free(p);
    > }
    > }
    >


    I didn't check the main

    > int main(int argc,char *argv[])
    > {
    > int data,n,i;
    > Link *head,*pHead;
    > pHead=head=(Link *)malloc(sizeof(Link));
    >
    > if(argc<2) error("oops!");
    >
    > n=atoi(argv[1]);
    >
    > scanf("%d",&data);
    > pHead=CreateLink(head,data);
    >
    > for(i=0;i<n-1;++i) {
    > scanf("%d",&data);
    > AppendLink(pHead,data);
    > }
    >
    > printf("#################\n");
    > DisplayLink(pHead);
    >
    > FreeLink(pHead);
    >
    > return 0;
    > }


    Good luck,


    --
    Martijn
    http://www.sereneconcepts.nl
    Martijn, Oct 1, 2003
    #2
    1. Advertising

  3. sugaray

    Al Bowers Guest

    sugaray wrote:
    > i'm learning data structure in advance by myself, here's my linked
    > list code, i don't know what's wrong with my code or just my
    > understanding not right.
    >


    It appears that you are starting to get an understanding of
    data structures and linked lists. I am not sure what problems
    you are referring to when you say something is wrong with the
    code. I see several problem areas. But first I think you
    need to get an understand that when up declare a link pointer
    in function main, and then you want to modify that link
    pointer in another function you want to use the address
    of this pointer as the argument in the called function.


    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > typedef struct link {
    > int data;
    > struct link *next;
    > }Link;
    >


    ......... code snipped...........

    For example in the function below:
    >
    > Link *AppendLink(Link *head,int data) {
    >


    You would make this prototype
    Link *AppendLink(Link **head, int data)
    and write the appropriate definition.
    And in function main to use the function:

    int main(void)
    {
    ......
    Link *head = NULL;
    ......
    AppendLink(&head, 5); /* Add node with data value 5 */
    ........

    Here is a rewrite of some of your functions using the above technique.
    I have not tested all of these functions and there may be flaws or
    they may not work as you desire.

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

    typedef struct link
    {
    int data;
    struct link *next;
    }Link;

    typedef enum {SUCCESS,ERROR,FAILURE,FATAL} Status;

    Link *AddLinkFront(Link **head,int data)
    {
    /* Inserts node at head of list*/
    Link *pNew=(Link *)malloc(sizeof(Link));
    if(pNew)
    {
    pNew->data=data;
    pNew->next= *head;
    *head = pNew;
    }
    return pNew;
    }

    Link *AddLinkEnd(Link **head, int data)
    {
    /* Appends new node to end of list */
    Link *tmp, *pNew = malloc(sizeof *pNew);
    if(pNew == NULL) return NULL;
    pNew->data = data;
    pNew->next = NULL;
    if(*head == NULL) *head = pNew;
    else
    {
    for(tmp = *head;tmp->next != NULL; tmp = tmp->next) ;
    tmp->next = pNew;
    }
    return pNew;
    }

    size_t LinkSize(Link *head)
    {
    size_t size=0;
    Link *p=head;
    while(p!=NULL)
    {
    p=p->next;
    size++;
    }
    return size;
    }

    Link *InsertLink(Link **head,size_t position,int data)
    {
    /* position value of 0 or 1 inserts at head */
    size_t i , link_sz = LinkSize(*head);
    Link *pNew,*tmp;

    if(!link_sz || position <= 1)
    return AddLinkFront(head, data);
    if(position >= link_sz) return AddLinkEnd(head, data);
    pNew = malloc(sizeof *pNew);
    if(pNew == NULL) return NULL;
    for(position--,i = 0,tmp = *head;i < position -1;
    i++,tmp= tmp->next) ;
    pNew->data = data;
    pNew->next = tmp->next;
    tmp->next = pNew;
    return pNew;
    }

    void DisplayLink(Link *head)
    {
    Link *p=head;
    size_t i;

    for(i = 0;p!=NULL;i++)
    {
    printf("Node #%u has value %d\n",i+1,p->data);
    p=p->next;
    }
    }

    Status DeleteLink(Link **head,size_t index)
    {
    Link *tmp, *current;
    size_t i, link_sz = LinkSize(*head);
    if(!link_sz || index >= link_sz) return FAILURE;
    if(index == 0)
    {
    tmp = *head;
    *head = tmp->next;
    free(tmp);
    }
    else
    {
    for(i = 0,current = *head; i < index-1;
    current = current->next,i++);
    tmp = current->next;
    current->next = current->next->next;
    free(tmp);
    }
    return SUCCESS;
    }

    size_t LocateElement(Link *head,int data)
    {
    Link *p=head;
    size_t location=0;

    while(p!=NULL && (p->data)!=data)
    {
    p=p->next;
    location++;
    }
    if(!p) return (size_t)-1;
    return location;
    }

    void FreeLink(Link **head)
    {
    Link *tmp ,*current;
    for(current = *head; current; current = tmp)
    {
    tmp = current->next;
    free(current);
    }
    *head = NULL;
    }

    int main(void)
    {
    int i,list_sz, value;
    Link *head = NULL;
    size_t index;

    printf("Enter the list size: ");
    fflush(stdout);
    scanf("%d",&list_sz);
    putchar('\n');
    for(i=0;i<list_sz;++i)
    {
    printf("List #%d value is: ",i+1);
    fflush(stdout);
    scanf("%d",&value);
    if(!AddLinkEnd(&head,value)) exit(EXIT_FAILURE);
    }
    InsertLink(&head,3, 99);
    puts("\nAttempt Value 99 insert at node 3");
    printf("\n#################\n");
    DisplayLink(head);
    if((index = LocateElement(head,99)) != (size_t)-1)
    {
    puts("\nValue 99 was found and is being removed");
    DeleteLink(&head,index);
    }
    printf("\n#################\n");
    DisplayLink(head);
    FreeLink(&head);
    return 0;
    }
    Al Bowers, Oct 1, 2003
    #3
  4. sugaray

    David Rubin Guest

    sugaray wrote:

    > void error(const char *msg) {
    > fprintf(stderr,"%s\n",msg);
    > exit(ERROR);
    > }
    >
    > void usage(void) {
    > fprintf(stderr,"usage:\n\t%s n\n");


    You've specified %s, but you haven't given an argument. Typically, you
    would declare a global variable

    static char *argv0;

    and have the statement

    argv0 = argv[0];

    in main(). Then, this would be

    fprintf(stderr, "usage: %s n\n", argv0);

    > exit(FAILURE);
    > }


    [snip]
    > int main(int argc,char *argv[])
    > {
    > int data,n,i;
    > Link *head,*pHead;
    > pHead=head=(Link *)malloc(sizeof(Link));
    >
    > if(argc<2) error("oops!");


    Better is

    char buf[32];
    char *p;

    argv0 = argv[0];
    if(argc != 1) /* assumes argv[0] is program name */
    usage();

    /* read data until EOF (e.g., ^C) */
    while(fgets(buf, sizeof buf, stdin) != 0){
    buf[strlen(buf)-1] = 0;
    p = buf;
    data = strtol(buf, &p, 10);
    if(*p != 0){
    /* error */
    }else{
    pHead = CreateLink(head, data);
    }
    }

    Which allows you to redirect a file full of input data to the program.

    > printf("#################\n");
    > DisplayLink(pHead);
    >
    > FreeLink(pHead);
    >
    > return 0;
    > }


    /david

    --
    Andre, a simple peasant, had only one thing on his mind as he crept
    along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
    -- unknown
    David Rubin, Oct 1, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    475
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    501
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    664
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    747
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page