Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Class StrNode : public BiNode
{ char *str; ... public: StrNode(const char *s); ~StrNode() { cerr<<"String:\""<<str<<"\" is deleted."<<endl; delete []str; } virtual int identify(void* s) { return strcmp(str,(char*)s); } virtual BiNode* insert(void* s) { return(new StrNode((char*)s)); } StrNode * search (void * s) { ... } .... };
11.4. Определение линейного списка. Программирование связных списков в C++ Линейный список представляет последовательность из n>0 узлов x[1], x[2],...,x[n], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре следует соблюдать условие: если n>0 и x[1] является первым узлом, а x[n] – последним, то k-тый узел x[k] следует за x[k-1] узлом и перед x[k+1] узлом для любого k лежащего в промежутке от 1 до n. С линейными списками могут выполняться следующие операции: · получение доступа к x[k] элементу списка для проверки и/или изменения содержания его полей. · вставка нового узла сразу до или после x[k] узла. · удаление x[k] узла. · объединение в один список двух или более линейных списков. · разбиение линейного списка на два и более списка. · создание копии линейного списка. · определение количества узлов с списке. · сортировка узлов в порядке возрастания значений в определенных полях этих узлов. · поиск узла с заданным значением некоторого поля. Линейные списки, в которых операции вставки, удаления и операции доступа к значению чаще всего выполняются в первом и последнем узле получили специальное название: стек – линейный список, в котором операции вставки и удаления (и как правило доступа к данным) выполняются только на одном из концов списка; очередь (односторонняя очередь) – линейный список, в котором все операции вставки выполняются на одном конце списка, а все операции удаления (и доступа, как правило) – на другом; дек (двухсторонняя очередь) – линейный список, в котором все операции вставки, удаления и доступа выполняются с обоих концов. Различают дек с ограниченным вводом и ограниченным выводом, в котором операция удаления и вставки элементов соответственно выполняется только на одном из концов. Программирование связных списков в C++. Под связными списками понимается набор элементов, причем каждый из них является часть узла Node, который также содержит ссылку Link.
struct node{Item item; node *next;}; typedef node* Link;
Соответственно узлы в связном списке ссылаются на узлы и поэтому связный список называется самоссылочным. Простые линейные списки можно рассматривать как последовательность, в которой принято одно из следующих соглашений для ссылки последнего узла, а именно: пустая (NULL) ссылка, не указывает ни на какой узел ссылка, которая указывает на фиктивный узел, который не содержит элемента ссылка, которая указывает на первый узел, делает список циклическим В каждом случае отслеживание ссылок от первого элемента до последнего формирует последовательность расположения элементов. При программировании связных списков, как только возникает необходимость использовать новый узел в списке, для него необходимо резервировать память. При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовывать вычисления, связанные с резервирование памяти во время выполнения посредством вызовов системных операторов управления памятью. Пример 1 link x = new node; Struct node { Item item; node *next; node (Item x; node *t) iteam = x; next = t; }; link t = new(x,t);
Если хотим удалить элемент
t = x -> next; x -> next = t -> next; Или x -> next = x -> next; x -> next = t; Если хотим добавить элемент
t->next = x -> next; t ->next = t; Пример 2 Пример циклического списка (задача Иосифа). Struct node { Item item; node *next; node (Item x; node *t) item = x; next = t; }; typedef node *link; int main(int argc; char *argv[]) { int i; N = atoi(argv[1]); M = atoi(argv[2]); link t = new node(1,1); t -> next = t; link x = t; for(i=2; i<=N; i++) x=(x -> next = new node a,t); while(x! = x -> next) { for(i=1; i<N; i++) x = x -> next; x -> next + x -> next -> next; } cout << x -> item << endl; } } N=9 M=5 517436928
|
|||||
Последнее изменение этой страницы: 2021-07-18; просмотров: 63; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.227.72.153 (0.009 с.) |