Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Простой вопрос по односвязным спискам / 21 сообщений из 21, страница 1 из 1
22.11.2012, 00:15
    #38047948
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Всем привет!
Читаю статью где объясняется односвязный список.
из статьи
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
struct address {
  char name[40];
  char street[40];
  char city[20];
  char state[3];
  char zip[11];
  struct address *next; /* ссылка на следующий адрес */
} info;


Приведенная ниже функция slstore() создает односвязный список путем помещения каждого очередного элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address, содержащую новую запись, и указатель на последний элемент списка. Если список пуст, указатель на последний элемент должен быть равен нулю.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
void slstore(struct address *i,
             struct address **last)
{
  if(!*last) *last = i; /* первый элемент в списке */
  else (*last)->next = i;
  i->next = NULL;
  *last = i;
}


Я не могу понять, почему в качестве указателя на последний элемент списка, передается указатель на указатель [**last], а не просто указатель [*last]?
Заранее спасибо за любые подсказки!
...
Рейтинг: 0 / 0
22.11.2012, 00:32
    #38047968
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_Gпочему в качестве указателя на последний элемент списка, передается
указатель на указатель [**last], а не просто указатель [*last]?

Потому что его изменять надо. А для этого его надо передавать по ссылке. Что и делается.
RTFM способы передачи параметров.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.11.2012, 00:51
    #38047982
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Dimitry SibiryakovMaximuS_Gпочему в качестве указателя на последний элемент списка, передается
указатель на указатель [**last], а не просто указатель [*last]?

Потому что его изменять надо. А для этого его надо передавать по ссылке. Что и делается.
RTFM способы передачи параметров.

Спасибо! Сорри, я не вьезжаю... Я вот что-то такое пытаюсь соорудить, но естественно не получается:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
void slstore(struct address *i, struct address **last)
{
	if(!*last) *last = i; /* первый элемент в списке */
	else (*last)->next = i;
	i->next = NULL;
	*last = i;
}

int main()
{
	struct address {
		char name[40];
		char street[40];
		char city[20];
		char state[3];
		char zip[11];
		struct address *next; /* ссылка на следующий адрес */
	} info;

	address info_new;
	slstore(&info_new, &&info);
	return 0;
}


Вот это явно бред
Код: plaintext
1.
slstore(&info_new, &&info);


Я даже не понимаю, почему тут
Код: plaintext
1.
void slstore(struct address *i, struct address **last)


объявлено, [struct address *i], а не [address *i].
...
Рейтинг: 0 / 0
22.11.2012, 01:09
    #38047993
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_G
Код: sql
1.
address info_new;


Должно быть
Код: sql
1.
address* info_new;


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.11.2012, 01:20
    #38048002
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Dimitry Sibiryakov,
ага, так яснее немного.
Если объект создается так:
Код: plaintext
1.
address object;


под него сразу выделяется память
если так
Код: plaintext
1.
address *object;


то выделяется 1 байт на указатель, а под сам объект не выделяется, так?
Я просто пытаюсь понять, зачем создавать указатель на объект и передавать указатель на указатель, а не создать объект и передать просто указатель на него?
...
Рейтинг: 0 / 0
22.11.2012, 01:55
    #38048017
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_G,

Элементы списка не могут быть созданы в виде локальных экземпляров структуры (так как у них время жизни - до окончания блока {} в котором они объявлены).
Это должны быть выделенные в динамической памяти (т.е. глобальные) экземпляры (через new если это в С++). А new возвращает указатели - поэтому список работает с указателями.

Вам надо объявить указатель на последний элемент списка, инициализированным 0, и передавать его адрес вторым аргументом в slstore. А первым аргументом - передавать созданный через new экземпляр элемента списка (перед этим при необходимости заполнить его поля нужными данными).

Правда функция slstore немного корявенько написана, можно сократить кое-что, добавтьь пару проверок, но в принципе - все должно работать.

ЗЫ. Указатель занимает не 1 байт, а машиное слово - обычно 4 или 8 байтов.
...
Рейтинг: 0 / 0
22.11.2012, 09:55
    #38048176
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_G,

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

На самом деле конечно так уже никто списки не делает, принято отделять реализацию списка от хранимых в списке данных.
...
Рейтинг: 0 / 0
22.11.2012, 10:12
    #38048205
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Вообще, это С-шный код, на С++ этот указатель на указатель был бы ссылкой на указатель, и все было бы проще. Это в наивной копии С-шного кода так бы было.
А в нормальной реализации списка обе переменные (указатели на голову и хвост) были бы спрятаны в класс, и функция была бы методом.
...
Рейтинг: 0 / 0
22.11.2012, 12:52
    #38048551
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Anatoly MoskovskyMaximuS_G,

Элементы списка не могут быть созданы в виде локальных экземпляров структуры (так как у них время жизни - до окончания блока {} в котором они объявлены).
Это должны быть выделенные в динамической памяти (т.е. глобальные) экземпляры (через new если это в С++). А new возвращает указатели - поэтому список работает с указателями.

Вам надо объявить указатель на последний элемент списка, инициализированным 0, и передавать его адрес вторым аргументом в slstore. А первым аргументом - передавать созданный через new экземпляр элемента списка (перед этим при необходимости заполнить его поля нужными данными).

Правда функция slstore немного корявенько написана, можно сократить кое-что, добавтьь пару проверок, но в принципе - все должно работать.

ЗЫ. Указатель занимает не 1 байт, а машиное слово - обычно 4 или 8 байтов.
Спасибо большое за разъяснение!
Почему нужно создавать именно указатель я понял теперь, я просто не додумался, что элементы созданные не через new (я так понимаю их можно называть локальными экземплярами структуры), будут удалены при завершении блока.
Сейчас дальше пробую по порядку. Например, у меня есть уже какие-то элементы списка, и я хочу новый добавить. Тут я так понимаю, я делаю так
А первым аргументом - передавать созданный через new экземпляр элемента списка (перед этим при необходимости заполнить его поля нужными данными).
Код: plaintext
1.
2.
address *info_new = new address;
info_new->name = "New_Instance";


На второй строчке получаю ошибку - Expression must be a modifiable value.
Вам надо объявить указатель на последний элемент списка, инициализированным 0, и передавать его адрес вторым аргументом в slstore.
То есть просто указатель объявить на структуру? Или ему надо как-то присвоить адрес последнего элемента списка? И как его инициализировать нулем? Так?
Код: plaintext
1.
address *last = new address; last = 0;


Заранее спасибо!
...
Рейтинг: 0 / 0
22.11.2012, 12:54
    #38048560
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MasterZivВообще, это С-шный код, на С++ этот указатель на указатель был бы ссылкой на указатель, и все было бы проще
Спасибо за комментарий! Я учу именно C++, можете показать, как это было бы реализовано на этом языке?
...
Рейтинг: 0 / 0
22.11.2012, 13:18
    #38048606
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_GА первым аргументом - передавать созданный через new экземпляр элемента списка (перед этим при необходимости заполнить его поля нужными данными).
Код: plaintext
1.
2.
address *info_new = new address;
info_new->name = "New_Instance";


На второй строчке получаю ошибку - Expression must be a modifiable value.
Вам надо объявить указатель на последний элемент списка, инициализированным 0, и передавать его адрес вторым аргументом в slstore.
То есть просто указатель объявить на структуру? Или ему надо как-то присвоить адрес последнего элемента списка? И как его инициализировать нулем? Так?
Код: plaintext
1.
address *last = new address; last = 0;



Код: plaintext
1.
2.
address *info_new = new address;
strcpy(info_new->name, "New_Instance"); // уже забыли что было в соседних ваших темах ?:)


Код: plaintext
1.
address *last = 0;  // в начале, когда список пустой никаких объектов еще нет
...
Рейтинг: 0 / 0
22.11.2012, 14:16
    #38048754
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Спасибо!
Anatoly Moskovsky// уже забыли что было в соседних ваших темах ?:)
Скорее не до конца разобрался). Я думал использовать strcpy , но не понимал почему. Еще раз вернусь к этой теме, когда закончу с этими списками :)
Я так понимаю, так как Вы написали
Код: plaintext
1.
address *last = 0;


и так как я
Код: plaintext
1.
2.
address *last = new address; 
last = 0;


разницы нету?

Теперь все таки остался вопрос, который я не могу понять, это зачем передавать один объект по указателю (новый объект), а второй объект (последний в списке) как-то через указатель на указатель?
Код: plaintext
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.
void slstore(struct address *i, struct address **last)
{
	if(!*last) *last = i; /* первый элемент в списке */
	else (*last)->next = i;
	i->next = NULL;
	*last = i;
}

struct address {
	char name[40];
	char street[40];
	char city[20];
	char state[3];
	char zip[11];
	struct address *next; /* ссылка на следующий адрес */
};

int main()
{
	address *info_new = new address;
	address *last = 0;
	strcpy(info_new->name,"New_Instance");
	slstore(info_new, &&info); //как тут передать last?
	return 0;
}


И почему в функции slstore параметры описаны как struct address , а не просто address , тоже не ясно :(.
Код: plaintext
1.
void slstore(struct address *i, struct address **last)
...
Рейтинг: 0 / 0
22.11.2012, 15:20
    #38048918
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_GСпасибо!
Я так понимаю, так как Вы написали
Код: plaintext
1.
address *last = 0;


и так как я
Код: plaintext
1.
2.
address *last = new address; 
last = 0;


разницы нету?

Здрасте. В первом случае ничего не создается, просто объявлен пустой указатель.
Во втором - создается объект в куче, и единственный указатель на него затирается нулем, т.е. - это утечка памяти.

авторТеперь все таки остался вопрос, который я не могу понять, это зачем передавать один объект по указателю (новый объект), а второй объект (последний в списке) как-то через указатель на указатель?
Второй аргумент - это не последний объект, а сам указатель на него. Функция его изменяет - поэтому передается адрес.
авторИ почему в функции slstore параметры описаны как struct address , а не просто address , тоже не ясно :(.

struct это синтаксис С, а С++ разрешает его опускать при объявлении переменных на основе ранее объявленных структур.
...
Рейтинг: 0 / 0
22.11.2012, 15:31
    #38048937
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Прочтите уже наконец какую-нибудь книгу.
Сначала по С, по том по С++.
...
Рейтинг: 0 / 0
22.11.2012, 18:46
    #38049416
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Anatoly MoskovskyПрочтите уже наконец какую-нибудь книгу.
Сначала по С, по том по С++.
Мне кажется, у Вас уже закончилось терпение, хотя я почти разобрался.
Вот здесь
Anatoly MoskovskВторой аргумент - это не последний объект, а сам указатель на него. Функция его изменяет - поэтому передается адрес.
Вы вот это имели ввиду (сделал для себя проще пример для понимания)?
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
void change_object(address** object_p)
{
	address *object2 = new address;
	strcpy(object2->name,"B");
	*object_p = object2;
}

int main()
{
	address *info_new = new address;
	strcpy(info_new->name,"A");
	cout<<info_new->name;
	
	change_object(&info_new);
	cout<<info_new->name;
	return 0;
}


До вызова функции change_object() , указатель info_new указывает на объект с именем "A" - cout<<info_new->name == "A" , после вызова, указывает на объект с именем "B" - cout<<info_new->name == "B" .
struct это синтаксис С, а С++ разрешает его опускать при объявлении переменных на основе ранее объявленных структур.
Ага, сорри тогда за глупый вопрос. Я учу С++, и в C вообще не заинтересован.
Здрасте. В первом случае ничего не создается, просто объявлен пустой указатель.
Во втором - создается объект в куче, и единственный указатель на него затирается нулем, т.е. - это утечка памяти.
М-да, это я что-то тормознул :). А разница между такими объявлениями:
Код: plaintext
1.
address *info;


и
Код: plaintext
1.
address *info = 0;


большая?
...
Рейтинг: 0 / 0
22.11.2012, 18:52
    #38049431
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
PS. С++ я учу не для того, что бы программировать на нем, хотя что-то не сложное не исключено. Я работаю продакт менеджером, немного пишу на JavaScript, экономическое образование. Что бы иметь более профессиональные навыки, пошел еще учиться в академию "ШАГ", хотя особой надобности нет, там и познакомился с С++. К сожалению, книги читать по С++, совсем времени нет, еле успеваю делать домашнее задания.
...
Рейтинг: 0 / 0
23.11.2012, 01:54
    #38049777
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Итак, я кажется все понял :). Напишу для таких же тугодумов как я, если кто-то будет пытаться выучить похожее.
И так, почему передается последний элемент через указатель на указатель. Это можно понять по следующему примеру:
Код: plaintext
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.
struct address {
	char name[40];
};

void change_object(address* object_p) // здесь передается ОБЪЕКТ по указателю,
{
        cout<<object_p->name; //по этому можно вывести его имя сразу же	
        address *object2 = new address;
	strcpy(object2->name,"B");
        object_p = object2;
}

void change_object(address** object_p) //здесь передается УКАЗАТЕЛЬ на объект
{
        cout<<(*object_p)->name; // поэтому, что бы получить значение его полей, его нужно разыменовать
	address *object2 = new address;
	strcpy(object2->name,"B");
	*object_p = object2;
}

int main()
{
	address *info_new = new address;
	strcpy(info_new->name,"A");

	change_object(info_new);
	cout<<info_new->name; // выведет А

	change_object(&info_new);
	cout<<info_new->name; // выведет B
        
        return 0;
}
...
Рейтинг: 0 / 0
23.11.2012, 02:14
    #38049785
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
MaximuS_GА разница между такими объявлениями:
Код: plaintext
1.
address *info;


и
Код: plaintext
1.
address *info = 0;


большая?
Если это объявление локальной переменной, то без инициализации там случайное число (мусор).
Если это неинициализированая глобальная переменая, то там будет 0.
...
Рейтинг: 0 / 0
23.11.2012, 02:18
    #38049787
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Прежде чем делать так
Код: plaintext
1.
*object_p = object2;


надо сначала удалить старый объект, иначе бедет утечка памяти
Код: plaintext
1.
2.
delete *object_p; //  если указатель==0, то delete ничего не делает
*object_p = object2;
...
Рейтинг: 0 / 0
23.11.2012, 02:20
    #38049788
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Насколько я смог узнать, чем полезен односвязный список, так это тем, что он позволяет вставить новый объект на любую позицию, и при этом изменить только 2 указателя (в объекте, на место которого вставляется новый объект, и в новом объекте). Для того, что бы вставить объект в массив объектов, нужно двигать все элементы начиная с позиции, на которую вставляется объект.
Вот моя реализация функции добавления объекта на любую позицию, кроме последней и первой (это допилю завтра) - putInMiddle . Думаю фукнция кривовата, но написана самостоятельно.
Код: plaintext
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.
void putInMiddle(address* first_object, address* new_object, int position)
{
	address *temp_pointer;
	
	temp_pointer = first_object;
	if(position-1!=1)
		for (int i=0;i<position-1;i++)
		{
			if (i==0)

				temp_pointer = first_object->next;
			temp_pointer->name;
		}
	new_object->next = temp_pointer->next;
	temp_pointer->next = new_object;
}

void display_objects(address* object)
{
	cout<<object->name<<" ";
	if (object->next)
		display_objects(object->next);
}

int main()
{	
	address *last =0;             // создали указатель на последний элемент, пока пустой
	address *obj1 = new address;  // создали указатель на первый элемент списка 
	
	strcpy(obj1->name,"Obj1");
	address *obj2 = new address;
	strcpy(obj2->name,"Obj2");
	address *obj3 = new address;
	strcpy(obj3->name,"Obj3");
	address *obj4 = new address;
	strcpy(obj4->name,"Obj4");

	slstore(obj1,&last);
	slstore(obj2,&last);
	slstore(obj3,&last);

	display_objects(obj1); //Obj1 Obj2 OBj3
	cout<<"\n";
	putInMiddle(obj1,obj4,2);
	display_objects(obj1); //Obj1 Obj4 OBj2 OBj3
	cout<<"\n";

	system("pause");
	return 0;
}
...
Рейтинг: 0 / 0
23.11.2012, 11:07
    #38050111
MaximuS_G
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Простой вопрос по односвязным спискам
Anatoly MoskovskyMaximuS_GА разница между такими объявлениями:
Код: plaintext
1.
address *info;


и
Код: plaintext
1.
address *info = 0;


большая?
Если это объявление локальной переменной, то без инициализации там случайное число (мусор).
Если это неинициализированая глобальная переменая, то там будет 0.
Спасибо большое за объяснения!
Anatoly Moskovskyнадо сначала удалить старый объект, иначе бедет утечка памяти
Спасибо за подсказку, я еще просто не привык сразу видеть такое, когда сфокусирован на том, что бы просто сделать пример, а не полноценную программу.
Удачи! :)
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Простой вопрос по односвязным спискам / 21 сообщений из 21, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]