КАТЕГОРИИ: Архитектура-(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) |
Линейный однонаправленный список
Описание простейшего элемента такого списка выглядит следующим образом: struct имя_типа { информационное поле; адресное поле; }; Информационное поле – это поле любого, ранее объявленного или стандартного, типа; адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка. Информационных полей может быть несколько. Примеры. 1. struct Node { int key;//информационное поле Node*next;//адресное поле }; 2. struct point { char*name;//информационное поле int age;//информационное поле point*next;//адресное поле }; Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом (пример 1), либо строкой (пример 2). Над списками можно выполнять следующие операции: - начальное формирование списка (создание первого элемента); - добавление элемента в конец списка; - добавление элемента в начало списка; - удаление элемента с заданным номером; - чтение элемента с заданным ключом; - вставка элемента в заданное место списка (до или после элемента с заданным ключом); - упорядочивание списка по ключу и др. Пример1. Создание и печать однонаправленного списка #include <iostream.h> #include<string.h> //описание структуры struct point {char *name;//информационное поле int age;//информационное поле point*next;//адресное поле };
point* make_point() //создание одного элемента { point*p=new(point);//выделить память char s[20]; cout<<"\nEnter the name:"; cin>>s; p->name=new char[strlen(s)+1];//выделить память под динамическую строку символов strcpy(p->name,s);//записать информацию в строку символов cout<<"\nEnter the age"; cin>>p->age; p->next=0;//сформировать адресное поле return p; } void print_point(point*p)
//печать информационных полей одного элемента списка { cout<<"\nNAME:"<<p->name; cout<<"\nAGE:"<<p->age; cout<<"\n--------------------------------\n"; }
point* make_list(int n) //формирование списка из n элементов { point* beg=make_point();//сформировать первый элемент point*r; for(int i=1;i<n;i++) { r=make_point();//сформировать следующий элемент //добавление в начало списка r->next=beg;//сформировать адресное поле beg=r;//изменить адрес первого элемента списка } return beg;//вернуть адрес начала списка } int print_list(point*beg) //печать списка, на который указывает указатель beg { point*p=beg;//р присвоить адрес первого элемента списка int k=0;//счетчик количества напечатанных элементов while(p)//пока нет конца списка { print_point(p);//печать элемента, на который указывает элемент p p=p->next;//переход к следующему элементу k++; } return k;//количество элементов в списке }
void main() { int n; cout<<"\nEnter the size of list"; cin>>n; point*beg=make_list(n);//формирование списка if(!print_list(beg)) cout<<"\nThe list is empty";}//печать списка
Пример 2. Удаление из однонаправленного списка элемента с номером k (рис 5.).
Рис. 5. Удаление элемента с номером k из однонаправленного списка
point*del_point(point*beg,int k) //удаление элемента с номером к { point*p=beg,//поставить вспомогательную переменную на начало списка *r;//вспомогательная переменная для удаления int i=0;//счетчик элементов в списке if(k==0) {//удалить первый элемент beg=p->next; delete[]p->name;//удалить динамическое поле name delete[]p;//удалить элемент из списка return beg;//вернуть адрес первого элемента списка } while(p)//пока нет конца списка { if(i==k-1)//дошли до элемента с номером k-1, чтобы поменять его поле next {//удалить элемент r=p->next;//поставить r на удаляемый элемент if(r)//если p не последний элемент { p->next=r->next;//исключить r из списка delete[]r->name;//удалить динамическое поле name delete[]r;//удалить элемент из списка } else p->next=0;//если p -последний элемент, то в поле next присвоить NULL
} p=p->next;//переход к следующему элементу списка i++;//увеличить счетчик элементов } return beg;//вернуть адрес первого элемента}
Дата добавления: 2014-01-04; Просмотров: 303; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |