Процедура реализации очереди в виде циклического списка.

// Реализация простейшего кольцевого списка

template <class T>

class CircularList {

// Элементы списка состоят из собственно хранимого значения

//и указателя на следующий элемент списка.

struct ListItem {

Т item; // элемент списка

ListItem *next; // следующий элемент

ListItem(const T & item, ListItem *next = NULL) { ListItem::item = item;

Listltem::next = next;

}

};

// Список представлен указателем на последний элемент списка,

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

// Этот указатель будет пустым, если список не содержит элементов. ListItem *last;

public:

// Конструктор по умолчанию создает новый пустой список. CircularList() { last = NULL; }

// Конструктор копирования создает

// копию аргумента с помощью присваивания.

CircularList(const ClrcularList<T> & src) { *this = src; }

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

virtual ~CircularList() { destroy(); }

// Вставка новых элементов может производиться

// как в начало, так и в конец списка.

void insertHead(const T & item);

void insertTail(const T & item);

// Удалять можно только первый элемент

void removeHead();

// Функция 'empty' проверяет, содержит ли список хоть один элемент.

bool empty() const { return last == NULL; }

// Функции доступа дают возможность чтения/записи

//в первый и последний элементы списка

Т & head();

const T & head() const;

Т s tail ();

const T & tail () const;

// Оператор присваивания

CircularList<T> & operator = (const CircularList<T> & src);

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

void destroy();

};

template <class T>

void CircularList<T>::insertHead(const T & item) {

if (last == NULL) {

// Новый элемент будет одновременно первым и последним

last = new ListItem(item);

last->next = last;

} else {

// Новый элемент вставляется за последним

last->next = new ListItem(item, last->next); } }

template <class T>

void CircularList<T>::insertTail(const. T & item) {

insertHead(item);

// Чтобы первый элемент стал последним в кольцевом списке,

// достаточно сдвинуться вперед на один шаг

last = last->next; }

template <class T>

void CircularList<T>::removeHead() {

if (last == NULL) throw EmptyException();

if (last->next = last) {

// удаляется единственный элемент

delete last;

last = NULL;

} else {

ListItem * itemToDelete = last->next;

last->next = last->next->next;

delete itemToDelete; } }

template <class T>

T & CircularList<T>::head() {

if (last == NULL) throw EmptyException();

return last->next->item; }

template <class T>

const T & CircularList<T>::head() const {

if (last == NULL) throw EmptyException();

return last->next->item; '

}

template <class T>

T & CircularList<T>::tail() {

if (last == NULL) throw EmptyException();

return last->item; }

template <class T>

const T & CircularList<T>::tail() const {

if (last == NULL) throw EmptyException();

return last->item; }

// Оператор присваивания

template <class T>

CircularList<T> & CircularList<T>::operator =

(const CircularList<T> & src) {

destroy ();

if (!src.empty()) {

ListItem * current = src.last->next; // Указатель на первый элемент

do {

insertTail(current->item);

if (current = src.last) break; // Последний элемент добавлен

current = current->next;

} while (true);

}

return *this;

}

template <class T>

void CircularList<T>::destroy() {

while (last) removeHead(); }

// Теперь на базе определения кольцевого списка определим класс,

// реализующий абстрактную очередь.

template<class T>

class ListQueue: public Queue<T> {

CircularList<T> list; // Базовый список

public:

// Конструкторы и деструкторы определяются очень просто.

ListQueue(): list() {}

ListQueue(const ListQueue & src) { list = src.list; }

virtual ~ListQueue() {}

// Теперь определим и реализуем все абстрактные операции.

void enqueue(const T & item) { list.insertTail(item); }

void dequeue();

bool empty() const { return list.empty(); }

T & head();

const T & head() const;

T & tail();

const T & tail() const;

};

// Операция удаления элемента из очереди

template <class T>

void ListQueue<T>::dequeue() {

try {

return list.removeHead();

) catch (EmptyException) {

throw QueueUnderflow();

}

}

//Функции доступа к концевым элементам очереди

template <class T>

T & ListQueue<T>::head() {

try {

return list.head();

} catch (EmptyException) {

throw QueueUnderflow();

} }

template <class T>

const T & ListQueue<T>::head() const {

try {

return list.head();

} catch (EmptyException) {

throw QueueUnderflow();

})

template <class T>

T & ListQueue<T>::tail{) {

try {

return list.tail();

} catch (EmptyException e) {

throw QueueUnderflow();

}}

template <class T>

const T & ListQueue<T>::tail() const {

try {

return list.tail();

} catch (EmptyException e) {

throw QueueUnderflow();

} }

Побудувати клас параметризованого обмеженого масиву

#include <iostream.h>

#include <stdlib.h>

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

template <class Atype> class atype {

Atype *a;

int length;

public:

atype (int size);

~atype () { delete [] a; }

Atype &operator[] (int I);

};

// конструктор

