Объединение (конкатенация) двух односвязных списков

@SkyFlyStaR · Регистрация: 16.10.2011

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

Задача: Построить стек (односвязный список). Показать реализацию стека на следующем примере: сцепить два связанных списка данных символьного типа, через функцию concatenate.
Списки ввожу до того момента, пока не введется '0'.
Вот то, что получилось:

C++

#include <iostream>
using namespace std;
 
struct node{
    char d;
    node *p;
};
node *first(char d);
void push(node **top, char d);
char pop(node **top);
node *concatenate(node **top, node **top2);
 
int main(){
    cout << "Введите 1й список" << endl;
    char t;
    cin >> t;
    node *top=first(t);
    cin >> t;
    while (t!='0'){
        push(&top,t);
        cin >> t;
    }
    cout << "Введите 2й список" << endl;
    cin >> t;
    node *top2=first(t);
    cin >> t;
    while (t!='0'){
        push(&top2,t);
        cin >> t;
    }
    node *res=concatenate(&top,&top2);
    while (res)
        cout << pop(&res) << ' ';
return 0;
}
node *first(char d){
    node *pv=new node;
    pv->d=d;
    pv->p=0;
    return pv;
}
void push(node **top, char d){
    node *pv=new node;
    pv->d=d;
    pv->p=*top;
    *top=pv;
}
char pop(node **top){
    char temp=(*top)->d;
    node *pv=*top;
    *top=(*top)->p;
    delete pv;
    return temp;
}
node *concatenate(node **top, node **top2){
    char temp;
    temp=pop(*&top2);
    node *pv=first(temp);
    while (top2){
        char temp2=pop(*&top2);
        push(&pv,temp2);
    }
    while (top){
        char temp2=pop(*&top);
        push(&pv,temp2);
    }
    return pv;
}

@kravam · 17.10.2011, 00:51

Допустим, первый список (схематично) из двух элементов
a->b
второй
c->e

У меня несколько вопросов: на что должен указывать b.p (и соответственно c.d) и каков должен быть конечный список (a->b->c->e или как? И если да, то на что должен указывать в таком случае e.d? )

@SkyFlyStaR · 17.10.2011, 00:57 **[ТС]**

kravam, список должен состоять из a,b,c,e, что за b.p и c.d?

@kravam · 17.10.2011, 01:01

a->b->c->e?

Ну поля, ё. У тебя же d это указатель, на что он указывать должен?:

Добавлено через 1 минуту
struct node{
char d;
node *p;
};
а, ошибся я; p указатель на что должен указывать?

@silentnuke · 17.10.2011, 01:03

Не по теме:

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

а, ошибся я; p указатель на что должен указывать?

на следующий элемент в списке, кэп?=)
есть список a, есть список b.

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

@SkyFlyStaR · 17.10.2011, 01:07 **[ТС]**

kravam,
silentnuke, да, p - это следующий элемент

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

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

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

именно это и не получается реализовать в функции concatenate

@silentnuke · 17.10.2011, 01:17

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

kravam,
silentnuke, да, p - это следующий элемент

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

именно это и не получается реализовать в функции concatenate

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

@SkyFlyStaR · 17.10.2011, 01:24 **[ТС]**

silentnuke, не совсем пойму, где бесконечный цикл, я pop'ом достаю поочередно элементы из списков и push'ем помещаю в новый

@silentnuke · 17.10.2011, 01:38

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

silentnuke, не совсем пойму, где бесконечный цикл, я pop'ом достаю поочередно элементы из списков и push'ем помещаю в новый

да, мой косяк, не обратил что так делаете=)

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

C++

#include <iostream>
using namespace std;
 
struct node{
    char d;
    node *p;
};
node *first(char d);
void push(node **top, char d);
char pop(node **top);
node *concatenate(node **top, node **top2);
 
