Динамическое выделение памяти под структуры

@v4567 · Регистрация: 10.05.2008

Author24 — интернет-сервис помощи студентам

Есть вот такая структура:

C

struct asd
{
 int data;
 struct asd *next;
};

Динамически выделяю память под такую структуру:

C

struct asd *newst(struct asd *head)
{
 struct asd *newstructura;
 newstructura = (struct asd *)malloc(sizeof(struct asd));
 newstructura -> next = head;
 return newstructura;
}

Потом в основном теле программы инициализирую несколько таких структур с динамическим выделением памяти под каждую:

C

int i, n = 20;
struct asd *head;
head = NULL;
 
for(i = 0; i < n; i++)
{
 head = newst(head);
}

Вопрос можно ли перемещаться по структурам меняя указатель head вот таким образом head-- или head++
Я думаю что нельзя, хотя написал небольшую тестовую программку и всё работает. Но работает я думаю из-за того, что данные структуры занимают очень мало места в памяти и при выделении памяти они все будут в одном месте, поэтому меняя указатель head - head-- или head++ мы будем перемещаться по структурам. Но если бы структуры были очень большими и их было очень много, то, есть вероятность, что одна часть их будет расположена в одном месте, а другая в другом месте памяти и тогда перемещаться по структурам меняя head не получиться.
Хотелось бы узнать правильно я думаю или ошибаюсь!
Правильно перемещаться по структурам надо наверное так:

C

int i, n = 20;
struct asd *head;
head = NULL;
 
for(i = 0; i < n; i++)
{
 head = newst(head);
}
 
struct asd *p;
p = head;
p = p -> next;

Исходя из этого перемещаться можно сверху вниз и если нужно подняться на одну структуру вверх, то надо переместиться в самый вверх, а потом опуститься до нужной структуры. Можно ли как то произвольно гулять по структурам?

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

Освобождение памяти с помощью free

Теперь рассмотри, как происходит освобождение памяти. Переменная указатель хранит адрес области памяти, начиная с которого она может им пользоваться. Однако, она не хранит размера этой области. Откуда тогда функция free знает, сколько памяти необходимо освободить?

Очевидно, что информация о размере выделенного участка должна где-то храниться. Есть несколько решения этой проблемы.
1. Можно создать карту, в которой будет храниться размер выделенного участка. Каждый раз при освобождении памяти компьютер будет обращаться к этим данным и получать нужную информацию.
2. Второе решение более распространено. Информация о размере хранится на куче до самих данных. Таким образом, при выделении памяти резервируется места больше и туда записывается информация о выделенном участке. При освобождении памяти функция free "подсматривает", сколько памяти необходимо удалить.
Функция free освобождает память, но при этом не изменяет значение указателя, о чём нужно помнить.

Но у меня почему то при освобождении памяти выдаёт ошибку хотя до освобождения памяти программа работает нормально:

Код

*** glibc detected *** ./yrok161: double free or corruption (out): 0x0812e020 ***
======= Backtrace: =========
/lib/libc.so.6[0xb35231]
./yrok161[0x8048654]
/lib/libc.so.6(__libc_start_main+0xe6)[0xadba66]
./yrok161[0x8048411]
======= Memory map: ========
003e7000-00411000 r-xp 00000000 08:02 2237624    /lib/libgcc_s-4.4.0-20090506.so.1
00411000-00412000 rw-p 00029000 08:02 2237624    /lib/libgcc_s-4.4.0-20090506.so.1
00a77000-00a78000 r-xp 00a77000 00:00 0          [vdso]
00a9d000-00abd000 r-xp 00000000 08:02 2236420    /lib/ld-2.10.1.so
00abd000-00abe000 r--p 0001f000 08:02 2236420    /lib/ld-2.10.1.so
00abe000-00abf000 rw-p 00020000 08:02 2236420    /lib/ld-2.10.1.so
00ac5000-00c30000 r-xp 00000000 08:02 2236959    /lib/libc-2.10.1.so
00c30000-00c31000 ---p 0016b000 08:02 2236959    /lib/libc-2.10.1.so
00c31000-00c33000 r--p 0016b000 08:02 2236959    /lib/libc-2.10.1.so
00c33000-00c34000 rw-p 0016d000 08:02 2236959    /lib/libc-2.10.1.so
00c34000-00c37000 rw-p 00c34000 00:00 0
08048000-08049000 r-xp 00000000 08:02 7955556
08049000-0804a000 rw-p 00000000 08:02 7955556
0812e000-0814f000 rw-p 0812e000 00:00 0          [heap]
b7efe000-b7f00000 rw-p b7efe000 00:00 0
b7f29000-b7f2b000 rw-p b7f29000 00:00 0
bfa15000-bfa2a000 rw-p bffeb000 00:00 0          [stack]
Аварийный останов

И последний вопрос надо ли после освобождения памяти обнулять указатель head: head = NULL?

Вот моя небольшая тестовая программка:

C

#include <stdio.h>
#include <stdlib.h>
 
struct asd
{
 int data;
 struct asd *next;
};
 
struct asd *newst(struct asd *);
void zdan(struct asd *, int);
int vivod(struct asd *);
 
void main(void)
{
 int i, n;
 struct asd *head;
 head = NULL;
 
 scanf("%d", &n);
 
 for(i = 0; i < n; i++)
 {
  head = newst(head);
 }
 
 for(i = 0; i < (n - 1); i++)
 {
  head--;
 }
 
 for(i = 0; i < n; i++)
 {
  zdan(head, i);
  if(i != (n - 1))
  {
   head++;
  }
 }
 
 for(i = 0; i < (n - 1); i++)
 {
  head--;
 }
 
 for(i = 0; i < n; i++)
 {
  printf("%d", vivod(head));
  if(i != (n - 1))
  {
   printf(" --> ");
   head++;
  }
 }
 printf("\n");
 
 for(i = 0; i < n; i++)
 {
  printf("%d", vivod(head));
  if(i != (n - 1))
  {
   printf(" --> ");
   head--;
  }
 }
 printf("\n");
 
 if(i != (n - 1))
 {
  head++;
 }
 free(head);
 head = NULL;
}
 
struct asd *newst(struct asd *head)
{
 struct asd *newstructura;
 newstructura = (struct asd *)malloc(sizeof(struct asd));
 newstructura -> next = head;
 return newstructura;
}
 
void zdan(struct asd *head, int x)
{
 head -> data = x;
}
 
int vivod(struct asd *head)
{
 return head -> data;
}

Компилирую командой:

Bash

1	gcc -o yrok161 yrok161.c

За помощь заранее благодарен!

Humanoid · 13.10.2016, 15:47

Сообщение от v4567

Вопрос можно ли перемещаться по структурам меняя указатель head вот таким образом head-- или head++

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

Сообщение от v4567

Правильно перемещаться по структурам надо наверное так

Да. Ну и надо проверять, что выбираемая структура не NULL.

Сообщение от v4567

Можно ли как то произвольно гулять по структурам?

Можно использовать два указателя:

C

struct asd
{
 int data;
 struct asd *prev;
 struct asd *next;
};

И заполнять:

C

struct asd *newst(struct asd *head)
{
 struct asd *newstructura;
 newstructura = (struct asd *)malloc(sizeof(struct asd));
 if (head)
   head -> next = newstructura;
 newstructura -> prev = head;
 newstructura -> next = NULL;  // next этой структуры будет заполнен при создании следующей структуры
 return newstructura;
}

Сообщение от v4567

надо ли после освобождения памяти обнулять указатель head: head = NULL?

Так как вы больше этой переменной не пользуетесь, то и обнулять её не имеет смысла.

@si1n3rd · 13.10.2016, 16:23

Сообщение от Humanoid

Можно использовать два указателя.

Это ведь получится связанный список из структур. Верно?

Humanoid · 13.10.2016, 19:58

Сообщение от si1n3rd

Это ведь получится связанный список из структур. Верно?

Честно говоря, не силён в названиях, но судя по википедии, да, это двусвязный список.

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

@v4567 · 13.10.2016, 23:08 **[ТС]**

Разобрался. Всем огромное спасибо за помощь!

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

C

#include <stdio.h>
#include <stdlib.h>
 
struct asd
{
 int data;
 struct asd *next;
};
 
struct asd *newst(struct asd *);
void zdan(struct asd *, int);
int vivod(struct asd *);
 
void main(void)
{
 int i, n, k;
 struct asd *head = NULL, *p = NULL;
 
 scanf("%d", &n);
 
 for(i = 0; i < n; i++)
 {
  head = newst(head);
 }
 
 p = head;
 i = (n - 1);
 
 while(p)
 {
  zdan(p, i);
  p = p -> next;
  i--;
 }
 
 p = head;
 
 for(k = 0; k < n; k++)
 {
  for(i = 0; i < (n - 1 - k); i++)
  {
   p = p -> next;
  }
  printf("%d", vivod(p));
  if(k != (n - 1))
  {
   printf(" --> ");
  }
  p = head;
 }
 printf("\n");
 
 while(p)
 {
  printf("%d", vivod(p));
  p = p -> next;
  if(p)
  {
   printf(" --> ");
  }
 }
 printf("\n");
 
 while(head)
 {
  p =  head -> next;
  free(head);
  head = p;
 }
 
 head = NULL;
 p = NULL;
}
 
struct asd *newst(struct asd *head)
{
 struct asd *newstructura;
 newstructura = (struct asd *)malloc(sizeof(struct asd));
 newstructura -> next = head;
 return newstructura;
}
 
void zdan(struct asd *head, int x)
{
 head -> data = x;
}
 
int vivod(struct asd *head)
{
 return head -> data;
}

@si1n3rd 48 / 46 / 18 Регистрация: 27.04.2016 Сообщений: 169
	13.10.2016, 16:23	3
	Сообщение от Humanoid Можно использовать два указателя. Это ведь получится связанный список из структур. Верно? 0

Humanoid Почетный модератор 11525 / 4320 / 448 Регистрация: 12.06.2008 Сообщений: 12,412
	13.10.2016, 19:58	4
	Сообщение от si1n3rd Это ведь получится связанный список из структур. Верно? Честно говоря, не силён в названиях, но судя по википедии, да, это двусвязный список. Добавлено через 1 минуту Так же как пример автора, похоже, является односвязным списком, который описан выше в той же статье. 1

	13.10.2016, 23:08