template <class Atype> atype<Atype>::atype(int size)

{

length = size;

a = new Atype[size]; // динамически выделение области хранения

if (!a) {

cout << "Невозможно выделить массив";

exit (1);

}

for (int i=0; i<size; i++) a[i] = 0;

}

template <class Atype> Atype &atype<Atype>::operator [] (int i)

{

if (i<0 || i>length-1){

cout << "\nЗначение с индексом ";

cout << i << " выходит за пределы диапазона. \n";

exit (1);

}

return a[i];

}

int main ()

{

atype<int> intob(20); // массив целых чисел

atype<double> doubleob(10); // массив рациональных чисел

int i;

cout << "Массив целых: ";

for (i=0; i<20; i++)

{

intob[i] = i;

cout << intob[i] << " ";

}

cout << endl;

cout << "Массив дробных чисел: ";

for (i=0; i<10; i++)

{

doubleob[i] = (double)i * 3.14;

cout << doubleob[i] << " ";

}

cout << endl;

intob[45] = 100; // генерация ошибки

return 0;

}

Написати на С++ параметризовану функцію бінарного пошуку в масиві.

#include <iostream.h>

template <class Stype> int binary_search(Stype *item, int count, Stype key);

int main ()

{

char str[]="acdefg";

int nums[] = { 1, 5, 6, 7, 13, 15, 21 };

int index;

index = binary_search(str, (int)sizeof(str), 'd');

if (index>=0)

cout << "Найдено совпадение в позиции: " << index << endl;

else

cout << "Совпадение не найдено\n";

index = binary_search(nums, 7, 21);

if (index>=0)

cout << "Найдено совпадение в позиции: " << index << endl;

else

cout << "Совпадение не найдено\n";

return 0;

}

template <class Stype> int binary_search(Stype *item, int count, Stype key)

{

int low=0, high = count-1, mid;

while (low<= high) {

mid = (low + high) /2;

if (key < item[mid]) high = mid - 1;

else if (key>item[mid]) low = mid+1;

else return mid; // совпадение

}

return -1;

}

Розробити мовою С++ класс сортування даних, додавши в нього динамічний масив та його розмір, функції сортування методами прямого включення, швидкого сортування, функції вводу і виводу даних масива. Реалізувати функції сортування.

#include "iostream"

using namespace std;

class Sort

{

private:

int n;//кол-во элементов

int COUNT;

int *sortArray; //динамический массив

public:

Sort(int n)

{

this->n = n;

sortArray = (int*)malloc(n * sizeof(int));//выделение память под массив

COUNT = 0;

}

~Sort()

{

free(sortArray);//очистка массива

}

void SortForward();

void QuickSort(int *a, int n);

void Enter(int el);

void Show();

void QS();

};

//функция добавления эл-ов в массив

void Sort::Enter(int el)

{

sortArray[COUNT] = el;

COUNT++;

}

//вывод массива

void Sort::Show()

{

for(int i = 0; i < n; i++)

{

printf("%d->", sortArray[i]);

}

}

void Sort::QS()

{

QuickSort(this->sortArray, this->n - 1);

}

//быстраю сортировка

void Sort::QuickSort(int *a, int N)

{

int left = 0, right = N;

int temp, p;

p = a[N>>1];// центральный элемент

do

{

while (a[left] < p)

left++;

while (a[right] > p)

right--;

if (left <= right)

{

temp = a[left];

a[left] = a[right];

a[right] = temp;

left++; right--;

}

}

while (left <= right);

// рекурсивные вызовы, если есть, что сортировать

if (right > 0)

QuickSort(a, right);

if (N > left)

QuickSort(a + left, N - left);

}

//прямое включение

void Sort::SortForward()

{

int *arr;

arr = (int*)malloc(n * sizeof(int));

arr[0] = sortArray[0];

for(int i = 1; i < n; i++)

{

int tmp = sortArray[i];

arr[i] = tmp;

for(int j = i - 1; j >=0; j--)

{

if(arr[j + 1] < arr[j])

{

int buf = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = buf;

}

}

}

sortArray = arr;

}

int main()

{

int n;

scanf("%d", &n);

Sort *s = new Sort(n);

int el;

for(int i = 0; i < n; i++)

{

scanf("%d", &el);

s->Enter(el);

}

s->QS();

//s->SortForward();

s->Show();

return 0;}

Написати функцію зціплення двох одно направлених списків (голова другого спуска стоїть після останнього елемента першого списка).

#include <iostream.h>

struct node{

int d;

node *next;

};

void add(node **p, node **e, int d)

{

node *cur = new node; //новый узел

cur->d = d; //заполняем поле значения

cur->next = NULL; //посдедний

if ((*p) == NULL){ //если список пуст

*p = cur; //текущий - голова

*e = *p; //текущий - хвост

}

else{ //иначе

(*e)->next = cur; //у последнего узла указатель указывает на текщий

*e = cur; //текущий становится хвостом

}

}

//соединяет и возврящает голову(reth) и хвост(rett) нового спика

void connect(node * const p1, node * const p2, node **reth, node **rett)

{

node *tmp1 = p1;

node *tmp2 = p2;

while (tmp1){

add(reth,rett,tmp1->d);

tmp1 = tmp1->next;

}

while (tmp2){

add(reth,rett,tmp2->d);

tmp2 = tmp2->next;

}

}

void main()

{

node *h1 = NULL; //начало 1 списка

node *t1 = NULL; //конец 1 списка

node *h2 = NULL; //начало 2 списка

node *t2 = NULL; //конец 2 списка

node *h3 = NULL; //начало 3 списка

node *t3 = NULL; //конец 3 списка

add(&h1,&t1,1);

add(&h1,&t1,2);

add(&h1,&t1,3);

add(&h2,&t2,4);

add(&h2,&t2,5);

add(&h2,&t2,6);

connect(h1,h2,&h3,&t3);

node *tmp = h3;

while (tmp){

cout << tmp->d << " ";

tmp = tmp->next;

}

cout << endl;

}

Розробити клас двонаправленого списку, реалізувати функції: вставки елементу, вилучення елементу та очищення списку.

#include "iostream.h"

class list

{private:

int data;

list * prev;

list * next;

public: static list * first;

static list * current;

static void ins(int a);

static int del();

static void clear();

};

list * list::first=NULL;

list * list::current=NULL;

//вставка после текущего элемента

void list::ins(int a)

{ list * newnode;

newnode=new list;

newnode->data=a;

if(current!=NULL)

{ newnode->next=current->next;

current->next=newnode;

}

Else newnode->next=NULL;

newnode->prev=current;

if(newnode->next!=NULL) newnode->next->prev=newnode;

current=newnode;

if(first==NULL)first=current;

}

int list::del()

{ list * prevnode;

int result;

if(current==NULL)return -1;

result=current->data;

prevnode=current->prev;

if(prevnode!=NULL) prevnode->next=current->next;

if(current->next!=NULL) current->next->prev=prevnode;

if(current==first)first=current->next;

delete current;

current=prevnode;

if((current==NULL)&&(first!=NULL))current=first;

return result;

}

void list::clear()

{ while(first!=NULL)del();

}

void main()

{ list l;

l.ins(1);

l.ins(2);

l.ins(3);

cout<<l.del()<<endl;

l.current=l.first;

cout<<l.del()<<endl;

cout<<l.del()<<endl;

cout<<l.del()<<endl;

}

Використовуючи представлення багаточлена у виді лінійного списку, вузли якого містять показник ступеня і коефіцієнт (члени з нульовим коефіцієнтом не включати), написати функцію, що виконує додавання двох заданих багаточленів.

struct list

{

int inf1; //информационное поле - степень

int inf2; //коэффициент

list *next; //указатель на следующий элемент

};

typedef list *Plist; //ссылка на структуру

void add(Plist &p, int x, int y) //добавить в конец списка

{

Plist q;

q=new list;

q->inf1=x;

q->inf2=y;

q->next=NULL;

p->next=q;

p=q;

}

void add_1(Plist &p, int x, int y) //добавить первый элемент

{

Plist q=new list;

q->inf1=x;

q->inf2=y;

q->next=NULL;

p=q;

}

void polynom(Plist &p, int n) //формирование многочлена

{

int dig;

Plist q;

while (n>=0)

{

cin>>dig;

if (dig!=0) if (p==NULL) { add_1(p,n,dig); q:=p;}

else add(q,n,dig);

n--;

}

}

void readlist(Plist p) //печать многочлена

{

Plist q;

q=p;

while (q!=NULL)

{

cout<<q^.inf1<<":"<<q^.inf2<<" ";

q=q->next;

}

}

void sum_poly(Plist p1, Plist p2, Plist &p3) //сложение многочленов

{

Plist q1,q2,q3;

int m1,m2;

q1=p1; q2=p2; p3=NULL;

while (q1!=NULL || q2!=NULL)

{

m1=q1->inf1; m2=q2->inf1;

if (m1==m2) { if (p3==NULL)

{ add_1(p3,m1,q1->inf2+q2->inf2);

q3=p3;

q1=q1->next; q2=q2->next;

}

else { add(q3,m1,q1->inf2+q2->inf2);

q1=q1->next; q2=q2->next;

}

} //m1=m2

else if (m1>m2) {

if (p3==NULL) { add_1(p3,m1,q1->inf2);

q3=p3;

q1=q1->next;

}

else { add(q3,m1,q1->inf2);

q1=q1->next;

}

} //m1>m2

else

if (p3==NULL) {add_1(p3,m2,q2->inf2);

q3=p3;

q2=q2->next;

}

else {add(q3,m2,q2->inf2);

q2=q2->next;

}

}

}

Не нашли, что искали? Воспользуйтесь поиском: