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
2 years ago
5.1 kB
4
Indexable
Never
```//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
}

//add an element to the list by adding an element to the front (prepending
list* newNode = create_list(d); //create a list
newNode->data = d; //add the data
newNode->prev = NULL; //make the previous node 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
}

//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++){
}
}

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");
}

//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){
//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);
}
}
}
}

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;
}```