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

  • Автор темы anna li
  • Дата начала
Статус
Закрыто для дальнейших ответов.
A

anna li

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

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

grigsoft

Well-known member
15.11.2005
735
0
#2
не решай все задачи сразу. Для начала забудь о шаблонах, и напиши просто для того же int. Когда все напишешь - не будет проблем превратить это в шаблон.
 
M
#4
Эх, добрый я сегодня, наваял специально для тебя :()

Код 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;
}
Алгоритм описан тут:

http://www.rsdn.ru/

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

anna li

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

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

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

anna li

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

......................... .........................
| | | | | | -------->| | | | | | --------> .........
......................... .........................
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.я могу вам намыло прислать картинку структуры
 
M
#8
Что-то я не очень понимаю суть задания :)

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

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

anna li

#9
в общем...
вот если просто массив на основе связанного списка.....
описываем так
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] и т.д. теперь понятно?
мне эту байду нужно завтра уже сдать(причем в билдере,со всякими стрингридами и т.д.;но мне бы хоть шаблон составить и описание ф-й)...на крайняк в четверг...а я вообще без понятия....
 
A

anna li

#10
че то я не того про массив на основе списка ниписала
struct Node
{
int info;
Node *next;
};
а дальше то,что было там
 
M
#11
Вроде суть понял, но чесно говоря даже в голову не может уложиться, где такой извратный список можно удачно применить :), сегодня уже ухожу домой, если завтра на работе напряга с утра не будет, подумаю чутка, хотя не имея на руках продуманного алгоритма, наваять быстро красивое и быстрое решение врядли получится. :)
 
A

anna li

#12
я тут написала....но не знаю,правильно ли это вообще....удаление совсем не доделанно.....может чего исправите....чего допишите....
Код:
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--;}

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

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;
}
};
Коментарии допишите сами, тут вроде всё понятно.

Надеюсь получите свой зачОт ;) . Эх, где мои студенческие годы ... ;)
 
A

anna li

#14
Спасибо огромное....вот только мне удаление нужно не поиндексу, а по эл-ту....я решила добавить ф-ю поиска,что бы индекс найденного эл-та возвращался и тогда можно было бы удалять по индексу....для эл-м первой ячейки(т.е.для 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;
}
}
 
M
#15
Ненадо никаких поисков, это через Ж... :)

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

Код:
	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;
}
}
 
A

anna li

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

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

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

Вложения

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

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

anna li

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

anna li

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

По поводу ошибки - ну посмотрю, если еще не поздно :huh:
 
Статус
Закрыто для дальнейших ответов.