int main(){
    cout << "Введите 1й список" << endl;
    char t;
    cin >> t;
    node *top=first(t);
    cin >> t;
    while (t!='0'){
        push(&top,t);
        cin >> t;
    }
    cout << "Введите 2й список" << endl;
    cin >> t;
    node *top2=first(t);
    cin >> t;
    while (t!='0'){
        push(&top2,t);
        cin >> t;
    }
    node *res=concatenate(&top,&top2);
    while (res)
        cout << pop(&res) << ' ';
    return 0;
}
node *first(char d){
    node *pv=new node;
    pv->d=d;
    pv->p=0;
    return pv;
}
void push(node **top, char d){
    node *pv=new node;
    pv->d=d;
    pv->p=*top;
    *top=pv;
}
char pop(node **top){
    char temp=(*top)->d;
    node *pv=*top;
    *top=(*top)->p;
    delete pv;
    return temp;
}
node *concatenate(node **top, node **top2){
    char temp;
    temp=pop(top2);
    node *pv=first(temp);
    while (*top2!=NULL){
        char temp2=pop(top2);
        push(&pv,temp2);
    }
    while (*top!=NULL){
        char temp2=pop(top);
        push(&pv,temp2);
    }
    return pv;
}

@kravam · 17.10.2011, 02:20

silentnuke, дядя, я спрашивал за ПОСЛЕДНИЙ указатель. Куда бы он указывал у меня , я знаю. Куда он должен указывать у ТС- один Бог ведает. может у него закольцованный список.

Но как бы то ни было.

Введём:

C++

Введите 1й список
q
0
Введите 2й список
w
0

И пронализируем поведение программы. Для этого в функцию конкантекации добавим такие
надписи:

