1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
storchak [24]
3 years ago
8

The LList class is (mostly) the same one discussed in lecture, but you must write a sort() function that uses one of the three i

nefficient sorts discussed in lecture. The function should sort the list contents from lowest to highest value using bubble sort, selection sort, or insertion sort. Since the original linked list code produced a sorted list, this version has been modified such that (1) insert() adds each new item to the start of the list, not in order and (2) remove() searches the entire list, since it can't assume the list is ordered. Also, display() has been modified to print all list contents on a single line, not one value per line.
The only file you may modify is LList.cpp, which contains space to write the definition for the sort() function, as well as the definitions of standard LList functions covered previously.
The other two files, LList.h and LList_test_main.cpp, are read-only. LList.h contains the LList class definition, while the other file exists solely to test the code you write.
LList.h
#ifndef LLIST_H
#define LLIST_H
#include
using std::ostream;
class LList {
public:
/***** FUNCTION TO BE WRITTEN *****/
void sort(); // Sort linked list using bubble, insertion, or selection sort
/***** FUNCTIONS BELOW THIS LINE ARE ALREADY WRITTEN--DO NOT MODIFY *****/
LList(); // Default constructor
~LList(); // Destructor
bool empty(); // True if list is empty
void insert(int v); // Add new value to list
void remove(int v); // Remove node with v
void display(ostream &out); // Print contents of list
// (could of course write as
// overloaded operator)
private:
/****************************************************************
Slightly different setup than we've seen before, as Node class
is defined *inside* LList class.
Benefits:
By making "Node" a member of LList, LList functions can
directly refer to Node data members val and next. No
need to write/call accessor functions for Node, so
fewer files in solution + no function call overhead on
simple data accesses. Node data members are "public" to
LList functions but "private" to outside world.
Downside:
This implementation of Node can *only* be used inside LList.
If you want Node objects in other classes, have to redefine.
****************************************************************/
class Node {
public:
int val; // Value in each node--could be generalized
// using templates
Node *next; // Pointer to next node
};
Node *first; // Pointer to first node
};
#endif
LList.cpp
#include "LList.h"
using namespace std;
/***** FUNCTION TO BE WRITTEN *****/
void LList::sort() { // Sort linked list using bubble, insertion, or selection sort
/***** ADD YOUR OWN SOLUTION *****/
}
/***** FUNCTIONS BELOW THIS LINE ARE ALREADY WRITTEN--DO NOT MODIFY *****/
// Default constructor
LList::LList() : first(NULL)
{}
// Destructor
LList::~LList() {
Node *temp;
while (first != NULL) {
temp = first;
first = first->next;
delete temp;
}
}
// True if list is empty
bool LList::empty() {
return (first == NULL);
}
// Add new value to list
/***** MODIFIED TO CREATE UNORDERED LIST *****/
void LList::insert(int v) {
// Allocate new node and place at beginning of list
Node* newNode = new Node;
newNode->val = v;
newNode->next = first;
first = newNode;
}
// Remove node with v
void LList::remove(int v) {
Node *prev; // Predecessor of node to be deleted
Node *cur; // Node to be deleted
// Find node, if it's in list
cur = first;
prev = NULL;
while (cur != NULL) { /***** MODIFIED--NO LONGER ASSUMES LIST ORDERED *****/
prev = cur;
cur = cur->next;
}
// Didn't find node
if (cur == NULL || cur->val > v) {
cout << "Node with value " << v << " not found\n";
return;
}
// Otherwise, remove node
if (prev == NULL) // Special case for first node
first = cur->next;
else
prev->next = cur->next;
delete cur;
}
// Display contents of list
void LList::display(ostream &out) {
Node *ptr = first;
while (ptr != NULL) {
out << ptr->val << ' ';
ptr = ptr->next;
}
out << '\n';
}
LList_test_main.cpp
#include "LList.h"
#include
#include
using namespace std;
int main() {
LList L1, L2; // Linked lists to use for testing
unsigned i; // Loop indexes
int seed; // RNG seed
// RNG seed--ensures you'll get same "random" values across
// multiple runs with same seed
cout << "Seed value: ";
cin >> seed;
srand(seed);
// Fill lists
for (i = 0; i < 10; i++) {
L1.insert(rand() % 50);
L2.insert(rand() % 50);
}
// Print lists before sorting
cout << "Before sorting:\nL1: ";
L1.display(cout);
cout << "\nL2: ";
L2.display(cout);
// Sort and print lists again
L1.sort();
L2.sort();
cout << "After sorting:\nL1: ";
L1.display(cout);
cout << "\nL2: ";
L2.display(cout);
return 0;
}
Computers and Technology
1 answer:
Vladimir79 [104]3 years ago
8 0

