Сортировать структуру по именам (вдвойне связанный список)
-
27-12-2019 - |
Вопрос
Я пытаюсь сортировать свою структуру на основе имен (в алфавитном порядке).Например, у меня есть эта структура:
struct person{
char name[MAX];
char num[MAX];
char email[MAX];
struct person *next;
struct person *previous;
};
struct person *next, *first, *end;
.
и в моей главной функции:
int main()
{
struct person p = {{0}}
.
.
.
switch(choice)
{
case 1 :
printf("Name : "); scanf("%s", &p.name);
printf("Num : "); scanf("%s", &p.num);
printf("E-Mail : "); scanf("%s", &p.email);
input(p); //function to input data
break;
case 2 :
sort(p); //function to sort the data
break;
}
}
.
и в моем прототипе функции:
void sort(struct person p)
{
struct person *ptr, *ptr2, *temp;
ptr=first;
ptr2=first;
for (ptr= first; ptr!= NULL; ptr= ptr->next)
{
for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)
{
if (strcmp(ptr->name, ptr2->name) > 0)
{
temp = ptr;
ptr= ptr2;
ptr2= temp;
}
}
}
}
.
Хорошо, поэтому у меня есть функция прототипа, которая сортирует структуру на основе его элемента, которая имеет имя.Я пытался сортировать его, используя тот же принцип, что и Bublyort, но это не поработало для меня.Указатель PTR указывает на первый узел в списке и PTR2 указывает на второй узел.Является ли мой алгоритм неправильно? Я не могу узнать, что не так.Главная проблема с сортировкой.Я надеюсь, что мой вопрос понятен.
Решение
Внутренняя петля
for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)
.
должен быть
for (ptr2= ptr->next; ptr2!= NULL; ptr2= ptr2->next)
.
(обратите внимание на ptr2
vs. ptr
).
Редактировать:
Обмен указатели тоже не будут работать.Вы должны перейти к элементам, которые требуют переменных помощников в петлях.Вещи могут быть сделаны более элегантными (-> иметь дело с главой списка) при работе со ссылками:
static void swap(struct person **a, struct person **b)
{
struct person *tmp;
if ((*a)->next)
(*a)->next->prev = *b;
if ((*b)->next)
(*b)->next->prev = *a;
tmp = (*a)->prev;
(*a)->prev = (*b)->prev;
(*b)->prev = tmp;
tmp = (*a)->next;
(*a)->next = (*b)->next;
(*b)->next = tmp;
tmp = *b;
*b = *a;
*a = tmp;
}
void foo()
{
struct person **a;
struct person *prev_a;
for (a = &first; *a != NULL; a = &(prev_a->next)) {
struct person **b;
struct person *prev_b;
prev_a = (*a)->prev;
for (b = &(*a)->next; *b != NULL; b = &(prev_b->next)) {
prev_b = (*b)->prev;
if (strcmp((*a)->name, (*b)->name) > 0)
swap(a, b);
/* prev_b == NULL can not happen because inner loop is started
in the middle of the list */
prev_b = prev_b->next;
}
if (prev_a)
prev_a = prev_a->next;
else
prev_a = first;
}
}
.
Редактировать:
Реализация ядра Linux, как связанные списки Linux, как связанные списки (наличие манекенной головки, которая связана на переднем и хвосте списка), сделайте все более простыми в методе подкачки, потому что проверки NULL указателя могут быть опущены.Например.список будет выглядеть как
,------------> HEAD ------------\
| +------------ <-----------\ \
| | | |
| `-> elem_n --> ... --> elem_0 -` |
`--- <-- ... <-- <---'
. Другие советы
Не подсказывать указатели, значения свопа.Кроме того, вам нужно инициализировать пустые указатели на NULL
, они не по умолчанию.