Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Для новичков > Однонарпавленный список


Автор: madbizarre 14.12.2010, 21:01
В однонаправленном списке пытаюсь удалить каждый 3 элемент.
Код

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

//Opisanie strukturi tipa odnonapravlenni spisok
typedef struct _Element{
    int value;
    struct _Element *next;
} Element;
Element *head = NULL, *curr = NULL;

int cnt = 0, ind = 0;

int Add(int value)
{
  //Выделение памяти под новый элемент
  Element *tmp = (Element*)malloc(sizeof(Element));
  if(!tmp) return 1; //Если память не выделилась, то выход

  tmp->next = NULL;          //нулевым значением
  tmp->value = value;
  
  if(curr) curr->next = tmp;
  curr = tmp;
  
  if(!head) head = curr;
  return 1;              //Успешное завершение
} 

int Del()
{
   if(curr==NULL) return 0;
   if (!curr->next){ //если число элементов списка кратно 3
       curr->next = curr->next->next;
       Element *tmp=curr->next;
       free(curr);
       curr = tmp;
       return 1;
   }
   curr->next = curr->next->next;
   Element *tmp=curr->next;
   free(curr); curr=tmp;
   return 1;
}  

int Print()
{
    Element *tmp = head;
    printf("\nSpisok elementov posle udalenia:\n");
    while (tmp) 
    {
        printf("%d  ", tmp->value);
        tmp = tmp->next;
    }
}

//Glavnaia functsia
int main()
{
  int kol,elem=0;
    printf("Vvedite kolichestvo elementov spiska: ");
    scanf("%d",&kol);
    printf("\n");
if(kol<3) return 0;
    for (int k = 0; k < kol; k++) 
  {
     printf("Vvedite element No%d : ",k);
     scanf("%d",&elem);
     Add(elem);
  }
    curr = head;
    int i = 1;
    while (curr = curr->next)
    {
        i++;
        if (i == 3){
            Del();
            i = 1;
        }
    }
    Print();
    printf("\n");
    return 0;
}


После ввода значений, выдает ошибку... Подскажите что я не правильно делаю!

Автор: Dov 14.12.2010, 23:48
Счас придёт Чоо и всё тебе подробненько расскажет...  smile 

Автор: Чoо 15.12.2010, 00:45
а Чоо в последнее время разленился и ни чо не расскажет smile

Код

   if (!curr->next){ //если число элементов списка кратно 3
       curr->next = curr->next->next;
       Element *tmp=curr->next;
       free(curr);
       curr = tmp;
       return 1;
   }
   curr->next = curr->next->next;

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

curr->next = curr->next->next->...->next;

если и получится что-нибудь сваять, то прежде чем получится, замучаетесь с отладкой. 
а хотя... гляну чо там дальше...
значит, если указатель после curr если не равен NULL выполняем следующее:
Код

   curr->next = curr->next->next;
   Element *tmp=curr->next;
   free(curr); curr=tmp;
   return 1;

следующий элемент за curr равен следующему после следующего
временный элемент равен тому же следующему после следующего (соответственно получаем утечку, так как потеряли указатель на первоначальный curr->next)
потом забываем о наших всех манипуляциях и убиваем элемент curr. А потом, в довершение всего, делаем новую утечку, меняя указатель curr, который еще указывает на некую область памяти, на элемент, который изначально следовал за следующим после следующего.

Честно говоря, не хочется думать, как в маин происходит вычисление каждого третьего элемента.
небольшое замечание по ипользованию постфикса в p++. Хоть в данном случае ошибок нет и не может быть, лучше привыкать к префиксному варианту: поможет избежать в будущем неявных ошибок. Дело в том, что ++p возвращает новое значение, хранящееся в p, а p++ возвращает значение, которое было до инкремента (хотя в обоих случаях p инкрементируется).

Добавлено @ 00:49
Код

Element *head = NULL, *curr = NULL;

вот тут.. тут достаточно хранить один указатель на голову списка. Текущий элемент можно передавать в функцию.

Добавлено @ 00:55
Код

int Add(int value)
{
  //Выделение памяти под новый элемент
  Element *tmp = (Element*)malloc(sizeof(Element));
  if(!tmp) return 1; //Если память не выделилась, то выход
  tmp->next = NULL;          //нулевым значением
  tmp->value = value;
  
  if(curr) curr->next = tmp;
  curr = tmp;
  
  if(!head) head = curr;
  return 1;              //Успешное завершение
} 

может все-таки:
Код

if(head)
  {
    tmp->next = head;
    head = tmp;
  }
  else
    head = tmp;

?
вопщем. посоветую разбить решение задачи на 3 подзадачи:
1. Составление списка
2. Вывод списка.
3. Удаление элемента из списка.

Когда список будет нормально составляться, то можно приступать к функции его вывода.
Как только функция готова, приступаем к удалению (для наглядности после каждого удаления можно выводить список на экран). 

Автор: Чoо 15.12.2010, 01:41
примерно вот так будет выглядить вся задача:
Код

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

struct element{
    int value;
    element* next;
};

static element* head;

void addlist(int const value)
{
    element* p;
    p = (element*)malloc(sizeof(element));
    p->value = value;
    p->next = 0;
    if(head)
    {
        p->next = head;
        head = p;
    }
    else
        head = p;
}

void printlist()
{
    element* curr = head;
    if(!curr)
    {
        printf("список пуст\n");
        return;
    }
    while(curr)
    {
        printf("%d->",curr->value);
        curr = curr->next;
    }
    printf("\n");
}

void del(element* pre, element* curr)
{
    if(pre)
        pre->next = curr->next;
    else
        head = curr->next;
    free(curr);
}

int main()
{
    for(int i = 0; i< 10; ++i)
        addlist(i);
    printlist();

    element* curr = head, *pre = 0;

    /*каждый третий
    а каждый третий кратен трем
    */
    for(int i = 1; curr; ++i)
    {
        if(i%3==0)
        {
            /*ввел дополнительнуе переменную, что бы не коверкать функцию удаления элементов*/
            element* tmp = curr->next;
            del(pre,curr);
            curr = tmp;
            continue;
        }
        pre = curr;
        curr = curr->next;
    }
    printlist();
    return 0;
}

Автор: madbizarre 15.12.2010, 18:35
Спасибо очень помог...
Можешь еще подсказать вот такую задачу...

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

Прочитал много по двочному дереву, но нигде не нашел примера объядинения разности и пересечения, можешь по пунктам расказать что от меня требуется, если не сложно лёгкие примеры алгоритмов

Автор: Dov 15.12.2010, 23:26
Цитата(Чoо @  15.12.2010,  00:41 Найти цитируемый пост)
примерно вот так будет выглядить вся задача:

А что, нормалёк, по-моему. Получай по репе...  smile .

Автор: Dov 15.12.2010, 23:47
Хотя мне больше импонирует http://codepad.org/tnM5iINz

Автор: Чoо 15.12.2010, 23:50
ну да, удаление каждого третего логичней всего было отправить в функцию smile.
ну и с указателями на указатели я пока еще путаюсь, потому пока что предпочитаю без них обходиться smile.

Автор: madbizarre 16.12.2010, 09:13
Так что по поводу дерева?

Автор: Чoо 16.12.2010, 13:09
дерево делать не буду. там немного больше теории и больше кода.
вопщем элементом бинарного дерева будет:
Код

struct tree{
  int value;
  tree* parent,
           child1,
           child2;
};

тоесть каждый элемент имеет связь с предшествующим ему узлом и двумя дочерними.
при построении должно соблюдаться следующее правило:
Код

*child1 <= *parent <= *child2 
*child1 != child2

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

Автор: madbizarre 16.12.2010, 16:03
Да это то понятно я литературу читал. Меня интересует пересечение, разность, обьядинение. Как реализовать? Это множества? Или в деревьях как то иначе

Автор: Чoо 16.12.2010, 16:42
Цитата(madbizarre @  16.12.2010,  16:03 Найти цитируемый пост)
Меня интересует пересечение, разность, обьядинение. Как реализовать? Это множества? 

не знаю

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)