Задача с листами на С

Рейтинг: 0Ответов: 1Опубликовано: 08.11.2014

Всем привет! Нужна помощь с листами, есть такой код, сам писал для практики, только, где беда, не понимаю, объясните, плиз.

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

typedef struct node
{
    int  num;
    struct node *next;
    struct node *Prev;
} Node;
Node *init()
{
    int i;
    Node *ptr = (Node*)calloc(10, sizeof(Node));
    for (i = 1; i <= 10; i++, ptr->next)
    {
        ptr->num = 1;
        ptr->next = NULL;
    }

}
int main()
{
    Node *head;
    head = 0;
    head->num = 1;
    head->next = NULL;
    head->Prev = NULL;
    return 0;
}

Ответы

▲ 1

А что Вы хотели получить?

Вот:

 head->num = 1;

в main -- это очевидная ошибка, поскольку строчкой ранее Вы сами пишете:

head = 0;

а по 0-му (он же NULL) адресу обращаться нельзя.

Обновление

@smackmychi, очевидно, что это именно так. Вот и попробуем (если, конечно, он сам не сбежит) быстренько подтолкнуть его в нужном направлении.

@nwhta, судя по структуре Node, Вы хотите сделать двусвязный список. Возможно, из 10 элементов, пронумерованных от 1 до 10.

Это так?

И еще один вопрос, вы уже читали про память, адреса и указатели?

Обновление 2

@nwhta, (без всяких наездов) зачем выделять память для 10 структур, да еще и в функции, которая не вызывается?

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

Т.е. основой main будет вот такой цикл:

 for (i = 1; i < 11; i++) {
   Node *item = init_item(i);
  // а здесь будем вставлять в список
 }

Кстати, двусвязные список лучше организовать в виде 2-х указателей, один на первый, а другой на последний элементы списка.

Обновление 3

@nwhta, если указатели на начало и конец двусвязного списка инициализированы нулями, то добавление нового элемента в конец списка делается вот так:

      // порядок строк кода важен !!!
      item->next = 0;
      if (!head) 
        head = item;
      else 
        tail->next = item;
      item->prev = tail;
      tail = item;

После этого список находится в согласованном состоянии и его можно, например, распечатывать в прямом

      for (item = head; item; item = item->next)
        printf("%d\n", item->num);

и обратном

      for (item = tail; item; item = item->prev)
        printf("%d\n", item->num);

порядке.

Все остальное, надеюсь, сделаете сами.

Обновление 4

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

Например, в нашем коде вставки постоянно производится проверка не пуст ли список? Очевидно, что если у нас задача сделать список известной длины, то это совершенно некрасиво.

Попробуем написать обобщенное решение частной задачи -- сделать список последовательных чисел размером N элементов.

Для начала напишем функцию, которая возвращает заполненный элемент списка.

#include <sysexits.h>

static inline struct node *make_item(int num) {
   struct node *p = (typeof(p))calloc(1, sizeof(*p));
   if (!p) {
     perror("allocate node");
     exit(EX_OSERR);  // корректный для такой ситуации код завершения из sysexits.h
   }
   p->num = num;

   return p;
}

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

Поскольку функция очень маленькая, попросим компилятор не вызывать ее (call), а всюду встраивать ее код в код вызывающей функции (это ускоряет выполнение) и для этого припишем ей слова static inline (подробнее в учебниках).

Здесь же принимаем проектное решение -- если ОС не может выделить память - сообщим юзеру об этом и завершим программу. Такое решение не бесспорно, но в большинстве случаев всех вполне устраивает, а жизнь программисту (анализ ошибок) сильно облегчает.

Теперь вспомним, что список (кстати, любой нециклический, что дву-, что односвязный) удобно представлять парой указателей. Для удобства объединим их в структуру:

 struct list2 {
   struct node *head, *tail;
 };

И вот все для написания функции, обобщенно решающей нашу частную задачку уже готово.

// Returns list (struct of 2 pointers) 
// строит двусвязный список последовательных чисел размером n элементов, 
// начиная с числа first_num
struct list2 
make_nlist (int first_num, int n)
{
  /* инициализируем структуру для разумного результата при ошибке в запрашиваемом размере списка */
  struct list2 list = {0, 0};

  if (n-- > 0) {  // запрошен непустой список 
    // вставим первый элемент, поэтому в if уменьшали n
    list.head = list.tail = make_item(first_num++); 
    while (n--) { 
      // вставим в хвост списка все остальные
      list.tail->next = make_item(first_num++);
      list.tail->next->prev = list.tail;
      list.tail = list.tail->next;
    }
  }
  return list;
}

Теперь можно использовать эту функцию, например, для печати последовательностей чисел, начинающихся с 1 "вперед и назад" :)

int 
main (int ac, char *av[])
{
  struct node *item;
  struct list2 list = make_nlist(1, atoi(av[1] ? av[1] : "10"));

  for (item = list.head; item; item = item->next)
    printf("%d\n", item->num);
  puts ("==");
  for (item = list.tail; item; item = item->prev)
    printf("%d\n", item->num);

  return puts("End") == EOF;
}