Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.89
SkyFlyStaR
1 / 1 / 0
Регистрация: 16.10.2011
Сообщений: 69
17.10.2011, 00:15     Объединение (конкатенация) двух односвязных списков #1
Задача: Построить стек (односвязный список). Показать реализацию стека на следующем примере: сцепить два связанных списка данных символьного типа, через функцию concatenate.
Списки ввожу до того момента, пока не введется '0'.
Вот то, что получилось:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
17.10.2011, 00:51     Объединение (конкатенация) двух односвязных списков #2
Допустим, первый список (схематично) из двух элементов
a->b
второй
c->e

У меня несколько вопросов: на что должен указывать b.p (и соответственно c.d) и каков должен быть конечный список (a->b->c->e или как? И если да, то на что должен указывать в таком случае e.d? )
SkyFlyStaR
1 / 1 / 0
Регистрация: 16.10.2011
Сообщений: 69
17.10.2011, 00:57  [ТС]     Объединение (конкатенация) двух односвязных списков #3
kravam, список должен состоять из a,b,c,e, что за b.p и c.d?
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
17.10.2011, 01:01     Объединение (конкатенация) двух односвязных списков #4
a->b->c->e?

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

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

Не по теме:

Цитата Сообщение от kravam Посмотреть сообщение
а, ошибся я; p указатель на что должен указывать?
на следующий элемент в списке, кэп?=)
есть список a, есть список b.

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

SkyFlyStaR
1 / 1 / 0
Регистрация: 16.10.2011
Сообщений: 69
17.10.2011, 01:07  [ТС]     Объединение (конкатенация) двух односвязных списков #6
kravam,
silentnuke, да, p - это следующий элемент

Добавлено через 3 минуты
Цитата Сообщение от silentnuke Посмотреть сообщение
создаем список с, в котором поочередно добавляем элементы списка a, затем элементы списка b, функция добавления есть,в чем проблема?
именно это и не получается реализовать в функции concatenate
silentnuke
Android Programmer
137 / 138 / 5
Регистрация: 08.12.2010
Сообщений: 421
17.10.2011, 01:17     Объединение (конкатенация) двух односвязных списков #7
Цитата Сообщение от SkyFlyStaR Посмотреть сообщение
kravam,
silentnuke, да, p - это следующий элемент

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

именно это и не получается реализовать в функции concatenate
ну дык, у вас там вечный цикл, кто за вас будет смещать указатель на следующий элемент списка, Страуструп?
SkyFlyStaR
1 / 1 / 0
Регистрация: 16.10.2011
Сообщений: 69
17.10.2011, 01:24  [ТС]     Объединение (конкатенация) двух односвязных списков #8
silentnuke, не совсем пойму, где бесконечный цикл, я pop'ом достаю поочередно элементы из списков и push'ем помещаю в новый
silentnuke
Android Programmer
137 / 138 / 5
Регистрация: 08.12.2010
Сообщений: 421
17.10.2011, 01:38     Объединение (конкатенация) двух односвязных списков #9
Цитата Сообщение от SkyFlyStaR Посмотреть сообщение
silentnuke, не совсем пойму, где бесконечный цикл, я pop'ом достаю поочередно элементы из списков и push'ем помещаю в новый
да, мой косяк, не обратил что так делаете=)

Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
17.10.2011, 02:20     Объединение (конкатенация) двух односвязных списков #10
silentnuke, дядя, я спрашивал за ПОСЛЕДНИЙ указатель. Куда бы он указывал у меня , я знаю. Куда он должен указывать у ТС- один Бог ведает. может у него закольцованный список.

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

Введём:
C++
1
2
3
4
5
6
Введите 1й список
q
0
Введите 2й список
w
0
И пронализируем поведение программы. Для этого в функцию конкантекации добавим такие
надписи:
C++
1
2
3
4
5
6
7
8
9
10
         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++
1
2
3
4
5
        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
2
3
4
5
6
7
8
9
10
11
Введите 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++
1
2
3
4
5
6
7
8
9
10
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
Android Programmer
137 / 138 / 5
Регистрация: 08.12.2010
Сообщений: 421
17.10.2011, 03:03     Объединение (конкатенация) двух односвязных списков #11
kravam, ошибка была в проверке, выше уже выложил решение.
itnomad
0 / 0 / 0
Регистрация: 03.11.2011
Сообщений: 3
03.11.2011, 17:59     Объединение (конкатенация) двух односвязных списков #12
у меня похожая задача, но на Си: напишите программу, выполняющую конкатенацию двух связанных списков символов. программа должна включать функцию concatenate, которой в качестве аргументов передаются указатели на оба списка и она присоединяет второй список к первому.

Вот что я написал:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
#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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
03.11.2011, 19:25     Объединение (конкатенация) двух односвязных списков #13
Правило перое:
1) ты должен найти данные, на которых твоя программа спотыкается.

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

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

2->3->4
3->5

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

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

Иначе всю эту подготовительную работу дожен будет проделать отвечающий (напрример, я), а меня с некоторых пор стало ломать это делать.
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) - печатается только первый список, а второй присоединенный -нет!

вот в этом и загвоздка. не могу понять почему.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
03.11.2011, 20:07     Объединение (конкатенация) двух односвязных списков #15
Чё надо делать, я сказал.
itnomad
0 / 0 / 0
Регистрация: 03.11.2011
Сообщений: 3
04.11.2011, 01:48     Объединение (конкатенация) двух односвязных списков #16
хмм.. че то не понятно, что от меня требуется
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2011, 05:45     Объединение (конкатенация) двух односвязных списков
Еще ссылки по теме:

Объявить объединение из двух структур и структуру из двух объединений C++
Объединение списков (list) C++
C++ Объединение двух списков

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
04.11.2011, 05:45     Объединение (конкатенация) двух односвязных списков #17
Правило перое:
1) ты должен найти данные, на которых твоя программа спотыкается.

Правило второе:
2) ты должен упростить их до минимума
...А я пока в упор не вижу чё надо вводить чтобы убедиться- да, вот конкантекации не происходит.
Yandex
Объявления
04.11.2011, 05:45     Объединение (конкатенация) двух односвязных списков
Ответ Создать тему
Опции темы

Текущее время: 18:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru