Динамические структуры данных. Организация данных в списковые структуры

 

Перечень используемой литературы

1. М. Уэйт, С. Прата "Язык Си", М: МИР, 1988

2. У. Мюррей, К. Паллас "Visual C++", М: BHV, 1996

3. Богуславский А.А., Соколов С.М. Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. - Коломна: КГПИ, 2007.

4. Демидович Е.М. Основы алгоритмизации и программирования. Язык СИ : учебн. Пособие. - СПб.: БХВ-Петербург, 2008.

5. Дэвис С. С++ для «чайников». - К. : Диалектика, 2009.

6. Павловская Т.А. С/С++. Программирование на языке высокого уровня. - СПб: Питер, 2007.

7. Плохотников К.Э. Методы разработки курсовых работ. Моделирование, вычисления, программирование на С/С++ и МАТLAB, виртуализация, образцы лучших студенческих курсовых работ: учебное пособие. - М.: СОЛОН-ПРЕСС, 2008.

8. Подбельский В.В. Фомин С.С. Программирование на языке Си  - М.: Финансы и статистика, 2007.

9. http://www.intuit.ru/department/algorithms/staldata/28/

10. http://www.intuit.ru/department/algorithms/staldata/30/

 

Приложение А -  Код программы

// ---------------------------------------------------------------------------

#include <vcl. h>

#pragma hdrstop

#include "Unit1. h"

#include <stdio. h>

#include <stdlib. h>

// ---------------------------------------------------------------------------

#pragma package (smart_init)

#pragma resource "*. dfm"

TForm1 *Form1;

// ---------------------------------------------------------------------------

__fastcall TForm1:: TForm1 (TComponent* Owner)

: TForm (Owner)

{

}

// ---------------------------------------------------------------------------

struct tStack

{

char strFName [255] ;

char strRValue [6] ;

int numPar;

char** pParams;

bool bFilled;

tStack* pNext;

tStack ()

{

pNext = NULL;

numPar = 0;

bFilled = false;

}

void Add (char* strFName_, char* strRValue_, int numPar_, char** pParams_);

void Delete ();

void Print (TMemo* memo);

void Free ();

};

tStack* temp;

int num = 0;

int max_num = 1000;

void tStack:: Add (char* strFName_, char* strRValue_, int numPar_, char** pParams_)

{

if (num == (max_num-1)) MessageBox ("Almost Overload", "Warning ", MB_OK);

if (num == max_num)

{

MessageBox ("Overload", "", "Error", MB_OK);

}

num++;

if (pNext)

pNext->Add (strFName_, strRValue_, numPar_, pParams_);

else

{

if (! bFilled)

{

strcpy (strFName, strFName_);

strcpy (strRValue, strRValue_);

numPar = numPar_;

pParams = new char* [numPar] ;

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

{

pParams [i] = new char [6] ;

strncpy (pParams [i], pParams_ [i],

6);

}

bFilled = true;

}

else

{

pNext = new tStack;

pNext->Add (strFName_, strRValue_, numPar_, pParams_);

}

}

}

void tStack:: Delete ()

{

if (pNext)

if (pNext->pNext)

pNext->Delete ();

else

{

delete [] pNext;

pNext = NULL;

}

}

void tStack:: Print (TMemo* memo)

{

memo->Lines->Add ("* - -------------- - *");

memo->Lines->Add ("Имя функции: "+ (AnsiString) strFName);

memo->Lines->Add ("Возвращаемое значение: "+ (AnsiString) strRValue);

memo->Lines->Add ("Количество параметров: "+ (AnsiString) IntToStr (numPar));

memo->Lines->Add ("Параметры функции: ");

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

{

memo->Lines->Add (pParams [i]);

}

if (pNext)

pNext->Print (memo);

}

void tStack:: Free ()

{

if (temp) delete [] temp;

if (pNext)

{

temp = this;

pNext->Free ();

}

}

tStack* stack;

void __fastcall TForm1:: Button1Click (TObject *Sender)

{

if (! stack) stack = new tStack;

char* str = new char [Edit1->Text. Length () + 1] ;

strcpy (str, Edit1->Text. c_str ());

char* str2 = new char [Edit2->Text. Length () + 1] ;

strncpy (str2, Edit2->Text. c_str (),

6);

char* str3 = Edit3->Text. c_str ();

char* ptr = strtok (str3, "; ");

char** p = new char* [255] ;

int n = 0;

while (ptr)

{

p [n] = new char [6] ;

strncpy (p [n], ptr,

6);

ptr = strtok (NULL, "; ");

n++;

}

stack->Add (str, str2, n, p);

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Button4Click (TObject *Sender)

{

Memo1->Lines->Clear ();

if (! stack) return;

stack->Print (Memo1);

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Button2Click (TObject *Sender)

{

if (! stack) return;

if (! stack->pNext)

{

delete [] stack;

stack = NULL;

return;

}

stack->Delete ();

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Button3Click (TObject *Sender)

{

if (! stack) return;

stack->Free ();

delete [] stack;

stack = NULL;

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: FormCreate (TObject *Sender)

{

temp = NULL;

}

// ---------------------------------------------------------------------------

 

Приложнеи Б -  Контрольный пример

Введём в программу следующие значения:

имя функции 'summ'

возвращаемое значение '2a+3b';

параметры '2a; 3b; 0; 1';

и нажмем кнопку добавить.

Далее введём аналогичные данные соответственно:

'test_summ', 'abajaba', 'qwerty asd; asd fg; asdgf1; 123 d456' и нажмем кнопку добавить.

Теперь нажмём кнопку распечатать и получим следующее, учитывая особенности условия:

* - -------------- - *

Имя функции: summ

Возвращаемое значение: 2a+3b

Количество параметров: 4

Параметры:

2a

3b

0

1

* - -------------- - *

Имя функции: text_summ

Возвращаемое значение: abajab

Количество параметров: 4

Параметры:

qwerty

asd fg

asdfg1

123d4

Теперь нажмём кнопку удалить, а затем кнопку распечатать:

Имя функции: summ

Возвращаемое значение: 2a+3b

Количество параметров: 4

Параметры:

2a

3b

0

1

Далее нажмём кнопку очистить и при нажатии кнопки распечатать на экран программа ничего выводить не будет.

Приложения В - Блок схема

 

 
 
Приложения Г - Динамические структуры данных: очередь и стек

Стек и очередь - это частные случаи линейного списка.

Стеки

В списках доступ к элементам происходит посредством адресации, при этом доступ к отдельным элементам не ограничен. Но существуют также и такие списковые структуры данных, в которых имеютсяограничения доступа к элементам. Одним из представителей таких списковых структур является стековый список или просто стек.

Стек (англ. stack - стопка) - это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала (рис. 30.1). В стеках используется метод доступа к элементам LIFO ( Last Input - First Output, "последним пришел - первым вышел"). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю.

Стек - это список, у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.

Рисунок Б.1 -Стек и его организация

Описание стека выглядит следующим образом:

struct имя_типа {

                 информационное поле;

                 адресное поле;

                };

где информационное поле - это поле любого ранее объявленного или стандартного типа;

адресное поле - это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента стека.

Например:

struct list {

             type  pole1;

             list *pole2;

            } stack;

Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с заголовком стека, то есть не требуется осуществлять просмотр элементов, удаление и вставку элементов в середину или конец списка, то достаточно использовать экономичный по памяти линейный однонаправленный список. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует, и указатель принимает значение NULL.

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка. Поэтому объявим стек через объявление линейного однонаправленного списка:

struct Stack {

              Single_List *Top;//вершина стека

             };

. . . . . . . . . .

Stack *Top_Stack;//указатель на вершину стека

Основные операции, производимые со стеком:

создание стека;

печать (просмотр) стека;

добавление элемента в вершину стека;

извлечение элемента из вершины стека;

проверка пустоты стека;

очистка стека.

Реализацию этих операций рассмотрим в виде соответствующих функций, которые, в свою очередь, используют функции операций с линейным однонаправленным списком. Обратим внимание, что в функции создания стека используется функция добавления элемента в вершину стека.

//создание стека

void Make_Stack(int n, Stack* Top_Stack){

  if (n > 0) {

    int tmp;//вспомогательная переменная

    cout << "Введите значение ";

    cin >> tmp; //вводим значение информационного поля

    Push_Stack(tmp, Top_Stack);

    Make_Stack(n-1,Top_Stack);

  }

}

//печать стека

void Print_Stack(Stack* Top_Stack){

  Print_Single_List(Top_Stack->Top); 

}

//добавление элемента в вершину стека

void Push_Stack(int NewElem, Stack* Top_Stack){

  Top_Stack->Top =Insert_Item_Single_List(Top_Stack->Top,1,NewElem);

}

//извлечение элемента из вершины стека

int Pop_Stack(Stack* Top_Stack){

  int NewElem = NULL;

  if (Top_Stack->Top != NULL) {

    NewElem = Top_Stack->Top->Data;

    Top_Stack->Top = Delete_Item_Single_List(Top_Stack->Top,0);

    //удаляем вершину

  }

  return NewElem;

}

//проверка пустоты стека

bool Empty_Stack(Stack* Top_Stack){

  return Empty_Single_List(Top_Stack->Top); 

}

//очистка стека

void Clear_Stack(Stack* Top_Stack){

  Delete_Single_List(Top_Stack->Top); 

}

Пример 1. Дана строка символов. Проверьте правильность расстановки в ней круглых скобок.

В решении данной задачи будем использовать стек. Приведем главную функцию и функцию для проверки правильности расстановки круглых скобок.

//главная функция

int _tmain(int argc, _TCHAR* argv[]){

  char text[255];

  printf("Введите текст, содержащий \"(\" и \")\" \n");

  gets(text);

  Check_Brackets (text);

  system("pause");

  return 0;

}

//функция проверки правильности расстановки скобок

void Check_Brackets (char *text){

  int i;

  int flag=1;

  Stack *Top_Stack;

  Top_Stack = new Stack();

  for(i=0;i<strlen(text); i++) {

    if(text[i]==')' ) {

      if(Empty_Stack(Top_Stack)) {

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

        flag=0;

        break;

      }

    if(Top_Stack->Top->Data == '(')

        Pop_Stack(Top_Stack);

    else {

        flag=0;

        break;

       }

    }

    if(text[i]=='(')

    Push_Stack(text[i],Top_Stack);

  }

  if(flag!=0 && Empty_Stack(Top_Stack))

    printf("Верно!");

  else printf("Неверно!");

  Clear_Stack(Top_Stack);

  printf("\n");

}

Очередь - это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. В очереди используется принцип доступа к элементам FIFO ( First Input - First Output, "первый пришёл - первый вышел") (рис. Б.2). В очереди доступны два элемента (две позиции):начало очереди и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала. Примером может служить обыкновенная очередь в магазине.

 
Рисунок Б.2 -   Очередь и ее организация

Описание очереди выглядит следующим образом:

struct имя_типа {

                 информационное поле;

                 адресное поле1;

                 адресное поле2;

                };

где информационное поле - это поле любого, ранее объявленного или стандартного, типа;

адресное поле1, адресное поле2 - это указатели на объекты того же типа, что и определяемая структура, в них записываются адреса первого и следующего элементов очереди.

Например:

1 способ: адресное поле ссылается на объявляемую структуру.

struct list2 {

              type  pole1;

              list2 *pole1, *pole2;

             }

2 способ: адресное поле ссылается на ранее объявленную структуру.

struct list1 {

              type  pole1;

              list1  *pole2;

             }

struct ch3 {

            list1 *beg, *next ;

           }

Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Хотя для работы с таким списком достаточно иметь один указатель на любой элемент списка, здесь целесообразно хранить два указателя - один на начало списка (откуда извлекаем элементы) и один на конец списка (куда добавляем элементы). Если очередь пуста, то списка не существует, и указатели принимают значение NULL.

Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим очередь через объявление линейного двунаправленного списка:

struct Queue {

              Double_List *Begin;//начало очереди

              Double_List *End; //конец очереди

             };

. . . . . . . . . .

Queue *My_Queue;//указатель на очередь

Основные операции, производимые с очередью:

создание очереди;

печать (просмотр) очереди;

добавление элемента в конец очереди;

извлечение элемента из начала очереди;

проверка пустоты очереди;

очистка очереди.

Реализацию этих операций приведем в виде соответствующих функций, которые, в свою очередь, используют функции операций с линейным двунаправленным списком.

//создание очереди

void Make_Queue(int n, Queue* End_Queue){

  Make_Double_List(n,&(End_Queue->Begin),NULL);

  Double_List *ptr; //вспомогательный указатель

  ptr = End_Queue->Begin;

  while (ptr->Next != NULL)

    ptr = ptr->Next;

  End_Queue->End = ptr;

}

 

//печать очереди

void Print_Queue(Queue* Begin_Queue){

  Print_Double_List(Begin_Queue->Begin);

}

 

//добавление элемента в конец очереди

void Add_Item_Queue(int NewElem, Queue* End_Queue){

  End_Queue->End = Insert_Item_Double_List(End_Queue->End,

     0, NewElem)->Next;

}

 

//извлечение элемента из начала очереди

int Extract_Item_Queue(Queue* Begin_Queue){

  int NewElem = NULL;

  if (Begin_Queue->Begin != NULL) {

   NewElem = Begin_Queue->Begin->Data;

   Begin_Queue->Begin=Delete_Item_Double_List(Begin_Queue->Begin,0);

   //удаляем вершину

  }

  return NewElem;

}

 

//проверка пустоты очереди

bool Empty_Queue(Queue* Begin_Queue){

  return Empty_Double_List(Begin_Queue->Begin); 

}

 

//очистка очереди

void Clear_Queue(Queue* Begin_Queue){