линейный и бинарный поиск списка с использованием массивов и связанного списка

До сих пор в структуре данных я изучал список с использованием массивов и связанный список (одиночный, двойной и круговой) с использованием указателя. Следующее в схеме — линейный и бинарный поиск. Я нашел примеры линейного поиска по списку и связному списку. для бинарного поиска я нашел пример в списке с использованием массива, но нет примера для связанного списка (одинарного, двойного и циклического).
1) Я хочу знать, что бинарный поиск не может применяться к любому типу связанного списка?
2) Также в линейном поиске односвязного списка я видел этот код

if (ptr->data = = SearchElement){
indexPtr = ptr;
return indexPtr;}

В этом случае, когда он найдет элемент, он вернет адрес указателя, правильно ли это? не было инициализации indexPtr, поэтому я предположил, что это также указатель типа узла.

См. также:  Указатели C ++ (1)
Понравилась статья? Поделиться с друзьями:
IT Шеф
Комментарии: 1
  1. Aadnan Farooq A

    Невозможно выполнить бинарный поиск с использованием связанного списка. Представьте, что это ваш связанный список.

    1->2->3->4->5->6 and you are searching for 1.
    

    Вы не можете получить 3-й элемент за постоянное время. В бинарном поиске вы должны перейти к элементу, когда захотите. Предположим, что ваш связанный список составляет 1 миллион узлов. Есть ли способ перейти к 500 000-му узлу за постоянное время? Если ответ да, то в любой реализации связанного списка вы можете найти его за O(log(n)).

    Проверьте это и это вопросы и ответы.

    Код линейного поиска должен быть примерно таким.

    ptr = head;
    while (ptr-> next != null)
        if(ptr -> data == searchedElement)
            return ptr;
    

    Он вернет вам указатель, указывающий на соответствующий узел.

    Прошло какое-то время, я не проверял, но должно быть так.

    cout << "address of ptr: " << &ptr << " address of node " << ptr << " value inside the node " << *ptr << endl; 
    

    1) бинарный поиск не может применяться к любому связанному списку (одиночному, двойному и круговому)? Можете ли вы более четко объяснить, почему нет возможности использовать двоичный поиск для связанного списка? 2) если я хочу показать вывод возврата, тогда он покажет адрес соответствующего узла, это правильно? person Aadnan Farooq A; 16.02.2016

    это означает, что мы можем применить бинарный поиск к тем проблемам, когда мы можем получить доступ к любому элементу за константное время, как в массиве, верно? person Aadnan Farooq A; 16.02.2016

    не совсем, есть типы, к которым вы обращаетесь в постоянное время, но вы не можете выполнять бинарный поиск. Например, хэш. Кроме того, для бинарного поиска массив должен быть отсортирован. вы можете выполнять бинарный поиск в массиве, массиве, векторе, матрице, когда они отсортированы. person Aadnan Farooq A; 16.02.2016

    Итак, каковы точные причины того, что бинарный поиск не работает со связанным списком. person Aadnan Farooq A; 16.02.2016

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: