помогите с шаблонами,пожалуйста..

anna li · 01.06.2007

условие: Массив переменного размера на основе связного списка непрерывных фрагментов (доступ по индексу,включение,исключение элементов)

где можно про это посмотреть вообще хоть что-ть?
может кто-ть подскажет с описанием шаблона и с как-ть одной функцией..
спасибо..

grigsoft · 01.06.2007

не решай все задачи сразу. Для начала забудь о шаблонах, и напиши просто для того же int. Когда все напишешь - не будет проблем превратить это в шаблон.

sdriver · 01.06.2007

Исходники STL помотри

mms · 01.06.2007

Эх, добрый я сегодня, наваял специально для тебя

)

Код LinkedList.h:

Код:

#pragma once

template <class T>
class LinkedList
{
private:
//номер ячейки Refs, указывающей на первый элемент списка
static const int c_nullElem = 0;
//номер ячейки Refs, указывающей на первый элемент из "свободного места"
static const int c_nullFreeSpace = 1;

//Массив для хранения элементов списка
T* m_elems;
// Массив для хранения ссылок
int* m_refs;
// Указатель предыдущего элемента
int m_before;
// Указатель следующего элемента
int m_after;
// длинна масива
int m_arrayLength;
// Количество элементов в списке
int m_count;

private:
// Присваивание виртуальному индексу virtualIndex значения realIndex
void Link(int virtualIndex, int realIndex)
{
m_refs[virtualIndex] = realIndex;
}

// Выделение места для новых элементов
int GetSpace()
{
int i, oldLength;
if (IsListFull())
{
oldLength = m_arrayLength;
IncreaseArrays();
// добавляемые элементы помечаются как свободное место
for (int j = oldLength; j < m_arrayLength; ++j)
{
m_refs[j] = j + 1;
}
m_refs[c_nullFreeSpace] = oldLength;
m_refs[m_arrayLength] = c_nullFreeSpace;
}
i = m_refs[c_nullFreeSpace];
Link(c_nullFreeSpace, m_refs[i]);
return i;
}

// освобождение места при удалении элемента из списка
void PutSpace(int i)
{
Link(i, m_refs[c_nullFreeSpace]);
Link(c_nullFreeSpace, i);
}

// увеличить массивы в 2 раза
void IncreaseArrays()
{
T* tmpElems = new T[m_arrayLength * 2];
int* tmpRefs = new int[m_arrayLength * 2];
memset(tmpElems, 0, m_arrayLength * 2);
memset(tmpRefs, 0, m_arrayLength * 2);
for (int i = 0; i < m_arrayLength; ++i)
{
tmpElems[i] = m_elems[i];
tmpRefs[i] = m_refs[i];
}
// очищаем память
delete [] m_elems;
delete [] m_refs;

// назначаем новые массивы
m_elems = tmpElems;
m_refs = tmpRefs;
m_arrayLength *= 2;
}

public:
// Создание списка для хранения capacity элементов
// 1-я ячейка Refs указывает на первый элемент списка
// 2-я ячейка Refs указывает на 1-й элемент Х из "свободного места"
// capacity - максимально допустимое количество элементов в списке.
LinkedList(int capacity)
{
m_elems = new T[capacity];
m_refs = new int[capacity];
m_arrayLength = capacity;
ClearList();
}

// Очистка списка
void ClearList()
{
// конец списка указывает сам на себя
m_refs[c_nullElem] = c_nullElem;
// Поскольку список пуст, то все ячейки массива помечаются
// как "свободное место".
for (int i = c_nullFreeSpace; i < m_arrayLength; ++i)
{
m_refs[i] = i + 1;
}
// Закольцовываем "свободное место".
m_refs[m_arrayLength - 1] = c_nullFreeSpace;

m_after = 0;
m_before = 0;
m_count = 0;
}

// добавить element в список
void AddItem(T element)
{
// получаем свободное место
int i = GetSpace();
// устанавливаем его в нужном месте списка устанавливаем 
// указатель добавляем элемент element в список
Link(m_after, i);
Link(i, m_before);
m_before = i;
m_elems[i] = element;
MoveNext();
// увеличиваем счетчик количества элементов
++m_count;
}

// удалить элемент из списка
void RemoveItem()
{
if (m_count != 0)
{
int i = m_before;
m_before = m_refs[i];
Link(m_after, m_before);
PutSpace(i);
--m_count;
}
}

// прочитать значение элемента из списка
// если параметр Index отсутствует или
// не является порядковым номером эелемента списка
// то возвращается значение элемента перед указателем
// в противном случае возвращается значение элемента
// с порядковым номером Index
T ReadItem(int index = -1)
{
if (!(index >= 0 && index < m_count))
{
if (IsEndOfList())
{
return m_elems[m_after];
}
else
{
return m_elems[m_before];
}
}
else
{
int k = c_nullElem;
for (int i = 0; i <= index; ++i)
{
k = m_refs[k];
}
return m_elems[k];
}
}

// вернуть количество элементов в списке
int GetCount()
{
return m_count;
}

// определить, есть ли свободное место в списке
bool IsListFull()
{
return m_refs[c_nullFreeSpace] == c_nullFreeSpace;
}

// передвинуть указатель на один элемент списка
void MoveNext()
{
m_after = m_before;
m_before = m_refs[m_before];
}

// передвинуть указатель в начало списка
void MoveFront()
{
m_after = 0;
m_before = m_refs[c_nullElem];
}

// определить, находится ли указатель в конце списка
bool IsEndOfList()
{
return m_refs[m_after] == c_nullElem;
}
};

Тестируем:

Код:

#include <iostream>
#include "LinkedList.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
LinkedList<int> list(3);

// вывод количества элементов
cout << "Count of elements in list - " << list.GetCount() << endl;

// заполнение списка случайными числами
for (int i = 0; i < 5; ++i)
{
list.AddItem(rand());
}
list.MoveFront();

// вывод содержимого списка
cout << "Elements:" << endl;
while (!list.IsEndOfList())
{
cout << list.ReadItem() << endl;
list.MoveNext();
}

cout << "Remove first element" << endl;

// удаление первого элемента
list.MoveFront();
list.RemoveItem();

// вывод количества элементов
cout << "Count of elements in list - " << list.GetCount() << endl;

// вывод содержимого списка
cout << "Elements:" << endl;
while (!list.IsEndOfList())
{
cout << list.ReadItem() << endl;
list.MoveNext();
}

// вывод содержимого 2-го элемента
cout << "Second element - " << list.ReadItem(1) << endl;

return 0;
}

Алгоритм описан тут:

Ссылка скрыта от гостей

Лезем в раздел Статьи -> Структуры данных -> Реализация связанных списков

anna li · 01.06.2007

А разве это то,что мне надо? По сути, мне ведь нужно описать однонаправленный(?) список с динамическими массивами в качестве полей данных..причем в первой ячейке(элементе списка) содержатся элементы массива с индексами (допустим, если разбиваем по 5) 0,1,2,3,4....во второй 5,6,7,8,9 и т.д. Разве должна быть такая прога как вы описали?

А разве это то,что мне надо? По сути, мне ведь нужно описать однонаправленный(?) список с динамическими массивами в качестве полей данных..причем в первой ячейке(элементе списка) содержатся элементы массива с индексами (допустим, если разбиваем по 5) 0,1,2,3,4....во второй 5,6,7,8,9 и т.д. Разве должна быть такая прога как вы описали?

mms · 04.06.2007

Если условие было такое:

Массив переменного размера на основе связного списка непрерывных фрагментов (доступ по индексу,включение,исключение элементов)

То то, что я написал, поидее то, что надо

, покажите преподу, он скажет что не так

anna li · 04.06.2007

Нет..вы понимаете,что мне препод сам нарисовал структуру........

......................... .........................
| | | | | | -------->| | | | | | --------> .........
......................... .........................
0 1 2 3 4 5 6 7 8 9

Цифры-это индексы массива (это для случая,если мы разбиваем по 5)....
Но ведь прога,которую вы написали, совсем не то....как мне кажется....я права?

Блин,как-то совсем криво выложилось....
ладно,опишу....допустим,если мы разбиваем по 5 эл-в.....тогда первая ячейка состоит из 5 эл-в....индексы этих эл-в 0,1,2,3,4....вторая тоже из 5 (индесы эл-в-5,6,7,8,9) и т.д. Эти ячейки и являются элементами связанного списка....т.е.в связанном списке инф.полем является не один эл-т, а массив....вся сложность(для меня) в том, что индексы в каждой ячейке не о,1,2,3,4...а в 1-й-0,1,2,3,4, во 2-й-5,6,7,8,9 и т.д.
p.s.я могу вам намыло прислать картинку структуры

mms · 04.06.2007

Что-то я не очень понимаю суть задания

Т.е. сделать что-то типа списка, только в основе его должен быть не один динамически изменяемый массив, а массив мелких массивов, например каждый по 5 элементов?

П.С. Сейчас на работе времени не много свободного, если подробнее и яснее опишете, что надо, подумаем

anna li · 04.06.2007

в общем...
вот если просто массив на основе связанного списка.....
описываем так
struct Node
{
int *A=new int[100];
Node *next;
};

т.е.эл-ми списка являются эл-ты массива. Т.е в 0-й ячейке(эл-те списка)-A[0], в 1-й-А[1] и т.д. Вы согласны?

А мне нужно,чтобы в 0-й ячейке-был не один эл-т массива(например А[0]),а фрагмент массива(допустим размера 5),т.е. эл-ты А[0]A[1]...A[4]; в 1-й ячейке-следующий фрагмент массива(естественно таково же размера,т.е 5), т.е это эл-ты А[5]A[6]....A[9] и т.д. теперь понятно?
мне эту байду нужно завтра уже сдать(причем в билдере,со всякими стрингридами и т.д.;но мне бы хоть шаблон составить и описание ф-й)...на крайняк в четверг...а я вообще без понятия....

anna li · 04.06.2007

че то я не того про массив на основе списка ниписала
struct Node
{
int info;
Node *next;
};
а дальше то,что было там

mms · 04.06.2007

Вроде суть понял, но чесно говоря даже в голову не может уложиться, где такой извратный список можно удачно применить

, сегодня уже ухожу домой, если завтра на работе напряга с утра не будет, подумаю чутка, хотя не имея на руках продуманного алгоритма, наваять быстро красивое и быстрое решение врядли получится.

anna li · 05.06.2007

я тут написала....но не знаю,правильно ли это вообще....удаление совсем не доделанно.....может чего исправите....чего допишите....

Код:

template <class T> class Node
{

public:
int ni; //кол-во эл-в в ячейке =6
int nj; //кол-во ячеек
T *mt;
int k,j;
class spisok
{
public:
spisok *next;
T *K;
spisok(){K=new T[5];}
~spisok (){delete []K;}
};
public:
spisok *root;
Node(int n,int m){k=0;j=0;ni=n;nj=m;mt=new T[ni*nj];root=NULL;}
~Node (){delete []mt;};

//Добавление элемента
void Add( T y)
{ div_t s;  int l;
spisok *el=new spisok;
spisok *cur=root;
el->next=NULL;
if (root==NULL)
{ root=el;nj++; mt[k]=y;el->K[j]=mt[k];k++;j++;s=div(k,5);
l=s.quot;}
else

{if ((l)<=nj)
{mt[k]=y;el->K[j]=mt[k];if ((j<6)&(k<(ni*nj))){k++;j++; s=div(k,5);
l=s.quot;}}
else
{while (cur->next!=NULL)cur=cur->next; j=0;nj++;mt[k]=y;cur->K[j]=mt[k];k++;j++; s=div(k,5);
l=s.quot;
cur->next=el;
}}

};

int poisk(T f)     //поиск
{
for (int p=0;p<k;p++)
if (mt[p]==f) return p;
return -1;
}

//удаление эл-та(не дописано)
void ydal( T y)
{int p;  div_t s;  int l,h; spisok *el=new spisok;
p=poisk(y);
if (p==-1)return;
s=div(p,6);
l=s.quot+1;   //номер ячейки
h=s.rem;    //номер эл-та в ячейке
for(int nj=0;nj<=j;nj++)

{for(int i=h+1;i<6;i++)
el->K[i-1]=el->K[i];}
k--;}

};

mms · 05.06.2007

Ну вот что получилось, писал быстро, времени мало:

MyList.h

Код:

#pragma once

template<class T>
struct MyListFragment
{
private:
T* m_data;
int m_length;
int m_count;

public:
MyListFragment* Next;

MyListFragment(int capacity)
{
m_data = new T[capacity];
m_length = capacity;
m_count = 0;
Next = NULL;
}

~MyListFragment()
{
if (Next != NULL)
{
delete Next;
}
delete [] m_data;
}

void Add(T value)
{
if (!IsFull())
{
m_data[m_count] = value;
++m_count;
}
}

T Remove(int index)
{
if (index >= 0 && index < m_count)
{
int result = m_data[index];
for (int i = index; i < m_count - 1; ++i)
{
m_data[i] = m_data[i + 1];
}
--m_count;
return result;
}
else
{
throw new exception("Wrong index");
}
}

T Get(int index)
{
if (index >= 0 && index < m_count)
{
return m_data[index];
}
else
{
throw new exception("Wrong index");
}
}

bool IsFull()
{
return m_length == m_count;
}

int Count()
{
return m_count;
}

int Capacity()
{
return m_length;
}
};

template<class T>
class MyList
{
private:
MyListFragment<T>* m_firstFragment;
const static int m_fragmentsCapacity = 5;
public:
MyList()
{
m_firstFragment = NULL;
}

virtual ~MyList()
{
if (m_firstFragment != NULL)
{
delete m_firstFragment;
}
}

T Get(int index)
{
if (index >= 0 && index < Count())
{
MyListFragment<T>* fragment = m_firstFragment;
int i = 0;
while (fragment != NULL)
{
if (index < i + fragment->Capacity())
{
return fragment->Get(index - i);
}
i += fragment->Count();
fragment = fragment->Next;
}
}
else
{
throw new exception("Wrong index");
}
}

void Remove(int index)
{
if (index >= 0 && index < Count())
{
MyListFragment<T>* fragment = m_firstFragment;
int i = 0;
while (fragment != NULL)
{
if (index < i + fragment->Capacity())
{
fragment->Remove(index - i);
while (fragment != NULL && fragment->Next != NULL && fragment->Next->Count() > 0)
{
int removed = fragment->Next->Remove(0);
fragment->Add(removed);
if (fragment->Next->Count() == 0)
{
delete fragment->Next; 
fragment->Next = NULL;
}
fragment = fragment->Next;
}
break;
}
fragment = fragment->Next;
}
}
else
{
throw new exception("Wrong index");
}
}

void Add(T value)
{
if (m_firstFragment == NULL)
{
m_firstFragment = new MyListFragment<T>(m_fragmentsCapacity);
}

MyListFragment<T>* fragment = m_firstFragment;
while (true)
{
if (fragment->IsFull())
{
if (fragment->Next == NULL)
{
fragment->Next = new MyListFragment<T>(m_fragmentsCapacity);
}
fragment = fragment->Next;
}
else
{
fragment->Add(value);
break;
}
}
}

int Count()
{
int result = 0;
MyListFragment<T>* fragment = m_firstFragment;
while (fragment != NULL)
{
result += fragment->Count();
fragment = fragment->Next;
}
return result;
}
};

Коментарии допишите сами, тут вроде всё понятно.

Надеюсь получите свой зачОт

. Эх, где мои студенческие годы ...

anna li · 06.06.2007

Спасибо огромное....вот только мне удаление нужно не поиндексу, а по эл-ту....я решила добавить ф-ю поиска,что бы индекс найденного эл-та возвращался и тогда можно было бы удалять по индексу....для эл-м первой ячейки(т.е.для 5 эл-в)работает,а для остальных нет....может подскажите,что я не так написала..

Код:

//в struct (т.е.для одного фрагмента)
T poisk(T value)		 //ïîèñê
{ int k;
for (int i=0;i<k;i++)
if (m_data[i]==value) return i;
return -1;
}

//в основной части
int poisk(T value)
{  MyListFragment<T>* fragment = m_firstFragment;
int i; int k=0;
while (fragment != NULL)
{
for ( i=0; i<fragment->Capacity();i++)
{
if (fragment->poisk(value)>=0)
return (k+fragment->poisk(value));
else break;}
k += fragment->Count();
fragment = fragment->Next;
}
}

mms · 06.06.2007

Ненадо никаких поисков, это через Ж...

Вот функция для удаления по значению элемента, а не по индексу:

Код:

	void Remove(T value)
{
MyListFragment<T>* fragment = m_firstFragment;
while (fragment != NULL)
{
for (int j = 0; j < fragment->Count(); j++)
{
if (fragment->Get(j) == value)
{
fragment->Remove(j);
while (fragment != NULL && fragment->Next != NULL && fragment->Next->Count() > 0)
{
int removed = fragment->Next->Remove(0);
fragment->Add(removed);
if (fragment->Next->Count() == 0)
{
delete fragment->Next; 
fragment->Next = NULL;
}
fragment = fragment->Next;
}
break;
}
}
fragment = fragment->Next;
}
}

anna li · 06.06.2007

Теперь все ок...но если я удаляю из последнего фрагмента...вылетает ошибка

Хотя...вроде теперь уже не вылетает...спасибо....завтра пойду сдавать...если все будет ок,я вас как-то могу отблагодарить?

вот и еще вопрос...у меня ведь структура такая в проге(как на рисунке)? Я отчет по ней пишу....грубо говоря: сначала мы все делаем для одного фрагмента, а потом их как бы склеиваем...или как мне описать,что делаем потом?

mms · 06.06.2007

При добавлении сначала заполняется первый фрагмент, потом когда он полон, создаётся второй, причем первый ссылается на второй и далее заполняется второй, потом третий и т.д.

При удалении элементы сдвигаются к началу, если последний фрагмент пустой, то он удаляется.

anna li · 06.06.2007

А вот еще...
template<class T>struct MyListFragment -это типа вложенная структура(а я могу вместо truct написать class ?)...или как вообще граммотно сказать (чтобы в отчет написать) что такое
template<class T>struct MyListFragment и template<class T>class MyList?
а еще я хочу перенисти сами ф-и из .h в .cpp,ну естественно их заголовки оставить в .h. а он мне ошибкуи выдает.перенос вообще возможен?

anna li · 06.06.2007

Вы знаете,все-таки при удалении(примерно на 5,10...но может и раньше выскакивает) выскакивает ошибка...указывает на последнюю строчку fragment = fragment->Next из ф-и void Remove(T value)...может подкорректируете

mms · 07.06.2007

Структуру на класс можно поменять, тут, в принципе, без разницы.

По поводу ошибки - ну посмотрю, если еще не поздно :huh:

Все сервисы Codeby

Поиск

Поиск

помогите с шаблонами,пожалуйста..

anna li

grigsoft

sdriver

mms

anna li

mms

anna li

mms

anna li

anna li

mms

anna li

mms

anna li

mms

anna li

Вложения

mms

anna li

anna li

mms