Однонаправленый линейный список

#cpp #алгоритм

Прошу помощи с заданием. Ввести с клавиатуры предложение и переписать его символы
в однонаправленный линейный список.  

С помощью этого списка скопировать в другой однонаправленный список K символов, начиная
с позиции N. Список:

typedef struct list
{ 
    char val;
    struct list *next;
} listn, *listp;

    

Ответы

Ответ 1

В С++ не нужны конструкции вида typedef struct X_ {} X, *PX;, вместо этого используется
обычная struct X {};.
Также в С++ есть конструкторы, поэтому в своем простейшем виде список выглядит так:

struct list {
  explicit list(char val = 0, list* next = nullptr) : val(val), next(next) {}

  char val;
  list* next;
};


У односвязного списка есть две основные операции:
1) добавление элемента в начало

void push_front(list*& list_head, list* new_element) {
  new_element->next = list_head;
  list_head = new_element;
}


2) и удаление элемента из начала списка

list* pop_front(list*& list_head) {
  auto element = list_head;
  if (list_head) list_head = list_head->next;
  if (element) element->next = nullptr;
  return element;
}


При помощи этих операций можно сделать другие полезные операции, а именно:
Чтение списка из потока ввода:

list* read() {
  list* reversed_list_head = nullptr;
  char c;
  while (std::cin >> c)
    push_front(reversed_list_head, new list(c));
  return reversed_list_head;
}


Разворот списка:

void reverse(list*& list_head) {
  list* reversed_list_head = nullptr;
  while (auto element = pop_front(list_head))
    push_front(reversed_list_head, element);
  list_head = reversed_list_head;
}


Печать списка:

std::ostream& operator<<(std::ostream& stream, list* list_head) {
  for (auto element = list_head; element != nullptr; element = element->next)
    stream << element->val;
  return stream;
}


Удаление списка:

void free(list* list_head) {
  while (auto element = pop_front(list_head))
    delete element;
}


При помощи этих функций можно написать программу:

int main() {
  auto list_head = read();
  reverse(list_head);


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

Далее, мы перемещаемся на N символов вперед (или меньше, если список короче):

const auto N = 2;
auto list_middle = list_head;
for (auto i = 0; i != N && list_middle != nullptr; ++i)
  list_middle = list_middle->next;


Затем копируем K элементов в новый список (или меньше, если список короче).
Т.к. мы всегда вставляем элементы в начало, то копия будет перевернутой, и ее надо
будет перевернуть.

const auto K = 3;
list* list_copy = nullptr;
for (auto i = 0; i != K && list_middle != nullptr; ++i) {
  push_front(list_copy, new list(list_middle->val));
  list_middle = list_middle->next;
}
reverse(list_copy);


Выводим копию списка на печать:

std::cout << "list copy: " << list_copy << std::endl;


И наконец удаляем оба списка

free(list_copy);
free(list_head);


Тут можно посмотреть >>>весь код<<<.