Очередь в виде односвязного списка.

R

Ravenholm

Сообщения
4
Реакции
0
Всем привет. Я давно не работал на C++, знакомый учится в универе ,просил помочь.

Задача реализовать список студентов при помощи очереди.
Предусмотреть возможность удаления студента по фамилии.
Так вот при попытке отобразить новый список после удаления, программа бросает исключение об ошибке доступа к памяти.

Хотя вроде, после удаления достаточно присвоить указателю на удаляемый элемент адрес следующего элемента.

День мучаюсь с этим.

C++: 
//Реализация очереди

template <class T>
struct BaseQueue
{
    T Element;
    BaseQueue* nextNode;
};

template <class T>
void InsertToQueue(BaseQueue<T>** pFirstElement, T pElement)
{
    BaseQueue<T>* currentElement = *pFirstElement;
    BaseQueue<T>* previous = nullptr;
    BaseQueue<T>* newNode = nullptr;
    while (currentElement)
    {
        previous = currentElement;
        currentElement = currentElement->nextNode;
    }
    newNode = new BaseQueue<T>;
    newNode->Element = pElement;
    if (previous)
    {
        newNode->nextNode = nullptr;
        previous->nextNode = newNode;
    }
    else
    {
        *pFirstElement = newNode;
        (*pFirstElement)->nextNode = nullptr;
    }
}

template<class T>
void DeleteElementFromQueue(BaseQueue<T>** pFirstElement)
{
    BaseQueue<T>* oldItem = *pFirstElement;
    if (*pFirstElement)
    {
        *pFirstElement = (*pFirstElement)->nextNode;
        delete oldItem;
    }
}
Реализация удаления по имени


Код: 
void DelStudentByName(BaseQueue<Student>** pStudentQueue, const char *pFullName,SearchStatus &status)
{
    BaseQueue<Student>* current = *pStudentQueue;
    BaseQueue<Student>* previous = nullptr;
    status = SEARCH_QUEUE_EMPTY;
    while (current)
    {
        status = SEARCH_QUEUE_NOT_FINDED;
        if (strstr(current->Element.FullName, pFullName))
        {
            status = SEARCH_QUEUE_SUCCESS;
            DeleteElementFromQueue(&current);
            break;
        }
        previous = current;
        current = current->nextNode;
    }
   

}
 
R

Ravenholm

Сообщения
4
Реакции
0
Я бы использовал другие способы реализации, но по методичке нельзя
 
fl0wer

fl0wer

Сообщения
1,701
Реакции
1,512
Помог
26 раз(а)
Посмотри исходники уже существующих списков.
 
R

Ravenholm

Сообщения
4
Реакции
0
fl0wer, смотрел , везде практически реализация одинаковая , но даже если просто присвоить элементу следующее значение списка, ничего не изменится
 
fantom

fantom

Сообщения
2,491
Реакции
2,794
Помог
61 раз(а)
Ravenholm написал(а):
смотрел , везде практически реализация одинаковая , но даже если просто присвоить элементу следующее значение списка, ничего не изменится
Нажмите для раскрытия...
Если почти везде одно и то же, то скорей всего это по мнению большинства либо самая простая либо самая лушчая реализация. И я склоняюсь скорее ко второму пункту. А если у вас преподаватель за крок врпаво крок влево и растрел если не пометодичке, то мне вас жаль, так как знаний он вам не даст. (но это совсем другой вопрос)
 
R

Ravenholm

Сообщения
4
Реакции
0
fantom, не мне, моему знакомому. У меня были другие варианты. Но они к сожалению не подходят. Сам я уже закончил универ. Когда преподавали у нас программирование, тоже такое себе было. Но так как мне очень интересно этим было заниматься, я учился сам. И после крестов на другие языки было очень легко переходить. Тот же Pawn как пример. А так я в основном работаю на C#.
 
R

Ravenholm

Сообщения
4
Реакции
0
Реализация из методички
C++: 
//Реализация из методички

