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

11 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)

// NET 6.x | C# 10.x | VS-2022

var rb = new RingBuffer(8);
new List<object> { "eins", '2', 3, 0x4, 0b101 }.ForEach(x => rb.Add(x));
Console.WriteLine($"Puffergroesse: {rb.BufferSize}");
Console.WriteLine($"\nAnzahl Elemente: {rb.BufferCount}");
rb.Print();
Console.WriteLine($"\nRemoved: {rb.Get()}\n");
Console.WriteLine($"Anzahl Elemente: {rb.BufferCount}");
rb.Print();

class RingBuffer {
    private int _bufferSize = int.MaxValue;
    private readonly List<object>? _buffer = null;

    public RingBuffer(int bufferSize) {
        BufferSize = bufferSize;
        _buffer = new List<object>(_bufferSize);
    }

    public void Add(object? obj = null) {
        if (_buffer?.Count < _bufferSize)
            _buffer?.Insert(0, obj ?? "null");
    }

    public object? Get() {
        object? r = null;
        if (_buffer?.Count != 0) {
            r = _buffer?[^1];
            _buffer?.RemoveAt(_buffer.Count - 1);
        }
        return r;
    }

    public int BufferSize { get => _bufferSize; private set => _bufferSize = value; }

    public int BufferCount => _buffer?.Count ?? 0;

    public void Print() => _buffer?.ForEach(Console.WriteLine);
}

Lösung von: Jens Kelm (@JKooP)

// C++ 20 | VS-2022
#include <iostream>
#include <vector>
#include <sstream>  // std::stringstream
#include <format>   // std::format (C++ 20 needed!)

template<class T>
class RingBuffer {
    size_t buffer_size_{};
    std::vector<T> ring_buffer_{};
public:
    RingBuffer() { }
    RingBuffer(size_t buffer_size) : buffer_size_{ buffer_size } { }
    RingBuffer(size_t buffer_size, const std::vector<T>& elements) : buffer_size_{ buffer_size } {
        const auto max{ elements.size() <= buffer_size ? elements.size() : buffer_size };
        for (size_t i{ 0 }; i < max; ++i) add_new_element(elements[i]);
        std::cout << std::format("{} von {} Elementen hinzugefuegt.\n", max, elements.size());
    }

    constexpr auto add_new_element(T value) noexcept {
        if (ring_buffer_.size() < buffer_size_) {
            ring_buffer_.insert(ring_buffer_.begin(), value);
            std::cout << std::format("Element ({}) hinzugefuegt!\n", value);
        }
        else {
            std::cout << std::format("Element ({}) nicht hinzugefuegt - Puffer voll!\n", value);
        }
    };

    constexpr auto get_all_elements() const noexcept {
        std::stringstream ss;
        for (const auto& elem : ring_buffer_)
            ss << elem << " ";
        return ss.str();
    };

    constexpr T get_first_element() {
        if (ring_buffer_.size() != 0) {
            const auto first{ ring_buffer_.back() };
            ring_buffer_.pop_back();
            return first;
        }
        throw "Keine Elemente im Puffer vorhanden!\n"; // vereinfachte Ausnahmebehandlung
    };

    constexpr auto get_buffer_size() const noexcept {
        return buffer_size_;
    };

    constexpr auto set_buffer_size(size_t value) noexcept {
        if (value < buffer_size_) {
            std::cout << std::format("Fehler - Puffergroesse ({}) kleiner als Anzahl Elemente im Puffer ({})!\n", value, get_number_of_elements());
        }
        else {
            buffer_size_ = value;
            std::cout << std::format("Puffergroesse wurde erfolgreich auf {} gesetzt!\n", value);
        }
    }

    constexpr auto get_number_of_elements() const noexcept {
        return ring_buffer_.size();
    };

    friend std::ostream& operator<<(std::ostream& os, const RingBuffer<T>& rb) noexcept {
        os << std::format("\tPuffergroesee: {}\n", rb.get_buffer_size());
        os << std::format("\tAnzahl Elemente: {}\n", rb.get_number_of_elements());
        os << std::format("\tElemente: {}\n", rb.get_all_elements());
        return os;
    }
};

auto main() -> int {
    try { // notwendig - falls Puffer leer, wird Ausnahme ausgelöst!

        // Variante 1 - ohne Festlegung der Puffergröße bei der Initialisierung -> 0
        std::cout << "Variante 1:\n";
        RingBuffer<int> rb1{};
        rb1.set_buffer_size(3);     // Puffergröße festlegen
        rb1.add_new_element(2);
        rb1.add_new_element(3);
        rb1.add_new_element(5);
        rb1.add_new_element(7);     // wird nicht hinzugefügt, da Puffer voll
        std::cout << rb1 << "\n";
        std::cout << std::format("Am laengsten im Puffer und entfernt: {}\n", rb1.get_first_element());
        std::cout << rb1 << "\n";
        rb1.add_new_element(7);     // jetzt wieder möglich
        std::cout << rb1 << "\n";
        rb1.set_buffer_size(2);     // Fehler, da noch 3 Elemente im Puffer
        rb1.set_buffer_size(10);    // möglich

        // Variante 2 - Festlegen der Puffergröße bei der Initialisierung
        std::cout << "\nVariante 2:\n";
        RingBuffer<const char*> rb2{ 3 };
        rb2.add_new_element("Meyer");
        rb2.add_new_element("Mueller");
        std::cout << rb2 << "\n";

        // Variante 3 - Festlegen der Puffergröße und Übergabe von Elementen bei der Initialisierung
        std::cout << "\nVariante 3:\n";
        RingBuffer<char> rb3{ 4, { 'a', 'b', 'c', 'd', 'e', 'f'}};
        std::cout << rb3 << "\n";
        std::cout << std::format("Am laengsten im Puffer und entfernt: {}\n", rb3.get_first_element());
        rb3.set_buffer_size(8);
        rb3.add_new_element('g');
        std::cout << rb3 << "\n";
    }
    catch (const char* msg) {
        std::cerr << msg << "\n";
    }
}

Lösung von: Jens Kelm (@JKooP)

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