#include<iostream>
#include<fstream>
#include<string>


using namespace std;

ifstream go("in.txt");
ofstream out("out.txt");

//#include "List.cpp"
template <class Item>
class List
{
	struct Element
	{
		Item inf;
		Element* next;
		Element(Item x) :inf(x), next(0)
		{
		}
	};

	Element* head; 	//указатель на начало списка
	int size;	// количество элементов в списке

//возвращает указатель на элемент списка с номером index
	Element* Find(int index)
	{
		if ((index < 1) || (index > size))	//если индекс элемента списка
		{					// находится вне диапазона, то
			return nullptr;		// возвращаем nullptr
		}
		else					//иначе
		{
			//устанавливаем указатель на начало списка
			Element* cur = head;
			for (int i = 1; i < index; i++)	// и перемещаемся по списку
			{	// на элемент с номером index
				cur = cur->next;
			}
			return cur;	//возвращаем указатель на требуемый элемент
		}
	}

public:
	List() :head(0), size(0)	//конструктор класса
	{
	}

	~List()	//деструктор класса
	{
		while (!Empty()) //пока список не пуст
		{
			Remove(1); //удаляем первый элемент списка
		}
	}

	bool Empty()	//проверка пустоты списка
	{
		return head == 0;
	}

	int GetLength() 	//возвращает количество элементов в списке
	{
		return size;
	}

	//возвращает значение элемента списка по его номеру
	Item Get(int index)
	{
		if ((index < 1) || (index > size))
		{
			std::cout << "Error";
		}
		else
		{
			Element* r = Find(index);
			Item i = r->inf;
			return i;
		}
	}

	//осуществляет вставку элемента со значением data в позицию index
	void Insert(int index, Item data)
	{
		if ((index < 1) || (index > size + 1))
		{
			std::cout << "Error";;
		}
		else
		{
			//создаем новый элемент
			Element* newPtr = new Element(data);
			size = GetLength() + 1;	//увеличиваем размерность списка
			if (index == 1) //если вставку производим в позицию 1
			{	//то см. рис. 16.6
				newPtr->next = head;
				head = newPtr;
			}
			else //иначе см. рис.16.7
			{
				Element* prev = Find(index - 1);
				newPtr->next = prev->next;
				prev->next = newPtr;
			}
		}
	}

	//осуществляет удаление элемента из списка с номером index
	void Remove(int index)
	{
		if ((index < 1) || (index > size))
		{
			std::cout << "Error";;
		}
		else
		{
			Element* cur;	//объявляем вспомогательный указатель	--size;		//уменьшаем размерность списка
			if (index == 1)	//если удаляем первый элемент
			{	//то см. рис. 16.8
				cur = head;
				head = head->next;
			}
			else	//иначе см. рис.16.9
			{
				Element* prev = Find(index - 1);
				cur = prev->next;
				prev->next = cur->next;
			}
			cur->next = nullptr;
			delete cur;
		}
	}

	//вывод элементов списка в глобальный поток out
	void Print()
	{
		for (Element* cur = head; cur != nullptr; cur = cur->next)
		{
			out << cur->inf << ' ';
		}
		out << std::endl;
	}
};


void main() {

	string word;
	char symbol;
	int count = 1;
	cout << "Vvedite symbol";

	cin >> symbol;
	List<string>list_word;//создаем список
	while (go >> word){//пока не конец файла собираем слова
		list_word.Insert(count, word);
		count++;//вставляем их в первый список в его конец (list_word.GetLength())
	}
	count = 1;
	List<string>list_word_copy;//создаем второй список под слова
	for (int i = 1; i <= list_word.GetLength(); i++) {

		word = list_word.Get(i);				//берем слово, тут они не удаляються как встеке и очереди, просто беруться
		if(word[0] == symbol) {
			list_word_copy.Insert(count, word);		//если слово нужное вставляем его в конец второго списка
			//list_word.Remove(i);	//удалем из первого списка слово
			//i--;
			count++;
		}
	}


	list_word.Print();//выводим первый список в файл
	out << endl;
	list_word_copy.Print();//выводим второй список в файл

	out.close();
	go.close();
	system("pause");
}