
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 27 March 2009 - 02:12 AM
Posted 27 March 2009 - 08:10 AM
#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); }
This post has been edited by David W: 27 March 2009 - 05:50 PM
Posted 02 April 2009 - 09:57 PM
David W, on 27 Mar, 2009 - 07:10 AM, said:
#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); }