Как итеративно взять определенные элементы структуры и сохранить их в 2D-массив в C?

Question

Итак, у меня есть двумерный массив строк, например:

char str[12][100] = {
    "a = 2.b, 1.d",
    "b = 2.a, 1.e, 2.c",
    "c = 2.b, 1.f",
    "d = 1.a, 1.g",
    "e = 1.h, 1.b",
    "f = 1.i, 1.c",
    "g = 1.j, 1.d",
    "h = 1.k, 1.e",
    "i = 1.l, 1.f",
    "j = 1.g, 2.k",
    "k = 2.j, 1.h, 2.l",
    "l = 2.k, 1.i"
};

Эти строки представляют макет карты, где точка «a» соединена с точкой «b» и «d» и естьсоответствующее расстояние (или вес) между точками, которые связаны с точкой "а".Вот как выглядит макет при преобразовании из всех этих строк:

    a--(2)--b--(2)--c
    |       |       |
   (1)     (1)     (1)
    |       |       |
    d       e       f
    |       |       |
   (1)     (1)     (1)
    |       |       |
    g       h       i
    |       |       |
   (1)     (1)     (1)
    |       |       |
    j--(2)--k--(2)--l

И у меня есть такая структура:

struct stopPoints {
    int  weights[10];
    char connectingPoints[10];
};

Я успешно взял каждую строку, ипоместите каждую букву и цифру в свою структуру.Я сделал это, создав массив структур наподобие этого: struct stopPoints store[26];, а затем я продолжал заполнять каждую структуру итеративно, добавляя соответствующий элемент каждой строки.Например, для моей первой строки "a = 2.b, 1.d" я положил буквы "a", "b" и "d" в store[0].connectingPoints[0], store[0].connectingPoints[1], and store[0].connectingPoints[2], соответственно.Так вот так:

store[0].connectingPoints[0] = 'a';
store[0].connectingPoints[1] = 'b';
store[0].connectingPoints[2] = 'd';

Я также вставил два числа в элемент "весов" структуры, например так:

store[0].weights[0] = 2;
store[0].weights[1] = 1;

Я проверил это для всех12 строк и все на месте.

Теперь я хочу создать матрицу смежности из этих строк, которые у меня есть.Вот как должна выглядеть матрица смежности:

0 2 0 1 0 0 0 0 0 0 0 0                                        
2 0 2 0 1 0 0 0 0 0 0 0                                        
0 2 0 0 0 1 0 0 0 0 0 0                                        
1 0 0 0 0 0 1 0 0 0 0 0                                        
0 1 0 0 0 0 0 1 0 0 0 0                                        
0 0 1 0 0 0 0 0 1 0 0 0                                        
0 0 0 1 0 0 0 0 0 1 0 0                                        
0 0 0 0 1 0 0 0 0 0 1 0                                        
0 0 0 0 0 1 0 0 0 0 0 1                                        
0 0 0 0 0 0 1 0 0 0 2 0                                        
0 0 0 0 0 0 0 1 0 2 0 2                                        
0 0 0 0 0 0 0 0 1 0 2 0

Чтобы объяснить немного больше, первая строка [0] (представляет точку "a") содержит 2 в индексе [0] [1] (представляет расстояние до точки "b") и содержит 1 в индексе [0] [3] (представляет расстояние до точки "d").

Таким образом, вторая строка [1] содержит 2в индексе [1] [0] и [1] [2], поскольку точка b соединена с точкой a и точкой c, а индекс [1] [5] содержит 1, поскольку точка b также связана с точкой e.Как видите, каждая строка и столбец фактически представляют буквы al в порядке (0 = a, 1 = b, 2 = c и т. Д.).

Я уже инициализировал и заполнил массив 12x12 всеми 0.Кажется, я просто не могу правильно заполнить свои значения веса соответствующим индексом.Вот один из моих многих неудачных подходов:

int row2, col2, ugh=1;        
for (row2 = 0; row2 < 12; row2++){
    for (col2 = 0; col2 < 12; col2++){
        while(store[row2].connectingPoints[ugh] != NULL){
            adjmatrix[row2][col2] = store[row2].weights[col2];
            ugh++;
        }
}

}

Вот как вы бы жестко закодировали первые две строки в матрицу смежности:

        //a=2b, 1d;
        adjmatrix[0][0] = 0; //point a
        adjmatrix[0][1] = store[0].weights[0];
        adjmatrix[0][3] = store[0].weights[1];

        //b=2a, 2c, 1e;
        adjmatrix[1][0] = store[1].weights[0];
        adjmatrix[1][1] = 0; //point b
        adjmatrix[1][2] = store[1].weights[1];
        adjmatrix[1][4] = store[1].weights[2];

Iпросто не знаю, как я могу сделать это итеративно.Любая помощь будет высоко ценится.

Answer 1

Преобразование символов в целые числа

Вы можете найти копию таблицы ASCII здесь .Вы должны добавить эту страницу в закладки, потому что, если вы тратите много времени на программирование, вы будете ссылаться на нее изрядно (два раза в год, скажем, на 30+ лет).

Важная вещь, которую нужно знать об ASCIIКод (который является подмножеством Latin1, Unicode и т. д.) состоит в том, что цифры, а также буквы верхнего и нижнего регистра находятся в трех смежных группах в порядке возрастания.

То естькод для «0» на единицу меньше, чем код для «1» и т. д., до «9».То же самое верно для 'A' .. 'Z' и 'a' .. 'z'.

Таким образом, вы можете преобразовать значения вашего символа в значение индекса простым вычитанием:

int ch0 = 'a' - 'a';  // == 0
int ch1 = 'b' - 'a';  // == 1
int ch4 = 'e' - 'a';  // == 4

Если у вас есть символьное значение (в нижнем регистре, ASCII), и вычтите из него «a», вы получите целочисленное значение в диапазоне 0..25.

Это означает, что вы можете использоватьэта формула для вычисления обоих значений индекса для вашей матрицы смежности:

#define MAX_CONN 10
#define NUM_STORES 12
#define STORE_INDEX(ch) ((ch) - 'a')
#define FIRST_STORE 'a'
#define END_STORES (FIRST_STORE + NUM_STORES)
#define MAX_WEIGHT 100

// NOTE: I'm ignoring return type, and adjmatrix's 
// lifetime, in favor of just putting this code all 
// in one place. You'll have to figure out the rest.

void build_adj() {

    struct stopPoints store[NUM_STORES]; // Values?
    int adjmatrix[NUM_STORES][NUM_STORES] = {0};

    for (st = FIRST_STORE; st < END_STORES; ++st) {
        int row = STORE_INDEX(st);

        // Set default weights: MAX_WEIGHT or 0 (for self)

        for (i = 0; i < NUM_STORES; ++i) {
                adjmatrix[row][i] = MAX_WEIGHT;
        }

        adjmatrix[row][row] = 0;

        // Install parsed weights for this row

        for (iconn = 0; iconn < MAX_CONN; ++iconn) {

            // NB: setting connectingPoints[x] to '\0' invalidates connection.
            char st2 = store[row].connectingPoints[iconn];

            if (st2 != '\0') {
                adjmatrix[row][STORE_INDEX(st2)] = store[row].weights[iconn];

                // FIXME: Maybe set reflexive weight? a->b, b->a?
           }                                        
        }
    }
}

Инверсия структуры / массива

Прямо сейчас у вас есть массив структуры, который содержит парумассивы.Я бы посоветовал вам инвертировать это и создать массив структур, содержащий один массив, который содержит структуру с двумя элементами данных.

Примерно так:

typedef struct Connection {
    char  conn_target; 
    int   conn_weight;
} Connection;

typedef struct StopPoints {
    Connection sp_connections[MAX_CONN];
} StopPoints;

И тогда у вас есть:

StopPoints store[MAX_STORES];

// most code stays the same

    st2 = store[row].sp_connections[iconn].conn_target;

// ...

    adjmatrix[row][STORE_INDEX(st2)] = store[row].sp_connections[iconn].conn_weight;

Преимущество этого концептуально: цель и вес соединения объединены вта же структура.Об этом легче думать, и легче переходить на использование указателей ;-).

С другой стороны, это займет больше памяти из-за заполнения структуры.Но я не думаю, что тебя это сейчас волнует.

Answer 2

Преобразование из char[][] в adjmatrix может быть выполнено с помощью парсинга строк, как показано в приведенном ниже коде.

int adjmatrix[26][26] = {0}; //assuming 26 possible points (from question "struct stopPoints store[26]")

int i,j,k = 0;
int n = 12;

for (i = 0; i < n; ++i) {
    int l = strlen(str[i]);
    for (j = 0; j < l; ++j) {
        if (str[i][j] == '.') {
            adjmatrix[str[i][0] - 'a'][str[i][j+1] - 'a'] = getWeight(str[i], j);
            // (char) - 'a', gives an integer value for the small case alphabets (a->1, b->2, c->3 ...)
        }
    }
}

getWeight()

int getWeight(char s[], int j) {
    // returns the integer on left of '.' from the string
    int w = 0,i = 0;
    int m = 1;
    for (i = j-1; s[i] >= '0' && s[i] <= '9'; --i) {
        w += (s[i] - '0')*m;
        m *= 10;
    }
    return w;
}

Если выдействительно нужно использовать структуру, тогда вы, вероятно, можете упростить ее, сделав число weights равным количеству connectingPoints для каждого магазина.то есть, если вы добавляете store[0].connectingPoints[0] = 'a';, пусть веса будут

store[0].weights[0] = 0;  // weight of point a to point a
store[0].weights[1] = 2;  // weight of point a to point b
store[0].weights[2] = 1;  // weight of point a to point d

Другой пример: "c = 2.b, 1.f", (Не уверен, каков порядок connectingPoints в вашем коде, но обратите внимание на сопоставление один к одномуочков и весов, основанных на индексе)

store[2].connectingPoints[0] = 'b';
store[2].connectingPoints[1] = 'c';
store[2].connectingPoints[2] = 'f';

store[2].weights[0] = 2;
store[2].weights[1] = 0;
store[2].weights[2] = 1;

Если вы знаете, что самокупов нет, вы можете избежать их сохранения в connectedPoints и дальнейшего добавления соответствующей записи в weights. * 1023.*

В этом случае вы можете построить adjmatrix, используя цикл вроде этого

struct stopPoints store[26];

for (i = 0; i < n; ++i) {
    int l = strlen(store[i].connectingPoints);
    for (j = 0; j < l; ++j) {
        adjmatrix[str[i][0] - 'a'][store[i].connectingPoints[j] - 'a'] = store[i].weights[j];
    }
}