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

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

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

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

#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;
}

P.S. С выходом Visual Studio 2017 и выше приведённый код разумнее считать устаревшим. Сформулируем задачу более полно и решим её в современных версиях Visual Studio 2019 (2022).

Для заданной структуры сформировать динамический односвязный список. Обязательные элементы приложения:

  • В структуре есть поле первичного ключа.
  • Реализован просмотр всего списка.
  • Реализовано добавление элементов в начало или в конец списка или по возрастанию ключевого поля.
  • Реализовано удаление элементов, выбранных по первичному ключу.
  • При необходимости, реализована правка элемента списка, выбранного по первичному ключу.
  • Данные хранятся в текстовом или бинарном файле.
  • Реализован интерфейс приложения с выбором команд.

Для хранения строкового поля используем std::string, что позволит нам в естественном виде сравнивать и складывать строки, но потребует внимательности при записи в бинарный файл и чтении из него (просто записать составной объект std::string оператором write нельзя).

#define _CRT_SECURE_NO_WARNINGS /* _strlwr, strcpy в Studio */
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <clocale>
#include <climits>
#include <windows.h>
using namespace std;

static const int MAX = 30; //максимальная длина фамилии
static int max_id; //максимальный идентификатор в БД
#define SEARCH_ID 1 /* режимы поиска */
#define SEARCH_NAME 2
#define SEARCH_BALL 4

struct student {
 int id;
 string f;
 int ekz[4];
 student* next;
};

void print(student* cur) { //Вывод одной записи
 cout << endl << cur->id << ". " << cur->f;
 for (int i = 0; i < 4; i++)  cout << " " << cur->ekz[i];
}

int show(student* head) { //Вывод записей, начиная с head
 int count = 0;
 if (!head) return 0;
 while (1) {
  print(head); //вывести данные очередного узла
  count++;
  if (head->next == NULL) break; //проверка на конец списка
  head = head->next;   //переход к следующему узлу
 }
 cout << endl << "All=" << count;
 return count;
}

student* search(student* head, const unsigned char* st, int mode = SEARCH_NAME) { //Поиск в любом поле
 if (head == NULL) return NULL; //список пуст
 student* next = head;
 st = (unsigned char*)_strlwr((char*)st); //чтобы поиск не зависел от регистра символов
 string tmp;
 do {
  tmp.clear();
  if (mode & SEARCH_ID) tmp += to_string(next->id) + " ";
  if (mode & SEARCH_NAME) tmp += next->f + " ";
  if (mode & SEARCH_BALL)
   for (int i = 0; i < 4; i++) tmp += to_string(next->ekz[i]) + (i < 3 ? " " : "");
  std::transform(tmp.begin(), tmp.end(), tmp.begin(),
   [](unsigned char c) { return std::tolower(c); }); //std::string в нижний регистр
  std::size_t find = tmp.find((char*)st);
  if (find != std::string::npos) return next;
  if (next->next == NULL) break;
  next = next->next;
 } while (1);
 return NULL; //не найдено
}

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

student* add1(student* head, student* st) {
 student* current = new student;
 if (!current) {
  cout << endl << "No memory!"; return NULL;
 }
 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 = new student;
 if (!current) {
  cout << endl << "No memory!"; return NULL;
 }
 current->id = ++max_id;
 copy0(current, st);
 current->next = NULL;
 if (last) last->next = current;
 return current;
}

int check(student* head, char* s) { //1, если фамилия есть в списке
 while (head) {
  if (head->f == s) 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 && q->f > p->f;
   pr = p, p = p->next);
  //ищем, куда включить очередной элемент - тут сравнение строк
  //задает критерий сравнения элементов, в вашей задаче м.б. другой
  if (pr == NULL) { q->next = out; out = q; } //включение в начало
  else { q->next = p; pr->next = q; } //или после предыдущего
 }
 return out;
}

student* exclude(student* head, int id) {
 if (head == NULL) return NULL;
 student* current = head, //текущая запись
  * start = head, //начало списка
  * prev = NULL; //предыдущая запись
 while (current) {
  if (current->id == id) {
   if (prev) prev->next = current->next;
   else start = current->next;
   delete current;
   break;
  }
  prev = current;
  current = current->next;
 }
 return start;
}

int enter_int(const unsigned char* msg, int min = INT_MIN, int max = INT_MAX, int num = 0) {
 //Ввод целого номер num со значением от min до max и приглашением msg
 int d;
 while (1) {
  cout << endl << msg;
  if (num) cout << " " << num;
  if (min != INT_MIN || max != INT_MAX) cout << " [" << min << " to " << max << "]";
  cout << ": ";
  if (cin >> d && d >= min && d <= max) {
   return d;
  }
  else {
   cin.clear();
  }
  cin.ignore(INT_MAX, '\n');
 }
}

string enter_string(const unsigned char* msg, int min = 1, int max = 79, int num = 0) {
 //Ввод строки номер num с длиной от min до max и приглашением msg
 string tmp;
 while (1) {
  cout << endl << msg;
  if (num) cout << " " << num;
  cout << " [" << min << " to " << max << "]: ";
  tmp.clear();
  cin.clear();
  cin.ignore(INT_MAX, '\n');
  getline(cin, tmp);
  if (tmp.length() >= min && tmp.length() <= max) {
   return tmp;
  }
 }
}

void enter(student* st) { //Ввод записи с клавиатуры в буферную запись
 string tmp = enter_string((unsigned char*)"Enter the name", 1, MAX);
 st->f = tmp;
 for (int i = 0; i < 4; i++)
  st->ekz[i] = enter_int((unsigned char*)"Enter ball", 2, 5, i + 1);
 st->id = ++max_id;
}

student* read(student* head) {
 string tmp;
 student st = { 0, tmp, {5,5,5,5}, NULL }; //Буферная запись для ввода
 unsigned char buf[MAX + 1]; //Буфер для чтения строк
 student* start = head;
 ifstream f("data.dat");
 if (!f) {
  cout << endl << "Can't open data.dat to read"; return start;
 }
 if (head) do { //удалить имеющийся список
  head = exclude(head, head->id);
 } while (head);
 int cnt = 1;
 while (1) { //загрузить данные из файла
  f.read((char*)&st.id, sizeof(int));
  if (f.eof()) break;
  if (!f) { cout << endl << "Can't read id #" << cnt << " from data.dat"; return start; }
  f.read((char*)&buf[0], MAX);
  if (!f) { cout << endl << "Can't read name #" << cnt << " from data.dat"; return start; }
  st.f = string((char*)buf);
  f.read((char*)&st.ekz[0], 4 * sizeof(int));
  if (!f) { cout << endl << "Can't read balls #" << cnt << " from data.dat"; return start; }
  st.next = NULL;
  if (st.id > max_id) max_id = st.id;
  if (head) add2(head, &st);
  else head = add1(head, &st);
  cnt++;
  if (f.eof()) break;
 }
 f.close();
 return head;
}

void save(student* head) {
 unsigned char buf[MAX + 1]; //Буфер для записи строк
 if (!head) {
  cout << endl << "Notning to write"; return;
 }
 ofstream f("data.dat");
 if (!f) {
  cout << endl << "Can't open data.dat to write"; return;
 }
 do {
  f.write((char*)&head->id, sizeof(int));
  strcpy((char*)buf, head->f.c_str());
  f.write((char*)&buf[0], MAX);
  f.write((char*)&head->ekz[0], 4 * sizeof(int));
  head = head->next;
  if (!head) break;
 } while (1);
 f.close();
}

int main() { //Меню и вызов функций
 string tmp;
 student st = { 0, tmp, {5,5,5,5}, NULL }; //Буферная запись для ввода
 unsigned char buf[MAX + 1]; //Буфер для чтения строк
 student* head = NULL, * ptr;
 int n, id;
 setlocale(LC_ALL, ".1251"); SetConsoleCP(1251); SetConsoleOutputCP(1251);

 do {
  cout << endl << "1. 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";
  n = enter_int((const unsigned char*)"", 0, 8);
  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: /* удалить */
   id = enter_int((unsigned char*)"Id for deleting", 1, max(max_id, 1));
   tmp = std::to_string(id);
   ptr = search(head, (unsigned char*)tmp.c_str(), SEARCH_ID);
   if (!ptr) cout << endl << "Not found";
   else head = exclude(head, id);
   break;
  case 6: /* сохранить в файл */
   save(head);
   break;
  case 7: /* прочитать из файла */
   head = read(head);
   break;
  case 8: /* поиск */
   ptr = head; id = 0;
   tmp = enter_string((unsigned char*)"Enter search string", 1, MAX);
   do { //возможность неоднократного поиска
    ptr = search(ptr, (unsigned char*)tmp.c_str(), SEARCH_ID | SEARCH_NAME | SEARCH_BALL);
    if (ptr) {
     id++;
     print(ptr);
     ptr = ptr->next; //следующий поиск - со след.эл.-та
    }
   } while (ptr);
   if (!id) cout << endl << "Not found";
   break;
  case 0: /* выход */
   exit(0);
  default: /* введено неверное n */
   break;
  }
 } while (1);
 return 0;
}

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


теги: c++ алгоритм studio

К этой статье пока нет комментариев, Ваш будет первым