материалы_к_лекции_списки
.pdf
Виды линейных списков
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
данные |
|
данные |
|
данные |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
данные |
|
данные |
|
данные |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
указатель |
|
указатель |
|
|
финиш |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
данные |
|
данные |
|
данные |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
старт |
|
указатель |
|
указатель |
|
указатель |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19
Вставка в линейный список
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
данные |
|
данные |
|
данные |
|
|
|
|
|
|
|
|
|
|
|
|
|
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
данные
указатель
20
Удаление из линейного списка
данные 
данные
старт |
|
указатель |
|
|
|
0 |
|
|
|
|
|
|
|
21
Удаление первого элемента
template <class T> void LineList<T>::deleteFirst()
{
if (start)
{
LineListElem<T>* temp = start->next;
delete start;
start = temp;
} else throw LineListException();
}
данные данные данные
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
Объектно-ориентированное |
26 |
программирование на языке C++
Вставка первого элемента
template <class T> void LineList<T>::insertFirst( const T& data)
{
LineListElem<T>* second = start;
start = new LineListElem<T>(data, second);
}
|
|
данные |
|
данные |
|
данные |
|
|
|
|
|
|
|
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
данные
указатель
Объектно-ориентированное |
28 |
программирование на языке C++
Удаление после данного элемента
template <class T> void LineList<T>::deleteAfter(
LineListElem<T>* ptr) {
if (ptr && ptr->next) {
LineListElem<T>* temp = ptr->next;
ptr->next = ptr->next->next;
delete temp;
} else throw LineListException();
}
данные данные данные
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
ptr
29
Вставка после данного элемента
template <class T> void LineList<T>::insertAfter(
LineListElem<T>* ptr, const T& data) {
if (ptr) {
LineListElem<T>* temp = ptr->next; ptr->next = new LineListElem<T>(data, temp);
}
} |
|
|
данные |
|
данные |
|
данные |
|
|
|
|
|
|
|
|
|
старт |
|
указатель |
|
указатель |
|
0 |
|
|
|
|
|
|
|
|
ptr
данные
указатель
30
Достоинства и недостатки однонаправленного списка
Достоинства
быстро вставляет и удаляет после
быстро вставляет и удаляет в начале
Недостатки
медленно вставляет и удаляет перед
медленно вставляет и удаляет в конце
Как справиться с недостатками?
34
//элемент стека и указатель
//на вершину стека
struct list
{
void *next; int val;
}*top=NULL;
//помещение в стек void push(struct list *p) { p->next=top;
top=p;
};
//извлечение из стека list *pop()
{ list *p;
if (top!=NULL)
{p=top; top=top->next; return p; }
else
return NULL;
}
int main(int argc, char* argv[])
{
return 0;
}
Стек
Фрагмент с использованием
struct list *p, *pp; p=new list; strcpy(p- >val,"Hello\n"); push(p); printf("%s",top->val); pp=pop(); printf("%s",pp->val);
Гаврилов А.В. |
22 |
НГТУ, Кафедра АППМ
Циклические списки
Гаврилов А.В. |
25 |
НГТУ, Кафедра АППМ