КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Работа с двунаправленным списком
Рис. 6 Двунаправленный список
Пример 3. 1. Создать двунаправленный список, выполнить удаление элемента с заданным номером, добавление элемента с заданным номером, печать полученных списков. #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=p;//запомнить адрес в переменную beg, в которой хранится начало списка 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"; } 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);//пройти по списку либо до элемента с предыдущим номером, либо до конца списка if(p==0||p->next==0)return beg;//если в списке нет элемента с номером k point*r=p->next;//встать на удаляемый элемент p->next=r->next;//изменить ссылку delete r;//удалить r r=p->next;//встать на следующий if(r!=0)r->pred=p;//если r существует, то связать элементы return beg;//вернуть начало списка } 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;//встать на начало списка for(int i=0;i<k-1&&r->next!=0;i++,r=r->next);//пройти по списку либо до конца списка, либо до элемента с номером k-1 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.Del 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); }
Дата добавления: 2014-01-04; Просмотров: 208; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |