Версия для печати темы

Автор: 18192123 29.04.2007 0:57

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

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

Автор: volvo 29.04.2007 1:00

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

Автор: 18192123 1.05.2007 20:24

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

Автор: volvo 1.05.2007 20:30

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

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

Автор: 18192123 1.05.2007 21:26

Цитата(volvo @ 1.05.2007 17:30)

Автор: volvo 1.05.2007 21:46

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

Автор: 18192123 1.05.2007 21:49

Цитата(volvo @ 1.05.2007 18:46)

Автор: 18192123 1.05.2007 23:19

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

#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 2.05.2007 0:48

#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 2.05.2007 1:56

Цитата(volvo @ 1.05.2007 21:48)

    strcpy(p -> number, s);

    

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

Автор: volvo 2.05.2007 2:20

Автор: 18192123 2.05.2007 14:17

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

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

Автор: volvo 2.05.2007 15:35

Автор: 18192123 2.05.2007 17:25

Цитата(volvo @ 2.05.2007 12:35)

Автор: volvo 2.05.2007 18:43

Будет гораздо проще сделать наоборот: отсортировать слова по возрастанию длины, а потом удалить 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 9.05.2007 1:33

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

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


Прикрепленные файлы
 Новый_рисунок__2_.bmp ( 75.76 килобайт ) Кол-во скачиваний: 580

Автор: volvo 9.05.2007 1:47

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

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


Эскизы прикрепленных изображений

Автор: 18192123 9.05.2007 1:56

Цитата(volvo @ 8.05.2007 22:47)

Автор: volvo 9.05.2007 2:24

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

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

Автор: 18192123 9.05.2007 3:37

Цитата(volvo @ 8.05.2007 23:24)

Автор: 18192123 9.05.2007 15:02

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

Автор: volvo 9.05.2007 15:27

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

Но это делай сама, я ЭТО делать не буду.

Автор: 18192123 9.05.2007 19:55

Я хочу добиться того, чтобы после удаления 5 элементов (остальные элементы расположены в порядке возрастания их длины), оставшиеся элементы были расположены в обратном порядке (т.е. в порядке убывания длины).
Как это будет выглядеть?
И куда в этом случае привязать проверку на наличие пяти самых коротких строк?

И ещё такой вопрос:
void sort(LIST **first) - почему мы в эту ф-ю передаём указатель на указатель на голову списка?

Автор: 18192123 9.05.2007 23:19

Цитата(18192123 @ 9.05.2007 16:55)

Автор: volvo 9.05.2007 23:56

Автор: 18192123 10.05.2007 2:21

объясните пожалуйста некоторые моменты:
1) о сортировке

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

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

sort(&root);

 for(p = root; p; p = p -> next)
    printf("%s\n", p -> number);

for(p = root; p && n < 5; n++) 

for(p = root; p; )

Автор: volvo 10.05.2007 3:23

Давай по порядку:

1) организацию циклов в С знаешь? Я имею в виду, синтаксис оператора цикла?
for(начальное_присвоение;условие_окончания;и
зменение_на_каждой_итерации) {
собственно_операторы_тела_цикла;
}

где
начальное_присвоение - делается один раз перед началом цикла;
условие_окончания - проверяется после завершения каждой итерации
изменение_на_каждой_итерации - делается после завершения итерации ПЕРЕД проверкой условия_окончания

причем любой (!!!) из этих параметров может отсутствовать (моогут, кстати, отсутствовать и 2 и все 3 - тогда цикл будет "вечным", и выходе из него возможен будет только через break)...

А теперь с учетом этого - смотри, что происходит:

/*
  ВНЕШНИЙ цикл

  Поскольку first передается как указатель на указатель
  (причину я объяснял выше), то L присваиваем значению
  разыменованного first (т.е. изначально L = указателю на
  голову списка)

  Условие окончания внешнего цикла - (L->next) подразумевает НЕравенство
  этого значения нулю... То есть, как только значение L->next станет NULL, цикл завершится...

  После обработки одной итерации продвигаемся по списку, путем L = L -> next
*/
for(L = *first; L -> next; L = L -> next)

    /*
    ВНУТРЕННИЙ цикл
    изначально p = L -> next
    условие окончания: закончится цикл - когда p будет нулевым
    продвижение - понятно как осуществляется...
    */
    for(p = L -> next; p; p = p -> next)

 /*
   изначально p = root
   окончание - когда p = NULL
   продвижение - p = p -> next
 */
 for(p = root; p; p = p -> next)
    printf("%s\n", p -> number);

  for(p = root; p; ) {
    printf("%s\n", p -> number);
    p = (T = p) -> next; /* <--- вот эту строку ты разобрала, как она работает? */
    free(T);
  }

Автор: 18192123 10.05.2007 4:06

volvo, большое спасибо! теперь всё поняла!

Автор: 18192123 14.05.2007 22:13

Возник ещё вопрос:

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);
      }
    }

Автор: volvo 15.05.2007 2:52

Можно, только код будет больше по размеру... Не забывай, у тебя односвязные списки, то есть, для того, чтобы пройти к предыдущему (менять-то указатель с предыдущего на новое значение надо?) тебе придется пробегать еще раз по списку с самого начала...

Автор: 18192123 15.05.2007 3:05

Цитата(volvo @ 14.05.2007 23:52)

Автор: 18192123 15.05.2007 18:34

Цитата(18192123 @ 14.05.2007 19:13)

Автор: volvo 15.05.2007 20:11

Ты сама просила

void sort(LIST **first) {

  LIST *L, *p, *pp, *T, *prv_L, *prv_p;
  char s[255];

  start_over:
  ;

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

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

      if(strlen(L -> number) > strlen(p -> number)) {

        // Вот тут раньше было 3 строки... Смотри теперь.

        if(L == *first) {

          for(pp = *first; pp -> next != p; pp = pp -> next);
          pp -> next = *first;

          T = (*first) -> next;
          *first = p;

          L -> next = p -> next;
          p -> next = T;

        }
        else {
          LIST *prv_L, *prv_p;
          for(prv_L = *first; prv_L -> next != L; prv_L = prv_L -> next);
          for(prv_p = *first; prv_p -> next != p; prv_p = prv_p -> next);

          prv_L -> next = p;
          prv_p -> next = L;
          T = p -> next;
          p -> next = L -> next;
          L -> next = T;
        }

        goto start_over;
      }
    }

}

Автор: 18192123 15.05.2007 21:58

Цитата(volvo @ 15.05.2007 17:11)

Ты сама просила

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

typedef struct list {

  char number[255];
  struct list *next;

} LIST;

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

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

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

    fgets(s,255, f);
    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 *p1=first, *p2=p1->next, *prev,*temp1, *temp2;
  int flag=1;
  while (flag&&p2)
  {
    flag=0;
    prev=first;
    while (p2)
    {

      if (strlen(p1->number)>strlen(p2->number))
	{
	  flag=1;
	  temp1=p1;
	  temp2=p2->next;
	  p1=p2;
	  p2=temp1;
	  p1->next=p2;
	  p2->next=temp2;
	  if (temp1==first) first=p1; else prev->next=p1;
	}
      prev=p1;
      p1=p1->next;
      p2=p2->next;
    }
    p1=first; p2=p1->next;
  }
}

void *sort1(LIST *first)
{
  LIST *p1=first, *p2=p1->next, *prev,*temp1, *temp2;
  int flag=1;
  while (flag&&p2)
  {
    flag=0;
    prev=first;
    while (p2)
    {

      if (strlen(p1->number) < strlen(p2->number))
	{
	  flag=1;
	  temp1=p1;
	  temp2=p2->next;
	  p1=p2;
	  p2=temp1;
	  p1->next=p2;
	  p2->next=temp2;
	  if (temp1==first) first=p1; else prev->next=p1;
	}
      prev=p1;
      p1=p1->next;
      p2=p2->next;
    }
    p1=first; p2=p1->next;
  }
}







void main() {
  struct list *root, *p, *T;
  int n;
  FILE *f;
  f=fopen("RGZ2.txt","w");

  root = read_list();


   sort1(root);

  for(p = root; p; p = p -> next)
    fprintf(f,"%s\n", p -> number);
    fprintf(f,"\n---\n");
  sort(root);

  n = 0;
  for(p = root; p && n < 5; n++) {

    p = (T = p) -> next;
    free(T);
  }

  root = p;
  sort1(root);


  for(p = root; p; ) {
  fprintf(f,"%s\n", p -> number);
    p = (T = p) -> next;
    free(T);
  }
  root = NULL; fprintf(f,"\n--------\n");

}

Автор: volvo 15.05.2007 22:22

Сорри, я больше в эту тему НЕ отвечаю! Я тебе привел работающую функцию сортировки, на отладку которой ушло больше 2-х часов, ты ее полностью перековеркала, и теперь тебя не устраивает результат?

Извини, но функции твои, вот и разбирайся, как они работают сама (а они НЕ работают, чтобы в этом убедиться достаточно вывести на экран содержимое списка ПЕРЕД первой сортировкой, и ПОСЛЕ нее)...

Автор: 18192123 15.05.2007 22:43

Цитата(volvo @ 15.05.2007 17:11)

          LIST *prv_L, *prv_p;
          for(prv_L = *first; prv_L -> next != L; prv_L = prv_L -> next);
          for(prv_p = *first; prv_p -> next != p; prv_p = prv_p -> next);