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 просмотра]