IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> Сортировка записей, Си++
Unknown
сообщение 12.12.2006 10:58
Сообщение #1


Гость






В общем, вот само задание:
Написать и протестировать функции сортировки записей и поиска их по ключам для следующих методов: линейный выбор с обменом, бинарный поиск.
Запись имеет три поля, например, фамилия, имя, номер телефона. Иметь не менее 30 записей. Поиск - по любому ключу, задаваемому из меню.

Вот то, что я сделал:

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

class qwe
{
public:
	char name[20];
	char sirname[20];
	char phone[7];
};

int main()
{
clrscr();
randomize;
int k;
qwe base[30];
for(int i=1;i<=30;i++)
	{
	for (k=1;k<random(10)+5;k++)
		{
		base[i].name[k]=char(random(25)+65);
		base[i].sirname[k]=char(random(25)+65);
		}
	for (k=1;k<8;k++)
		base[i].phone[k]=random(9);
	}
getch();
}


Этот кусок программы должен заполнять базу данных: имя, фамилию и телефон. Имя и фамилия - случайный набор букв (заглавных латинских), телефон - случайная последовательность из 7 цифр. Где здесь ошибка?

Допустим, есть у меня эта база, а что дальше делать?
 К началу страницы 
+ Ответить 
volvo
сообщение 12.12.2006 12:33
Сообщение #2


Гость






Во-первых, если ты уже написал, что это С++, и пользуешься классами, то почему бы тебе не воспользоваться и конструкторами, чтобы не делать генерацию вручную, а она проводилась бы автоматически?

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

const int size = 20;
class qwe
{
public:
    char name[size];
    char sirname[size];
    char phone[8];

    qwe();
};

qwe :: qwe() {

  int k;

  for(k = 0; k < random(10) + 5; k++)
    name[k] = char(random(25)+65);
  name[k] = '\0';

  for(k = 0; k < random(10) + 5; k++)
    sirname[k] = char(random(25)+65);
  sirname[k] = '\0';

  for(k = 0; k < 7; k++)
    phone[k] = char(random(10) + '0');
  phone[7] = '\0';

}

int main() {

  clrscr();
  randomize;

  qwe base[30];
  for(int i = 0; i < 30; i++)
    cout << base[i].name << " , " <<
            base[i].sirname << " : " <<
            base[i].phone << endl;

  getch();
  return 0;

}
Вот так, например...

Цитата
а что дальше делать?
А теперь пиши процедуры сортировки, которые тебе нужны (в Паскалевском FAQ-е есть эти методы: Методы сортировок + Бинарный (двоичный) поиск ), также есть описание способа как из меню выбрать поле для сортировки по нему: Сортировка записи с процедурой

Посмотри, как это делается...
 К началу страницы 
+ Ответить 
Unknown
сообщение 12.12.2006 22:09
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 104
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Хмм, чего-то я не пойму... Линейная сортировка (она же пузырьковая) - это упорядочение всех записей в базе по определенному условию - правильно? В порядке возрастания/убывания номеров и т.п., да? В задании написано - "Поиск - по любому ключу, задаваемому из меню." Т.е. фамилии/имена в алфавитном порядке, номера телефонов в порядке возрастания? или как?
С бинарным поиском - то же самое? Т.е. задали фамилию Иванов - ищем местоположение буквы "И", потом - "в" и т.п.?

Цитата
Во-первых, если ты уже написал, что это С++, и пользуешься классами, то почему бы тебе не воспользоваться и конструкторами, чтобы не делать генерацию вручную, а она проводилась бы автоматически?

Конструктор - это та функция qwe(), которая описана в классе qwe? А зачем ее описание вынесено за пределы описания класса? Или так обязательно делать? Сорри, за глупые вопросы...


--------------------
go ask Alice
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 12.12.2006 22:22
Сообщение #4


Гость






Цитата
С бинарным поиском - то же самое? Т.е. задали фамилию Иванов - ищем местоположение буквы "И", потом - "в" и т.п.?
Все гораздо проще... Если ты задал фамилию "Иванов", значит, сортируешь массив по фамилии, и ищешь бинарным поиском (ты прочел по ссылке, вообще, как это делается? Интервал поиска каждый раз уменьшается в 2 раза, благодаря чему поиск идет ГОРАЗДО быстрее, чем полный просмотр всего массива) эту фамилию ... То есть, алгоритм такой: меню - что будете искать (имя, фамилию или телефон)? Выбрал, скажем, "Фамилию" - программа тебя спрашивает: "А какую именно фамилию искать будем?" Ты вводишь, и она ищется...

