Remove duplicates from doubly-linked list
Given a list of 200 random integers ranging from 0-49, this program sorts the list in numerical order and removes all the duplicate numbers.unknown
plain_text
3 years ago
5.1 kB
10
Indexable
//Week 3 Honors Assignment //Modify the singly linked list to be a doubly linked list. Now write a routine that removes all duplicate data in the doubly linked list. //The data will be integers generated at random from [0,49]. Initially have a list of 200 elements. //Now do this in one of two ways. //1. Sort the list by its data field. Remove adjacent elements of the sorted list with the same value. //2. Or, take the first element—search the remainder of the list for elements with the same data and remove them. Then take the second element and do the same. Repeat until only one element is left. #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <time.h> #include <math.h> typedef struct list{ int data; //can replace this with a more complex data structure struct list *next; //pointer to next element struct list *prev; //pointer to previous element }list; //function to create the list list* create_list(int d){ list* head = malloc(sizeof(list)); //use malloc to allocate space for the list head->data = d; //set the data parameter head->next = head->prev = NULL; //set the previous and next elements to NULL return head; //return the head } //add an element to the list by adding an element to the front (prepending list *add_to_front(int d, list* head){ list* newNode = create_list(d); //create a list newNode->data = d; //add the data newNode->next = head; //Make the next node after newNode the head newNode->prev = NULL; //make the previous node null if(head!=NULL){ head->prev = newNode; //set the previous node from the head to the new node we created } head = newNode; //mode the head to point to the new node return head; } //convert an array to a list list* array_to_list(int d[], int size){ list* head = create_list(d[0]); //create lsit using first element of the array for(int i=1; i<size; i++){ head = add_to_front(d[i], head); //add array elements to the front of the lsit we made } return head; } int is_empty(const list *l){ return l == NULL; //the tail is null. if this is what the lsit equals, we know its empty } void print_list(list *h, char *title){ printf("%s\n", title); //give the list a title for identification purposes int index = 0; while(h!=NULL){ //while we are not at the end of the list printf("%d\t", h->data); //print the element h = h->next; //go to the next element index++; //increment index if(index%5==0){ printf("\n");; } } printf("\n"); } int getItem(list *head, int index){ list* current = head; //index of the node we're looking at int count = 0; while(current!=NULL){ if(count == index){ return current->data; } count++; current = current->next; } assert(0); } void setItem(list *head, int index, int data){ list* current = head; //index of the node we're looking at int count = 0; while(current!=NULL){ if(count == index){ current->data = data; return; } count++; current = current->next; } assert(0); } void swap(list* data, int a, int b){ //swap the nodes at index a and b int temp = getItem(data, a); setItem(data, a, getItem(data, b)); setItem(data, b, temp); } void bubbleSort(list* data, int amt){ for(int i=0; i<amt; i++){ for(int j = amt-1; j>i; j--){ if(getItem(data, j-1)>getItem(data, j)){ swap(data, j-1, j); } } } } void removeDuplicates(list* head){ list* current = head; //pointer to traverse the linked list list* nextPointer; //pointer to store the next pointer of the node to be deleted if(is_empty(current)){ return; //do nothing if the lsit is empty } //traverse the list until the last node is reached while(current->next!=NULL){ //if the current node and the node after the current node have the same value: if(current->data == current->next->data){ nextPointer = current->next->next; //set the next pointer to be the node after the node after the current node free(current->next); //free the node after the current node current->next = nextPointer; //set the node after the current node to the node after the node after the current node. The node was successfuly deleted. }else{ //if the current node and the node after the current node aren't the same value, advance to the next node without deletion current = current->next; } } } #define SIZE 200 //we will generate 200 random integers from 0 to 49 inclusive int main(){ //Use srand to set the seed. we will use the current time, as that produces a unique number every time the program is run srand(time(0)); int numbers[SIZE]; //fill the array of numbers with random numbers for(int i=0; i<SIZE; i++){ numbers[i] = rand()%50; //add random number to the array. using %50 makes the numbers from 0 to 49 } //convert array to a list list* myList = array_to_list(numbers, SIZE); //sort the list using bubble sort bubbleSort(myList, SIZE); //remove the duplicates removeDuplicates(myList); //print the list print_list(myList, "myList"); return 0; }
Editor is loading...