Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.09.2022, 16:22   #1
iXNomad
Пользователь
 
Регистрация: 06.01.2021
Сообщений: 31
Радость Придумал алгоритм помогите улучшить

Пытаюсь разобраться с концепцией односвязного списка, задача - "перевернуть" его.
Для этого мне потребовалось аж два вспомогательных указателя. Пока не могу придумать способ лучше.
Только не пишите плиз готовые решения, мне интересно именно подхватить какую-то идею и дальше уже придумать, как сделать

Он работает!!!

Код:
program linkedlistrevesed;
type
	itemptr = ^item;
	item = record
		data: int64;
		next: itemptr;
	end;
var
	p0, p1, p2, p3: itemptr;
	i: int64;

procedure createlist;
begin
	p0 := nil;
	while not SeekEof do begin
		if p0 = nil then begin
			new(p0);
			p1 := p0;
		end else begin
			new(p1^.next);
			p1 := p1^.next;
		end;
		read(i);
		p1^.data := i;
		p1^.next := nil;
	end;
end;

procedure printlist;
begin
	p1 := p0;
	writeln('--------');
	while p1 <> nil do begin
		writeln(p1^.data);
		p1 := p1^.next;
	end;
end;

procedure reverselist;
begin
	if p0 <> nil then begin
		p1 := p0;
		p3 := p1^.next;
		p1^.next := nil;
		while p3 <> nil do begin
			p2 := p1;
			p1 := p3;
			p3 := p1^.next;
			p1^.next := p2;
		end;
		p0 := p1;
	end;
end;

procedure freememory;
begin
	if p0 <> nil then begin
		p1 := p0;
		while p0^.next <> nil do begin
			p1 := p0^.next;
			dispose(p0);
			p0 := p1;
		end;
		dispose(p0);
	end;
end;

begin
	createlist;
	printlist;
	reverselist;
	printlist;
	freememory;
end.
Суть задачи - на вход подаются числа до символа "конец файла", никаких ограничений на количество задавать нельзя.
Нужно вывести весь получившийся односвязный список, потом инвертировать его, и вывести заново.

Меня интересует процедура reverselist.

Моя логика такая: у меня один основной указатель p1 и два вспомогательных p2, p3
сначала я кладу в p3 адрес следующего элемента, а в p2 - текущего
меняю ссылку next так, чтобы она указывала на элемент p2, ну и p3 как раз был нужен чтобы сохранился адрес следующего элемента
и я двигаю p1 к p3, и т.д., циклический процесс, пока не будет NULL (nil).
Изображения
Тип файла: jpg image.jpg (68.7 Кб, 0 просмотров)

Последний раз редактировалось iXNomad; 12.09.2022 в 16:28.
iXNomad вне форума Ответить с цитированием
Старый 12.09.2022, 16:24   #2
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

Про локальные переменные почитайте.
Arigato вне форума Ответить с цитированием
Старый 12.09.2022, 16:35   #3
iXNomad
Пользователь
 
Регистрация: 06.01.2021
Сообщений: 31
По умолчанию

Цитата:
Сообщение от Arigato Посмотреть сообщение
Про локальные переменные почитайте.
Точно, теперь эти два указателя, получается, в стеке хранятся?
Изображения
Тип файла: jpg image.jpg (47.3 Кб, 0 просмотров)
iXNomad вне форума Ответить с цитированием
Старый 12.09.2022, 17:19   #4
macomics
Участник клуба
 
Регистрация: 17.04.2022
Сообщений: 1,833
По умолчанию

Еще можно так, но любитель asm вставок в Pascal у нас в других темах водятся
Код:
asm
  mov rdx, p0
  test rdx, rdx
  jz e
  mov rcx, [rdx + 8]
l:
  jrcxz e
  xchg [rcx + 8], rdx
  xchg rcx, rdx
  jmp l
e:
  mov p0, rdx
end;
Зато так вы не используете дополнительных переменных совсем.

Последний раз редактировалось macomics; 12.09.2022 в 17:25.
macomics вне форума Ответить с цитированием
Старый 12.09.2022, 18:06   #5
iXNomad
Пользователь
 
Регистрация: 06.01.2021
Сообщений: 31
По умолчанию

Цитата:
Сообщение от macomics Посмотреть сообщение
Еще можно так, но любитель asm вставок в Pascal у нас в других темах водятся
Код:
asm
  mov rdx, p0
  test rdx, rdx
  jz e
  mov rcx, [rdx + 8]
l:
  jrcxz e
  xchg [rcx + 8], rdx
  xchg rcx, rdx
  jmp l
e:
  mov p0, rdx
end;
Зато так вы не используете дополнительных переменных совсем.
До ассемблера пока не дошёл((
Но очень интересно. Если это даёт возможность экономить память и увеличивает скорость работы - я только за использование низкоуровневых фишек.
iXNomad вне форума Ответить с цитированием
Старый 12.09.2022, 18:15   #6
macomics
Участник клуба
 
Регистрация: 17.04.2022
Сообщений: 1,833
По умолчанию

Этим надо пользоваться очень осторожно. Оно не совсем экономит память. У вас экономии на переменных много не выйдет. Для глобальных переменных выделяется секция памяти. Минимальный размер секции равен 1 странице памяти. От того, что вы избавитесь от 1, 2 глобальных переменных ничего не изменится. Страницы памяти у процессора фиксированного размера.

А вот скорость работы может обеспечить, но надо использовать вставки в нужных местах и по делу. Особенно это касается использования технологий параллельных вычислений (SIMD - одна инструкция для группы данных сразу).
macomics вне форума Ответить с цитированием
Старый 12.09.2022, 18:22   #7
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Что то не так в моей голове, но, например:
Написали функционал для создания односвязного списка.
Данные для списка получаете из файла и, в цикле, добавляете в список в порядке поступления (функция addList(), например).
Используем полученный список и функционал для переворачивания списка.
Надо, что бы на функционал, формирующий список, данные поступали из исходного списка.
Т.е. использовать функцию чтения списка (readList(), например) а не файла.

Или тут переворачивать надо на месте?

PS: Пример работы со списком приводится в любимой мной книжке: Т.А. Павловская, Программирование на ЯВУ. Паскаль.
Была в списке литературы в соответствующем разделе.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 12.09.2022, 18:42   #8
macomics
Участник клуба
 
Регистрация: 17.04.2022
Сообщений: 1,833
По умолчанию

Еще вариант вашей функции. Попробуйте решить тоже самое с использованием рекурсии.
macomics вне форума Ответить с цитированием
Старый 14.09.2022, 11:22   #9
Алексей_2012
t45t
Участник клуба
 
Аватар для Алексей_2012
 
Регистрация: 20.03.2012
Сообщений: 1,849
По умолчанию

Календарь надо переворачивать было :-D, простите, не удержался
from dark to light)
Алексей_2012 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как сделать чтобы символы пробел и Ентер не записывались? Вот как я придумал но, что-то не работает Aqua77 Общие вопросы C/C++ 4 05.08.2015 03:52
JAXB придумал дьявол Voipp Общие вопросы по Java, Java SE, Kotlin 1 11.10.2013 04:28
так и не придумал Giku Windows 4 11.01.2013 03:57
Улучшить алгоритм нахождения элемента, чаще всего повторяющегося в возрастающем массиве nitrolighter Помощь студентам 6 18.10.2009 13:33
составил программу ,но ненравиться механизм работы.помогите улучшить Василийпрог Помощь студентам 1 23.11.2008 11:38