Result=sum(Array,nrow,ncol); // определение суммы элементов
cout << "Result="<<Result<<endl;
free_memory(Array,nrow,ncol); // освобождение памяти
// Array[0][0]=1 // ошибка - массив Array не существует
Array=(int **)&Result; // но можно так, переменная Array статическая
return 0;
}
//------------------------------------------------------------------------------------
int** get_memory1(int nrow,int ncol)
// функция выделения памяти для двумерного массива
{ // возвращает указатель
int** array = new int*[nrow];
for (int i=0;i<nrow;i++)
array[i]=new int[ncol];
return(array);
}
//------------------------------------------------------------------------------------
void get_memory2(int **& array,int nrow,int ncol)
// функция выделения памяти для двумерного массива
{ // указатель передается по ссылке
array = new int*[nrow];
for (int i=0;i<nrow;i++)
array[i]=new int[ncol];
}
//------------------------------------------------------------------------------------
void free_memory (int** array,int nrow,int ncol)
// функция освобождения памяти
{
for (int i=0;i<nrow;i++)
delete array[i];
delete [] array ;
}
//------------------------------------------------------------------------------------
void vvod (int** array,int nrow,int ncol)
// функция заполнения матрицы, например так
{
for (int i=0; i<nrow; i++)
for (int j=0; j<ncol; j++)
array[i][j]=rand()%20;
}
//------------------------------------------------------------------------------------
void vyvod (int** array,int nrow,int ncol)
// функция вывода матрицы на экран
{
for (int i=0; i<nrow; i++)
{
for (int j=0; j<ncol; j++)
cout <<setw(5)<<array[i][j];
cout<<endl;
}
}
//------------------------------------------------------------------------------------
int sum(int** array,int nrow,int ncol)
// функция суммирования элементов матрицы
{
int Sum=0;
for (int i=0; i<nrow; i++)
for (int j=0; j<ncol; j++)
Sum+=array[i][j]; //накопление суммы
return (Sum);
}
Пример 4. Базовые операции со стеком
Программа, реализации базовых операций со стеком:
1. создаем стек из 5 элементов: 1,2,3,4,5.
2. вывод на экран элементов стека (5,4,3,2,1).
3. удаление всех элементов стека.
#include <iostream.h>
struct Node // описание элемента стека
{ int d;
Node* p; // указатель на следующий элемент стека
};
void push1 (Node** top,int d);
void push 2(Node*& top,int d);
void stek (Node* top);
int pop1 (Node** top);
int pop2 (Node*& top);
void main( void )
{
Node* top=NULL; // top – указатель вершины стека
for (int i=1;i<6;i++) push1(&top,i); // добавляем элементы в стек
// for (int i=1;i<6;i++) push2(top,i); // или так
stek (top); // выводим содержимое стека на экран
while (top)
cout<<pop1(&top)<<” ”; // выталкиваем элементы стека
// while (top)
// cout<<pop2(top)<<” ”; // или так
stek(top); // проверяем, что стек пуст
}
//------------------------------------------------------------------------------------
void push1(Node** top,int d)
// функция занесения элемента в вершину стека вариант 1
{ // top – указатель начала стека
Node* pv;
pv=new Node; // выделение памяти для элемента стека
pv->d=d;
pv->p=*top; // связываем новый элемент с предыдущим
*top=pv; // меняем адрес начала стека
}
//------------------------------------------------------------------------------------
void push2(Node*& top,int d)
// функция занесения элемента в вершину стека вариант 2
{ // top – указатель начала стека
Node* pv;
pv=new Node; // выделение памяти для элемента стека
pv->d=d;
pv->p=top; // связываем новый элемент с предыдущим
top=pv; // меняем адрес начала стека
}
//------------------------------------------------------------------------------------
int pop1(Node** top) // функция удаления элемента из вершины стека вариант 1
{ // top – указатель начала стека
Node* pv;
int temp;
temp=(*top)->d;
pv=*top;
*top=(*top)->p; // меняем адрес начала стека
delete pv; // освобождение памяти
return(temp);
}
//------------------------------------------------------------------------------------
int pop2(Node*& top) // функция удаления элемента из вершины стека вариант 2
{ // top – указатель начала стека
Node* pv;
int temp;
temp=top->d;
pv=top;
top=top->p; // меняем адрес начала стека
delete pv; // освобождение памяти
return(temp);
}
//------------------------------------------------------------------------------------
void stek(Node* top) // функция просмотра и вывода элементов стека на экран
{
while (top){
cout<<top->d<<' ';
top=top->p; // переход к следующему элементу стека
}
cout<<"\n";
}
Пример 5. Базовые операции с очередью
Программа, реализации базовых операций с очередью:
1. создаем первый элемент очереди (1)
2. добавляем в очередь из 4 элемента: 2,3,4,5.
3. вывод на экран элементов очереди (1,2,3,4,5).
4. удаление всех элементов очереди.
5. еще один вариант создания очереди (рекурсивный).
6. вывод на экран элементов очереди (1,2,3,4,5).
#include <iostream.h>
struct Node // описание элемента очереди аналогичен стеку
{ int d;
Node* p; // указатель на следующий элемент очереди
};
Node* first1 (int d);
void first2 (Node *&,int d);
void first3 (Node **,int d);
void add1 (Node** end,int d);
void add2 (Node*& end,int d);
void push(Node*& top,int d);
void ochered (Node* top);
int del1 (Node** top);
int del2 (Node*& top);
void main( void )
{ Node *top, *end; // top – указатель начала очереди, end – конец очереди
top=first1(1); // заносим первый элемент в очередь
// first2(top,1); // или так
// first3(&top,1); // или так
end=top; // последний есть первый
for (int i=2;i<6;i++) add1(&end,i); // добавляем элементы в конец очереди
// for (int i=2;i<6;i++) add2(end,i); // или так
ochered (top); // выводим содержимое очереди на экран
while (top) cout<<del1(&top)<<" "; // удаляем элементы очереди сначала
// while (top) cout<<del2(top)<<" "; // или так
ochered(top); // проверяем, что очередь пуста
for (i=1;i<6;i++) push(top,i); // другой способ создания очереди (рекурсивный)
ochered (top); // выводим содержимое очереди на экран
}
//------------------------------------------------------------------------------------
Node* first1(int d) // функция занесения первого элемента в очередь способ 1
{ Node* pv; // функция аналогична функции для стека
pv=new Node; // выделение памяти
pv->d=d;
pv->p=NULL;
return pv;
}
//------------------------------------------------------------------------------------
void first2(Node * &top, int d)
// функция занесения первого элемента в очередь способ 2
{ // функция аналогична функции для стека
top=new Node; // выделение памяти
top->d=d;
top->p=NULL;
}
//------------------------------------------------------------------------------------
void first3(Node **top, int d)
// функция занесения первого элемента в очередь способ 3
{ // функция аналогична функции для стека
*top=new Node; // выделение памяти
(*top)->d=d;
(*top)->p=NULL;
}
//------------------------------------------------------------------------------------
void add1(Node** end,int d)
// функция занесения элемента в конец очереди вариант 1
{ Node* pv; // end - адрес последнего элемента очереди
pv=new Node; // выделение памяти
pv->d=d;
pv->p=NULL;
(*end)->p=pv; // связываем с предыдущим элементом очереди
(*end)=pv; // меняем адрес последнего элемента
}
//------------------------------------------------------------------------------------
void add2(Node*& end,int d)
// функция занесения элемента в конец очереди вариант 2
{ // end - адрес последнего элемента очереди
Node* pv;
pv=new Node; // выделение памяти
pv->d=d;
pv->p=NULL;
end->p=pv; // связываем с предыдущим элементом очереди
end=pv; // меняем адрес последнего элемента
}
//------------------------------------------------------------------------------------
void push(Node*& top,int d) // функция занесения элемента в конец очереди
{ if (!top) // вариант 3 рекурсивный
{ top=new Node; // выделение памяти
top->d=d;
top->p=NULL;
}
else push(top->p,d); // рекурсия
}
//------------------------------------------------------------------------------------
int del1(Node** top)
// функция удаления элемента из начала очереди вариант 1
{ int temp; // top - указатель начала очереди
Node* pv; // функция аналогична функции для стека
temp=(*top)->d;
pv=*top;
*top=(*top)->p; // меняем адрес начала очереди
delete pv; // освобождение памяти
return(temp);
}
//------------------------------------------------------------------------------------
int del2(Node*& top)
// функция удаления элемента из начала очереди вариант 2
{ // top - указатель начала очереди
Node* pv; // функция аналогична функции для стека
int temp;
temp=top->d;
pv=top;
top=top->p; // меняем адрес начала очереди
delete pv; // освобождение памяти
return(temp);
}
//------------------------------------------------------------------------------------
void ochered(Node* top)
// функция просмотра и вывода элементов очереди на экран
{ // функция аналогична функции для стека
while (top)
{ cout<<top->d<<' ';
top=top->p;
}
cout<<"\n";
}
Пример 5. Базовые операции с линейным односвязным списком
Программа, реализации базовых операций с линейным односвязным списком:
1. создаем первый элемент списка (1)
2. добавляем в список 4 элемента: 6,5,4,3 (элементы в список добавляются по возрастанию ключей).
3. вывод на экран элементов списка (1,2,3,4,5).
4. удаление элемента списка со значением 3.
5. вывод на экран элементов списка (1,2,4,5).
#include <iostream.h>
struct Node // описание элемента списка аналогичен стеку и очереди
{ int d;
Node* p; // указатель на следующий элемент списка
};
void find_eq (Node* ,int , Node *&, Node *& );
void find_gt (Node* ,int , Node *&, Node *& );
void add (Node*& ,int );
void vyvod (Node* );
void del (Node*& ,int );
void main( void )
{ Node *top=NULL;
add(top,1); // заносим первый элемент в список
for (int i=5;i>1;i--) add(top,i); // добавляем элементы в список
// ключи вводятся по убыванию, но в список заносятся по возрастанию
vyvod(top); // выводим содержимое списка на экран
del(top,3); // удаляем элемент списка с ключом = 3
vyvod(top); // выводим содержимое списка на экран
}
//------------------------------------------------------------------------------------
void find_eq(Node* top,int k, Node *&pv, Node *& ppv)
// функция нахождения элемента c ключом =k
// top - адрес начала списка
// pv - адрес найденного элемента списка
// ppv - адрес предыдущего элемента списка
{
pv=top; ppv=top;
while (pv && pv->d != k ) // поиск элемента c ключом = k
{ ppv=pv; // запоминаем адрес предыдущего элемента
pv=pv->p;
}
}
//------------------------------------------------------------------------------------
void find_gt(Node* top,int k, Node *&pv, Node *& ppv )
// функция нахождения элемента c ключом >k
// top - адрес начала списка
// pv - адрес найденного элемента списка ppv - адрес предыдущего элемента списка
{ pv=top; ppv=top;
while (pv && pv->d <= k ) // поиск элемента c ключом > k
{ ppv=pv; // запоминаем адрес предыдущего элемента
pv=pv->p;
}
}
//------------------------------------------------------------------------------------
void add(Node*& top,int k) // функция занесения элемента c ключом k в список
// по возрастанию ключей элементов
{ // top - указатель начала списка
Node *nv, *pv=NULL,*ppv=NULL;
nv=new Node; // образуем новый элемент списка
nv->d=k;
nv->p=NULL;
if (!top) // если список пуст
{ top=nv; } // первый элемент списка
else
{ if (top->d >= k) // вставляем в начало списка
{ nv->p=top;
top=nv;
}
else
{ find_gt(top, k, pv, ppv); // поиск по ключу места для нового элемента
nv->p=pv; // вставляем между элементами с адресами ppv и pv
ppv->p=nv;
}
}
}
//------------------------------------------------------------------------------------
void vyvod(Node* top)
// функция просмотра и вывода элементов списка на экран
{
while (top)
{ cout<<top->d<<' ';
top=top->p;
}
cout<<"\n";
}
//------------------------------------------------------------------------------------
void del(Node*& top,int k) // функция удаления элемента c ключом k
{ // top - указатель начала списка
Node* pv, *ppv;
Find_eq(top, k, pv, ppv); // поиск элемента с ключом =k
if (pv) // если нашли
{
if (top->d == k) // удаляем первый элемент
top=top->p;
else
ppv->p=pv->p; // удаляем элемент из середины или конца списка
delete pv; // освобождение памяти
}
}
Пример 6. Базовые операции с линейным двусвязным списком
Программа, реализации базовых операций с линейным двусвязным списком:
1. создаем первый элемент списка (1)
2. добавляем в список 4 элемента: 6,5,4,3 (элементы в список добавляются по возрастанию ключей).
3. вывод на экран элементов списка (1,2,3,4,5).
4. вывод на экран элементов списка в обратном порядке (5,4,3,2,1).
5. удаление элемента списка со значением 3.
6. вывод на экран элементов списка (1,2,4,5).
7. вывод на экран элементов списка в обратном порядке (5,4,2,1).
#include <iostream.h>
struct Node
{
int d;
Node *next; // указатель на следующий элемент списка
Node *pred; // указатель на предыдущий элемент списка
};
void find (Node* ,int , Node *&, Node *& );
void find (Node* ,int , Node *&, Node *& , char );
void add (Node*& ,Node *&, int );
void vyvod1 (Node* );
void vyvod2 (Node* );
void del (Node*& ,Node *&,int );
void main( void )
{
Node *top=NULL, *end=NULL;
add(top,end,1); // заносим первый элемент в список
vyvod1(top); // выводим содержимое списка на экран
vyvod2(end); // выводим содержимое списка на экран в обратном порядке
for (int i=5;i>1;i--) add(top,end,i); // добавляем элементы в список
// ключи вводятся по убыванию, но в список заносятся
// по возрастанию, начиная с top;
vyvod1(top); // выводим содержимое списка на экран
vyvod2(end); // выводим содержимое списка на экран в обратном порядке
del(top,end,1); // удаляем элемент списка с ключом = 3
vyvod1(top); // выводим содержимое списка на экран
vyvod2(end); // выводим содержимое списка на экран в обратном порядке
}
//------------------------------------------------------------------------------------
void find(Node* top,int k, Node *&pv, Node *& ppv)
// аналогична односвязному списку
// функция нахождения элемента c ключом k top - адрес начала списка
// pv - адрес найденного элемента списка ppv - адрес предыдущего элемента
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