#include "stdafx.h"
#include "string.h"
#include "stdlib.h"
#include "stdio.h"
#include "ctype.h"

#define QUEUE struct List //Зачем?

QUEUE
{
    char *info;
    int num;
    QUEUE *next;

};

void insert(QUEUE **pbeg, char *item, int number);
void del(QUEUE **pbeg);
void enter(int *spos, QUEUE **q);
void review(QUEUE **q);
int _tmain(int argc, _TCHAR* argv[])
{
    char s[80];
    int spos=0;
    QUEUE *q=0;
    for(;;)
    {
        printf("Enter, List, Remove, Quit: ");
        gets(s);
        *s = toupper(*s);
        switch(*s)
        {
            case 'E':
            enter(&spos,&q);
            break;
            case 'L':
            review(&q);
            break;
            case 'R':
            del(&q);
            break;
            case 'Q':
            exit(0);
        }
    }
return 0;
}

void insert(QUEUE **pbeg, char *item, int number)
{

    QUEUE *current = *pbeg;
    QUEUE *previous = 0;
    QUEUE *new_node;
    while (current)
    {
        previous = current;
        current = current -> next;
    }
        new_node = new QUEUE;
        strcpy(new_node->info, item);
        new_node->num = number;
    if (previous)
    {
        new_node->next = 0;
        previous->next = new_node;
    }
    else
    {
        *pbeg = new_node;
        (*pbeg)->next = 0;
    }
}

void del (QUEUE **pbeg)
{
    QUEUE *old_item = *pbeg;
    if(*pbeg)
    {
        printf("%d: %s\n",(*pbeg)->num,(*pbeg)->info);
        *pbeg =(*pbeg)->next;
        free(old_item);
    }
}

void enter(int *spos, QUEUE **q)
{
    char *s;
    QUEUE *q1=*q;
    s = new char;
    do
    {
        printf("Enter appointment %d: ", spos+1);
        gets(s);
        if(*s==0)
            break;
        spos++;
        insert(&q1,s,spos);
        *q = q1;
    }while(*s);
}

void review(QUEUE **q)
{
    QUEUE *temp = *q;
    while(temp)
    {
        printf("%d. %s\n", temp->num, temp->info);
        temp = temp->next;
    }
}
 
R

Ravenholm

Сообщения
4
Реакции
0
Облазив все форумы и группы в вк, я не нашел способа решения проблемы. Может я конечно неправильно понимаю.

Этот форум, последний лучик моей надежды.

Выкладываю просто всю программу.

Чтобы не приходилось вам лишний раз скачивать исходники выкладываю на pastebin.com

base_queue.h
Код: 
//base_queue.h

#ifndef _BASE_QUEUE_H_INCLUDED
#define _BASE_QUEUE_H_INCLUDED


template <class T>
struct BaseQueue
{
    T Element;
    BaseQueue* nextNode;
};

template <class T>
void InsertToQueue(BaseQueue<T>** pFirstElement, T pElement)
{
    BaseQueue<T>* currentElement = *pFirstElement;
    BaseQueue<T>* previous = nullptr;
    BaseQueue<T>* newNode = nullptr;
    while (currentElement)
    {
        previous = currentElement;
        currentElement = currentElement->nextNode;
    }
    newNode = new BaseQueue<T>;
    newNode->Element = pElement;
    if (previous)
    {
        newNode->nextNode = nullptr;
        previous->nextNode = newNode;
    }
    else
    {
        *pFirstElement = newNode;
        (*pFirstElement)->nextNode = nullptr;
    }
}

template<class T>
void DeleteElementFromQueue(BaseQueue<T>** pFirstElelemt)
{
    BaseQueue<T>* oldItem = *pFirstElelemt;
    if (*pFirstElelemt)
    {
        *pFirstElelemt = (*pFirstElelemt)->nextNode;
        delete oldItem;
        oldItem = nullptr;
    }
}


#endif
Student.h
Код: 
//student.h

#ifndef _STUDENT_H_INCLUDED
#define _STUDENT_H_INCLUDED

#define STUDENT_MAX_FULLNAME_LENGTH 128

#define STUDENT_MAX_MARKS_COUNT 5
#include "base_queue.h"
#include <iostream>
#include <cstdlib>
#include <Windows.h>

struct Student
{
    char FullName[STUDENT_MAX_FULLNAME_LENGTH];
    size_t GroupNumber;
    size_t ListOfMarks[STUDENT_MAX_MARKS_COUNT];
};

enum SearchStatus
{
    SEARCH_QUEUE_EMPTY=101,
    SEARCH_QUEUE_NOT_FINDED,
    SEARCH_QUEUE_SUCCESS
};

void ShowStudentInfo(Student student);

void InputStudentDataFromConsole(Student& student);

void DelStudentByName(BaseQueue<Student>** pStudentQueue, const char* pFullName,SearchStatus &status);

bool isHaveStudentThisMark(Student student, int iMarkValue);

void ShowAllStudentsInfo(BaseQueue<Student>** pStudentQueue,SearchStatus& status);

void ShowAllStudentsByMark(BaseQueue<Student>* pStudentQueue, size_t iMarkValue, SearchStatus& status);

                            
#endif // !_STUDENT_H_INCLUDED
Student.cpp
Код: 
//Student.cpp

#include "student.h"






void ShowStudentInfo(Student student)
{
    std::cout << "ФИО:" <<student.FullName<<std::endl;
    std::cout << "Номер группы:" << student.GroupNumber << std::endl;
    std::cout << "Оценки:";
    for (int i = 0; i < STUDENT_MAX_MARKS_COUNT; i++)
        std::cout << student.ListOfMarks[i] << " ";
    std::cout << std::endl;
}

void InputStudentDataFromConsole(Student& student)
{
    std::cout << "ФИО:";
    std::cin.ignore();
    std::cin.getline(student.FullName, STUDENT_MAX_FULLNAME_LENGTH);
    std::cout << "Номер группы:" << std::endl;
    while (!(std::cin >> student.GroupNumber))
    {
        std::cin.clear();
        while (std::cin.get() != '\n');                               
        {
            std::cout << "Ошибка ввода данных" << std::endl;
            std::cout << "Номер группы:";
        }
    }
    for (int i = 0; i < STUDENT_MAX_MARKS_COUNT; i++)
    {
        std::cout << i + 1 << "-я оценка:";
        while (!(std::cin >> student.ListOfMarks[i]))
        {
            std::cin.clear();
            while (std::cin.get() != '\n');
            {
                std::cout << "Ошибка ввода данных" << std::endl;
                std::cout << i+1 <<"-я оценка:";
            }
        }
    }
}

void DelStudentByName(BaseQueue<Student>** pStudentQueue, const char *pFullName,SearchStatus &status)
{
    BaseQueue<Student>* current = *pStudentQueue;
    BaseQueue<Student>* previous = nullptr;
    status = SEARCH_QUEUE_EMPTY;
    while (current)
    {
        status = SEARCH_QUEUE_NOT_FINDED;
        if (strstr(current->Element.FullName, pFullName))
        {
            status = SEARCH_QUEUE_SUCCESS;
            DeleteElementFromQueue(&current);
            break;
        }
        previous = current;
        current = current->nextNode;
    }
    

}

bool isHaveStudentThisMark(Student student, int iMarkValue)
{
    for (int i = 0; i < STUDENT_MAX_MARKS_COUNT; i++)
        if (student.ListOfMarks[i] == iMarkValue)
            return true;
    return false;
}

void ShowAllStudentsInfo(BaseQueue<Student>* pStudentQueue,SearchStatus& status)
{
    status = SEARCH_QUEUE_EMPTY;
    BaseQueue<Student>* current = *pStudentQueue;
    if (!current)
        system("PAUSE");
    int iCount = 0;
    while (current)
    {
        status = SEARCH_QUEUE_SUCCESS;
        std::cout << "id=" << iCount + 1 << std::endl;
        ShowStudentInfo(current->Element);
        current = current->nextNode;
        iCount++;
        std::cout << "---------------------------------" << std::endl;
    }
}

void ShowAllStudentsByMark(BaseQueue<Student>* pStudentQueue, size_t iMarkValue,SearchStatus& status)
{
    status = SEARCH_QUEUE_EMPTY;
    BaseQueue<Student>* current = pStudentQueue;
    BaseQueue<Student>* previous = nullptr;
    while (current)
    {
        status = SEARCH_QUEUE_NOT_FINDED;
        if (isHaveStudentThisMark(current->Element, iMarkValue))
        {
            status = SEARCH_QUEUE_SUCCESS;
            ShowStudentInfo(current->Element);
            std::cout << "-------------------------" << std::endl;
            if (!current->nextNode)
            {   
                //std::cout << "Конец списка " << std::endl;
                break;
            }
        }
        previous = current;
        current = current->nextNode;
    }   
}
Ну и сам main.cpp

C++: 
#include "student.h"


enum MenuItem
{
    MENU_KEY_1=1,
    MENU_KEY_2,
    MENU_KEY_3,
    MENU_KEY_4,
    MENU_KEY_5
};

void ShowMenuItems()
{
    std::cout << "1.Добавить студента в базу" << std::endl;
    std::cout << "2.Вывести всех студентов в базе" << std::endl;
    std::cout << "3.Удалить студента по фамилии(удаляет первого попавшегося)" << std::endl;
    std::cout << "4.Вывести двоечников" << std::endl;
    std::cout << "5.Выход" << std::endl;
}

int main(int argc, char* argv[])
{
    BaseQueue<Student>* studentList = 0;
    SearchStatus status = SEARCH_QUEUE_EMPTY;
    bool isExit = false;
    bool isEmpty = true;
    int iMenuItem = 0;
    int iStudentCount = 0;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    char buffer[STUDENT_MAX_FULLNAME_LENGTH];
    Student inputStudent;
    do {
        system("cls");
        ShowMenuItems();
        std::cout << "Пункт меню";
        while (!(std::cin >> iMenuItem))
        {
            std::cin.clear();
            while (std::cin.get() != '\n');
            {
                std::cout << "Ошибка, неккоректный ввод" << std::endl;
                std::cout << "Пункт меню";
            }
        }
        switch (iMenuItem)
        {
            case MENU_KEY_1:
                system("cls");
                std::cout << iStudentCount + 1 << "-й студент" << std::endl;
                InputStudentDataFromConsole(inputStudent);
                InsertToQueue(&studentList, inputStudent);
                iStudentCount++;
                std::cout << "Успешно" << std::endl;
                system("PAUSE");
                break;
            case MENU_KEY_2:
                system("cls");
                if (studentList)   //Это я уже с ума сходил когда пытался понять в чем дело.
                    system("PAUSE");
                    ShowAllStudentsInfo(studentList, status);
                switch (status) {
                    case SEARCH_QUEUE_EMPTY:
                        std::cout << "Список пуст" << std::endl;
                        break;
                }
                system("PAUSE");
                break;
            case MENU_KEY_3:
                system("cls");
                std::cout << "Введите фамилию:";
                std::cin.ignore();
                std::cin.getline(buffer, STUDENT_MAX_FULLNAME_LENGTH);
                DelStudentByName(&studentList, buffer, status);
                switch (status)
                {
                    case SEARCH_QUEUE_EMPTY:
                        std::cout << "Список пуст" << std::endl;
                        break;
                    case SEARCH_QUEUE_NOT_FINDED:
                        std::cout << "Студент с такой фамилией не найден" << std::endl;
                        break;
                    case SEARCH_QUEUE_SUCCESS:
                        std::cout << "Запись успешно удалена" << std::endl;
                        iStudentCount--;
                        break;
                }
                system("PAUSE");
                break;
            case MENU_KEY_4:
                system("cls");
                std::cout << "Двоечники" << std::endl;
                ShowAllStudentsByMark(studentList, 2, status);
                switch (status)
                {
                    case SEARCH_QUEUE_EMPTY:
                        std::cout << "Список студентов пуст" << std::endl;
                        break;
                    case SEARCH_QUEUE_NOT_FINDED:
                        std::cout << "Двоечники не найдены" << std::endl;
                        break;
                    case SEARCH_QUEUE_SUCCESS:
                        std::cout << "Двоечники найдены" << std::endl;
                        break;

                }
                system("PAUSE");
                break;
            case MENU_KEY_5:
                isExit = true;
                break;
        }
    } while (!isExit);

    return 0;
}
 
Последнее редактирование модератором:
fantom

fantom

Сообщения
2,491
Реакции
2,794
Помог
61 раз(а)
Ravenholm, я так до конца и не понял что нужно сделать. Но спешу вас огорчить. Тут тех кто шарит в Си не так много. Возможно вам лучше обратится на профильный форум или чат в мессенджерах?
 
R

Ravenholm

Сообщения
4
Реакции
0
fantom, удалить студента по имени из очереди. Но при попытке вывода нового списка после удаления, программа бросает исключение об ошибке доступа к памяти.
 
Garey

Garey

ninjaCow
Сообщения
440
Реакции
1,094
Помог
11 раз(а)
Код: 
template<class T>
void DeleteElementFromQueue(BaseQueue<T>** pPrevious, BaseQueue<T>** pCurrent)
{
    if (*pCurrent)
    {
        if (*pPrevious)
        {
            (**pPrevious).nextNode = (**pCurrent).nextNode;
        }
        delete *pCurrent;
    }
}
и т.к. если указатель BaseQueue<Student>* current внутри функции DeleteElementFromQueue изменить, то указатель на pStudentQueue не изменится, то надо добавить условие если это первый элемент списка:
Diff: 
void DelStudentByName(BaseQueue<Student>** pStudentQueue, const char* pFullName, SearchStatus& status)
{
    BaseQueue<Student>* current = *pStudentQueue;
    BaseQueue<Student>* previous = nullptr;
    status = SEARCH_QUEUE_EMPTY;
    while (current)
    {
        status = SEARCH_QUEUE_NOT_FINDED;
        if (strstr(current->Element.FullName, pFullName))
        {
            status = SEARCH_QUEUE_SUCCESS;
++          if (!previous)
++              *pStudentQueue = (*current).nextNode;
            DeleteElementFromQueue(&previous ,&current);
            break;
        }
        previous = current;
        current = current->nextNode;
    }
}
 
R

Ravenholm

Сообщения
4
Реакции
0
Garey, спасибо большое , я просто думал, что если подставлять в функцию DeleteElementFromQueue конкретный элемент, то он просто все последующие передвинет на 1 блок. У меня походу наступила эйфория.

И еще один вопрос. Код читабельным был?
 
R

Ravenholm

Сообщения
4
Реакции
0
fl0wer, к сожалению, в университете нормально никогда программирование не преподают, или не разбирают типовые задачи. Чаще всего если студенту интересно заниматься программированием, он сам уже ищет способы как этому научиться. Сам сталкивался с этим много раз. У нас например на втором курсе, пока мы делали что-то, препод играл в 3х героев.
 
fl0wer

fl0wer

Сообщения
1,701
Реакции
1,512
Помог
26 раз(а)
Ravenholm, ой, видимо вас на ИВТ не учил Тарасов. Привет, ИжГТУ.
 
Войдите или зарегистрируйтесь для ответа.

Пользователи, просматривающие эту тему

Сейчас на форуме нет ни одного пользователя.
Всего: 1 (пользователей: 0, гостей: 1)
Сверху Снизу