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 нельзя).
На основе этого шаблона легко реализовать свой вариант задания, изменив описание структурного типа и методы print, search, copy0, check, sort, enter, read, save и организацию меню в функции main.
/*
Реализация лабораторной работы с помощью динамического односвязного списка
структур фиксированного размера
*/
#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 << "Всего: " << 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) {
//Добавление записи st в начало списка head
student* current = new student;
if (!current) {
cout << endl << "Нет памяти!"; 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) {
//Добавление записи st в конец списка, начинающегося с head
student* last = NULL;
if (head) {
last = head;
while (last->next) last = last->next;
}
student* current = new student;
if (!current) {
cout << endl << "Нет памяти!"; 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, если фамилия s есть в списке head
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) {
//Удаление записи по 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) {
//Ввод целого со значением от min до max и приглашением msg, номер num опционален
int d;
while (1) {
cout << endl << msg;
if (num) cout << " " << num;
if (min != INT_MIN || max != INT_MAX) cout << " [" << min << "-" << 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) {
//Ввод строки с длиной от min до max символов и приглашением msg, номер num опционален
string tmp;
bool clear = true;
while (1) {
cout << endl << msg;
if (num) cout << " " << num;
cout << " [" << min << "-" << max << "]: ";
if (clear) {
cin.clear();
cin.ignore(INT_MAX, '\n');
}
getline(cin, tmp);
if (tmp.length() >= min && tmp.length() <= max) return tmp;
else clear = false;
tmp.clear();
}
}
void enter(student* st) {
//Ввод одной записи с клавиатуры в буферную запись
string tmp = enter_string((unsigned char*)"Enter the name", 2, 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) {
//Чтение списка из файла data.dat
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 << "Не могу открыть файл data.dat для чтения";
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 << "Не могу прочитать id #" << cnt << " из data.dat";
return start;
}
f.read((char*)&buf[0], MAX);
if (!f) {
cout << endl << "Не могу прочитать имя #" << cnt << " из data.dat";
return start;
}
st.f = string((char*)buf);
f.read((char*)&st.ekz[0], 4 * sizeof(int));
if (!f) {
cout << endl << "Не могу прочитать баллы #" << cnt << " из 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) {
//Запись списка в файл data.dat
unsigned char buf[MAX + 1]; //Буфер для записи строк
if (!head) {
cout << endl << "Нечего записывать"; return;
}
ofstream f("data.dat");
if (!f) {
cout << endl << "Не могу открыть data.dat для записи";
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 }; //Буферная запись для ввода
student* head = NULL, * ptr;
int n, id;
setlocale(LC_ALL, ".1251"); SetConsoleCP(1251); SetConsoleOutputCP(1251);
do {
cout << endl <<
"1. Добавить в начало\n" <<
"2. Добавить в конец\n" <<
"3. Показать все\n" <<
"4. Сортировать по имени\n" <<
"5. Удалить по id\n" <<
"6. Сохранить в файл\n" <<
"7. Загрузить из файла\n" <<
"8. Поиск\n" <<
"0. Выход";
n = enter_int((const unsigned char*)"Выберите действие", 0, 8);
switch (n) {
case 1: /* добавить в начало */
enter(&st);
if (check(head, (char*)st.f.c_str())) //Фамилия уже есть
cout << endl << "Имя уже существует, не добавлено";
else
head = add1(head, &st);
break;
case 2: /* добавить в конец */
enter(&st);
if (check(head, (char*)st.f.c_str())) //Фамилия уже есть
cout << endl << "Имя уже существует, не добавлено";
else {
if (head) add2(head, &st);
else head = add1(head, &st);
}
break;
case 3: /* показать всё */
if (!head) { cout << endl << "Список пуст"; continue; }
show(head);
break;
case 4: /* сортировать */
if (!head) { cout << endl << "Список пуст"; continue; }
head = sort(head);
break;
case 5: /* удалить */
if (!head) { cout << endl << "Список пуст"; continue; }
id = enter_int((unsigned char*)"Id для удаления", 1, max(max_id, 1));
tmp = std::to_string(id);
ptr = search(head, (unsigned char*)tmp.c_str(), SEARCH_ID);
if (!ptr) cout << endl << "Запись не найдена";
else head = exclude(head, id);
break;
case 6: /* сохранить в файл */
save(head);
break;
case 7: /* прочитать из файла */
head = read(head);
break;
case 8: /* поиск */
if (!head) { cout << endl << "Список пуст"; continue; }
ptr = head; id = 0;
tmp = enter_string((unsigned char*)"Введите строку для поиска", 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 << "Ничего не найдено";
break;
case 0: /* выход */
exit(0);
default: /* введено неверное n */
break;
}
} while (1);
return 0;
}
07.03.2015, 13:27 [20119 просмотров]