VPF::Бинарный поиск - Форум программистов

marysia

Дата 22.3.2006, 19:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2006

Репутация: нет
Всего: нет

дано задание-Написать программу, реализующую поиск имени абонента телефонной станции по его телефонному номеру. Телефонный справочник организован однонаправленным списком. Поиск произвести методом бинарного поиска.
Сам список и вывод составила.А поис по абоненту не получается.Помогите.

Код


//#include "stdafx.h"
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

const l=4;
struct El
{
    char name[20];
    char *tel;
    El *next;
};

void vivod(El *E) //вывод списка
{
    do 
{cout<<E->name<<" :   ";
cout<<E->tel<<"\n";
E=E->next;}
while(E!=NULL);
}

void main()
{
char buf[255];
cout<<"\n";
El *E=new El;
E->next=NULL;
cout<<"name:  ";
cin>>E->name;
cout<<"tel:  ";
cin>>buf;
E->tel=strdup(buf);
El *head=E; 
for(int i=2;i<=l;i++)
{                      //Создание списка
    cout<<"\n";
    E->next=new El;
    E=E->next;
    cout<<"name:  ";
    cin>>E->name;
    cout<<"tel:  ";
    cin>>buf;
    E->tel=strdup(buf);
    E->next=NULL;
};
cout<<"*******************************\n";
vivod(head);
El *P=new El;
cout<<"\n"<<"Vvedite tel\n";
cin>>P->tel;

}

sergejzr

Дата 22.3.2006, 19:18 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Условием бинарного поиска является то, что список просортирован!

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

marysia

Дата 22.3.2006, 19:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2006

Репутация: нет
Всего: нет

Я знаю ,но у меня именно с сортировкой и с поиском проблема

sergejzr

Дата 22.3.2006, 19:32 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Ну поиск вот...

Код


//Возвратит искомый El или NULL, если его не существует
El binarSearch(El *a, int start, int end, const char* key)
{
   int mitte,cmp;

   while(start <= end)                    // пока в листе чтото есть
   {
      mitte = (start + end) / 2;
      cmp=strcmp(a[mitte].name ,key);
      if(cmp==0)
         return mitte;                    // Нашли
      else if(cmp<0)
         start = mitte + 1;               // Ищем справа
      else // cmp>0
         end = mitte - 1;                 // Ищем слева
   }

   return NULL;
}

Писал на коленке, но вроде всё ОК
Добавлено @ 19:34
Кстати, это работает только с массивом. Бинарный поиск по листу невозможен!

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

cardinal

Дата 22.3.2006, 19:44 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 15
Всего: 99

Не по листу, а по списку наверно? smile

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

marysia

Дата 22.3.2006, 19:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2006

Репутация: нет
Всего: нет

Вот мне по списку надо для данной программы.Завтра сдавать.а не получается

sergejzr

Дата 22.3.2006, 19:51 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Я наверное отстал от жизни. Это на самом деле практикуется? Бинарный поиск по списку?

Какой то бред smile

. Ну отличие только в том, что надо по списку бежать, а не по индексу брать.

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

cardinal

Дата 22.3.2006, 22:22 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 15
Всего: 99

Цитата(sergej.z @ 22.3.2006, 17:51

)

Какой то бред

Особенно если список однонаправленный... Да, тоже пока не понял в чем прикол. smile

Точнее организовать поиск можно как угодно через ж4№%, но толку то от такого поиска?

Не исключаю, что под бинарным поиском имелось в виду нечто другое, чем ты подумал sergej.z.

--------------------

marysia

Дата 22.3.2006, 22:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2006

Репутация: нет
Всего: нет

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

Fixin

Дата 22.3.2006, 22:27 (ссылка)

(нет голосов)

Загрузка ...

Ёжик

Профиль
Группа: Комодератор
Сообщений: 1357
Регистрация: 6.1.2004

Репутация: 5
Всего: 18

Я не пойму, чего вы не понимаете? Отсортировать список и дихотомить скока влезет.

--------------------

Пользуйтесь ссылкой <<решенный\нерешенный вопрос>>
IRC-канал Винграда

sergejzr

Дата 22.3.2006, 22:30 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Гы я имел ввиду то, что называется бинарным поиском.
Или может дерево собрать....?

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

marysia

Дата 22.3.2006, 22:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2006

Репутация: нет
Всего: нет

не могу сделать именно по той программе бинарный поиск+ для того чтобы искать , нужно отсортировать

Fixin

Дата 22.3.2006, 22:33 (ссылка)

(нет голосов)

Загрузка ...

Ёжик

Профиль
Группа: Комодератор
Сообщений: 1357
Регистрация: 6.1.2004

Репутация: 5
Всего: 18

ИМХО, бинарный - поиск в упорядоченном массиве, где сначала искомый сравнивается с центральным, потом с центральным из левой или правой половины и тд.

--------------------

Пользуйтесь ссылкой <<решенный\нерешенный вопрос>>
IRC-канал Винграда

cardinal

Дата 22.3.2006, 22:41 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 15
Всего: 99

Может надо пройтись по списку, вставить значения в массив, а потом уже сортировать? smile

Добавлено @ 22:42
А потом уже новый список лепить...

--------------------

marysia

Дата 22.3.2006, 22:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 22.3.2006

Репутация: нет
Всего: нет

Вот пример М-блочного поиска для такого же списка,только как его переделать под бинарный???????????????

Код


char* List::poisk(int n, char *slovo, Node **mas)
{
    int m=int(sqrt(n));//pow(n,0.5));
    int k=int(n/m);
    char *perevod=new char[50];
    strcpy(perevod,"");

    int a=0,b=n-1;
    int j=0;

    while(a!=b)
    {
        if(j<=b)
        if(strcmp(mas[j]->get_en_s(),slovo)==0)
        {
            strcpy(perevod,mas[j]->get_rus_s());
            return perevod;
        };

        if(j>b)
        {
            b=n-1;
            a=b-k+1;
            n=k;
            m=int(sqrt(n))+1;
            k=int(n/m);
            j=a;

        }
        else
        if(strcmp(mas[j]->get_en_s(),slovo)==1)
        {
            b=j-1;
            a=b-k+1;
            n=k;
            m=int(sqrt(n))+1;
            k=int(n/m);
            j=a;
        };

        j+=k;
    };
        return perevod;
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »