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

16.02.2016Рубрика: ВопросыАвтор: admin

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

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

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

Post Views: 141

См. также: используйте install.sh в определенном conda env

1 arrays binary-search data-structures linear-search linked-list

Комментарии: 1

Aadnan Farooq A 16.02.2016 в 00:00
Невозможно выполнить бинарный поиск с использованием связанного списка. Представьте, что это ваш связанный список.
```
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
Ответить

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