C++

         printf ("top2= %x\n", top2);
        temp=pop(*&top2);
        node *pv=first(temp);
 
        printf ("top2= %x\n", top2);
 
        while (top2){
                printf ("wwwwwwwwww\n");
                char temp2=pop(*&top2);
                printf ("rrrrrrrrrrrrr\n");

Теперь внимательно меня слушаем.
По запуску программы мы не увидим

C++

1	printf ("rrrrrrrrrrrrr\n");

Делаем вывод, что сбой где-то во втором вызове pop. Действительно, первый вызов pop, вот этот

C++

        printf ("top2= %x\n", top2);
        temp=pop(*&top2);
        node *pv=first(temp);
 
        printf ("top2= %x\n", top2);

не вызвал сбоя, wwwwwwwwwww напечаталось
Но вызовы pop совершенно одинаковы! И даже передаются одинаковые адреса! Почему первый pop отрабатывает нормально, а второй даёт сбой?

Делаем предположение: Значит, между вызовами pop меняется СОДЕРЖАНИЕ адресов. Причём меняется АВАРИЙНО так, что второй pop не может сработать.
Где находится участок кода, в котором могло бы аварийно поменяться содержание адресов? (И этот участок должен находиться МЕЖДУ вызовами pop)

Правильно. Этот участок- сама функция pop. При её первом вызове что-то там нехорошее происходит.

Смотрим на функцию pop. Она принимает параметр top, равный top2, проверяем это, пишем так:

C++

1 2	char pop(node **top){ printf ("top= %x\n", top);

Запускаем прогу и видим:

C++

Введите 1й список
q
0
Введите 2й список
w
0
top2= 22ff54
top= 22ff54
top2= 22ff54
wwwwwwwwww
top= 22ff54

ага, функция pop вызвалась 2 действительно, top==top2, адреса не меняются, значит меняется то, что лежит по этим адресам; при втором вызове pop даёт крах

Обращаю твоё внимание на одну очень важную вещь: мы убедились, что pop даёт крах при ВТОРОМ вызове, но исследовать будем ПЕРВЫЙ ВЫЗОВ, ибо, как мы поняли, именно в первый раз аварийно меняется содержимое top! (или top2, что то же самое)

Итак, пошли в функцию смотреть, что такого происходит с этим адресом:

C++

1
2
3

        char temp=(*top)->d;
//Тут вроде всё нормально, даже можем посмотреть чему равно становится temp 
//        printf ("temp= %c\n", temp);

////////////////////////////////////////////////////////

C++

1	node pv=top;

Это уже интереснее. Содержимое top куда-то кладётся- а мы уже помним, что нас интересует именно содержимое этого адреса! Держим в уме переменную pv!

C++

1	top=(top)->p;

Ага, *top это адрес объекта и он меняется! На корректное ли значение? Нет! Ведь (*top)->p указывает на ноль! ПРоверяем:

C++

char pop(node **top){
        printf ("top= %x\n", top);
        char temp=(*top)->d;
//        printf ("temp= %c\n", temp);
        node *pv=*top;
        *top=(*top)->p;
        printf ("__*top= %d\n", *top);
        delete pv;
        return temp;
}

Введите 1й список
q
0
Введите 2й список
w
0
top2= 22ff54
top= 22ff54
__*top= 0
top2= 22ff54
wwwwwwwwww
top= 22ff54

Ноль! А в следующий вызов pop мы также вызовем её со значением 22ff54. разыменуем и получим 0, с котрого безуспешно будем пытаться взять вот это:

C++

1	char temp=(*top)->d;

И вот тут-то и будет самый настоящий крах.
Ввыод: при первом вызове pop НЕПРАВИЛЬНО писать это:

C++

1	top=(top)->p;

- читай: класть ноль в переменную p, ибо будет второй вызов, который обратится по адресу p, равному 0 и потерпит крах!

Добавлено через 16 минут
В обшем, я с самого начал хотел написать, что нужна функция вывода списка- щас бы проверили.
Короче, размышляя так. приходим к выводу, что эти условия неверны:

C++

1 2	while (top2) while (top){

а надо так:

C++

1 2	while ((top2)) while ((top))

Запускаем, прога сбоев не даёт. Но и проверить конкантекацию возможности нет- ведь нет соответсвующей функции. Пиши. Пивет!

Добавлено через 3 минуты
НУ то есть мы делаем неправильно одно из двух: это

C++

1	top=(top)->p;

или это

C++

1	while (top2)

ибо если условие не выполнялось, то ы бы и в функцию не вошли и краха бы не было.
Ну а дальше уж сам сообразишь что менять.

@silentnuke · 17.10.2011, 03:03

kravam, ошибка была в проверке, выше уже выложил решение.

@itnomad · 03.11.2011, 17:59

у меня похожая задача, но на Си: напишите программу, выполняющую конкатенацию двух связанных списков символов. программа должна включать функцию concatenate, которой в качестве аргументов передаются указатели на оба списка и она присоединяет второй список к первому.

Вот что я написал:

C

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
 
struct listNode{
    char data;
    listNode *nextPtr;
};
 
typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
 
//funktsia obiedinenia spiskov
void concatenate(LISTNODEPTR , LISTNODEPTR );
//funktsia pechati spiska
void printList(LISTNODEPTR);
//funktsia vvoda bukv v spisok
void insert(LISTNODEPTR *, char);
 
void main(){
    clrscr();
    char item;
    LISTNODEPTR startPtr=NULL;
    LISTNODEPTR startPtr2=NULL;
    //vvodim 3 bukvi v pervii spisok
    for(int i=0;i<3;i++){
       printf("Enter a character list1: \n");
       scanf("%s", &item);
       insert(&startPtr, item);
       printList(startPtr);
    }
       //vvodim 3 bukvi vo vtoroi spisok
    for(i=0;i<3;i++){
       printf("Enter a character list2: \n");
       scanf("%s", &item);
       insert(&startPtr2, item);
       printList(startPtr2);
    }
    //obiedinenie
    concatenate(startPtr,startPtr2);
    printf("\nConcatenate list(1+2): \n");
    printList(startPtr);
    getch();
}
 
//funktia vvoda bukv v spisok
void insert(LISTNODEPTR *sPtr, char value){
    LISTNODEPTR newPtr, prevPtr, curPtr;
    newPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE));
    if(newPtr!=NULL){
       newPtr->data=value;
       newPtr->nextPtr=NULL;
       prevPtr=NULL;
       curPtr=*sPtr;
       while(curPtr!=NULL&&value>curPtr->data){
          prevPtr=curPtr;
          curPtr=curPtr->nextPtr;
       }
       if(prevPtr==NULL){
          newPtr->nextPtr=*sPtr;
          *sPtr=newPtr;
       }
       else{
          prevPtr->nextPtr=newPtr;
          newPtr->nextPtr=curPtr;
       }
    }
    else
       printf("%c  not inserted. No memory avaible\n", value);
}
 
//funktia raspechatki spiska
void printList(LISTNODEPTR curPtr){
    if(curPtr==NULL)
       printf("List is empty\n");
    else{
       printf("The list is: \n");
       while(curPtr!=NULL){
          printf("%c-> ", curPtr->data);
          curPtr=curPtr->nextPtr;
       }
       printf("NULL\n\n");
    }
}
 
//funktia obiedinenia dvuh spiskov
void concatenate(LISTNODEPTR startPtr, LISTNODEPTR startPtr2){
    LISTNODEPTR curPtr;
    curPtr=startPtr;
    while(curPtr!=NULL){
       printf("%c-> ", curPtr->data);
       curPtr=curPtr->nextPtr;
    }
    if(curPtr->nextPtr==NULL) {
       curPtr->nextPtr=startPtr2;
    }
}

вроде правильно, но почему не объединяет - ума не приложу. подскажите пожалуйста, что не так?

@kravam · 03.11.2011, 19:25

Правило перое:
1) ты должен найти данные, на которых твоя программа спотыкается.

