There is such a condition:

Develop a program for the task - to form a unidirectional list of the input string. In the field of each element of the list, write a separate symbol. If the first character is the letter “A”, then add one more letter “A” to the end of the list, otherwise, delete all the letters “A” from the list. Print the result.

I coped with the first condition and added another letter to the end of the list, but I can’t with the second one. My code is:

Node *pv = new Node; char b; pv = head; if (pv->item != 'A') { while (pv->next != NULL) { if (pv->item == 'A') { delete pv; } pv = pv->next; } }

I understand that you can not do it right away: delete pv. But I just do not know how to solve this problem. I would be very grateful for the help.

  • They are deleted as follows 1. Find the previous element from the given one, 2. link the previous element to the next element from the specified one. Then the chain will be without disturbances in the memory. Plus nuances when finding a given element at the beginning / end of the list. - nick_n_a Nov.
  • @ Denis Show me how you determined the list itself. - Vlad from Moscow

4 answers 4

Something like this (not compiled, so there may be flaws; the main thing is the principle itself) ...

 pv = head; if (pv->item != 'A') { // Если первый - не А, исключить все А while (pv->next != NULL) { while (pv->next && pv->next->item == 'A') // Пока следующий А, { Node * tmp = pv->next; // Убираем его pv->next = pv->next->next; delete tmp; } if (pv->next) pv = pv->next; // Если не последний - цикл продолжаем } } else // Первый А, так что добавить еще оди А в конец { while (pv->next) pv = pv->next; // Выход на последний Node * tmp = new Node; tmp->next = 0; tmp->item = 'A'; pv->next = tmp; } }

    If you need to insert an element at the end of the list, then such a simply linked list is best done two-way.

    Below is a demo program that shows how such a list can be implemented.

     #include <iostream> #include <string> class List { private: struct Node { char item; Node *next; }; Node *head; Node *tail; private: void delete_all() { while ( head ) { Node *tmp = head; head = head->next; delete tmp; } tail = head; } void copy_all( const Node *src_head ) { for ( ; src_head; src_head = src_head->next ) { push_back( src_head->item ); } } std::ostream & out( std::ostream &os = std::cout ) const { for ( Node *current = head; current; current = current->next ) { os << current->item << ' '; } return os; } public: // constructors List() : head( nullptr ), tail( nullptr ) { } List( const std::string &s ) : List() { for ( char c : s ) { push_back( c ); } } List( const List &lst ) : List() { copy_all( lst.head ); } // destructor ~List() { delete_all(); } // copy assignment operator List & operator =( const List &lst ) { if ( this != &lst ) { delete_all(); copy_all( lst.head ); } return *this; } // methods void push_fron( char c ) { head = new Node { c, head }; if ( tail == nullptr ) tail = head; } void push_back( char c ) { if ( tail == nullptr ) { tail = new Node { c, nullptr }; head = tail; } else { tail->next = new Node { c, nullptr }; tail = tail->next; } } void remove( char c ) { for ( Node **current = &head; *current; ) { if( ( *current )->item == c ) { Node *tmp = *current; *current = ( *current )->next; delete tmp; if ( *current == nullptr ) tail = nullptr; } else if ( ( *current )->next && ( *current )->next->item == c ) { if ( tail == ( *current )->next ) tail = *current; Node *tmp = ( *current )->next; ( *current )->next = tmp->next; delete tmp; } else { current = &( *current )->next; } } } char front() const { return head->item; } char & front() { return head->item; } char back() const { return tail->item; } char back() { return tail->item; } bool empty() const { return head == nullptr; } friend std::ostream & operator <<( std::ostream &os, const List &lst ); }; std::ostream & operator <<( std::ostream &os, const List &lst ) { return lst.out( os ); } int main() { List lst1( "ABC" ); std::cout << lst1 << std::endl; if ( lst1.front() == 'A' ) lst1.push_back( 'A' ); std::cout << lst1 << std::endl; List lst2( "BAAACA" ); std::cout << lst2 << std::endl; if ( lst2.front() != 'A' ) lst2.remove( 'A' ); std::cout << lst2 << std::endl; }

    The output of the program to the console may look as follows.

     ABCABCABAAACABC

      if you can use containers from STL, and not invent your own implementation of the list, then you can somehow do this:

       #include <iostream> #include <list> int main() { std::list<char> l; char c, cmp_char = 'A'; while ((c = std::cin.get()) != 'EOF') { l.push_back(c); } if (l.front() == cmp_char) { l.push_back(cmp_char); } else { l.remove(cmp_char); } for (std::list<char>::const_iterator it = l.begin(); it != l.end(); ++it) { std::cout << *it; } return 0; }

        I got a little bit different: http://ideone.com/E1cpcz

         #include <iostream> struct Node { char key; Node *next; }; // ---------------------------------------------------------- // Инициализация односвязанного списка из строки // ---------------------------------------------------------- Node* FuncInit(const std::string &iStr) { Node* Res = nullptr; Node* Cur = nullptr; for (const auto &i:iStr) { Node* Tmp = new Node({i,nullptr}); if (Res) Cur->next = Tmp; else Res = Tmp; Cur = Tmp; } return Res; } // ---------------------------------------------------------- // Разрушение односвязанного списка // ---------------------------------------------------------- void FuncDestroy(Node* &iTop) { if (iTop) { Node *Tmp = iTop->next; FuncDestroy(Tmp); delete iTop; } iTop = nullptr; } // ---------------------------------------------------------- // Вставка символа в конец односвязанного списка // ---------------------------------------------------------- void FuncBackInsert(Node* &iTop, const char iChar) { Node* Res = iTop; Node* Tmp = new Node({iChar,nullptr}); while(iTop && iTop->next) iTop=iTop->next; if (iTop) iTop->next = Tmp; else Res = Tmp; iTop = Res; } // ---------------------------------------------------------- // Удаление найденного символа из односвязанного списка // ---------------------------------------------------------- void FuncRemoveChar(Node* &iTop, const char iChar) { Node *Res = nullptr; Node *Prev = iTop; while(iTop) { if (iTop->key == iChar) { Prev->next = iTop->next; delete iTop; iTop = Prev; } else { if (!Res) Res = iTop; Prev = iTop; iTop = iTop->next; } } iTop = Res; } // ---------------------------------------------------------- // Печать односвязанного списка // ---------------------------------------------------------- void FuncPrint(Node* iTop) { while (iTop) { std::cout << iTop->key; iTop=iTop->next; } std::cout << std::endl; } int main() { Node *Chain = FuncInit("MAMA MILA RAMU"); // инициализируем FuncPrint(Chain); // печатаем FuncBackInsert(Chain,'!'); // вставляем символ '!' FuncPrint(Chain); // печатаем FuncRemoveChar(Chain,'A'); // удаляем все вхождения 'A' FuncPrint(Chain); // печатаем FuncDestroy(Chain); // разрушаем оставшуюся структуру return 0; }