Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/18: Рейтинг темы: голосов - 18, средняя оценка - 4.56
0 / 0 / 0
Регистрация: 07.12.2009
Сообщений: 18

Кольцевой односвязный список

05.12.2011, 22:42. Показов 3673. Ответов 5
Метки нет (Все метки)
Студворк — интернет-сервис помощи студентам
Реализовал класс для работы со списком студентов( использовал кольцевой односвязный список). Для навигации по классу используется итератор. Со временем данный класс будет сделан шаблонным.

Код рабочий, но хотелось бы услышать Ваши замечания, может что улучшить можно.

Stud.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#define SUCCESS 1
#define NOT_SUCCESS -1
 
#include <iostream.h>
#include <string.h>
 
class Student
{
friend ostream &operator<<(ostream &, const Student &);
friend istream &operator>>(istream &, Student &);
 
private:
    char* surName;
    char* fatherName;
    char* name;
    int birthYear;
    float avgMark;
    char* group;
 
public:
    Student();
    ~Student();
    void SetAllFields(char*, char*, char*, int, float, char*);
    void ClearMemory();
    void FreeField(char **);
    int CheckStud(Student &s);
 
    Student& operator= (const Student &);
 
    int operator== (Student &);
    int operator!= (Student &);
    int operator>= (Student &);
    int operator<= (Student &);
    int operator> (Student &);
    int operator< (Student &);
 
 
    void SetSurName(char*);
    void SetFatherName(char*);
    void SetName(char*);
    void SetBirthYear(int bYear=1991);
    void SetAverMark(float);
    void SetGroup(char*);
 
    char* GetSurName() const;
    char* GetFatherName() const;
    char* GetName() const;
    int GetBirthYear() const;
    float GetAverageMark() const;
    char* GetGroup() const;
};
Stud.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

#include "stud.h"
 
Student::Student()
{
    surName=fatherName=name=group=NULL;
}
 
Student::~Student()
{
    //ClearMemory();
}
 
 
void Student::SetAllFields(char* sName, char* fName, char* mName, int bYear, float avMark, char* aGroup)
{
    ClearMemory();
 
    surName=new char[strlen(sName)+1];
    fatherName=new char[strlen(fName)+1];
    name=new char[strlen(mName)+1];
    group=new char[strlen(aGroup)+1];
 
    strcpy(surName, sName);
    strcpy(fatherName, fName);
    strcpy(name, mName);
    strcpy(group, aGroup);
 
    birthYear=bYear;
    avgMark=avMark;
}
 
void Student::FreeField(char **tmp)
{
    if(*tmp!=NULL)
    {
        delete *tmp;
        *tmp=NULL;
    }
}
 
void Student::ClearMemory()
{
    FreeField(&surName);
    FreeField(&fatherName);
    FreeField(&name);
    FreeField(&group);
}
 
int Student::CheckStud(Student &s)
{
    if((surName == NULL) || (s.surName == NULL))
        return 0;
    return (strcmp(surName,s.surName));
}
 
 
Student& Student::operator= (const Student &s)
{
    if(this != &s)
        SetAllFields(s.surName, s.fatherName, s.name, s.birthYear, s.avgMark, s.group);
 
    return *this;
}
 
int Student::operator==(Student &s)
{
    return (CheckStud(s) == 0) ? 1 : 0;
}
 
int Student::operator!=(Student &s)
{
    return(CheckStud(s) != 0) ? 0 : 1;
}
 
int Student::operator>=(Student &s)
{
    return (CheckStud(s) >= 0) ? 1 : 0;
}
 
int Student::operator<=(Student &s)
{
    return (CheckStud(s) <= 0)  ? 1 : 0;
}
 
int Student::operator>(Student &s)
{
    return (CheckStud(s) > 0) ? 1 : 0;
}
 
int Student::operator<(Student &s)
{
    return (CheckStud(s) < 0) ? 1 : 0;
}
 
 
void Student::SetSurName(char *sName)
{
    surName=sName;
}
 
void Student::SetFatherName(char *fName)
{
    fatherName=fName;
}
 
void Student::SetName(char *aName)
{
    name=aName;
}
 
void Student::SetBirthYear(int bYear)
{
    birthYear=bYear;
}
 
void Student::SetAverMark(float avMark)
{
    avgMark=avMark;
}
 
void Student::SetGroup(char *aGroup)
{
    group=aGroup;
}
 
char* Student::GetSurName() const
{
    return surName;
}
 
char* Student::GetFatherName() const
{
    return fatherName;
}
 
char* Student::GetName() const
{
    return name;
}
 
int Student::GetBirthYear() const
{
    return birthYear;
}
 
float Student::GetAverageMark() const
{
    return avgMark;
}
 
char* Student::GetGroup() const
{
    return group;
}
 
 
ostream &operator<<(ostream &output,const Student &s)
{
    output<<"\nSurName: "<<s.surName
          <<"\nFatherName: "<<s.fatherName
          <<"\nName: "<<s.name
          <<"\nYear of birth: "<<s.birthYear
          <<"\nAverage mark: "<<s.avgMark
          <<"\nGroup: "<<s.group<<"\n";
    return output;
}
 
istream &operator>>(istream &input,Student &s)
{
    input>>s.surName>>s.fatherName>>s.name
         >>s.birthYear>>s.avgMark>>s.group;
    
    return input;
}

list.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#ifndef List_stud
#define List_stud
 
#include "iterator.h"
#include "stud.h"
 
#define SUCCESS     1
#define NOT_SUCCESS -1
 
//typedef int Student;
typedef Student INF;
//typedef int INF;
 
class List
{
private:
    struct Node
    {
        INF inf;
        Node *next;
    };
    Node *head, *tail;
 
public:
 
    friend class Iterator<Node, Student>;
    typedef Iterator<Node, Student> Iterator;
 
    List();
    List(const INF &);
    ~List();
 
    bool empty();
    void addElem(const INF &);
    int delElem(INF &);
    void delAllElem();
    int searchElement(INF &);
    void sort();
 
    Iterator begin()
    {
        return Iterator(head);
    }
 
    Iterator end()
    {
        return Iterator(tail);
    }
};
 
#endif
list.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#include "list.h"
#include <iostream.h>
 
List::List()
{
    head=tail=NULL;
}
 
List::List(const INF &data)
{
    //head=new Node;
    head->inf=data;
}
 
List::~List()
{
    delAllElem();
}
 
bool List::empty()
{
    return (head == NULL);
}
 
void List::addElem(const INF &data)
{
    Node *cur=new Node;
    cur->inf=data;
 
    if(head != NULL)
        tail->next=cur;
    else
        head=cur;
 
    cur->next=head;
    tail=cur;
}
 
// Переделать!
int List::delElem(INF &data)
{
    if (!(head))
        return NOT_SUCCESS;
 
    Node *cur=head;
    Node *temp=tail;
 
    do
    {
        if(cur->inf == data)
        {
            if(cur == head)
                head=cur->next;
            if(cur == tail)
                tail=temp;
 
            temp->next=cur->next;
            delete cur;
            tail->next=head;
            return SUCCESS;
        }
 
        temp=cur;
        cur=cur->next;
    }while(cur!=head);
    
return NOT_SUCCESS;
}
 
void List::delAllElem()
{
    Node *cur;
 
    if(head)
        tail->next=NULL;
 
    while(head != NULL)
    {
        cur=head;
        head=head->next;
        delete cur;
    }
    tail=NULL;
}
 
int List::searchElement(INF &data)
{
    if (!(head))
        return NOT_SUCCESS;
 
    Node *cur=head;
 
    do
    {
        if(cur->inf == data)
            return SUCCESS;
 
        cur=cur->next;
    }while(cur!=head);
 
    return NOT_SUCCESS;
}
 
//СОРТИРОВКА НЕДОДЕЛАНА
void List::sort()
{
    if(head)
        tail->next=NULL;
 
    Node* new_begin=NULL;
    Node* new_end=NULL;
    Node* sprev=NULL;
 
    for(Node *scur=this->head;scur!=NULL;scur=this->head)
    {
        Node *smin=NULL;
        Node *sminprev=scur;
        Student min_elem=scur->inf;
 
        for(Node *gp=scur->next;gp!=NULL;gp=gp->next)
        {
            if((gp->inf)<=min_elem)
            {
                min_elem=gp->inf;
                smin=gp;
                sprev=sminprev;
            }
            sminprev=gp;
        }
        if(smin==NULL)
        {
            smin=scur;
        }
        else if(smin==scur->next)
        {
            scur->next=scur->next->next;
        }
        else
        {
            sprev->next=smin->next;
        }
        if(new_begin!=NULL)
        {
            new_end->next=smin;
            new_end=smin;
        }
        else
        {
            new_begin=smin;
            new_end=smin;
        }
        if(smin==this->head)
         this->head=smin->next;
    }
    this->head=new_begin;
    this->tail=new_end;
 
    tail->next=head;
}

iterator.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#ifndef Iterator_List
#define Iterator_List
 
template<typename T, typename E>
class Iterator
{
    T* cur;
 
public:
    Iterator();
    Iterator(T *);
 
    Iterator& operator++();
    bool operator==(const Iterator &) const;
    bool operator!=(const Iterator &) const;
    E& operator*();
};
 
template<typename T, typename E>
Iterator<T,E>::Iterator()
{
    cur=NULL;
}
 
template<typename T, typename E>
Iterator<T,E>::Iterator(T *node)
{
    cur=node;
}
 
template<typename T, typename E>
Iterator<T,E>& Iterator<T,E>::operator ++()
{
    if(*this != NULL)
        cur = cur->next;
 
    return *this;
}
 
template<typename T, typename E>
bool Iterator<T,E>::operator==(const Iterator& right) const
{
    return (cur == right.cur);
}
 
template<typename T, typename E>
bool Iterator<T,E>::operator!=(const Iterator& right) const
{
    return !(*this == right.cur);
}
 
template<typename T, typename E>
E& Iterator<T,E>::operator*()
{
    if(*this != NULL)
        return cur->inf;
}
 
#endif

Ну и напоследок файл test.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <conio.h>
#include <iostream.h>
 
#include "list.h"
 
int main()
{
    List ls;
    List::Iterator it=ls.begin();
    INF a,b,c;
 
    a.SetAllFields("Ivanov", "Ivan", "Ivanovich", 1992, 64.3f, "KT-09-1");
    b.SetAllFields("Baranov", "Ivan2", "Ivanovich2", 1991, 74.3f, "KS-09-1");
    c.SetAllFields("Avdeev", "Ivan3", "Ivanovich3", 1990, 84.3f, "KM-09-1");
 
    ls.addElem(a);
    ls.addElem(b);
    ls.addElem(c);
 
    cout<<"\nList: ";
    it=ls.begin();
    do
    {
        cout<<*it<<" ";
        ++it;
    }while(it!=ls.begin());
 
//    ls.delElem(c);
//    ls.sort();
    
    cout<<"\nList: ";
    it=ls.begin();
    do
    {
        cout<<*it<<" ";
        ++it;
    }while(it!=ls.begin());
 
    cout<<"\n";
    getch();
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
 05.12.2011, 22:42
Ответы с готовыми решениями:

Односвязный кольцевой список
Односвязный кольцевой список. в качестве аргумента передается значение value. Если оно есть в списке, необходимо вместо первого...

Кольцевой односвязный список
Есть список программа удаляет добавляет редактирует сортирует есть поиск но если сначала добавить потом еще добавить потом редактировать...

Кольцевой односвязный список
Доброго времени суток, требуется помощь в создании односвязного кольцевого списка. смог только этот быдлокод: struct stud { ...

5
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
05.12.2011, 23:02
int operator== (Student &);
int operator!= (Student &);
int operator>= (Student &);
int operator<= (Student &);
int operator> (Student &);
int operator< (Student &);

операторы должны быть константными и принимать константные ссылки на студентов.

Если есть возможность один оператор реализовать через другой, то наверно стоит этим воспользоваться.
Например для реализации != можно воспользоваться уже имеющейся реализации ==: return !(lhs == rhs). C другими операторами прожно проделать то же самое.

Почему вместо std::string используются указатели на чары? На это есть причина или просто по не знанию?

Добавлено через 15 минут
List(const INF &); - сомнительный конструктор. зачем такой нужен?
bool empty(); - константная ф-ия
int delElem(INF &); - сомнительно. Удалять лучше по итератору. Не очевидно, что тут удалится. Первый студент или все такие студенты.
int searchElement(INF &); - константная ф-ия, возвращающая bool и принимающая константного студента. В стл такие ф-ии возвращают итераторы. то, что вернулось из ф-ии проверяется на равеноство с end итератором

Iterator begin()
Iterator end()
// без константных версий ф-ии в некоторых контекстах список будет сложно или невозможно использовать. Нужны константные версии ф-ий и константные итераторы.


template<typename T, typename E> - имхо лучше без второго аргумента делать, а потребовать, чтобы у типа Т был вложенный тип ValueType. Так выглядит целостнее чтоли. Внутни итератора его можно перетайпдефить для удобства, ну или использовать как есть, т.е. typename T::ValueType

Имплемент не смотрел, ибо интерфейсы сильно хромают.
0
0 / 0 / 0
Регистрация: 07.12.2009
Сообщений: 18
05.12.2011, 23:06  [ТС]
Насчёт константных операторов сравнения учту, спасибо. В условии к лабе указано что именно такие операторы сравнения должны присутствовать, тоесть особо нет смысла реализовать один через другой. Использование char* обусловлено тем, что для данного списка студентов будет разработан GUI.
0
Фрилансер
Эксперт С++
 Аватар для Dekio
5845 / 1226 / 499
Регистрация: 23.11.2010
Сообщений: 3,373
Записей в блоге: 1
05.12.2011, 23:09
Цитата Сообщение от slonni Посмотреть сообщение
#ifndef List_stud #define List_stud
#pragma once
1
DU
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
05.12.2011, 23:12
ну и что, что будет GUI. если нужны именно указатели на чары, то у std::string есть для этого ф-ия c_str. со стрингами будет меньше мороки и ошибок с управлением памяти. У вас уже сейчас в классе студента заложен баг из-за отсутствия своего а не дефолтного конструктора копирования. Дефолтный вам не подойдет. Кстити, у списка тоже нет конструктора копирования. Из-за этого будут проблемы.

На счет операторов:
не соблюдение правил их написания может привести к ошибкам компиляции. например
Student GetSomeMagicStudent();

Student student;
...
if (student == GetSomeMagicStudent()) ...
Не везде это скомпилится, потому что в оператор уйдет неконстантная ссылка на временный объект, что не разрешается.
1
0 / 0 / 0
Регистрация: 07.12.2009
Сообщений: 18
05.12.2011, 23:53  [ТС]
Ага, конструктор и вправду сомнительный, хотя это и есть констуктор копирования, точнее должен был им быть , правда в реализании непонятно что я написал, пока удалю его.

Функция int delElem(INF &) удаляет конкретный элемент списка, удаляется только один такой студент, хотя с несколькими одинаковыми не пробовал.

Здесь итератор используется исключительно для навигации по списку, тоесть поиск впринципе можно прикрутить, а вот удаление я оставлю классу List.

И, наверное таки нужно будет убрать Iterator end(). Всё таки список кольцевой а не линейный.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
 05.12.2011, 23:53
Помогаю со студенческими работами здесь

Кольцевой односвязный список
Собственно что это и с чем его едят! Как реализовать, если это что-то страшное! Задача : сделать класс реализующий односвязный...

Кольцевой односвязный список, сортировка
Помогите, пожалуйста, с сортировкой списка. #include &lt;iostream&gt; #include &lt;stdlib.h&gt; using namespace std; struct Node { int...

Односвязный кольцевой список, реализовать
Помогите написать и реализовать кольцевой список

Кольцевой односвязный список, удалить из него все отрицательные числа
Здравствуйте, необходимо решить проблему в задаче: &quot;Сформулируйте кольцевой список с вещественным информационным полем и удалите из него...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Условия использования - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru