0

Na disciplina de estrutura de dados, o professor nos deu um código cpp com uma lista ordenada e nos pediu para implementar os métodos de busca binária, busca sequencial e inserção, mas não estou conseguindo identificar porque o programa executa mas a saída não é a esperada (termina retornando 1). Já tentei debugar, mas ainda não sou muito experiente nisso.

O código:

#include <iostream>

using namespace std;

class ListaOrdenada {
private:
    int * items;
    int tamanho, capacidade;
public:
    ListaOrdenada(int cap) {
        this->capacidade = cap;
        this->tamanho = 0;
        items = new int[cap];
    }

    ~ListaOrdenada() {
        delete [] items;
    }

    void insere(int key) {
        if (tamanho < capacidade) {
            int i = 0;
            while (key < items[i] and i <= tamanho) {
                i++;
            }
            int j = capacidade-1;
            for (; j > i; j--) {
                items[j] = items[j+1];
            }
            items[i] = key;
        }

    }

    int buscaSequencial(int key) {
        int i = 0;
        while (i <= tamanho) {
            if (items[i] == key) {
                return i;
            }
            i++;
        }
        return -1;
    }

    int buscaBinaria(int item) {
        return buscaBinaria(0, tamanho - 1, item);
    }

    int valida() {
        for (int i = 0; i < tamanho - 1; i++) {
            if (items[i] > items[i + 1]) return 0;
        }
        return 1;
    }

    void exibe() {
        for (int i = 0; i < tamanho; i++) {
            cout << i << ": " << items[i] << "; ";
        }
        cout << endl;
    }

private:

    int buscaBinaria(int inicio, int final, int item) {
        int meio = (inicio + final)/2;
        if (items[meio] == item) {
            return meio;
        }
        else if (items[meio] > item) {
            return buscaBinaria(inicio, meio, item);
        }
        else {
            return buscaBinaria(meio, final, item);
        }
    }

};


int main () {

    ListaOrdenada lista(10);

    int elementos [] = {10, 5, 25, 1, 5, 13, 50, 99, 33, 12};

    for (int i = 0; i < 10; i++) {
        lista.insere(elementos[i]);
    }

    cout << "Lista valida: " << (lista.valida()?"sim":"nao") << endl;
    lista.exibe();

    int teste [] = {5, 7, 16, 99, 45, 12, 33, 1, 60, 6};

    for (int i = 0; i < 10; i++) {
        cout << "Buscando " << teste[i] << ": sequencial = " << lista.buscaSequencial(teste[i]) << " binaria = " << lista.buscaBinaria(teste[i]) << endl;

    }

} 

1 Resposta 1

0

Tem vários erros no seu código. Arrumei a função insere e coloquei alguns comentários.

    void insere(int key) {
        if (tamanho < capacidade) {
            int i = 0;
            // primeiro tem que garantir que a posição é válida (i < tamanho)        
            // se quiser a lista ordenada de forma crescente, 
            //você deve inserir quando (key > items[i]) for falso
            while (i < tamanho and key > items[i]) { 
                i++;
            } // i está na posição em que será feita a inserção ou no final da lista (i == tamanho)
            int j = tamanho; // j é o tamanho da lista
            for (; j >= i; j--) { 
                items[j + 1] = items[j]; // desloca os elementos 
            }
            items[i] = key;
            tamanho += 1; // Aumenta o tamanho da lista após inserir
        }

    }

Para debugar você pode colocar alguns prints no meio do código para verificar se o valor de uma variável está no valor que você espera que esteja. Por exemplo:

for (int i = 0; i < 10; i++) {
    lista.insere(elementos[i]);
    // Imprime a lista para ver se está inserindo corretamente
    lista.exibe();
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .