[ganselo]

Вот реализация стека. Писал на 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++". Там все виды динамических структур данных.

[DaRiYs]

Спс, я уже сам разобрался. Только есть одна проблемка, када все было написано в одном файле то компилилось и работало, а када все было разбито по файлам то при компиляции выскакивают ошибки линкера Linker Eror: Undefined Symbol stack<int>::stack<int>() in module menu.cpp
Undefined Symbol stack<int>:utfile(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;
}

Помогите разобратся в проблемме плиз

[ganselo]

Думаю проблема в том, что компилятор не может найти реализацию методов из класса Stack<type>. Добавте в проект файл Stack.cpp. Т.к я не работал в BC++ 3.1 сказать точно, как это сделать, я не могу. (примерно так: Project->Add resource ну и там выбрать файл Stack.cpp).

[DaRiYs]

Так какраз все файлы *.cpp внесены в проэкт. Што теперь посоветуете?

[ganselo]

Ну попробуйте в menu.h и menu.cpp добавить #include "Stack.cpp".

[DaRiYs]

Все решилось, спасибо за помощь. Нада просто было в stack.h прописать #include "stack.cpp" Хотя непонятно почему без этого не работало если stack.cpp включен в проэкт.