Отправляет email-рассылки с помощью сервиса Sendsay

C и C++ для начинающих

Рассылка закрыта

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Июнь 2001   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор Гость

Статистика

8.368 подписчиков
за неделю
←   Все выпуски   →

C и C++ для начинающих - Выпуск 11. Структуры и связные списки.


Служба Рассылок Subscribe.Ru проекта Citycat.Ru
Доброго времени суток! Сегодня речь пойдет о структурах и связных списках.

Возвращаясь к напечатанному

В восьмом выпуске рассылки я допустил опечатку - сразу после синтаксиса описания массивов в рассылке идет пример программы. В нем в строке printf не должно быть амперсанта. То есть программа должна выглядеть так: 
 #include <stdio.h>

 int main (void)
 {
  int i, a [100];

  for (i = 0; i < 100; i++)
   scanf ("%d", &(a [i]));
  for (i = 99; i >= 0; i--)
   printf ("%d\n", a [i]);

  return 0;
 }
Еще раз извиняюсь. Но те, кто нашел ошибку - молодцы! Это доказывает, что с указателями вы освоились.

Вопрос - ответ

Q. Где взять в Сети компилятор С?
A. Не знаю. Сомневаюсь даже, что в Сети они вообще есть. Поищите у друзей, знакомых. Тем же, кому для освоения С не жалко 70 рублей, могут купить диск с любым компилятором С.

Q. Цитирую письмо (по материалам 10-го выпуска): 
Здравствуй !!!

Вижу продвигается рассылка...
Я вот заглянул в №10 и сижу и думаю:
то ли я не понял, то ли я глючу, то ли тута действительно что-то на так..
Тама ты пишешь:
"Например, если мы создали переменную типа int, но размером в 8 байт, то
sizeof возвратит 2 или 4 в зависимости от платформы, но никак не 8"

Дело в том что эта "хитрая и коварная" sizeof возвратит именно 8.
Она возвращает размер в байтах, не приводя к типу !!!
(можешь в хелповнике почитать, хотя и сам знаешь)
т.е. sizeof(int a) =4..
A. Что ж... похоже, мы друг друга не поняли. Я имел в виду нижеследующее: 
 #include <stdio.h>
 int main (void)
 {
  int *a;
  a = (int*) malloc (8);
  printf ("%d\n", sizeof (*a))
  /* будет напечатано 2 или 4 */
  return 0;
 }

Организационная часть

  1. Многие предлагают мне рассматривать некоторые зависимые от платформы детали. Вообще-то я этого делать не хотел. Но, видимо, придется... Для того, чтобы определиться, мне нужна ваша помощь. Итак, вопрос: какую платформу вы используйте?
    Win32 (MS VC++, C++ Builder, BC++ 4.0 или выше)
    DOS (MS Quick C, Borland C++ 3.1 или ниже)
    Unix
    Прочее

    Если выяснится, что подавляющее большинство подписчиков используют что-то одно, то я буду более детально рассматривать особенности именно этой платформы.

  2. Также по просьбе некоторых подписчиков открывается форум. Так что все вопросы по части программирования можете задавать туда. А можете, как и раньше, мне - еще не знаю, получится ли у меня регулярно просматривать этот самый форум. Да, если знаете ответ на вопрос, заданный другим подписчиком - напишите! Этим вы сильно поможете всем. Не исключено, что со временем к форуму добавятся еще некоторые полезные вещи и все это выльется в некоторое подобие сайта - но пока что на него у меня просто нет времени.

Программирование

Итак, ближе к теме. Как мы знаем, массив - это множество однотипных переменных. Структура представляет из себя нечто похожее - это тоже множество переменных, но только разнотипных. Элементы структуры (вернее, поля стркутуры), в отличие от элементов массива, не имеют индекса, но имеют собственное имя. Структуры на С описываются так: 
 struct [имя_структуры]
 {
  имя_типа имя_переменной [, имя_переменной [,...]];
  имя_типа имя_переменной [, имя_переменной [,...]];
  .......
  имя_типа имя_переменной [, имя_переменной [,...]];
 };
Чтобы было более понятно, я просто приведу пример: 
 struct MyStruct
 {
  int a, b;
  char c[5];
  float d;
 };
Таким образом мы объявили новый тип - MyStruct, представляющий из себя структуру. Если мы хотим объявить переменную a типа MyStruct, то это следует делать так: 
 struct MyStruct a;
Доступ к полям структуры осуществляется с помощью точки, например: 
 a.c[3] = 5;
Но если у нас есть указатель на структуру, то мы можем получить доступ к полю этой структуры с помощью оператора ->. Например: 
 struct MyStruct *a;
 a->c[3] = 5;
Объявление типа структуры и экземпляра этой структуры можно совместить: 
 struct MyStruct
 {
  int a, b;
  char c[5];
  float d;
 } a;
Теперь вы, возможно, поняли, почему название типа структуры в объявлении можно не указывать. Это дает возможность создавать безымянные структуры, например: 
 struct
 {
  int a, b;
  char c[5];
  float d, *e;
 } a;
Ввиду того, что у объявленного типа нет названия, a - единственный возможный экземпляр данного типа.

Как и все переменные, структуры можно инициализировать сразу при их объявлении. Инициализируются они так же, как и массивы: в фигурных скобках через запятую перечисляются подряд значения всех полей. Как вы уже догадались, объявление типа структуры, экземпляра и его инициализацию можно вообще объединить, получив нечто вроде: 
 struct
 {
  int a, b;
  char c[5];
  float d;
 } a = {1, 2, {3, 4, 5, 6, 7}, 8.5};
Откуда взялись вложенные скобки? Просто не надо забывать, что a.d - это массив, следовательно, и инициализировать его надо как массив.

Следует сказать, что вы можете просто указать компилятору, что существует тип структуры, а объявить его позже: 
 struct MyStruct;

 ...................

 struct MyStruct
 {
  int a, b;
  char c[5];
  float d;
 };
Для чего это нужно - увидите позже. Что может быть элементом структуры? Да все, что угодно - переменные, указатели, массивы, другие структуры. Единственное ограничение - переменная должна быть полностью объявлена раньше в программе. Если на структуру объявлен прототип, но сама она не объявлена, то ее включать в определение структуры нельзя. Но можно включать указатель на нее. Это нам сильно поможет в дальнейшем. Определяемая структура считается необъявленной, но на нее как бы объявлен прототип.

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

Если бы не последнее условие, то нам идеально подошел бы динамический массив. Но тут он оказывается бессильным - если мы будем каждый раз при добавлении нового элемента делать realloc, то очень скоро получим нехватку памяти - в результате копироваия данных в новое место память может оказаться фрагментированной настолько, что в ней просто не найдется непрерывного блока требуемой длины. Так что динамиеские массивы отпадают. Что делать?

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

Что, если мы применим этот подход? Он как раз идеально подходит нашим условиям. (Конструкции такого типа называют связными списками). Итак, первым делом опишем структуру элемента: 
 struct TElem
 {
  int Int1, Int2;
  float Float;
  TElem *Next;
 };
Выделенное красным цветом поле - это и есть указатель на следующий элемент нашего списка. Теперь можно написать функции для работы с этим списком. Вся работа сводится к манипуляциям указателями: 
 /* Добавление нового элемента в список.
  List - список
  Place - номер элемента, перед которым следует вставить новый элемент
   (0 - в самое начало, -1 - в самый конец)
  Int1, Int2, Float - поля нового элемента
 */
 void InsertElem (struct TElem **List, int Place, int Int1, int Int2, float Float)
 {
  struct TElem *NewElem, *Cur;

  NewElem = (struct TElem*) malloc (sizeof (struct TElem));
  NewElem->Int1 = Int1;
  NewElem->Int2 = Int2;
  NewElem->Float = Float;

  if (!*List)
  {
   NewElem->Next = NULL;
   *List = NewElem;
  }
  else
   if (!Place)
   {
    NewElem->Next = *List;
    *List = NewElem;
   }
   else
   {
    for (Cur = *List; --Place && Cur->Next; Cur = Cur->Next);
    NewElem->Next = Cur->Next;
    Cur->Next = NewElem;
   }
 }

 /* Удаление элемента из списка.
  List - список
  Place - номер элемента, подлежащего удалению (начиная с нуля)
 Возвращаемое значение:
  1 - удаление успешно
  0 - выход за границы списка
 */
 int RemoveElem (struct TElem **List, int Place)
 {
  struct TElem *Elem, *Cur;

  if (!(*List)->Next)
   if (!Place)
   {
    Elem = *List;
    *List = NULL;
   }
   else
    return 0;
  else
   if (!Place)
   {
    Elem = *List;
    *List = Elem->Next;
   }
   else
   {
    for (Cur = *List; --Place && Cur->Next; Cur = Cur->Next);
    if (!Cur->Next)
     return 0;
    Elem = Cur->Next;
    Cur->Next = Elem->Next;
   }

  free (Elem);
  return 1;
 }

 /* Удаление элемента из списка.
  List - список
  Place - номер элемента, подлежащего считыванию (начиная с нуля)
  Int1, Int2, Float - переменные-получатели соответствующих полей элемента
 Возвращаемое значение:
  1 - считывание успешно
  0 - выход за границы списка
 */
 int GetElem (struct TElem **List, int Place, int *Int1, int *Int2, float *Float)
 {
  struct TElem *Cur;

  for (Cur = *List; Place-- && Cur; Cur = Cur->Next);
  if (!Cur)
   return 0;

  *Int1 = Cur->Int1;
  *Int2 = Cur->Int2;
  *Float = Cur->Float;

  return 1;
 }

 /* Удаление всего списка */
 void DeleteList (struct TElem **List)
 {
  while (*List)
   RemoveElem (List, 0);
 }

 /* Небольшая функция для проверки работы */
 int main (void)
 {
  struct TElem *List = NULL;
  int a, b;
  float c;

  InsertElem (&List, 0, 1,  9,  0.5);
  InsertElem (&List, 10, 2,  8,  1.6);
  InsertElem (&List, -1, 3,  7,  2.7);
  InsertElem (&List, 0,  4,  6,  3.8);
  InsertElem (&List, 2,  5,  5,  4.9);

  GetElem (&List, 3, &a, &b, &c);

  RemoveElem (&List, 0);
  RemoveElem (&List, 10);
  RemoveElem (&List, 2);

  DeleteList (&List);

  return 0;
 }
Как видите, набор функций получился несколько объемистым. Тем не менее постарайтесь разобраться в нем сами - нет ничего более поучительного, чем поковырять чужие исходники. Еще рекомендую скопировать их в свою систему разработки и пройтись по ним отладчиком. Это и будет ваше домашнее задание (пусть оно будет числиться под номером 11.1.). Да, если все предыдущие задания были обязательны, то это - обязательно вдвойне! Без него вы просто не поймете того, что будет позже.

За сим все. До встречи!

Ведущий рассылки, av


Архив рассылки Подписаться Статистика рассылки Форум
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться Relayed by Corbina
Рейтингуется SpyLog
В избранное