Реализация стека и методы работы с ним в Borland Turbo C++ 3.11
Ребята помогите с реализацией стека на основе односвязного или двусвязного списка и реализацией основных методов работы с ним: добавление элементов, удаление, вывод одно\всех елементов на экран\в файл, сортировка, поиск. Дело в том што я никада с таким не работал, а пришлось( Начал сам разбиратся и никак не могу вкурить( Помогите плиз
|
Вот реализация стека. Писал на 1 курсе... (задание было такое. Реальзовать стек на базе списка. С помощью этого стека реализовать Т-образный перекрёсток для отсеевания поездов). Код "грубый"..
Код:
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
class node
{
friend class stack;
public:
node(const int &data = 0) : d(data), nextPtr(NULL){}
int getData() const { return d; }
node *getNextNode() const { return nextPtr; }
private:
node *nextPtr;
int d;
};
class stack
{
public:
stack() : top(NULL){}
~stack();
void inserRand(const int size);
void insertKeyboard(const int size);
void insertFile(const char *path);
void insert(const int &data);
bool empty() const { return top == 0; }
void sort();
void razdelit(const int val);
void proverka();
node *getTopNode() const{ return top; }
private:
node *top;
node *getNewNode(const int &data);
friend ostream& operator <<(ostream &out, stack &print);
friend stack& operator +(stack &one, stack &two);
};
ostream& operator <<(ostream &out, stack &print)
{
node *currentPtr = print.top;
while(currentPtr != NULL)
{
out << currentPtr->getData() << " ";
currentPtr = currentPtr->getNextNode();
}
return out;
}
stack& operator +(stack &one, stack &two)
{
stack *out = new stack;
if(!two.empty())
{
stack *twoTemp = new stack;
node *temp = two.getTopNode();
while(temp != NULL)
{
twoTemp->insert(temp->getData());
temp = temp->getNextNode();
}
temp = twoTemp->getTopNode();
while(temp != NULL)
{
out->insert(temp->getData());
temp = temp->getNextNode();
}
delete twoTemp;
}
if(!one.empty())
{
stack *oneTemp = new stack;
node *temp = one.getTopNode();
while(temp != NULL)
{
oneTemp->insert(temp->getData());
temp = temp->getNextNode();
}
temp = oneTemp->getTopNode();
while(temp != NULL)
{
out->insert(temp->getData());
temp = temp->getNextNode();
}
delete oneTemp;
}
return *out;
}
stack::~stack()
{
if(!empty())
{
node *tempPtr, *currentPtr = top;
while(currentPtr != NULL)
{
tempPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
delete tempPtr;
}
}
}
void stack::insert(const int &data)
{
node *newNode = getNewNode(data);
if(empty())
{
top = newNode;
}
else
{
newNode->nextPtr = top;
top = newNode;
}
}
node *stack::getNewNode(const int &data)
{
node *newNode = new node(data);
if(newNode != NULL)
return newNode;
else
cerr << "Error. No memory available" << endl << endl;
return NULL;
}
void stack::sort()
{
stack *one = new stack;
stack *two = new stack;
node *currentPtr = top;
while(currentPtr != NULL)
{
if(currentPtr->getData() == 0) one->insert(0);
else two->insert(currentPtr->getData());
currentPtr = currentPtr->nextPtr;
}
cout << endl << endl;
cout << *one;
cout << endl << endl;
cout << *two;
}
void stack::inserRand(const int size)
{
srand(time(NULL));
for(int i = 0; i < size; i++)
this->insert(rand()%2);
}
void stack::insertKeyboard(const int size)
{
int data;
for(int i = 0; i < size; i++)
{
cin >> data;
this->insert(data);
}
}
void stack::insertFile(const char *path)
{
ifstream file(path, ios::in);
if(!file) cerr << "Error. File is not found." << endl;
else
{
int data;
while(!file.eof())
{
file >> data;
this->insert(data);
}
}
}
void stack::razdelit(const int val)
{
int proverka = 0;
stack *one = new stack;
stack *two = new stack;
stack *oneTemp = new stack;
stack *twoTemp = new stack;
node *temp = this->getTopNode();
while(temp != NULL)
{
temp = temp->getNextNode();
proverka++;
}
temp = this->getTopNode();
for(int i = 0; i < val; i++)
{
one->insert(temp->getData());
temp = temp->getNextNode();
}
for(int i = val; i < proverka; i++)
{
two->insert(temp->getData());
temp = temp->getNextNode();
}
temp = one->getTopNode();
while(temp != NULL)
{
oneTemp->insert(temp->getData());
temp = temp->getNextNode();
}
temp = two->getTopNode();
while(temp != NULL)
{
twoTemp->insert(temp->getData());
temp = temp->getNextNode();
}
cout << endl << "1: " << *oneTemp << endl;
cout << "2: " << *twoTemp << endl;
delete one, two, oneTemp, twoTemp;
}
void stack::proverka()
{
node *temp = this->getTopNode();
int proverk = 0;
while(temp != NULL)
{
temp = temp->getNextNode();
proverk ++;
}
if(proverk >= 30)
{
this->razdelit(proverk/2);
}
}
#endif // STACK_H_INCLUDED
А вообще советую открыть (если нету то в гугле: скачать книгу "Как программировать на C++" Авторы Харви Дейтел & Пол Дейтел) книгу "Как программировать на C++". Там все виды динамических структур данных. |
Спс, я уже сам разобрался. Только есть одна проблемка, када все было написано в одном файле то компилилось и работало, а када все было разбито по файлам то при компиляции выскакивают ошибки линкера Linker Eror: Undefined Symbol stack<int>::stack<int>() in module menu.cpp
Undefined Symbol stack<int>::outfile(char near*) in module menu.cpp
element.h
Код:
#ifndef _selem
#define _selem
template <class type> class Elem
{
public:
type data;
Elem <type> *next, *prev;
Elem();
};
#endif
stack.h
Код:
#include "selem.h"
#ifndef _stack
#define _stack
template <class type> class Stack
{
private:
Elem <type> *start, *end;
type *mass;
int count;
public:
Stack();
void AddEnd(type ntype);
Stack(const Stack<type> & nstack);
Elem<type>* GetElem(int pos);
void AddStart(type newdata);
void Del(int pos);
void Print(int pos);
void ToMass();
void OutMass();
void bubbleSort();
int increment(type* inc, int size);
void shellSort();
int linfind(type x);
void Print();
void DelAll();
int GetCount();
void Insert(int pos,type data);
void ToFile(char* fname);
Stack<type>& operator = (const Stack<type> & nstack);
Stack <type> operator + (const Stack<type> &nstack);
void Invert();
void OutFile(char* ffname);
~Stack();
};
#endif
stack.cpp
Код:
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <fstream.h>
#include "selem.h"
#include "stack.h"
#include "menu.h"
template <class type> Stack<type>::Stack()
{
start=end=0;
count=0;
};
template <class type> void Stack<type>::AddEnd(type ntype)
{
Elem<type> *temp= new Elem <type>;
temp->next=0;
temp->data=ntype;
temp->prev=end;
if(end)
end->next=temp;
if(!count)
start=end=temp;
else
end=temp;
count++;
};
template <class type> Stack<type>::Stack(const Stack<type> &nstack)
{
start=end=0;
count=0;
Elem<type> *temp=nstack.start;
while(temp)
{
AddEnd(temp->data);
temp=temp->next;
}
};
template <class type> Elem<type>* Stack<type>::EGetElem(int pos)
{
Elem<type> *temp=start;
if(pos<1 || pos>count)
{
cout<<"Incorrect position!\n";
return NULL;
}
for(int i=1; i<pos && temp!=0; i++)
{
temp=temp->next;
}
if(temp==0)
return 0;
else
return temp;
};
template <class type> void Stack<type>::AddStart(type newdata)
{
Elem<type> *temp=new Elem<type>;
temp->prev=0;
temp->data=newdata;
temp->next=start;
if(start)
start->prev=temp;
if(!count)
start=end=temp;
else
start=temp;
count++;
};
template <class type> void Stack<type>::Del(int pos)
{
if(pos<1 || pos>count)
{
cout<<"Incorrect position!\n";
return;
}
Elem<type> *del=start;
for(int i=1; i<pos; i++)
del=del->next;
Elem<type>* PrevDel=del->prev;
Elem<type>* AfterDel=del->next;
if(PrevDel!=0&&count!=1)
PrevDel->next=AfterDel;
if(AfterDel!=0&&count!=0)
AfterDel->prev=PrevDel;
if(pos==1)
start=AfterDel;
if(pos==count)
end=PrevDel;
delete del;
count--;
};
template <class type> void Stack<type>::Print(int pos)
{
if(pos<1 || pos>count)
{
cout<<"Incorrect position\n";
return;
}
Elem<type> *temp;
if(pos<=count/2)
{
temp=start;
for(int i=1; i<pos; i++)
temp=temp->next;
}
else
{
temp=end;
for(int i=1; i<=count-pos;i++)
temp=temp->prev;
}
cout<<temp->data;
};
template <class type> void Stack<type>::ToMass()
{
if(count)
{
mass=(type*)malloc(count+2);
Elem<type> *temp=start;
for(int i=0; temp; i++)
{
mass[i]=temp->data;
temp=temp->next;
}
}
};
template <class type> void Stack<type>::OutMass()
{
if(count)
{
Elem<type> *temp=start;
for(int i=0; temp; i++)
{
temp->data=mass[i];
temp=temp->next;
}
}
};
template <class type> void Stack<type>::bubbleSort()
{
if(count)
{
ToMass();
type x;
for(long i=0; i < count; i++)
{
for(long j = count-1; j > i; j-- )
{
if ( mass[j-1] > mass[j] )
{
x=mass[j-1];
mass[j-1]=mass[j];
mass[j]=x;
}
}
}
OutMass();
}
};
template <class type> int Stack<type>::increment(type* inc, int size)
{
type p1, p2, p3;
int s;
p1 = p2 = p3 = 1;
s = -1;
do
{
if (++s % 2)
{
inc[s] = 8*p1 - 6*p2 + 1;
}
else
{
inc[s] = 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
}
while(3*inc[s] < size);
return s > 0 ? --s : 0;
};
template <class type> void Stack<type>::shellSort()
{
if(count)
{
ToMass();
int inc, seq[40];
int s;
s = increment(seq, count);
while (s >= 0)
{
inc = seq[s--];
for (int i = inc; i < count; i++)
{
type temp = mass[i];
for (int j = i-inc; (j >= 0) && (mass[j] > temp); j -= inc)
mass[j+inc] = mass[j];
mass[j+inc] = temp;
}
}
OutMass();
}
};
template <class type> int Stack<type>::linfind(type x)
{
if(count)
{
ToMass();
int state=0;
for (int i=0;i<count;i++)
if (x == mass[i])
{
return i+1;
state=1;
break;
}
if(!state)
cout<<"There is no math\n";
}
};
template <class type> void Stack<type>::Print()
{
if(count)
{
Elem<type> *temp=start;
while(temp)
{
cout<<temp->data<<" ";
temp=temp->next;
}
}
};
template <class type> void Stack<type>::DelAll()
{
while(count)
Del(1);
};
template <class type> int Stack<type>::GetCount()
{
return count;
};
template <class type> void Stack<type>::Insert(int pos,type data)
{
if(pos < 1 || pos > count + 1)
{
cout << "Incorrect position !!!\n";
return;
}
if(pos == count + 1)
{
AddEnd(data);
return;
}
else
if(pos == 1)
{
AddStart(data);
return;
}
int i = 1;
Elem<type>* Ins = start;
while(i < pos)
{
Ins = Ins->next;
i++;
}
Elem<type>* PrevIns = Ins->prev;
Elem<type>* temp = new Elem<type>;
temp->data=data;
if(PrevIns != 0 && count != 1)
PrevIns->next = temp;
temp->next = Ins;
temp->prev = PrevIns;
Ins->prev = temp;
count++;
};
template <class type> void Stack<type>::ToFile(char* fname)
{
if(count)
{
ofstream fout(fname);
Elem<type> *temp=start;
for(int i=0; i<count; i++)
{
fout<<temp->data<<'\n';
temp=temp->next;
}
fout.close();
}
};
template <class type> Stack<type>& Stack<type>::operator = (const Stack<type> & nstack)
{
if(this==&nstack)
return *this;
this->DelAll();
Elem<type> *temp=nstack.start;
while(temp)
{
AddEnd(temp->data);
temp=temp->next;
}
return *this;
};
template <class type> Stack<type> Stack<type>::operator + (const Stack<type> &nstack)
{
Stack<type> result(*this);
Elem<type> *temp=nstack.start;
while(temp)
{
result.AddEnd(temp->data);
temp=temp->next;
}
return result;
};
template <class type> void Stack<type>::Invert()
{
ToMass();
type temp;
for(int i=0; i<count/2;i++)
{
temp=mass[count-1-i];
mass[count-1-i]=mass[i];
mass[i]=temp;
}
OutMass();
};
template <class type> void Stack<type>::OutFile(char* ffname)
{
DelAll();
ifstream fin(ffname);
type a;
Elem<type> *temp=start;
while(fin.eof()==0)
{
fin>>a;
AddStart(a);
temp=temp->next;
}
Del(1);
Invert();
fin.close();
};
template <class type> Stack<type>::~Stack()
{
DelAll();
};
menu.h
Код:
#include "selem.h"
#include "stack.h"
#ifndef _menu
#define _menu
class Menu
{
private:
Stack<int> st;
char ch;
public:
void main_mnu();
Menu();
};
#endif
menu.cpp
Код:
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <fstream.h>
#include "selem.h"
#include "stack.h"
#include "menu.h"
void Menu::main_mnu()
{
clrscr();
cout<<"1. Add n-th element of stack\n2. Delete n-th element of stack\n3. Destroy stack\n4. View n-th element of stack\n5. View all stack\n6. Sort stack\n7. Find in stack\n8. Save stack to file\n9. Read from file to stack\n0. Exit\n";
a:ch=getch();
if((int)ch<48||(int)ch>57)
goto a;
int a,b;
flushall();
switch(ch)
{
case '1': cout<<"Enter position & data: ";cin>>a>>b; st.Insert(a,b);break;
case '2': cout<<"Enter position: "; cin>>a; st.Del(a); break;
case '3': cout<<"Stack destroyed!";st.DelAll(); getch(); break;
case '4': cout<<"Enter position: "; cin>>a; st.Print(a); getch();break;
case '5': cout<<"All stack: \n"; st.Print();getch();break;
case '6': cout<<"Choose the method:\n1. Bubble\n2. Shell\n";b: if((int)getch()==50){ st.bubbleSort();break;} else if((int)getch()==51) {st.shellSort();break;} else goto b;
case '7': cout<<"Enter what find: ";cin>>a;cout<<"There is "<<st.linfind(a)<<" element"; getch(); break;
case '8': cout<<"Stack saved to file stack.txt!"; st.ToFile("stack.txt"); getch(); break;
case '9': cout<<"Stack read from file stack.txt!"; st.OutFile("stack.txt"); getch(); break;
case '0': exit(1);
}
main_mnu();
}
Menu::Menu()
{
main_mnu();
}
main.cpp
Код:
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <fstream.h>
#include "selem.h"
#include "stack.h"
#include "menu.h"
void main()
{
Menu m;
}
Помогите разобратся в проблемме плиз |
Думаю проблема в том, что компилятор не может найти реализацию методов из класса Stack<type>. Добавте в проект файл Stack.cpp. Т.к я не работал в BC++ 3.1 сказать точно, как это сделать, я не могу. (примерно так: Project->Add resource ну и там выбрать файл Stack.cpp).
|
Так какраз все файлы *.cpp внесены в проэкт. Што теперь посоветуете?
|
Ну попробуйте в menu.h и menu.cpp добавить #include "Stack.cpp".
|
Все решилось, спасибо за помощь. Нада просто было в stack.h прописать #include "stack.cpp" :biggrin: Хотя непонятно почему без этого не работало если stack.cpp включен в проэкт. :dont-know :read: :closed-to
|
Время: 06:17.
© OSzone.net 2001-
