Премини към съдържанието

Препоръчан отговор


Здравейте! Имам следната задача : Да се състави функция за обединение на два подредени двусвързани списъка с начални указатели START1 и START2 в нов списък със запазване на подредбата. 

До колкото разбирам си създавам двата списъка и ги пълна с числа, но как става да създам нов списък и да ги запази.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Некст на последния елемент от първия списък го насочваш към първия елемент на втория списък, а превиус на първия елемент от втория списък го насочваш към последния елемент на първия списък. Ако поддържаш и сайз, нюсайз = сайз1 + сайз2.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Новия списък за да е пак подреден, вземаш по-малкия  от първите елементи на списъците и го дабавяш към новия, после повтаяш докато единия списък не свърши и след това добавяш това което е останало от другия към края на новия списък.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

А, ако подредени означава сортирани, си вземам думите назад и си посипвам главата с пепел.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Нещо не мога да схвана. Трябва да пиша по два пъти ли примерно void add_b, void add_mid и за start 1 и за start 2, така ли. Ако може малко повече помощ


Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 1 час, mitko9670 написа:

Нещо не мога да схвана. Трябва да пиша по два пъти ли примерно void add_b, void add_mid и за start 1 и за start 2, така ли. Ако може малко повече помощ

Отговори на следния въпрос, за да те разберем какво имаш като въпрос.

Имаш списък едно със елементи: 1 8 4 5
Имаш сисък две със елементи: 2 9 3 6

Как трябва да изглежда третият списък?

1 8 4 5 2 9 3 6 или 1 2 3 4 5 6 8 9 ?

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Сега като чета условието, обаче никъде не е казано че трябва да има трети списък ами да се обединят двата.

Между другото при STL за списъците има функция merge() която точно това прави - добавя към елементите на подреден списък елементите на втори подреден списък като получения списък е отново подреден. Така че просто трябва да си напишеш такава функция за двусвързан списък.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 3 часа, programprogram написа:

Отговори на следния въпрос, за да те разберем какво имаш като въпрос.

Имаш списък едно със елементи: 1 8 4 5
Имаш сисък две със елементи: 2 9 3 6

Как трябва да изглежда третият списък?

1 8 4 5 2 9 3 6 или 1 2 3 4 5 6 8 9 ?

Имам примерно:

списък 1: 2 5 6 3

Списък  2: 4 9 8 7 

и да ми изведе 2 5 6 3 4 9 8 7

преди 2 часа, ined написа:

Сега като чета условието, обаче никъде не е казано че трябва да има трети списък ами да се обединят двата.

Между другото при STL за списъците има функция merge() която точно това прави - добавя към елементите на подреден списък елементите на втори подреден списък като получения списък е отново подреден. Така че просто трябва да си напишеш такава функция за двусвързан списък.

как се пише тази функция, но би трябвало да има и друг вариант

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
struct elem 
{
    int key;
    elem *prev;
    elem *next;
};

struct list
{
    elem *start;
    elem *end;
};


void merge(list &a, list &b)
{
     elem *p=a.start;
     if (p==NULL)
     {
         a.start=b.start;
         a.end=b.end;
         b.start=NULL;
         b.end=NULL;
         return;
     }
     while (p && b.start)
     {
         elem *q=b.start;
         if (q->key < p->key)
         {
             if (p->prev) p->prev->next=q;
             else a.start=q;
             q->prev=p->prev;
             p->prev=q;
             b.start=q->next;
             q->next=p;
         } else p=p->next;
     }
     if (b.start) 
     {
         a.end->next=b.start;
         b.start->prev=a.end;
         a.end=b.end;
         b.start=NULL;
     }
     b.end=NULL;
}

 

Редактирано от ined (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

А тея лист а и лист б как да го ноправя с добавяне на елементите в началото нали

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
#include <iostream>
using namespace std;

struct elem
{
	int key;
	elem *prev;
	elem *next;
}e;

struct list
{
	elem *start;
	elem *end;
}a, b;

void pushback(list& a, elem& e)
{
	elem* conductor;
	conductor = a.end;
	a.end = new elem;
	a.end->prev = conductor;
	a.end->next = 0;
	a.end->key = e.key;
	if (conductor !=0) conductor->next = a.end;
	if (a.start == 0) a.start = a.end;
}


void merge(list &a, list &b)
{
	elem *p = a.start;
	if (p == NULL)
	{
		a.start = b.start;
		a.end = b.end;
		b.start = NULL;
		b.end = NULL;
		return;
	}
	while (p && b.start)
	{
		elem *q = b.start;
		if (q->key < p->key)
		{
			if (p->prev) p->prev->next = q;
			else a.start = q;
			q->prev = p->prev;
			p->prev = q;
			b.start = q->next;
			q->next = p;
		}
		else p = p->next;
	}
	if (b.start)
	{
		a.end->next = b.start;
		b.start->prev = a.end;
		a.end = b.end;
		b.start = NULL;
	}
	b.end = NULL;
}


int main()
{
	elem* conductor;
	for (;;)
	{
		cout << "vavedete nov element v spisak a ili 0 za kraj -> ";
		cin >> e.key;
		if (e.key == 0) break;
		pushback(a, e);
	}
	cout << "\n\n";
	for (;;)
	{
		cout << "vavedete nov element v spisak b ili 0 za kraj -> ";
		cin >> e.key;
		if (e.key == 0) break;
		pushback(b, e);
	}
	cout << "\n\n";
	merge(a, b);
	conductor = a.start;
	for (;;)
	{
		cout << conductor->key << " ";
		if (conductor->next == 0) break;
		conductor = conductor->next;
	}
	return 0;
}

 

Може и в началото, тогава трябва да напишеш pushfront.

По същия начин се пише като pushback, ама не е съвсем пом същия начин.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
void pushback(list& a, elem& e)
{
	elem* conductor; // декларирам локален помощен указател
	conductor = a.end; // насочвам помощния указател към последния елемент
	a.end = new elem; // заделям място в хипа за новия елемент и насочвам края на списъка към него
	a.end->prev = conductor; // насочвам привиъс на последния елемент към предпоследния
	a.end->next = 0; // нулирам некст на последния елемент
	a.end->key = e.key; // вкарвам в последния елемент новите данни
	if (conductor !=0) conductor->next = a.end; // насочвам некст на предпоследния елемент към последния
	if (a.start == 0) a.start = a.end; // ако се окаже, че нововъведения елемент е първи и единствен насочвам старт към него
}

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Митко, Митко за никакъв *** не ставаш, ако си мислиш, че ще седна да ти пиша обяснения за всеки ред - много си се объркал.

А това което е написал Реджеп Иведик най-добре той сам да си го коментира ако иска. За мене поголовното използване на безкрайни цикли с break и сравняването на указател с число са лоши практики и трябва да се избягват.

Редактирано от ined (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
на 04/25/2016 at 11:57, ined написа:

Митко, Митко за никакъв *** не ставаш, ако си мислиш, че ще седна да ти пиша обяснения за всеки ред - много си се объркал.

А това което е написал Реджеп Иведик най-добре той сам да си го коментира ако иска. За мене поголовното използване на безкрайни цикли с break и сравняването на указател с число са лоши практики и трябва да се избягват.

Тогава ти защо присвояваш на указателите NULL вместо nullptr?

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.