#include "string.h"
#include "stdio.h"

struct SNo
{
	 char palavra[20];
	 SNo * prox;
	 SNo * ant;
};

SNo * palavras = NULL;

void Insere(SNo * * palavras, char * palavra)
{
	 SNo * novo;
	 SNo * pi; // Ponto de Insercao
	 SNo * antpi; // No anterior ao ponto de insercao

	 novo = new SNo;
	 strcpy(novo->palavra, palavra);
	 novo->prox = NULL;
	 novo->ant = NULL;

	 if(*palavras == NULL)
	 {
		 *palavras = novo;
	 }
	 else
	 {

		 antpi = NULL;
		 for(pi=*palavras ; pi!=NULL && strcmp(palavra,pi->palavra)>0 ; pi=pi->prox)
		 {
			 antpi = pi;
		 }

		 if(pi==NULL) // Palavra maior que todas as outras. Insercao no final
		 {
				antpi->prox = novo;
				novo->ant = antpi;
		 }
		 else
		 {
				if(antpi != NULL) antpi->prox = novo;
				else // Primeiro elemento da lista. Alterar Ponteiro para Inicio.
				{
					 *palavras = novo;
				}
				pi->ant = novo;
				novo->prox = pi;
				novo->ant = antpi;
		 }
	 }
}

void MostraListaR(SNo * inicio)
{
	 if(inicio==NULL) return;
	 else
	 {
			printf("%s ",inicio->palavra);
			MostraListaR(inicio->prox);
	 }
}


void main()
{
	 char Temp[20];
	 int i;

	 strcpy(Temp,"lixo");

	 while(strcmp(Temp,"fim") != 0)
	 {
			 printf("Digite Qualquer Palavra ou <fim> para sair: ");
			 scanf("%s",Temp);
			 Insere(&palavras,Temp);
			 MostraListaR(palavras);
			 printf("\n");
	 }
}