Аналогично - по другим ключам...

Цитата
А зачем ее описание вынесено за пределы описания класса?
А нет смысла оставлять его внутри класса, подстановкой конструктор все равно не будет, так как в нем используются циклы, следовательно это будет обычный вызов функции - поэтому я вынес описание из класса, (1) чтобы не было предупреждения компилятора, и (2) чтобы было сразу видно, что ЭТО - не подстановка (не inline)...
 К началу страницы 
+ Ответить 
Unknown
сообщение 12.12.2006 22:49
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 104
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Я к тому, что если в базе есть фамилии Иванов и Иванченко - тогда как (записи же отсортированы в алфавитном порядке, да?)? Вот взяли мы 15-й элемент и посмотрели, а там - Лыков. Значит, до (л<и). Взяли 7 - Иванченко. Значит, до (т.к. и=и, в=в, а=а, н=н, о<ч).
Все правильно?

Цитата
Ты вводишь, и она ищется...


Сначала список сортируется методом пузырька, потом ищется нужный элемент, так?


--------------------
go ask Alice
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 12.12.2006 22:52
Сообщение #6


Гость






Да что тебя так тянет сравнивать ПОБУКВЕННО? Кто же это делает? strcmp для кого? Сравниваешь СТРОКУ со СТРОКОЙ... Переливать из пустого в порожнее заканчиваю. Я уже дал всю необходимую информацию... Теперь твоя очередь это реализовать (хотя бы начать)...
 К началу страницы 
+ Ответить 
Unknown
сообщение 13.12.2006 13:05
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 104
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Вот, что я сделал:
 #include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

const int size = 20;
class qwe
{
public:
    char name[size];
    char sirname[size];
    char phone[8];

    qwe();
};
qwe :: qwe() {
  int k;
  for(k=0; k<random(10)+5; k++)
    name[k]=char(random(25)+65);
  name[k]='\0';
  for(k=0; k<random(10)+5; k++)
    sirname[k]=char(random(25)+65);
  sirname[k]='\0';
  for(k=0; k<7; k++)
    phone[k]=char(random(10)+'0');
  phone[7]='\0';
}
qwe base[30];
char ch[size];

void bubblename ()
{
for (int i=0; i<30; i++)
    for (int j=0; j<30; j++)
	if (strcmp(base[j].name,base[j+1].name)>0)
	   {
	   ch=base[j].name;base[j].name=base[j+1].name;base[j+1].name=ch;
	   }
};

void bubblesirname ()
{
for (int i=0; i<30; i++)
    for (int j=0; j<30; j++)
	if (strcmp(base[j].sirname,base[j+1].sirname)>0)
	   {
	   ch=base[j].sirname;base[j].sirname=base[j+1].sirname;base[j+1].sirname=ch;
	   }
};

void bubblephone ()
{
for (int i=0; i<30; i++)
    for (int j=0; j<30; j++)
	if (strcmp(base[j].phone,base[j+1].phone)>0)
	   {
	   ch=base[j].phone;base[j].phone=base[j+1].phone;base[j+1].phone=ch;
	   }
};

int main()
{
  clrscr();
  randomize;
  for(int i=0; i<30; i++)
    cout << base[i].name << " , " <<
	    base[i].sirname << " : " <<
	    base[i].phone << endl;
  cout<<"\nBBeguTe napaMeTp (name - 1/sirname - 2/phone - 3): ";
  if (getch=='1') bubblename() else if (getch=='2') bubblesirname() else bubblephone();
  getch();
  return 0;
}

Пока только сортировка. Где ошибка?


--------------------
go ask Alice
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 13.12.2006 13:31
Сообщение #8


Гость






Цитата
Где ошибка?
Откомпилируй программу, увидишь... Что тебе здесь, компиляторы сидят? nea.gif

"Где ошибка"? Ладно бы спросил, "Как исправить, пробовал вот это и вот это - не получается..."
 К началу страницы 
+ Ответить 
Unknown
сообщение 13.12.2006 13:45
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 104
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Ошибка такая: Lvalue required на строке
ch=base[j].name;base[j].name=base[j+1].name;base[j+1].name=ch;

Это раз, и как ее исправить я не знаю....
А два - это то, что я упорядочивал только один параметр всех записей, при этом не трогая остальные... unsure.gif
Ща попробую исправить


--------------------
go ask Alice
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Unknown
сообщение 13.12.2006 16:41
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 104
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Уф, вроде все получилось:
 #include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

const int size = 20;
int n,left=0,right=29;
class qwe
{
public:
    char name[size];
    char sirname[size];
    char phone[8];

    qwe();
};
qwe :: qwe() {
  int k;
  for(k=0; k<random(10)+5; k++)
    name[k]=char(random(25)+65);
  name[k]='\0';
  for(k=0; k<random(10)+5; k++)
    sirname[k]=char(random(25)+65);
  sirname[k]='\0';
  for(k=0; k<7; k++)
    phone[k]=char(random(10)+'0');
  phone[7]='\0';
}
qwe base[31];

void sortname ()
{
for (int i=0; i<30; i++)
    for (int j=i; j<30; j++)
	if (strcmp(base[j].name,base[i].name)<0)
	   {base[30]=base[i];base[i]=base[j];base[j]=base[30];}
};

void sortsirname ()
{
for (int i=0; i<30; i++)
    for (int j=i; j<30; j++)
	if (strcmp(base[j].sirname,base[i].sirname)<0)
	   {base[30]=base[i];base[i]=base[j];base[j]=base[30];}
};

void sortphone ()
{
for (int i=0; i<30; i++)
    for (int j=i; j<30; j++)
	if (strcmp(base[j].phone,base[i].phone)<0)
	   {base[30]=base[i];base[i]=base[j];base[j]=base[30];}
};

void baseout()
{
  for(int i=0; i<30; i++)
  {
    cout.width(15);
    cout << base[i].name << ", ";
    cout.width(15);
    cout << base[i].sirname << " : ";
    cout << base[i].phone << endl;
  }
};

int main()
{
  clrscr();
  randomize;
  baseout();
  cout<<"\nWhat would you like to find? (name - 1/sirname - 2/phone - 3): ";
  char ch=getch();
  if (ch=='1')
	{
	sortname();clrscr();
	cout<<"base sorted by name:\n\n";baseout();
	cout<<"\nEnter the name: ";cin>>base[30].name;
	while ((right-left)>1)
	      {
	      n=(right+left+1)/2;
	      if (strcmp(base[30].name,base[n].name)>0)
		 left=n; else right=n;
	      }
	}

  else if (ch=='2')
	{
	sortsirname();clrscr();
	cout<<"base sorted by sirname:\n\n";baseout();
	cout<<"\nEnter the sirname: ";cin>>base[30].sirname;
	while ((right-left)>1)
	      {
	      n=(right+left)/2;
	      if (strcmp(base[30].sirname,base[n].sirname)>0)
		 left=n; else right=n;
	      }
	}
  else  {
	sortphone();clrscr();
	cout<<"base sorted by phone:\n\n";baseout();
	cout<<"\nEnter the phone: ";cin>>base[30].phone;
	while ((right-left)>0)
	      {
	      n=(right+left)/2;
	      if (strcmp(base[30].phone,base[n].phone)>0)
		 left=n; else right=n;
	      }
	}
  clrscr();
  cout << base[n].name << " , " <<
	    base[n].sirname << " : " <<
	    base[n].phone << endl;
  getch();
  return 0;
}

volvo, огромное спасибо за помощь!

Сообщение отредактировано: Unknown - 19.12.2006 21:10


--------------------
go ask Alice
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Unknown
сообщение 19.12.2006 21:09
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 104
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Все-таки ошибки имеют место быть... sad.gif
Во-первых, был выбран не тот метод сортировки (в вашем факе пузырьковая и линейная с обменом - одно и то же, а в методичке нашего препода - разные вещи...), но это я исправил (см. выше)
Во-вторых, если заданный элемент в бинарном поиске - первый, то программа ошибается... Может кто-нибудь помочь с этим?


--------------------
go ask Alice
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 26.07.2025 17:09
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"