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

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

05.12.2011, 22:42. Просмотров 2466. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 05.12.2011, 22:42
Ответы с готовыми решениями:

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

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

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

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

5
DU
1492 / 1138 / 165
Регистрация: 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

Имплемент не смотрел, ибо интерфейсы сильно хромают.
0
0 / 0 / 0
Регистрация: 07.12.2009
Сообщений: 18
05.12.2011, 23:06  [ТС] 3
Насчёт константных операторов сравнения учту, спасибо. В условии к лабе указано что именно такие операторы сравнения должны присутствовать, тоесть особо нет смысла реализовать один через другой. Использование char* обусловлено тем, что для данного списка студентов будет разработан GUI.
0
Фрилансер
Эксперт С++
5843 / 1224 / 499
Регистрация: 23.11.2010
Сообщений: 3,377
Записей в блоге: 1
05.12.2011, 23:09 4
Цитата Сообщение от slonni Посмотреть сообщение
#ifndef List_stud #define List_stud
#pragma once
1
DU
1492 / 1138 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
05.12.2011, 23:12 5
ну и что, что будет 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  [ТС] 6
Ага, конструктор и вправду сомнительный, хотя это и есть констуктор копирования, точнее должен был им быть , правда в реализании непонятно что я написал, пока удалю его.

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

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

И, наверное таки нужно будет убрать Iterator end(). Всё таки список кольцевой а не линейный.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 05.12.2011, 23:53

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Реклама - Обратная связь
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.