(C++) Using linked lists and numbers.txt, use radix sort and print it to the con

Question

(C++) Using linked lists and numbers.txt, use radix sort and print it to the console.

Specification:

Radix sort is a unique sorting algorithm; implement the Radix Sort algorithm. Use the numbers.txt (shown below) for the numbers to sort.

* Convert your linked list code (https://www.chegg.com/homework-help/questions-and-answers/c-write-program-reads-list-words-wordstxt-file-shown-stores-singly-linked-list-prints-word-q26295882) to have a 'prev' AND 'next' pointer (or object). (DoublyLinkedList)

* Use the DynamicArray from (https://www.chegg.com/homework-help/questions-and-answers/c-using-pseudo-code-listed-extend-include-reading-data-strings-file-convert-int-based-cont-q26217211) to make a dynamic array of SinglyLinkedLists (use your now DoublyLinkedList - use the next, rather than prev, node).

* The 10 positions in the array of LinkedList are used for each base 10 radix. In mathematical numeral systems, the radix or base is the number of unique digits, including zero, used to represent numbers in a positional numeral system. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.

* Read the numbers.txt file and sort them using the Radix Sort algorithm.

* Output the sorted numbers to the console.

numbers.txt (this should work if there are many more numbers in the file):

9380

64

21111

11053

27116

23354

13272

21277

233

42453

2

4324

Explanation / Answer

here is your program : ----------------------------->>>>>>>>>>>>>>>

#include<iostream>

#include<fstream>

#include<string>

using namespace std;

struct Node{

string data;

struct Node *prev;

struct Node *next;

};

class LinkedList{

struct Node *head;

int size;

int lNum;//for loop throw every digits

public:

LinkedList(){

head = null;

size = 0;

lNum = 0;

}

void add(string data){

size++;

if(lNum < data.length())

lNum = data.length();

Node *temp = new Node;

temp->data = data;

temp->next = NULL;

temp->prev = NULL;

if(head == NULL){

head = temp;

}

else{

temp->next = head->next;

head->prev = temp;

}

}

void sort(){//radix sort

Node *temp = head;

Node *tt = NULL;

for(int i=0;i<lNum;i++){

temp = head;

for(int j = 0;j<size;j++){

Node *tmp = temp;

for(int k = j;k<size;k++){

if(tmp->data[i] > temp->data[i])

tmp->prev->next = temp;

tt = tmp->prev;

tmp->prev = temp->prev;

temp->prev = tt;

tt = tmp->next;

tmp->next = temp->next;

tmp->prev->next = tmp;

tmp->next->prev = tmp;

temp->next = tt;

tt->prev = temp;

}

tmp = tmp->next;

}

temp = temp->next;

}

}

}

void print(){

Node *temp = head;

cout<<" Your List : ";

for(int i = 0;i<size;i++){

cout<<temp->data<<endl;

temp = temp->next;

}

}

};

int main(){

ifstream f;

LinkedList l1;

string data;

f.open("numbers.txt");

if(f.is_open()){

while(!f.eof()){

f>>data;

l1.add(data);

}

f.close();

l1.print();

cout<<" after Radix Sort : ";

l1.sort();

l1.print();

}else{

cout<<"File opening error";

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.