Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Ringpuffer mit Arrays (Datenstrukturen)

Ein Ringpuffer (engl. Buffer) ist eine Warteschlange einer vorgegebenen Größe. Er kann Daten auf einer Seite anfügen und auf der anderen Seite wieder auslesen. Die folgenden Methoden müssen Sie zur Verfügung stellen:

  • init(maxCount: integer): initialisiert den Puffer mit einer maximalen Elementzahl.
  • add(o: Object): fügt ein Objekt am Ende des Puffers ein.
  • get(): Object: liest das Element aus, das schon am längsten im Puffer ist.

Implementieren Sie diese Schnittstelle mit einem Array. Daneben gibt es zwei (versteckte) Attribute: erster: integer und anzahl: integer.

Die Variable erster zeigt auf das Element, das zuerst eingefügt wurde, also dasjenige, das nun als nächstes ausgelesen werden soll (First in/First out = FiFo).

Die Variable anzahl gibt an, wie viele Elemente zurzeit gültig sind und somit auch, wo das nächste Element in den Array eingefüllt werden muss.

Das nächste einzufügende Element kann (falls erster > 0) die Array-Grenze sprengen, obschon wieder freier Platz auf den ersten Feldern vorhanden ist (s. Grafik). Die nächste freie Position ist somit (erster + anzahl) MODULO maxCount. MOD maxCount ist insofern wichtig, denn der nächste freie Platz kann auch vor dem ersten zu liegen kommen. Daher der Name Ringpuffer (s. Grafik).

Array als Ringbuffer

Wenn wir nun diesem Datentypen Ringpuffer jedes erdenkliche Objekt (String, integer, boolean, Verbund-Variable, ...) hinzufügen können, sprechen wir von einem abstrakten Datentypen.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

9 Lösung(en)

public class Queue {
    Object[] data;
    int      size      = 0; // anzahl
    int      startPos  = 0; // erster
    
    // init(maxSize)
    public Queue(int maxSize) {
        data = new Object[maxSize];  }
    
   public void add(Object object) {
        if(size >= data.length) {
            throw new  IndexOutOfBoundsException("Zu viele Elemente"); }
        int newPos  = getFirstFreePos();
        data[newPos] = object;
        size = size + 1;  }

    private int getFirstFreePos() {
        return (getLastFilledPos() + 1) % data.length; }

    private int getLastFilledPos() {
        return (startPos + size - 1) % data.length; }

    public int getSize() {
        return size;   }
 
    public Object get() {
        if(0 == size) { return null; }
        size = size - 1;
        Object o = data[startPos];
        startPos = (startPos + 1) % data.length;
        return o;
    }

} // end of class Queue
                
# Ringbuffer
class RingBuffer:
    def __init__(self, size):
        self.maxsize = size
        self.data = []
        self.size = 0

    def append(self, x):    
        self.data.append(x)
        if self.size < self.maxsize:
            self.size = self.size + 1
        else:
            self.data.pop(0)
            
    def get(self):
        if self.size > 0:
            self.size = self.size -1
            return self.data.pop(0)

    def get_buffer(self):
        return self.data

    def get_size(self):
        return self.size

r = RingBuffer(4)
for i in range(10):
    r.append(i)
    print r.get_buffer()
    
                

Lösung von: Martin Guggisberg (Universität Basel / PH FHNW)

#include <stdlib.h>
#include <string.h>

struct ringbuf {
	size_t max, elem_size;
	size_t n_elem;
	unsigned int start, end;
	void *buf;
};

enum {
	RINGBUF_SUCCESS = 0,
	RINGBUF_ERROR
};

struct ringbuf *ringbuf_new(size_t elem_size, size_t max)
{
	struct ringbuf *r;

	r = malloc(sizeof(*r));
	if (!r)
		return NULL;

	r->buf = calloc(max, elem_size);
	if (!r->buf) {
		free(r);
		return NULL;
	}

	r->max = max;
	r->elem_size = elem_size;
	r->n_elem = 0;
	r->start = 0;
	r->end = 0;

	return r;
}

void ringbuf_destroy(struct ringbuf *r)
{
	free(r->buf);
	free(r);
}

int ringbuf_put(struct ringbuf *r, void *elem)
{
	void *dest;

	if (r->n_elem == r->max)
		return RINGBUF_ERROR;

	dest = r->buf + r->end * r->elem_size;
	memcpy(dest, elem, r->elem_size);

	if (++r->end == r->max)
		r->end = 0;
	r->n_elem++;

	return RINGBUF_SUCCESS;
}
#define ringbuf_add(r,e) ringbuf_put(r,e)

int ringbuf_get(struct ringbuf *r, void *elem)
{
	void *src;

	if (!r->n_elem)
		return RINGBUF_ERROR;

	src = r->buf + r->start * r->elem_size;
	memcpy(elem, src, r->elem_size);

	if (++r->start == r->max)
		r->start = 0;
	r->n_elem--;

	return RINGBUF_SUCCESS;
}

