6. Последовательности (динамические массивы).

Мы уже рассмотрели варианты создания массивов – статический, когда заранее известен размер, и динамический, когда выделяемая память запрашивается в процессе выполнения программы при помощи функции malloc.

В любом случае в результате с точки зрения АСД имеется статическиймассив. Будучи один раз распределенным в оперативной памяти, он обеспечивает в дальнейшем быструю реализацию доступа к своим элементам.

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

Подобные операции реализуются на основе перераспределенияпамяти. Но для обеспечения этой возможности использование стандартных типов данных языка Си уже становится недостаточным.

7. Реализация операций над последовательностями.

Будем рассматривать последовательность целых чисел и опишем ее при помощи структуры SEQ. Определим набор операций над этим типом данных:

Init – начальное распределение памяти под элементы последовательности;

Add – добавление к последовательности нового элемента;

Delete – удаление из последовательности указанного элемента;

GetAt – чтение элемента последовательности;

SetAt – запись элемента последовательности;

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <memory.h>

#include <conio.h>

typedef struct

{

int *pArr;

Int nMaxSize; // Размер выделенной области памяти

Int nSize; // Количество элементов последовательности

} SEQ;

int Init(SEQ* seq, int MaxSize);

int Add(SEQ* seq, int El);

void Delete(SEQ* seq, int n);

int GetAt(SEQ* seq,int n, int *res);

int SetAt(SEQ* seq, int n, int El);

Программа реализации интерфейса для последовательности:

#include "SEQ.h"

/////////////////////////////////////////////////////////

// Инициализация последовательности (захват памяти)

// seq - указатель на последовательность

// MaxSize - размер заказываемой памяти

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

// <количество элементов в последовательности> либо

// -1 - ошибка: память уже распределена

// -2 - ошибка распределения памяти

/////////////////////////////////////////////////////////

int Init(SEQ* seq, int MaxSize)

{

if (seq->pArr != NULL)

return -1;

seq->pArr = (int*) malloc(MaxSize*sizeof(int));

if (seq->pArr == NULL)

return -2;

seq->nMaxSize = MaxSize;

seq->nSize = 0;

return MaxSize;

}

/////////////////////////////////////////////////////////

// Добавление к последовательности нового элемента

// seq - указатель на последовательность

// El - записываемое значение

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

// <количество элементов в последовательности> либо

// -2 - ошибка распределения памяти

/////////////////////////////////////////////////////////

int Add(SEQ* seq, int El)

{

if (seq->nMaxSize == seq->nSize){

if (seq->pArr == NULL) {

if (Init(seq,10) < 0)

return -2;

}

else {

int *pArr;

pArr = (int*)malloc((seq->nMaxSize+10)*sizeof(int));

if (pArr == NULL)

return -2;

// Копия существующих элементов

memcpy (pArr, seq->pArr, seq->nMaxSize*sizeof(int));

free(seq->pArr); // Освобождение памяти

// Определение новых параметров последовательности

seq->pArr = pArr;

seq->nMaxSize += 10;

}

}

seq->pArr[seq->nSize++]=El;

return seq->nSize;

}

/////////////////////////////////////////////////////////

// Удаление элемента из последовательности

//

// seq - указатель на последовательность

// n - номер (адрес) удаляемого элемента

/////////////////////////////////////////////////////////

void Delete(SEQ* seq, int n)

{

if (seq->nSize < n)

return;

if (seq->nSize > n + 1)

{

memcpy(&seq->pArr[n],&seq->pArr[n+1],(seq->nSize-n-1)

*sizeof(int));

}

seq->nSize--;

}

/////////////////////////////////////////////////////////

// Чтение элемента

// seq - указатель на последовательность

// n - адрес считываемого элемента

// res-указатель,куда будет занесен код ошибки

// 0 - ошибки нет, -1 - ошибка

/////////////////////////////////////////////////////////

int GetAt(SEQ* seq, int n, int *res)

{ if (seq->nSize < n)

{

*res = -1;

return 0;

}

*res = 0;

return seq->pArr[n];

}

/////////////////////////////////////////////////////////

// Запись элемента по указанному адресу

// seq - указатель на последовательность

// n - номер (адрес) записываемого элемента

// El - записываемое значение

/////////////////////////////////////////////////////////

int SetAt(SEQ* seq, int n, int El)

{ if (seq->nSize < n)

return -1;

seq->pArr[n] = El;

return n;

}

Стеки, очереди, множества и их использование.