Реализация двусвязанного списка

Реализация некоторых структур данных

Пример через класс (хранимое данное: нетипизированный указатель (void*)). Особенностью списка является отсутствие управляющей структуры данных, операции над списком могут быть выполнены над любым элементом. Другой особенностью является «закольцованность», т.е. после последнего элемента идёт опять первый, перед первым – последний. Это позволяет в любой момент выбрать любой элемент списка в качестве первого.

class List

{

private:

List *next,*prev; //адрес следующего и предыдущего элементов

int *cnt; //указатель на количество элементов списка

public:

bool linkdata; //удалять ли связанные данные при удалении элемента

void *data; //указатель на данные

protected:

//закрытый «быстрый» конструктор, используется для добавления элемента

List(void* data,int *cnt):data(data),linkdata(false),cnt(cnt)

{

}

public:

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

List(void* data = NULL):data(data),linkdata(false)

{

prev=next=this;

cnt = new int(1); //создаётся новый счётчик числа элементов

}

virtual ~List() //деструктор

{

if (linkdata&&data!=NULL) free(data);//если есть данные и они «связаны», то удаляем их

next->prev=prev; prev->next=next; //переопределение связей

--(*cnt); //уменьшение количества элементов списка

if (*cnt==0) delete cnt; //если это последний элемент, то удаляем и счётчик

}

inline List* Next() {return next;} //следующий элемент

inline List* Prev() {return prev;} //предыдущий элемент

inline List* PushAfter(void* data = NULL) //добавить элемент после текущего

{

List *t = new List(data,cnt); //создаём новый элемент

if (t==NULL) return NULL; //если создание неуспешно, возврат

t->prev = this; //переопределение связей

t->next = next;

t->data = data;

next->prev = t;

next = t;

++(*cnt); //увеличение счётчика

return t;

}

void Clear() //очистка списка, остаётся только текущий элемент

{

List *t = next;

while (t!=this)

{

if (t->linkdata) free(t->data);

t = t->next;

delete t->prev;

}

cnt = 1;

next = prev = this;

}

inline int Count() {return *cnt;} //количество элементов

};

Организация на языке «С» (struct)

struct List

{

List *next,*prev;

int *cnt;

void *data;

char linkdata;

}

int Init(List* element)

{

element->prev= element->next= element;

if (element->cnt = malloc(sizeof(int))==NULL) return -1;

return 0;

}

List* PushAfter(List* elenemt, void* data)

{

List *t = malloc(sizeof(List));

if (t==NULL) return NULL;

t->data = data;

t->cnt = cnt;

t->linkdata = 0;

t->prev = element;

t->next = element->next;

t->data = element->data;

element->next->prev = t;

element->next = t;

++(*element->cnt);

return t;

}

int Delete(List* element)

{

if (element->linkdata&&element->data!=NULL) free(data);

element->next->prev= element->prev; element->prev->next=element->next;

--(*element->cnt);

if (*element->cnt==0) free(element->cnt);

free(element);

}

Реализация массива переменного размера:

1. С быстрым извлечением – создаётся вектор размера top, если происходит попытка записи элемента с номером n больше top, происходит перевыделение памяти так, чтобы (n < top). Может дополнительно задаваться шаг роста массива. Далее существующие данные копируются в новый массив; освобождается место, где ранее размещался массив. Недостаток – существенные временные затраты на «рост».

2. С быстрым расширением – создаётся список векторов, инициализируется только первый вектор (размер top). При попытке записи элемента с номером n больше top к списку добавляются один или несколько векторов, чтобы (n<top). Для ускорения доступа все векторы целесообразно создавать одного размера. Доступ к элементу осуществляется по номеру вектора (k) и номеру элемента в векторе (m). При равных размерах векторов (top) и заданном порядковом номере элемента (n) получаем: k=n/top, m=n%top.

В качестве модификации можно использовать вектор векторов (несколько быстрее доступ, но сложнее организовать рост).

class Vector

{

protected:

void** data; //поле данных

int top,step; //верхняя граница и шаг роста

public:

//конструктор принимает аргументы: начальный размер вектора и шаг роста

Vector(int top = 10, int step = 10):top(top),step(step)

{

data = (void**)malloc(top*sizeof(void*));

memset(data,0,top*sizeof(void*)); //сброс всех данных в ноль

}

~Vector()

{

free(data);

}

void* GetAt(int n)

{

if (n>-1 && n<top) return data[n];

return NULL; //если данные за допустимым диапазоном

}

bool SetAt(int n, void* element)

{

if (n>=top) //рост массива если вышли за границы

{

int oldtop = top;

while((top+=step)<=n);

void **tdata = (void**)malloc(top*sizeof(void*));

if (tdata == NULL) return false;

memcpy(tdata,data,oldtop*sizeof(void*));

memset(tdata+oldtop,0,(top-oldtop)*sizeof(void*));

free(data);

data = tdata;

}

*(data+n) = element;

return true;

}

int Count() {return top;} //верхняя граница

};

Дата добавления: 2014-01-05