Динамические структуры данных. Несвязанные динамические структуры данных. Связанные динамические структуры данных

Страницы работы

54 страницы (Word-файл)

Фрагмент текста работы

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 - адрес предыдущего элемента

Похожие материалы

Информация о работе

Тип:
Методические указания и пособия
Размер файла:
470 Kb
Скачали:
0