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
    27 сен 2011 в 18:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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