0

Есть такое условие:

Разработать программу для задачи - сформировать однонаправленный список из вводимой строки. В поле каждого элемента списка записать отдельный символ. Если первый символ - буква "А", то в конец списка добавить еще одну букву "А", иначе из списка исключить все буквы "А". Вывести полученный результат.

С первым условием я справился и добавил еще одну букву в конец списка, а вот со вторым никак не могу. Мой код:

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

Понимаю, что делать так сразу нельзя: delete pv. Но я просто не знаю, как решить эту задачу. Буду очень благодарен за помощь.

2
  • Удаляются так 1. Найти предыдущий елемент от заданого, 2. связать предыдущий елемент с следующим от заданого. Тогда цепочка будет без нарушений в памяти. Плюс ньюансы при нахождении заданого елемента в начале/конце списка.
    – nick_n_a
    24 ноя 2016 в 6:51
  • @Денис Покажите, как вы определили сам список. 24 ноя 2016 в 11:16

4 ответа 4

2

Примерно так (не компилировал, так что огрехи могут быть; главное - сам принцип)...

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

}
1

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

Ниже приведена демонстрационная программа, которая показана, как такой список может быть реализован

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

Вывод программы на консоль может выглядеть следующим образом

A B C 
A B C A 
B A A A C A 
B C 
0

если можно использовать контейнеры из STL, а не придумывать свою реализацию списка, то можно как-то так:

#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;
}
0

У меня получилось немножко по другому: 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;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.