UnionSet по рангу со строками в C

Question

Итак, я пытался составить объединенную по рангу программу городов, которые можно подключить
И я только что понял, что если я хочу объединить родителей, мне нужно объединить оба города в одного родителя, так что если у меня есть

parent[0][20] = "City"
parent[1][20] = "Cities" 

Мне нужно сделать это

parent[1] = "City", "Cities";

И при проверке isSameSet Я также должен посмотреть на parent[i] содержит оба

parent[i] = "City", "Cities";

Это возможно с 2d массивом? Или я мог бы использовать 3d-массив, чтобы сделать строки:

parent[i][j][k]
parent[0][0][20] = "City"
parent[0][1][20] = "Cities"

Могу ли я вообще это сделать? Я понятия не имею, или я должен просто использовать struct/linked list вместо этого? Кто-нибудь может дать мне некоторую подсказку или совет, о том, как сделать объединение наборов со строками?
* Редактировать: я тоже не думаю, что мой findSet (); функция будет работать, если я использую 2d массивы

#include<stdio.h>
#include<stdio.h>
#include<conio.h>
#include<windows.h>


void initialize(char parent[][20], int *ranks, char x[], int i){

    strcpy(parent[i], x);
    ranks[i] = 0;

}

int findSet(char parent[][20], char x[], int n){

    int i;

    for(i = 0; i < n; i++){
        if(strcmp(parent[i], x) == 0){
            return i;
        } else{
            printf("City not found!\n");
        }
    }
}

int isSameSet(char parent[][20], char x[], char y[], int n){

    if(strcmp(parent[findSet(parent, x, n)], parent[findSet(parent, y, n)]) == 0) return 1;
        else return 0;

}

void unionSet(char parent[][20], int *ranks, char x[], char y[], int n){

    int i = findSet(parent, x, n);
    int j = findSet(parent, y, n);

    if(i != j){
        if(ranks[i] > ranks[j]){
            parent[j] = 1;
        } else {
            if(ranks[i] == ranks[j]){
                ranks[j]++;
            }
            parent[i] = j;
        }
    }
}

int main(){

    int n, i = 0, choice;
    char x[20], y[20];

    printf("Enter the number of cities : "); scanf("%d", &n);

    char parent[n][20];
    int ranks[n];

    while(1){
        system("cls");
        printf("================================================\n");
        printf("            City Connection Program\n");
        printf("================================================\n");
        printf("1. Enter City\n");
        printf("2. Connect city\n");
        printf("3. Check cities connected\n");
        printf("4. Exit\n");
        printf("Pilihan: ");scanf("%d", &choice); fflush(stdin);

        if(choice == 1){
            if(i < n){
                printf("Enter city name: "); scanf("%[^\n]", x);fflush(stdin);
                initialize(parent, ranks, x, i);
                i++;
                printf("City %s is entered\n", parent[i]);
            } else{
                printf("The city is at maximum!\n");
            }
        } else if( choice == 2){
            printf("Enter city 1: ");scanf("%[^\n]", x);
            printf("Enter city 2: ");scanf("%[^\n]", y);
            if(isSameSet(parent, x, y, n)){
                printf("Both cities are already Connected\n");
            } else{
                unionSet(parent, ranks, x, y, n);
                printf("Both cities are connected!\n");
            }

        }
        /*else if(choice == 3){
            printf("Enter city 1: ");scanf("%[^\n]", x);
            printf("Enter city 2: ");scanf("%[^\n]", y);
            if(isSameSet(parent, x, y)) printf("City %s and city %s connected\n", x, y);
                else printf("City %s and city %s is not connected\n", x, y");
        } else if(choice == 4){
            return 1;
        }

        getch();

    }

    return 0;

}

Answer 1

Итак, у вас есть список n городов, идентифицированных по их названиям:

char city[n][20] = {"Amsterdam", "Beijing", "Cairo", ..., "Zurich"};

Обратите внимание, что каждый город также определяется по позиции в массиве: Амстердам равен 0, Брюссель равен 1, и т. д.

Эти города должны быть сгруппированы в непересекающиеся множества. Наборы описаны как деревья. У каждого города есть родитель. Город, родителем которого является сам, является городом root для этого набора. Он идентифицирует набор.

Так что вы должны как-то хранить родителя. Ваша идея состоит в том, чтобы сохранить имя родителя, а затем сравнить имена при обнаружении узла root:

char parent[n][20];        // initialize to same strings as city

Вы можете сделать это, но было бы проще, если бы вы просто сохранили парант index:

int parent[n];

Когда вы соединяете два города, вы должны сначала определить, какие это города. Вы должны определить n, который вы передаете своим функциям. (Вы передаете n, который в main - это число городов и, следовательно, димеизон массива. В C, n - один за пределами допустимого диапазона индексов массива.)

Наконец, вы получаете свои ранги:

int rank[n];

Теперь вам нужны следующие функции:

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

int findCity(char city[][20], int n, const char *name)
{
    int i;

    for (i = 0; i < n; i++) {
        if (strcmp(city[i], name) == 0) {
            return i;
        }
    }

    return -1;
}

Функция, чтобы найти набор города, то есть "root город" для набора. Эта функция должна знать только о родителе каждого города. Если массив настроен правильно, т.е. если k и все возможные parent[k] являются действительными индексами, и если родительский элемент thr root является самим root, эта функция не может завершиться с ошибкой. Тогда этой функции не нужно знать о количестве городов:

int findSet(int parent[], int k)
{
    while (parent[k] != k) {
        k = parent[k];
    }

    return k;
}

Функция, чтобы определить, являются ли два города одинаковыми. Это действительно просто «удобная функция» для findSet:

int isSameSet(int parent[], int a, int b)
{
    return (findSet(parent, a) == findSet(parent, b));
}

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

void unionSet(int parent[], int rank[], int a, int b)
{
    int s = findSet(parent, a);
    int t = findSet(parent, b);

    if (s != t) {
        if (rank[s] > rank[t]) {
            parent[t] = s;
        } else {
            if (rank[s] == rank[t]) rank[t]++;            
            parent[s] = t;
        }
    }
}

См. Пример в действии здесь .

Подводя итог: используйте названия городов только для пользователя интерфейс, когда вы берете ввод и когда вы печатаете вывод. Сделайте лог c наборов по целочисленным индексам.

Дополнительные примечания:

• Лучшим представлением может быть создание структуры города, которая содержит данные для каждого города, включая Родитель и звание. Вместо целочисленных индексов вы можете использовать указатели на эти структуры.
• В настоящее время большая часть времени тратится впустую на поиск городов в массиве. Это нормально для небольшого примера, но в реальной программе вам придется использовать хотя бы двоичный поиск для поиска имен.