КАТЕГОРИИ: Архитектура-(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) |
Работа с двунаправленным списком
Двунаправленный список представлен на рис. 27. Пример 107 даёт представление о работе с двунаправленным списком. Рис. 27. Двунаправленный список
Пример 107. Создать двунаправленный список, выполнить удаление элемента с заданным номером, добавление элемента с заданным номером, печать полученных списков. #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); } 4.11. Ввод-вывод в C++
Дата добавления: 2014-11-29; Просмотров: 371; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |