Разбор задач (Rezolvarea problemelor)

Задача №1. Постановка задачи

Для демонстрации реализации работы с динамическим списком, решим задачу:

"В текстовом файле находятся идентификаторы переменных и их числовые значения (например: x 15 abc 12.098 z -1.23). Перенести их в динамический список, для которого реализовать следующие операции: поиск идентификатора в списке; изменение значения указанного идентификатора; удаление идентификатора из списка, добавление в список нового идентификатора с заданным значением. По окончании сеанса работы список идентификаторов и их значений переносится обратно в файл"

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

Решение:

Стандартное начало.

Приступим к решению. Создаем консольный проект, и пишем довольно стандартный код - организовываем файловый ввод. Для чтения из файла используем метод getline(), где в качестве третьего параметра указываем пробел, являющийся разделителем в нашем файле.

#include <fstream>

#include <iostream>

#include <cstdlib>

//TODO: Описание списка

//TODO: Операции со списком

using namespace std;

int main()

{

       char* fileName = new char[50];

       char* buf_name = new char[20];

       char* buf_value = new char [10];

      

       cout << "Enter name of file -> ";

       cin >> fileName;

       ifstream* inp = new ifstream(fileName);

       if (!inp->good())

       {

                cout << "File opening error!\n";

                system("PAUSE");

                return 0;

       }

       while (!inp->eof())

       {

                inp->getline(buf_name, 20, ' ');

                inp->getline(buf_value, 10, ' ');

Кажется, тут все ясно и ничего не требует особого внимания. В первом разделе TODO мы опишем типы, необходимые для работы со списком, во втором у нас будут функции для работы с ним. Теперь приступим непосредственно к описанию списка, т.к. в программе мы уже вплотную подошли к его заполнению.

3.2. Описание динамического списка

Для начала, вспомним (или впервые узнаем)), что динамический список представляет из себя некоторое количество компонентов (узлов), содержащих непосредственно информационную часть (число, строка или более сложные типы данных), а также ссылку на следующий компонент (возможно, что узел содержит 2 ссылки: на следующий и на предыдущий, в таком случае, список называется двусвязным). Таким образом, получаем следующую структуру, описывающую компонент списка для нашей задачи:

 struct comp {

                char name[20]; // Имя переменной

                char value[10]; // Значение переменной

                comp* next; //Ссылка на следущий элемент списка

};

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

 struct dyn_list {

                comp* head; // Первый элемент (голова) списка

                comp* tail; // Последний элемент (хвост) списка

       };

Несложно понять, что значит создать пустой список. Фактически делать ничего не нужно, разве что присвоить ссылке на первый элемент списка (head) значение NULL. Оформим это как функцию, параллельно создав еще одну, проверяющую по этому условию, пуст ли список.

 // Создание пустого списка

void constr_list(dyn_list &l)

{

       l.head = NULL;

}

// Проверка списка на пустоту

bool chk_empty(dyn_list l)

{

       return (l.head==NULL);

}

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

 dyn_list vars; // Динамический список

constr_list(vars);

Операции с компонентами списка

Ну, перед тем, как проводить какие-то операции с компонентами, их необходимо добавить в список, чем мы сейчас и займемся. Прежде всего, нам необходимо создать новый компонент и заполнить его информационную часть. Так как мы будем помещать его в конец списка, то ссылочная часть узла будет иметь значение NULL. Теперь давайте поймем, что должно происходить со ссылками head и tail при этой операции. Здесь рассматриваются 2 случая - наш список пуст или в нем есть хотя бы один компонент. Если пуст, то и head и tail будут указывать на только что созданный компонент. Если же узлы в списке присутствуют, очевидно, что сначала нужно последний узел связать с добавляемым (для этого ссылочной части компонента, на который указывает tail, присвоить адрес того, который хотим добавить), а затем "передвинуть" tail. Вот как просто все это выглядит на С++:

 // Включение в список нового компонента

void comp_in(dyn_list &l, char* n, char* v)

{

       comp* c = new comp();

       strcpy_s(c->name, 20, n);

       strcpy_s(c->value, 10, v);

       c->next = NULL;

       if (chk_empty(l))

                l.head = c;

       else

                l.tail->next = c;

       l.tail = c;

}

Теперь займемся поиском компонента. Искать будет по имени переменной, по желанию вы можете искать и по значению. В качестве аргументов, функции поиска передаем сам список и искомый текст. Возвращать наша функция будет адрес найденного узла или NULL, если ничего не найдено. Искать начнем с компонента, на который указывает head и, двигаясь вперед, сравнивать имя текущей переменной с искомым. В функции поиска мы можем не боясь, передвигать ссылку head, так как передаем ее не по ссылке.

 // Поиск компонента в списке по имени

comp* search(dyn_list l, char *n)

{

       while (l.head != NULL)

       {

                if (!strcmp(l.head->name,n))

                         return l.head;

                l.head = l.head->next;

       }

       return l.head;

}

А сейчас удалим компонент. В качестве аргумента, передаем по ссылке список, а также ссылку на компонент, который собираемся удалить. В самой же функции рассматриваем 2 случая. Первый случай простой: если компонент является первым (то есть на него указывает head), то достаточно лишь переместить ссылку на первый элемент вперед. В противном случае, нам понадобится рабочая переменная-узел, которую мы будем использовать для движения по списку. Двигаться будем до тех пор, пока следующий за текущим узел не будет тем, который мы собираемся удалить. Ну а после этого, "перепрыгиваем" удаляемый компонент, присваивая ссылочной части предшествующего удаляемому компоненту адрес следующего за удаляемым. Все эти слова умещаются буквально в несколько строк исходного кода:

 // Удаление компонента из списка

void comp_del(dyn_list &l, comp* c)

{

       if (c == l.head)

       {

                l.head = c->next;

                return;

       }

       comp* r = new comp();

       r = l.head;

       while (r->next != c)

                r = r->next;

       r->next = c->next;

       delete c;

}

Последняя и самая простая операция - это изменение значения информационной части узла. Менять будем поле value. В качестве параметров, по ссылке передадим адрес компонента, а также новое значение изменяемого поля. Ну и в одну строчку все изменим. Вот как просто это выглядит:

 // Изменение значения компонента

void comp_edit(comp &c, char* v)

{

       strcpy_s(c.value, 10, v);

}

С операциями закончили, теперь осталось дописать программу.

Тестируем функции и завершаем программу

Ну, тут все просто, в цикле нам осталось лишь обратиться к функции добавления компонента в список. После цикла, тестируем остальные наши функции и выводим весь список в файл. Привожу здесь весь код функции main()

 int main()

{

       char* fileName = new char[50];

       char* buf_name = new char[20];

       char* buf_value = new char [10];

       dyn_list vars; // Динамический список

       cout << "Enter name of file -> ";

       cin >> fileName;

       ifstream* inp = new ifstream(fileName);

       if (!inp->good())

       {

                cout << "File opening error!\n";

                system("PAUSE");

                return 0;

       }

       constr_list(vars);

       while (!inp->eof())

       {

                inp->getline(buf_name, 20, ' ');

                inp->getline(buf_value, 10, ' ');

                comp_in(vars, buf_name, buf_value);

       }

       inp->close();

       comp* p = new comp();

       p = search(vars, "z");

       if (p)

                comp_del(vars, p);

       p = search(vars, "abc");

       if (p)

                comp_edit(*p, "2");

       ofstream* out = new ofstream(fileName);

       while (vars.head != NULL)

       {

                out->write(vars.head->name, strlen(vars.head->name));

                out->write(" ",1);

                out->write(vars.head->value, strlen(vars.head->value));

                out->write(" ",1);

                vars.head = vars.head->next;

       }

       out->close();

       system("PAUSE");

       return 0;

}

Задача решена :

Выводы

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

В любом случае, использовать связанные списки в своих программах или нет, придется решать вам, надеюсь, моя статья хоть немного поможет вам в этом. Спасибо за внимание.

Задача №2: Дан текстовый файл размером не более 64 Кб, содержащий действительные числа, по одному в каждой строке. Переписать содержимое файла в массив, разместив его в динамически распределяемой памяти. Вычислить среднее значение элементов массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от –100 до 100 и вычислить его среднее значение.

#include < stdio.h >
#include < time.h >
#include < stdlib.h >
#include < iostream.h >
#define NMax 10000
typedef int MasInt;
typedef float MasReal;
MasInt *PInt; MasReal *PReal;
int I, n, MidInt; float MidReal; char S[255];
FILE *t; char *endptr;
void main()
{     cout << "Введите имя файла: "; cin >> S;
      t=fopen(S, "r");
      MidReal = 0; MidInt = 0;
      randomize(); I=0;
      /*Выделение памяти под вещественный массив*/
      PReal = (MasReal*) malloc (sizeof(MasReal));
      /*Ввод и суммирование вещественного массива*/
      while (!feof(t))
       {fgets(S, 255, t); // вводим из файла строку
        PReal[I] = strtod(S, &endptr); // преобразуем введенную строку в вещественное число
 MidReal += PReal[I]; I++;}
      n=I+1;
      free (PReal); /*Удаление вещественного массива*/
      PInt = (MasInt*) malloc(sizeof(MasInt)); /*Выделение памяти под целый массив*/
      /* Вычисление и суммирование целого массива */
      for (I=0; I < NMax; I++)
       { PInt[I] = -100 + random(201);
  MidInt += PInt[I];}
      /*Вывод средних значений*/
      cout << "\nсреднее целое равно " << MidInt / double(NMax) << "\n";
      cout << "среднее вещественное равно: " << MidReal / n << "\n";
      fclose(t);
}

Задача №3. Составить программу, которая на основе заданного списка формирует два других, помещая в первый из них положительные, а во второй — отрицательные элементы исходного списка.

При реализации алгоритма будем использовать подпрограммы разработанного модуля. Это существенно облегчает решение задачи.




#include "SPIS.CPP"
void main()
{Zveno *S1, *S2, *S3, *V1, *V2, *V3;
 BT a; int i, n;
 clrscr();
 randomize();
 S1=NULL;
 // создаём первый элемент
 a=-100+random(201);
 S1=V_Nachalo(S1, a);
 n=1+random(20);
 // формируем список произвольной длины и выводим на печать
 V1=S1;
 for (i=2; i<=n; i++)
 {
    a=-100+random(201);
    V1=V_Spisok(V1, a);
 }
 Print(S1);
 V1 = S1;  S2 = NULL; S3 = NULL;
    while (V1)
 {if (V1->Inf > 0)
       if (!S2)
   {S2=V_Nachalo(S2, V1->Inf); V2 = S2;}
       else {V_Spisok(V2, V1->Inf); V2 = V2->Next;};
  if (V1->Inf < 0)
      if (!S3)
  {S3=V_Nachalo(S3, V1->Inf); V3 = S3;}
      else {V_Spisok(V3, V1->Inf); V3 = V3->Next;};
  V1= V1->Next;}
  cout << "Результирующий список из положительных элементов: \n";
  Print(S2);
  cout << "Результирующий список из отрицательных элементов: \n";
  Print(S3);
  S1=Ochistka(S1); S2=Ochistka(S2); S3=Ochistka(S3);
}