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