Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Стандартная ссылочная реализация списков

Читайте также:
  1. IV. Реализация национальной морской политики
  2. Воплощение и реализация
  3. Выбор и реализация решения
  4. Лабораторная работа №3. СОЗДАНИЕ СПИСКОВ, ВСТАВКА СИМВОЛОВ
  5. Методы списков дисков
  6. Нестандартная точка зрения
  7. Нестандартная точка зрения

Обычно, используется ссылочная реализация списков. Для этого следует создать объект, содержащий собственно данные, ссылку на следующий аналогичные объект и, для L2-списков, ссылку на предыдущий объект. Например, для реализации двунаправленного списка целых чисел на языке С следует определить следующий тип

 

Struct SList2

{

Int value;

struct SList2 *prev, *next;

};

здесь данные будут храниться в члене структуры value, а ссылки, соответственно, на предыдущий/следующий объекты представлены указателями prev и next. Признаком того, что данный элемент является первым в списке, может служить нулевое значение указателя prev, а признаком конца списка может служить нулевое значение указателя next.

Для сокращения имени типа в языке С можно использовать оператор typedef. Принцип работы данного оператора следующий. Если перед определением некоторой переменной с именем NAME написать оператор typedef, то NAME из имени переменной превратится в имя нового типа. Т.о. следующий оператор создает новый тип TList2, который можно использовать вместо типа struct SList2:

Typedef struct SList2 TList2;

Для работы со списком следует определить два указателя: указатель на головной элемент списка и указатель на текущий элемент списка:

TList2 *head=NULL, *current=NULL;

Признаком пустоты списка служит нулевое значение указателя head. Установка текущего элемента на начало списка сводится к присвоению

current=head;

Вставка элемента со значением value после текущего может быть произведена следующим образом:

TList2 *InsertData(int value, TList2 **head, TList2 **current)

{

TList2 *New=(TList2 *)malloc(sizeof(TList2));

New->value = value;

if(*head == NULL) //Случай пустого списка

{*current =*head = New; (*head)->next= (*head)->prev=NULL; return New;}

if(*current==NULL) //Случай вставки в начало списка

{

(*current)=New; (*current)->next=*head; (*current)->prev=NULL;

(*head)->prev=New;

(*head)=New;

Return New;

}

New->next = (*current)->next; New->prev=*current;

if((*current)->next!= NULL) (*current)->next->prev = New;

(*current) ->next = New;

Return New;

}

 

функция возвращает указатель на новый элемент. Текущее положение в списке не изменяется. Для того, чтобы при вызове указатель на текущий элемент перемещался бы на новый элемент, данная функция может быть вызвана следующим образом

 

current = InsertData(value, &head, &current);

Здесь следует отметить, что в функции могут изменяться значения указателей на головной и текущий элементы списка. Особенностью языка С является то, что параметры передаются в функции исключительно по значению, т.е. в функцию передаются копии переменных. Альтернативой, в других языках программирования (например С++) служит передача параметров по ссылке. При передаче параметров по ссылке реально передается не значение переменной, а ее адрес. При этом внешний вид (синтаксис) как формальных, так и фактических параметров не отличается от случая передачи параметров по значению (фактическими параметрами называются параметры, передаваемые снаружи при вызове функции, а формальными – параметры, встречающиеся в определении функции). Для указания того, что переменная передается по ссылке, в языке С++ используется символ & перед именем переменной в описании параметров функции. Поэтому в языке С++ вышеуказанная функция может выглядеть чуть проще

 

TList2 *InsertData(int value, TList2 *&head, TList2 *&current)

{

TList2 *New=(TList2 *)malloc(sizeof(TList2));

New->value = value;

if(head == NULL) //Случай пустого списка

{current =head = New; head->next= head->prev=NULL; return New;}

if(current==NULL) //Случай вставки в начало списка

{

current=New; current->next=head; current->prev=NULL;

head->prev=New;

head=New;

Return New;

}

New->next = current->next; New->prev=current;

if(current->next!= NULL) current->next->prev = New;

current ->next = New;

Return New;

}

Вызывать эту функцию надо следующим образом


Дата добавления: 2015-10-30; просмотров: 142 | Нарушение авторских прав


Читайте в этой же книге: Доказательство корректности работы алгоритма. | Оценки времени работы алгоритма. | Некоторые задачи, сводящиеся к сортировке. | Сортировки и связанные с ними задачи. | SortB (A, N, M, B) | То return QFindStatP (A, p, j, k,N ) | QFindStat5(A,1,N,k) | Структуры данных. | Struct SStack3 st3; | Стек. Реализация 5 (на основе указателя на указатель). |
<== предыдущая страница | следующая страница ==>
Struct SQueue| InsertData( value, head, current);

mybiblioteka.su - 2015-2024 год. (0.008 сек.)