Списки

[GippoRex]

Вопрос относительно алгоритма создания односвязного динамического списка (очереди). Я понимаю общее построение списков, но... Относительно реализации этого в коде у меня крайние сомнения (примеры, которые я нагуглила, мне не помогают; общий смысл мне и так ясен).
Например, у меня такая задача: пользователь вводит произвольное число имен, из которых мне надо сделать список. Можете проверить ход моих размышлений?

struct dude  //элемент списка
	{
		char name[20];
		dude *next;
	};
dude *first, *p;    //вспомогательные указатели
...
first = new dude;   //создаю новый элемент
gets(first->name);   //присваиваю полю элемента значение
first->next = NULL;  //указатель на следующий элемент пока нулевой

Это я создала первый элемент очереди. Но что дальше? Можно уже устроить цикл с условием? Однако ж присваивание указателю next у first'а будет единичным, а для этого надо создать еще один элемент списка, и все это до цикла...

p = new dude;
gets(first->name);
p->next=NULL;
first->next=p; // теперь есть первый элемент, его next указывает на р, next p'а будет вести в никуда 

Теперь, по идее, я могу завести цикл для создания произвольного количества элементов списка. Но я в нем путаюсь.

do
	{
		p->next = p;    //смещаем указатель на уже 3-й элемент в списке
		p = new dude;
		gets(p->name);
		p->next = NULL;
		puts("Next? Y/N"); // спрашиваем у пользователя, добавить ли еще один элемент в список
		scanf("%c", &key);
                if ((key=='n') || (key=='N'))
                      nextflag = false;     
	} while (nextflag==true);

Честно, я как-то с плеча делаю этот цикл. Особенно строчку "p->next = p;" Я ведь просто перемещаю указатель, так? И p->next = p (= NULL), так? Или нет?

@темы: C++

Comments

[Скептичный циник]

Я так предполагаю, это односвязный список?

Чтобы не путаться, нужно ввести три переменных:
curr – указатель на текущего чувака, в который будет писаться имя, и указатель на который будет прилепляться к списку
begin – самый первый чувак
end – крайник чувак

Тогда добавление нового чувака (не в начало списка) будет феерично простым:

cur = new Dude;
cur->name = "Lebowsky";
end->next = cur;
end = cur;
end->next = NULL;


А у вас в последнем куске кода каша из-за того, что используете одно и то же имя переменной p и не хватает третьей переменной-"кэша".

у списка будет три состояния: нет записей, есть одна запись, и есть много записей. все три состояния нужно учитывать внутри цикла проверками.
p->next = p; - это указатель на самого себя. в переменной next записан адрес переменной р, который не равен NULL или равен NULL, зависит от предыдущих действий над ним.

вообще, очередь не предполагает произвольного доступа к элементам. мы добавляем в конец и забираем в начале. т.е. нам нужны постоянные указатели на начало и конец очереди (которые могут указывать на один единственный элемент, либо на NULL, если элементов нет), и дополнительный указатель на текущий создаваемый элемент. Общий алгоритм добавления: создаем новый элемент, наполняем его инфой, и в конце перенаправляем на него указатель на конец очереди и указатель next бывшего последнего элемента.

[tven]

ninelya, вы сами написали

т.е. нам нужны постоянные указатели на начало и конец очереди ..., и дополнительный указатель на текущий создаваемый элемент

а это как раз три переменные, о которых говорил товарищ выше.
Кстати говоря, установка указателя следующего элемента на самого себя — крайне неудачная идея. Обычно его ставят всё-таки в NULL.

tven,
ну, коммент товарища выше я увидела после публикации своего, так что извиняюсь за тавтологию

[GippoRex]

Черт, забыла подписаться
Спасибо большое за ответы! Вы мне сильно помогли.