упорядоченный линейный список

[Saske_Master]

Помогите, пожалуйста, написать программу на "С", расщепляющую упорядоченный линейный список слов на два упорядоченных списка: список со словами, встречающимися ровно 1 раз, и список с оставшимися словами. В итоге, вывести оба списка.

Дополнительные условия:
Программа должна состоять из нескольких функций.
Во всех заданиях располагать узлы списка/дерева в динамической памяти.
Предусмотреть функции вывода на экран списка/дерева.
Разрешены к использованию следующие функции: printf, scanf, getchar (считывание символа с клавиатуры), gets, fgets, malloc, free, fopen, fclose

Заранее очень благодарен за помощь!

[Пётр Седов]

#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* структура переменного размера */
struct word_t {
  struct word_t* next;
  char elems[1]; /* на самом деле длина будет не 1; это поле должно быть последним в структуре */
};

struct word_list_t {
  struct word_t* first;
  struct word_t* last;
};

struct word_t* create_word(const char* text) {
  struct word_t* w;
  int len;

  len = strlen(text);
  /* выделяем блок памяти в heap-е */
  w = (struct word_t*)malloc(offsetof(struct word_t, elems) + len + 1); /* sizeof(char) = 1, по определению языка C */
  if (w == NULL) { /* если не получилось выделить блок памяти */
    /* упрощённая обработка ошибки */
    printf("Cannot allocate memory block.\n");
    exit(1);
  }
  w->next = NULL;
  memcpy(w->elems, text, len + 1); /* копируем вместе с завершающим нулевым элементом ('\0') */
  return w;
}

/* добавляет слово в конец списка */
void add(struct word_list_t* list, struct word_t* word) {
  word->next = NULL;
  if (list->last != NULL) {
    list->last->next = word;
  } else {
    list->first = word;
  }
  list->last = word;
}

/* вставляет слово в сортированный список */
void insert(struct word_list_t* list, struct word_t* word) {
  struct word_t* prev;
  struct word_t* next;

  /* ищем подходящее место для вставки */
  prev = NULL;
  next = list->first;
  while (next != NULL) {
    if (strcmp(word->elems, next->elems) < 0) {break;}
    prev = next;
    next = next->next;
  }

  /* вставляем слово */
  word->next = next;
  if (prev != NULL) {
    prev->next = word;
  } else {
    list->first = word;
  }
  if (next == NULL) {
    list->last = word;
  }
}

void clear(struct word_list_t* list) {
  struct word_t* w;
  struct word_t* w2;

  for (w = list->first; w != NULL; w = w2) {
    w2 = w->next;
    free(w); /* освобождаем блок памяти */
  }
  list->first = list->last = NULL;
}

/* words должен быть сортированным списком */
void split(struct word_list_t* words, struct word_list_t* unique_words, struct word_list_t* repeating_words) {
  struct word_t* w;
  struct word_t* w2;

  assert(unique_words->first == NULL); /* список должен быть пустой */
  assert(repeating_words->first == NULL); /* список должен быть пустой */
  w = words->first;
  while (w != NULL) {
    w2 = w->next;
    if ((w2 != NULL) && (strcmp(w2->elems, w->elems) == 0)) { /* если два одинаковых слова подряд */
      add(repeating_words, w);
      do {
        w = w2;
        w2 = w2->next;
        add(repeating_words, w);
      } while ((w2 != NULL) && (strcmp(w2->elems, w->elems) == 0));
    } else {
      add(unique_words, w);
    }
    w = w2;
  }
  words->first = words->last = NULL;
}

void print(const struct word_list_t* list) {
  const struct word_t* w;

  for (w = list->first; w != NULL; w = w->next) {
    printf("%s ", w->elems);
  }
  printf("\n");
}

int main() {
  struct word_list_t words = {NULL, NULL};
  struct word_list_t unique_words = {NULL, NULL};
  struct word_list_t repeating_words = {NULL, NULL};

  insert(&words, create_word("print"));
  insert(&words, create_word("and"));
  insert(&words, create_word("zoom"));
  insert(&words, create_word("and"));
  insert(&words, create_word("clone"));
  insert(&words, create_word("and"));
  insert(&words, create_word("block"));
  insert(&words, create_word("and"));
  insert(&words, create_word("abort"));
  split(&words, &unique_words, &repeating_words);
  printf("Unique words: ");
  print(&unique_words);
  printf("Repeating words: ");
  print(&repeating_words);
  assert(words.first == NULL); /* список должен быть пустой */
  clear(&unique_words);
  clear(&repeating_words);
  return 0;
}

Вывод на консоль:

Unique words: abort block clone print zoom
Repeating words: and and and and

Сообщение от Saske_Master

Разрешены к использованию следующие функции: printf, scanf, getchar (считывание символа с клавиатуры), gets, fgets, malloc, free, fopen, fclose

Я использовал стандартные функции exit, strlen, memcpy, strcmp и стандартные макросы assert, offsetof. Они не входят в список разрешённых, но попробуйте так, а если не получится, можно будет что-нибудь переделать.