Вставить в первый список, все узлы из второго

@David_G · Регистрация: 18.09.2020

Author24 — интернет-сервис помощи студентам

Дана следующая задача:
Даны два линейных однонаправленных
списка L1 и L2.
Разработать функцию, которая
вставляет в список L1 за узлом с заданным
значением Х все узлы списка L2, если узел Х
есть в списке L1.
Я с этими списками вообще на "Вы", так до сих пор и не понял как они работают и как к ним обращаться. В общем создал что-то типа того:

C++

#include <iostream>
 
using namespace std;
 
struct node
{
    char data;
    node *next;
};
 
node* func (node *L1, node *L2, char key)
{
    node *q1 = L1;
    node *q2 = L2;
    while(q1!=0 && q1->data!=key)
    {
        q1 = q1->next;
    }
    if(q1->data == key)
    {
        while(q2!=0){
        q1 = q1->next;
        q1->data = q2 ->data;
        q2 = q2->next;
        }
    }
    return q1;
}
 
void print(node *L1)
{
    node *q1 = L1;
    cout << q1->data << endl;
    q1 = q1->next;
}
 
int main()
{
    node *ptr1, *ptr2,*ptr3,*ptr4,*ptr5;
    ptr1 = new node;
    ptr1 -> data = 'a';
    ptr1 -> next = 0;
 
    ptr2 = new node;
    ptr2 -> data = 'b';
    ptr2 -> next = 0;
 
    ptr3 = new node;
    ptr3 -> data = 'c';
    ptr3 -> next = 0;
 
    ptr4 = new node;
    ptr4 -> data = 'd';
    ptr4 -> next = 0;
 
    ptr5 = new node;
    ptr5 -> data = 'e';
    ptr5 -> next = 0;
 
    node *L1 = nullptr;
    L1 = ptr1;
    ptr1 -> next = ptr5;
 
    node *L2 = nullptr;
    L2 = ptr2;
    ptr2 -> next = ptr3;
    ptr3 -> next = ptr4;
 
    node *L3 = func(L1,L2,'a');
    print(L3);
    return 0;
}

В функцию func, я передаю оба списка и нужный символ, внутри неё я даже могу отыскать этот символ, но вот как вставлять я не имею малейшего понятия, у них нет нумерации, программа выше не работает.

@Annemesski · 26.03.2021, 12:08

Для начала напишите функцию добавления элемента в список, чтобы не заниматься тем, чем Вы у себя в main() занимаетесь.

C++

void addToList(node *&head, char value)
{
    node *newnode = new node{ value, head };
    head = newnode;
}

Удаление списка тоже лучше сделать функцией

C++

void deleteList(node *head)
{
    while (head)
    {
        node *forDeleteNode = head;
        head = nead->next;
        delete forDeleteNode;
    }
}

Далее удобнее будет, написать функцию поиска элемента списка по значению, которая возвращает указатель на элемент списка если таковой найден, а если не найден то нулевой указатель

C++

node * findInList(node *head, char value)
{
    while (head)
    {
        if (head->data == value)
            return head;
        head = neat->next;
    }
    return nullptr;
}

И теперь совсем чуть-чуть: объединить списки

C++

bool joinListsIf(node *lst1, node *lst2, char value)
{
    node *forInsertNode = findInList(lst1, value);
    if (forInsertNode)
    {
        node *lst1Tail = forInsertNode->next;
        forInsertNode->next = lst2;
 
        while (forInsertNode->next)
            forInsertNode = forInsertNode->next;
 
        forInsertNode->next = lst1Tail;
 
        return true;
    }
 
    return false;
}

@David_G · 26.03.2021, 15:52 **[ТС]**

Помимо ваших функций добавил ещё

C++

void print(node *L)
{
    node *q = L;
    while(q)
    {
        cout << q->data << endl;
        q = q->next;
    }
}

ну и конечно main

C++

int main()
{
    node *L1;
    char value;
    for(int a = 0; a<10; a++){
    cin >> value;
    addToList(L1,value);
    }
    node *L2;
    for(int a = 0; a<10; a++){
    cin >> value;
    addToList(L2,value);
    }
    if(joinListsIf(L1,L2,'a')==true)
        print(L1);
    else
        cout << "NO KEY";
    return 0;
}

Когда символ есть вроде работает нормально, а когда символ не находит, то не выводит ничего вообще, и в обоих случаях возвращается с ошибкой Process returned -1073741819 (0xC0000005)

@Annemesski · 26.03.2021, 17:11

David_G, первые ноды L1 и L2 надо правильно инициализировать

C++

1
2
3

node *L1 = new node{ '1', nullptr };
//......
node *L2 = new node{ '2', nullptr };

@David_G · 26.03.2021, 17:23 **[ТС]**

Сообщение от Annemesski

первые ноды L1 и L2 надо правильно инициализировать

Спасибо, заработало, только вот теперь в конце он выводит два непонятных символа, что это такое?

@Annemesski · 26.03.2021, 17:40

Сообщение от David_G

что это такое?

это Ваше )) приведите полный код, что у Вас получилось?

@David_G · 26.03.2021, 19:10 **[ТС]**

Сообщение от Annemesski

это Ваше )) приведите полный код, что у Вас получилось?

C++

#include <iostream>
 
using namespace std;
 
struct node
{
    char data;
    node *next;
};
 
void print(node *L)
{
    node *q = L;
    cout << "OUT" << endl;
    while(q)
    {
        cout << q->data << endl;
        q = q->next;
    }
}
 
void addToList(node *&head, char value)
{
    node *newnode = new node{ value, head };
    head = newnode;
}
 
void deleteList(node *head)
{
    while (head)
    {
        node *forDeleteNode = head;
        head = head->next;
        delete forDeleteNode;
    }
}
 
node * findInList(node *head, char value)
{
    while (head)
    {
        if (head->data == value)
            return head;
        head = head->next;
    }
    return nullptr;
}
 
bool joinListsIf(node *lst1, node *lst2, char value)
{
    node *forInsertNode = findInList(lst1, value);
    if (forInsertNode)
    {
        node *lst1Tail = forInsertNode->next;
        forInsertNode->next = lst2;
 
        while (forInsertNode->next)
            forInsertNode = forInsertNode->next;
 
        forInsertNode->next = lst1Tail;
 
        return true;
    }
 
    return false;
}
 
int main()
{
    node *L1 = new node{1,nullptr};
    char value;
    for(int a = 0; a<10; a++){
    cin >> value;
    addToList(L1,value);
    }
    node *L2 = new node{2,nullptr};
    for(int a = 0; a<10; a++){
    cin >> value;
    addToList(L2,value);
    }
    if(joinListsIf(L1,L2,'a')==true)
        print(L1);
    else
        cout << "NO KEY";
    return 0;
}

Добавлено через 5 минут

Сообщение от Annemesski

это Ваше )) приведите полный код, что у Вас получилось?

кажется я вместо char, передавал при инициализации через new - int, изменил на пустой символ ' ', стало всё нормально.

@Annemesski · 27.03.2021, 07:53

David_G, да, Вы передавали код символа у символа "единица" код 49

@David_G 4 / 4 / 1 Регистрация: 18.09.2020 Сообщений: 149
	26.03.2021, 17:23 [ТС]	5
	Сообщение от Annemesski первые ноды L1 и L2 надо правильно инициализировать Спасибо, заработало, только вот теперь в конце он выводит два непонятных символа, что это такое? Миниатюры 0

@Annemesski 2528 / 1247 / 461 Регистрация: 08.11.2016 Сообщений: 3,428
	26.03.2021, 17:40	6
	Сообщение от David_G что это такое? это Ваше )) приведите полный код, что у Вас получилось? 0

@Annemesski 2528 / 1247 / 461 Регистрация: 08.11.2016 Сообщений: 3,428
	27.03.2021, 07:53	8
	David_G, да, Вы передавали код символа у символа "единица" код 49 0

Вставить в первый список, все узлы из второго

Решение