3 Replies - 2276 Views - Last Post: 02 April 2009 - 09:57 PM Rate Topic: -----

#1 muhaded  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 27-March 09

need helps on linked lists

Post icon  Posted 27 March 2009 - 02:12 AM

1) Given a linked list of integers sorted in an ascending order, and a pointer to a single node containing an integer, write a C program that insert the node P in the linked list so that it remains sorted.

Posted Image



2) Given two null terminated linked lists, combine their nodes so that the nodes of the new list alternate between those of the two original nodes.

Note: Do not allocate any new nodes.

Posted Image

Is This A Good Question/Topic? 0
  • +

Replies To: need helps on linked lists

#2 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 856
  • View blog
  • Posts: 2,339
  • Joined: 20-August 07

Re: need helps on linked lists

Posted 27 March 2009 - 03:21 AM

What part of it do you need help on? Please post your attempt so far, and explain in as much detail as possible where you're having problems; anything you don't understand and/or any errors you're getting from your code.
Was This Post Helpful? 0
  • +
  • -

#3 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: need helps on linked lists

Posted 27 March 2009 - 08:10 AM

This may give you a running start ...

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

/* make this big enough so ALL C strings DO have the 'fgets' '\n' char at end */
#define BUFFER_SIZE 1024


typedef struct Text_line
{
    char* str; /* 'str' holds the address of a new C string ... */
    struct Text_line* next; /* points to the next C string ... */
}Text_line;

typedef Text_line* pText_line; /* to hold the address of a C string */
typedef char* CString;


/* prototypes ... */

/* INSERTS C string 'data' into 'list' in 'ABC...abc...' order */
pText_line insert(char data[], pText_line list);
/* erase/free up all memory in list */
void free_list(pText_line list);
/* show all the (insert-sorted) 'text lines' in the 'list' */
void print_list(pText_line list);

/* utility function to return a copy ... in NEWly allocated memory */
CString newCopy( CString str )
{
    int i, len;
    len = strlen( str );
    CString nCopy = (CString) malloc( len+1 );/* can omit times sizeof(char)=1 */
    for( i=0; i<len; ++i )
        nCopy[i] = str[i];

    nCopy[len] = 0;
    return nCopy;
}



int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
    char buffer[BUFFER_SIZE];
    char prompt[] = "Enter line of text to insert into list (or Ctrl Z to end) ";
    pText_line list = NULL;/* 'list' ... holds the address of the list's HEAD */
    
    puts(prompt);
    while( (fgets(buffer, 1024, stdin)) != NULL )
    { 
        list = insert(buffer, list);
        puts(prompt);
    }
    
    print_list(list);
    free_list(list);
    printf("\nPress 'Enter' ... to continue ... ");
    getchar();
    return 0;
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */



/* pass in the address of the 'head' ... and the line to insert ...*/
pText_line insert(char data[], pText_line list)
{
    pText_line p;
    pText_line q;
    
    /* create a new node */
    p = (pText_line) malloc( sizeof(Text_line) );
    /* save address of new memory (copy of data) into the new node ... */
    p->str = newCopy(data);
    
    /* first, we handle the case where 'data' should be the first element */
    if(list == NULL || strcmp(list->str, data) > 0)
    {
        /* apparently this IS the first element */
        /* now data should [be ...i.e. becomes] the first element */
        p->next = list;
        return p;
    } 

    /* if program reaches here, search the linked list for the right location */
    q = list;
    while(q->next != NULL && strcmp(q->next->str, data) < 0)
    {
        q = q->next;
    }
    p->next = q->next;
    q->next = p;
    return list;
}
    
void free_list(pText_line list)
{
    pText_line p;
    while(list != NULL) 
    {
        p = list->next;
        free(list);
        list = p;
    }
}

