0

Здравствуйте. Мне нужно описать функцию, которая, в списке из каждой группы подряд идущих одинаковых элементов, составляет только один элемент. Я не понимаю, как написать функцию даже для удаления просто одного конкретного элемента. Пока написал все остальное.

    struct list
{
    int info;
    list *next;
};

void New(list* &head, list* &tail)
{   int c;
    scanf("%d",&c);
    head=new list;
    head->info=c;
    head->next=NULL;
    tail=head;
}

void Add(list* &tail)
{   int c;
    list *T;
    scanf("%d",&c); 
    T=new list;

    T->info=c;
    T->next=NULL;
    tail->next=T;
    tail=T;         
 }
void Delete()

void Print(list *head, list *tail)
{
    list *T;

    T=new list;
    T=head;
    while (T!=NULL)
    {
        printf("%d ",T->info);
        T=T->next;
    }

}

void main()
{
    list *head, *tail;
    int i, n,a;
    printf("\nEnter number of elements: ");
    scanf("%d",&n);
    New(head,tail);
    for (i=1;i<=n-1;i++)
    {  
    Add(tail);}
    printf("Your list: ");
    Print(head,tail);
    Delete();
    printf("Your new list: ");
    Print(head,tail);

    getch();
}

Помогите разобраться в алгоритме построения функции удаления на каком-нибудь примере (можно даже на моем:) с подробными комментариями.

0

2 ответа 2

6

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

  1. node->data = node->next->data - копируем данные из следующего элемента.
  2. temp = node->next - запоминаем следующий элемент.
  3. node->next = node->next->next - переносим ссылку на элемент следующий за следующим.
  4. free(temp) - освобождаем память бывшего следующего элемента.
3

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

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

struct el {
  int info;
  struct el *next;
};

static void
fatal(char *txt)
{
  perror(txt);
  exit(1);
}

static struct el *
Add_new (struct el *elem, FILE *in)
{
  int  data = 0;
  for (;;) {
    printf ("Enter number: "); fflush(stdout);
    if (fscanf(in,"%d",&data) == 1)
      break;
    if (feof(in))
      return NULL;
    if (ferror(in))
      fatal("input");
    char buf[1024];
    fgets(buf,1024,in);
    if (buf[0] == '.')
      return NULL;
    printf ("Some error. Again ");
  }
  struct el *el = malloc(sizeof(*el));
  el->info = data;
  el->next = NULL;
  if (elem)
    elem->next = el;
  return el;
}

void
Pri_list (char *title,struct el *list)
{
  puts(title);
  while (list) {
    printf ("%d\n",list->info);
    list = list->next;
  }
}

struct el *
Get_seq (struct el * elem)
{
  if (elem) {
    int  info = elem->info;
    while (elem->next && elem->next->info == info)
      elem = elem->next;
  }
  return elem;
}

void
Del_list (struct el *elem)
{
  while (elem) {
    struct el *p = elem->next;
    free(elem);
    elem = p;
  }
}

main ()
{
  struct el *list, *elem;

  if (list = elem = Add_new(NULL,stdin))
    while(elem = Add_new(elem,stdin));

  Pri_list("",list);

  struct el *last;
  for (elem = list;last = Get_seq(elem);elem = elem->next) {
    if (elem != last) {
      struct el *p = elem->next;
      elem->next = last->next;
      last->next = NULL;
      Del_list(p);
    }
  }

  Pri_list("Result",list);
  exit(0);
}

Некоторые пояснения по коду. Конец списка определяем по next == NULL.

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

Pri_list() пробегает по списку и печатает кждый элемент в новой строке.

Del_list() удаляет элементы списка от заданного до конца (освобождает память).

Get_seq() возвращает адрес элемента данных в последовательности элементов с одинаковыми info, начиная с заданного. Возвращает последний адрес последнего элемента в такой цепочке. Если за заданным (ее аргумент) элементом следует элемент с другим info, то возвращает свой аргумент (цепочка из одного звена).

Прикладная логика в main() (и Get_seq()). Читаем список со стандартного ввода, печатаем его.

В цикле for(;;) идем по цепочкам элементов с одинаковым info. Такую цепочку выделяет Get_seq(). Если она длиннее одного элемента, то вырезаем из списка все элементы цепочки, кроме первого (меняя указатель next первого элемента цепочки на next последнего в цепочке). Для удаления из памяти хвоста цепочки обнуляем next ее последнего элемента и вызываем Del_list() со вторым элементом цепочки.

Печатаем результат. (Вроде работает).

UPD Добавил конкретно для удаления элементов списка по заданному значению элемента. Вас ведь интересовало, как удалить элемент ?

struct el *
Del_info (struct el *list, int info, int *cnt, int *done)
{
  *done = 0;
  struct el *p = list, *prev = NULL;

  while (list) {
    if (*cnt < 1)
      break;
    if (list->info == info) {
      if (prev) {
        prev->next = list->next;
        free(list);
        (*done)++;
        (*cnt)--;
        list = prev->next;
      } else {
        p = list->next;
        free(list);
        (*done)++;
        (*cnt)--;
        list = p;
      }
    } else {
      prev = list;
      list = list->next;
    }
  }
  return p;
}

Удаляет из списка до cnt элементов с заданным значением. Количество удаленных возвращает в параметре done. Возвращает указатель на новый первый элемент списка (предыдущий первый может быть удален).

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

1
  • извините , что не спрашивал. вообще не было времени. щас примусь разбирать.
    – Dexter384
    Commented 27 сент. 2011 в 18:15

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.