Сортировка массива из typedef struct в C
Проблема. Попытка сортировать массив из созданной мной структуры typedef (телефонной книги).
Цель: попытка создания телефонной книги, которая позволяет пользователям добавлять, удалять, сортировать и печатать телефонную книгу.
Где я нахожусь в: у меня все работает, кроме сортировки. Я объединил функцию сортировки от чтения различных веб-форумов/примеров, но не могу заставить ее работать.
Проблема У меня есть: после добавления записей (что отлично работает), если вы пытаетесь сортировать записи, функция обнуляет значения этих записей и когда вы печатаете телефонную книгу, она показывает все записи пусты. Он должен сортировать их по алфавиту по фамилии.
Вот алгоритм сортировки, который у меня есть:
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;
}
}
}
}
Любые идеи?
Полный код здесь:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//typedef struct to define what 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
Вы можете использовать уже реализованную функцию сортировки qsort, доступную в stdlib.h:
int SortFunc(void* a, void* b) {
phone *p1 = (phone*)a;
phone *p2 = (phone*)b;
return strcmp(p1->Surname, p2->Surname);
}
void Sort (phone phonebook[]) {
qsort(phonebook, counter, sizeof(phone), &SortFunc);
}
Обычно функция Quicksort, но это зависит от реализации библиотеки C.
Update:
Пустое перечисление состоит в том, что сортировка отменяется и всегда сортирует все 19 элементов телефонной книги, сравнивая пустые с реальными. Если в телефонной книге имеется менее 19 записей, фактические данные будут присутствовать в конце массива телефонной книги.
Ваша первоначальная функция сортировки всегда работала почти нормально. Просто измените конечное условие на два для.
void Sort (phone phonebook[]) {
phone temp;
int i; int j;
for (i=0; i<counter; i++) {
for (j=i+1; j<counter; j++) {
if (strcmp(phonebook[i].Surname, phonebook[j].Surname) > 0) {
temp=phonebook[i];
phonebook[i]=phonebook[j];
phonebook[j]=temp;
}
}
}
}
Я также обновил мой Sort выше.
Ответ 2
Во-первых, у вас проблема с переполнением буфера:
char userChoice;
:
scanf("%s", &userChoice);
То, что scanf будет писать два байта при вводе одного символа (символ плюс нулевой ограничитель). Это испортило первое имя первой записи телефонной книги в моей среде, но, поскольку это поведение undefined, оно может сделать что угодно!
Вы можете обойти это, используя:
char userChoice[] = "something that not Q";
:
scanf("%s", userChoice);
:
if (*userChoice == 'A') // for all of these.
Это не остановит переполнение буфера, если вы введете достаточно текста, но это произойдет, если вы ограничитесь одиночными командами символов. Если вы хотите по-настоящему надежную функцию ввода пользователя, см. здесь.
Теперь к вашей конкретной проблеме. Похоже, у вас есть немного пузырьков, которые происходят там, но ваша логика немного выключена. Предполагая, что вы не хотите использовать qsort (что было бы лучшим способом для реального кода), вам просто нужно исправить несколько вещей.
Ваш внешний цикл в порядке, как и ваш внутренний цикл, но тело внутреннего цикла должно сравнивать элементы j и j+1, а не j и i. Это потому, что он работает путем замены соседних элементов, если они не соответствуют порядку.
Кроме того, сперва сфокусированная сортировка пузырьков поместит самый высокий элемент в конце списка на первом проходе, поэтому вы не сможете запустить j на i+1 на втором проходе, просто потому, что первый элемент может быть еще не верным.
Следующий псевдо-код - ваш классический вид пузыря:
didSwap = true
while didSwap:
didSwap = false
for i = 0 to lastidx - 1:
if array[i] > array[i+1]:
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
didSwap = true
Прочитайте это, поймите, как он работает, а затем реализуйте его самостоятельно. Если у вас есть проблемы с этим, я включил рабочую версию ниже:
void Sort (phone phonebook[]) {
phone temp;
int i; int didSwap;
didSwap = 1;
while (didSwap) {
didSwap = 0;
for (i = 0; i < counter - 1; i++) {
if (strcmp(phonebook[i].Surname, phonebook[i+1].Surname) > 0) {
temp=phonebook[i];
phonebook[i]=phonebook[i+1];
phonebook[i+1]=temp;
didSwap = 1;
}
}
}
}
Ответ 3
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;
}
}
}
Три проблемы с вашим кодом. Во-первых, это логика вашего алгоритма. Bubble sort работает, фиксируя порядок двух смежных элементов. В вашем коде после первой итерации вашего внутреннего цикла for он не будет сравнивать два соседних элемента.
Вторая проблема, опять же в алгоритме сортировки, ваши счетчики i и j равны 19, даже если количество записей меньше. Это может испортить сортировку, поскольку они будут читать недопустимую (неинициализированную) запись. вы должны проверить верхнюю границу для счетчика.
Следующий элемент находится в деле удаления
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;
}
}
}
Приведенный выше код не будет корректно проверять, будет ли первая и фамилия, так как вы проверяете их отдельно. Вам нужен только один цикл for с if( strcmp(deleteSurname, phonebook[x].Surname) == 0 && strcmp(deleteName, phonebook[x].Name) == 0 )
