polevoi_cpp_2013_spring_lecture_04
.pdf
Структурное и процедурное программирование
(с использованием C++)
Полевой Дмитрий Валерьевич к.т.н., доцент КиК
e-mail: oop.misis@gmail.com
АТД и структуры данных
•АТД определяет набор допустимых операций
•структура данных определяет способ хранения информации и совершения операций (физическое размещение в памяти, реализация)
•АТД может реализовываться различными структурами данных
•часто называются одинаково
23.03.2013 |
2 |
Связный список
•список – структура данных, состоящая из узлов
•предназначен для хранения данных с последовательным доступом
•узел содержит как собственно данные, так и связи с другими узлами
23.03.2013 |
3 |
Односвязный список
• однонаправленный список
pHead
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
голова |
|
хвост |
||||
|
(первый узел) |
|
(последний узел) |
||||
23.03.2013 |
4 |
Односвязный список (узел)
struct SSList;
struct SSList
{
SSList* m_pNext;
T m_data;
};
23.03.2013 |
5 |
Двусвязный список
• двунаправленный список
pHead
0 
0
23.03.2013 |
6 |
Двусвязный список (узел)
struct SDList;
struct SDList
{
SDList* m_pPrev;
SDList* m_pNext;
T m_data;
};
23.03.2013 |
7 |
Операции над линейным списком
•создание
•уничтожение (удаление всех узлов)
•вставка списка (узла)
•удаление списка (узла)
•навигация по узлам (следующий, предыдущий)
•доступ к данным узла
23.03.2013 |
8 |
Навигация по линейному списку
pNode
pHead
0
if (0 != pNode)
{
pNode = pNode->m_pNext;
}
23.03.2013 |
9 |
Навигация по линейному списку
pNode
pHead
0
if (0 != pNode)
{
pNode = pNode->m_pNext;
}
23.03.2013 |
10 |