Правило второе:
2) ты должен упростить их до минимума

То есть, допустим программа спотыкается на списках (грубо говоря

2->3->4
3->5

В данном контектсе упростить- значит уменьшить списки до минимума- до одного или двух (естессно, программа должна продолжать виснуть)

И потом, если не найдушь ошибку говорить:
вот у меня список 1->2 и 1->NULL, не присоединяется ни фига. Согласись, гораздо проще работаь с маленькими данными, нежели с большими? И не говори, что программа всегда не присоединяет. Тут конкретика нужна.

Иначе всю эту подготовительную работу дожен будет проделать отвечающий (напрример, я), а меня с некоторых пор стало ломать это делать.

@itnomad · 03.11.2011, 19:59

Ок! я просто не знал, только что буквально зарегистрировался на форуме.

В программе все работает, но
проблема, мне кажется в функции объединения списков concatenate.
функция получает два указателя на начало первого списка (startPtr)и на начало второго списка (startPtr2).
Дальше в while я дохожу до конца первого списка, т.е. до указателя последнего узла первого списка, который равен NULL и в if присваиваю ему указатель на начало второго списка:
curPtr->nextPtr=startPtr2;

Присваивание происходит, т.к.проверял, распечатывается второй список.
Т.е., если я правильно понимаю, связывание двух списков произошло.

Потом в main запускаю функцию печати списка с параметром указателем на начало списка printList(startPtr) - печатается только первый список, а второй присоединенный -нет!

вот в этом и загвоздка. не могу понять почему.

@kravam · 03.11.2011, 20:07

Чё надо делать, я сказал.

@itnomad · 04.11.2011, 01:48

хмм.. че то не понятно, что от меня требуется

@kravam · 04.11.2011, 05:45

Правило перое:
1) ты должен найти данные, на которых твоя программа спотыкается.

Правило второе:
2) ты должен упростить их до минимума
...А я пока в упор не вижу чё надо вводить чтобы убедиться- да, вот конкантекации не происходит.

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	03.11.2011, 19:25	13
	Правило перое: 1) ты должен найти данные, на которых твоя программа спотыкается. Правило второе: 2) ты должен упростить их до минимума То есть, допустим программа спотыкается на списках (грубо говоря 2->3->4 3->5 В данном контектсе упростить- значит уменьшить списки до минимума- до одного или двух (естессно, программа должна продолжать виснуть) И потом, если не найдушь ошибку говорить: вот у меня список 1->2 и 1->NULL, не присоединяется ни фига. Согласись, гораздо проще работаь с маленькими данными, нежели с большими? И не говори, что программа всегда не присоединяет. Тут конкретика нужна. Иначе всю эту подготовительную работу дожен будет проделать отвечающий (напрример, я), а меня с некоторых пор стало ломать это делать. 0

@itnomad 0 / 0 / 0 Регистрация: 03.11.2011 Сообщений: 3
	03.11.2011, 19:59	14
	Ок! я просто не знал, только что буквально зарегистрировался на форуме. В программе все работает, но проблема, мне кажется в функции объединения списков concatenate. функция получает два указателя на начало первого списка (startPtr)и на начало второго списка (startPtr2). Дальше в while я дохожу до конца первого списка, т.е. до указателя последнего узла первого списка, который равен NULL и в if присваиваю ему указатель на начало второго списка: curPtr->nextPtr=startPtr2; Присваивание происходит, т.к.проверял, распечатывается второй список. Т.е., если я правильно понимаю, связывание двух списков произошло. Потом в main запускаю функцию печати списка с параметром указателем на начало списка printList(startPtr) - печатается только первый список, а второй присоединенный -нет! вот в этом и загвоздка. не могу понять почему. 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	03.11.2011, 20:07	15
	Чё надо делать, я сказал. 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	17.10.2011, 00:51	2
	Допустим, первый список (схематично) из двух элементов a->b второй c->e У меня несколько вопросов: на что должен указывать b.p (и соответственно c.d) и каков должен быть конечный список (a->b->c->e или как? И если да, то на что должен указывать в таком случае e.d? ) 0

@SkyFlyStaR 1 / 1 / 0 Регистрация: 16.10.2011 Сообщений: 69
	17.10.2011, 00:57 [ТС]	3
	kravam, список должен состоять из a,b,c,e, что за b.p и c.d? 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	17.10.2011, 01:01	4
	a->b->c->e? Ну поля, ё. У тебя же d это указатель, на что он указывать должен?: Добавлено через 1 минуту struct node{ char d; node *p; }; а, ошибся я; p указатель на что должен указывать? 0

@silentnuke
	17.10.2011, 01:03 #5
	Не по теме: Сообщение от kravam а, ошибся я; p указатель на что должен указывать? на следующий элемент в списке, кэп?=) есть список a, есть список b. создаем список с, в котором поочередно добавляем элементы списка a, затем элементы списка b, функция добавления есть,в чем проблема? 0

@SkyFlyStaR 1 / 1 / 0 Регистрация: 16.10.2011 Сообщений: 69
	17.10.2011, 01:07 [ТС]	6
	kravam, silentnuke, да, p - это следующий элемент Добавлено через 3 минуты Сообщение от silentnuke создаем список с, в котором поочередно добавляем элементы списка a, затем элементы списка b, функция добавления есть,в чем проблема? именно это и не получается реализовать в функции concatenate 0

@silentnuke Android Programmer 141 / 142 / 10 Регистрация: 08.12.2010 Сообщений: 421
	17.10.2011, 01:17	7
	Сообщение от SkyFlyStaR kravam, silentnuke, да, p - это следующий элемент Добавлено через 3 минуты именно это и не получается реализовать в функции concatenate ну дык, у вас там вечный цикл, кто за вас будет смещать указатель на следующий элемент списка, Страуструп? 0

@SkyFlyStaR 1 / 1 / 0 Регистрация: 16.10.2011 Сообщений: 69
	17.10.2011, 01:24 [ТС]	8
	silentnuke, не совсем пойму, где бесконечный цикл, я pop'ом достаю поочередно элементы из списков и push'ем помещаю в новый 0

@silentnuke Android Programmer 141 / 142 / 10 Регистрация: 08.12.2010 Сообщений: 421
	17.10.2011, 03:03	11
	kravam, ошибка была в проверке, выше уже выложил решение. 0

@itnomad 0 / 0 / 0 Регистрация: 03.11.2011 Сообщений: 3
	04.11.2011, 01:48	16
	хмм.. че то не понятно, что от меня требуется 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,679
	04.11.2011, 05:45	17
	Правило перое: 1) ты должен найти данные, на которых твоя программа спотыкается. Правило второе: 2) ты должен упростить их до минимума ...А я пока в упор не вижу чё надо вводить чтобы убедиться- да, вот конкантекации не происходит. 0