Давыдов В.Г. - Программирование и основы алгоритмизации - 2003
.pdf// Добавление |
|
элемента |
add |
перед |
элементом |
find |
|
|
||||||
void Before_Add |
( char |
find, |
cba.r |
add |
) |
|
|
|
|
|
||||
{ |
|
|
*temp, |
|
|
// |
Указатель |
на |
|
добавляемый |
элемент |
|||
EL |
|
|
|
|
|
|||||||||
|
|
|
*cur, |
|
|
// |
Указатель |
на |
|
текущий |
элемент |
|||
|
|
|
"^prev; |
|
|
// |
Указатель |
на |
|
элемент |
стоящий |
|||
|
|
|
|
|
|
// |
перед |
текущим) |
|
|
|
|||
±f( |
start |
=- NULL |
) |
|
|
|
|
|
|
|
|
|
||
{ |
printf( |
"\n |
Список |
пуст. |
Нельзя |
найти |
нужный |
" |
||||||
|
||||||||||||||
|
|
|
"элемент |
" ) ; |
|
|
|
|
|
|
|
|||
; |
jretujrn/ |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
содержащих |
символ |
|
find, |
с |
|
добавлением |
|||
// Поиск элементов, |
|
|
|
|||||||||||
// |
перед |
ними |
элемента |
с символом |
add |
|
|
|
||||||
сиг |
= |
start; |
|
|
|
|
|
|
|
|
|
|
|
|
while |
( |
cur |
/- NULL |
) |
|
|
|
|
|
|
|
|
|
|
{ |
// |
Нужный элемент |
найден |
(он |
является |
текущим) |
||||||||
|
||||||||||||||
±f( cur->ch == find )
{
// |
1: |
динамическое |
размещение |
элемента |
|
|||
temp |
= new |
EL; |
) |
|
|
|
||
if( |
temp |
== NULL |
|
|
|
|||
{ |
printf( |
|
"\n |
Элемент списка |
не |
размещен" |
) ; |
|
|
|
|||||||
|
exit |
( 8 |
) ; |
|
|
|
|
|
} |
2: |
занесение |
данных |
|
|
|
||
// |
|
|
|
|||||
temp->ch |
= |
add; |
|
на |
элемент с |
|
||
// |
3: |
новый |
элемент указывает |
|
||||
//символом find
temp->next |
|
= |
cur; |
find |
был |
первым, |
|
// |
4: если |
|
элемент с символом |
||||
// |
то |
start |
смещается влево |
(на |
новый |
элемент) |
|
±£( сиг == |
start |
) |
|
|
|
||
|
start |
= |
temp; |
|
|
|
|
else
// 4: элемент, стоящий перед сиг указывает на
|
|
|
// |
новый |
|
|
||
|
} |
|
prev->next |
|
= temp; |
|
|
|
|
= |
cur; |
|
// |
Продвижение |
текущего и |
||
|
prev |
|
||||||
|
сиг |
= cur->next; |
// |
предыдущего |
элементов |
|||
|
// |
по |
списку |
|
||||
|
} |
|
|
|
|
|
|
|
} |
return; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Удаление |
элемента |
после |
|
элемента |
find |
|
|
void |
After |
Del( |
char |
find |
|
) |
|
|
160
EL |
|
|
*del, |
|
|
// |
|
Указатель |
|
на |
удаляемый |
элемент |
||||||||
|
|
|
|
*сиг; |
|
|
// |
|
Указатель |
|
на |
текущий |
элемент |
|
||||||
±£( |
start |
|
== NULL |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
{ |
|
|
|
|
|
Список |
пуст. |
|
Нельзя |
найти |
нужный " |
|
||||||||
|
|
printf( |
"\n |
|
|
|||||||||||||||
|
|
|
|
"элемент |
" |
) |
; |
|
|
|
|
|
|
|
|
|
|
|||
|
|
jr&bVLJCZi; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
±f( |
start->next |
|
== NULL |
) |
|
|
|
|
|
|
|
|
|
|
||||||
{ |
|
printf |
|
( "\n |
В |
списке |
|
только |
один |
элемент. |
Нельзя |
" |
||||||||
|
|
|
|
|||||||||||||||||
|
|
return/ |
"выполнить |
|
данную |
|
операцию" |
) ; |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
} |
|
Поиск |
элементов,, |
содержащих |
символ |
find,, |
с |
удалением |
||||||||||||
// |
||||||||||||||||||||
// |
элементов |
г |
следуюшр1Х |
за |
|
найденными |
|
|
|
|
||||||||||
сиг |
= |
start; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
do |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
{ |
|
'±f( |
cur->ch |
== find |
|
) |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
найден |
|
(он |
является |
текущем) |
|||||||||||||
|
|
( |
// |
Нужный |
элемент |
|
||||||||||||||
|
|
|
// |
1 : |
указатель |
|
|
на |
элемент |
для |
удаления |
|
||||||||
|
|
|
del |
= |
cur->next; |
|
|
элемента |
с |
|
элементом, |
|
||||||||
|
|
|
// |
2: |
связь |
текущего |
|
|
||||||||||||
|
|
|
// |
|
следуюш;им |
|
за |
|
удаляемым |
|
|
|
|
|||||||
|
|
|
cur->next |
del; |
= |
// |
del->next; |
|
|
элемента |
|
|
||||||||
|
|
|
delete |
|
|
|
3: |
удаление |
|
|
|
|||||||||
|
|
|
// |
4: |
является |
|
ли |
теперь |
текущей |
|
элемент |
и |
||||||||
|
|
|
// |
|
последним? |
|
Если |
"да" |
- |
выход |
из |
цикла |
||||||||
|
|
|
// |
|
|
функции |
== NULL |
) |
|
|
|
|
|
|
|
|||||
|
|
|
±f( |
cur->next |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
геЬит; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
} |
= |
cur->next; |
|
// |
|
Продвижение |
по |
списку |
|
|
||||||||
} |
|
cur |
!= |
|
|
|
||||||||||||||
while( |
cur->next |
NULL |
) |
; |
|
|
|
|
|
|
|
|
||||||||
return; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// Удаление |
элемента |
перед |
|
элементом |
|
find |
|
|
|
|
||||||||||
void. |
Before_Del |
( |
chstr |
find |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|||
{
// Указатель на предпредыдуш:ий элемент по отношению к
//заданному
EL |
|
'*'pprev, |
/ / |
Указатель |
на |
удаляемый |
элемент |
|
|
'*'dei, |
|||||
|
|
*сиг; |
// |
Указатель |
на |
текущий |
элемент |
lf( |
start |
== NULL |
) |
|
|
|
|
{ |
|
|
|
|
|
|
|
161
printf( |
"\n |
Список |
пуст. |
Нельзя |
найти нужный " |
||
|
"элемент |
" |
) ; |
|
|
|
|
} |
|
== |
|
|
|
|
|
±£( start->next |
|
NULL ) |
|
|
|
||
{ |
|
в списке |
только один |
элемент. |
Нельзя " |
||
printf( |
"\n |
||||||
|
"выполнить |
данную |
операцию" ) ; |
|
|||
return/
} |
|
элементов, |
|
содержащих |
символ |
find, |
с |
удалением |
||||
// Поиск |
|
|||||||||||
// |
элементов, |
предшествующих |
найденным |
|
|
|||||||
pprev |
= |
NULL/ |
cur |
= |
start->next/ |
|
|
|
||||
while( |
cur |
!= |
NULL |
) |
|
|
|
|
|
|
||
( |
|
cur->ch |
== |
find |
) |
|
|
|
|
|
||
±f( |
найден |
(он |
является |
|
||||||||
|
{ |
// |
Нужный |
элемент |
|
|||||||
|
|
// |
текущим) |
|
|
|
вторым в ЛС |
|||||
|
|
// |
Найденный |
элемент является |
||||||||
|
|
±f( |
pprev |
== NULL |
) |
|
|
|
|
|||
|
|
{ |
// |
1: |
будем |
удалять |
головной |
элемент |
|
|||
|
|
|
|
|||||||||
|
|
|
del |
= |
|
start/ |
элементом списка |
теперь |
будет |
|||
|
|
|
// |
2: |
первым |
|||||||
|
|
|
// |
|
бывший |
|
второй |
|
|
|
|
|
|
|
|
start |
= |
|
start->next/ |
|
|
|
|||
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
else |
|
|
|
|
|
|
|
|
|
|
|
|
{ |
// |
1: |
указатель |
на удаляемый |
элемент |
|
||||
|
|
|
|
|||||||||
|
|
|
del |
= |
|
pprev->next/ |
|
и |
текущего |
|||
|
|
|
// |
2: |
связь |
предпредыдущего |
||||||
|
|
|
// |
|
|
элементов |
|
|
|
|
||
pprev->next = del->next/
|
} |
|
|
|
|
|
|
|
|
|
delete |
del/ |
// |
Удаление |
элемента |
|
|
||
} |
|
|
|
|
|
|
|
|
|
else |
// |
Продвижение |
указателя |
pprev требуется, |
если на |
||||
{ |
|||||||||
|
// |
|
очередном |
шаге не |
было |
удаления |
элемента |
||
|
±f( |
pprev |
== NULL ) |
|
|
|
|
||
|
|
pprev |
= |
start/ |
|
|
|
|
|
|
else |
|
= pprev->next |
/ |
|
|
|
||
|
|
pprev |
|
|
|
||||
} |
|
|
|
|
|
|
|
|
|
cur |
= |
cur->next/ |
// |
Продвижение |
этого |
указателя |
|||
|
|
|
|
// |
требуется |
всегда |
|
|
|
}
retujm/
}
Файл LS.DAT, из которого программа читает исходные дан ные, имеет следующий вид:
162
1234567890
Результаты выполнения программы выдаются на экран и име ют вид:
1234567890 |
Нельзя |
найти нужный |
элемент |
|
||
Список |
пуст. |
|
||||
Список |
пуст. |
Распечатывать |
нечего |
|
операцию |
|
В списке |
только один |
элемент. |
Нельзя выполнить данную |
|||
С |
|
|
|
|
|
|
0987654321 ABCD
ВС
22222
1212121212
123123123123123
11231123112311231123
1122311223112231122311223
11222231122223112222311222231122223
1122223311222233112222331122223311222233
11222231122223112222311222231122223
12222122221222212222122223
8.3. Добавление элемента в начало списка
Эта операция имеет не только самостоятельное значение, но и может быть использована для создания линейного списка, когда по следний занесенный элемент будет находиться в начале ЛС.
Смысл операции иллюстрирует рис. 46. Прототип функции Add beg, выполняющей добавление элемента в начало списка, ее определение и пример вызова содержатся в вышеприведенном при мере. На данном этапе также рекомендуем из примера рассмотреть только часть программы, которая относится к функции Addjbeg. Ос тальной материал рассмотрим далее, применяя указанный подход.
8.4. Добавление элемента в конец списка
Эта операция, как и предыдущая, имеет, как самостоятельное значение, так и может быть использована для создания линейного списка, когда первый занесенный элемент будет находиться в нача ле ЛС.
Смысл операции иллюстрирует рис. 47. Прототип функции Add_end, выполняющей добавление элемента в конец списка, ее оп ределение и пример вызова содержатся в примере, приведенном ра нее.
163
|
|
До выполнения операции |
|
|
Общий случай |
Особый случай |
|||
|
|
• W NULL |
Start = NULL; |
|
• |
h> |
|
|
|
t Start |
|
|
|
|
|
|
После выполнения операции |
|
|
2: занесение данного «с» |
2 занесение данного «с» |
|||
|
|
• — Н NULL |
NULL |
3: temp->next = |
|
|
Start; |
||
t |
|
|
t |
|
1: динамическое размещение |
1. динамическое размещение |
|||
temp = new EL; |
|
|
||
|
|
temp = new EL; |
||
t |
|
|
||
|
|
t |
|
|
4: Start = temp; |
|
|
4: Start = temp; |
|
Рис. 46. Добавление элемента в начало линейного списка
8.5. Создание ЛС с первым занесенным элементом в начале
Для создания ЛС с первым занесенным элементом в начале списка достаточно в теле цикла вызывать функцию занесения одно го элемента в конец списка с аргументом, представляющим собой очередное прочитанное число. Прототип функции Create_beg, вы полняющей создание списка с первым прочитанным элементом в его начале, определение функции и пример вызова содержатся в приме ре, приведенном выше.
8.6.Создание ЛС с первым занесенным элементом
вконце списка
Эта операция аналогична предыдущей. Для создания ЛС с пер вым занесенным элементом в конце списка достаточно в теле цикла вызывать функцию занесения одного элемента в начало списка с ар гументом, представляющим собой очередное прочитанное число. Прототип функции Create end, выполняющей создание списка с первым прочитанным элементом в его конце, определение функции и пример вызова содержатся в том же примере.
164
|
|
До выполнения операции |
|
|
|
Общий случай |
Особый случай |
||
|
|
NULL |
Start = NULL, |
|
|
• — h > |
|
|
|
t |
Start |
|
|
|
|
|
После выполнения операции |
|
|
|
|
2: |
2: занесение данного « о |
|
|
# |
4в: NULL |
NULL |
3: temp->next = |
|
•^ |
|
NULL; |
|
t |
Start |
t |
t |
|
|
|
1- |
1- |
|
|
|
динамическое размещение temp = new EL; |
||
|
|
t |
t |
|
|
|
46: cur |
|
|
|
|
4B: cur->next = temp; |
4a: Start = temp; |
|
Рис. 47. Добавление элемента в конец списка
8.7. Удаление элемента из начала списка
Данная операция, также как и операции добавления элемента в начало или конец линейного списка, позволяет решить две задачи:
•удаление одного элемента из начала ЛС;
•разрушение линейного списка с освобождением занятой им ди намической памяти путем циклического выполнения операции удаления элемента из начала списка.
Реализация операции, представленная в графической форме,
дана на рис. 48. Прототип функции Del beg, выполняющей удаление первого элемента списка, ее определение и пример вызова содер жатся в программном проекте, приведенном в подразд. 8.1.
165
|
|
До выполнения операции |
|
|
|
Общий случай |
Особые случаи: |
|
|||
|
|
а) в ЛС один элемент |
б) |
||
• — — • ! |
• — ^ > |
• • ^ NULL |
NULL |
Start = NULL; |
|
|
|
||||
I |
I |
|
|
|
|
Start |
|
t |
Start |
|
|
|
|
После выполнения операции |
|
|
|
• ^ NULL
1: del = Start;
t
3: delete del; 2: Start = del->next;
Вывод сообщения и возврат из функции
t
1: del = Start;
t
2: Start = del->next = NULL; 3- delete del;
Рис. 48. Удаление элемента из начала списка
8.8. Удаление элемента из конца списка
Реализация операции, представленная в графической форме, дана на рис. 49. Прототип функции Delend, выполняющей удаление последнего элемента списка, ее определение и пример вызова со держатся в программном проекте, приведенном в подразд. 8.1.
8.9. Разрушение ЛС с освобождением занятой им динамической памяти
Разрушение линейного списка с освобождением занятой им динамической памяти может быть выполнено путем циклического выполнения операции удаления элемента из начала списка.
Прототип функции Destls, выполняющей разрушение списка, ее определение и пример вызова содержатся в программном проек те, приведенном в подразд. 8.1.
166
|
|
До выполнения операции |
|
|
||
|
Общий случай |
|
Особые случаи: |
|
||
|
|
|
|
а) в ЛС один элемент |
б) |
|
|
• — и |
• — — • NULL 1 |
I NULL |
Start = NULL; |
||
|
|
|
||||
t Start |
|
|
|
t Start |
|
|
|
|
После выполнения операции |
|
|
||
L__ |
|
|
|
Вывод сообщения |
||
|
|
|
|
и возврат из |
||
|
NULL |
|
|
функции |
||
t |
t |
|
t |
t |
|
|
start |
1: prev |
end |
1: prev = NULL; |
|
||
|
|
|
|
end |
|
|
|
|
|
2: delete end; 2: delete end; |
|
|
|
|
3 |
prev->next = NULL; |
3: Start = NULL; |
|
||
|
Рис. 49. Разрушение линейного списка |
|
|
|||
8.10. Печать содержимого ЛС
Печать содержимого линейного списка может быть выполнена путем циклического выполнения печати содержимого текущего элемента списка и продвижения по списку от начала до конца. Опе рация тривиальна и не требует особых пояснений.
Прототип функции Printls, выполняющей печать содержимого линейного списка на экран, ее определение и пример вызова содер жатся в программном проекте, приведенном в подразд. 8.1.
8.11. Добавление элемента после каждого элемента ЛС, содержащего заданное значение
Реализация операции, представленная в графической форме, дана на рис. 50.
Прототип функции AfterAdd, выполняющей добавление эле мента с данным add после каждого элемента ЛС, содержащего за данное значение y?«(i, ее определение и пример вызова содержатся в программном проекте, приведенном в подразд. 8.1.
167
До выполнения операции Общий случай
find
|
|
|
w |
,, .^ NULL |
|
t Start |
|
|
|
|
|
|
|
После выполнения операции |
|||
|
|
|
2: |
|
|
|
find |
|
add |
|
|
|
^ |
4: |
3: |
|
NULL |
|
W |
|
• w |
||
|
|
|
|
||
t |
t |
t |
|
|
|
Start |
cur |
1: temp = new EL; |
|
|
|
|
|
2: temp->ch = add; |
|
||
|
|
3: temp->next = cur->next, |
|||
|
|
4. cur->next = temp; |
|
||
|
|
t |
5: cur = temp; |
|
|
Особые случаи
Start = NULL,
Вывод сообщения и возврат из функции
Рис. 50. Добавление элемента после каждого элемента ЯС, содержащего заданное значение
8.12. Добавление элемента перед каждым элементом ЛС, содержащим заданное значение
Реализация операции, представленная в графической форме, дана на рис. 51.
Прототип функции BeforAdd, выполняющей добавление эле мента с данным add перед каждым элементом ЛС, содержащим за данное значение find, ее определение и пример вызова содержатся в программном проекте, приведенном в подразд. 8.1.
8.13. Удаление элемента после каждого элемента ЛС, содержащего заданное значение
Реализация операции, представленная в графической форме, дана на рис. 52.
168
|
|
До выполнения операции |
|
|
||
|
Общий случай |
|
|
|
Особые случаи |
|
|
|
|
find |
|
|
a) Start = NULL; |
•—ь> |
|
|
|
|
NULL |
6) cur = Start; |
|
|
|
|
|
||
t Start |
|
|
|
|
|
|
|
|
После выполнения операции |
|
|||
|
|
2: |
|
|
|
a) Вывод |
|
|
add |
find |
|
|
|
|
|
|
|
сообщения и |
||
• \-> |
|
4: |
3: |
|
NULL |
возврат из |
|
•• W |
' W |
—• |
функции |
||
t |
|
|
|
|
|
б) См. |
prev |
t |
cur |
|
|
реализацию |
|
start |
|
|
шага 4 |
|||
|
1: temp = new EL; |
|
|
|
||
|
|
|
|
|
||
|
|
2: temp->ch = add; |
|
|
|
|
|
|
3: temp->next = cur; |
|
|
||
|
|
T 4: Start = temp при cur = Start |
||||
|
|
или prev->next = temp в остальных |
||||
|
|
случаях |
|
|
|
|
Рис. 51. Добавление элемента перед каждым элементом ЛС, |
||||||
|
содержащим заданное значение |
|
||||
Прототип функции After_Del, |
выполняющей удаление элемен |
|||||
та после каждого элемента ЛС, содержащего заданное значение find, ее определение и пример вызова содержатся в программном проек те, приведенном в подразд. 8.1.
При реализации операции удаления производится просмотр элементов линейного списка, начиная с первого элемента до пред последнего элемента списка.
Отличительной особенностью операции является то, что если после удаления элемента текущий элемент является последним, то необходимо выйти из цикла просмотра элементов и из данной функ ции. Тем самым предотвращается ошибка, связанная с выполнением продвижения в ЯС на следующий элемент сиг — cur->next и после дующей проверкой условия повтора цикла cur->next != NULL.
169