Бинарный поиск в 2-связном списке Опции

[-Антон-]

Как осуществить поиск в 2-связном списке без нумерации его элементов.
Список уже отсортирован.

С номерами у меня так получилось:

Zveno=^r;
r= record
s:st;
N:integer;
next,pred:zveno;
end;


{-----Процедура поиска элемента списка по его номеру-----}
procedure spi(k:integer; var spis:zveno);
begin
if k<spis^.N then
while (k<spis^.N)do
begin
 spis:=spis^.pred;
 if spis^.pred=nil then exit;
end
   else
if k>spis^.N then
while (k>spis^.N)do
begin
 if (spis^.next=nil) then exit;
 spis:=spis^.next;
 end
end;


{-----Поиск в списке-----}
procedure TForm1.P3Click(Sender: TObject);
Var i,i1,m:Integer; b:Boolean;
x:st;
sp:zveno;
  Begin
x:=edit1.text;   label7.Caption:='0';
sp:=spisok^.next;
     i:=1; i1:=j;         {На первом шаге рассматривается весь массив.}
     b:=False;            {Признак того, что Х не найден.}
While (i<=i1) And Not b Do
Begin
  m:=(i+i1) Div 2;        {Среднее}
  spi(m,sp);   caption:=caption+inttostr(sp^.N)+',';
  If sp^.s=X Then b:=True  {Элемент найден, поиск прекращается.}
   Else If sp^.s <X Then i:=m+1 {Исключаем из рассмотрения левую часть списка }
    Else i1:=m-1               {Правую часть.}
End;

if b then label7.Caption:=inttostr(m);
caption:=caption+'|_|';
End;

[volvo]

Как осуществить поиск в 2-связном списке без нумерации его элементов.

Кто бы мне еще объяснил, зачем для поиска элемента в списке нужно нумеровать элементы? Поиск осуществляется одним проходом по списку...

[Guest]

А как найти средний элемент в списке, Ведь так действует бинарный поиск.
Сначала средний во всём списке, потом средний в его половине .....

[volvo]

А бинарный поиск вообще неприменим к спискам... Он применяется для отсортированных массивов... Чувствуешь разницу?

[Guest]

И как мне это информатичек обьяснить, если стоит задача: отсортировать массив, список, файл и произвести в них бинарный поиск. Сказать, чтоб на повышение квалификации записалась???

[-Антон-]

Может где информация по спискам есть, книжки какие-нить, статьи, чё ещё бывает, Или простым последовательным поиском искать?

[volvo]

Ну, если уж так нужно сделать именно бинарный поиск в списке, то можно просто напросто убрать нумерацию из самих узлов и работать с порядковыми номерами элементов (правда, быстродействие пострадает).

Посмотри вот здесь: Указатель на i элемент списка, я приводил функцию, которая без всякой нумерации элементов просто по порядковому номеру находит сам элемент (правда, список односвязный, но в данном случае это ничего не меняет).

Дальше разберешься?

[Guest]

Да, конечно, бинарный поиск в списке- это извращение, но вроде получилось без номеров:

Код

type
st=string[5];

Zveno=^r;
r= record
s:st;
next,pred:zveno;
end;

var
spisok,begun:zveno;

{Сортировка}
procedure TForm1.Button7Click(Sender: TObject);
var x1,sp:zveno;

s,a1:st;
begin
sp:=spisok^.next;       {Первый значащий элемент списка}
while sp^.next<>nil do
begin
x1:=sp;
s:=x1^.next^.s;          {Инф. из списка после первого}
while (x1^.pred<>nil) And (s<x1^.s) Do
begin
a1:=x1^.s;
x1^.s:=x1^.next^.s;
x1^.next^.s:=a1;

  x1:=x1^.pred;
end;
x1^.next^.s:=s;
x1:=sp^.next;
sp:=sp^.next;


end;

P3.Enabled:=true;
end;


{-----Процедура поиска элемента списка по номеру, зная начальный-----}
procedure spi(nast,k:integer; var spis:zveno);
var l,i:integer;
begin
i:=0;
l:=abs(nast-k);         {Столько нужно пролистать}
if nast>k then          {Если счас номер эл. списка больше искомого, то искать "назад"}
while l>i do
begin
i:=i+1;                 {Счётчик пролистаных звеньев}  
spis:=spis^.pred;
if spis^.pred=nil then exit;
end
  else
if nast<k then          {Если счас номер эл. списка меньше искомого, то искать "вперёд"}
while l>i do
begin
i:=i+1;                 {Счётчик пролистаных звеньев}
if (spis^.next=nil) then exit;
spis:=spis^.next;
end
end;


{-----Поиск в списке-----}
procedure TForm1.P3Click(Sender: TObject);
Var i,i1,m,n:Integer; b:Boolean;
x:st;
sp:zveno;
 Begin
x:=edit1.text;   label7.Caption:='0';
sp:=spisok^.next;
   n:=1;                       {Начальный номер эл. списка}
   i:=1; i1:=j;                {На первом шаге рассматривается весь массив.}
   b:=False;                   {Признак того, что Х не найден.}
While (i<=i1) And Not b Do      {Пока нижняя граница меньше= верхней}
Begin
 m:=(i+i1) Div 2;              {Среднее}
 spi(n,m,sp);                  {Процйедура поиска нужного звена}

 If sp^.s=X Then b:=True       {Элемент найден, поиск прекращается.}
  Else If sp^.s <X Then i:=m+1 {Исключаем из рассмотрения левую часть списка }
   Else i1:=m-1;               {Правую часть.}
n:=m;                           {Запомнить, проверенное звено}
End;

if b then label7.Caption:=inttostr(m);

End;

<_< Только оспаётся ощущение, что я написал кучку бесполезного кода