View
6
Download
0
Category
Preview:
Citation preview
MEMORIA DINÁMICA
Administración del almacenamiento en tiempo de ejecución
Un programa en C almacena sus datos en memoria en tres áreas diferentes:
Tipos de memoria en C
Memoria global: Se almacenan todos los datos queestán presentes desde el comienzo del programahasta que finaliza.
Pila: Área en la que las variables aparecen ydesaparecen, usada principalmente paraalmacenar variables locales a las funciones.
Heap: Contiene memoria disponible para reservary liberar en cualquier momento durante la ejecuciónde un programa. Es la memoria “dinámica”.
Tipos de memoria en C
La memoria global tiene un tamaño fijo y que sesabe cuando comienza la ejecución de unprograma.
La pila y el heap albergan datos cuyo tamaño nose puede saber hasta que el programa está enejecución.
Las áreas de la pila y el heap tienen un tamañovariable, el Sistema Operativo reserva un espacioinicial y las dos zonas crecen y decrecen dentro deese espacio.
Pila
El funcionamiento de una pila es como un espaciode anotación temporal.
En ella se almacenan las variables locales de unafunción, así también los parámetros de una función.
En la pila se crea espacio para las variables y sedestruye al acabar la función.
Heap y la memoria dinámica
La memoria dinámica que se almacena en el heapse utiliza para resguardar datos que se crean enmedio de la ejecución de un programa.
En C se solicita tanta memoria en bytes como seanecesaria, y una vez que ya no es requerida, sedevuelve (libera) la memoria para poder serreutilizada.
Hay cuatro operaciones en C para gestionar lamemoria: *malloc(), *calloc(), free() y*realloc() y se encuentran en stdlib.h
Funciones de gestión de memoria en C
void *malloc(size_t size)
La función reserva tantos bytes consecutivos de memoria como lo indica size. Devuelve la dirección de memoria de la porción reservada. La memoria no se inicializa a ningún valor.
void *calloc(size_t nmemb, size_t size)Reserva espacio para tantos elementos como lo indica nmemb, y cada uno de ellos con un tamaño de byte size. Devuelve la dirección de memoria y la función inicializa todos los bytes de la zona en cero.
Funciones de gestión de memoria en C
void free(void *ptr)
Función que dado un apuntador, libera el espaciopreviamente reservado. El apuntador que recibe comoparámetro tiene que ser el que ha obtenido con unallamada de reserva de memoria.
void *realloc(void *ptr, size_t size)Función que redimensiona una porción de memoriapreviamente reservada. La función devuelve ladirección de memoria de la nueva porciónredimensionada y el apuntador no necesariamenteigual al que se ha pasado como parámetro. Los datosse conservan.
Función sizeof()
La función recibe como parámetro el nombre de lavariable, o el nombre de un tipo de dato, ydevuelve el tamaño en bytes.
sizeof(int) devuelve el número de bytes paraalmacenar un entero.
La función también devuelve el tamaño en bytes detipos de datos estructurados o uniones
Llamadas a funciones de gestión de memoria
Para invocar a la función malloc se puede enunciarde la siguiente manera. El espacio en memoriadinámica para una variable tipo T se obtiene
T *ptr = (T *)malloc(sizeof(T));
Una vez que una estructura de datos reservada conmemoria dinámica no se necesita, se libera mediante lallamada a la función free.
free(ptr);
PILA
Estructura de datos compuestos
Estructuras de datos
Estructuras de Datos
Estáticas
Datos simples
Arreglos
Matrices
Dinámicas
Lineales
Pila
Cola
Listas
No lineales
Árboles
Grafos
Estructuras estáticas
En las estructuras anteriores, la capacidadmáxima de las colecciones deben definirsepreviamente.
Ejemplo: persona_t Persona[100];
El programa reserva una cantidad de memoriafija, más allá de que durante su ejecución lautilice o no.
Conjuntos dinámicos
Los conjuntos son manipulados poralgoritmos que pueden crecer, disminuir oque cambian con respecto a sus dimensionestodo el tiempo son conocidos como dinámicos.
Una conjunto dinámico típicamente serepresenta con un atributo que puedeexaminarse y manipularse; y un apuntador aotro elemento del conjunto.
Estructura dinámica
En programación, una estructura dinámica es laimplementación de un conjunto dinámico.
La colección de valores del mismo tipo puede variardurante la ejecución del programa aumentando odisminuyendo, en consecuencia, utilizando mayor omenor cantidad de memoria.
Se puede formar una estructura dinámica“enlazando” nodos.
Pilas y colas (Stacks & queues)
De manera abstracta, las pilas y las colas sonconjuntos dinámicos en donde el elemento eliminadodel conjunto por la operación Delete estápredefinido.
En una pila, el elemento eliminado del conjunto es elque más recientemente se insertó Last-In First Out oLIFO .
En una cola, el elemento eliminado es siempre elprimero que se insertó al conjunto First-In First-Outo FIFO
Operaciones en una pila
La operación Insert() de una pila es llamadapush(), y la operación Delete() que no tomaargumentos, es llamada pop()
Los nombres hacen alusión a una pila de platos en una cafetería.
Implementación de una pila
Con un arreglo
a) La pila S tiene 4 elementos. El último es el 9
b) La pila después de la operación push(S,17) y push(S,3).
c) La pila después de pop(S) el cual regresa 3, el 3 aparece en el arreglo pero ya no en la pila.
Underflows y overflows
Cuando la pila no contiene elementos, la pila está vacía empty.
Si se efectúa un pop sobre la pila vacía, se dice que la pila subdesborda (underflows) y esto normalmente es un error.
Si la cantidad de elementos excede la capacidad de la pila, se dice que la pila desborda (overflows)
Pseudocódigo de las operaciones de una pila
empty(S)if S.top==0 return TRUE
elsereturn FALSE
push(S,x)if S.top == MAX
error “overflow”else
S.top = S.top +1S[S.top] = x
pop(S)if empty(S)
error “underflow”else
v = S[S.top] S.top = S.top-1
return v
PILA de forma dinámica
El nodo implementado en C
Un nodo representa un conjunto de uno o más valores,más un apuntador haciendo referencia al siguientenodo de la colección.
typedef struct nodo{int valor;struct nodo* sig;
} nodo_t;
nodo_t *apNodo;
valor sig
apNodo
Implementación de la pila con memoria dinámica
Agregar los elementos {3,2,1} en una pila. Definimos un apuntador p de tipo nodo_t* e inicializado en
NULL
nodo_t *p = NULL; Agregamos al inicio de la estructura apuntada por p los
elementos {3,2,1}, iniciando con 3, push(&p,3);
Agregamos el segundo elemento, push(&p,2);3 x
2 3 x
p
p
Implementación con memoria dinámica
Agregamos el 1, push(&p,1);
Luego para sacar un elemento de la pila, tomaremos el primero de la estructura definida.
Veamos el diagrama y la codificación de las funciones y una manera de definir la pila vacía
1 2 3 Xp
Push
void push(nodo_t** p, int v){
nodo_t* nuevo = (nodo_t*) malloc(sizeof(nodo_t));nuevo->valor = v;nuevo->sig = *p;*p = nuevo;
}
nodo_t *nuevo = (nodo_t*)malloc(sizeof(nodo_t))
nuevo->valor = v
nuevo-> sig = *p
*p = nuevo
Pop y empty
int pop(nodo_t** p){
nodo_t* aux = *p;int ret = aux->valor;*p = aux->sig;free(aux);return ret;
}
int empty(nodo_t* p){
return p == NULL;}
aux = *p
ret = aux -> valor
*p = aux -> sig
return ret
free(aux)
COLA (QUEUE)
Estructura de datos compuestos
Colas
La operación Insert() en una cola es llamada enqueue y la operación Delete de la cola dequeue
Una analogía de la estructura FIFO (First-In First-Out) es la fila para pasar a pagar en el super
Operaciones en una cola
Pensando en las colas como un conjuntodinámico, la operación de Insert() esenqueue (como el push de una pila) y laoperación Delete() es dequeue.
Se reconoce a estas operaciones como encolary desencolar aunque coloquialmente es másnatural decir “formarse en la fila” y “salir dela fila (de las tortillas o del super)”
Implementación de una cola estática (circular).
Usando arreglos
Los elementos de la cola Q aparecen más claros.
La cola tiene dos apuntadores, uno que marca el inicio head y uno que marca el final tail
a)la cola Q tiene 5 elementos: Q[7..11]
Implementación de una cola estática (circular)
b) La cola muestra el resultado de enqueue(Q,17), enqueue(Q,3) y enqueue(Q,5).
c) Vemos el resultado de la operación dequeue(Q) que devolvería el 15
Underflow y overflow
Una similitud de la cola con una pila es el error quese presenta al no tener elementos almacenados oexceder de ellos.
Los apuntadores head y tail serían iguales enambos casos de error, cuando no hay elementos(underflow) y cuando exceden el almacenamiento(overflow).
Pseudocódigo de enqueue y dequeue(circular)
Enqueue(Q,x)Q[Q.tail]=xif Q.tail== Q.length
Q.tail = 1else
Q.tail=Q.tail+1
Dequeue(Q)x=Q[Q.head]if Q.head == Q.length
Q.head = 1else
Q.head = Q.head+1return x
Implementación de la cola con memoria dinámica
De vuelta a la cola del super, la gente que llega ala cola se ubica al final. La cajera atiende alprimero, y ese cliente se retira para dejar su lugaral segundo y así sucesivamente.
Utilizaremos una estructura con dos apuntadores:uno al primer nodo del conjunto y uno al último.
Luego para enqueue() un elemento lo agregamos alfinal del conjunto y para dequeue() eliminamos alprimero de la lista.
Estructuras para el uso de queue
typedef struct nodo{
int valor;struct nodo *sig;
} nodo_t;
typedef struct queue{
nodo_t *head;nodo_t *tail;
} queue_t;
enqueue
void enqueue( queue_t *q , int v){
nodo_t *nuevo = (nodo_t *)malloc(sizeof(nodo_t));
nuevo->valor = v;nuevo->sig = NULL;
if(q->head == NULL && q->tail== NULL){
//primer elemento de qq->head = nuevo;q->tail = nuevo;
}else{
q->tail->sig = nuevo; // Enlazar el nuevo nodoq->tail = nuevo; // Recorre Tail al ultimo nodo
}}
dequeue
int dequeue( queue_t *q ){
int v_retorno = 0;nodo_t *aux;
if(q->head != NULL && q->tail != NULL ){
v_retorno = (q->head)->valor;aux = q->head;
if(q->head == q->tail){
// coloca los apuntadores a nulo// debido a que se trata del ultimo elementoq->head = NULL;q->tail = NULL;
}
dequeue (continuación)
else{// mover el apuntador headq->head = aux->sig; // q->head=(q->head)->sig;}free(aux);
}else{
printf("Q vacia, error de underflow \n");}
return v_retorno;}
crearQueue()
Cola circular
La cola circular es una mejora de la cola simple, debido a que es
una estructura de datos lineal en la cual el siguiente elemento del
último es, en realidad, el primero. La cola circular utiliza de
manera más eficiente la memoria que una cola simple.
Debido a que una cola circular es una mejora de la cola simple,
maneja las mismas operaciones para INSERTAR (ENCOLAR) y
ELIMINAR (DESENCOLAR).
Cola circular
Cuando se inserta un nodose verifica si el número deelementos que tiene laestructura es menor alnúmero máximo deelementos definidos, si esasí, existe espacio y elnuevo nodo se puedeinsertar, si el apuntador Tailse encuentra en la posiciónMAX , el apuntador Tail seasigna en la posición 1 dela estructura.
queue (circular)
typedef struct nodo { int valor; struct nodo* sig; //referencia al sig nodo } nodo_t; typedef struct queue { nodo_t *tail; } queue_t;
enqueue (circular)
void enqueue( queue_t *q, int v) {
nodo_t *nuevo = (nodo_t *)malloc(sizeof(nodo_t));nuevo->valor = v;
if( empty(q) ) {// Primer nodo nuevo->sig = nuevo;
} else {nuevo->sig = q->tail->sig;q->tail->sig = nuevo;// Enlazar el nuevo nodo
}q->tail = nuevo;
}
dequeue (circular)
int dequeue( queue_t *q ){
int v_retorno = 0;nodo_t *aux;if( empty(q) ) {
printf("Q vacia, error de underflow \n");} else {
v_retorno = (q->tail->sig)->valor;aux = q->tail->sig;if(aux == q->tail) {
q->tail = NULL;} else {
q->tail->sig = aux->sig;}
free(aux);}return v_retorno;}
empty
int empty( queue_t *q ) {
return q->tail == NULL? 1:0;
}
Implementación funcional de una cola
A continuación se muestra un ejemplo del funcionamiento de una colaint main() {
queue_t *q = crearQueue();//encolamos varios elementos enqueue(q,1);enqueue(q,2);enqueue(q,3);//desencolamos un elemento (sale el 1) printf("%d\n",dequeue(q));//desencolamos un elemento (sale el 2) printf("%d\n",dequeue(q));//encolamos mas elementos
return 0;}
Cola doble
Una cola doble (o bicola) es una estructura de datos tipocola simple en la cual las operaciones ENCOLAR yDESENCOLAR se pueden realizar por ambos extremos dela estructura, es decir, en una cola doble se puedenrealizar las operaciones:
Encolar por Head Desencolar por Head Encolar por Tail Desencolar por Tail
Cola doble
Recommended