Сортировка и поиск в массиве структур

[cooler_3105]

У нас есть инцилизированный массив структур типа:

Код:

struct city
	{
	char name[15];
	int people;
	int S;
	int year;
	int school;
	} list [20];

Мы спрашиваем у пользователя по какому полю мы будем проводить поиск (т.е. мы будем искать название города (name), кол-во населения (people), площадь города (S), год основания (year) или кол-во школ (school)). На основании результата мы проводим сортировку (вот тут я не знаю как делать: мы не должны изменять массив структур, но
1. должны упорядочить поле по которому ищем,
2. провести поиск делением пополам и найти данные или вывести сообщение, что таковых не найдено
3. если данные найдены, то надо узнать где они лежат в исходной структуре (номер элемента массива (структуры))

Я написал функцию сортировки названий городов:

Код:

void qs_string(char items[][20], int left, int right
/*items - массив названий городов, left задаем 0, right - кол-во городов-1*/
{
  int i=left, j=right;
  char temp[20], *x;
  x = items[(left+right)/2];
  do {
    while((strcmp(items[i],x) < 0) && (i < right)) i++;
    while((strcmp(items[j],x) > 0) && (j > left)) j--;
    if(i <= j) {
      strcpy(temp, items[i]);
      strcpy(items[i], items[j]);
      strcpy(items[j], temp);
      i++; j--;
   }
  } while(i <= j);
  if(left < j) qs_string(items, left, j);
  if(i < right) qs_string(items, i, right);
}

но как не изменяя структуры произвести оптимизационный поиск

[Алексей++]

cooler_3105, я ж поставил теги, зачем убираешь ? )) Погоди, не правь пост

[cooler_3105]

cooler_3105, я ж поставил теги, зачем убираешь ? )) Погоди, не правь пост

Извини, я редактировал смысл поста Пытался донести, что я хочу сделать...

[Алексей++]

я бы переписал код так (пока ничего не меняя)

Код:

void qs_string(char items[][20], int number)
//items - массив названий городов, number кол-во городов
{
  int i=0;
  int j=number-1;
  char temp[20];
  char* x;
  x = items[number/2]; // +++++++++ тут уже одна ошибка ушла сама собой
  do
  {
    while((strcmp(items[i],x) < 0) && (i < number-1))
    {
      i++;
    }

    while((strcmp(items[j],x) > 0) && (j > 0))
    {
      j++;
    }

    if(i <= j)
    {
      strcpy(temp, items[i]); // ++++++ а ты уверен, что тут строки оканчиваются нулевым символом ?
      strcpy(items[i], items[j]);
      strcpy(items[j], temp);
      i++;
      j--;
    }
  }while(i <= j);

  if(0< j) qs_string(items, 0, j);
  if(i < number-1) qs_string(items, i, number-1);
}

[Алексей++]

теперь, поясни, зачем

Код:

char items[][20] 
 items - массив названий городов, number кол-во городов

и как это связано со структурой city ?

может удобнее передать

Код:

qs_string(city* Array, int number)

и зачем сюда вкралась рекурсия, когда можно и без неё, в принципе

[cooler_3105]

теперь, поясни, зачем

Код:

char items[][20] 
 items - массив названий городов, number кол-во городов

и как это связано со структурой city ?

может удобнее передать

Код:

qs_string(city* Array, int number)

и зачем сюда вкралась рекурсия, когда можно и без неё, в принципе

Я не знаю как сортировку увязать со структурой. Исходная структура не должна сортироваться. Может надо делать  и сортировать доп. структуру с полями city (само название) и number (номер этого города в исходной структуре).
Я сделал только с рекурсией. Штука в том, что хоть сортировка и работает, но мы теряем связь со структурой, т.е. после поиска в отсортированном списке и найдя что-то, мы уже не знаем где это что-то находится в массиве структур.

[Алексей++]

так связи то и нету )

Код:

//пузырьковый метод. Он не эффективный, поэтому напишешь лучше :) 
qs_string(city* Array, int number)
{
   city tempCity;

   for(int i=0;i+1<number;i++)
   {
      if(is_true_order(Array[i].name,Array[i+1].name))continue;

      //меняем местами
      tempCity=Array[i];
      Array[i]=Array[i+1];
      Array[i+1]=tempCity;

      if(i)i--;
   }
}

bool is_true_order(const char* str1, const char* str2)
{
   //если строка str1 должна находится перед str2, вертаем true

   //иначе - вертаем false
}

вот, не тестировал, правда, но типа этого должно выйти

[Алексей++]

и вроде бы строки умеет сравнивать
int strcmp(
   const char *string1,
   const char *string2
);

Return Value
The return value for each of these functions indicates the lexicographic relation of string1 to string2.

Value Relationship of string1 to string2
< 0 string1 less than string2
0 string1 identical to string2
> 0 string1 greater than string2


а _stricmp - сравнение без учёта регистра

[Антон (LogRus)]

Значится так эх чето меня прёт сегодня.

я бы просто построил индексы по массиву, искал бы в индексах
вот пример с использованием stl переделать под обычные массивы не составит труда, я думаю.

Код:

struct city
{
	std::string name;
	int people;
	int S;
	int year;
	int school;
};

typedef std::vector<city> CityVec;
typedef CityVec::iterator CityVecIter;
typedef std::vector<CityVec::iterator> CityIndex; // эту штуку лудше заменить на multimap
typedef CityIndex::iterator CityIndexIter;

// такой вот предикат для сортировки и поиска по полю name
bool CityNameLess(const CityVecIter lhs, const CityVecIter rhs) 
{
	return lhs->name < rhs->name;
}

int _tmain(int argc, _TCHAR* argv[])
{
	CityVec vcity;
	vcity.resize(20); // вроде как массив структур
	vcity[0].name = "Z";
	vcity[1].name = "F";
	vcity[2].name = "Moscow";
	vcity[3].name = "J";
	vcity[4].name = "A";
	vcity[12].name = "Moscow";
	vcity[13].name = "Z";
	vcity[14].name = "K";
	vcity[15].name = "Moscow"; // проинициализировали

	CityIndex vindex;
	vindex.reserve(vcity.size()); // чтобы небыло реалокаций
	for (CityVecIter it = vcity.begin(); it != vcity.end(); ++it) // заполнили индекс
		vindex.push_back(it);

	std::sort(vindex.begin(),vindex.end(),CityNameLess); // отсортируем индекс, именно индекс
	// поищем чтоли чего-нибуть

	//вынужден создать вектор с одним элементом, т.к. предикат работает с итераторами
	CityVec tmp;
	tmp.push_back(city());
	tmp.front().name = "Moscow";

	std::pair<CityIndexIter, CityIndexIter> range;
	// теперь делаем поиск
	range = std::equal_range(vindex.begin(),vindex.end(),tmp.begin(),CityNameLess);
	for (CityIndexIter it = range.first; it != range.second; ++it)
	{
		city & c = **it;
		std::cout << "City name = " << c.name << "\n";
	}

	return 0;
}

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

у кода есть несколько минусов(для примера и так сойдёт)
1. При добавлении нового элемента может быть реалокация вектора, что приведут к инвалидации итераторов(укателей) в индексе
2. При добавлении элемента в массив нужно перестраивать индекс

Цель примера показать работу с индексами.

[Алексей++]

щас у парня от твоих шаблонов башню как заклинит ) А ему ведь преподу ещё объяснять

[cooler_3105]

LogRus, да, я немного, что понял С сортировкой я разобрался. Остался только один вопрос: поиск (по полю name) в этом сортированном массиве структур:

Код:

struct search_name
	{
		char name [15];
		int number;
} p[20];

Т.е. вот есть массив структур. Нужно найти полностью совпадающую строку (или символ), который ввел пользователь. Никак не пойму как организовать поиск половинного деления

[Алексей++]

например, имеется массив Array из N строк, отсортированных по возрастанию, то

Код:

int beg=0;
int end=N-1;
int currCenter=0;

int nFound=-1;//ещё ничего не найдено (== -1)
for(;;)
{
	//смотрим середину интервала beg...end
	currCenter=beg+(end-beg+1)/2;
	if(currIndx>=end)currIndx=end;

	if( Array[currCenter] "равно" искомому)
	{
		//нашли одну из строк.
		//возможно, ранее есть ещё такие же строки,
		//стоящие рядом (так как отсортировано)
		//Если нужно - двигаемся по единичке вверх и ищем самую первую строку
		
		//поиск окончен
		nFound=currCenter;
		break;
	}
	else
	if( Array[currCenter] "больше" чем искомое)
	{
		end=currCenter;
	}
	else
	{
		beg=currCenter;
	}

	if(end<=beg)break;
}

if(nFound==-1)
{
	 //не найдено
}
else
{
	//найдено, индекс == nFound
}

что то навроде такого

[cooler_3105]

Алексей1153++, я вот сделал программку, но она почему-то не обрабатывает первый и последний элемент

Код:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stdafx.h"
#define N 7
char Array [][N]={"один", "два", "три", "четыре", "пять"};
char key[]="один";
int main(int argc, char* argv[])
{
int beg=0;
int end=N-1;
int currCenter=0;
int nFound=-1;//ещё ничего не найдено (== -1)

for(;;)
{
	currCenter=beg+(end-beg+1)/2;
	if((strncmp(Array[currCenter],key,strlen(key)))==0)
	{
		nFound=currCenter;
		break;
	}
	else
	if((strncmp(Array[currCenter],key,strlen(key)))>0)
		end=currCenter-1;
	else
		beg=currCenter;
	if(end<=beg)break;
}
if(nFound==-1)
	printf ("Not found");//не найдено
else
	printf ("%d", nFound+1);//найдено, индекс == nFound

	return 0;
}

З.ы. Сории, массив не упорядочил

[Алексей++]

а условие сортировки выполнено ?

Код:

char Array [][N]={"один", "два", "три", "четыре", "пять"};

-отсюда видно, что нет ) И в программе нету сортировки.

а ещё, зачем

char Array [][N]

, а не просто

char Array [N]

?

[Алексей++]

а вот я накосячил, а ты просто строку то выкинул ))

if(currIndx>=end)currIndx=end;

надо
if(currCenter>=end)currCenter=end;

И не бойся ты фигурные скобки блока ставить, красивше же и надёжнее, то есть вместо

Код:

else
	if((strncmp(Array[currCenter],key,strlen(key)))>0)
		end=currCenter-1;
	else
		beg=currCenter;
	if(end<=beg)break;

делай

Код:

else
{
	if((strncmp(Array[currCenter],key,strlen(key)))>0)
	{
		end=currCenter-1;
	}
	else
	{
		beg=currCenter;
	}
	if(end<=beg)break;
}

[cooler_3105]

а условие сортировки выполнено ?

Код:

char Array [][N]={"один", "два", "три", "четыре", "пять"};

-отсюда видно, что нет ) И в программе нету сортировки.

а ещё, зачем

char Array [][N]

, а не просто

char Array [N]

?

у нас двумерный массив символов, т.к. строка является массивом символов. А с условием сортировки работает так же, как и без нее...

Код:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stdafx.h"
#define N 7
char Array [][N]={"äâà","îäèí", "ïÿòü", "òðè", "÷åòûðå"};
char key[]="äâà";
int main(int argc, char* argv[])
{
int beg=0;
int end=N-1;
int currCenter=0;
int nFound=-1;//åù¸ íè÷åãî íå íàéäåíî (== -1)

for(;;)
{
	currCenter=beg+(end-beg+1)/2;
	if(currCenter>=end)currCenter=end;
	if((strncmp(Array[currCenter],key,strlen(key)))==0)
	{
		nFound=currCenter;
		break;
	}
	else
	if((strncmp(Array[currCenter],key,strlen(key)))>0)
		end=currCenter;
	else
		beg=currCenter;
	if(end<=beg)break;
}
if(nFound==-1)
	printf ("Not found");//íå íàéäåíî
else
	printf ("%d", nFound+1);//íàéäåíî, èíäåêñ == nFound

	return 0;
}

[Алексей++]

нужно взять отладчик и по шагам пройтись - в момент ошибка найдётся. я просто же не тестировал код. Прогони в отладчике

[Антон (LogRus)]

щас у парня от твоих шаблонов башню, как заклинит ) А ему ведь преподу ещё объяснять

Ладно завтра переделают под указателе и обычные массивы, если лень не будет.

[cooler_3105]

С этим вопросом разобрался Большое спасибо Алексей1153++.

[Алексей++]

cooler_3105, где косяк был ?

[cooler_3105]

мы объявляем массив как char Array [][N] (двумерный), а обращаемся к его элементам, как к одномерному массиву - Array[currCenter]. Сначала я попробовал сделать через приведенный индекс, а потом переделал под структуры, как мне надо было. И заработало

[Алексей++]

так я вроде сразу тебе сказал про это )

[Джон]

Короткое замечание, так на всякий случай: в С++ нет двумерных массивов.

[Алексей++]

Джон, ну если так подходить - то их нигде нету, одни 1-мерные )))

[Джон]

Лёш, знать этого - мало, надо ещё это понимать.

[cooler_3105]

Короткое замечание, так на всякий случай: в С++ нет двумерных массивов.

А кто сказал, что я в С++ делаю? Я на С пишу.

[Джон]

cooler_3105,  а в С уж и подавно.

[cooler_3105]

Джон, почему нет? есть... Мы ведь можем в Си создать массив A[1][2][3], другое дело что к его элементам можно получить доступ через приведенный индекс, и в памяти он располагается как одномерный... Если не прав, прошу меня поправить