Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
slonni
0 / 0 / 0
Регистрация: 07.12.2009
Сообщений: 18
#1

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

05.12.2011, 22:42. Просмотров 1516. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2011, 22:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Кольцевой односвязный список (C++):

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

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

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

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

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

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

5
DU
1483 / 1129 / 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

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

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

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

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

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

И, наверное таки нужно будет убрать Iterator end(). Всё таки список кольцевой а не линейный.
0
05.12.2011, 23:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2011, 23:53
Привет! Вот еще темы с ответами:

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

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

Реализовать кольцевой список. Как закольцевать список обычный? - C++
Помогите пожалуйста реализовать кольцевой список. Я так понимаю, он может быть двусвязным и односвязным? Меня интересует односвязный....

Сформировать список из 10 книг, используя динамическую структуру данных односвязный список - C++
друзья спасайте Сформировать список из 10 книг, используя динамическую структуру данных односвязный список С++


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

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

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