Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Удаление элемента с заданным номером
Чтобы удалить элемент с заданным номером (например, с номером k) нужно поставить указатель на элемент с номером k-1 и изменить его адресное поле, присвоив ему значение адреса элемента с номером k+1. Затем элемент с номером k удаляется с помощью функции delete (рис.). Рис. 12. Удаление элемента из списка //Удаление из однонаправленного списка элемента с номером k point*del_point(point*beg,int k) { //поставить вспомогательную переменную на начало списка point*p=beg; point *r; //вспомогательная переменная для удаления int i=0; //счетчик элементов в списке
if(k==0) //удалить первый элемент { beg=p->next; delete p; //удалить элемент из списка return beg; //вернуть адрес первого элемента }
while(p)//пока нет конца списка { /*дошли до элемента с номером k-1, чтобы поменять его поле next* if(i==k-1) { /*поставить r на удаляемый элемент r=p->next;
if(r) //если p не последний элемент { p->next=r->next; //исключить r из списка delete r; //удалить элемент из списка }
/*если p -последний элемент, то в поле next присвоить 0*/ else p->next=0; }
p=p->next; //переход к следующему элементу i++; //увеличить счетчик элементов }
return beg;//вернуть адрес первого элемента }
Удаление элемента с заданным ключом осуществляется аналогично, но вместо условия if(i==k-1) //проверка номера нужно использовать условие: if(p->next->key==KEY)//проверка ключа, где KEY заданный ключ. Ключ KEY передается как параметр функции удаления.
Добавление элемента с заданным номером
Для добавления в список элемента с номером k нужно поставить указатель на элемент с номером k-1. Затем нужно создать новый элемент и поменять значения адресных полей таким образом, чтобы адресное поле нового элемента содержало адрес элемента с номером k, а адресное поле k-1 элемента – адрес нового элемента (см. рис.).
Рис. 13. Добавление элемента номером k point* add_elem(point*beg, int NOM) { point*p=make_point();//создание нового элемента if (NOM==0)//добавление первого элемента { p->next=beg;//связываем новый элемент со списком beg=p;//меняем адрес beg return beg; } point*r=beg;//указатель для перехода на нужный номер
/*проходим по списку до элемента с номером NOM-1 или до конца списка, если такого элемента нет */ for(int i=0; i<NOM-1&& r!=0;i++) r=r->next; //если элемента с указанным номером в списке нет if (!r) { cout<<"\nNot such NOM!"; //сообщение об ошибке return beg; }
p->next=r->next;//связываем новый элемент со списком //связываем элемент с номером NOM-1 с новым элементом
r->next=p; return beg; }
Двунаправленные списки
Двунаправленный список имеет два адресных поля, которые указывают на следующий элемент списка и на предыдущий. Поэтому двигаться по такому списку можно как слева направо, так и справа налево.
Рис. 14. Двунаправленный список
//пример описания двунаправленного списка struct point //описание структуры { int key; //ключевое поле //адресные поля point* pred, //адрес предыдущего элемента *next; // адрес следующего элемента
};
Ниже рассматривается программа, которая создает двунаправленный список, выполняет удаление элемента с заданным номером, добавление элемента с заданным номером и печать полученных списков
#include <iostream.h>
struct point //описание структуры { int key; //ключевое поле point* pred,*next; //адресные поля };
//формирование списка point*make_list() { int n; //количество элементов списка cout<<"n-?"; cin>>n;
point* p, *r, *beg; p=new (point); //создать первый элемент /*запомнить адрес в переменную beg, в которой хранится начало списка*/ beg=p; cout<<"key-?"; cin>>p->key; //заполнить ключевое поле p->pred=0;p->next=0; //запомнить адресные поля //добавить элементы в конец списка
for(int i=1;i<n;i++) { r=new(point); //новый элемент cout<<"key-?"; cin>>r->key; //адресное поле p->next=r; //связать начало списка с r r->pred=p; //связать r с началом списка r->next=0; //обнулить последнее адресное поле p=r; //передвинуть p на последний элемент списка }
return beg;//вернуть первый элемент списка } //печать списка void print_list(point *beg) { if (beg==0) //если список пустой { cout<<"The list is empty\n"; return; } point*p=beg; while(p) //пока не конец списка { cout<<p->key<<"\t"; p=p->next; //перейти на следующий элемент } cout<<"\n"; }
//удаление элемента с номером k point* del_point(point*beg, int k) { point *p=beg; if(k==0)//удалить первый элемент { //переставить начало списка на следующий элемент beg=beg->next; //если в списке только один элемент if(beg==0)return 0; //если в списке более одного элемента beg->pred=0;//обнулить адрес предыдущего элемента delete p; //удалить первый return beg; //вернуть начало списка }
/*если удаляется элемент из середины списка, пройти по списку либо до элемента с предыдущим номером, либо до конца списка*/ for(int i=0;i<k-1&&p!=0;i++,p=p->next);
//если в списке нет элемента с номером k if(p==0||p->next==0)return beg;
//если в списке есть элемент с номером k point*r=p->next; //встать на удаляемый элемент p->next=r->next; //изменить ссылку delete r; //удалить r r=p->next; //встать на следующий //если r существует, то связать элементы if(r!=0)r->pred=p; return beg; //вернуть начало списка }
//добавить элемент с номером k point* add_point(point *beg,int k) { point *p;
//создать новый элемент и заполнить ключевое поле p=new(point); cout<<"key-?"; cin>>p->key;
if(k==0)//если добавляется первый элемент { p->next=beg; //добавить перед beg p->pred=0; //обнулить адрес предыдущего //связать список с добавленным элементом beg->pred=p; beg=p; //запомнить первый элемент в beg return beg; //вернуть начало списка }
//если добавляется элемент середину или конец списка point*r=beg; //встать на начало списка
/*пройти по списку либо до конца списка, либо до элемента с номером k-1*/ for(int i=0;i<k-1&&r->next!=0;i++,r=r->next);
p->next=r->next; //связать р с концом списка //если элемент не последний, то связать конец списка с р if(r->next!=0)r->next->pred=p; p->pred=r; //связать р и r r->next=p; return beg; //вернуть начало списка }
void main() { point*beg; int i,k; do { //печать меню cout<<"1.Make list\n"; cout<<"2.Print list\n"; cout<<"3.Add point\n"; cout<<"4.Delete point\n"; cout<<"5.Exit\n"; cin>>i; //ввод выбранного пункта меню switch(i) { case 1://формирование списка { beg=make_list(); break; } case 2://печать списка { print_list(beg); break; } case 3://добавление элемента { cout<<"\nk-?"; cin>>k; beg=add_point(beg,k); break; } case 4://удаление элемента { cout<<"\nk-?"; cin>>k; beg=del_point(beg,k); break; } } } while(i!=5); //выход из программы }
Очереди и стеки
Очередь и стек – это частные случаи однонаправленного списка. В стеке добавление и удаление элементов осуществляются с одного конца, который называется вершиной стека. Поэтому для стека можно определить функции: · top() – доступ к вершине стека (вывод значения последнего элемента · pop() – удаление элемента из вершины (удаление последнего элемента); · push() – добавление элемента в вершину (добавление в конец). Такой принцип обслуживания называют LIFO (last in – first out, последний пришел, первый ушел).
point* pop(point*beg) { point*p=beg; if (beg->next==0)//один элемент { delete beg; return 0; } //ищем предпоследний элемент while (p->next->next!=0) p=p->next; // ставим указатель r на последний элемент point*r=p->next; //обнуляем адресное поле предпоследнего элемента p->next=0; delete r; //удаляем последний элемент return beg; } point* push(point* beg) { point*p=beg;// ставим указатель p на начало списка point*q=new(point);// создаем новый элемент cout<<"Key?"; cin>>q->data; q->next=0; if (beg==0)//список пустой { beg=q;//q становится первым элементом return beg; } while (p->next!=0)//проходим до конца списка p=p->next; p->next=q; //связываем последний элемент с q return beg; }
В очереди добавление осуществляется в один конец, а удаление из другого конца. Такой принцип обслуживания называют FIFO (first in – first out, первый пришел, первый ушел). Для очереди также можно определить функции: · front() – доступ к первому элементу; · back() – доступ к последнему элементу; · pop() – удаление элемента из конца; · push() – добавление элемента в начало. Бинарные деревья Бинарное дерево - это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных не более двух ссылок на другие бинарные деревья (поддеревья). На каждое поддерево имеется ровно одна ссылка (рис. ) Описать такую структуру можно следующим образом: struct point { int data;//информационное поле point* left;//адрес левого поддерева point* right;//адрес правого поддерева }; Начальный узел называется конем дерева. Узел, не имеющий поддеревьев, называется листом дерева. Исходящие листы называются предками, входящие – потомками. Высота дерева определяется количеством уровней, на которых располагаются узлы. Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше называется деревом поиска. Одинаковые ключи не допускаются. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения в каждом узле. Такой поиск является более эффективным, чем поиск по линейному списку, т. к. время поиска определяется высотой дерева, а она пропорциональна двоичному логарифму количества узлов (аналогично бинарному поиску). В идеально сбалансированном дереве количество узлов в справа и слева отличается не более, чем на единицу. Линейный список можно представить как вырожденное бинарное дерево, в котором каждый узел имеет не более одной ссылки. Для списка среднее время поиска равно половине длины списка. Деревья и списки являются рекурсивными структурами данных, т. к. каждое поддерево также является деревом. Дерево можно определить как рекурсивную структуру, в которой каждый элемент является: · либо пустой структурой; · либо элементом, с которым связано конечное число поддеревьев. Действия с рекурсивными структурами удобнее всего описываются с помощью рекурсивных алгоритмов.
Обход дерева
Для того, чтобы выполнить определенную операцию над всем узлами дерева, надо обойти все узлы. Такая задача называется обходом дерева. При обходе узлы должны посещаться в определенном порядке. Существуют три принципа упорядочивания, которые естественно вытекают из структуры дерева. Рассмотрим следующее дерево.
Рис. 15. Структура бинарного дерева На этом дереве можно определить три метода упорядочения: · Слева направо: Левое поддерево – Корень – Правое поддерево; · Сверху вниз: Корень – Левое поддерево – Правое поддерево; · Снизу вверх: Левое поддерево – Правое поддерево – Корень. Эти три метода можно сформулировать в виде рекурсивных алгоритмов. Эти алгоритмы служат примером того, что действия с рекурсивными структурами лучше всего описываются рекурсивными алгоритмами.
//Обход слева направо: void Run(point*p) { if(p) { Run(p->left); //переход к левому п/д <обработка p->data> Run(p->right);//переход к правому п/д } } Если в качестве операции обработки узла поставить операцию вывода информационного поля узла, то мы получим функцию для печати дерева. Для дерева поиска на рис. обход слева направо даст следующие результаты: 1 3 5 7 8 9 12
Рис. 16. Пример дерева поиска //Обход сверху вниз: void Run(point*p) { if(p) { <обработка p->data> Run(p->left); //переход к левому п/д Run(p->right);//переход к правому п/д } }
Результаты обхода слева направо для дерева поиска на рис. : 5 3 1 9 8 7 12
//Обход снизу вверх void Run(point*p) { if(p) { Run(p->left); //переход к левому п/д Run(p->right);//переход к правому п/д <обработка p->data> } } Результаты обхода сверху вниз для дерева поиска на рис. : 1 3 7 8 12 9 5
Формирование дерева
Рассмотрим построение идеально сбалансированного дерева. При построении такого дерева надо распределять узлы таким образом, чтобы количество узлов в левом и правом поддеревьях отличалось не более чем на единицу.
# include <iostream.h> struct point { int data; point*left,*right; };
point* Tree(int n,point* p) { point*r; int nl,nr; if(n==0){p=NULL;return p;}
nl=n/2;//считаем количество узлов в левом поддереве nr=n-nl-1; //считаем количество узлов в правом поддереве
r=new point;//создаем новый узел cout<<"?"; cin>>r->data;//заполняем информационное поле r->left=Tree(nl,r->left);//формируем левое поддерево r->right=Tree(nr,r->right);//формируем правое поддерево p=r;//связываем return p; } //печать дерева void Print(point*p, int l) { //обход слева направо if(p) { Print(p->left,l+5); for(int i=0;i<l;i++)cout<<" "; cout<<p->data<<"\n"; Print(p->right,l+5); } }
void main() { point*root; root=Tree(10,root); Print(root,1); }
Функция печати, которая используется в данной программе, печатает дерево по уровням слева направо. Переменная l считает количество пробелов, которые надо отступить для печати следующего уровня. Результат работы программы представлен на рис.17. Рис. 17. Результат работы программы формирования и печати дерева поиска При формировании дерева поиска нужно учитывать упорядоченность элементов в таком дереве, т. е. добавление элемента с ключом больше текущего осуществляется в правое поддерево, а меньше текущего – в левое. Ключи не дублируется, поэтому необходимо проверить существует ли элемент с заданным ключом в дереве и если существует, то завершить функцию добавления элемента.
point* first(int d)//формирование первого элемента дерева { point* p=new point; p->key=d; p->left=0; p->right=0; return p; } //добавление элемента d в дерево поиска Point* Add(point*root,int d) { Point*p=root,*r; // флаг для проверки существования элемента d bool ok=false; while(p&&!ok) { r=p; if(d==p->key)ok=true; else if(d<p->key)p=p->left;//пойти в левое поддерево else p=p->right;//пойти в правое поддерево } if(ok) return p;//найдено, не добавляем //создаем узел point* q=new point();//выделили память q->key=d; q->left=0; q->right=0; //добавляем в левое поддерево if(d<r->key)r->left=q; //добавляем в правое поддерево else r->right =q; return q; }
|
||
Последнее изменение этой страницы: 2018-04-12; просмотров: 511. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |