Сортировка массива из структуры typedef в C - PullRequest
Новая
       266

Сортировка массива из структуры typedef в C

11 голосов
/ 27 октября 2011

Проблема : Попытка отсортировать массив из созданной мной структуры 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'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;
            }
        }
    }
}

Ответы [ 3 ]

6 голосов
/ 27 октября 2011

Вы можете использовать уже реализованную функцию сортировки. 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);
}

. Обычно эта функция Быстрая сортировка , но это зависит от реализации библиотеки Cпринять решение.

Обновление:

Пустой листинг состоит в том, что сортировка происходит в обратном порядке и всегда сортирует все 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 выше.

1 голос
/ 27 октября 2011

Перво-наперво, у вас возникла проблема переполнения буфера: 

char userChoice;
:
scanf("%s", &userChoice);

Что scanf будет записывать два байта при вводе одного символа (символа плюс нулевой терминатор).Это повредило имя первой записи телефонной книги в моей среде, но, поскольку это неопределенное поведение, оно может сделать что угодно!

Вы можете обойти это, используя: 

char userChoice[] = "something that's not Q";
: 
scanf("%s", userChoice);
:
if (*userChoice == 'A')  // for all of these.

Это не остановит переполнение буфера, если вы введете достаточно текста, но будет, если вы ограничитесь односимвольными командами.Если вам нужна действительно надежная функция пользовательского ввода, см. здесь .

Теперь к вашей конкретной проблеме.Похоже, у вас там что-то вроде пузыря, но ваша логика немного не в порядке.Предполагая, что вы не хотите использовать qsort (что было бы лучшим способом для реального кода), вам просто нужно исправить пару вещей.

Ваш внешний цикл в порядке, как и ваш внутреннийцикл, но внутреннее тело цикла должно сравнивать элементы j и j+1, а не j и i.Это объясняется тем, что он работает путем замены смежных элементов, если они не в порядке.

Кроме того, направленная вперед направленная пузырьковая сортировка поместит самый высокий элемент в конец списка на первом проходе, поэтому вы не можете начать j с i+1 на втором проходе просто потому, что элемент first может быть еще не верным.

Следующий классический псевдо-код - это ваша классическая пузырьковая сортировка: 

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;
            }
        }
    }
}
0 голосов
/ 27 октября 2011 
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 )

...