VPF::как добавить памяти - Форум программистов

BSOD

Дата 9.2.2006, 16:55 (ссылка)

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

Загрузка ...

Опытный

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

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

Вобщем проблема такая:
я выделил слолько-нибудь памяти

Код


  p=(int *)malloc(x*sizeof(int));

теперь мне надо еще. Как добавить еще памяти?

ЗЫ
C тока начал учить, потому вопрос может быть и ламерский....

Это сообщение отредактировал(а) BSOD - 9.2.2006, 17:15

--------------------

как корабль назовешь - то на нем и напишешь

Ignat

Дата 9.2.2006, 16:59 (ссылка)

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

Загрузка ...

Флудератор

Профиль
Группа: Экс. модератор
Сообщений: 4030
Регистрация: 19.4.2004
Где: غيليندزيك مدينة

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

Код


p=(int *)realloc(p, x*sizeof(int));

--------------------

Теперь при чем :P

BSOD

Дата 9.2.2006, 17:10 (ссылка)

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

Загрузка ...

Опытный

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

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

сэнкс

--------------------

как корабль назовешь - то на нем и напишешь

BSOD

Дата 9.2.2006, 18:28 (ссылка)

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

Загрузка ...

Опытный

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

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

малость не работает....

Код


  ....
  kg=(int *)malloc(n+1*sizeof(int));
  for (int i=0;i<=n;i++)
  {
    g[i]=(int *)malloc(sizeof(int));
    p[i]=(int *)malloc(sizeof(int));
  };
  for (int i=1;i<=m;i++)
  {
    fscanf(in,"%d %d %d",&a,&b,&c);
    kg[a]++;
    kg[b]++;
    g[a]=(int *)realloc(g[a],sizeof(int));
    g[b]=(int *)realloc(g[b],sizeof(int));
    g[a][kg[a]]=b; p[a][kg[a]]=c;  // здесь вылетает access violation на первом же круге
    g[b][kg[b]]=a; p[b][kg[b]]=c;
  };
  ...

int *g[10000],*p[10000],*kg;

a=1 b=2 c=3

--------------------

как корабль назовешь - то на нем и напишешь

Ignat

Дата 9.2.2006, 18:43 (ссылка)

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

Загрузка ...

Флудератор

Профиль
Группа: Экс. модератор
Сообщений: 4030
Регистрация: 19.4.2004
Где: غيليندزيك مدينة

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

Я вот в эти две строчки вообще не въехал:

Цитата(BSOD @ 9.2.2006, 18:28

)

g[a][kg[a]]=b; p[a][kg[a]]=c; // здесь вылетает access violation на первом же круге
g[b][kg[b]]=a; p[b][kg[b]]=c;

Здесь вообще ничего не меняется (под *g[a] и так уже была выделена память объемом в sizeof(int) ):

Цитата(BSOD @ 9.2.2006, 18:28

)

g[a]=(int *)realloc(g[a],sizeof(int));
g[b]=(int *)realloc(g[b],sizeof(int));

--------------------

Теперь при чем :P

BSOD

Дата 9.2.2006, 19:08 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

Здесь вообще ничего не меняется (под *g[a] и так уже была выделена память объемом в sizeof(int) ):

Цитата(BSOD @ 9.2.2006, 18:28 )

g[a]=(int *)realloc(g[a],sizeof(int));
g[b]=(int *)realloc(g[b],sizeof(int));

дык а как именно добавить(!) еще один int?

Цитата

Я вот в эти две строчки вообще не въехал:

Цитата(BSOD @ 9.2.2006, 18:28 )

g[a][kg[a]]=b; p[a][kg[a]]=c; // здесь вылетает access violation на первом же круге
g[b][kg[b]]=a; p[b][kg[b]]=c;

впринципе их можно заменить на any_action();

--------------------

как корабль назовешь - то на нем и напишешь

Hroft

Дата 9.2.2006, 19:18 (ссылка)

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

Загрузка ...

Опытный

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

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

Нужно накапливать где-то размер компонент g[], чтобы писать в realloc вместо sizeof(int) этот размер.
А вообще - несравнимо удобнее vector, его для того и писали.

Ignat

Дата 9.2.2006, 19:33 (ссылка)

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

Загрузка ...

Флудератор

Профиль
Группа: Экс. модератор
Сообщений: 4030
Регистрация: 19.4.2004
Где: غيليندزيك مدينة

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

Цитата(BSOD @ 9.2.2006, 19:08

)

дык а как именно добавить(!) еще один int?

realloc используется для изменения памяти отведенного под тип данных. Т.е. как увеличения, так и уменьшения. Второй параметр определяет новый размер памяти, отведенный тип, в данном случае int. Это необходимо, если нужно, к примеру, строку char[32] удлиннить до char[64]. Но тип int имеет стандартную длину 32 бита, его можно привести к типам short и long.
А добавить можно инкрементировав индекс указателя.

Код



int * ptr_arr[];

ptr_arr[0]=(int *)malloc(sizeof(int));// выделили память
* ptr_arr[0]=1; //присвоили значение

ptr_arr[1]=(int *)malloc(sizeof(int));// выделили память еще под один int
* ptr_arr[1]=2; //присвоили значение новому int

Цитата(BSOD @ 9.2.2006, 19:08

)

впринципе их можно заменить на any_action();

А вот если будет any_action, то и ошибка будет другой, либо её не будет вообще. Т.к. ошибка именно в этих строках.

--------------------

Теперь при чем :P

BSOD

Дата 9.2.2006, 19:51 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Цитата

А вот если будет any_action, то и ошибка будет другой, либо её не будет вообще. Т.к. ошибка именно в этих строках.

ну any_action_with_p_or_g();

--------------------

как корабль назовешь - то на нем и напишешь

Hroft

Дата 9.2.2006, 20:00 (ссылка)

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

Загрузка ...

Опытный

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

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

А для эффективности их еще не по одному элементу желательно удлинять - снова std::vector.

BSOD

Дата 9.2.2006, 21:27 (ссылка)

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

Загрузка ...

Опытный

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

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

вектор это конечно хорошо, но т.к. я решаю олимпиадную задачу => <vector.h> подключать низя... =(
нуна все-таки думать самому....

--------------------

как корабль назовешь - то на нем и напишешь

Ignat

Дата 9.2.2006, 21:28 (ссылка)

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

Загрузка ...

Флудератор

Профиль
Группа: Экс. модератор
Сообщений: 4030
Регистрация: 19.4.2004
Где: غيليندزيك مدينة

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

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

--------------------

Теперь при чем :P

BSOD

Дата 9.2.2006, 21:39 (ссылка)

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

Загрузка ...

Опытный

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

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

все... разобрался... c realloc я все делал правильно... я как обычно забыл обнулить kg (не бейте меня сильно, я с паскаля пережжаю... там такое иногда прокатывает =) )

--------------------

как корабль назовешь - то на нем и напишешь

BSOD

Дата 9.2.2006, 23:35 (ссылка)

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

Загрузка ...

Опытный

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

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

Так... проблемы продолжаются...
с небольшими m,n,a,b,c.. прога работает на ура, а вот если m=9999 и n=10000
вылетает access violation, при чем не сразу..

Код


  for (int i=1;i<=m;i++)
  {
    fscanf(in,"%d %d %d",&a,&b,&c);
    if (a!=b)
    {
    kg[a]++;
    kg[b]++;
    g[a]=(int *)realloc(g[a],kg[a]*sizeof(int)); // вылетает тут, когда а=501 b=344 (на третьей итерации)
    g[b]=(int *)realloc(g[b],kg[b]*sizeof(int));
    g[a][kg[a]]=b; p[a][kg[a]]=c;
    g[b][kg[b]]=a; p[b][kg[b]]=c;
    };
  };

Немного поясню что это:
Вобщем я решаю задачу:
Есть граф с n вершинами и m ребрами, нужно найти кратчайший путь из одной вершины в другую. Оюычнай дейкстра не подходит (по времени) + если просто хранить граф в двумерном массиве (вершины смежные с текущей) - не влазит по памяти. Нужно написать дейкстру с кучей + "извратный" (динамический) массив. Дейкстру с кучей я написал а вот с "извратным" массивом - проблемы....
походу - учу C++ smile

Это сообщение отредактировал(а) BSOD - 9.2.2006, 23:35

--------------------

как корабль назовешь - то на нем и напишешь

Ignat

Дата 10.2.2006, 10:50 (ссылка)

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

Загрузка ...

Флудератор

Профиль
Группа: Экс. модератор
Сообщений: 4030
Регистрация: 19.4.2004
Где: غيليندزيك مدينة

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

Цитата(BSOD @ 9.2.2006, 23:35

)

учу C++

Только это C без ++ smile

В стиле C++ выделение памяти делается оператором new.

К вопросу об access violation: рекомендуется проверять выделилась ли память, примерно так:

Код


if( ptr=(int *)malloc(n*sizeof(int))){
    //что-то делаем
}else{
   printf(stderr, "недостаточно памяти для операции для n=%i", n); //не помню точный синтаксис
}

--------------------

Теперь при чем :P

BSOD

Дата 10.2.2006, 16:34 (ссылка)

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

Загрузка ...

Опытный

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

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

ну дык эт мона, тока памяти хватает... (еще метров 200 свободно, а надо 64)
и кастати, с new все точно также...
smile

--------------------

как корабль назовешь - то на нем и напишешь

BSOD

Дата 10.2.2006, 21:19 (ссылка)

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

Загрузка ...

Опытный

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

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

Походу возникает еще один вопрос:
а какой вобще может быть максимальный размер динамического (да и статического) массива (у меня почему-то 10000 на 10000 даже не компилится....) (памяти хватает, т.к. в делфи такой массив нормально создается и работает,а в С - нет ... )

--------------------

как корабль назовешь - то на нем и напишешь

Hroft

Дата 11.2.2006, 17:36 (ссылка)

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

Загрузка ...

Опытный

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

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

А какой компилятор? На каком-нибудь Borland C++ 3.0 если, то ее столько и нет.

BSOD

Дата 11.2.2006, 20:00 (ссылка)

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

Загрузка ...

Опытный

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

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

Builder 6.0

Тут вот на одном форуме сказали, что компилятор не может выделить больше 16 мб, но должны быть опции для выделения больше... какие?

--------------------

как корабль назовешь - то на нем и напишешь

Ignat

Дата 13.2.2006, 10:23 (ссылка)

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

Загрузка ...

Флудератор

Профиль
Группа: Экс. модератор
Сообщений: 4030
Регистрация: 19.4.2004
Где: غيليندزيك مدينة

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

Для MSVC есть ключик /Zm, а для билдера не знаю... Попробуй спросить bcc32 -h -

--------------------

Теперь при чем :P

BSOD

Дата 13.2.2006, 17:30 (ссылка)

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

Загрузка ...

Опытный

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

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

ничего похожего не нашел... и потом мне нужно, что бы типа как в паскале, ключик (типа {$M xxx xxx xxx}) прямо в коде...
мож я че с кодом напортачил....

выложу ка я листинг... может есть че-нить, бросающееся в глаза... (ч то си еще тока учу.. =) )

Код


#include <stdio.h>
#include <stdlib.h>

int n,m,*g[10001],*p[10001],*kg,*heap,*pos,*p1,*pred,a,b,c,hs;

int __fastcall left(const int a)
{
  return a*2;
};

int __fastcall right(const int a)
{
  return (a*2)+1;
};

int __fastcall parent(const int a)
{
  return a % 2;
};

void __fastcall swap(int const a,int const b)
{
  int sw=heap[a];
  heap[a]=heap[b];
  heap[b]=sw;
  sw=pos[heap[a]];
  pos[heap[a]]=pos[heap[b]];
  pos[heap[b]]=sw;
};

void __fastcall heapify_d(const int i)
{
  int l=left(i);
  int r=right(i);
  int max=i;
  if ((l<=hs) && (p1[heap[l]]<p1[heap[i]])){max=l;};
  if ((r<=hs) && (p1[heap[r]]<p1[heap[max]])){max=r;};
  if (max!=i)
  {
    swap(i,max);
    heapify_d(max);
  };
};

int extract_max()
{
  int o=heap[1];
  swap(1,hs);
  hs--;
  heapify_d(1);
  return o;
};

void buildheap()
{
  for (int i=n / 2;i>0;i--)
  {
    heapify_d(i);
  };
};

void __fastcall heapify_u(int const a)
{
  int i=a;
  while (i>0 && heap[i]<heap[parent(i)])
  {
    swap(i,parent(i));
    i=parent(i);
  };
};

void dijkstr()
{
  for (int j=1;j<n;j++)
  {
    m=extract_max();
    for (int i=1;i<=kg[m];i++)
    {
      if (p1[m]+p[m][i]<p1[g[m][i]])
      {
        p1[g[m][i]]=p1[m]+p[m][i];
        pred[g[m][i]]=m;
        heapify_u(pos[g[m][i]]);
      };
    };
  }
};

void main()
{
  int i;
  FILE *out,*in;
  in=fopen("input.txt","rb");
  out=fopen("output.txt","wb");
  fscanf(in,"%d",&n);
  fscanf(in,"%d",&m);
  kg=(int *)malloc((n+1)*sizeof(int));
  heap=(int *)malloc((n+1)*sizeof(int));
  pos=(int *)malloc((n+1)*sizeof(int));
  p1=(int *)malloc((n+1)*sizeof(int));
  pred=(int *)malloc((n+1)*sizeof(int));
  for (i=0;i<=n;i++)
  {
    kg[i]=0;
  };
  for (i=0;i<=n+1;i++)
  {
    g[i]=(int *)malloc(sizeof(int));
    p[i]=(int *)malloc(sizeof(int));
  };
  for (i=1;i<=m;i++)
  {
    fscanf(in,"%d%d%d",&a,&b,&c);
    if (a!=b)
    {
    kg[a]++;
    kg[b]++;
    g[a]=(int *)realloc(g[a],kg[a]*sizeof(int));
    g[b]=(int *)realloc(g[b],kg[b]*sizeof(int)); //вот тут вылетает... примерно где-то после i=700
    g[a][kg[a]]=b; p[a][kg[a]]=c;
    g[b][kg[b]]=a; p[b][kg[b]]=c;
    };
  };
  fscanf(in,"%d",&a);
  fscanf(in,"%d",&b);
  for (i=1;i<=n;i++)
  {
    heap[i]=i;
    p1[i]=999999999;
    pred[i]=a;
    pos[i]=i;
  };
  for (i=1;i<=kg[a];i++)
  {
    p1[g[a][i]]=p[a][i];
  };
  pred[a]=0;
  p1[a]=0;
  hs=n;
  buildheap();
  c=extract_max();
  dijkstr();
  fprintf(out,"%d",p1[b]);
  fclose(in);
  fclose(out);
}

а вот тестик, на котором не работает... http://leonovich.h14.ru/input.rar

помогите плз.. уже который день мучаюсь.. smile

и еще, если без realloc'a сразу выделить памяти по 10000, то еррор уже другой, но тоже непонятно почему....

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 15.2.2006, 08:28 (ссылка)

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

Загрузка ...

Шустрый

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

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

BSOD, у Вас есть как минимум один косяк в Вашей программе - в цикле for, в строках 106-110:

Код


  for (i=0;i<=n+1;i++)
  {
    g[i]=(int *)malloc(sizeof(int));
    p[i]=(int *)malloc(sizeof(int));
  };

Обратите внимание: массивы g и p у Вас имеют по 10001 элементов, а тело цикла выполняется 10002 раза (поскольку n в Вашем тесте имеет значение 10000)!! И Вы вылезаете за границы массива. Маленький совет: если Вы на Сях в цикле for используете переменную-счетчик в качестве индекса массива, никогда в кач-ве условия не ставьте <=, ставте просто знак <. (Т.е, если размер массива 10001 эл-тов, то индекс должен изменятся в пределах от 0 до 10000, а не от 0 до 10001).

Это сообщение отредактировал(а) Lotrex - 15.2.2006, 08:36

BSOD

Дата 15.2.2006, 14:42 (ссылка)

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

Загрузка ...

Опытный

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

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

исправил - не помогло... smile

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 15.2.2006, 16:55 (ссылка)

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

Загрузка ...

Шустрый

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

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

В других местах у Вас ничего похожего нет? Остальные for'ы поглядите! Я тож погляжу

Lotrex

Дата 15.2.2006, 19:01 (ссылка)

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

Загрузка ...

Шустрый

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

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

Вот тут у Вас еще 2 косяка (по-моему, это строки 111-123 приведенного текста):

Код


  for (i=1;i<=m;i++)
  {
    fscanf(in,"%d%d%d",&a,&b,&c);
    if (a!=b)
    {
        kg[a]++;
        kg[b]++;
        g[a]=(int *)realloc(g[a],kg[a]*sizeof(int));
        g[b]=(int *)realloc(g[b],kg[b]*sizeof(int)); //вот тут вылетает... примерно где-то после i=700
        g[a][kg[a]]=b; p[a][kg[a]]=c;
        g[b][kg[b]]=a; p[b][kg[b]]=c;
    };
  };

Косяк №1

:
Итак, помним, что g[a] - это массив из kg[a] элементов, следовательно, допустимый диапазон изменения индексов - от 0 до kg[a]-1!! А у Вас что написано? Опять за границы вылезаем... Аналогично с массивом g[b].
Косяк №2 smile

:
массивы p[a] и p[b] у Вас инициализированы только 1 раз! Я так понимаю, память под них тоже надо функцией realloc перераспределять - первоначально Вы выделили память только под 1 элемент!

BSOD

Дата 15.2.2006, 20:42 (ссылка)

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

Загрузка ...

Опытный

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

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

опа ... вот это косяк так косяк... пасиба... глюк продвинулся гораздо дальше smile

буду дальше думать... =)

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 16.2.2006, 10:24 (ссылка)

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

Загрузка ...

Шустрый

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

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

Ну как, движение есть? smile

BSOD

Дата 16.2.2006, 16:15 (ссылка)

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

Загрузка ...

Опытный

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

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

хех, опять не работает....
и похоже я опять что-то где-то с памятью упустил...
теперь еррор в процедуре swap, причем не сразу, а когда она вызывается из heapify_u....
опять access violation...

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 16.2.2006, 16:17 (ссылка)

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

Загрузка ...

Шустрый

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

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

новый код приведи полностью - поковыряем на досуге. smile

BSOD

Дата 16.2.2006, 16:35 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


#include <stdio.h>
#include <stdlib.h>

int n,m,*g[10002],*p[10002],*kg,*pos,*pred,*p1,*heap,a,b,c,hs;

int __fastcall left(const int a)
{
  return a*2;
};

int __fastcall right(const int a)
{
  return (a*2)+1;
};

int __fastcall parent(const int a)
{
  return a / 2;
};

void __fastcall swap(int const a,int const b)
{
  int sw;
  sw=heap[a];
  heap[a]=heap[b];
  heap[b]=sw;
  sw=pos[heap[a]];
  pos[heap[a]]=pos[heap[b]];
  pos[heap[b]]=sw;
};

void __fastcall heapify_d(const int i)
{
  int l=left(i);
  int r=right(i);
  int max=i;
  if ((l<=hs) && (p1[heap[l]]<p1[heap[i]])){max=l;};
  if ((r<=hs) && (p1[heap[r]]<p1[heap[max]])){max=r;};
  if (max!=i)
  {
    swap(i,max);
    heapify_d(max);
  };
};

int inline extract_max()
{
  int o=heap[1];
  swap(1,hs);
  hs--;
  heapify_d(1);
  return o;
};

void inline buildheap()
{
  for (int i=(n / 2)+1;i>0;i--)
  {
    heapify_d(i);
  };
};

void __fastcall heapify_u(int const a)
{
  int i=a;
  while (i>0 && heap[i]<heap[parent(i)])
  {
    swap(i,parent(i));
    i=parent(i);
  };
};

void inline dijkstr()
{
  for (int j=1;j<n;j++)
  {
    m=extract_max();
    for (int i=1;i<=kg[m];i++)
    {
      if (p1[m]+p[m][i]<p1[g[m][i]])
      {
        p1[g[m][i]]=p1[m]+p[m][i];
        pred[g[m][i]]=m;
        heapify_u(pos[g[m][i]]);
      };
    };
  }
};

void main()
{
  int i;
  FILE *out,*in;
  in=fopen("input.txt","rb");
  out=fopen("output.txt","wb");
  fscanf(in,"%d",&n);
  fscanf(in,"%d",&m);
  pos=(int *)malloc((n+1)*sizeof(int));//new int(n+1);
  heap=(int *)malloc((n+1)*sizeof(int));//new int(n+1);
  p1=(int *)malloc((n+1)*sizeof(int));//new int(n+1);
  pred=(int *)malloc((n+1)*sizeof(int));//new int(n+1);
  kg=(int *)malloc((n+1)*sizeof(int));//new int(n+1);
  for (i=0;i<=n;i++)
  {
    g[i]=(int *)malloc(sizeof(int));
    p[i]=(int *)malloc(sizeof(int));
  };
  for (i=0;i<=n;i++)
  {
    kg[i]=0;
  };
  for (i=1;i<=m;i++)
  {
    fscanf(in,"%d%d%d",&a,&b,&c);
    if (a!=b)
    {
    kg[a]++;
    kg[b]++;
    g[a]=(int *)realloc(g[a],(kg[a]+1)*sizeof(int));
    g[b]=(int *)realloc(g[b],(kg[b]+1)*sizeof(int));
    p[a]=(int *)realloc(p[a],(kg[a]+1)*sizeof(int));
    p[b]=(int *)realloc(p[b],(kg[b]+1)*sizeof(int));
    g[a][kg[a]]=b; p[a][kg[a]]=c;
      g[b][kg[b]]=a; p[b][kg[b]]=c;
    };
  };
  fscanf(in,"%d",&a);
  fscanf(in,"%d",&b);
  for (i=1;i<=n;i++)
  {
    heap[i]=i;
    p1[i]=999999999;
    pred[i]=a;
    pos[i]=i;
  };
  for (i=1;i<=kg[a];i++)
  {
    p1[g[a][i]]=p[a][i];
  };
  pred[a]=0;
  p1[a]=0;
  hs=n;
  buildheap();
  c=extract_max();
  dijkstr();
  fprintf(out,"%d",p1[b]);
  fclose(in);
  fclose(out);
}

воть...

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 17.2.2006, 08:43 (ссылка)

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

Загрузка ...

Шустрый

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

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

Слушай, у меня на работе твой новый вариант не вылетает - до конца доходит. Я еще дома погляжу (там комп послабже)

BSOD

Дата 17.2.2006, 18:51 (ссылка)

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

Загрузка ...

Опытный

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

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

на каком тесте, и какой ответ выдает?

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 17.2.2006, 19:32 (ссылка)

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

Загрузка ...

Шустрый

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

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

На том, что ты дал, ответ - 9 девяток.

Если это правильно - давай другой тестик сваргань, позыркаем, что там и как. Дома у меня тоже идет.

BSOD

Дата 17.2.2006, 21:27 (ссылка)

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

Загрузка ...

Опытный

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

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

дык вот 9 девяток - это как раз и не правильно...
странно как-то, алгоритм вроде правильный... на малых тестах то работал правильно...

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

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

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

Загрузка ...

Шустрый

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

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

Если у Вас тесты делаются автоматом - сделайте штуки 3 разных размеров, определимся на каком идет.

А еще лучше - сделайте прогу, которая тесты клепает - на входе ей даешь размер графа (или что там), на выходе - тест и правильный ответ к нему. На Паскале (или Дельфях) - у Вас, насколько я понимаю, там все без проблем получается.

Еще маленький советик - сделайте так, что бы в Вашей программе не было глобальных переменных (вообще). Передавайте их в функции как параметры. В сях с этим просто - все пр-ры передаются просто по значению - если передаешь int, то передается значение переменной, если передаешь какой-то указатель (не важно, какой размерности) - передается значение указателя. Внутри функции можете с ними что хотите делать (только free для указателей не вызывайте smile

).

Это сообщение отредактировал(а) Lotrex - 18.2.2006, 13:41

BSOD

Дата 18.2.2006, 17:07 (ссылка)

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

Загрузка ...

Опытный

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

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

Нет, тесты сами не генерятся, но все-таки пару тестов есть...
http://leonovich.h14.ru/test1.zip
http://leonovich.h14.ru/test2.zip
http://leonovich.h14.ru/test3.zip
воть...

На счет указателей - поробую, но не думаю, что поможет...

--------------------

как корабль назовешь - то на нем и напишешь

Lotrex

Дата 20.2.2006, 10:07 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

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