1. Вставка элемента в начало односвязного списка.
Вставим в начало данного списка элемент, информационное поле которого содержит переменную D. Чтобы это осуществить, необходимо произвести следующие действия :
а) Создать пустой элемент, на который указывает указатель p.
b) Информационному полю созданного элемента присвоить значение D.
с) Связать новый элемент со списком.
Ptr(p)=lst (lst - уже не указывает на начало списка)
d) Перенести указатель lst на начало списка.
Окончательно:
2. Удаление элемента из начала односвязного списка
Удалим 1-й элемент списка, но при этом запомним информацию, содержащуюся в поле info этого элемента.
Чтобы это осуществить, необходимо произвести следующие действия :
a) Ввести указатель р, который будет указывать на удаляемый элемент.
P=lst
b) Запомнить поле info элемента, на который ссылается указатель р, в некоторую переменную (х).
X=info( P )
c) Перенести указатель lst на новое начало списка.
lst=ptr( P )
d) Удалить элемент на который указывает указатель р.
Freenode( P )
Окончательно:
3. Вставка элемента в список
Вставим в данный список после элемента на который указывает указатель р, элемент с информационным полем х.
х. 
Чтобы это осуществить, необходимо произвести следующие действия :
a) Создать пустой элемент на который указывает указатель q.
Q=getnode
b) Внести х в информационное поле созданного элемента.
Info(Q)=x
c) Связать элемент х с элементом В.
Ptr(Q)=Ptr(P) - это значит, что указателю созданного элемента присваивается значение указателя элемента р.
d) Связать элемент А с элементом х.
Ptr(p)=Q - это значит, что следующим за элементом А будет элемент на который указывает указатель Q.
Окончательно:
4. Удаление элемента из односвязного списка
Удалим из списка элемент, который следует за элементом с рабочим указателем р.
Чтобы это осуществить необходимо произвести следующие действия :
a) Ввести указатель Q, который будет указывать на удаляемый элемент.
Q=ptr(p)
b) Поставить за элементом А элемент В.
Ptr(p)=Ptr(Q)
с) Запомнить информацию, которая содержится в поле info удаляемого элемента.
K=info(Q)
d) Удалим элемент с указателем Q.
Freenode(Q)
Окончательно:
Кольцевые списки
Пример кольцевого списка представлен на следующем рисунке.
На этом рисунке, список замыкается в своеобразное "кольцо": двигаясь по ссылкам, можно от последнего элемента списка переходить к заглавному элементу. В связи с этим списки подобного рода называют кольцевыми списками.
Чтобы закольцевать список необходимо присвоить указателю последнего элемента указатель начала списка (Ptr(p)=lst).
p - указатель последнего элемента;
Lst - указатель начала списка.
Операции с кольцевыми списками:
1. Вставка элемента в кольцевой список
Чтобы осуществить эту операцию необходимо произвести следующие действия:
a) Создать пустой элемент на который указывает указатель q
q=getnode
b) Внести х в информационное поле созданного элемента
info(q)=x
c) Связать элемент Х с элементом В
ptr(q)=ptr(p) - это означает, что указателю созданного элемента присваивается значение указателя элемента p.
d) Связать элемент А с элементом Х
ptr(p)=q - это означает, что следующим за элементом А будет элемент на который указывает указатель q.
Окончательно:
2. Удаление элемента из кольцевого списка
Удалим из списка элемент, который следует за элементом с рабочим указателем р.
Чтобы это осуществить, необходимо произвести следующие действия:
a) Ввести указатель q, который будет указывать на удаляемый элемент.
q=ptr(p)
b) Поставить за элементом А элемент В
ptr(p)=ptr(q)
c) Запомнить информацию, которая содержится в поле info удаляемого элемента.
k=info(q)
d) Удалить элемент с указателем q.
Freenode(q)
Окончательно:
Контрольные вопросы по теории
Дата: 2019-12-10, просмотров: 279.
