Lista #3

#include <iostream>

using namespace std;

typedef int Dado;

class noh {
    friend class lista;
    private:
        const Dado dado;
        noh* proximo;
    public:
        noh(Dado d = 0);
};

noh::noh(Dado d) : dado(d) {
    proximo = NULL;
}

class lista {
    private:
        noh* primeiro;
        noh* ultimo;
        int tamanho;
    public:
        lista();
        ~lista();
        void insere(Dado dado);
        void insere(Dado dado, int pos);
        void remove(int posicao);
        int procura(Dado valor);
        void imprime();
        inline bool vazia();
};

// constrói uma lista inicialmente vazia
lista::lista() {
    tamanho = 0;
    primeiro = NULL;
    ultimo = NULL;
}

lista::~lista() {
    noh* iter = primeiro;
    noh* proximo = NULL;
    while (iter != NULL) {
        proximo = iter->proximo;
        delete iter;
        iter = proximo;
    }
}

// método básico que *percorre* a lista, imprimindo seus elementos
void lista::imprime() {
    noh* aux = primeiro;
    while (aux != NULL) {
        cout << aux->dado << " ";
        aux = aux->proximo;
    }
    cout << endl;
}

// insere por padrão no final da lista
void lista::insere(Dado dado) {
    noh *no = new noh(dado);
    if (tamanho == 0) {
        primeiro = no;
        ultimo = no;
    }
    else {
        ultimo->proximo = no;
        ultimo = no;
    }
    tamanho++;
}

// insere um dado em uma determinada posição da lista
void lista::insere(Dado dado, int posicao) {
    noh *no = new noh(dado);
    if (posicao == 0) {
        no->proximo = primeiro;
        primeiro = no;
        tamanho++;
    }
    else if (posicao == tamanho) {
        ultimo->proximo = no;
        ultimo = no;
        tamanho++;
    }
    else if (posicao < tamanho)  {
        noh *aux = primeiro;
        int posAux = 0;
        while (posAux < (posicao-1)) {
            aux = aux->proximo;
            posAux++;
        }
        no->proximo = aux->proximo;
        aux->proximo = no;
        tamanho++;
    }
}

// remove o item da posição passada por parâmetro
// Atenção - o código deve tratar de posição inválidas
void lista::remove(int posicao) {
    if (tamanho > 0) {
        if (posicao == 0) {
            primeiro = primeiro->proximo;
            tamanho--;
        }
        else if (posicao < tamanho and posicao > 0) {
            noh *aux = primeiro;
            for (int i = 0; i < posicao-1; i++) {
                aux = aux->proximo;
            }
            aux->proximo = aux->proximo->proximo;
            tamanho--;
        }
    }
}

// procura por um elemento e retorna a posição ou -1 se não encontrado
int lista::procura(Dado valor) {
    noh *aux = primeiro;
    int pos = 0;
    while (aux != NULL) {
        if (aux->dado == valor)
            return pos;
        else {
            aux = aux->proximo;
            pos++;
        }
    }
    return -1;
}

// verifica se a lista está vazia
inline bool lista::vazia() {
    if (tamanho == 0)
        return true;
    return false;
}

int main() { // NÃO MODIFIQUE!
    lista minhaLista;
    char opcao;
    int valor, pos;
    cin >> opcao;
    while (opcao != 'Q') {
        switch(opcao) {
            case 'I':
                cin >> valor;
                minhaLista.insere(valor);
                break;
            case 'W':
                cin >> valor;
                cin >> pos;
                minhaLista.insere(valor, pos);
                break;
            case 'P':
                cin >> valor;
                cout << minhaLista.procura(valor) << endl;
                break;
            case 'R':
                cin >> pos;
                minhaLista.remove(pos);
                break;
            case 'V':
                cout << minhaLista.vazia() << endl;
                break;
        }
        cin >> opcao;
    }
    minhaLista.imprime();
    return 0;
}