C++: Односвязный список в консольном приложении

На самом деле, тема уже фигурировала много где - раз, два, три, четыре... Просто здесь - почти законченный пример, делающий следующее: описать структуру, сформировать динамический односвязный список структур; реализовать просмотр списка, добавление элементов в начало и конец, удаление (по ключу или номеру записи), сортировку. Организовать меню для выбора операций над списком.

В начале работы программы список пуст, так что надо добавить записи с клавиатуры. Проверено в Visual C++, работает.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <clocale>
#include <windows.h>
using namespace std;
#define MAX 30
static int max_id;

struct student {
 int id;
 unsigned char f[MAX];
 int ekz[4];
 student* next;
};

int show(student* head) {
 int count = 0;
 if (!head) return 0;
 while (1) {
  //вывести данные очередного узла
  printf("\n%d. %s", head->id, head->f);
  for (int i = 0; i < 4; i++)  printf(" %d", head->ekz[i]);
  count++;
  //проверка на конец списка
  if (head->next == NULL) break;
  //переход к следующему узлу
  head = head->next;
 }
 printf("\nAll=%d", count);
 return count;
}

student* search(student* head, char* st) {
 if (head == NULL) return NULL; //список пуст
 student* next = head;
 st = _strlwr((char*)st); //чтобы поиск не зависел от регистра символов
 do {
  char* find = strstr(_strlwr((char*)next->f), st);
  if (find != NULL) return next;
  if (next->next == NULL) break;
  next = next->next;
 } while (1);
 return NULL; //не найдено
}

void copy0(student* to, student* from) {
 //to->id = from->id;
 strcpy((char*)to->f, (char*)from->f);
 for (int i = 0; i < 4; i++) to->ekz[i] = from->ekz[i];
}

student* add1(student* head, student* st) {
 student* current = (student*)malloc(sizeof(student));
 current->id = ++max_id;
 copy0(current, st);
 if (head == NULL) current->next = NULL;
 else {
  current->next = head;
  head = current;
 }
 return current;
}

student* add2(student* head, student* st) {
 student* last = NULL;
 if (head) {
  last = head;
  while (last->next) last = last->next;
 }
 student* current = (student*)malloc(sizeof(student));
 current->id = ++max_id;
 copy0(current, st);
 current->next = NULL;
 if (last) last->next = current;
 return current;
}

int check(student* head, char* s) {
 while (head) {
  if (_stricmp((char*)head->f, s) == 0) return 1;
  head = head->next;
 }
 return 0;
}

student* sort(student* ph) {
 student* q, *out = NULL, *p, *pr; //out - выход - сначала пуст
 while (ph != NULL) { //пока не конец входного списка
  q = ph; ph = ph->next; //исключить очередной элемент
  for (p = out, pr = NULL;
   p != NULL && _stricmp((char*)q->f, (char*)p->f) > 0;
   pr = p, p = p->next);
  //ищем, куда включить очередной элемент - тут stricmp
  //задает критерий сравнения элементов, в вашей задаче м.б. другой
  if (pr == NULL) { q->next = out; out = q; } //включение в начало
  else { q->next = p; pr->next = q; } //или после предыдущего
 }
 return out;
}

student* exclude(student* head, char* f) {
 if (head == NULL) return NULL;
 student* current = head, //текущая запись
  *start = head, //начало списка
  *prev = NULL; //предыдущая запись
 while (current) {
  if (_stricmp((char*)current->f, f) == 0) {
   if (prev) prev->next = current->next;
   else start = current->next;
   free(current);
   break;
  }
  prev = current;
  current = current->next;
 }
 return start;
} //в коде выше заменил strlwr => _strlwr, strstr => _strstr

void enter(student *st) { //Ввод записи с клавиатуры в буферную запись
 printf("\nEnter the name and 4 balls:");
 scanf("%s %d %d %d %d", st->f, &st->ekz[0], &st->ekz[1],
  &st->ekz[2], &st->ekz[3]);
 //st->id = ++max_id;
}

void save(student* head) {
 if (!head) {
  printf("\nNotning to write"); return;
 }
 FILE* f = fopen("data.dat", "wb");
 if (!f) {
  printf("\nCan't open data.dat to write"); return;
 }
 do {
  fwrite(head, sizeof(student), 1, f);
  head = head->next;
  if (!head) break;
 } while (1);
 fclose(f);
}

int main() { //Меню и вызов функций
 setlocale(LC_ALL, ".1251"); SetConsoleCP(1251); SetConsoleOutputCP(1251);
 student* head = NULL; student* s; char buf[40]; FILE* f; 
 student st = {0, "Anonymous", {5,5,5,5}, nullptr }; //Буферная запись для ввода
 int k;
 do {
  printf("\n1. Add in head\n2. Add in tail\n3. Show all\n\
4. Sorting\n5. Delete\n6. Save to file\n7. Load from file\n8. Search\n0. Exit\n");
  fflush(stdin); int n; scanf("%d", &n);
  student* ptr; char searchbuf[MAX];
  switch (n) {
  case 1: enter(&st); head = add1(head, &st); break;
  case 2: enter(&st); if (head) add2(head, &st); else head = add1(head, &st);  break;
  case 3: show(head); break;
  case 4: head = sort(head); break;
  case 5:
   printf("\nName for deleting:");
   scanf("%s", buf);
   s = search(head, buf);
   if (!s) printf("\nNot found"); else head = exclude(head, buf);
   break;
  case 6: save(head); break;
  case 7:
   f = fopen("data.dat", "rb");
   if (!f) {
    printf("\nCan't open data.dat to read"); break;
   }
   if (head) do { //удалить имеющийся список
    head = exclude(head, (char*)head->f);
   } while (head);
   while (1) { //загрузить данные из файла
    k = fread(&st, sizeof(student), 1, f);
    if (k != 1) break;
    st.next = NULL;
    if (st.id > max_id) max_id = st.id;
    if (head) add2(head, &st);
    else head = add1(head, &st);
    if (feof(f)) break;
   }
   fclose(f);
   break;
  case 8:
   ptr = head;
   printf("\nEnter search string: ");
   fflush(stdin);
   scanf("%s", searchbuf);
   do { //возможность неоднократного поиска
    ptr = search(ptr, searchbuf);
    if (ptr) {
     printf("\n%s", ptr->f); //лучше - вызвать метод для вывода записи
     ptr = ptr->next; //следующий поиск - со след.эл.-та
    }
   } while (ptr);

   break;
  case 0: exit(0);
  }
 } while (1);
 return 0;
}

07.03.2015, 13:27 [18374 просмотра]