/*
    Note: all these lines (strings) have a '\n' char at the end ...
    except maybe, the last line ... (if we reached EOF with-out a '\n' char)
*/
void print_list(pText_line list)
{
    pText_line p;
    for(p = list; p != NULL; p = p->next)
    printf("%s", p->str);
}


Shalom,
David
http://developers-he.../index.p...opic,127.0.html
http://developers-he.../index.p...opic,106.0.html

This post has been edited by David W: 27 March 2009 - 05:50 PM

Was This Post Helpful? 0
  • +
  • -

#4 muhaded  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 27-March 09

Re: need helps on linked lists

Posted 02 April 2009 - 09:57 PM

View PostDavid W, on 27 Mar, 2009 - 07:10 AM, said:

This may give you a running start ...

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

/* make this big enough so ALL C strings DO have the 'fgets' '\n' char at end */
#define BUFFER_SIZE 1024


typedef struct Text_line
{
    char* str; /* 'str' holds the address of a new C string ... */
    struct Text_line* next; /* points to the next C string ... */
}Text_line;

typedef Text_line* pText_line; /* to hold the address of a C string */
typedef char* CString;


/* prototypes ... */

/* INSERTS C string 'data' into 'list' in 'ABC...abc...' order */
pText_line insert(char data[], pText_line list);
/* erase/free up all memory in list */
void free_list(pText_line list);
/* show all the (insert-sorted) 'text lines' in the 'list' */
void print_list(pText_line list);

/* utility function to return a copy ... in NEWly allocated memory */
CString newCopy( CString str )
{
    int i, len;
    len = strlen( str );
    CString nCopy = (CString) malloc( len+1 );/* can omit times sizeof(char)=1 */
    for( i=0; i<len; ++i )
        nCopy[i] = str[i];

    nCopy[len] = 0;
    return nCopy;
}



int main() /* * * * * * * * * * * * * * MAIN BEGINS * * * * * * * * * * * * * */
{
    char buffer[BUFFER_SIZE];
    char prompt[] = "Enter line of text to insert into list (or Ctrl Z to end) ";
    pText_line list = NULL;/* 'list' ... holds the address of the list's HEAD */
    
    puts(prompt);
    while( (fgets(buffer, 1024, stdin)) != NULL )
    { 
        list = insert(buffer, list);
        puts(prompt);
    }
    
    print_list(list);
    free_list(list);
    printf("\nPress 'Enter' ... to continue ... ");
    getchar();
    return 0;
}/* * * * * * * * * * * * * * * * * * MAIN ENDS * * * * * * * * * * * * * * * */



/* pass in the address of the 'head' ... and the line to insert ...*/
pText_line insert(char data[], pText_line list)
{
    pText_line p;
    pText_line q;
    
    /* create a new node */
    p = (pText_line) malloc( sizeof(Text_line) );
    /* save address of new memory (copy of data) into the new node ... */
    p->str = newCopy(data);
    
    /* first, we handle the case where 'data' should be the first element */
    if(list == NULL || strcmp(list->str, data) > 0)
    {
        /* apparently this IS the first element */
        /* now data should [be ...i.e. becomes] the first element */
        p->next = list;
        return p;
    } 

    /* if program reaches here, search the linked list for the right location */
    q = list;
    while(q->next != NULL && strcmp(q->next->str, data) < 0)
    {
        q = q->next;
    }
    p->next = q->next;
    q->next = p;
    return list;
}
    
void free_list(pText_line list)
{
    pText_line p;
    while(list != NULL) 
    {
        p = list->next;
        free(list);
        list = p;
    }
}

/*
    Note: all these lines (strings) have a '\n' char at the end ...
    except maybe, the last line ... (if we reached EOF with-out a '\n' char)
*/
void print_list(pText_line list)
{
    pText_line p;
    for(p = list; p != NULL; p = p->next)
    printf("%s", p->str);
}


Shalom,
David
http://developers-he.../index.p...opic,127.0.html
http://developers-he.../index.p...opic,106.0.html




thank you so much.. really appreciated... :D
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1