Answer:

see explaination

Explanation:

#include <iostream>

#include <string>

using namespace std;

class LinkedList{

class Node{

public :

int data;

Node* next;

Node(int data){

this->data = data;

next = NULL;

}

};

public :

Node *head;

LinkedList(){

this->head = NULL;

}

void insert(int d){

Node* new_node = new Node(d);

new_node->next = head;

head = new_node;

}

// sort the list with selection sort algorithm.

// Pick the smallest element in the unsorted array and place in the first element in the unsorted.

void sort_list(){

if (head == NULL){

return;

}

Node* current = head;

while (current->next != NULL){

Node* min_node = current;

Node* traverse = current->next;

while(traverse != NULL){

if(traverse->data < min_node->data){

min_node = traverse;

}

traverse = traverse->next;

}

int temp = current->data;

current->data = min_node->data;

min_node->data = temp;

current = current->next;

}

}

void print_list(){

Node* current = head;

while(current !=NULL){

cout<<current->data<<" ";

current = current->next;

}

cout<<"\n";

}

};

int main(){

LinkedList ll;

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

ll.insert(i);

}

ll.print_list();

cout<<"*******************************************\n";

ll.sort_list();

ll.print_list();

cout<<"*******************************************\n";

}

You might be interested in
Write short notes on the following:<br>I. keyboard ii.Control unit iii.printer​
Andreas93 [3]

Answer:

- the Keyboard:

The keyboard is a handheld device used to input alphabet, numbers, symbols and characters to a monitor. It also houses the special manipulative and function keys.

- the Control Unit:

The control unit is a component of the CPU which directs the operation of the processor.

- the Printer:

The printer is an external hardware output device which takes electronic data stored on a device and creates a hard copy.

4 0
2 years ago
Java what are synchronized functions.
adelina 88 [10]

<h2>answer:</h2>

Synchronized method is used to lock an object for any shared resource. When a thread invokes a synchronized method, it automatically acquires the lock for that object and releases it when the thread completes its task.','.

4 0
3 years ago
Without a/an ________. a computer is useless
Len [333]
Without a/an Operating system. a computer is useless
3 0
3 years ago
When does copyright protection start?
Fittoniya [83]

Answer:

The moment work is produced, written, or developed.

Explanation:

Your work is under copyright protection the moment it is created and fixed in a tangible form that it is perceptible either directly or with the aid of a machine or device.

8 0
2 years ago
A license plate consists of 2 letters followed by 1 digit. How many license plates are possible if the first letter can be any l
Art [367]

Answer:

5400

Explanation:

  • As there are three spaces to be filled. First can have any alphabet, but not i and o. And there are 26 alphabets so, only one out of 24 can be filled in the first blank.
  • In the second blank any alphabet can be used, but not the one same as the first one so we can choose from the remaining 25 alphabets.
  • In the last blank any number can be chosen, but not 0 so we have 9 options to choose from.

Finally,the number of options available is <em>24*25*9 = 5400</em>. So, 5400 license plates can be made using these combinations.

8 0
3 years ago
Other questions:
  • A programmer wrote the code segment below to display the average of all the elements in a list called numbers. There is always a
    8·1 answer
  • When you use the Filter feature, what appears in each column label
    11·1 answer
  • Why coaxil cable called coxial cable ?
    15·2 answers
  • python This program outputs a downwards facing arrow composed of a rectangle and a right triangle. The arrow dimensions are defi
    5·2 answers
  • All slides in a presentation must use the same transition. True or False?
    13·2 answers
  • What is outlook used for?
    14·2 answers
  • WHAT IS ONE WAY A PIVOTTABLE COULD COMBINE THE FOLLOWING DATA
    10·1 answer
  • Hey im b---o---r---e---d dont report cuz if u do ur l a m e :)
    14·1 answer
  • What does a for loop look for in the sequence of data? Check all that apply.
    6·2 answers
  • Besides your computer, where else can you find and use an operating system?
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!