Need a project done?

C++ Programming Developer

Search This Blog

Sorting linked list in C++

Linked list has been sorted alphabetically in the following program.

struct pen{
char* color;
Int qty;
pen* link;
}
Q1. Using the above structure you are required to manage the linked list considering the
following rules.
Pen should be stored in alphabetical order.
* If you have two pens of color red and green, your linked list will be as follows:
head
* If you have 5 pens, Aqua, Green, Blue, Red and yellow, your linked list will be:
head
● Your program should display the menu:
Select your choice
1. Add Pen
2. Sell Pen
3. Display Stock
//------------------------------------------------------------------------------------------
Solution:
//Following program uses the technique in which first the place for new item in the linked list is searched, and then the item is inserted at the correct place rather than first inserting it somewhere (say at tail) and then Sorting it.

#include <iostream>
#include <conio.h>

using std::cout;
using std::endl;
using std::cin;

//------------------------------------------------------------
struct pen{
char color[10];
int qty;
pen* link;
};
//------------------------------------------------------------

void insert(pen **head, pen **tail, pen *temp);
void insertAtHead(pen **head, pen *tail, pen *temp);
void insert_anywhere(pen* head, pen **tail, pen *temp);//Doesn't insert at head.
pen* getData();
void addPen(pen **head, pen ** tail, pen *temp);
void display(pen *head);

//============================================================

int main(){
pen *head = NULL, *tail = NULL, *temp = NULL;

while (1){
cout << "Select your choice\n" <<
"1. Add Pen\n" <<
// "2. Sell Pen\n" <<
"3. Display Record.\n" <<
"0. Exit" << endl;
int opt; cin >> opt;

switch(opt){
case 1:
insert(&head, &tail, temp);
break;
case 2:
////////////////////////
break;
case 3:
display(head);
break;
case 0:
return 0;
}
system("cls");
}
return 0;
}

//============================================================

//------------------------------------------------------------
void insert(pen **h, pen **t, pen *temp){
temp = getData();
bool i = 0;
if (*h == NULL && *t == NULL){
*h = temp;
*t = temp;
i = 1;
}
else{
//Checking where to insert.
pen *check = *h;
while (check!=NULL){
if (temp -> color[0] > check->color[0]){
insert_anywhere(*h,t,temp);
i = 1;
break;
}
check = check->link;
}//End of while.
if (i==0){
insertAtHead(h,*t,temp);
}
}
}

//-------------------------------------------------------------------------------
void insertAtHead(pen **h, pen *t, pen *temp){
temp->link = *h;
*h = temp;
}
//-------------------------------------------------------------------------------
void insert_anywhere(pen* ph, pen **pt, pen *temp){//Doesn't insert at head.
//finding where to insert.
pen *check = ph;
while (check!=NULL){
if (check->color[0] > temp->color[0]){
break;
}
check = check->link;
}
if (check == NULL){//insertion at tail is needed.
temp->link = NULL;
(*pt)->link = temp;
*pt = temp;
}
else{//check points to the node before which we've to insert
pen *b = ph;
while (b->link != check){
b = b->link;
}//b points just before check. We've to insert after 'b' and before 'check'.
//insert
temp->link = check;
b->link = temp;
}
}
//-------------------------------------------------------------------------------
pen* getData(){
pen *p = new pen;
cout << "Color: "; cin >> p->color;
cout << "Quantity: "; cin >> p->qty;
p->link = NULL;
return p;
}
//-------------------------------------------------------------------------------

//-------------------------------------------------------------------------------
void display(pen *h){
while (h!=NULL){
cout << "Color: " << h->color << endl;
cout << "Quantity: " << h->qty << endl;
cout << endl;
h = h->link;
}
getch();
}
//-------------------------------------------------------------------------------

"Don't let anyone ever make you feel like you don't deserve what you want."