Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Линейный однонаправленный список
Описание простейшего элемента такого списка выглядит следующим образом: 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;//вернуть адрес первого элемента}
|
||||||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 37; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.19.74.29 (0.006 с.) |