Печать страницы - Проблемы с двухсвязным списком[РЕШЕНО]

Название: Проблемы с двухсвязным списком[РЕШЕНО]
Отправлено: Larry от Январь 08, 2012, 15:48

Доброе утро, форумчане! Помогите решить проблему. Есть функция добавления элементов в двухсвязный список

Код:

void add_link(char *name, link *item, link *parent)
{
    link *menu = NULL;
    menu = new link;
    if(menu == NULL)
    {
        std::cout << "Error" << std::endl;
        return NULL;
    }
    strcpy_s(menu->name, name);
    link *ptr = item;
    int count = 0;
    if(parent == NULL)
    {
        if(ptr == NULL)
        {
            menu->next = NULL;
            menu->previous = NULL;
        }
        else
        {
            link *last = NULL;
            while(ptr != NULL)
            {
                last = ptr;
                
                ptr = ptr->next;
            }
            menu->next = NULL;
            menu->previous = last;
        }
    }
    ptr = menu;
}

Но при вызове функции она возвращает пустой указатель. А если переписать ф-цию так

Код:

link* add_link(char *name, link *item, link *parent)
{
    link *menu = NULL;
    menu = new link;
    if(menu == NULL)
    {
        std::cout << "Error" << std::endl;
        return NULL;
    }
    strcpy_s(menu->name, name);
    link *ptr = item;
    int count = 0;
    if(parent == NULL)
    {
        if(ptr == NULL)
        {
            menu->next = NULL;
            menu->previous = NULL;
            //ptr = menu;
        }
        else
        {
            link *last = NULL;
            while(ptr != NULL)
            {
                last = ptr;
                
                ptr = ptr->next;
            }
            menu->next = NULL;
            menu->previous = last;
        }
    }
    ptr = menu;
    return ptr;
}

то все работает, только конечно возвращает указетель на конец списка. Объясните где ошибка?

Название: Re: Проблемы с двухсвязным списком
Отправлено: Igors от Январь 08, 2012, 16:34

Если Вы сказали что список двухсвязный, то должны быть его "голова" и "хвост"

Код

C++ (Qt)
void Add2List(link * item, link * prevItem, link *& head, link *& tail)
{
 item->previous = prevItem; 
 
 item->next = prevItem ? prevItem->next : head;
 if (item->next) item->next->previous = item;
 else tail = item; 
 
 if (!prevItem) head = item;
 else prevItem->next = item;
}

Лучше упаковать в класс (head и tail явно members)

Название: Re: Проблемы с двухсвязным списком
Отправлено: Larry от Январь 08, 2012, 22:23

Извините, но не смог ответить раньше. Спасибо, но в класс оборачивать не буду, т.к. это под микроконтроллер меню. Это даже не двухсвязный, а четырех:)..А обязательно иметь и голову и хвост? Можно ведь иметь только голову и дальше по указателям прыгать...

Название: Re: Проблемы с двухсвязным списком
Отправлено: andrew.k от Январь 08, 2012, 22:42

Цитата: Larry от Январь 08, 2012, 22:23

Тогда это не будет двусвзязный список)

Название: Re: Проблемы с двухсвязным списком
Отправлено: BRE от Январь 08, 2012, 22:47

Цитата: andrew.k от Январь 08, 2012, 22:42

Тогда это не будет двусвзязный список)

Почему?
Двусвязный означает что каждый элемент знает предыдущий и следующий элемент.

Название: Re: Проблемы с двухсвязным списком
Отправлено: Larry от Январь 08, 2012, 22:55

Цитата: BRE от Январь 08, 2012, 22:47

Цитата: andrew.k от Январь 08, 2012, 22:42

Тогда это не будет двусвзязный список)

Почему?
Двусвязный означает что каждый элемент знает предыдущий и следующий элемент.

Вот я тоже так думаю:). А все-таки почему в передаваемом указателе ничего не сохраняется? В чем ошибка?

Название: Re: Проблемы с двухсвязным списком
Отправлено: mutineer от Январь 09, 2012, 00:33

Пардон, может я что не вкурил, но
1) с какими парметрами вызов функции происходит?
2) как void функция может возвращать пустой указатель?

Название: Re: Проблемы с двухсвязным списком
Отправлено: Larry от Январь 09, 2012, 00:41

это я обшибся при написании сообщения...в данном случае я передаю указатель link *item, где и хранится список. Но после вызова ф-ции он пустой...

Название: Re: Проблемы с двухсвязным списком
Отправлено: mutineer от Январь 09, 2012, 00:47

Есть как минимум одна ошибка - отсутствует last->next = menu;
Как я понимаю список передается не пустой в item?

Название: Re: Проблемы с двухсвязным списком
Отправлено: Larry от Январь 09, 2012, 01:16

Цитата: mutineer от Январь 09, 2012, 00:47

Есть как минимум одна ошибка - отсутствует last->next = menu;
Как я понимаю список передается не пустой в item?

перед тем, как прочитал ваше сообщение ее и нашел ;D...оказалось три ошибки ;D
Рабочая функция выглядит так:

Код:

void add_link(char *name, link **item, link *parent)
{
	link *menu = NULL;

	menu = new link;

	if(menu == NULL)
	{
		std::cout << "Error" << std::endl;
		return;
	}

	strcpy_s(menu->name, name);

	link *ptr = *item;

	if(parent == NULL)
	{
		if(ptr == NULL)
		{
			menu->next = NULL;
			menu->previous = NULL;

			*item = menu;
		}
		else
		{
			link *last = NULL;

			while(ptr != NULL)
			{
				last = ptr;
				
				ptr = ptr->next;
			}

			menu->next = NULL;
			menu->previous = last;

			last->next = menu;
		}
	}
}

Спасибо за ответы...Подскажите пожалуйста почему при передаче указателя на структуру link *item функция не работает, а при передаче указателя на указатель link **item все нормально...чего-то не могу сообразить?

Название: Re: Проблемы с двухсвязным списком
Отправлено: andrew.k от Январь 09, 2012, 01:18

Цитата: BRE от Январь 08, 2012, 22:47

Цитата: andrew.k от Январь 08, 2012, 22:42

Тогда это не будет двусвзязный список)

Почему?
Двусвязный означает что каждый элемент знает предыдущий и следующий элемент.

Видимо я не правильно понял, что имелось в виду.

Каждый элемент знает следующий и предыдущий, какой смысл делать исключение для крайних? Об этом речь?

Название: Re: Проблемы с двухсвязным списком
Отправлено: andrew.k от Январь 09, 2012, 01:22

Цитата: Larry от Январь 09, 2012, 01:16

Потому что в одном случае ты передаешь указатель по значению и присваиваешь его внутри функции и наружу значение не попадает. Во втором ты передаешь указатель на указатель, поэтому можешь менять значение указателя и получать результат.

Можешь передавать указатель по ссылке (link * &item). Мне, например, так больше нравится)
Хотя наверное это не распространенная конструкция и закаленные сишники будут возражать)

Название: Re: Проблемы с двухсвязным списком[РЕШЕНО]
Отправлено: Larry от Январь 09, 2012, 02:00

Спасибо большое за ответы, очень помогли...

Название: Re: Проблемы с двухсвязным списком
Отправлено: Igors от Январь 09, 2012, 14:05

Цитата: Larry от Январь 09, 2012, 01:16

Рабочая функция выглядит так:

Код:

void add_link(char *name, link **item, link *parent)
{
	link *menu = NULL;

	menu = new link;

	if(menu == NULL)
	{
		std::cout << "Error" << std::endl;
		return;
	}

	strcpy_s(menu->name, name);

	link *ptr = *item;

	if(parent == NULL)
	{
		if(ptr == NULL)
		{
			menu->next = NULL;
			menu->previous = NULL;

			*item = menu;
		}
		else
		{
			link *last = NULL;

			while(ptr != NULL)
			{
				last = ptr;
				
				ptr = ptr->next;
			}

			menu->next = NULL;
			menu->previous = last;

			last->next = menu;
		}
	}
}

Если parent != NULL, то созданный menu просто уплывет, будет утерян. Не видно зачем вообще подавать параметр parent

У Вас есть previous, но Вы добавляете в хвост пробегаясь до него (как обычно делают для односвязного списка). Тогда лучше смотрится так

Код

C++ (Qt)
// использование
menu = AppendMenu(menu, CreateItem("name")); 
 
// добавление в хвост
link * AppendMenu( link * menu, link * item )
{
 item->previous = item->next = 0;  // это лучше сделать в CreateItem
 if (!menu) return item;
 
 link * last = menu;
 while (last->next) 
  last = last->next;
 
 last->next = item;
 item->previous = last;
 return menu;
}

Название: Re: Проблемы с двухсвязным списком[РЕШЕНО]
Отправлено: KontAr от Март 24, 2012, 12:30

случайно забрел, но если нужен 4-связный список для контроллера, то может вот это может помочь: http://easyelectronics.ru/organizaciya-drevovidnogo-menyu.html#more-316

Russian Qt Forum

Программирование => С/C++ => Тема начата: Larry от Январь 08, 2012, 15:48