Colas con Nodos
jOeY
03 de Agosto del 2005
Necesito por favor aayuda con un programa de colas con nodos y uno de listas enlazadas..
De antemano, Gracias!!
Saluods!
De antemano, Gracias!!
Saluods!
noel solw
03 de Agosto del 2005
Te mando un programa que trabaja con listas enlazadas y el header file correspondiente.
Desagraciadamente no se que entiende por colas de nodos, explicame de que se trata y si es posible que nombre tienen en ingles, quizas pueda ayudate.
// program k18a7.cpp - page 368
// Linked List : recursive reverse print.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include "LinkList.h"
#include <string.h>
void ReversePrint(Node<char> *p,int sw)
{
if(!p)
{
cout << "{";
return;
}
ReversePrint(p->next,sw+1);
cout << p->info;
if(sw)
cout << ",";
} // REVERSE PRINT
void Process()
{
char *A = "abcdefgh";
LinkedList <char> a(strlen(A),A);
cout << setw(30) << "list A, direct print : " << a;
cout << setw(30) << "list A, reverse print : ";
ReversePrint(a.GetBegin(),0);
cout << "}" << endl;
} // PROCESS
void main()
{
clrscr();
cout << "Linked List : recursive reverse printn";
cout << "-----------------------------------------------------"
"-------------------------n";
Process();
cout << "-----------------------------------------------------"
"-------------------------n";
cout << "end of program - good bye ! ! !n";
getch();
} // MAIN
/*
Linked List : recursive reverse print
------------------------------------------------------------------------------
list A, direct print : {a,b,c,d,e,f,g,h}
list A, reverse print : {h,g,f,e,d,c,b,a}
------------------------------------------------------------------------------
end of program - good bye ! ! !
*/
Nota : LinkList.h es generico, es decir puede usarse con diferentes tipo de tipos en el campo info.
// program LinkdList.h - page 366 . . . . .
// Header File for Linked List.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
template <class T>
struct Node
{
T info;
Node<T> *next;
}; // STRUCT NODE
template <class T>
class LinkedList
{
private:
Node<T> *begin;
int len;
public:
LinkedList(int num = 0,T *data = NULL);
LinkedList(LinkedList &right);
~LinkedList();
int GetLen() {return len;}; // GET LEN
Node<T> *GetBegin() {return begin;} // GET BEGIN
void SetBegin(Node<T> *BEGIN) {begin = BEGIN;} // SET BEGIN
T operator [] (int index) const;
void FirstDelete(Node<T> *actual);
void InnerDelete(Node<T> *anterior);
void Remove(Node<T> *p);
void FirstInsert(Node<T> *pMin);
void Insert(Node<T> *p,Node<T> *pMin);
friend ostream &operator<<(ostream &,const LinkedList<T> &);
}; // CLASS LINKED LIST
template <class T>
LinkedList<T>::LinkedList(int num = 0,T *data = NULL)
{
if(!data)
{
begin = NULL;
len = 0;
}
else
{
len = 1;
begin = new Node<T>;
Node<T> *p = begin;
p->info = data[0];
for(int i = 1;i < num;i++)
{
p->next = new Node<T>;
p = p->next;
p->info = data[i];
len++;
}
p->next = NULL;
}
} // LINKED LIST CONSTRUCTOR
template <class T>
LinkedList<T>::LinkedList(LinkedList<T> &right)
{
Node<T> *p = right.GetBegin(),*q;
if(!p)
{
begin = NULL;
}
else
{
this->begin = new Node<T>;
q = this->begin;
q->info = p->info;
p = p->next;
while(p)
{
q->next = new Node<T>;
q = q->next;
q->info = p->info;
p = p->next;
}
q->next = NULL;
len = right.len;
}
} // LINKED LIST COPY CONSTRUCTOR
template <class T>
LinkedList<T>::~LinkedList()
{
Node<T> *p = begin,*q;
while(p)
{
q = p;
p = p->next;
delete q;
}
} // LINKED LIST DESTRUCTOR
template <class T>
T LinkedList<T>::operator [] (int index) const
{
if(index < 0 || index >= len)
{
cout << index << " out of range index ";
return 0;
}
Node<T> *p = begin;
while(index)
{
index--;
p = p->next;
}
return p->info;
} // LINKED LIST OPERATOT []
template <class T>
void LinkedList<T>::FirstDelete(Node<T> *actual) // remode and delete node
{ // at the begining of list
cout << setw(30) << "first delete . . . . " << actual->info << endl;
begin = actual->next;
delete actual;
len--;
} // LINKED LIST FIRST DELETE
template <class T>
void LinkedList<T>::InnerDelete(Node<T> *anterior) // remode and delete nodr
{ // inside the list
Node<T> *actual = anterior->next;
cout << setw(30) << "delete . . . . " << actual->info << endl;
anterior->next = actual->next;
anterior->next = actual->next; // ***************
delete actual;
len--;
} // LINKED LIST INNER DELETE
template <class T>
void LinkedList<T>::Remove(Node<T> *p) // remove node inside the list
{ // without destruyed it
p->next = p->next->next;
} // REMOVE
template <class T>
void LinkedList<T>::FirstInsert(Node<T> *pMin) // insert existent node
{ // at the begining of list
pMin->next = begin;
begin = pMin;
} // FIRST INSERT
template <class T>
void LinkedList<T>::Insert(Node<T> *p,Node<T> *pMin) // insert existent node
{ // inside the list
pMin->next = p->next;
pMin->next = p->next;
p->next = pMin;
p->next = pMin;
} // INSERT
template <class T>
ostream &operator<<(ostream &out,const LinkedList <T> &LIST)
{
Node<T> *p = LIST.begin;
if(!p)
out << "{empty list}";
else
{
out << "{" << p->info;
p = p->next;
for(;p;p = p->next)
out << "," << p->info;
}
out << "}" << endl;
return out;
} // OPERATOR <<
Desagraciadamente no se que entiende por colas de nodos, explicame de que se trata y si es posible que nombre tienen en ingles, quizas pueda ayudate.
// program k18a7.cpp - page 368
// Linked List : recursive reverse print.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include "LinkList.h"
#include <string.h>
void ReversePrint(Node<char> *p,int sw)
{
if(!p)
{
cout << "{";
return;
}
ReversePrint(p->next,sw+1);
cout << p->info;
if(sw)
cout << ",";
} // REVERSE PRINT
void Process()
{
char *A = "abcdefgh";
LinkedList <char> a(strlen(A),A);
cout << setw(30) << "list A, direct print : " << a;
cout << setw(30) << "list A, reverse print : ";
ReversePrint(a.GetBegin(),0);
cout << "}" << endl;
} // PROCESS
void main()
{
clrscr();
cout << "Linked List : recursive reverse printn";
cout << "-----------------------------------------------------"
"-------------------------n";
Process();
cout << "-----------------------------------------------------"
"-------------------------n";
cout << "end of program - good bye ! ! !n";
getch();
} // MAIN
/*
Linked List : recursive reverse print
------------------------------------------------------------------------------
list A, direct print : {a,b,c,d,e,f,g,h}
list A, reverse print : {h,g,f,e,d,c,b,a}
------------------------------------------------------------------------------
end of program - good bye ! ! !
*/
Nota : LinkList.h es generico, es decir puede usarse con diferentes tipo de tipos en el campo info.
// program LinkdList.h - page 366 . . . . .
// Header File for Linked List.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
template <class T>
struct Node
{
T info;
Node<T> *next;
}; // STRUCT NODE
template <class T>
class LinkedList
{
private:
Node<T> *begin;
int len;
public:
LinkedList(int num = 0,T *data = NULL);
LinkedList(LinkedList &right);
~LinkedList();
int GetLen() {return len;}; // GET LEN
Node<T> *GetBegin() {return begin;} // GET BEGIN
void SetBegin(Node<T> *BEGIN) {begin = BEGIN;} // SET BEGIN
T operator [] (int index) const;
void FirstDelete(Node<T> *actual);
void InnerDelete(Node<T> *anterior);
void Remove(Node<T> *p);
void FirstInsert(Node<T> *pMin);
void Insert(Node<T> *p,Node<T> *pMin);
friend ostream &operator<<(ostream &,const LinkedList<T> &);
}; // CLASS LINKED LIST
template <class T>
LinkedList<T>::LinkedList(int num = 0,T *data = NULL)
{
if(!data)
{
begin = NULL;
len = 0;
}
else
{
len = 1;
begin = new Node<T>;
Node<T> *p = begin;
p->info = data[0];
for(int i = 1;i < num;i++)
{
p->next = new Node<T>;
p = p->next;
p->info = data[i];
len++;
}
p->next = NULL;
}
} // LINKED LIST CONSTRUCTOR
template <class T>
LinkedList<T>::LinkedList(LinkedList<T> &right)
{
Node<T> *p = right.GetBegin(),*q;
if(!p)
{
begin = NULL;
}
else
{
this->begin = new Node<T>;
q = this->begin;
q->info = p->info;
p = p->next;
while(p)
{
q->next = new Node<T>;
q = q->next;
q->info = p->info;
p = p->next;
}
q->next = NULL;
len = right.len;
}
} // LINKED LIST COPY CONSTRUCTOR
template <class T>
LinkedList<T>::~LinkedList()
{
Node<T> *p = begin,*q;
while(p)
{
q = p;
p = p->next;
delete q;
}
} // LINKED LIST DESTRUCTOR
template <class T>
T LinkedList<T>::operator [] (int index) const
{
if(index < 0 || index >= len)
{
cout << index << " out of range index ";
return 0;
}
Node<T> *p = begin;
while(index)
{
index--;
p = p->next;
}
return p->info;
} // LINKED LIST OPERATOT []
template <class T>
void LinkedList<T>::FirstDelete(Node<T> *actual) // remode and delete node
{ // at the begining of list
cout << setw(30) << "first delete . . . . " << actual->info << endl;
begin = actual->next;
delete actual;
len--;
} // LINKED LIST FIRST DELETE
template <class T>
void LinkedList<T>::InnerDelete(Node<T> *anterior) // remode and delete nodr
{ // inside the list
Node<T> *actual = anterior->next;
cout << setw(30) << "delete . . . . " << actual->info << endl;
anterior->next = actual->next;
anterior->next = actual->next; // ***************
delete actual;
len--;
} // LINKED LIST INNER DELETE
template <class T>
void LinkedList<T>::Remove(Node<T> *p) // remove node inside the list
{ // without destruyed it
p->next = p->next->next;
} // REMOVE
template <class T>
void LinkedList<T>::FirstInsert(Node<T> *pMin) // insert existent node
{ // at the begining of list
pMin->next = begin;
begin = pMin;
} // FIRST INSERT
template <class T>
void LinkedList<T>::Insert(Node<T> *p,Node<T> *pMin) // insert existent node
{ // inside the list
pMin->next = p->next;
pMin->next = p->next;
p->next = pMin;
p->next = pMin;
} // INSERT
template <class T>
ostream &operator<<(ostream &out,const LinkedList <T> &LIST)
{
Node<T> *p = LIST.begin;
if(!p)
out << "{empty list}";
else
{
out << "{" << p->info;
p = p->next;
for(;p;p = p->next)
out << "," << p->info;
}
out << "}" << endl;
return out;
} // OPERATOR <<
jOeY
03 de Agosto del 2005
Muchas gracias!!!
Hablando de la cola con nodos..es igual que la pila (stack)..solo que esta trabaja con FIFO (first in, first out)...el nombre en ingles creo que es Queue...
Gracias por ayudame.!!
Hablando de la cola con nodos..es igual que la pila (stack)..solo que esta trabaja con FIFO (first in, first out)...el nombre en ingles creo que es Queue...
Gracias por ayudame.!!
noel solw
03 de Agosto del 2005
Exactamente lo que pensaba. Se que lo tengo programado, pero no lo puedo encontrar.
Te envio el programa del Stack, que con muy poca transformacion podras convertirlo en Queue.
// program k19a7.cpp - page 397
// bracket balance.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include "Stack.h"
#include <string.h>
int CheckNegativeCounters(int *counter)
{
for(int i = 0;i < 3;i++)
if(counter[i] < 0)
return 0;
return 1;
} // CHECK NEGATIVE COUNTERS
int CheckZeroCounters(int *counter)
{
for(int i = 0;i < 3;i++)
if(counter[i])
return 0;
return 1;
} // CHECK NEGATIVE COUNTERS
int Check(Stack<char> a)
{ // ( ) --> index = 0
int counter[3] = {0,0,0}; // [ ] --> index = 1
while(!a.EmptyStack()) // { } --> index = 2
{
switch(a.Pop())
{
case '(' : counter[0]++;
break;
case ')' : counter[0]--;
break;
case '[' : counter[1]++;
break;
case ']' : counter[1]--;
break;
case '{' : counter[2]++;
break;
case '}' : counter[2]--;
break;
}
if(!CheckNegativeCounters(counter))
return 0;
}
return CheckZeroCounters(counter);
} // CHECK
void Process(char *data)
{
Stack<char> a(strlen(data),data);
char *msg[2] = {"not balanced expression","balanced expression"};
cout << setw(30) << "giving string : " << data << endl;
cout << setw(27) << msg[Check(a)] << endl;
cout << "-----------------------------------------------------"
"-------------------------n";
} // PROCESS
void main()
{
clrscr();
cout << "bracket balance.n";
cout << "-----------------------------------------------------"
"-------------------------n";
char *data[5] = {"{[1+2]*b+3*(c+d)}",
"[a*(b+1)]-{[c-2]*(d+3-(e+{f*(4/(g+5)]})))}",
"[a*(b+1)]-{[c-2]*(d+3-(e+{f*[4/(g+5)]}))}",
"(({{[[100*a+b]]}}))","({{{[[a]]}}))"};
for(int i = 0;i < 5;i++)
Process(data[i]);
cout << "end of program - good bye ! ! !n";
getch();
} // MAIN
/*
bracket balance.
------------------------------------------------------------------------------
giving string : {[1+2]*b+3*(c+d)}
balanced expression
------------------------------------------------------------------------------
giving string : [a*(b+1)]-{[c-2]*(d+3-(e+{f*(4/(g+5)]})))}
not balanced expression
------------------------------------------------------------------------------
giving string : [a*(b+1)]-{[c-2]*(d+3-(e+{f*[4/(g+5)]}))}
balanced expression
------------------------------------------------------------------------------
giving string : (({{[[100*a+b]]}}))
balanced expression
------------------------------------------------------------------------------
giving string : ({{{[[a]]}}))
not balanced expression
------------------------------------------------------------------------------
end of program - good bye ! ! !
*/
// program Stack.h - page 393 . . . . .
// Header File for Stack class.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
// -------------------------------------------------------------------------
template <class T>
struct Node
{
T info;
Node<T> *next;
}; // STRUCT NODE
// -------------------------------------------------------------------------
template <class T>
class Stack
{
private:
Node<T> *top;
unsigned int len;
public:
Stack(int num = 0,T *data = NULL);
Stack(Stack<T> &right);
~Stack();
void Push(T);
T Pop();
int EmptyStack();
T StackTop();
unsigned int StackLen();
Node<T> *GetTopPointer() {return top;}
void operator=(Stack<T> &);
friend ostream &operator<<(ostream &,const Stack &);
}; // CLASS STACK
// -------------------------------------------------------------------------
template <class T>
Stack<T>::Stack(int num = 0,T *data = NULL)
{
top = NULL;
len = 0;
for(int i = num-1;i >= 0;i--)
Push(data[i]);
} // STACK CONSTRUCTOR
template <class T>
Stack<T>::Stack(Stack<T> &right)
{
top = NULL;
len = 0;
Transfer(*this,right.GetTopPointer());
} // COPY CONSTRUCTOR
template <class T>
Stack<T>::~Stack()
{
while(!this->EmptyStack())
Pop();
} // STACK DESTRUCTOR
template <class T>
void Stack<T>::Push(T INFO)
{
Node<T> *holder = top;
top = new Node<T>;
top->info = INFO;
top->next = holder;
len++;
} // STACK PUSH
template <class T>
T Stack<T>::Pop()
{
if(EmptyStack())
{
cout << "error : empty stack pop" << endl;
return 0;
}
T ret = top->info;
Node<T> *holder = top;
top = top->next;
delete(holder);
len--;
return ret;
} // STACK POP
template <class T>
int Stack<T>::EmptyStack()
{
return top == NULL;
} // EMPTY STACK
template <class T>
T Stack<T>::StackTop()
{
return top->info;
} // STACK TOP
template <class T>
unsigned int Stack<T>::StackLen()
{
return len;
} // STACK LEN
template <class T>
void Transfer(Stack<T> &a,Node<T> *p)
{
if(p->next)
Transfer(a,p->next);
a.Push(p->info);
} // TRANSFER
template <class T>
void Stack<T>::operator=(Stack<T> &right)
{
while(!this->EmptyStack())
Pop();
top = NULL;
len = 0;
Transfer(*this,right.GetTopPointer());
} // STACK OPERATOR =
template <class T>
ostream &operator<<(ostream &out,const Stack <T> &STACK)
{
Node<T> *p = STACK.top;
if(!p)
out << "{empty stack}" << endl;
else
{
out << "{" << p->info;
p = p->next;
for(;p;p = p->next)
out << "," << p->info;
out << "}" << endl;
}
return out;
} // STACK OPERATOR <<
// -------------------------------------------------------------------------
Te envio el programa del Stack, que con muy poca transformacion podras convertirlo en Queue.
// program k19a7.cpp - page 397
// bracket balance.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include "Stack.h"
#include <string.h>
int CheckNegativeCounters(int *counter)
{
for(int i = 0;i < 3;i++)
if(counter[i] < 0)
return 0;
return 1;
} // CHECK NEGATIVE COUNTERS
int CheckZeroCounters(int *counter)
{
for(int i = 0;i < 3;i++)
if(counter[i])
return 0;
return 1;
} // CHECK NEGATIVE COUNTERS
int Check(Stack<char> a)
{ // ( ) --> index = 0
int counter[3] = {0,0,0}; // [ ] --> index = 1
while(!a.EmptyStack()) // { } --> index = 2
{
switch(a.Pop())
{
case '(' : counter[0]++;
break;
case ')' : counter[0]--;
break;
case '[' : counter[1]++;
break;
case ']' : counter[1]--;
break;
case '{' : counter[2]++;
break;
case '}' : counter[2]--;
break;
}
if(!CheckNegativeCounters(counter))
return 0;
}
return CheckZeroCounters(counter);
} // CHECK
void Process(char *data)
{
Stack<char> a(strlen(data),data);
char *msg[2] = {"not balanced expression","balanced expression"};
cout << setw(30) << "giving string : " << data << endl;
cout << setw(27) << msg[Check(a)] << endl;
cout << "-----------------------------------------------------"
"-------------------------n";
} // PROCESS
void main()
{
clrscr();
cout << "bracket balance.n";
cout << "-----------------------------------------------------"
"-------------------------n";
char *data[5] = {"{[1+2]*b+3*(c+d)}",
"[a*(b+1)]-{[c-2]*(d+3-(e+{f*(4/(g+5)]})))}",
"[a*(b+1)]-{[c-2]*(d+3-(e+{f*[4/(g+5)]}))}",
"(({{[[100*a+b]]}}))","({{{[[a]]}}))"};
for(int i = 0;i < 5;i++)
Process(data[i]);
cout << "end of program - good bye ! ! !n";
getch();
} // MAIN
/*
bracket balance.
------------------------------------------------------------------------------
giving string : {[1+2]*b+3*(c+d)}
balanced expression
------------------------------------------------------------------------------
giving string : [a*(b+1)]-{[c-2]*(d+3-(e+{f*(4/(g+5)]})))}
not balanced expression
------------------------------------------------------------------------------
giving string : [a*(b+1)]-{[c-2]*(d+3-(e+{f*[4/(g+5)]}))}
balanced expression
------------------------------------------------------------------------------
giving string : (({{[[100*a+b]]}}))
balanced expression
------------------------------------------------------------------------------
giving string : ({{{[[a]]}}))
not balanced expression
------------------------------------------------------------------------------
end of program - good bye ! ! !
*/
// program Stack.h - page 393 . . . . .
// Header File for Stack class.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
// -------------------------------------------------------------------------
template <class T>
struct Node
{
T info;
Node<T> *next;
}; // STRUCT NODE
// -------------------------------------------------------------------------
template <class T>
class Stack
{
private:
Node<T> *top;
unsigned int len;
public:
Stack(int num = 0,T *data = NULL);
Stack(Stack<T> &right);
~Stack();
void Push(T);
T Pop();
int EmptyStack();
T StackTop();
unsigned int StackLen();
Node<T> *GetTopPointer() {return top;}
void operator=(Stack<T> &);
friend ostream &operator<<(ostream &,const Stack &);
}; // CLASS STACK
// -------------------------------------------------------------------------
template <class T>
Stack<T>::Stack(int num = 0,T *data = NULL)
{
top = NULL;
len = 0;
for(int i = num-1;i >= 0;i--)
Push(data[i]);
} // STACK CONSTRUCTOR
template <class T>
Stack<T>::Stack(Stack<T> &right)
{
top = NULL;
len = 0;
Transfer(*this,right.GetTopPointer());
} // COPY CONSTRUCTOR
template <class T>
Stack<T>::~Stack()
{
while(!this->EmptyStack())
Pop();
} // STACK DESTRUCTOR
template <class T>
void Stack<T>::Push(T INFO)
{
Node<T> *holder = top;
top = new Node<T>;
top->info = INFO;
top->next = holder;
len++;
} // STACK PUSH
template <class T>
T Stack<T>::Pop()
{
if(EmptyStack())
{
cout << "error : empty stack pop" << endl;
return 0;
}
T ret = top->info;
Node<T> *holder = top;
top = top->next;
delete(holder);
len--;
return ret;
} // STACK POP
template <class T>
int Stack<T>::EmptyStack()
{
return top == NULL;
} // EMPTY STACK
template <class T>
T Stack<T>::StackTop()
{
return top->info;
} // STACK TOP
template <class T>
unsigned int Stack<T>::StackLen()
{
return len;
} // STACK LEN
template <class T>
void Transfer(Stack<T> &a,Node<T> *p)
{
if(p->next)
Transfer(a,p->next);
a.Push(p->info);
} // TRANSFER
template <class T>
void Stack<T>::operator=(Stack<T> &right)
{
while(!this->EmptyStack())
Pop();
top = NULL;
len = 0;
Transfer(*this,right.GetTopPointer());
} // STACK OPERATOR =
template <class T>
ostream &operator<<(ostream &out,const Stack <T> &STACK)
{
Node<T> *p = STACK.top;
if(!p)
out << "{empty stack}" << endl;
else
{
out << "{" << p->info;
p = p->next;
for(;p;p = p->next)
out << "," << p->info;
out << "}" << endl;
}
return out;
} // STACK OPERATOR <<
// -------------------------------------------------------------------------