Bubblesort - Doppelte Zahlen vermeiden und ausgewählte Zahlen löschen in C

Verfasser Nachricht

Kempl

Beiträge: 82
Bewertung: 0
Registriert seit: May 2013
Status: offline

Beitrag: #1

Bubblesort - Doppelte Zahlen vermeiden und ausgewählte Zahlen löschen in C

Guten Tag,

ich sitze zur Zeit an einem Problem.
Ich habe ein Bubblesort Algorhythmus programmiert, der wie folgt funktioniert:

Man gibt eine Zahl ein und die wird gespeichert.
Man gibt eine zweite Zahl ein und die wird verglichen mit der Ersten.
Wenn die erste Zahl größer ist als die zweite, dann werden diese vertauscht.

Wie bekomme ich es hin, das wenn ich eine Zahl doppelt eingebe, das diese dann trotzdem nur einmal vorhanden ist?

Und wie kriege ich es hin eine Zahl aus dieser Liste herauszulöschen, sodass ich danach wiede eine neue eingeben kann?

Code:

#include <stdio.h>

int main()

{

    int i=0,zahlen[10];

    int tmp;

    char menu;

    do

    {    

        printf("\nAnwendungen:\n");

        printf("E,e,I,i Schluessel zum Einfuegen z.B. e27\n");

        printf("D,d,L,l Schluessel zum Loeschen z.B. l27\n");

        printf("Q,q,X,x zum Beenden:\n");

        scanf(" %c%d",&menu,&zahlen[i]);

        int d;

        if(menu == 'E' || menu == 'e' || menu == 'I' || menu == 'i')

        {

            for(d=0;d<=i;d++)

            {                

                if(zahlen[i] == zahlen[d])

                {    

                }

                if(zahlen[i] < zahlen[d])

                {

                    tmp = zahlen[d];

                    zahlen[d] = zahlen[i];

                    zahlen[i] = tmp;

                }

            }

            for(d=0;d<=i;d++)

            {

                printf("%d \t",zahlen[d]);

            }

        }

        i++;

    }

    while(menu == 'D' || i != 9);

    return 0;

}

Gruß
Kempl

22.03.2016 23:05

Diese Nachricht in einer Antwort zitieren

eret12

Beiträge: 1.130
Bewertung: 29
Registriert seit: Jun 2008
Status: offline

Beitrag: #2

RE: Bubblesort - Doppelte Zahlen vermeiden und ausgewählte Zahlen löschen in C

Hi,

anbei meine Lösung für dein Problem.
Ich habe aus Gründen der bequemlichkeit C++ anstatt C verwendet, was sich hier aber nur in der Eingabe/Ausgabe unterscheidet.

Mit dem Bubblesort direkt ist es nicht möglich duplikate zu umgehen, da du immer direkt im Array sortierst und keine zusätzliche Variable zur Verfügung hast. Es wäre natürlich möglich vor dem Beginn des Sortierens erst eine Schleife zu durchlaufen die nach einem Duplikat der Zahl sucht und wenn gefunden, das Sortieren verhindert. Dabei hättest du bei jedem Eintrag allerdings den doppelten Aufwand. Da heutzutage selbst auf kleinen Microcontrollern nicht mehr soooo stark auf Speicherplatz geachtet werden muss, wäre hier eine zusätzliche Variable empfehlenswert. So habe ich es auch in meinem Beispiel gelöst.

Code:

#include <iostream>

using namespace std;

// Initialisieren der Variablen die in jedem Schritt zur Verfügung stehen sollen.

int zahlen[10];

int i = 0;

char menu;

int main() 

{

    // Hier wird das Array mit 0-en aufgefüllt um einen definierten Zustand zu haben.

    // Wenn dies nicht gemacht wird können alle beliebigen Werte schon im Array stehen. (Fehlerquelle!)

    for (int d = 0; d <= 9; d++)

    {

        zahlen[d] = 0;

    }

    do 

    {

        cout << "E,e,I,i Schluessel zum Einfuegen z.B. e27\n";

        cout << "D,d,L,l Schluessel zum Loeschen z.B. l27\n";

        cout << "Q,q,X,x zum Beenden:\n";

        cin >> menu >> i;

        cout << "Menue: " << menu << ", i: " << i << endl << endl;

        // If-Abfrage ob befüllt werden soll

        if (menu == 'E' || menu == 'e' || menu == 'I' || menu == 'i')

        {

            // Schleife zum einsortieren. Für die Sortierung von klein nach groß (links nach rechts)

            // wird die Schleife rückwärts im Array laufen gelassen.

            for (int d = 9; d >= 0; d--)

            {

                // Abfrage ob die Eingegebene Zahl "i" größer oder gleich der Zahl im Array ist.

                if (i >= zahlen[d])

                {

                    // Sind die Zahlen gleich groß, so wird die for-Schleife abgebrochen.

                    if (i == zahlen[d])

                    {

                        break;

                    }

                    // Sonst wird die Zahl getauscht.

                    else

                    {

                        int tmp = zahlen[d];

                        zahlen[d] = i;

                        i = tmp;

                    }

                }

            }

            // Ausgabe des neu sortierten Arrays.

            for (int d = 0; d <= 9; d++)

            {

                cout << zahlen[d] << " ";

            }

            cout << endl << endl;

        }

        // Abfrage ob eine Zahl aus dem Array gelöscht werden soll.

        else if (menu == 'D' || menu == 'd' || menu == 'L' || menu == 'l')

        {

            // Auch beim Löschen wird das Array von hinten angefangen zu vergleichen.

            for (int d = 9; d >= 0; d--)

            {

                // Abfrage ob die Zahlen gleich sind.

                if (i == zahlen[d])

                {

                    // Ist die Zahl gleich wird sie durch eine "0" ersetzt.

                    zahlen[d] = 0;

                    // Die Null wird nun bis nach vorne durchgeschoben.

                    for (int e = d; e >= 1; e--)

                    {

                        zahlen[e] = zahlen[e - 1];

                        if (e == 1)

                        {

                            zahlen[0] = 0;

                        }

                    }

                }

            }

            // Ausgabe des neu sortierten Arrays.

            for (int d = 0; d <= 9; d++)

            {

                cout << zahlen[d] << " ";

            }

            cout << endl << endl;

        }

      // Die do-while-Schleife wird solange ausgeführt bis der Befehl zum Beenden gewählt wurde.

    } while (menu != 'Q' & menu != 'q' & menu != 'X' & menu != 'x');

    return 0;

}

Ich habe den Code möglichst detailiert Kommentiert um ihn nachvollziehbar zu machen.

Zu deinen Fragen:

1: Du musst die schon eingefügten Werte im Array mit dem einzufügenden Wert vergleichen. Sind sie gleich kannst du die Schleife mit break einfach stoppen, da hier nun keine weiteren Schritte notweendig sind.

2: Nun es gibt mehrere Möglichkeiten die Werte zu löschen. Entweder du sagst welche Position im Array gelöscht werden soll (was ich nicht so super finde), oder du sagst welche Zahl aus dem Array gelöscht werden soll. Zweites habe ich in meinem Beispiel verwendet. Das Array wird dan nach der zu löschenden Zahl abgesucht. Wird sie gefunden wird die Zahl durch eine 0 ersetzt und die 0 an die passende Stelle geschoben. Mit reinem Bubblesort wird das aber unschön.

Was mir generell aufgefallen ist an deinem Code:

1: Jedem int sollte zu Beginn ein definierter Wert zugewiesen werden, z.B. 0. Da du nicht weißt, was zuvor im Speicher der Variablen lag, könnte hier sonst alles mögliche schon drin stehen. Das gilt auch für das Array. Dieses sollte zu Beginn mit lauter 0-en aufgefüllt werden (oder eine andere beliebige Zahl).

2: Die Laufvariablen von for Schleifen sollten direkt in der Schleife Deklariert werden, da diese dann nur innerhalb der Schleife benutzt wird und danach wieder für das Programm zur verfügung steht.
for(int d=0; d<=9; d++)

3: Die Variable tmp sollte nur innerhalb der IF-Abfrage in der sie benutzt wird deklariert sein, da sie sonst unnötig Speicher beansprucht der sonst nirgends benötigt wird.

Sollten noch Fragen offen sein, kannst du mich auch gerne per PN anschreiben.

Geloeschter User schrieb:

Eine idee wäre es evtl mit einer Liste zu versuchen und nicht mit einem Array.
Wobei dein Array auch eine feste Länge hat.

Nimm eine Liste, da kannst du beliebig hinzufügen und löschen. Beim Array gibts den Fehler dass es beschränkt ist und due immer das ganze Array vergrößern musst und alle Zahlen im Array kopieren musst. Und wenn du eine kleinste Zahl einfügst musst du alle anderen einen "platz" nach hinten rücken, was auch zeitaufwendig ist.

Versuchs hiermit:
[Link: Registrierung erforderlich]

Nun ja es gibt auch andere Algorythmen um mit Arrays eine deutlich bessere Laufzeit beim Sortieren zu erhalten. Das Array sehe ich hier nicht als Problem. Gerade für einsteiger sind Arrays deutlich einfacher zu handhaben als Listen. Generell ist es gerade bei C++ oft vorteilhaft Arrays (String/Vektor) zu verwenden, da es dort sehr gut optimierte Befehle gibt um mit den Arrays zu arbeiten. Bei Listen gibt es diese nicht.

Lg eret12

Dieser Beitrag wurde zuletzt bearbeitet: 23.03.2016 12:56 von eret12.

23.03.2016 12:48

Kempl

Beiträge: 82
Bewertung: 0
Registriert seit: May 2013
Status: offline

Beitrag: #3

RE: Bubblesort - Doppelte Zahlen vermeiden und ausgewählte Zahlen löschen in C

Vielen Dank für die schnelle antworten.
Ich muss mit meinem Professor nochmal abklären, ob ich für dieses Programm jede Methode anwenden darf. Klar habe ich auch schon Listensysteme in programmieren 1 durchgenommen, allerdings muss ich diesen Algorhythmus in dem Modul "Algorhythmen und Datenstrukturen" programmieren.

Vielen Dank nochmal für die ganzen Antworten.

23.03.2016 17:44

Baumstrukturmodus | Brettstrukturmodus

« Ein Thema zurück | Ein Thema vor »

Möglicherweise verwandte Themen...
Thema:		Verfasser	Antworten:	Ansichten:	Letzter Beitrag
	Disqus Kommentare zählen	IaMmE	4	1.710	30.07.2013 09:29 Letzter Beitrag: Loster
	Dateien mit php von Webspace löschen	Swat 6	9	2.049	01.06.2013 18:45 Letzter Beitrag: Swat 6
	PHP Datei entpacken, löschen	Aaron	2	1.674	11.12.2012 14:22 Letzter Beitrag: Twinker
	[CGI] zeichen zählen und nach 7 zeichen unterbrechen	Stricted	0	1.457	19.01.2012 01:53 Letzter Beitrag: Terrax2
	Bitte löschen	Fast-Sponsoring	1	1.443	28.11.2011 19:00 Letzter Beitrag: _DEL0002

Druckversion anzeigen
Thema einem Freund senden
Thema abonnieren
Thema zu den Favoriten hinzufügen