C++ !!! I need to sort the following data by linked list display them first and
ID: 3865664 • Letter: C
Question
C++ !!! I need to sort the following data by linked list
display them first and than remove those population less than 4 miilion
Thanks for the help!
Data:
Idaho Boise 1,297,274
Washington Olympia 5,908,684
Vermont Montpelier 609,890
Hawaii Honolulu 1,216,642
Arizona Phonenix 5,140,683
Montana Helena 905,316
Virginia Richmond 7,100,702
North Dakota Bismarck 643,756
Colorado Denver 4,311,882
Mississippi Jackson 2,852,927
Delaware Dover 785,068
Georgia Atlanta 8,206,975
South Carolina Columbia 4,025,061
Illinois Springfield 12,439,042
Nebraska Lincoln 1,715,369
Arkansas Little Rock 2,679,733
New Hampshire Concord 1,238,415
Ohio Columbus 11,374,540
Kansas Topeka 2,693,824
Louisiana Baton Rouge 4,480,271
Michigan Lansing 9,955,829
Florida Talahasse 16,028,890
Connecticut Hartford 3,409,535
Iowa Des Moines 2,931,923
West Virginia Charleston 1,813,077
Missouri Jefferson 5,606,260
Wyoming Cheyenne 495,304
California Sacramento 33,930,798
Explanation / Answer
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include <sstream>
#include <string>
#include <fstream>
using namespace std;
/*
* Node Declaration
*/
struct Node
{
string State;
string Capital;
int Population;
struct Node *next;
};
// insert node at first
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
int Insert(struct Node** head_ref, string new_State, string new_Capital, int new_Population,int length)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->State = new_State;
new_node->Capital=new_Capital;
new_node->Population=new_Population;
new_node->next = (*head_ref);
(*head_ref) = new_node;
length++;
return length;
}
// print the whole list
void printList(struct Node *node)
{
while (node != NULL)
{
cout << "State : " <<node->State<<endl ;
cout <<"Capital : "<<node->Capital<<endl;
printf("population %d ", node->Population);
node = node->next;
}
}
/* Given a reference (pointer to pointer) to the head of a list
and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct Node **head_ref,struct Node *node)
{
// Store head node
struct Node* temp = *head_ref, *prev;
// If head node itself holds the key to be deleted
if (temp != NULL && temp->Population < 4000000)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && temp->Population >= 4000000)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL) return;
// Unlink the node from linked list
prev->next = temp->next;
free(temp); // free memory
}
// sort by population in assending order
void SortByPopulation (struct Node **head_ref,int length)
{
if (*head_ref != 0)
{
Node* current = *head_ref;
Node* prev = 0;
Node* tempNode = 0;
int changeFlag = 0;
for (int i = 0; i < length; i++)
{
while (current->next != 0)
{
tempNode = current->next;
if (current->Population > tempNode->Population)
{
changeFlag = 1;
current->next = tempNode->next;
tempNode->next = current;
if (prev != 0)
prev->next = tempNode;
prev = tempNode;
if (*head_ref == current)
*head_ref= tempNode;
}
else
{
prev = current;
current = current->next;
}
}
if (changeFlag == 0)
break;
else
{
prev = 0;
current = *head_ref;
changeFlag = 0;
}
}
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node* node=NULL; // an empty node
int length=0;
std::ifstream infile("c++.txt"); // file name
string line;
while (getline(infile, line))
{
//puts("Check file reading ");
std::istringstream iss(line);
string state;
string capital;
int population;
if (!(iss >> state >> capital >> population )) { break; } // error
length=Insert(&head,state,capital,population,length);
}
/* length=Insert(&head, "Idaho","Boise",1297247,length);
length=Insert(&head, "Washington","Olympia",5908684,length);
length=Insert(&head, "Hawaii","Honolulu",1216642,length);
length=Insert(&head, "Arizona","phonix",5140683,length);
length=Insert(&head, "Vermont","Montpelier",609890,length);
length=Insert(&head, "Montana","Helena",905316,length);
length=Insert(&head, "Virginia","Richmond",7100702,length); */
SortByPopulation(&head,length);
puts("Created Linked List: ");
printList(head);
node=head; // store head in the empty node
// call a loop which delete the node have population less than 4 milion
while (node != NULL)
{
deleteNode(&head, head);
node = node->next;
}
puts(" Linked List after Deletion of: ");
printList(head);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.