Лучшая структура данных в C для этих двух ситуаций? - PullRequest
Новая
       39

Лучшая структура данных в C для этих двух ситуаций?

1 голос
/ 22 марта 2009

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

Мне нужно сделать 2 вещи, вероятно, они будут использовать разные структуры данных.

  1. Мне нужна структура данных для хранения записей профиля. Профили должны быть в состоянии искать по имени и номеру социального страхования. SSN уникален, поэтому я могу использовать его для своего преимущества? Я полагаю, хеш-карты - лучший выбор здесь? Но как мне использовать SSN в хэш-карте, чтобы использовать это в качестве преимущества при поиске определенного профиля? Очень хотелось бы получить простое и понятное объяснение.

  2. Мне нужна структура данных для хранения записей о городах. Мне нужно знать, какие города имеют наибольшее количество посетителей, меньше посещаемых городов и клиентов (профиль извлекается из структуры данных в # 1 для данных о клиентах) , которые посещают определенный город .

Это третья структура данных, которая мне нужна для моего проекта, и именно эту структуру данных я не знаю, с чего начать. Предположения относительно того, какой тип структуры данных следует использовать, по возможности, приводятся с примерами того, как старым данные выше выделены жирным шрифтом.

Как примечание:
Первая структура данных уже сделана (я говорил об этом в на предыдущем вопросе ). Второй размещен здесь, на # 1, и хотя другие члены группы позаботятся об этом, мне просто нужно знать, является ли то, что мы пытаемся сделать, «лучшим» подходом. Третий - № 2, тот, который мне больше всего нужен.

Ответы [ 3 ]

3 голосов
/ 22 марта 2009

Ответ вправо находится где угодно между сбалансированным деревом поиска и массивом.

Ситуация, которую вы упомянули здесь, и else-thread упускает из виду очень важный момент: размер обрабатываемых вами данных. Вы выбираете свою структуру данных и алгоритм (ы) в зависимости от объема данных, которые вы должны обработать. Важно, чтобы вы могли обосновать свой выбор (ы). Использование менее эффективного общего алгоритма не всегда плохо . Возможность резервного копирования вашего выбора (например, выбор пузырьковой сортировки, так как размер данных <10 всегда) показывает а) большую власть в поле и б) прагматизм - оба из которых в дефиците.

1 голос
/ 22 марта 2009

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

Первое, что вам нужно выяснить, как уже указывали другие out, сколько данных вы обрабатываете. O ( n ) перебор достаточно быстро, пока n мало. Поскольку тривиальное количество данных будет сделать это тривиальной задачей (положить в массив, и просто перебор поиск), я предполагаю, что объем данных велик.

Хранение городов

Во-первых, ваши требования к поиску требуют данных, отсортированных в несколько способов:

  1. Какой-то уникальный идентификатор города (имя?)
  2. Количество посетителей

Это на самом деле не так уж сложно удовлетворить. (1) проще всего. Хранить города в каком-то массиве. Индекс массива становится уникальным идентификатором (предположение: мы не удаляем города или, если мы удаляем города, мы можем просто оставьте эту точку массива неиспользованной, тратя впустую немного памяти. Добавление в порядке).

Теперь нам также нужно найти наибольшее и меньшее количество посещений. Если предположить, могут произойти изменения (например, добавление городов, изменение количества посетители и т. д.) и заимствования из реляционных баз данных, я бы предложил Создание индекса с использованием некоторой формы сбалансированного дерева. Базы данных будут обычно используют B-дерево, но для вас могут подойти разные: check Википедия статья на деревьях . В каждом узле дерева я просто держу указатель (или индекс массива) данных города. Нет причин делать еще одну копию!

Я рекомендую дерево над хешем по одной простой причине: вы можете очень легко сделать предварительный заказ или обратный порядок обхода, чтобы найти вершину или нижние N предметов. Хэш не может этого сделать.

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

Связывание городов с профилями

Как это сделать, зависит от того, как вы должны запрашивать данные, и какой формы это может занять. Наиболее общим является то, что каждый профиль может быть связан с несколькими городами, и каждый город может быть связан с несколькими профили. Кроме того, мы хотим иметь возможность эффективно запрашивать Направление - спросите обоих "кто посещает Феникс?" и "какие города делает Боб посетить?».

Снова бесстыдно поднимаясь из баз данных, я бы создал другие данные структура, довольно простая по направлениям: 

struct profile_city {
    /* btree pointers here */
    size_t profile_idx; /* or use a pointer */
    size_t city_idx;    /* for both indices */
};

Итак, если сказать, что Боб (профиль 4) посетил Феникс (город 2), вы бы profile_idx = 4 и city_idx = 2. Сказать, что Боб посетил Вегас (город 1) Кроме того, вы бы добавили еще один, чтобы у вас было два из них для Боба.

Теперь у вас есть выбор: вы можете хранить их либо в дереве, либо хэш. Лично я бы пошел с деревом, так как этот код уже написано. Но хеш будет для O ( n ) вместо O (log n ) для поиска.

Кроме того, как мы сделали для подсчета посещений города, создайте индекс для city_idx так что поиск можно выполнить и с этой стороны.

Заключение

Теперь у вас есть возможность посмотреть 5 самых посещаемых городов (через просмотрите индекс посещений города) и выясните, кто посещает эти по городам в поиске для каждого города в индексе city_idx, чтобы получить profile_idx. Хватайте только уникальные предметы, и у вас есть ответ.

О, и здесь что-то не так: кажется, что ваш инструктор хочет написать много кода за несколько часов!

1 голос
/ 22 марта 2009

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

Это может быть так же просто, как сохранить данные в массиве (или связанном списке, или ...) в порядке их создания, и сохранить кучу {hashtables | отсортированных массивов | btrees} карт (key, data*) для все интересные ключи (SSN, имя, ...).

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

Я думаю, что это решение, вероятно, относится к обеим вашим проблемам.

Удачи.

Для ясности:

Сначала у нас есть простой массив студенческих записей 

typedef
struct student_s {
   char ssn[10]; // nul terminated so we can use str* functions 
   char name[100];
   float GPA;
   ...
} student;
student slist[MAX_STUDENTS];

который заполняется по мере поступления. У него нет порядка, поэтому поиск по клавише любой является линейной временной операцией. Не проблема для 1000 записей, но, возможно, проблема для 10000, и, конечно, проблема для 1 миллиона. См. комментарии dirkgently .

Если мы хотим иметь возможность быстрого поиска, нам нужен еще один слой структуры. Я строю карту между ключом и основной структурой данных следующим образом: 

typedef
struct str_map {
   char* key;
   student *data;
} smap;
smap skey[MAX_STUDENTS]

и поддерживайте skey отсортированными на ключе, чтобы я мог быстро выполнять поиск. (Только массив мешает сохранять отсортированным, поэтому мы, вероятно, предпочитаем дерево или hashmap.)

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

...