Sortieren von array-von typedef struct in C
Problem: beim Sortieren eines Arrays aus einer typedef struct habe ich erstellt (Telefonbuch).
Ziel: Versuche zu bauen, ein Telefonbuch, die ermöglicht Benutzern das hinzufügen, löschen, Sortieren und drucken Sie das Telefonbuch.
Wo ich bin: ich habe alles, außer die Sortierung. Ich habe mit Kopfsteinpflaster zusammen eine Art Funktion aus dem Lesen der verschiedenen web-Foren/Beispiele, aber kann nicht ankommen es zu wirken.
Problem ich bin mit: Nach hinzufügen von Einträgen (was gut funktioniert), wenn Sie versuchen, die Einträge Sortieren, die Funktion Nullen out-Werte dieser Einträge, und wenn Sie drucken Sie das Telefonbuch zeigt alle Einträge werden als leere. Es sollte Sie alphabetisch sortiert nach Nachnamen.
Hier ist die sort-Algorithmus habe ich in:
void Sort (phone phonebook[])
{
phone temp;
int i; int j;
for (i=0; i<19; i++)
{
for (j=i+1; j<19; j++)
{
if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0)
{
temp=phonebook[i];
phonebook[i]=phonebook[j];
phonebook[j]=temp;
}
}
}
}
Irgendwelche Ideen?
Vollständigen code hier:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//typedef struct to define what's in the phonebook
typedef struct PhoneBookContacts
{
char Name[20];
char Surname[20];
char PhoneNumber[20];
} phone;
//Function prototypes
void AddEntry (phone[]);
void DeleteEntry (phone[]);
void PrintEntry (phone[]);
void Sort (phone[]);
int counter = 0; //Global counter variable used to keep track of number of contacts
//Begin main function
int main (void)
{
phone phonebook[20]; //Phonebook instance
char userChoice; //Variable to use to select menu choice
while (userChoice != 'Q') {
printf ("***************\n");
printf ("Please enter a command:\n");
printf("'A': Add an entry\n");
printf("'D': Delete an entry\n");
printf("'S': Sort entries\n");
printf("'P': Print the phonebook\n");
printf("'Q': Quit\n");
printf ("***************\n");
scanf("%s", &userChoice); //Stores menu choice into variable userChoice
//Add Contact
if (userChoice == 'A')
AddEntry(phonebook);
//Remove Contact
if (userChoice == 'D')
DeleteEntry (phonebook);
//Print Contacts
if (userChoice == 'P')
PrintEntry(phonebook);
//Sort Contacts
if (userChoice == 'S')
Sort(phonebook);
//Quit
if (userChoice == 'Q') {
printf("Phonebook will now quit.");
return 0;
}
}
}
//Function Definition to Add Contacts to the Phonebook
void AddEntry (phone phonebook[]) {
counter++; //global counter increase
printf("\nFirst Name: ");
scanf("%s", phonebook[counter-1].Name); //counter-1 b/c arrays start at 0
printf("Last Name: ");
scanf("%s", phonebook[counter-1].Surname);
printf("Phone Number (XXX-XXX-XXXX): ");
scanf("%s", phonebook[counter-1].PhoneNumber);
printf("\n%s added to phonebook\n", phonebook[counter-1].Name); //tell user friend added
}
void DeleteEntry (phone phonebook[])
{
int x = 0;
char deleteName[20]; //Temp string to compare to existing phonebook
char deleteSurname[20]; //temp string
char nullStr[20] = {"\0"}; //empty string to remove phonenumber
printf("\nEnter name: ");
scanf("%s", deleteName); //place into temp string
printf("Enter Surname: ");
scanf("%s", deleteSurname); //place into temp string
for (x = 0; x < counter; x++)
{
if (strcmp(deleteName, phonebook[x].Name) == 0) //compare deleteName to phonebook.Name
{
for (x = 0; x < counter; x++)
{
if (strcmp(deleteSurname, phonebook[x].Surname) == 0) //If deleteSurname matches phonebook.Surname
{
strcpy(phonebook[x].Name, nullStr); //Put null into Name
strcpy(phonebook[x].Surname, nullStr); //Null into Surname
strcpy(phonebook[x].PhoneNumber, nullStr); //Null into PhoneNumber
printf("Contact removed from phonebook.\n");
counter--;
break;
}
}
}
else printf("Invalid entry--try again.\n");
}
}
//Function def to print contacts
void PrintEntry (phone phonebook[]) {
int x = 0;
printf("\nPhonebook entries:\n");
for ( x = 0; x < counter; x++) {
printf("\n(%d)\n", x+1); //Show contact number
printf("Name: %s %s\n", phonebook[x].Name, phonebook[x].Surname); //Name
printf("Number: %s\n", phonebook[x].PhoneNumber); //Number
}
}
void Sort (phone phonebook[]) {
phone temp;
int i; int j;
for (i=0; i<19; i++) {
for (j=i+1; j<19; j++) {
if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0) {
temp=phonebook[i];
phonebook[i]=phonebook[j];
phonebook[j]=temp;
}
}
}
}
- +1 für ein sehr gut Organisiertes Frage. 🙂
- Dies nicht Ihr problem lösen, aber man sollte wirklich betrachten mit radix sort anstelle von bubble-sort (es sei denn, Sie haben memory-allocation-Probleme). Es ist schon ein bisschen schneller - Average-case-performance - Radix O(n) vs. BubbleSort O(n^2).
- Er wird die Sortierung durch ein string-Feld; radix sort passt nur beim Sortieren von ganzen zahlen.
- "Ein Stellenwertsystem ist erforderlich, aber weil die ganzen zahlen können strings von Zeichen (z.B. Namen oder Daten) und speziell formatierte floating-point-zahlen, radix sort ist nicht beschränkt auf die ganzen zahlen." - Wikipedia
- .. oder benutzen Sie quicksort ist O(n log n), die nachweislich zu den am schnellsten alle Sortieren kann, und es kommt mit der C-Bibliothek, so dass Sie nicht haben, um es zu schreiben
- Sören: sorry, Sie sind falsch. Quicksort ist in der Regel der Schnellste im Durchschnitt, aber am schlimmsten ist immer noch O(n2). Und einige Sorten sind O(n) zu.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Können Sie die bereits implementierten Sortier-Funktion
qsort
- Funktion zur Verfügung zustdlib.h
:Die Funktion ist in der Regel Quicksort, aber das ist bis auf die C-Bibliothek-implementation zu entscheiden.
Update:
Die leere Liste ist, weil die Sortierung wird Umgekehrt, und immer Sortieren alle 19 Einträge der Telefonbuch, Vergleich der leere gegen die echten. Wenn Sie weniger als 19 Einträge auf das Telefonbuch, den aktuellen Daten präsent sein wird am Ende von das Telefonbuch-array.
Ihre ursprüngliche Funktion Sortieren war immer arbeiten fast OK. Ändern Sie einfach die Ende-Bedingung auf die beiden für.
Habe ich auch aktualisiert, meine
Sort
oben.qsort
ist nicht erforderlich, zu quicksort.Ersten Dinge zuerst, Sie haben einen buffer-overflow-Problem hier:
Dass
scanf
schreiben zwei bytes, wenn Sie geben Sie ein Zeichen (das Zeichen plus ein null-terminator). Diese beschädigt die ersten Namen des ersten Eintrags im Telefonbuch, in meinem Umfeld aber, da es ein Undefiniertes Verhalten, könnte es nichts!Können Sie dies umgehen, indem mit:
Dass wird nicht aufhören, einen Puffer-überlauf, wenn Sie genug text, aber es wird, wenn Sie beschränken sich auf einzelne Zeichen-Befehle. Wenn Sie möchten, eine wirklich robuste Benutzer-Eingangs-Funktion finden Sie unter hier.
Nun zu deinem konkreten problem. Es sieht aus wie Sie haben ein bisschen ein bubble-sort geht es, aber deine Logik ist etwas abseits. Vorausgesetzt, Sie wollen nicht zu verwenden
qsort
(das wäre der bessere Weg für die Echtzeit-code), die Sie gerade brauchen, um fix ein paar Sachen.Ihre äußere Schleife ist okay, wie ist Ihre innere Schleife, aber die innere Schleife sollte vergleichen von Elementen
j
undj+1
, nichtj
undi
. Das ist, weil es funktioniert, indem die Swap - angrenzenden Elemente, wenn Sie nicht in Ordnung.Zusätzlich darauf fokussiert bubble-sort werden die höchsten element an der Ende der Liste auf der erste pass, so dass Sie nicht starten können
j
beii+1
auf den zweiten pass, einfach weil die ersten element kann nicht richtig sein noch.Den folgenden Pseudo-code ist ein klassisches bubble-sort:
Gelesen, dass, zu verstehen, wie es funktioniert, dann setzen Sie es auf Ihrem eigenen. Wenn Sie Schwierigkeiten haben, mit, dass, ich habe eine funktionierende version unter:
Drei Probleme mit Ihrem code. Zunächst wird die Logik des Algorithmus. Bubble-sort funktioniert, indem man die Reihenfolge von zwei benachbarten element. In deinem code nach der ersten iteration der inneren
for
Schleife, es ist nicht zu vergleichen zwei benachbarte Elemente.Das zweite problem, wieder in der Sortier-Algorithmus, Ihre Zähler
i
undj
sind beide gehen auf 19, selbst, wenn es weniger Einträge als das. Dies kann mess up das Sortieren wie Sie Lesen werden, ungültig(nicht initialisierten) Eintrag. Sie sollten überprüfen Sie die Obergrenze für den Zähler.Der nächste ist, der die Löschung
Den code oben nicht richtig überprüfen, ob die erste und Nachname, da Sie die Prüfung separat. Sie brauchen nur eine
for
Schleife mitif( strcmp(deleteSurname, phonebook[x].Surname) == 0 && strcmp(deleteName, phonebook[x].Name) == 0 )