можно ли делать массивы в массиве структур так
Решаю задачу:
Дан массив чисел A длины N , а также K массивов чисел M1,. . . ,MK длин m1,. . . ,mK соответ- ственно. Требуется найти наибольший по длине массив среди M1,. . . ,MK , который может быть получен из массива A при помощи удаления каких-либо элементов массива A. Если таких мас- сивов несколько, выведите первый из них в лексикографическом порядке. Если такого массива нет, выведите сообщение об ошибке.
Написал код, который вроде даже запускается и определяет есть ли нужный массив, но вот если есть, то выводит мусорные рандомные значения. Меня смущает, как я делаю массив из структуры arrays, а потом, когда уже выделил память для него, я делаю массивы в каждом из элементов массива структуры. Буду благодарен, если укажите на ошибку!
#include <stdio.h>
#include <stdlib.h>
struct arrays{
int size;
int* data;
};
int Process(int* dataA, int* dataMi, int sizeA, int sizeMi);
int ReadArray(FILE* file, int* data, int size);
int Search(int* result, int* dataMi, int maxlen, int sizeMi);
int ReadArray(FILE* file, int* data, int size){
for(int i = 0; i < size; i++){
if(fscanf(file, "%d", data + i) != 1){
return -1;
}
}
return 0;
}
// Определние, является ли Mi подпоследовательностью A
int Process(int* dataA, int* dataMi, int sizeA, int sizeMi){
int indicator = 0;
for(int i = 0; i < sizeA; i++){
if(indicator < sizeMi){
if(dataA[i] == dataMi[indicator]){
indicator++;
}
}
else{
break;
}
}
if(indicator == sizeMi){
return sizeMi;
}
else{
return -1;
}
}
// Для лексикографического порядка
int Search(int* result, int* dataMi, int maxlen, int sizeMi){
if(sizeMi == maxlen){
for(int i = 0; i < sizeMi; i++){
if(result[i] < dataMi[i]){
return 1;
}
}
}
return 0;
}
int main(void){
FILE* finA;
FILE* finM;
int* dataA;
struct arrays* dataM;
int sizeA;
int sizeM;
int maxlen = 0;
int tmp = 0;
int* result;
if((finA = fopen("inputA.txt", "rt")) == NULL){
printf("Can't open input file!\n");
return -1;
}
if(fscanf(finA, "%d", &sizeA) != 1){
printf("Can't read size!\n");
fclose(finA);
return -1;
}
if(sizeA < 1){
printf("Incorrect size!\n)");
fclose(finA);
return -1;
}
if((dataA = (int*) malloc(sizeA * sizeof(int))) == NULL){
printf("Can't allocate memory!\n");
fclose(finA);
return -1;
}
if(ReadArray(finA, dataA, sizeA) < 0){
printf("Can't read array!\n");
free(dataA);
fclose(finA);
return -1;
}
if((finM = fopen("inputM.txt", "rt")) == NULL){
printf("Can't open input file!\n");
return -1;
}
if(fscanf(finM, "%d", &sizeM) != 1){
printf("Can't read count of files!\n");
fclose(finM);
return -1;
}
if(sizeM < 1){
printf("Incorrect size!\n)");
fclose(finM);
return -1;
}
if((dataM = (struct arrays*) malloc(sizeM * sizeof(struct arrays))) == NULL){
printf("Can't allocate memory!\n");
fclose(finM);
return -1;
}
for(int i = 0; i < sizeM; i++){
if(fscanf(finM, "%d", &dataM[i].size) != 1){
printf("Can't read size!\n");
fclose(finM);
return -1;
}
if(dataM[i].size < 1){
printf("Incorrect size!\n)");
fclose(finM);
return -1;
}
if((dataM[i].data = (int*) malloc(dataM[i].size * sizeof(int))) == NULL){
printf("Can't allocate memory!\n");
fclose(finM);
return -1;
}
if(ReadArray(finM, dataM[i].data, dataM[i].size) < 0){
printf("Can't read array!\n");
free(dataM[i].data);
fclose(finM);
return -1;
}
}
// Определяем максимальную длину подпоследовательности
for(int i=0; i < sizeM; i++){
tmp = Process(dataA, dataM[i].data, sizeA, dataM[i].size);
if(maxlen < tmp){
maxlen = tmp;
}
}
result = (int*) malloc(tmp * sizeof(int));
// Находим самый первый Mi длины maxlen в лексикографическом порядке
for(int i = 0; i < sizeM; i++){
if(Search(result, dataM[i].data, maxlen, dataM[i].size) == 1){
for(int i = 0; i < maxlen; i++){
result[i] = dataM[i].data;
}
}
}
if(result == NULL){
printf("There are no need sequences!\n");
free(dataA);
for(int i = 0; i < sizeM; i++){
free(dataM[i].data);
}
free(dataM);
return -1;
}
for(int i = 0; i < maxlen; i++){
printf("%d\n", result[i]);
}
free(dataA);
for(int i = 0; i < sizeM; i++){
free(dataM[i].data);
}
free(dataM);
return 0;
}
Ответы (1 шт):
Мусор выводился по причине того что данные не инициировались. При выделении памяти под массив там находится мусор — случайные числа. которые были больше имеющихся в реальном массиве.
В этой функции я поправил условие на обратное так как в лексиграфическом значении
1 < 2 т.е. если result = 2 а dataM = 1 или result > dataM, то его нужно переписать result = dataM сделав result = 1 так же нужно учесть что если в результате сравнения первых чисел нет равенства нужно выходить из цикла — при > и при < тоже:
// Для лексикографического порядка
int Search(int* result, int* dataMi, int maxlen, int sizeMi){
if(sizeMi == maxlen){
for(int i = 0; i < sizeMi; i++){
if(result[i] != dataMi[i]){
return result[i] < dataMi[i] ? 0 : 1;
}
}
}
return 0;
}
Этот код я просто сократил:
// Определние, является ли Mi подпоследовательностью A
int Process(int* dataA, int* dataMi, int sizeA, int sizeMi){
int size = 0;
for(int i = 0; i < sizeA && size < sizeMi; i++){
if(dataA[i] == dataMi[size]) size++;
}
return size == sizeMi ? sizeMi : -1;
}
Я добавил в структуру булиев флаг для того чтобы помечать то что совпало
struct arrays{
int size;
int* data;
bool isExist;
};
// Определяем максимальную длину подпоследовательности
for(int i=0; i < sizeM; i++){
tmp = Process(dataA, dataM[i].data, sizeA, dataM[i].size);
if (tmp != -1) dataM[i].isExist = true;
if(maxlen < tmp) maxlen = tmp;
}
Этот код я немного переписал, добавив еще одну переменную А еще я заметил что i переназначалось внутренним циклом, так делать не стоит, поэтому ввел j:
int continueIndex = 0; // чтобы не проходить дважды по части массива
// Находим самый первый Mi длины maxlen
for(int i = 0; i < sizeM; i++){
continueIndex = i + 1;
if(dataM[i].isExist == true && dataM[i].size == maxlen){
for(int j = 0; j < maxlen; j++){
result[j] = dataM[i].data[j];
}
break;
}
}
// Выбираем массив в лексикографическом порядке с startIndex
for(int i = startIndex; i < sizeM; i++){
if(Search(result, dataM[i].data, maxlen, dataM[i].size) == 1){
for(int j = 0; j < maxlen; j++){
result[j] = dataM[i].data[j];
}
}
}