#include <assert.h>
#include <stdio.h>
static void test(void)
{
	struct ringbuf *r;
	int a;

	r = ringbuf_new(sizeof(int), 2);
	if (!r) {
		fprintf(stderr, "Out of memory");
		return;
	}

	assert(ringbuf_get(r, &a) == RINGBUF_ERROR);

	a = 1;
	assert(ringbuf_put(r, &a) == RINGBUF_SUCCESS);
	assert(a == 1);

	a = 2;
	assert(ringbuf_put(r, &a) == RINGBUF_SUCCESS);
	assert(r->n_elem == 2);

	assert(ringbuf_get(r, &a) == RINGBUF_SUCCESS);
	assert(a == 1);
	assert(r->n_elem == 1);

	a = 3;
	assert(ringbuf_put(r, &a) == RINGBUF_SUCCESS);

	a = 4;
	assert(ringbuf_put(r, &a) == RINGBUF_ERROR);

	assert(ringbuf_get(r, &a) == RINGBUF_SUCCESS);
	assert(a == 2);

	assert(ringbuf_get(r, &a) == RINGBUF_SUCCESS);
	assert(a == 3);

	assert(ringbuf_get(r, &a) == RINGBUF_ERROR);
	assert(a == 3);

	ringbuf_destroy(r);
}

int main(void)
{
	test();

	return EXIT_SUCCESS;
}
                

Lösung von: Jonathan Neuschäfer (St.-Bernhard-Gymnasium, 47877 Willich)

package Queue;
use strict;
use warnings;

sub new {
	my $type = shift;
    my %params = @_;
    my $self = {};

    $self->{'Length'} = $params{'Length'};
	$self->{'Data'} = [];
    bless($self, $type);
}

sub get {
	my $self = shift;
	my $getitem = shift($self->{'Data'});
	return $getitem;
}

sub add {
	my ($self, $additem) = @_;
	my $arraysize = @{$self->{'Data'}};
	unless ($arraysize == $self->{'Length'}) {
		push($self->{'Data'},$additem);
		return 0;
	}
	else {
		return 1;
	}
}

1;
                

Lösung von: Name nicht veröffentlicht

class Ringpuffer(object):
    """Ringpuffer nach dem Vorschlag der Implementation"""
    def __init__(self, maxCount=1):
        self.init = self.__init__
        self.maxCount = maxCount
        self.array = [None for i in range(self.maxCount)]
        self.anzahl = 0
        self.erster = 0
    def add(self, obj):
        i = (self.erster+self.anzahl)%self.maxCount
        if self.array[i] is not None:
            raise RuntimeError("Die maximale Groesse des Ringpuffers wurde ueberschritten")
        self.array[i] = obj
    def get(self):
        r = self.array[self.erster]
        self.array[self.erster] = None
        self.erster = (self.erster+1)%self.maxCount
        return r

from collections import deque
class Ringpuffer2(deque):
    """Ringpuffer mit collections.deque als Basis-Klasse"""
    def __init__(self, maxCount=1):
        self.init = self.__init__
        super().__init__([], maxCount)
    def add(self, obj):
        if len(self) == self.maxlen:
            raise RuntimeError("Die maximale Groesse des Ringpuffers wurde ueberschritten")
        super().append(obj)
    def get(self):
        return super().pop()

                

Lösung von: Karl Welzel ()

function Queue(maxSize) {
  this.maxSize = maxSize || Number.MAX_VALUE;
  var arr = [];

  this.add = function(input) {
    try {
      if (arr.length == this.maxSize) throw "Überschreitung der Puffergröße";
      else {
        arr.unshift(input);
        return true;
      }
    }
    catch (err) {
      console.log(err);
      return false;
    }
  }

  this.get = function() {
    try {
      if (arr.length == 0) throw "Puffer ist leer";
      else return arr.pop();
    }
    catch (err) {
      console.log(err);
      return undefined;
    }
  }
}

var lummerland = new Queue(4);
lummerland.add("Lukas der Lokomotivführer");
lummerland.add("Alfons der Viertelvorzwölfte");
lummerland.add("Frau Waas");
lummerland.add("Her Ärmel");
if (!lummerland.add("Jim Knopf")) console.log(lummerland.get());

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

package ch.santis.buch.kapitel8.Ringpuffer;

public class RingPufferArray {

	public int[] puffer;
	public int head;
	public int size = 10;
	public int elements;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new RingPufferArray().run();
	}

	public void run()
	{
		init(size);  
		
		add(1);
		add(2);
		add(3);
		add(4);
		add(5);
		add(6);
		add(7);
		add(8);
		add(9);
		add(10);
		
		ArrayAuslesen();
		
		System.out.println("Auslesen: "+ get());
		System.out.println("Auslesen: "+ get());
		System.out.println();
		
		ArrayAuslesen();
		
		add(11);
		add(12);
		
		ArrayAuslesen();
		System.out.println("Auslesen: "+ get());
		ArrayAuslesen();
		add(13);
		ArrayAuslesen();
	}
	
	public void init(int size)
	{
		puffer = new int[size];
		head = 0;
		elements = 0;
	}
	
	public void add(int number)
	{
		if(elements == 0)  
		{
			puffer[head] = number;     
			
     		head++;	
			elements++;				
		}
		else if(elements > 0 )    
		{
			if(isPufferFree())
			{
				if(head == size)
				{
					head = 0;
				}
				
				puffer[head] = number;
				
	     		head++;	
				elements++;				
			}
			else
			{
				System.out.println("Puffer ist voll: "+ number);
			}
		}				
	}

	public int get()
	{
		int leseZeiger = head - elements;
		if(leseZeiger < 0 )
		{
			leseZeiger = elements + leseZeiger;
		}
		
		int getInt = puffer[leseZeiger];
		puffer[leseZeiger] = 0;
		elements--;
		return getInt;
	}
	
	public boolean isPufferFree()
	{
		if(elements < size)  
			return true;
	    else
	    	return false;
	}
	
	public void ArrayAuslesen()
	{
		for (int i = 0; i<puffer.length; i++)
		{
			System.out.println(i+": "+puffer[i]);
		}
		System.out.println();
	}
}

                

Lösung von: David Zeindler ()

package ch.santis.programmierenlernen.kapitel8;

import java.util.ArrayList;
import java.util.Scanner;

public class Aufgabe_8_5 {
	
	public static void main(String[] args) {
		new Aufgabe_8_5().top();
	}
	
	public class Ringpuffer {
		Object element;
	}
	
	void top() {
		// Es wird bewusst kein Array verwendet sondern eine ArrayList. Das erlaubt uns eine einfachere Programmierung
		// Genau genommen ist es eine lineare Warteschlange und nur ein sehr abstrakt gedachter Ringbuffer
		ArrayList<Ringpuffer> queue = new ArrayList<Ringpuffer>();
		int size = maxCount();
		String control = "";
		while(!"end".equalsIgnoreCase(control)) {
			control = eingabeString("\'add\' oder \'get\' eingeben. \'end\' zum beenden.");
			if("add".equalsIgnoreCase(control)) {
				add(queue, size);
			}
			else if("get".equalsIgnoreCase(control)) {
				get(queue, size);
			}
			else if("end".equalsIgnoreCase(control)) {
				System.out.println("Programm beendet.");
			}
			else {
				System.out.println("Ungültige eingabe!");
			}
		}
	}

	public ArrayList<Ringpuffer> get(ArrayList<Ringpuffer> queue, int size) {
		int qsize = queue.size();
		if(qsize > 0) {
			Ringpuffer r = new Ringpuffer();
			r 			 = queue.get(0);
			System.out.println("Ringbuffer ausgabe: " + r.element);
			queue.remove(0);
			return queue;
		}
		else {
			System.out.println("Ringpuffer ist leer!");
		}
		return queue;
	}
	
	public ArrayList<Ringpuffer> add(ArrayList<Ringpuffer> queue, int size) {
		int qsize = queue.size();
		if(qsize < size) {
			Ringpuffer r = new Ringpuffer();
			r.element	 = eingabeString("Element eingeben:");
			queue.add(r);
		}
		else if(qsize == size) {
			System.out.println("Ringpuffer ist voll!");
		}
		return queue;
	}
	
	public int maxCount() {
		int size = Integer.parseInt(eingabeString("Grösse des Ringpuffers angeben:").trim());
		return size;
	}
	
	// Scanner Einlesen
	Scanner sc = new Scanner(System.in);
	public String eingabeString(String text) {
		System.out.println(text);
		return sc.nextLine();
	}
	
}
                

Lösung von: Jan Roth (Santis Training AG)

class ringbuffer():
    def __init__(self, maxCount = 8):
        self.maxCount = maxCount
        self.ring = [None] * maxCount
        self.__anzahl = 0
        self.__erster = 0

    def add(self, object):
        nextPosition = (self.__erster + self.__anzahl) % self.maxCount
        if self.ring[nextPosition] is not None:
            raise IndexError("Zuviele Objekte eingefügt")
        else:
            self.ring[nextPosition] = object
        self.__anzahl += 1

    def get(self):
        self.__erster = (self.__erster % (self.maxCount))
        self.__anzahl -= 1
        temp = self.ring[self.__erster]
        self.ring[self.__erster] = None
        self.__erster += 1
        return temp
                

Lösung von: Peter Pan (Home Office)

Verifikation/Checksumme:

Beachten Sie, dass mit der Methode add() nicht mehr als maxCount Elemente in Serie eingefügt werden dürfen. Damit das nicht möglich ist, muss die Methode add() einen Fehlercode generieren können. Dies kann auf verschiedene Arten geschehen:

  1. Globale Fehlervariable
  2. Boole'scher Return-Wert
  3. Ausnahmebehandlung (Exception)

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: k.A.
Webcode: yui8-z5du
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen