Вывод натыкается на null хоть его там не должно быть
Вот моя программа, почему то когда запускаю ее, выводит первые 81 записи, хотя их 400 в базе.
#include <iostream>
#include <fstream>
#include <cstdio>
#include <limits>
#define N 4000
using namespace std;
struct tData
{
unsigned char street[18];
short int house;
};
struct List
{
char name[32];
union
{
tData home;
unsigned char Digit[sizeof(home)];
};
short int flat;
char data[10];
List* next;
};
struct Queue
{
List* head;
List* tail;
};
void DigitalSort(List*& S) {
const int L = 4;
int KDI[L] = { 0, 1, 2, 18 };
int j, i, k, d;
List* p;
Queue* Q = new Queue[256];
for (j = L - 1; j >= 0; j--) {
for (i = 0; i < 256; i++)
Q[i].tail = (List*)&Q[i].head;
p = S;
k = KDI[j];
while (p) {
d = p->Digit[k];
Q[d].tail->next = p;
Q[d].tail = p;
p = p->next;
}
p = (List*)&S;
for (i = 0; i < 256; i++) {
if (Q[i].tail != (List*)&Q[i].head) {
p->next = Q[i].head;
p = Q[i].tail;
}
}
p->next = NULL;
}
}
void Run(List*& p, int step) {
int count = 0, i;
for (i = 0; i < 80; i++) cout << "#";
cout << "# #";
while (p && count < 20) {
printf("# %4d) %32s ", step * 20 + count + 1, p->name);
printf("%-18s ", p->home.street);
printf("%-3d ", p->home.house);
printf("%-4d ", p->flat);
printf("%-8s #", p->data);
p = p->next;
count++;
}
cout << "# #";
for (i = 0; i < 80; i++) cout << "#";
cout << "Do you want to continue? 1/0 : ";
}
int main() {
system("mode con cols=80 lines=25");
int i, step = 0, choose;
fstream file("testBase4.dat", ios::binary | ios::in);
List* head = new List;
head = NULL;
if (!file.is_open()) {
cout << "Could not open the file" << endl;
return 1;
}
List* p, * temp;
for (i = 0; i < N; i++) {
p = new List;
file.read((char*)&p->name, 32);
file.read((char*)&p->home.street, 18);
file.read((char*)&p->home.house, sizeof(short int));
file.read((char*)&p->flat, sizeof(short int));
file.read((char*)&p->data, 10);
p->next = head;
head = p;
}
file.close();
choose = 2;
DigitalSort(head);
while (choose != 0 && step < 200) {
temp = head;
Run(head, step);
cin >> choose;
if (cin.fail()) {
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
choose = 2;
head = temp;
continue;
}
if (choose != 1 && choose != 0) {
head = temp;
continue;
}
if (choose == 1) step++;
}
system("CLS");
return 0;
}
Ответы (1 шт):
Ну тут трудно сказать, где должен быть null, а где нет. Добавьте файл с данными в задачу. А лучше короткий тестовый пример без файла, с заранее определенными входными данными.
Правильно написал @AlexGlebe - вы напутали с приведением типов. Когда вы передаете в качестве параметра функции ссылку на указатель DigitalSort(List*& S), то в теле функции S - это уже указатель, имеет тип List*. &S - это адрес указателя, т.е. будет иметь тип List**. А далее вы указатель на указатель насильно (и неправильно) приводите к типу List*. Должно быть просто p = S;.
Если не смотреть на эту глобальную ошибку, то и других ошибок и недочетов в коде немало.
Не стоит использовать макросы. Используйте константы.
// вместо
#define N 4000
// используйте
const int N = 4000;
На первых строчках программы - утечка памяти. Выделили память под объект и тут же обнулили указатель!
int main()
{
List* head = new List;
head = NULL;
Примерно то же самое в функции DigitalSort() - память выделили и нигде не удалили. При том, что этот массив используется только в функции сортировки локально. Чтобы не сильно думать про владение объектами, используйте умные указатели из стандартной библиотеки - unique_ptr<> или shared_ptr<>. А конкретно в данном случае, т.к. вы знаете размер необходимого массива, не надо его выделять в куче, сделайте локальным, заодно и работать быстрее будет. А для того, чтобы проще было отлавливать ошибки в отладчике, я бы обнулял указатели в массиве.
void DigitalSort(List*& S)
{ // вместо этого
Queue* Q = new Queue[256];
// проще вот так
Queue Q[256];
// и обнуление
for (i = 0; i < 256; i++)
Q[i].tail = Q[i].head = nullptr;
}
А т.к. это временный массив для сортировки, вам не нужен массив элементов типа struct Queue, т.к. Q[i]->head нигде не используется. Тут достаточно просто List* Q[256];
В функции Run(List*& p, int step) вы просто выводите на экран 20 записей. Но зачем-то передаете ссылку на указатель и в результате меняете исходный указатель, когда движетесь по списку. По сути у вас константная функция, не изменяющая внутри себя данные. Передайте в неё указатель по копии Run(List* p, int step).
И с выводом намудрено - проще сделать функцию вывода 1 узла списка, а потом в цикле вывести 20. Чем внутри функции изменять начальный указатель, а потом снаружи функции возвращать ему первоначальное значение.
for(int i = 0; i < 20 && p!=NULL; i++)
{
Run(p, step); // вывод 1 узла
p = p->next;
}
То же самое внутри функции вы выводите приглашение на ввод cout << "Do you want to continue? 1/0 : ";, а сам ввод осуществляется за пределами функции. Отследить такое поведение - очень сложно.
И с последним циклом для вывода на экран - много заморочек - достаточно просто отследить ввод 0 и закончить цикл. Всё, что не 0 - продолжаем цикл. Или отслеживать 1 - всё остальное - прекратить цикл. Да и работает он криво - если было введено что-то кроме 0 и 1 то будет заново выведено на экран 20 первых записей.
Опять-таки вы не отслеживаете количество введенных записей. В вопросе вы написали что у вас их 400, а в коде используете константу 4000. И при вводе данных из файла в том числе - у вас цикл до 4000 а в файле я так понял всего 400 for (i = 0; i < N; i++) {. И не пишите циклы до магического числа - всегда надо использовать количество, чтобы избежать ошибки.
while (step * 20 < NumListNode)
{
temp = head;
Run(head, step);
cout << "Do you want to continue? 1/0 : ";
cin >> choose;
if (choose == 1)
step++;
else
break;
}
Ну и сама сортировка вызывает множество вопросов. Начиная от выбора структуры данных и заканчивая методом сортировки.
Вообще непонятно зачем вот эта конструкция
struct tData
{
unsigned char street[18];
short int house;
};
struct List
{
union
{
tData home;
unsigned char Digit[sizeof(home)];
};
}
Хотите сравнивать по номеру дома - ну и сравнивайте по номеру дома. Сейчас вы пытаетесь сравнивать по младшему байту от short int house (для x86 процессоров с little-endian), т.к. short int обычно 2 байта. А если номер дома больше 255? - они все будут сортироваться под номером 255. Если вам точно нужно не более 1 байта под хранение номера дома - используйте unsigned char, а ещё лучше uint8_t.
А следующие итерации пытаются сравнивать по 3, затем по 2, затем по 1-му символу в названии строки. Что-то очень странная сортировка.
Далее, на первом шаге, элементы массива Q - какой-то случайный мусор. И разыменовывать его - это неопределенное поведение.
void DigitalSort(List*& S)
{
Queue* Q = new Queue[256];
for (j = L - 1; j >= 0; j--)
{
...
p = S;
while (p)
{
d = p->Digit[k];
// вот здесь Q[d].tail не указывает ни на какой объект List
// в нем - какой-то мусор, допустим 0
Q[d].tail->next = p; // получается nullptr->next = p
Q[d].tail = p;
p = p->next;
}
В первом цикле вы ваш список разбиваете на 256 отдельных списков, указатель на первый элемент каждого списка хранится в массиве Queue Q[256]. А дальше я так понял вы пытаетесь их собрать обратно в один список. Только делаете это неправильно. И тут начинаются потери элементов и соответственно утечки памяти.
Сначала вы временному указателю присваиваете значение указателя на элемент, который раньше был началом списка. Раньше, S указывал на первый элемент списка, назовем его условно unit1. S = unit1. И допустим, что у этого элемента номер дома - 200. После первого цикла элемент unit1 будет висеть в 201 цепочке, привязанной к элементу массива Q[200]. А вы опять делаете его первым p=S=unit1. А затем вы этот элемент теряете, т.к. делаете p->next = Q[i].head; p = Q[i].tail; А в Q[i].head напомню, находится мусор.
Далее, Вам нужно собрать в список все цепочки, которые висят на элементах массива Q. А вы собираете только первые элементы этих цепочек.
p = S; // временное начало списка - на 200 элемент.
for (i = 0; i < 256; i++) // проходите по массиву с цепочками
if (Q[i].tail != Q[i].head) // если цепочка не пустая
{
p->next = Q[i].head; // теряете элемент который был началом нового списка
p = Q[i].tail; // началом нового списка становится первый элемент цепочки, которая была привязана к Q[i]
} // и переходите на следующую цепочку, вместо того, чтобы пройти по цепочке до последнего элемента.
p->next = NULL;
}
}
Более того, как написал @AlexGlebe - вы не запомнили начало списка, указатель p начал двигаться дальше по списку.
А на следующей итерации всё повторяется. Сначала вы заполняете массив Q[i] мусором.
for (i = 0; i < 256; i++)
Q[i].tail = Q[i].head;
И так по-новой 4 раза. То, что у вас в итоговом списке осталось хоть сколько-то элементов - чистая удача!