Logical Error in Sorted List (C ++)

Question

Logical Error in Sorted List (C ++)

Navigation

#1 by (0 votes)

0

In the data structure discipline, the teacher gave us a cpp code with an ordered list and asked us to implement the methods of binary search, sequential search and insertion, but I can not identify why the program executes but the output does not is expected (ends up returning 1). I've tried debugging, but I'm still not very experienced at it.

The code:

#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;

    }

}

c++

asked by anonymous 26.10.2017 / 19:26

1 answer

Create a package from another Sort a list of objects by a string list

score 0 · Answer 1

You have several errors in your code. I set up the insert function and I put some comments.

    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
        }

    }

To debug you can put some prints in the middle of the code to check if the value of a variable is in the value you expect it to be. For example:

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