C++ Linked Lists This program is to implement a number of functions on a linked

Question

C++

Linked Lists

This program is to implement a number of functions on a linked list.

1.Insertion of a node to a linked list, by given criteria

2. Deletion of a node on a linked list, by given criteria

3. Search a node on a linked list, by given criteria

4. Sorting a linked list, by given criteria

5. Write: print out information (name and score) in each and every node on the linked list, from the first node to the last Node

structure: Use the circular doubly linked list discussed in lecture Info Field: Name (only one string, for simplicity) Score (an integer) Links: prev, next

1. Insertion criteria: a. The linked list insertion is based on alphabetical order of the given names. b. Names will not be duplicated. 2. Deletion criterion For a given name, delete that name associated node from the linked list, if it exists.

3. Search criteria: a. For a given name, search on the linked list if there is a node that has this name. b. If found, print out the node info: Name and Score. One single line for each searched node. c. If not found, print out “not found”. d. The search process cannot change any info or node on the list.

4.Given a criterion, sort the linked in either ascending or descending order. The program reads from a3.txt for actions (insertion, deletion, or search): %SEARCH, %INSERT, %DELETE, %WRITE, %SORT, %END The “WRITE” command directs the program to print out information (name and score) in each and every node on the linked list, from the first node to the last. The “SORT” is to sort the list according to the scores, in ascending order. The “END” command ends the program running, but not closing the window.

A code blocks project (assig3_start) is provided as a starting point to build on. The project opens the text file and reads in the instructions. This is provided as an example as to how to read in the instructions and do conversions from strings to integers. The program uses an if-then-else structure for implementing the commands. Also the project provides a possible llist (linked list) class structure to implement the linked list functions. Please feel free to use this structure or change it. There are many ways to implement these functions. Hint for implementing the sort function you can use the selection sort algorithm. You can use two pointersthat are moved as the for loop indices are incremented. You need a swap function for nodes. It is easier to swap node data than pointers but this is less efficient for nodes that hold large amounts of data.

Explanation / Answer

PROGRAM:

/* Program to perform operations such as Insertion, deletion,
search, sorting and displaying in the Doubly Linked List*/

#include <iostream.h>
#include <stdlib.h> //for exit(1)
#include <conio.h>
#define MAX 10

//This creates a node
struct node{
int data;
struct node *lptr;
struct node *rptr;
};

//This class is used to provide the framework of the list and its functions
class dbllist{
node *head;
public:
dbllist(){
head=NULL;
}
void create();
void insert();
void del();
void search();
void sort();
};

//This function of the dbllist creates the node
void dbllist :: create(){
node *start=NULL,*newl=NULL,*end=NULL;
int takedata;
clrscr();
cout<<" *****Creating List***** ";
while(1){
cout<<" -999 to Quit ";
cout<<" Enter data : ";
cin>>takedata;
if(takedata == -999)
break;
else{
//create memory for new node
newl = new node;
if(newl == NULL){
cout<<" There is not enough memory";
getch();
exit(1);
}
newl->data = takedata;
newl->lptr = NULL;
newl->rptr = NULL;

//check for first nodeif(start == NULL){
start->rptr = newl;
newl->lptr = start;
start = newl;
}
else{
end->rptr = newl;
newl->lptr = end;
}
end = newl;
}//end else
}//end while

head->rptr = start;
start->lptr = head;
head = start;
}

void dbllist :: display(int check){
node *tmp=NULL;

cout<<" *****Display***** ";
cout<<" ";
if(check==1){ //forward displayfor(tmp=head; tmp!=NULL; tmp=tmp->rptr){
cout<<tmp->data;
if(tmp->rptr != NULL)
cout<<"-->";
}//end for
}
else{ //Reverse displayfor( tmp=head; tmp->rptr!=NULL; tmp=tmp->rptr);//points to last nodewhile(tmp!=NULL)
{
cout<<tmp->data;
if(tmp->lptr != NULL)
cout<<"-->";
tmp = tmp->lptr;
}//end whiile
}//end if
getch();
}

int dbllist :: count(int check){
node *tmp=NULL;
int cnt;

for(tmp=head,cnt=0 ; tmp!=NULL; tmp=tmp->rptr,cnt++);//do nothingif(check==1){
cout<<" ****Status of List**** ";
cout<<" Total Items : "<<cnt;
getch();
return(cnt);
}
elsereturn(cnt); //To use count value in other functions
}

void dbllist :: insert(){
node *newl=NULL,*tmp=NULL,*prev=NULL,*next=NULL;
int choice,takedata,pos,i;
while(1){
clrscr();
cout<<" ****Insertion**** ";
cout<<" 1) Begining ";
cout<<" 2) In Between ";
cout<<" 3) End ";
cout<<" 4) Return to Main Menu ";
cout<<" Enter your choice : ";
cin>>choice;
if(choice==1 || choice==2 || choice==3){
//create memory for new node
newl = new node;
if(newl == NULL){
cout<<" Not Enough Memory";
getch();
exit(1);
}
cout<<" Enter data : ";
cin>>takedata;
newl->data = takedata;
newl->lptr = NULL;
newl->rptr = NULL;
}
elsereturn;

switch(choice){
case 1 : newl->rptr = head;
head->lptr = newl;
head = newl;
break;

case 2 : cout<<" Enter Position : ";
cin>>pos;
if(pos <=1 || pos >= count(2)){
cout<<" Invalid Position";
getch();
break;
}
else{

next = prev->rptr;
newl->rptr = next;
next->lptr = newl;
newl->lptr = prev;
prev->rptr = newl;
break;
}
case 3 :   

tmp->rptr = newl;
newl->lptr = tmp;
}//end switch
}//end while
}

void dbllist :: del(){
node *delnode=NULL,*tmp=NULL,*prev=NULL,*next=NULL;
int choice,deldata,pos,i;
while(1){
clrscr();
cout<<" ****Deletion**** ";
cout<<" 1) Begining ";
cout<<" 2) In Between ";
cout<<" 3) End ";
cout<<" 4) Return to Main Menu ";
cout<<" Enter your choice : ";
cin>>choice;
switch(choice){
case 1 : delnode = head;
head = head->rptr;
head->lptr = NULL;
break;

case 2 : cout<<" Enter Position : ";
cin>>pos;
if(pos <=1 || pos >= count(2)){
cout<<" Invalid Position";
getch();
break;
}
else{
//to points to previous node

next=prev->rptr->rptr;
delnode = prev->rptr;
prev->rptr = prev->rptr->rptr;
next->lptr = prev;
break;
}
case 3 : //For pointing to last node
delnode = tmp->rptr;
tmp->rptr = NULL;
break;
case 4 : return;
default : cout<<" Invalid Position";
getch();
}//end switch
delete(delnode);
}//end while
}

void dbllist :: search(){
node *tmp=NULL;
int item,n;
cout<<" *****Search***** ";
cout<<" Enter data to be searched : ";
cin>>item;
for(tmp=head,n=1; tmp!=NULL; tmp=tmp->rptr,n++){
if(tmp->data == item){
cout<<" Search is located at "<<n<<" location";
getch();
return;
}
}
cout<<" Search Not Found";
getch();
}

void dbllist :: sort(){
node *i,*j;
int tmp;
cout<<" ****Sorting the list**** ";
for(i=head;i!=NULL;i=i->rptr){
for(j=i;j!=NULL;j=j->rptr){
if(i->data > j->data){
tmp = i->data;
i->data = j->data;
j->data = tmp;
}
}
}
cout<<" After Sorting...";
cout<<" ==List==";
display(1);
}

void main()
{
int choice;
dbllist obj;
while(1){
clrscr();
cout<<" OPERATIONS AVAILABLE ";
cout<<" 1) Create List ";
cout<<" 2) Display List ";
cout<<" 3) List Status ";
cout<<" 4) List Insertion ";
cout<<" 5) List Deletion ";
cout<<" 6) Search List ";
cout<<" 7) Sort List ";
cout<<" 8) Exit ";
cout<<" Enter your Choice : ";
cin>>choice;
switch(choice){
case 1 : obj.create(); // 1 for A listbreak;
case 2 : obj.display(1);// 1 for A listbreak;
case 3 : choice = obj.count(1);
//choice value is not used anywhere//it is just a placeholderbreak;
case 4 : obj.insert();
break;
case 5 : obj.del();
break;
case 6 : obj.search();
break;
case 7 : obj.display(2);
break;
case 8 : obj.sort();
break;
case 9 : gotoout;
default: cout<<" Invalid Choice ";
getch();
break;
}
}
out:
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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