1

Тема: Парсинг рядка в зв'язаний список

Потрібно перетворити рядок (наприклад, "1 -> 2 -> 3 -> nullptr") на зв'язаний список.
Це звідси https://www.codewars.com/kata/582c5382f000e535100001a7
Зробив ось так:

class Node {
public:
    int data;
    Node* next;
    Node(int data, Node* next = nullptr)
        : data(data)
        , next(next)
    {
    }
};

Node* parse(const std::string& s)
{
    Node* head { nullptr };
    Node* cur { nullptr };

    stringstream ss;
    ss << s;
    string temp { "" };
    int number;
    while (!ss.eof()) {
        ss >> temp;

        if (stringstream(temp) >> number) {
            if (!head) {
                head = new Node(number);
                cur = head;
            } else {
                cur->next = new Node(number);
                cur = cur->next;
            }
        }

        temp = "";
    }
    cur = cur->next;
    delete cur;
    return head;
}

Але десь протікає, не можу зрозуміти де.
Клас Node — це їхній клас, з яким треба працювати.

2

Re: Парсинг рядка в зв'язаний список

У ванній дивилися? Може, забилося щось?

Будь ласка, замість своїх висновків описуйте те, що ви бачите. Якщо в у вас на столі вода - це один симптом, якщо на підлозі - то інший, якщо є повідомлення про протікання пам'яті від системи тестування - то третій, а якщо просто вам не подобається, скільки пам'яті виділяється - то четвертий. Ну а якщо повідомлення взагалі не про протікання, але ви собі нафантазували, що "десь протікає" без жодних на те підстав, то п'ятий, і я ставлю саме на нього.
Так, і ще:
- ви не присвоюєте nullptr next-у новостворених вузлів; може, воно так і треба, але в кінці там же має бути nullptr, чи не так?
- нащо ви видаляєте останній елемент?

3 Востаннє редагувалося Teg Miles (28.10.2024 22:53:42)

Re: Парсинг рядка в зв'язаний список

koala написав:

У ванній дивилися? Може, забилося щось?

Будь ласка, замість своїх висновків описуйте те, що ви бачите. Якщо в у вас на столі вода - це один симптом, якщо на підлозі - то інший, якщо є повідомлення про протікання пам'яті від системи тестування - то третій, а якщо просто вам не подобається, скільки пам'яті виділяється - то четвертий. Ну а якщо повідомлення взагалі не про протікання, але ви собі нафантазували, що "десь протікає" без жодних на те підстав, то п'ятий, і я ставлю саме на нього.
Так, і ще:
- ви не присвоюєте nullptr next-у новостворених вузлів; може, воно так і треба, але в кінці там же має бути nullptr, чи не так?
- нащо ви видаляєте останній елемент?

Навіть без видалення останнього елемента виходить ось таке:
SUMMARY: AddressSanitizer: 48 byte(s) leaked in 3 allocation(s).

4 Востаннє редагувалося koala (29.10.2024 07:45:21)

Re: Парсинг рядка в зв'язаний список

Так, я був неправий, визнаю.

Спробував ваш код на тому сайті - пише

UndefinedBehaviorSanitizer:DEADLYSIGNAL
==1==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x000000000008 (pc 0x0000004257fc bp 0x7ffea33959c0 sp 0x7ffea3395810 T1)
==1==The signal is caused by a READ memory access.

Після видалення рядків

Teg Miles написав:
    cur = cur->next;
    delete cur;

проблема зникає.

Будь ласка, наступного разу дотримуйтеся формату "завдання-код-результат[-роздуми]". Перші три частини обов'язкові, остання бажана.

Подякували: Teg Miles, leofun012

5 Востаннє редагувалося steamwater (03.11.2024 09:36:53)

Re: Парсинг рядка в зв'язаний список

Teg Miles, знов жеж незрозумiло, до чого список до парсiнгу. Парсити можна будь-куди. Хоч у вектор чи навiть масив. Той хто пише таки кати є кат. Це слушна причина щоб його за це катувати. Бо вчити список таким чином, це марна витрата часу. Ось код, який не дуже жвавий та короткий, але - для наглядностi:

#include <iostream>
#include <string>
 
using std::cout;

struct Node
{
    Node(int a)
    :data(a)
    {
    }

    int data;
    Node *next;
};

struct nb_list
{
    nb_list()
    :head(nullptr)
    {
    }

    ~nb_list()
    {
        if(head){
        Node *next_head;
        while(next_head=head->next)
        {
            delete head;
            head=next_head;
        }
        }
    }

    Node *insert_after(int a, Node *targ=nullptr)
    {
        Node *ins=new Node(a);
        Node *ret=nullptr;
        if(!head){
           head=ins;
           head->next=nullptr;
           ret=head;
        }else{
            if(!targ){
             Node *current=head;
                do
                {
                   targ=current;
                }while(current=current->next);

            }
            ins->next=targ->next;
            targ->next=ins;

            ret=ins;
        }
        return ret;
    }

    void prn()
    {
        if(!head) return;
        Node *current=head;
        do
        {
            cout<<current->data<<' ';
        }while(current=current->next);
        cout<<'\n';
    }

 Node *head;

};

int main()
{
    std::string test_str("12 -> 2346 -> 315 -> nullptr");
    nb_list lst;

    std::string::size_type n_left(0), n_right(0), shift_after_terminal_str=4;//3+1
    const char *terminal_str=" -> ";
    const char *final_terminal_str="nullptr";
    std::string subs;
    Node *node_target=nullptr;

    while(true)
    {
         n_right=test_str.find_first_of(terminal_str, n_left);//finds the first space symbol in " -> "
             subs=test_str.substr(n_left,n_right-n_left);
                 if(subs[0]==final_terminal_str[0])break;//'n' in "nullptr"
                     int extracted_int=std::stoi(subs);
                         node_target=lst.insert_after(extracted_int, node_target);
                            n_left=n_right+shift_after_terminal_str;
    }

    lst.prn();
    return 0;
}


Але що у ньому стосується списку? Один метод вставки елементу? А тодi навiщо воно? Задачи геть непов'язанi якоюсь логiкою.

6

Re: Парсинг рядка в зв'язаний список

steamwater написав:

Teg Miles, знов жеж незрозумiло, до чого список до парсiнгу. Парсити можна будь-куди. Хоч у вектор чи навiть масив. Той хто пише таки кати є кат. Це причина щоб його за це катувати. Бо вчити список таким чином, це марна витрата часу. От код, який не дуже жвавий та короткий, але - для наглядностi:

#include <iostream>
#include <string>
 
using std::cout;

struct Node
{
    Node(int a)
    :data(a)
    {
    }

    int data;
    Node *next;
};

struct nb_list
{
    nb_list()
    :head(nullptr)
    {
    }

    ~nb_list()
    {
        if(head){
        Node *next_head;
        while(next_head=head->next)
        {
            delete head;
            head=next_head;
        }
        }
    }

    Node *head;

    Node *insert_after(int a, Node *targ=nullptr)
    {
        Node *ins=new Node(a);
        Node *ret=nullptr;
        if(!head){
           head=ins;
           head->next=nullptr;
           ret=head;
        }else{
            if(!targ){
             Node *current=head;
                do
                {
                   targ=current;
                }while((current=current->next)!=nullptr);

            }
            ins->next=targ->next;
            targ->next=ins;

            ret=ins;
        }
        return ret;
    }

    void prn()
    {
        if(!head) return;
        Node *current=head;
        do
        {
            cout<<current->data<<' ';
        }while(current=current->next);
        cout<<'\n';
    }

};

int main()
{
    std::string test_str("12 -> 2346 -> 315 -> nullptr");
    nb_list lst;

    std::string::size_type n_beg(0),
                           n_left(n_beg),
                           n_right(n_beg),
                           n_end(std::string::npos),
                           shift_after_terminal_str=4;//3+1
    const char *terminal_str=" -> ";
    const char *final_terminal_str="nullptr";
    std::string subs;
    Node *node_target=nullptr;
    while(true)
    {
         n_right=test_str.find_first_of(terminal_str, n_left);
             subs=test_str.substr(n_left,n_right-n_left);
                 if(subs==final_terminal_str)break;
                     int extracted_int=std::stoi(subs);
                         node_target=lst.insert_after(extracted_int, node_target);
                            n_left=n_right+shift_after_terminal_str;
    }

    lst.prn();
    return 0;
}


Але що у ньому стосується списку? Один метод вставки елементу? А тодi навiщо воно? Задачи геть непов'язанi якоюсь логiкою.

Такі задачі потрібні для набуття досвіду. Це як дитині дають написати одну й ту ж окрему літеру багато разів, а лише потім цілі слова й речення.
І незважаючи на простоту завдання, з вказівниками я все одно наплутав. Тому в таких завдань є свій сенс.

7 Востаннє редагувалося steamwater (30.10.2024 20:18:36)

Re: Парсинг рядка в зв'язаний список

Teg Miles написав:

Такі задачі потрібні для набуття досвіду. Це як дитині дають написати одну й ту ж окрему літеру багато разів, а лише потім цілі слова й речення.
І незважаючи на простоту завдання, з вказівниками я все одно наплутав. Тому в таких завдань є свій сенс.

Нi, Teg Miles, вони потрiбнi, щоб получити зареестрованих користувачiв сайту. Тобто задача - якось заробити. Але, якщоб з цього ще була користь, то чом би й нi? Дивiться, вам пропонують спарсити строку, конвертувати у iнший формат, а вже тодi - заповнити список. Так, - той самий список з яким у вас виникли проблеми. Але ж перша частка завдання нiяк iз списком як таким не пов'язана, будючи бiльш навантаженою працею. З такимож успiхом ви могли б рiшати завдання по заповненню списку з якогось простого джерела. Наприклад, це мiг би бути банальний ввод з клавiатури. В вас би виникли тiж самi проблеми, пов'язанi саме iз списком i ви могли б зосередитись, саме на них. Це була б цiльоспрямована дiяльнiсть. А те що я бачу, це знущання над студентом. Вiд таких завдань як побiчний эфект, може виникнути звичка до поневолення розуму. Роби що кажуть i не думай! Я вважаю, що це погано.
Доречи, в вас є Пратта? У нього до кожного роздiлу купка завдань. Там теж не все гладко, але кажуть, що непогано. Можна було б тут порiшати)
Хоч як там що, а вашi запитання, це покi що, єдиний струмочок енергiї, що живить цей роздiл. Тож продовжуйте i не звертайте увагу на моє бурчання. А я буду бурчати)