[muhaded]

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.





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.

[Bench]

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.

[David W]

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

[muhaded]

David 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...