Thread: Add elements from linked list to array

  1. #1
    Registered User
    Join Date
    Oct 2020
    Posts
    11

    Add elements from linked list to array

    I'm new to C and am creating a program that initializes two different linked lists of books. The goal of the program will eventually merge the data from the two linked lists into a dynamically allocated array of movie pointers. Once ordered by book title, and the second time ordered by the book author. The linked list I'm creating is supposed to be a doubly linked list. I'm having trouble with my mergeBooks() function in book.c which is supposed to add every book from each linked list to an array in the order that is specified by the sort type. I'm supposed to expand the dynamically allocated array every time a new book is added, and I'm not allowed to use functions such as realloc() or memcpy() to help achieve this.


    I'm struggling with figuring out how to iterate through the nodes in each linked list and then add the items to the array. Since there are 2 lists, I'm not sure how I can add the contents of the 2nd list to the array without overwriting the first.


    I tried searching online and found some posts discussing how to add elements from an array to a linked list but not the other way around. I would appreciate some help or guidance!

    defs.h

    Code:
    	typedef struct{
    		char *title; 
    		char *author;
    	} BookType;
    
    
    	typedef struct Node {
    	  BookType *data;
    	  struct Node *prev;
    	  struct Node *next;
    	} BookNode; 
    
    
    	typedef struct{
    		BookNode *head;
    		BookNode *tail;
    	} BookList;
    	
    	typedef struct {
    	  int size;
    	  BookType **books;
    	} BookArray;
    	
    	typedef enum{
    		BY_TITLE,
    		BY_AUTHOR
    	}SortType;
    book.c

    Code:
    	void initBook(char *t, char *a, BookType **b){
    		*b = malloc(sizeof(BookType));
    		(*b)->title = t; 
    		(*b)->author = a;
    	}
    
    
    
    
    	void addBookToList(SortType s, BookList *list, BookType *b){
    		BookNode* current;
    		BookNode* previous;
    		BookNode* temp;
    		
    		current = list->head;
    		previous = NULL;
    		
    		
    		temp = malloc(sizeof(BookNode));
    		temp->data = b;
    		temp->next = NULL;
    		temp->prev = NULL;
    		
    
    
    		while(current != NULL){
    			if(s == BY_TITLE){
    				if(strcmp(b->title, current->data->title) < 0){
    					break;
    				}
    			}
    			if(s == BY_AUTHOR){
    				if(strcmp(b->author, current->data->author) < 0){
    					break;
    				}
    			}
    			previous = current;
    			current = current->next;
    		}
    		
    		if(previous == NULL){
    			list->head = temp;
    			list->tail = temp;
    		}
    		else{
    			previous->next = temp;
    			temp->prev = previous;
    			temp->next = current;
    		}
    		
    		if(temp->next == NULL){
    			list->tail = temp;
    		}else{
    	        current->prev = temp;
    		}
    		temp->next = current;
    	}
    
    
    
    
    	void mergeBooks(SortType s, BookArray *arr, BookList *listOne, BookList *listTwo){
    
    
    		BookArray **newArr;
    		newArr = calloc(arr->size + 1, sizeof(BookType*));
    		
    		BookNode* temp;
    		temp = malloc(sizeof(BookNode));
    		
    		arr[0] = temp->data;
    		temp->next = NULL;
    		
    		int i;
    		for(i = 0 ; i < arr->size; ++i){
    		if(s == BY_TITLE){
    			listOne->head = temp;
    			BookNode* tempTwo;
    				tempTwo = malloc(sizeof(BookNode));
    				temp->next = tempTwo;
    				arr[i] = tempTwo->data;
    				tempTwo->next = NULL;
    				temp = tempTwo
    			}
    		if(s == BY_AUTHOR){
    			listTwo->head = temp;
    			BookNode* tempTwo;
    				tempTwo = malloc(sizeof(BookNode));
    				temp->next = tempTwo;
    				arr[i] = tempTwo->data;
    				tempTwo->next = NULL;
    				temp = tempTwo
    			}
    		}	
    		
    		free(arr->books);
    		arr->books = newArr;
    		++(arr->size);
    	}

    main.c

    Code:
    	int main(){
    		
    		BookList *sarahsList = malloc(sizeof(BookList));
    		BookList *davidsList = malloc(sizeof(BookList));
    		
    		sarahsList->head = NULL;
    		sarahsList->tail = NULL;
    		
    		davidsList->head = NULL;
    		davidsList->tail = NULL;	
    		
    		initBooks(sarahsList, davidsList);
    
    
    		return 0;
    		
    	}
    init.c

    Code:
    	void initBooks(BookList *listOne, BookList *listTwo){
    	  BookType *b;
    
    
    	  initBook("Hamlet", "William Shakespeare", &b);
    	  addBookToList(BY_TITLE, BY_AUTHOR, b);
    	  initBook("The Hobbit", "Tolkien", &b);
    	  addBookToList(BY_TITLE, BY_AUTHOR, b);
    	}

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,703
    I'm supposed to expand the dynamically allocated array every time a new book is added, and I'm not allowed to use functions such as realloc() or memcpy() to help achieve this.
    This makes no sense at all.

    Code:
    void mergeBooks(SortType s, BookArray *arr, BookList *listOne, BookList *listTwo){
        arr->size = listlen(listOne) + listlen(listTwo);
        arr->books = calloc(arr->size, sizeof(BookType*));
    Step 1 is count how many books are in both lists, and allocate an array of pointers.

    The rest is just traverse both lists at the same time, and at each step, figure out which one should be appended to the array.
    Code:
    BookNode *n1 = listOne->head;
    BookNode *n2 = listTwo->head;
    for(i = 0 ; i < arr->size; ++i){
      if ( someCompareFunction(s,n1,n2) ) {
        arr->books[i] = n1->data;
        n1 = n1->next;
      } else {
        arr->books[i] = n2->data;
        n2 = n2->next;
      }
    }
    This is a mergesort if you want a google topic.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Deleting elements from a linked list
    By gdz98 in forum C++ Programming
    Replies: 10
    Last Post: 05-27-2018, 01:57 PM
  2. Removing elements from an array of linked list
    By koplersky in forum C Programming
    Replies: 13
    Last Post: 10-08-2012, 02:04 PM
  3. number of elements in double linked list
    By cnu_sree in forum C++ Programming
    Replies: 4
    Last Post: 01-25-2008, 12:18 PM
  4. swap elements in a linked list.
    By Axel in forum C Programming
    Replies: 6
    Last Post: 10-15-2006, 07:11 AM

Tags for this Thread