Schnelle Hilfe: Alghorithmus zum Löschen

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von maceroni, 7. April 2005 .

  1. 7. April 2005
    Hi @all!

    Habe eine Schulaufgabe bekommen, und zwar: Ich habe ein Integer Array ( Grösse = beliebig) in dem Werte zwischen Null (0) und Hundert (100) gespeichert sind! Nun soll ich alle Werte über 90 und alle Werte unter 10 löschen! Dabei soll nur das eine Array verwendet werden, verwendung von Pointern wäre erwünscht! Der Haken daran, der Alghorithmus soll Komplexität (n) haben (zeit) und wie erwähnt nicht zu große Platzkomplexität haben!
    Benutzt wird Borland C++!
    Also wer etwas weiss, bitte antworten!
    Ist dringend!!!
    Hoffe auf eure Hilfe, danke im Vorraus!!!
     
  2. 7. April 2005
    1. Welche Programmiersprache und welche Umgebung?
    2. Was verstehst du unter löschen? Auf 0 setzen?
    3. Ich wüsste ehrlich gesagt gar nicht, wie ich einen Algorithmus für dieses Problem schreiben sollte, dessen Komplexität nicht in n liegt?!
     
  3. 7. April 2005
    Programmiersprache ist C++, auf Dos Ebene falls du das meinst?!
    Nein das Array sollte dann um die gelöschten Werte kürzer sein, also entweder werden die anderen aufgeschoben, oder sonst so was. Ich habs noch nicht geschafft, programmier noch nich so lange!! Wie würdest du das machen, würde mich über das Prog freuen!
    Danke im Vorraus!!
    Ich bewerte euch sehr gut (10), danke!!!!
     
  4. 7. April 2005
    Da brummt euch euer Pauker aber fiesen kram auf!

    Nun erste und ich denke auch fast einzige Möglichkeit, wenn wirklich das tatsächliche Array verändert werden muss ist die Funktion realloc.
    Mit dieser Funktion kann der Speicherbereich Re-Allokiert werden und du kannst ihn entsprechend verkleinern.

    Wenn ihr allerdings tatsächlich C++ und nicht C programmiert, würde ich immer einen Vector bevorzugen. Vectoren haben die klassischen Eigenschaften von Arrays, sind aber noch um viele Möglichkeiten und Sicherheiten erweitert. Einen Anfänger-Guide zu diesen Vectoren findest du hier: http://www.codeguru.com/Cpp/Cpp/cpp_mfc/stl/article.php/c4027

    Ansonsten habt ihr doch bestimmt eine Art Aufgabenblatt bekommen, oder? Poste doch mal den genauen Wortlaut der Aufgabe, wenn ihr noch nicht lange Programmiert, kann ich mir eine solche Aufgabe nicht so richtig vorstellen.
     
  5. 8. April 2005
    Für mich sieht das eher so aus, als hätte da jemand einfach nicht aufgepasst...
     
  6. 8. April 2005
    Ne ist eigentlich eine Zusatzaufgabe, die er uns kurz erklärt hat! Hab ihn gestern nochmal gefragt, hat gesagt, das mit dem Verkleinern das Arrays ist doch zu schwer, deshalb sagte er: Ich soll die besagten werte aus dem Array "löschen", indem ich sie zb. mit einem sowiso unmöglichen Wert, wie zb. 900 überschreibe und an das Ende des Array setze, man muss aber danach genau wissen, wo im Array danach die veränderten oder "gelöschten" sich befinden! Dass man das Array dann anschließlich bis dort hin ausgibt! Es sollen halt keine "verbotenen" Werte also <10 und >90 mehr im Array stehen, oder beim Löschen Lücken im Array hinterlassen. Die ganzen Zahlen zwischen 10 und 90 sollten zum Schluss dann am Anfang des Arrays stehen!!!
     
  7. 8. April 2005
    Hi!

    Wenn ich das Problem richtig verstehe, kann man es vom Prinzip her so lösen:
    zwei Zeiger auf das Array.
    zu Begin:
    Zeiger A am Anfang und Zeiger B am Ende des Array's
    Schleife mit Abbruchkriterium: Position von A ist größergleich Position von B
    Innerhalb der Schleife tut sich folgendes:
    Zeiger A wandert vorwärts bis zur ersten Position mit verbotenem Wert.
    Zeiger B wandert rückwärts bis zur ersten Position mit erlaubten Wert, aber nicht weiter als Zeiger A.
    Tausche Inhalt von A mit Inhalt von B
     
  8. 8. April 2005
    So, ich würde es, denke ich, wie folgt machen. Auch wenn die Allokierungsfunktionen C und nicht C++ sind:

    Code:
    #include <iostream.h>
    #include <stdlib.h>
    #include <conio.h>
    
    int main()
    {
     int *array=NULL; //Array Zeiger deklarieren und mit NULL initialisieren
     int size = 200; //Größe des Array
    
     array = (int *)calloc(size, sizeof(int)); //Speicher allokieren. size-Anzahl Speichereinheit
     //der Größe des Types int (4 Byte).
     //Jede Speichereinheit wird mit 0 initalisiert und
     //die Startadresse des Bereiches wird in array speichern
    
     if(array == NULL) {
     cout << "Nicht genügend Speicher vorhanden";
     return EXIT_FAILURE;
     }
    
     for (int i=0; i < size; i++) // Eingabe aller Werte für das Array
     {
     cout << "Zahl " << i+1 << " eingeben: ";
     cin >> array[i];
     }
    
     if(size < 100) return EXIT_FAILURE; // Sicherstellen, dass das Array mind. 100 Elemente hat
    
     memmove(array, &array[9], 90 * sizeof(int)); // Kopieren des Speicherblockes.
     // Angefangen beim 10 Element des Array (array[9]).
     // Es werden 90 Elemente kopiert (insg. 360 Byte)
     // Adresse von array ist die Startadresse des neuen
     // Blocks
    
     array = (int *) realloc (array, 90 * sizeof(int)); // array auf 90 Elemente verkleinern und
     // überschüssigen speicher frei geben
     if(array == NULL) {
     cout << "Fehler bei Speicheränderung";
     return EXIT_FAILURE;
     }
    
     size = 90; //zur spätern weiterverwendung 
    
     cout << array[0]; // Ausgabe des 1. Elementes, was vorher das 10. Element war
     getch();
    
     free(array); //Speicherplatz frei geben
    
     return EXIT_SUCCESS;
    }
     
  9. 8. April 2005
    Jo danke, ich glaub das passt, habs überdacht, müsste klar gehen! Danke, Bewertung hab ich dir (ResusPos) schon eine 10 gegeben!
    Auch bitter hat für seine Hilfe eine 10!!!


    Danke für eure Hilfe!!!​
     
  10. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.