Сортировка слов по алфавиту - C (СИ)
Формулировка задачи:
Есть какая-то строка, с словами, длина которых составляет от 6 до 16 символов. Слово заканчивается пробелом, запятой или точкой. Необходимо отсортировать их по алфавиту. Идей никаких нет(
Решение задачи: «Сортировка слов по алфавиту»
textual
Листинг программы
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef struct _node {
const char* ptr;
struct _node* next;
} node;
void slist_words(node** lst, char* s);
void slist_sort(node** lst);
void slist_clear(node* lst);
int main(void){
node* lst, *p;
char s[] = "XYZ Pascal, Lisp, Algol, C, D, WORD, APL, Prolog, ADA, PHP, Java, Snobol, Actor.";
lst = NULL;
slist_words(&lst, s);
slist_sort(&lst);
for(p = lst; p != NULL; p = p->next)
puts(p->ptr);
slist_clear(lst);
return 0;
}
//заполнение списка словами
void slist_words(node** lst, char* s){
char* i;
node* p, *tail = NULL;
const char delim[] = " \t\n.,?!";
*lst = NULL;
for(i = strtok(s, delim); i != NULL; i = strtok(NULL, delim)){
p = (node*)malloc(sizeof(node));
if(p == NULL)
break;
p->ptr = i;
p->next = NULL;
if(tail == NULL)
*lst = tail = p;
else {
tail->next = p;
tail = p;
}
}
}
//сортировка списка по алфавиту
void slist_sort(node** lst){
node* p, *i, *l, *n, *t, *q, *lp = *lst;
if((lp == NULL) || (lp->next == NULL))
return;
i = l = *lst;
p = n = t = NULL;
for(q = *lst; (q != NULL) && (q->next != NULL); q = q->next->next) {
l = i;
i = i->next;
}
l->next = NULL;
slist_sort(&lp);
slist_sort(&i);
while((lp != NULL) || (i != NULL)){
if(i == NULL) {
n = lp;
lp = lp->next;
} else if(lp == NULL) {
n = i;
i = i->next;
} else if(strcmp(lp->ptr, i->ptr) < 0) {
n = lp;
lp = lp->next;
} else {
n = i;
i = i->next;
}
if(p == NULL)
p = n;
else
t->next = n;
t = n;
}
*lst = p;
}
//удаление всего списка
void slist_clear(node* lst){
node* t;
while(lst != NULL){
t = lst;
lst = lst->next;
free(t);
}
}
Объяснение кода листинга программы
- Объявление структуры узла списка.
- Функция slist_words заполняет список словами, разделенными запятыми и пробелами, из входной строки.
- Функция slist_sort сортирует список по алфавиту.
- В функции slist_sort реализуется сортировка слиянием.
- Функция slist_clear освобождает память, выделенную для узлов списка.
- В функции main создается список слов из входной строки.
- Затем список сортируется и выводится на экран.
- После этого список очищается и программа завершается.