Слайд 2
11.1. Контейнеры
Контейнер – хранилище некоторой
совокупности данных
Операции
с контейнером не зависят от
типа данных, размещенных в
контейнере
Пример: стек. Операции со стеком:
положить в стек
взять из стека
Слайд 3
11.2. Простой шаблон класса
// файл file.h
template
MyType>
class Stack {
private:
static const int SZ = 100;
int top;
MyType
arr[SZ];
Слайд 4
11.2. Простой шаблон класса
(продолжение)
public:
Stack();
int push(const MyType &);
int pop(MyType
&);
};
template
Stack ::Stack():top(0){}
Слайд 5
11.2. Простой шаблон класса
(продолжение)
template
int Stack::push(const T
&el)
{
if(top < SZ){
arr[top++] = el;
return 0;
}
return -1;
}
Слайд 6
11.2. Простой шаблон класса
(продолжение)
template
int Stack::pop(P &el)
{
if(top
> 0){
el = arr[--top];
return 1;
}
return 0;
}
Слайд 7
11.3. Использование шаблона класса
// файл file.cpp
#include “file.h”
int
main()
{
Stack st1, st2;
st1.push(12); // в стеке число 12
st1.push(25); //
в стеке число 25
st2 = st1;
Слайд 8
11.3. Использование шаблона класса
(продолжение)
int x, y;
st1.pop(x); // извлечение
числа 25
st1.pop(y); // извлечение числа 12
cout
" << x << ", y = " << y << endl;
return 0;
}
x = 25, y = 12
Для продолжения нажмите любую клавишу . . .
Слайд 9
11.4. Вариант 1 шаблона класса
// файл file.h
template
class Stack {
private:
int top;
MyType arr[SZ];
Слайд 10
11.4. Вариант 1 шаблона класса
(продолжение)
public:
Stack();
int push(const MyType &);
int
pop(MyType &);
};
template
Stack::Stack():top(0){}
Слайд 11
11.4. Вариант 1 шаблона класса
(продолжение)
template
N>
int Stack::push(const T &el)
{
if(top < N){
arr[top++] = el;
return
0;
}
return -1;
}
Слайд 12
11.4. Вариант 1 шаблона класса
(продолжение)
template
N>
int Stack::pop(P &el)
{
if(top > 0){
el = arr[--top];
return 1;
}
return
0;
}
Слайд 13
11.5. Использование шаблона класса
// файл file.cpp
#include “file.h”
int
main()
{
Stack st1;
Stack st2;
st1.push(12); // в стеке число
12
st1.push(25); // в стеке число 25
Слайд 14
11.5. Использование шаблона класса
(продолжение)
int x, y;
st1.pop(x); // извлечение
числа 25
st1.pop(y); // извлечение числа 12
cout
" << x << ", y = " << y << endl;
return 0;
}
x = 25, y = 12
Для продолжения нажмите любую клавишу . . .
Слайд 15
11.6. Вариант 2 шаблона класса
template
T>
class Stack {
private:
int top;
T *arr;
int sz;
public:
Stack(int = 0);
Слайд 16
11.6. Вариант 2 шаблона класса
(продолжение)
int push(const T
&);
int pop(T &);
Stack(const Stack &);
~Stack(){delete [ ] arr; }
Stack
&operator =(const Stack &);
};
Слайд 17
11.6. Вариант 2 шаблона класса
(продолжение)
template
int
Stack::push(const T &el)
{
if(top < sz){
arr[top++] = el;
return 0;
}
return -1;
}
Слайд 18
11.6. Вариант 2 шаблона класса
(продолжение)
template
int
Stack::pop(P &el)
{
if(top > 0){
el = arr[--top];
return 1;
}
return 0;
}
Слайд 19
11.6. Вариант 2 шаблона класса
(продолжение)
template
Stack::Stack(int
n):top(0)
{
sz = n > 0 ? n : 10;
arr
= new T[sz];
}
Слайд 20
11.6. Вариант 2 шаблона класса
(продолжение)
template
Stack::Stack(const
Stack &s):
top(s.top), sz(s.sz), arr(new T[s.sz])
{
for(int i = 0;
i < top; ++i)
arr[i] = s.arr[i];
}
Слайд 21
11.6. Вариант 2 шаблона класса
(продолжение)
template
Stack
&Stack::operator =(
const Stack &s)
{
if(this != &s){
delete [] arr;
top =
s.top;
sz = s.sz;
Слайд 22
11.6. Вариант 2 шаблона класса
(продолжение)
arr = new
T[sz];
for(int i = 0; i < top; ++i)
arr[i] =
s.arr[i];
}
return *this;
}
Слайд 23
11.7. Использование шаблона класса
int main()
{
Stack st1, st2;
st1.push(12);
st1.push(25);
st2
=st1;
int x, y;
st1.pop(x);
Слайд 24
11.7. Использование шаблона класса
(продолжение)
st2.pop(y);
cout
<< endl;
return 0;
}
x = 25, y = 25
Для продолжения нажмите любую клавишу . . .
Слайд 25
11.8. Контейнер: список
struct SLink {
SLink *next;
SLink(): next(NULL){
}
SLink(SLink *p): next(p){ }
};
first
next
next
next
Слайд 26
11.8. Контейнер: список
(продолжение)
class BList {
protected:
SLink *first;
public:
BList(): first(NULL){ }
BList(SLink
*a): first(a){ }
void insert(SLink *);
SLink *get();
friend class BListIter;
};
Слайд 27
11.8. Контейнер: список
(продолжение)
class BListIter {
private:
BList *cs;
SLink *cl;
public:
BListIter(BList &a):cs(&a),
cl(a.first){ }
SLink *operator()();
};
Слайд 28
11.8. Контейнер: список
(продолжение)
SLink *BList::get()
{
SLink *res = first;
if(first){
first =
first->next;
res->next = NULL;
}
return res;
}
next
next
first
res
Слайд 29
11.8. Контейнер: список
(продолжение)
void BList::insert(SLink *a)
{
a->next = first;
first =
a;
a = NULL;
}
next
next
a
first
next
Слайд 30
11.8. Контейнер: список
(продолжение)
SLink *BListIter::operator()()
{
SLink *ret = cl;
cl =
cl ? cl->next : cs->first;
return ret;
}
Слайд 31
11.9. Контейнер: список – использование
class StackInt: public SLink{
protected:
int
val;
public:
StackInt(int a = 0):val(a){}
int getVal() const {return val;}
};
next
val
Слайд 32
11.9. Контейнер: список – использование (продолжение)
int main()
{
BList st;
StackInt
*p = NULL;
st.insert(new StackInt(12));
st.insert(new StackInt(25));
st.insert(new StackInt(38));
Слайд 33
11.9. Контейнер: список – использование (продолжение)
std::cout
#3: " getVal())
st.get()
);
Слайд 34
11.9. Контейнер: список – использование (продолжение)
std::cout
";
BListIter it(st);
SLink *pl;
while(pl = it()){
p = static_cast(pl);
std::cout
(p->getVal()) << ' ';
}
std::cout << std::endl;
Слайд 35
11.9. Контейнер: список – использование (продолжение)
p = static_cast
*>(st.get());
std::cout
return 0;
}
Слайд 36
11.9. Контейнер: список – использование (продолжение)
item #3: 38
Iterator:
25 12
item #2: 25
Для продолжения нажмите любую клавишу .
. .
Слайд 37
11.10. Шаблон списка
template
struct TLink: public SLink{
T
info;
TLink(const T &a):info(a){ }
};
Слайд 38
11.10. Шаблон списка
(продолжение)
template
class SListIter;
template
class SList:private BList
{
friend class SListIter;
public:
void insert(const T &a);
T get();
};
Слайд 39
11.10. Шаблон списка
(продолжение)
template
void SList::insert(const T &a)
{
BList::insert(new
TLink(a));
}
Слайд 40
11.10. Шаблон списка
(продолжение)
template
T SList::get()
{
T res;
TLink *lnk
=
static_cast(BList::get());
Слайд 41
11.10. Шаблон списка
(продолжение)
if(lnk){
res = lnk->info;
delete lnk;
}
return res;
}
Слайд 42
11.10. Шаблон списка
(продолжение)
template
class SListIter:public BListIter{
public:
SListIter(SList &a):
BListIter(a){ }
T *operator()();
};
Слайд 43
11.10. Шаблон списка
(продолжение)
template
T *SListIter::operator()()
{
SLink *p = BListIter::operator()();
return
p ?
&(static_cast(p))->info :
NULL;
}
Слайд 44
11.11. Использование шаблона списка
int main()
{
SList st;
st.insert(12);
st.insert(25);
st.insert(38);
int res
= st.get();
std::cout
std::endl;
Слайд 45
11.11. Использование шаблона списка (продолжение)
SListIter it(st);
int *p =
NULL;
std::cout
' ';
std::cout << std::endl;
Слайд 46
11.11. Использование шаблона списка (продолжение)
std::cout
"
#2: 25
Для продолжения нажмите любую клавишу . . .