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

Тема в разделе "Общие вопросы по С и С++", создана пользователем anna li, 1 июн 2007.

Наш партнер Genesis Hackspace
Статус темы:
Закрыта.
  1. anna li

    anna li Гость

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

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

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    не решай все задачи сразу. Для начала забудь о шаблонах, и напиши просто для того же int. Когда все напишешь - не будет проблем превратить это в шаблон.
     
  3. sdriver

    sdriver Гость

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

    mms Гость

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

    Код LinkedList.h:

    Код (Text):
    #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;
    }
    };

    Тестируем:

    Код (Text):
    #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/

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

    anna li Гость

    спасибо
     
  6. anna li

    anna li Гость

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

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

    mms Гость

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

    То то, что я написал, поидее то, что надо :(, покажите преподу, он скажет что не так ;)
     
  8. anna li

    anna li Гость

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

    ......................... .........................
    | | | | | | -------->| | | | | | --------> .........
    ......................... .........................
    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.я могу вам намыло прислать картинку структуры
     
  9. mms

    mms Гость

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

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

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

    anna li Гость

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

    anna li Гость

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

    mms Гость

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

    anna li Гость

    спасибо...
     
  14. anna li

    anna li Гость

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

    };
     
  15. mms

    mms Гость

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

    MyList.h

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

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

    anna li Гость

    Спасибо огромное....вот только мне удаление нужно не поиндексу, а по эл-ту....я решила добавить ф-ю поиска,что бы индекс найденного эл-та возвращался и тогда можно было бы удалять по индексу....для эл-м первой ячейки(т.е.для 5 эл-в)работает,а для остальных нет....может подскажите,что я не так написала..
    Код (Text):
    //в 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;
    }
    }
     
  17. mms

    mms Гость

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

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

    Код (Text):
        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;
    }
    }
     
  18. anna li

    anna li Гость

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

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

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

    Вложения:

    • __________.bmp
      Размер файла:
      184,4 КБ
      Просмотров:
      35
  19. mms

    mms Гость

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

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

    anna li Гость

    А вот еще...
    template<class T>struct MyListFragment -это типа вложенная структура(а я могу вместо truct написать class ?)...или как вообще граммотно сказать (чтобы в отчет написать) что такое
    template<class T>struct MyListFragment и template<class T>class MyList?
    а еще я хочу перенисти сами ф-и из .h в .cpp,ну естественно их заголовки оставить в .h. а он мне ошибкуи выдает.перенос вообще возможен?
     
Загрузка...
Похожие Темы - помогите шаблонами пожалуйста
  1. Gantzer61
    Ответов:
    1
    Просмотров:
    1.519
  2. Rina
    Ответов:
    0
    Просмотров:
    44
  3. maksiiimka
    Ответов:
    2
    Просмотров:
    50
  4. Ким
    Ответов:
    23
    Просмотров:
    479
  5. Sr233
    Ответов:
    2
    Просмотров:
    126
Статус темы:
Закрыта.

Поделиться этой страницей