VPF::Разреженные массивы: помогите исправить ошибки

Aline

Дата 5.6.2013, 15:05 (ссылка)

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

Загрузка ...

Опытный

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

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

Необходимо реализовать разреженный массив. На просторах инета нашла пример, как это можно сделать http://www.galaxy797.net/c/shildt/23/2302.htm . Структура данных у меня можно сказать такая же как и в пример: поле ID - массив из 9 байтов ( значения 3-х индексов будут передоваться: 1-й индекс это 1-4 байт, 2-й индекс 5-8 байт и 3-й индекс - это 9-й байт), поле данных в виде массива из 120 байт, ну и ссылка на следующий элемент списка.

Перенесла всё это себе в проект. И тут посыпались ошибки :( Вернее 2 процедуры пока нормально перенеслись, но я к ним еще не обращалась из программы:

Код


struct afdx *start = NULL; /*первый элемент списка*/
struct afdx *last = NULL;  /*последний элемент списка*/

//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void TForm1::insert_data(struct afdx *i, struct afdx **start, struct afdx **last) //вставка данных в упорядоченный список
{
  struct afdx *old, *p;

  if (!*last) {
      i->next = NULL;
      i->prior = NULL;
      *last = i;
      *start = i;
      return;
  }
  p = *start;

  old = NULL;

  while (p){
    if (p->ID == i->ID){        //
        old = p;
        p = p->next;
    }
    else {
        if (p->prior) {
            p->prior->next = i;
            i->next = p;
            i->prior = p->prior;
            p->prior = i;
            return;
        }
        i->next = p;
        i->prior = NULL;
        p->prior = i;
        *start = i;
        return;
    }
  }
  old->next = i;
  i->next = NULL;
  i->prior = old;
  *last = i;
  return;
}

//---------------------------------------------------------------------------

void TForm1::delete_data(unsigned char *ID, struct afdx **start, struct afdx **last) //удаление данных из списка
{
  struct afdx *info;
  info = find_data(ID,*start);
  if (info) {
      if (*start == info) {
          *start = info->next;
          if (*start) (*start)->prior = NULL;
          else *last = NULL;
      }
  }
  else {
      if (info->prior) info->prior->next = info->next;
      if (info != *last) info->next->prior = info->prior;
      else *last = info->prior;
  }
  free (info);
}

В процедуре insert_data есть сомнения,что правильно написана строка if (p->ID == i->ID), наверное надо сравнивать по каждому элементу,раз это массив

А вот в этой функции сразу выскочили ошибки, она вызывается из процедуры delete_data

Код


struct afdx  TForm1::*find_data(unsigned char *ID, struct afdx *start) //поиск данных
{
    struct afdx *info;
    info = start;
    while (info){
      if (ID == info->ID) return info;
      info = info->next;
    }

    MessageDlg("Данные с таким индексом не найдены!",mtInformation, TMsgDlgButtons() << mbOK,0);
    return NULL;
}

А вот объявление класса:

Код


class TForm1 : public TForm
{
__published:    // IDE-managed Components
    TButton *btnInsert;
    TButton *btnDelete;
    TButton *btnFind;
    TEdit *edtIndex;
    TMemo *mOutput;
    TLabel *Label1;
    TLabel *Label2;
    TEdit *edtData;
private:    // User declarations
    struct afdx{
        unsigned char ID[9];        /* индексы: 4 байта 1-й индекс, 4 байта 2-й индекс и 1 байт 3-й индекс*/
        unsigned char Data[120];    /*данные*/
        struct afdx *next;          /*указатель  на следующую запись*/
        struct afdx *prior;         /*указатель на предыдущую запись*/
    };
public:        // User declarations
    __fastcall TForm1(TComponent* Owner);

    void insert_data(struct afdx *i, struct afdx **start, struct afdx **last); //вставка данных в упорядоченный список
    void delete_data(unsigned char *ID, struct afdx **start, struct afdx **last); //удаление данных из списка
    struct afdx  *find_data(unsigned char *ID, struct afdx *start); //поиск данных
};

В общем,я запуталась и очень прошу вашей помощи...
В приложении исходник и header

Это сообщение отредактировал(а) Aline - 5.6.2013, 15:05

Присоединённый файл ( Кол-во скачиваний: 2 )

Projects.rar 1,49 Kb

Guinness

Дата 5.6.2013, 15:42 (ссылка)

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

Загрузка ...

Опытный

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

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

Я так понимаю Вам по ближе к Си нужно. Я бы ID сделал структурой, по типу этого:

Код


typedef unsigned char BYTE;

typedef struct ID_{
   BYTE index1[3];
   BYTE index2[3];
   BYTE index3;
} ID;

К ней допишите необходимые функции.
Далее по afdx:

Код


struct afdx{
   ID id;
   BYTE data[120];    /*данные*/
};

Data - лучше сделать std::vector<BYTE>. Если, конечно, нет острой необходимости в контейнере Си.
Указатели лучше уберем. Вместо этого лучше использовать std::list<afdx> или другой, подходящий Вам контейнер.
Так вот, если это все дело мы храним в контейнерах, то написание всяких "чудо-функций" нам не особо и нужно. Достаточно посмотреть algorithms. Надеюсь, там Вы найдете большинство аналогов того, что Вы хотите сделать.

Это сообщение отредактировал(а) Guinness - 5.6.2013, 15:45

Aline

Дата 5.6.2013, 15:46 (ссылка)

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

Загрузка ...

Опытный

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

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

Guinness, спасибо! Гляну. Где то видела примеры с вектором, встречались. Просто я с этим ни разу не сталкивалась, новое для меня. Необходимо реализовать разреженный массив данных, тэо было самое простое и первое,что я нашла smile

Добавлено через 3 минуты и 30 секунд
Guinness, а как Вам это?
http://cppbuilder.ru/articles/0038.php
Мне кажется это понятнее, хотя бы потому,что описание на русском:)

