Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11642
Последний выпуск: 19.06.2015

Лекции по программированию на Паскале

40.   Л И Н Е Й Н Ы Е   С П И С К И
    
   В стеки или очереди компоненты можно добавлять только  в  какой  -
либо один конец структуры данных, это относится и к извлечению компо-
нент.
   Связный (линейный) список является структурой данных, в произволь-
но выбранное место которого могут включаться данные, а также изымать-
ся оттуда.
   Каждая компонента списка определяется ключом.  Обычно ключ -  либо
число, либо  строка символов. Ключ располагается в поле данных компо-
ненты, он может занимать как отдельное поле записи, так и быть частью
поля записи.
   Основные отличия связного списка от стека и очереди следующие:
   -для чтения доступна любая компонента списка;
   -новые компоненты можно добавлять в любое место списка;
   -при чтении компонента не удаляется из списка.
   Над списками выполняются следующие операции:
   -начальное формирование списка (запись первой компоненты);
   -добавление компоненты в конец списка;
   -чтение компоненты с заданным ключом;
   -вставка компоненты в заданное место списка (обычно  после  компо-
ненты с заданным ключом);
   -исключение компоненты с заданным ключом из списка.
   Для формирования списка и работы с ним необходимо иметь пять пере-
менных типа указатель,  первая из которых определяет  начало  списка,
вторая - конец списка, остальные- вспомогательные.
   Описание компоненты списка и переменных типа указатель дадим  сле-
дующим образом:

   type
    PComp= ^Comp;
    Comp= record
           D:T;
           pNext:PComp
          end;
   var
    pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

где pBegin - указатель начала списка, pEnd - указатель  конца списка,
pCKey, pPreComp, pAux - вспомогательные указатели.
   Начальное формирование списка, добавление компонент в конец списка
выполняется так же, как и при формировании очереди.

г=====¬     г=====¬    г=====¬       г=====¬    г=====¬    г=====¬
¦  *--¦-¬   ¦ D1  ¦    ¦ D2  ¦       ¦ DN1 ¦    ¦ DN  ¦  --¦--*  ¦
L=====- ¦   ¦=====¦    ¦=====¦       ¦=====¦    ¦=====¦  ¦ L=====-
pBegin  L-->¦  *--¦--->¦  *--¦-....->¦  *--¦--->¦ NIL ¦<--   pEnd
            L=====-    L=====-       L=====-    L=====-
                                                                                                                                                                                                                                                               
   Для чтения  и вставки компоненты по ключу необходимо выполнить по-
иск компоненты с заданным ключом:
    
  pCKey:=pBegin;
  while (pCKey<>NIL) and (Key<>pCKey^.D) DO
   pCKey:=pCKey^.pNext;
   
Здесь Key - ключ, тип которого совпадает с типом данных компоненты.
   После выполнения  этих операторов указатель pСKey будет определять
компоненту с заданным ключом или такая компонента не будет найдена.
   Пусть pCKey определяет компоненту с заданным ключом. Вставка новой
компоненты выполняется следующими операторами:
    
 New(pAux);               г===¬
 pAux^.D:= DK1;        ---¦-* ¦
                       ¦  L===-
                       ¦  pCKey
                       ¦
г===¬     г===¬      г===¬     г===¬      г===¬     г===¬
¦ *-¦--¬  ¦D1 ¦      ¦Key¦     ¦KK1¦      ¦DN ¦  ---¦-* ¦
L===-  ¦  ¦===¦      ¦===¦     ¦===¦      ¦===¦  ¦  L===-
pBegin L->¦ *-¦-...->¦ *-¦---->¦ *-¦-...->¦NIL¦<--  pEnd
          L===-      L===-     L===-      L===-
                                                                                                                                                                                                                                                               
    
                                           г===¬     г===¬
                                           ¦DK1¦  ---¦-* ¦
                                           ¦===¦  ¦  L===-
                                           ¦   ¦<--   pAux
                                           L===-
    
 pAux^.pNext:=pCKey^.pNext;
 pCKey^.pNext:=pAux;
                                         
                          г===¬
                       ---¦-* ¦
                       ¦  L===-
                       ¦  pCKey
                       ¦
г===¬     г===¬      г===¬     г===¬      г===¬     г===¬
¦ *-¦--¬  ¦D1 ¦      ¦Key¦     ¦KK1¦      ¦DN ¦  ---¦-* ¦
L===-  ¦  ¦===¦      ¦===¦     ¦===¦      ¦===¦  ¦  L===-
pBegin L->¦ *-¦-...->¦ * ¦     ¦ *-¦-...->¦NIL¦<--  pEnd
          L===-      L===-     L===-      L===-
                       ¦         ^
                       ¦         ¦          г===¬     г===¬
                       ¦         ¦          ¦DK1¦  ---¦-* ¦
                       ¦         L----------¦===¦  ¦  L===-
                       L------------------->¦-* ¦<--   pAux
                                            L===-
    
    Для удаления компоненты с заданным ключом необходимо при поиске
нужной компоненты помнить адрес предшествующей:

  pCKey:=pBegin;
  while (pCKey<>NIL) and (Key<>pCKey^.D) do
   begin
    pPreComp:=pCKey;
    pCKey:=pCKey^.pNext
   end;
    
Здесь указатель pCKey определяет компоненту с заданным ключом, указа-
тель pPreComp содержит адрес предидущей компоненты.
    
   Удаление компоненты с ключом Key выполняется оператором:

 pPreComp^.pNext:=pCKey^.pNext;
    
                    pPreComp   pCKey
                     г===¬     г===¬
                     ¦ * ¦     ¦ * ¦
                     L===-     L===-
                       ¦         ¦
                       ¦         ¦
                       ¦         ¦
г===¬     г===¬      г===¬     г===¬    г===¬      г===¬     г===¬
¦ *-¦--¬  ¦D1 ¦      ¦KK1¦     ¦Key¦    ¦KK2¦      ¦DN ¦  ---¦-* ¦
L===-  ¦  ¦===¦      ¦===¦     ¦===¦    ¦===¦      ¦===¦  ¦  L===-
pBegin L->¦ *-¦-...->¦ *-¦-¬   ¦ *-¦--->¦ *-¦-...->¦NIL¦<--   pEnd
          L===-      L===- ¦   L===-    L===-      L===-
                           ¦              ^
                           ¦              ¦
                           L---------------
                                                                                                                                                                                                                                                               
   Пример. Составить программу, которая формирует список, добавляет в
него произвольное количество компонент,  выполняет вставку и удаление
компоненты по ключу,  а затем читает и выводит весь список  на  экран
дисплея. В    качестве данных взять строку символов.  Ввод данных - с
клавиатуры дисплея, признак конца ввода - строка символов END.

 Program LISTLINKED;
  uses Crt;
  type
   Alfa= String[10];
   PComp= ^Comp;
   Comp= record
          sD:Alfa;
          pNext:PComp
         end;
  var
   pBegin, pEnd, pAux, pCKey, pPreComp: PComp;
   sC, sKey: Alfa;
   bCond: Boolean;
  Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa);
   begin
    New(pBegin);
    pBegin^.pNext:=NIL;
    pBegin^.sD:=sC;
    pEnd:=pBegin
   end;
  Procedure AddLL(var pEnd: PComp; var sC: Alfa);
   var pAux: PComp;
   begin
    New(pAux);
    pAux^.pNext:=NIL;
    pEnd^.pNext:=pAux;
    pEnd:=pAux;
    pEnd^.sD:=sC
   end;
  Procedure Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp;
                 var bCond: Boolean);
   begin
    pCKey:=pBegin;
    while (pCKey <> NIL) and (sKey <> pCKey^.D) do
     begin
      pPreComp:=pCKey;
      pCKey:=pCKey^.pNext
     end;
    if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE
                                             else bCond:=TRUE
   end;
  Procedure InsComp(var sKey,sC: Alfa);
   var pAux:PComp;
   begin
    Find(sKey,pBegin,pCKey,pPreComp,bCond);
    New(pAux);
    pAux^.sD:=sC;
    pAux^.pNext:=pCKey^.pNext;
    pCKey^.pNext:=pAux
   end;
  Procedure DelComp(var sKey: Alfa; var pBegin: PComp);
   begin
    Find(sKey,pBegin,pCKey,pPreComp,bCond);
    pPreComp^.pNext:=pCKey^.pNext
   end;
  begin
   ClrScr;
   writeln('  ВВЕДИ СТРОКУ ');
   readln(sC);
   CreateLL(pBegin,pEnd,sC);
   repeat
    writeln('ВВЕДИ СТРОКУ ');
    readln(sC);
    AddLL(pEnd,sC)
   until sC='END';
   writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****');
   pAux:=pBegin;
   repeat
    writeln(pAux^.sD);
    pAux:=pAux^.pNext;
   until pAux=NIL;
   writeln;
   writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ');
   readln(sKey);
   writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ');
   readln(sC);
   InsComp(sKey,sC);
   writeln;
   writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ');
   readln(sKey);
   DelComp(sKey,pBegin);
   writeln;
   writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****');
    pAux:=pBegin;
    repeat
     writeln(pAux^.sD);
     pAux:=pAux^.pNext;
    until pAux=NIL
  end.

Часть 1 | Часть 2 | Часть 3 | Часть 4 | Часть 5 | Часть 6

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
57K
23 января 2010 года
Spellofnew
2 / / 23.01.2010
+0 / -1
Мне нравитсяМне не нравится
23 января 2010, 13:33:47
привет всем помогите решить несколько задач на паскале а то ни как не получается заранее спасибо
1) Дана последовательность действительных чисел а1,а2,...аn.Выяснить будет ли она возрастающей.
2)Составить программу ,которая выводит True, если в строке буква A встречается чаще, чем буква B, и False в противном случае.
3)Пусть дана символьная квадратная матрица порядка 10. Замените буквой а все её элементы расположенные выше главной диагонали.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог