Поиск числа в однонаправленном списке - Free Pascal
Формулировка задачи:
Доброго дня. Очень хочу разобраться, как работать со списками. Дана задача: создать текстовый файл, записать не менее 15 строк с числами от 0 до 100. Считать эти данные и записать числа в бинарный файл, где на каждое число выделяется по 1 байту. После создать из этих данных ОДНОНАПРАВЛЕННЫЙ ЦИКЛИЧЕСКИЙ список с обеспечением интерактивного поиска числа. Нужна процедура поиска числа с возвратом позиции. У меня получается что в списке два одинаковых числа. Как сделать так, чтобы можно было найти все позиции введенного числа? Помогите.
type
Marker = ^ElementType;
ElementType = record
info: word;
next: Marker
end;
const
PCur: Marker = nil;(*указатель на текущий элемент-при старте программы список пуст*)
var
PFirst: Marker;
n: byte;
f1:text;
f2: file of byte;
v, ercode, i: byte;
s: string;
Procedure AddElement(data: byte);
var
PTemp: Marker;
begin
if PCur = nil then begin
new(PFirst);
PCur:= PFirst;
PCur^.next:= PFirst
end else begin
new(PTemp);
PCur^.next := PTemp^.next;
PCur^.next:= PTemp;
PCur:= PTemp
end;
PCur^.info:= data
end;
function Find(data: byte):byte;
var
PTemp: Marker;
i: byte;
begin
Find := 0;
if PFirst <> nil then
PTemp := PFirst;
for i := 1 to 15 do
if PTemp^.info = data then
begin
Find := i;
exit;
end else
PTemp := PTemp^.next;
end;
begin
Assign(f1, 'numbers.txt');
Rewrite(f1);
for i:=1 to 15 do
begin
str(random(101), s);
writeln(f1,s);
end;
close(f1);
Reset(f1);
Assign(f2, 'numbers.bin');
Rewrite(f2);
While not eof(f1) do
Begin
Readln(f1,s);
val(s, v, ercode);
If ercode = 0 Then Write(f2,v);
if eof(f1) then writeln('12 чисел из файла numbers.txt считаны');
End;
if eof(f2) then writeln('Данные сохранены в файле numbers.bin');
Close(f2);
close(f1);
Writeln('Бинарный файл содержит числа:');
Reset(f2); {открываем второй файл для чтения}
While not eof(f2) do {пока не конец второго файла}
Begin
Read(f2,v);{считываем очередную строку из второго файла}
Write(v, ' '); {выводим строку на экран}
AddElement(v)
End;
writeln;
if eof(f2) then writeln('Список создан');
Close(f2);
writeln('Для выхода введите строку, например stop');
repeat
writeln('Введите искомое число: ');
read(n);
if Find(n) = 0 then
writeln('Числа нет в списке')
else
writeln('Число найдено в позиции:',Find(n))
until false;
end.Решение задачи: «Поиск числа в однонаправленном списке»
textual
Листинг программы
type
Marker = ^ElementType;
Item = word;
ElementType =
record
info: Item;
next: Marker
end;
var
PHead : Marker = nil;
PTail : Marker = nil;
var
n: integer;
f1:text;
f2: file of byte;
v, ercode, i: byte;
s: string;
procedure AddElement(data : Item);
var p : Marker;
begin
new (p);
p^.info := data;
if not Assigned(PHead) then // список пуст
begin
p^.next := p; // Первый элемент указывает сам на себя
PHead := p; // это будет "голова" списка, отсюда начинается обход
end
else
begin
p^.next := PHead; // новый элемент указывает на "голову"
PTail^.next := p;
//PTail := p;
end;
PTail := p; // это будет элемент, после которого добавляются новые элементы
end;
procedure ShowList;
var p : Marker;
begin
if Assigned(PHead) then
begin
p := PHead;
repeat
write(p^.info:4);
p := p^.next;
until p = PHead;
writeln;
end
else writeln('Пусто');
end;
function Find(var From: Marker; data: byte):byte;
var
P: Marker;
i: byte;
begin
Find := 0; i := 0;
if PHead <> nil then
begin
P := PTail;
repeat
inc(i);
p := p^.next;
until p = From;
end;
repeat
if p^.info = data then
begin
Find := i;
From := p^.next;
exit;
end
else
begin
p := p^.next;
inc(i);
end;
until p = pHead;
end;
var
m : Marker;
index, count : byte;
begin
Assign(f1, 'D:\__Volvo\Programs\pascal\numbers.txt');
Rewrite(f1);
for i:=1 to 15 do
begin
str(random(101), s);
writeln(f1,s);
end;
close(f1);
Reset(f1);
Assign(f2, 'D:\__Volvo\Programs\pascal\numbers.bin');
Rewrite(f2);
While not eof(f1) do
Begin
Readln(f1,s);
val(s, v, ercode);
If ercode = 0 Then Write(f2,v);
if eof(f1) then writeln('12 чисел из файла numbers.txt считаны');
End;
if eof(f2) then writeln('Данные сохранены в файле numbers.bin');
Close(f2);
close(f1);
Writeln('Бинарный файл содержит числа:');
Reset(f2); {открываем второй файл для чтения}
While not eof(f2) do {пока не конец второго файла}
Begin
Read(f2,v);{считываем очередную строку из второго файла}
Write(v, ' '); {выводим строку на экран}
AddElement(v)
End;
writeln;
writeln('Список создан: ');
ShowList;
writeln('Поиск (для выхода введите -1) :');
repeat
writeln('Введите искомое число: ');
read(n);
m := PHead; count := 0;
repeat
index := Find(m, n);
if index <> 0 then
begin
writeln('Число найдено в позиции:', index);
inc(count);
end;
until (index = 0) or (m = PHead);
if count = 0 then writeln('Числа нет в списке')
until n = -1;
end.
Объяснение кода листинга программы
- Тип данных Marker используется для хранения указателей на элементы списка.
- Тип данных Item представляет собой слово (4 байта).
- Элемент списка ElementType содержит информацию и ссылку на следующий элемент.
- Переменные PHead и PTail указывают на начало и конец списка соответственно.
- Функция AddElement добавляет новый элемент в список.
- Процедура ShowList выводит все элементы списка на экран.
- Функция Find ищет число в списке и возвращает его позицию.
- Переменные m, index и count используются в цикле поиска числа в списке.
- Файлы f1 и f2 используются для чтения и записи чисел в текстовом и бинарном форматах.
- В цикле While не eof(f1) считываются числа из файла f1 и записываются в файл f2.
- В цикле While not eof(f2) считывается очередная строка из второго файла и выводится на экран, а также добавляется в список.
- После создания списка и ввода искомого числа начинается поиск числа в списке.
- Если число найдено, то выводится его позиция в списке.
- Если число не найдено, то выводится сообщение об этом.
- Для выхода из программы вводится число -1.