Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Бинарный поиск, помогите !! 
:(
    Опции темы
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;

}
PM MAIL   Вверх
sergejzr
Дата 22.3.2006, 19:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


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

Репутация: 11
Всего: 360
Условием бинарного поиска является то, что список просортирован!



--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
marysia
Дата 22.3.2006, 19:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Я знаю ,но у меня именно с сортировкой и с поиском проблема
PM MAIL   Вверх
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.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
cardinal
Дата 22.3.2006, 19:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


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

Репутация: 15
Всего: 99
Не по листу, а по списку наверно? smile


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

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
marysia
Дата 22.3.2006, 19:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Вот мне по списку надо для данной программы.Завтра сдавать.а не получается
PM MAIL   Вверх
sergejzr
Дата 22.3.2006, 19:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


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

Репутация: 11
Всего: 360
Я наверное отстал от жизни. Это на самом деле практикуется? Бинарный поиск по списку?

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


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
cardinal
Дата 22.3.2006, 22:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


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

Репутация: 15
Всего: 99
Цитата(sergej.z @ 22.3.2006, 17:51 Найти цитируемый пост)
Какой то бред

Особенно если список однонаправленный... Да, тоже пока не понял в чем прикол. smile Точнее организовать поиск можно как угодно через ж4№%, но толку то от такого поиска?

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


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

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
marysia
Дата 22.3.2006, 22:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Нам дали такое задание и завтра сдавать, чтобы получить допуск на зачет.Помогите плиз в эту программу поиск сделать
PM MAIL   Вверх
Fixin
Дата 22.3.2006, 22:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Ёжик
***


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

Репутация: 5
Всего: 18
Я не пойму, чего вы не понимаете? Отсортировать список и дихотомить скока влезет.


--------------------
Пользуйтесь ссылкой <<решенный\нерешенный вопрос>>
IRC-канал Винграда
PM MAIL ICQ   Вверх
sergejzr
Дата 22.3.2006, 22:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


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

Репутация: 11
Всего: 360
Гы я имел ввиду то, что называется бинарным поиском.
Или может дерево собрать....?


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
marysia
Дата 22.3.2006, 22:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
не могу сделать именно по той программе бинарный поиск+ для того чтобы искать , нужно отсортировать
PM MAIL   Вверх
Fixin
Дата 22.3.2006, 22:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Ёжик
***


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

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


--------------------
Пользуйтесь ссылкой <<решенный\нерешенный вопрос>>
IRC-канал Винграда
PM MAIL ICQ   Вверх
cardinal
Дата 22.3.2006, 22:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


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

Репутация: 15
Всего: 99
Может надо пройтись по списку, вставить значения в массив, а потом уже сортировать? smile
Добавлено @ 22:42
А потом уже новый список лепить...


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

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
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;
}
PM MAIL   Вверх
sergejzr
Дата 22.3.2006, 22:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


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

Репутация: 11
Всего: 360
короче говоря, как видим-массив.


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1991 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.