Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
slonni
0 / 0 / 0
Регистрация: 07.12.2009
Сообщений: 18
05.12.2011, 22:42     Кольцевой односвязный список #1
Реализовал класс для работы со списком студентов( использовал кольцевой односвязный список). Для навигации по классу используется итератор. Со временем данный класс будет сделан шаблонным.

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

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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2011, 22:42     Кольцевой односвязный список
Посмотрите здесь:

кольцевой список C++
C++ Кольцевой список
Кольцевой список C++
C++ Кольцевой односвязный список
C++ Кольцевой односвязный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
05.12.2011, 23:02     Кольцевой односвязный список #2
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

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

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

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

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

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

И, наверное таки нужно будет убрать Iterator end(). Всё таки список кольцевой а не линейный.
Yandex
Объявления
05.12.2011, 23:53     Кольцевой односвязный список
Ответ Создать тему
Опции темы

Текущее время: 14:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru