Списки - класс для звена списка

#ifndef _________ DATLINK_H

#define _________ DATLINK_H

#include <iostream.h>

class TDatLink;

typedef TDatLink *PTDatLink;

typedef int TData; // тип значений в СД

class TDatLink { protected:

TData Value; // значение

PTDatLink pNext; // указатель на следующее звено public:

TDatLink (TData Val = 0) { Value = Val; pNext = NULL;

}

void SetDatValue (TData Val) { Value = Val; }

TData GetDatValue () { return Value; }

void SetNextLink (PTDatLink pLink) { pNext = pLink; }

PTDatLink GetNextLink () { return pNext; } friend class TList;

t;

#endif

Вопрос 2.8. Представление отношения следования с использованием указателей. Понятие линейного списка. Реализация класса Стек на списке с использованием динамического выделения памяти.

Необходимость перепаковки для обеспечения динамического распределения памяти возникает в силу принятого способа реализации отношения следования - следующий элемент структуры располагается в следующем элементе памяти (с адресом большим на 1)

Устранение перепаковки возможно только при кардинальном изменении способа реализации основных отношений - необходимо допустить размещение следующих элементов структуры в произвольных элементах памяти (там, где имеется свободные области памяти)

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

Интерпретация содержимого элемента памяти (значение или адрес следующего элемента) в самом простом варианте может быть обеспечена фиксированным форматом используемых участков памяти

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой.

class TListStack: public TDataCom { protected:

PTDatLink pFirst; 11 указатель на первое звено списка public:

TListStack () { pFirst = NULL; }

int IsFull (void) const; // контроль переполнения СД

int IsEmpty (void) const; // контроль переполнения СД

virtual void Put (TData Val); // добавить значение в стек virtual TData Get(void); // извлечь значение из стека (#JI1)

// служебные методы

virtual void Print(); // печать значений

// virtual void Paint(int у,int xl,int x2) {} // показать рисунок структуры // virtual int IsValidO { return 0; } // тестирование структуры

// virtual void CopyToQueue(TQueue *pQ) {} // копировать в очередь

};

#endif

#include "datlist.h"

int TListStack:: IsFull(void) const { // контроль пустоты СД PTDatLink рТешр - new TDatLink(); int res = (pTemp==NULL)? 1: 0; delete pTemp; return res;

/*-------------------------------------------------------------------------------------------- */

int TListStack:: IsEmpty(void) const { // контроль переполнения СД return pFirst -= NULL;

}

/*-------------------------------------------------------------------------------------------- */

void TListStack:: Put (TData Val) { // добавить значение в стек if (IsFull()) SetRetCode (DataFull); else {

PTDatLink pTemp = new TDatLink(); pTemp->SetDatValue(Val); pTemp->SetNextLink(pFirst); pFirst = pTemp; SetRetCode (DataOK);

}

}

/*------------------------------------------------------------------------------------------------------------------- */

TData TListStack:: Get (void) { // извлечь значение из стека TData Val; // SKIP_ON

if (IsEmpty()) SetRetCode (DataEmpty); else {

PTDatLink pTemp = pFirst; Val = pFirst->GetDatValue(); pFirst = pFirst->GetNextLink (); delete pTemp; SetRetCode (DataOK);

}

return Val; // SKIP_OFF

}

/*-------------------------------------------------------------------------------------------- */

void TListStack:: Print(void) { // печать стека PTDatLink pTemp = pFirst;

cout << "Печать стека (от вершины)" << endl; while (pTemp!= NULL) {

cout << pTemp->GetDatValue () «" ¹¹; pTemp = pTemp->GetNextLink();

}

cout << endl;

}

void main () { TListStack mst; int code, temp, val=0; clrscr();

cout << "Тестирование системы поддержки стеков (списки)" << endl; cout << "Нажмите любую клавишу" << endl; while (1) { va1 + +;

code = random(4); // операция if (code<2) mst.Put(val); else temp=mst.Get(); if (kbhit()) break;

}

getch ();

cout «"Печать стека" «endl; mst.Print ();

cout << "Нажмите любую клавишу" << endl; getch ();

while (!mst.IsEmpty()) temp=mst.Get();

}

Вопрос 2.9. Представление отношения следования с использованием указателей. Понятие линейного списка. Реализация класса Очередь на списке с использованием динамического выделения памяти.

Необходимость перепаковки для обеспечения динамического распределения памяти возникает в силу принятого способа реализации отношения следования - следующий элемент структуры располагается в следующем элементе памяти (с адресом большим на 1)

Устранение перепаковки возможно только при кардинальном изменении способа реализации основных отношений - необходимо допустить размещение следующих элементов структуры в произвольных элементах памяти (там, где имеется свободные области памяти)

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

Интерпретация содержимого элемента памяти (значение или адрес следующего элемента) в самом простом варианте может быть обеспечена фиксированным форматом используемых участков памяти

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой.

(КОД ИЛИ ПОТОМ НАЙДУ, ИЛИ С ТЕЛЕФОНА)

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