Одна из возможных реализаций объекта для работы с двусвязным циклическим списком (создание и вывод списка, добавление элемента справа от текущего элемента, удаление элемента слева от текущего):
unit obj_type;
point=^element;
element= record
last, next: point;
List= object
procedure Init;
procedure Create;
procedure Current;
procedure Output;
procedure Add_right;
procedure Del_left;
Implementation
procedure List.Init;
procedure List.Create;
writeln(‘ Данные: ’);
readln(p^. data);
if pcur<>nil then
pcur^. next:= p;
writeln(‘ Продолжить ввод?(Д/Н) ’);
until ans= ‘Н’;
pcur^. next:=p1;
p1^. last:=pcur;
procedure List.Current;
p, pnt: point;
writeln(‘Данные текущего элемента:’);
if p^.data=k then
break;
procedure List.Output;
until p=pcur;
procedure List.Add_right;
p, pnt: point;
writeln(‘Данные:’);
#10. Двусвязный список. Структура и основные операции | Структуры данных
p^.next:=pcur^.next;
pnt:=pcur^.next;
procedure List.Del_left;
if pcur^.next<>pcur then
p:=pcur^.last;
pcur^.last:=p^.last;
p^.last^.next:=pcur;
В данном случае указатель на первый элемент списка отсутствует. Для предотвращения зацикливания при обходе списка во время поиска указатель на текущий элемент предварительно копируется и служит ограничителем.
3. Организация данных
На основе массивов и списков можно смоделировать широко используемые в программировании организацию данных – стек и очередь, т. е. организацию хранения последовательности элементов (переменных), для которой задан определенный порядок их включения и исключения.
3.1. Организация данных – стек.
Стек представляет собой организацию данных, из которой первым извлекается тот элемент, который был добавлен в нее последним, т. е. последовательность элементов, включение и исключение элементов из которой производится только с одного конца, – таким образом, доступ к элементам происходит по принципу LIFO (last in first out).
Представление стека в виде списка.
Стек как организацию данных можно представить в виде линейного списка, для которого достаточно хранить указатель вершины стека, указывающий на первый элемент списка, т. е. на конец последовательности, в который производится добавление элементов и из которого производится их исключение. Начало последовательности называется дном стека.
Если стек пуст, то списка не существует, и указатель стека принимает значение nil.
Операция добавления нового элемента (запись в стек или включение элемента вершины стека) называется операцией проталкивания в стек и имеет общепринятое название Push.
Операция исключения элемента из вершины стека (удаление элемента) называется операцией выталкивания из стека и имеет общепринятое название Pop.
Операции Push и Pop являются безадресными в том смысле, что для их выполнения никакой дополнительной информации о месте размещения элементов не требуется (для этого достаточно указателя стека).
Реализация односвязного списка c++ Часть 1 | Урок #133
Для работы со стеками на основе списка необходимо иметь указатель на вершину стека Тор и дополнительный (временный) указатель Р, который используется для выделения и освобождения памяти элементов списка.
Источник: studfile.net
Разработка программы для создания и работы с двусвязным списком, состоящим из структур. (Структура содержит фамилию и год рождения)
Разработать программу для создания и работы с двусвязным списком, состоящим из структур. Для работы со списком создать меню со следующими пунктами:
1. Создание списка.
2. Просмотр списка.
3. Добавление в конец списка новой структуры.
4. Корректировка списка.
Пункт «корректировка списка» выполнить согласно своему варианту задания:
Вариант №7: структура содержит фамилию и год рождения. Добавлять новые записи так, чтобы список был упорядочен по алфавиту.
Введение
Связный список относится к одному из видов организации хранения структур данных.
Структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Структуры данных подразделяют на линейные и иерархические. Связный список относится к линейным структурам данных.
Связный список – структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки на следующее и/или предыдущее поле. Основные виды списков: однократно или дважды связный, отсортированный или неотсортированный, кольцевой или некольцевой [3, стр. 264]. Двусвязный список разновидность связного списка, который содержит две ссылки – на следующее и предыдущее поле.
При написании программ очень важную роль играет правильный выбор структур данных для организации и хранения тех или иных данных. В формальных языках программирования (C/C++, C#, Java) именно структуры данных ставятся во главу угла архитектуры программного средства.
При выборе структуры данных, необходимо ясно представлять, какие задачи она будет решать. Так преимущество связного списка перед массивом в том, что их размер является динамическим (т.е. в отличие от массива для добавления нового элемента не нужно заново пересоздавать всю структуру данных и копировать данные по новому адресу). Особенно быстро вставка новых элементов осуществляется на концах связного списка.
Тем не менее, необходимо помнить, что осуществление доступа к элементу по индексу в связном списке гораздо медленнее, чем в массиве.
Таким образом, при выборе между массивами и списками нужно определить, какие действия в работе со структурой данных будут превалирующими. Если чаще всего будет осуществляться доступ к элементам структуры по индексу и лишь изредка (возможно) понадобиться добавление новых элементов, то выбирать нужно массив. Если же необходимо будет постоянно добавлять новые элементы, и при этом доступ по индексу не так важен (к примеру, главное – это сортировка элементов и вывод их на экран), то, безусловно, выбор – списки.
1. Постановка комплекса задач
1.1. Комплекса задач
На примере создания связного списка:
· освоить и закрепить навыки синтаксиса языка C;
· получить базовые знания о структурах данных и их проектированию;
· получить базовые знания об алгоритмах и их программированию (на примере сортировки);
· получить опыт проектирования и создания API;
· получить опыт создания интерфейсов взаимодействия с пользователем.
1.2. Метод решения
Решение поставленных задач осуществляется путем написания программы, которая должна уметь создавать связный список, выводить его содержимое на экран, добавлять в конец списка новые данные, добавлять в список данные таким образом, чтобы список был упорядочен по алфавиту.
1.3. Входные данные
В качестве исходных входных данных, на основе которых создается список, используются данные получаемые при помощи генератора случайных чисел. Для выполнения других пунктов меню используются данные вводимые пользователем.
2. Блок-схема функционирования системы
3. Структура проекта
3.1. Использование подключаемых модулей
В программе использовались только те функции, которые входят в стандартную библиотеку C:
Использование в контексте программы
Конвертация времени в формат строки
Получение строки из потока stdin
Перемещение указателя в потоке stdin
Получение символа из потока stdin
Выделение памяти под указатель
Обнуление области памяти
Конвертация времени в формат time_t
Вывод форматированной строки в поток stdout
Вывод строки с началом новой линии в поток stdout
Получение случайного числа
Получение данных из потока stdin
Установка точки старта генерации случайного числа
Сравнение двух строк
Длина строки в символах
Получение системного времени
Примечание к таблице. Функции, обозначенные звездочкой, являются устаревшими и могут быть небезопасными. В современных системах проектирования должны быть использованы новые функции в соответствии со стандартом ISO.
3.2. Структура программы
Программа разрабатывалась на основе шаблона функционального дизайна. Функциональный дизайн гарантирует, что каждый модуль компьютерной программы имеет только одну обязанность и исполняет ее с минимум побочных эффектов на другие части программы [1, статья «Связный список»].
Применительно к данной программе этот шаблон применялся на уровне проектирования архитектуры программы (т.е. разбиение программы на модули и организация взаимодействия между ними) и на уровне организации кода (т.е. разбиение кода каждого из модулей на функции).
Таким образом, программа разделена на два модуля:
1. Двусвязный список – обеспечивает работу с двусвязным списком: создание списка, добавление новых элементов, сортировка, удаление списка. Предоставляет программный интерфейс для использования этой функциональности.
2. Интерфейс взаимодействия с пользователем – обеспечивает взаимодействие программы и пользователя, выводит на экран определенные данные, обрабатывает входные данные, поступающие от пользователя. На основе этого выполняет команды по работе с двусвязным списком (посредствам предоставленного интерфейса модуля двусвязного списка).
Похожие материалы
- Создание файла из 10 структур, используя функции и режим меню (Структура имеет вид: фамилия, номер телефона, дата рождения)
- Сортировка двусвязного динамического списка, структура которого содержит фамилию, год рождения
- Тесты для самоконтроля знаний по курсу «Программирование на языках высокого уровня». Часть 2. Алгоритмический язык С++
Источник: vunivere.ru
Структуры данных: двусвязный (двунаправленный) список
Двусвязный (двунаправленный) список — это разновидность связного списка, при которой переход по элементам возможен в обоих направлениях (как вперед, так и назад), в отличие от односвязного (однонаправленного) списка.
Вот термины, необходnuимые для понимания концепции двусвязных (двунаправленных) списков:
- Ссылка. В каждой ссылке связного списка могут храниться данные, называемые элементом.
- Следующая ссылка. В каждой ссылке связного списка содержится ссылка на следующую ссылку (Next).
- Предыдущая ссылка. В каждой ссылке связного списка содержится ссылка на предыдущую ссылку (Prev).
- Связный список содержит ссылку (связку) на первую ссылку (First) и на последнюю ссылку (Last).
Представление двусвязного (двунаправленного) списка
Здесь надо учитывать следующие важные моменты:
- Двусвязный (двунаправленный) список содержит элемент ссылок — first (первой) и last (последней).
- Каждая ссылка имеет поле или поля данных и два поля ссылки — next (следующей) и prev (предыдущей).
- Каждая ссылка связана со следующей посредством своей ссылки next.
- Каждая ссылка связана с предыдущей посредством своей ссылки prev.
- Последняя ссылка содержит ссылку со значением null, обозначающую конец списка.
Базовые операции
Это основные операции, проводимые над списками:
- Вставка, то есть добавление элемента в начало списка.
- Удаление элемента из начала списка.
- Вставка последним, то есть добавление элемента в конец списка.
- Удаление последнего, то есть удаление элемента из конца списка.
- Вставка после, то есть добавление элемента после какого-то элемента списка.
- Удаление элемента из списка по заданному ключу.
- Отображение вперед полного списка в прямом порядке.
- Отображение назад полного списка в обратном порядке.
Вставка
В этом коде показана операция вставки в начало двусвязного (двунаправленного) списка:
Пример
//вставляем ссылку на первое место void insertFirst(int key, int data) < //создаем ссылку struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) < //делаем ее последней ссылкой last = link; >else < //меняем первую предыдущую ссылку head->prev = link; > //указываем ей на прежнюю первую ссылку link->next = head; //указываем первой на новую первую ссылку head = link; >
Удаление
В этом коде показана операция удаления в начале двусвязного (двунаправленного) списка:
Пример
//удаляем первый элемент struct node* deleteFirst() < //сохраняем ссылку на первую ссылку struct node *tempLink = head; //если только одна ссылка if(head->next == NULL) < last = NULL; >else < head->next->prev = NULL; > head = head->next; //возвращаем удаленную ссылку return tempLink; >
Вставка в конце операции
В этом коде показана операция вставки в последнее место двусвязного (двунаправленного) списка:
Пример
//вставляем ссылку в последнее место void insertLast(int key, int data) < //создаем ссылку struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) < //делаем ее последней ссылкой last = link; >else < //делаем ссылку новой последней ссылкой last->next = link; //обозначаем прежний последний узел как предыдущий для новой ссылки link->prev = last; > //указываем последней на новый последний узел last = link; >
Реализация на языке программирования C:
#include
#include
#include
#include
struct node int data;
int key;
struct node *next;
struct node *prev;
>;
//Указатель показывает на начало списка
struct node *head = NULL;
//Указатель показывает на конец списка
struct node *last = NULL;
struct node *current = NULL;
//пуст ли список
bool isEmpty() return head == NULL;
>
int length() int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next) length++;
>
return length;
>
//показать список с первого элемента по последний
void displayForward()
//начать с начала списка
struct node *ptr = head;
//выводить пока не конец списка
printf(«n[ «);
while(ptr != NULL) <
printf(«(%d,%d) «,ptr->key,ptr->data);
ptr = ptr->next;
>
printf(» ]»);
>
//показать список с последнего по первый элемент
void displayBackward()
//начать с конца списка
struct node *ptr = last;
//выводить пока не начало списка
printf(«n[ «);
while(ptr != NULL) <
//вывести данные
printf(«(%d,%d) «,ptr->key,ptr->data);
//перейти к следующему элементу
ptr = ptr ->prev;
>
>
//вставить элемент в начало списка
void insertFirst(int key, int data)
//создать элемент
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) //поставить элемент в конец
last = link;
> else //update first prev link обновить у первого элемента ссылку на предыдущий элемент
head->prev = link;
>
//установить указатель на прошлый первый элемент
link->next = head;
//point first to new first link установить указатель списка первого элемента на новый первый элемент
head = link;
>
//добавить элемент в конец списка
void insertLast(int key, int data)
//создать указатель на элемент
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) //сделать последним элементом
last = link;
> else //сделать элемент новым последним элементом
last->next = link;
//установить указатель с нового элемента на прошлый последний элемент
link->prev = last;
>
//сделать элемент последним в списке
last = link;
>
//удалить первый элемент
struct node* deleteFirst()
//сохранить ссылку на первый элемент
struct node *tempLink = head;
//если один элемент
if(head->next == NULL) last = NULL;
> else head->next->prev = NULL;
>
head = head->next;
//return the deleted link возвратить удаленный элемент
return tempLink;
>
//удалить последний элемент
struct node* deleteLast() //сохранить ссылку на последний элемент
struct node *tempLink = last;
//если один элемент
if(head->next == NULL) head = NULL;
> else last->prev->next = NULL;
>
last = last->prev;
//возвратить удаленный элемент
return tempLink;
>
//удалить элемент с заданным ключом
struct node* delete(int key)
//начать с первого элемента
struct node* current = head;
struct node* previous = NULL;
//если список пуст
if(head == NULL) return NULL;
>
//продвигаться по списку
while(current->key != key) //если элемент последний
if(current->next == NULL) return NULL;
> else //сохранить указатель на текущий элемент
previous = current;
//перейти к следующему элементу
current = current->next;
>
>
//если найдено совпадение, обновить ссылку
if(current == head) //изменить указатель на первый элемент
head = head->next;
> else //установить у прошлого элемента ссылку на следующий от текущего
current->prev->next = current->next;
>
if(current == last) //изменить указатель на последний элемент
last = current->prev;
> else current->next->prev = current->prev;
>
return current;
>
bool insertAfter(int key, int newKey, int data) //начать с первого элемента
struct node *current = head;
//если лист пуст
if(head == NULL) return false;
>
//продвигаться по списку
while(current->key != key)
//если это последний элемент
if(current->next == NULL) return false;
> else <
//перейти к следующему
current = current->next;
>
>
//создать указатель на новый элемент
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = newKey;
newLink->data = data;
if(current == last) newLink->next = NULL;
last = newLink;
> else newLink->next = current->next;
current->next->prev = newLink;
>
newLink->prev = current;
current->next = newLink;
return true;
>
void main() insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf(«nList (First to Last): «);
displayForward();
printf(«n»);
printf(«nList (Last to first): «);
displayBackward();
printf(«nList , after deleting first record: «);
deleteFirst();
displayForward();
printf(«nList , after deleting last record: «);
deleteLast();
displayForward();
printf(«nList , insert after key(4) : «);
insertAfter(4,7, 13);
displayForward();
printf(«nList , after delete key(4) : «);
delete(4);
displayForward();
>
- Связный список в деталях
- Язык C: основы синтаксиса
- Структуры данных: основные понятия
Источник: nuancesprog.ru