Добавлено через 6 минут и 3 секунды
Guinness, что я посмотрела и вообще ничего не поняла :( с указателями мне как то понятней

Guinness

Дата 5.6.2013, 15:57 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Aline @ 5.6.2013, 16:46

)

что я посмотрела и вообще ничего не поняла :( с указателями мне как то понятней

А что не понятно? Лучше понять, а то есть немалый шанс понапридумывать велосипедов.

ЗЫ пример взят из данной книжки? ссылка
ЗЗЫ а зачем Вам вообще разреженный массив?

Это сообщение отредактировал(а) Guinness - 5.6.2013, 16:01

volatile

Дата 5.6.2013, 18:20 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

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

std::map - практически готовый разряженный массив.

Aline

Дата 6.6.2013, 07:59 (ссылка)

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

Загрузка ...

Опытный

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

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

Guinness, да, ссылка из того учебника
Массив нужен для тго,чтобы память экономит и данные будут разбросаны (ну по крайней мере я так поняла smile

)

volatile, спасибо, посмотрю

Aline

Дата 6.6.2013, 10:16 (ссылка)

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

Загрузка ...

Опытный

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

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

volatile, А Вы могли бы привести пример для моего случая?

Я с помощью typedef определила :

Код


typedef byte Key_type[9];
typedef byte Data_type[1500];

Как оказалось данных всё таки 1500 байт приходит.
Далее объявила:

Код


Key_type key;
Data_type data;

map< Key_type, Data_type > afdx_map;

Затем заполнила массивы key и data данными. И пытаюсь их связать:

Код


 afdx_map[ key ] = data;

Здесь выдает ошибку. Что неправильно и как сделать правильно? Или надо vector использовать для key и data?

xvr

Дата 6.6.2013, 10:27 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Цитата(Aline @ 6.6.2013, 10:16

)

Здесь выдает ошибку. Что неправильно и как сделать правильно?

У Key_Type должен быть определен оператор сравнения. Как то так:

Код


struct KeyType {
 byte key[9];

 bool operator < (const KeyType& op2) const {return memcmp(key,op2.key,sizeof(key))<0;}
};

Aline

Дата 6.6.2013, 10:29 (ссылка)

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

Загрузка ...

Опытный

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

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

xvr, чем дальше в лес, тем больше дров... smile

и как этим пользоваться в дальнейшем?

xvr

Дата 6.6.2013, 10:39 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Цитата(Aline @ 6.6.2013, 10:29

)

и как этим пользоваться в дальнейшем?

Так же, как и вашим оригинальным typedef'ом:

Код


Key_type key;
Data_type data;
map< Key_type, Data_type > afdx_map;

afdx_map[ key ] = data;

Или вы о заполнении key? Тут тоже все просто -

Код


memcpy(key.key,<тут ваш ключ>,9)

Если из массива, то так же, как и ваш typedef (плюс лишние скобочки) -

Код


Key_Type keys[]={
{{0,1,2,3,4,5,6,7,8}},
{{2,3,4,5,6,7,8,9,0}},
...
};

Aline

Дата 6.6.2013, 10:45 (ссылка)

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

Загрузка ...

Опытный

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

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

xvr, сейчас попробую,но что то для меня это темный лес совершенно :(

А структуру только для key надо делать?

Добавлено @ 10:50
При написании этого:

Цитата(xvr @ 6.6.2013, 10:27

)

struct KeyType { byte key[9]; bool operator < (const KeyType& op2) const {return memcmp(key,op2.key,sizeof(key))<0;}};

а затем этого:

Цитата(xvr @ 6.6.2013, 10:39

)

Key_type key;Data_type data;map< Key_type, Data_type > afdx_map;

компилятор выдал 44 ошибки...

Это сообщение отредактировал(а) Aline - 6.6.2013, 10:50

xvr

Дата 6.6.2013, 10:52 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Цитата(Aline @ 6.6.2013, 10:45

)

А структуру только для key надо делать?

Да

Цитата(Aline @ 6.6.2013, 10:45

)

компилятор выдал 44 ошибки...

Давайте ошибки, я же не телепат smile

volatile

Дата 6.6.2013, 10:59 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

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

Цитата(Aline @ 6.6.2013, 10:16

)

typedef byte Key_type[9];
typedef byte Data_type[1500];

Aline, простые массивы в С/С++ - это такие не очень полноценные типы.
их невозможно копировать, сравнивать и т.д. (операторами =, <), а это необходимо для мапа
Лучше использовать вектор, вместо них.
typedef std::vector <byte> Key_type;

Либо, если размер фиксирован, можно обернуть в структуру, в последнем случае нужно будет написать еще оператор<
Вот простейший пример:

Код


struct Key_type {
   BYTE data [9]; // наши данные

   bool operator < (const key_t & r) const
   {  return 0 < memcmp (data, r.data, sizeof data);
   }
};

Добавлено через 1 минуту и 42 секунды
упс.., несколько последних сообщений не видел.

Aline

Дата 6.6.2013, 12:21 (ссылка)

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

Загрузка ...

Опытный

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

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

xvr

вот к примеру: [bcc32 Error] xtree(36): E2450 Undefined structure 'pair<const Key_type,unsigned char[1500]>'
Full parser context

Это сообщение отредактировал(а) Aline - 6.6.2013, 12:22

volatile

Дата 6.6.2013, 13:05 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

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

Цитата(xvr @ 6.6.2013, 10:27

)

struct KeyType

Цитата(xvr @ 6.6.2013, 10:39

)

Key_type

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

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