Односвязные линейные списки, Си Опции

[18192123]

Дан текстовый файл. Строки этого файла расположить в порядке убывания их длины и удалить пять самых коротких из них.
Для размещения в памяти содержимого файлов использовать односвязные линейные списки.

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

Сообщение отредактировано: 18192123 - 28.04.2007 20:57

[volvo]

После прочтения строки из файла, проверяй ее длину (strlen) и выделяй под информационное поле в списке на 1 байт больше (для хранения завершающего '\0')

[18192123]

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

Сообщение отредактировано: 18192123 - 1.05.2007 16:25

[volvo]

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

Скорее всего, второй? Тогда я уже выкладывал где-то переведенную на Паскаль рекурсивную функцию сортировки списка вставками (из книги Sedgewick-а "Fundamental C++"), если надо - выложу оригинал на С ...

Сообщение отредактировано: volvo - 1.05.2007 16:30

[18192123]

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

Скорее всего, второй? Тогда я уже выкладывал где-то переведенную на Паскаль рекурсивную функцию сортировки списка вставками (из книги Sedgewick-а "Fundamental C++"), если надо - выложу оригинал на С ...

да, второй. только это не должна быть рекурсивная ф-я....

[volvo]

Ну, тогда тебе и карты в руки... Опять изобретение велосипеда? Что же за преподаватели-то такие? Они же просто угробят все, что только можно!!! С одной стороны они ограничили тебя односвязным списком, то есть, у тебя только последовательный проход по списку (про сотню проходов по списку из 100 элементов я не говорю - это вообще полный бред), а с другой стороны - те методы, которые эффективны при последовательном доступе (в частности - mergesort) - они рекурсивные... А рекурсия запрещена. Замкнутый круг...

[18192123]

Ну, тогда тебе и карты в руки... Опять изобретение велосипеда? Что же за преподаватели-то такие? Они же просто угробят все, что только можно!!! С одной стороны они ограничили тебя односвязным списком, то есть, у тебя только последовательный проход по списку (про сотню проходов по списку из 100 элементов я не говорю - это вообще полный бред), а с другой стороны - те методы, которые эффективны при последовательном доступе (в частности - mergesort) - они рекурсивные... А рекурсия запрещена. Замкнутый круг...

ээээ...и как быть?

[18192123]

попыталась написать ф-ю, которая формирует список (ф-я возвращает указатель на голову списка).
но насчёт занесения строки в информационное поле элемента списка - ???

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>
typedef struct list {
char number[50];
struct list *next;
} LIST;

LIST *read_list(LIST *lst)
{
  LIST *p;
  FILE *f;
  f=fopen("rg.txt","r");
  if (!feof(f))
  {
    lst=(LIST *)malloc(sizeof(LIST));
    p=lst;
    while (1)
    {
      fscanf(f,"%s",p->number[50]);
      if (!feof(f))
      {
	p->next=(LIST *)malloc(sizeof(LIST));
	p=p->next;
      } else break;
    }
    p->next=NULL;
  }
  else printf("Файл пустой\n");
  fclose(f);
  return lst;
}

[volvo]

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>

typedef struct list {

  char number[50];
  struct list *next;

} LIST;

LIST *read_list() {
  char s[255];

  LIST *p, *lst, *final;
  FILE *f;
  f=fopen("rg.txt","r");

  lst = NULL;
  while(!feof(f)) {

    fscanf(f, "%s", s);
    p = (LIST*)malloc(sizeof(list));
    strcpy(p -> number, s);

    if(!lst) lst = p;
    else final -> next = p;

    final = p;

  }
  fclose(f);

  if(!lst) {
    printf("empty file\n");
    return NULL;
  }
  final -> next = NULL;

  return lst;
}

void sort(LIST **first) {

  LIST *L, *p;
  char s[255];

  for(L = *first; L -> next; L = L -> next)

    for(p = L -> next; p; p = p -> next) {

      if(strcmp(L -> number, p -> number) > 0) {
        strcpy(s, L -> number);
        strcpy(L -> number, p -> number);
        strcpy(p -> number, s);
      }
    }

}


int main() {
  struct list *p;
  p = read_list();
  sort(&p);
  for(; p; p = p -> next)
    printf("%s\n", p -> number);

  return 0;
}

Так работает?

[18192123]

    strcpy(p -> number, s);

    

да, работает!
А что значит эта строка?

if(!lst) lst = p;
    else final -> next = p;

и что это?

*final - указатель на конец списка, да?

[volvo]

А что значит эта строка?

Эта строка значит следующее: если lst == NULL (или, как я написал, отрицание lst не равно нулю, что одно и то же для С), значит в список пока ничего не было добавлено, в таком случае в lst надо записать значение p, поскольку в данный момент добавляется первый элемент...

А по ветке else - если список уже НЕ пуст, то в указатель next последнего поля надо записывать p, связывая выделенную память с собственно списком...

*final - указатель на конец списка, да?

Именно... Это указатель на тот элемент списка, к которому будет присоединяться новый при добавлении его в конец списка...

[18192123]

А как будет выглядеть удаление 5 нужных элементов? ( тогда это ещё одна ф-я, куда, наверно, нужно передать указатель на голову списка...а что-то кроме этого нужно передавать?)

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

[volvo]

А как будет выглядеть удаление 5 нужных элементов?

А по какому признаку будешь удалять?

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

Нужно... Пробежаться по всему списку, и сделать free для каждого узла списка. Алгоритм - точно такой же, как и в FAQ по Паскалю -> "Все о динамических структурах данных".

[18192123]

А по какому признаку будешь удалять?

удалять 5 самых коротких, т.е. вроде как после сортировки стоящих в конце

[volvo]

Будет гораздо проще сделать наоборот: отсортировать слова по возрастанию длины, а потом удалить 5 первых, поскольку у тебя односвязный список, и работать от "головы" к "хвосту" легче, чем от "хвоста" к "голове"... Смотри:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>

typedef struct list {

  char number[50];
  struct list *next;

} LIST;

LIST *read_list() {
  char s[255];

  LIST *p, *lst, *final;
  FILE *f;
  f=fopen("rg.txt","r");

  lst = NULL;
  while(!feof(f)) {

    fscanf(f, "%s", s);
    p = (LIST*)malloc(sizeof(list));
    strcpy(p -> number, s);

    if(!lst) lst = p;
    else final -> next = p;

    final = p;

  }
  fclose(f);

  if(!lst) {
    printf("empty file\n");
    return NULL;
  }
  final -> next = NULL;

  return lst;
}

void sort(LIST **first) {

  LIST *L, *p;
  char s[255];

  for(L = *first; L -> next; L = L -> next)

    for(p = L -> next; p; p = p -> next) {

      if(strlen(L -> number) > strlen(p -> number)) { /* сортируем по длине */
        strcpy(s, L -> number);
        strcpy(L -> number, p -> number);
        strcpy(p -> number, s);
      }
    }

}


int main() {
  struct list *root, *p, *T;
  int n;

  /* читаем список из файла */
  root = read_list();

  /* сортируем его по возрастанию длин строк */
  sort(&root);
  /* и печатаем ... */
  for(p = root; p; p = p -> next)
    printf("%s\n", p -> number);

  /* теперь удаляем первые 5 элементов */
  n = 0;
  for(p = root; p && n < 5; n++) {

    p = (T = p) -> next;   /* запоминаем текущее P в переменной T, для того чтобы потом удалить */
    free(T);
  }
  /* и устанавливаем новое начало списка */
  root = p;

  /* еще раз проходим, и печатаем весь список, сразу удаляя все узлы, которые уже распечатаны */
  for(p = root; p; ) {
    printf("%s\n", p -> number);
    p = (T = p) -> next;
    free(T);
  }
  root = NULL;
  return 0;
}

Вот и все...

[18192123]

вот такие тестовые данные ввожу в исходный файл:
qwerty
asdf
qwertyu
qwertyqwerty
qwertyuioop
zxcvbnmjhy
qw
q
zxcvfgh

результат в прикреплённом файле.
не пойму, почему строчка zxcvfgh выводится 2 раза?

Сообщение отредактировано: 18192123 - 8.05.2007 21:51

[volvo]

Потому что из списка удаляется всего 5 элементов, а не все элементы, с 5-ю наименьшими длинами...

Добавлено через 3 мин.
А, так он у тебя именно дублируется? Интересно... У меня - нет...

[18192123]

Потому что из списка удаляется всего 5 элементов, а не все элементы, с 5-ю наименьшими длинами...

Добавлено через 3 мин.
А, так он у тебя именно дублируется? Интересно... У меня - нет...

именно дублируется....и при сортировке выводится 2 раза и после удаления 5-ти самых коротких строк тоже 2 раза...

[volvo]

Так... Кажется мне удалось повторить проблему, которая есть у тебя...

Убедись, что после последней строки файла данных НЕТ перевода строки, т.е., последняя строка - НЕ пустая... Если она будет пустой - то получишь то, что ты сказала...

[18192123]

Так... Кажется мне удалось повторить проблему, которая есть у тебя...

Убедись, что после последней строки файла данных НЕТ перевода строки, т.е., последняя строка - НЕ пустая... Если она будет пустой - то получишь то, что ты сказала...

да, действительно. спасибо.