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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 79, средняя оценка - 4.76
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
06.04.2011, 19:57     Кольцевой односвязный список #1
Доброго времени суток, требуется помощь в создании односвязного кольцевого списка. смог только этот быдлокод:
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
struct stud
{
   int m;
   stud* l;
   stud* r;
};
 
stud* FindLast(stud* firstC)
{
    if(firstC==NULL) return NULL;
    stud *tmp=firstC;
    while(tmp!=firstC)
        tmp=tmp->next;// переходим на последний элемент
    return tmp;//возвращает указатель на сущ. последний элемент
}
void showC(stud* firstC)
{
    while(FindLast(firstC)!=firstC)
    {
        cout<<endl<<firstC->name;
        firstC=firstC->next;
    }
}
void add(stud* &firstC)
{
    if(firstC==NULL)
    {
        cout<<"Input string: ";
        firstC=new stud;
        cin>>firstC->name;
        firstC->next=NULL;
        return;
    }
    stud* p=new stud;
    cout<<"Input string: ";
    cin>>p->name;
    p->next=firstC;
    firstC=p;
    FindLast(firstC)->next=firstC;;//находим последний ссылаем его на новодобавленный
}
void del(stud* &firstC)
{
    if(firstC!=NULL && FindLast(firstC)==NULL){delete firstC; firstC=NULL; return;}
    if(firstC==NULL) {cout<<"\nAlready empty"; Sleep(200); return;}
    stud*p=firstC;
    while(p->next->next!=firstC)
        p=p->next;//нашли предпоследний
    delete p->next;//удалили посл.
    p->next=firstC;//предпоследний->первый
}
Добавлено через 1 час 23 минуты
слегка разобрался с остальными, а вот второй и дальше никак не хочет добавлять
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
stud* FindLast(stud* firstC)
{
    if(firstC==NULL) return NULL;
    stud *tmp=firstC;
    while(tmp!=firstC)
        tmp=tmp->next;// переходим на последний элемент
    return tmp;//возвращает указатель на сущ. последний элемент
}void add(stud* &firstC)
{
    if(firstC==NULL)
    {
        cout<<"Input string: ";
        firstC=new stud;
        cin>>firstC->name;
        firstC->next=NULL;
        return;
    }
    stud* p=new stud;
    cout<<"Input string: ";
    cin>>p->name;
    p->next=firstC;
    firstC=p;
    FindLast(firstC)->next=firstC;//находим последний ссылаем его на новодобавленный
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2011, 19:57     Кольцевой односвязный список
Посмотрите здесь:

кольцевой список C++
C++ Кольцевой список
C++ Кольцевой односвязный список
кольцевой список C++
C++ Кольцевой односвязный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 20:45     Кольцевой односвязный список #2
навскидку:
  1. tmp=tmp->next;обращается к несуществующему полю( и дальше по коду так же обращения к несуществующим полям). Опишите структуру stud.
  2. stud* FindLast(stud* firstC) возвращает указатель на 1 узел списка (судя по названию -требуется вернуть указатель на последний.
  3. void add(stud* &firstC) возможно имелось ввиду void add(stud* firstC) ??
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
06.04.2011, 20:47  [ТС]     Кольцевой односвязный список #3
Цитата Сообщение от Vladimir. Посмотреть сообщение
навскидку:
  1. tmp=tmp->next;обращается к несуществующему полю( и дальше по коду так же обращения к несуществующим полям). Опишите структуру stud.
  2. stud* FindLast(stud* firstC) возвращает указатель на 1 узел списка (судя по названию -требуется вернуть указатель на последний.
  3. void add(stud* &firstC) возможно имелось ввиду void add(stud* firstC) ??
3. если я изменил указатель на 1 элемент - надо сохранить изменение - передаю его по-ссылке.
и структура описана в самом верху
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 20:51     Кольцевой односвязный список #4
3. если я изменил указатель на 1 элемент - надо сохранить изменение - передаю его по-ссылке.
пример вызова функции покажите пожалуйста =)
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
06.04.2011, 20:52  [ТС]     Кольцевой односвязный список #5
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
struct stud
{
   int m;
   stud* l;
   stud* r;
};
stud* FindLast(stud* firstC)
{
    if(firstC==NULL) return NULL;
    stud *tmp=firstC;
    while(tmp!=firstC || tmp->next==NULL)
        tmp=tmp->next;// переходим на последний элемент
    return tmp;//возвращает указатель на сущ. последний элемент
}
void showC(stud* firstC)
{
    if(firstC==NULL){cout<<"\nEmpty";Sleep(500); return;}
    if(firstC->next==NULL){cout<<endl<<firstC->name<<endl;Sleep(900);return;}
    stud* t=firstC;
    while(t!=firstC)
    {
        cout<<endl<<t->name;
        t=t->next;
    }
    system("CLS");
}
void add(stud* &firstC)
{
    if(firstC==NULL)
    {
        cout<<"Input string: ";
        firstC=new stud;
        cin>>firstC->name;
        firstC->next=NULL;
        return;
    }
    stud* p=new stud;
    cout<<"Input string: ";
    cin>>p->name;
    p->next=firstC;
    firstC=p;
    FindLast(firstC)->next=firstC;//находим последний ссылаем его на новодобавленный
}
void del(stud* &firstC)
{
    if(firstC->next==NULL){delete firstC; firstC=NULL; return;}
    if(firstC==NULL) {cout<<"\nAlready empty"; Sleep(200); return;}
    stud*p=firstC;
    while(p->next->next!=firstC)
        p=p->next;//нашли предпоследний
    delete p->next;//удалили посл.
    p->next=firstC;//предпоследний->первый
}
void mainC()
{
    stud* firstC=NULL;
    int sw;
    while(1)
    {
        system ("CLS");
        cout<<"1. Add first\n"<<"2. Delete last\n";
        cout<<"3. Is empty\n"<<"4. Clear"<<endl<<"5. Save to file"<<"\n6. Add to somewhere"<<"\n7. Delete finded\n"<<"0. Exit"<<endl<<endl<<"Make your choose>>>";
        cin>>sw;
        switch(sw)
        {
            case 1: add(firstC); break;
            case 2: del(firstC); break;
            case 3: empty(firstC); break;
            case 4: clear(firstC); break;
            case 5: showC(firstC);break;
            //case 6: addSome(firstC);break;
            case 7: searchL(firstC); break;
            case 0: return; break;
        }
    }
}
 void main()
 {
     int sw;
     cout<<"1. Queue\n2. Stak\n3. Circle list";
     cin>>sw;
     switch(sw)
     {
        case 1: mainQ();break;
        case 2: mainS();break;
        case 3: mainC();break;
     }
 }
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
07.04.2011, 14:09     Кольцевой односвязный список #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
понятно.
Основынм элементом связного списка является узел. Узел хранит полезные данные (в нашем случае это фамилии студентов) и обеспечивает связь со следующим элементом. Узел удобно описывать как структуру. Например такую:
C++
1
2
3
4
struct nodes{
    char data[str_size];
    nodes* next;
};
где str_size максимальная длинна символьного массива.

Отлично, едем дальше. У нас стоит задача построить кольцевой односвязный список. Описываем класс с минимальным набором функций - добавление/удаление узла, просмотр данных узла (без возможности редактирования), навигация по списку. вместе с указателем на голову(начало) списка получим минимальный комплект. Для удобства добавим счетчик узлов и возможность перехода к первому узлу. Имеем следующее:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class my_list{
    public:
        void insert(char* str); //Вставляет запись за текущей.
        void del_next();        //Удаляет запись за текущей.
        void go_next();         //Переходит к следующей записи.
        void go_first();        //Переходит к первой записи.
        const char* show();     //возвращает указатель на хранимые данные.
        int  size();            //Возвращает количество элементов в списке.
 
        my_list();
        ~my_list();
    private:
        nodes*  head;           //начало списка.
        nodes*  position;       //активная (текущая) запись.
        int     count;          //количество элементов списка.
        
        void free();            //удаляет все элементы, освобождает память
};
реализация методов my_list:
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
my_list::my_list(){
    head = NULL;
    count = 0;
    go_first();
}
 
my_list::~my_list(){
    free();
}
 
//public:
 
void my_list::insert(char* str){
//Вставляет запись за текущей.
    nodes* new_node = new nodes;
    strcpy(new_node->data,str);
    if(position != NULL){
        new_node->next = position->next;
        position->next = new_node;
    }else{
        new_node->next = new_node;
        position = head = new_node;
    }
    count++;
}
 
void my_list::del_next(){
//Удаляет запись за текущей.
    if (position != NULL){
        nodes* tmp = position->next;
        position->next = position->next->next;
        
            if(tmp == head) head = tmp->next;
        delete tmp;
    }
    count--;
}
 
void my_list::go_next(){
//Переходит к следующей записи.
    if (position != NULL)
        position = position->next;
}
 
void my_list::go_first(){
//Переходит к первой записи.
    position = head;
}
 
const char* my_list::show(){
//возвращает указатель на хранимые данные.
    if(position != NULL)
        return position->data;
    else
        return NULL;
}
 
int my_list::size(){
//Возвращает количество элементов в списке.
    return count;
}
 
// private:
 
void my_list::free(){
//удаляет все элементы, освобождает память
    go_first();
    while(head->next != head) del_next();
    del_next(); 
}


на этом описание класса связного списка завершено
примеры обращения из main:
примеры
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
int main(){
    char name1[] = "Иванов";
    char name2[] = "Петров";
    char name3[] = "Сидоров";
    //создание списка студентов:
    my_list student_list;
    
    //добавляем записи в список.
    student_list.insert(name1);
    student_list.insert(name2);
    student_list.insert(name3);
 
    //вывод списка на консоль:
    student_list.go_first();
    for(int i = 1;i<=student_list.size();i++){
        std::cout<<student_list.show()<<std::endl;
        student_list.go_next();
    }
 
    //удаление первого элемента из трех:
    student_list.go_first();
    student_list.go_next();
    student_list.go_next();
    student_list.del_next();
    
    //вывод отредактированного списка на консоль:
    student_list.go_first();    
    for(int i = 1;i<=student_list.size();i++){
        std::cout<<student_list.show()<<std::endl;
        student_list.go_next();
    }
    
return 0;
}


И в завершение необходимые для работы хидеры и константы:
C++
1
2
3
#include<iostream>
#include<string.h>
const int str_size=256;
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
24.04.2011, 23:09     Кольцевой односвязный список #7
Только начал изучать C++, есть вопросов пару.
реализация методов my_list:
собственно что это? часть класса? или это уже вне класса пишется?
C++
1
2
3
4
5
my_list::my_list(){
        head = NULL;
        count = 0;
        go_first();
}
что значит эта часть?

Что значат такие строки
C++
1
2
new_node->next
position->next
конкретно интересует ->

Будут еще вопросы пока что - это

Добавлено через 33 минуты
а еще
методы разве не внутри структуры должны быть?

Добавлено через 41 минуту
Начал все по плотнее разглядывать! В общем или я где-то накосячил, или вы!

У меня список выводится таким образом
Например 5 элементов:
1 - 5 - 4 - 3 - 2
Например 3:
1 - 3 - 2
Например 4:
1 - 4 - 3 - 2
Поняли к чему я?

Быть может я куда-то не туда смотрю?

Я честно говоря скопипастил и попробовал переписать. В итоге и моя версия и ваша "глючные".

Еще кое что....
Не могли бы вы поподробнее объяснить что делает оператор -> и как им пользоваться. Для чего структура nodes ? За что отвечают ее элементы?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 00:53     Кольцевой односвязный список #8
VladSharikov, Nodes - узел списка.
Оператор -> - косвенная адрессация. Доступ к элементам через указатель.
mylist::mylist() - консруктор по-умолчанию.

Методы объявлены в классе, но описываются вне класса. Это хорошая практика для нешаблонных классов.
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
25.04.2011, 01:55     Кольцевой односвязный список #9
Цитата Сообщение от ForEveR Посмотреть сообщение
консруктор


Окей, а можно поподробнее на счет -> ?
Ощущение у меня такое, что он просто сдвигает вправо но видимо ощущение ложное.

Допустим рассмотрим метод go_next()
C++
1
2
3
4
5
void my_list::go_next(){
//Переходит к следующей записи.
        if (position != NULL)
                position = position->next;
}
как блин?! объясните пожалуйста что и как тут происходит ! пошагово !
Во первых ради интереса, а во вторых думаю это нужно знать обязательно! Так же нужно сделать go_previous();! Не пишите как, хочу додуматься как, просто тыкните в какую сторону думать!

Вот я и разбираюсь в этом коде, чтобы сделать свою задачу!
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 07:54     Кольцевой односвязный список #10
VladSharikov, Окей. Функция класса go_next не принимающая параметров.
position - указатель на Nodes.
Если указатель не нулевой - то ему присваивается его поле next. position->next - обращение к члену структуры через указатель, можно так же (*position).next
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
25.04.2011, 08:06     Кольцевой односвязный список #11
ForEveR, тоесть .... хорошо. А чему равно поле next? Где именно это написано? Как он определил что в поле next 2 , а здесь 1?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 09:35     Кольцевой односвязный список #12
VladSharikov, next это указатель. У него есть адрес. Код как следует просмотрите.
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
25.04.2011, 16:18     Кольцевой односвязный список #13
C++
1
position = position->next
что конкретно делает такой код?
эквивалентная запись такая?
C++
1
position = (*int).next;
в каком то хелпе прочитал. не пойму что конкретно делает эта строка.

position - текущая позиция? значит этой командой текущей позиции присваиваем указатель на предыдущий элемент? (или на следующий?!)
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 16:21     Кольцевой односвязный список #14
VladSharikov, Следующий. Кстати записи отнюдь не эквивалентны. И вообще вторая запись некорректна.
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
25.04.2011, 16:38     Кольцевой односвязный список #15
Нет нет ! Это вопрос на счет второй записи.
значит корректна будет
C++
1
position = (*position).next;
?

бррр... я в упор не могу "представить" себе этот переход к следующему! И от этого не понимаю весь код блин!

Добавлено через 13 минут
C++
1
2
3
4
5
6
7
8
9
void my_list::go_next(){
//Переходит к следующей записи.
        if (position != NULL) {
                position = position->next;
        } else {
            cout << "End of list...\nPress any key..." << endl;
            getch();
        }
}
дописал кое-что... ну это так! метод проб и ошибок, ибо не до конца понял.
Если position(указатель на структуру) не NULL то переместить указатель но структуру на следующий, так? А если NULL то написать "Конец листа".
Почему не вывелась надпись?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 16:44     Кольцевой односвязный список #16
VladSharikov, Возможно position никогда не становится NULL... Вообще если список кольцевой - то это абсолютно логично.
По сути position == NULL, когда в списке нет ничего. В других случаях оно не может быть равным NULL.
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
25.04.2011, 16:49     Кольцевой односвязный список #17
Также.. подумал тут...
чтобы вернутся на несколько элементов назад(n) нужна такая функция.

C++
1
2
3
4
5
6
7
 void my_list::back_step(int step){
//Переходит на step записей назад
        go_first();
        for(int i = 1; i <= step; i++) {
            position = position->next;
        }
}
так?

Добавлено через 48 секунд
2 #16. И вправду. Что-то я не о том думаю! логично!

Добавлено через 1 минуту
Вопрос из той же оперы? Возможно ли узнать где мы находимся сейчас в данный момент? Или мы всегда находимся в конце списка?
И да... с массивами было проще
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.04.2011, 16:50     Кольцевой односвязный список #18
VladSharikov, Вообщем на несколько элементов назад вернуться невозможно, ибо список односвязный. Исключительно на несколько элементов вперед. НО если учитывать что он кольцевой, тогда теоретически возможно прохождение всего списка до головы и проход далее. Но проход назад в односвязном списке по идее не соответствует его концепции. А функция да, верная по-моему.

position это и есть место где мы находимся в данный момент...
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
25.04.2011, 17:31     Кольцевой односвязный список #19
А зачем переход до головы, если можно просто присвоить position = head? тоесть начало списка?

А в функции моей нужно исправить steps на (count - steps) и тогда поидее она будет верной и будет работать, как думаете?

Добавлено через 3 минуты
Хотя count это ведь общее количество элементов списка... Тоесть мы получается с конца делаем три шага назад и указываем на этот элемент(например 10 элементов было, стали указывать на 7 элемент, даже если я находился на 6 позиции. Все равно в итоге будем указывать на 7 позицию.) и не важно на какой позиции мы находились, я прав?

Добавлено через 15 минут
Все таки как узнать где мы находимся в данный момент?
Где мы должны находится в данный момент? по моему или в начале, или в конце. Посередине вроде никак?

к position не обратится , ибо он private, да еще и указатель!
Как?!

Добавлено через 15 минут
Кстати! При добавлении элемента в список таким образом
C++
1
2
3
4
5
6
7
8
9
boy1[] = "ruslan";
boy2[] = "vlad";
boy3[] = "viktor";
boy4[] = "nikolay";
 
guys.insert(boy1);
guys.insert(boy2);
guys.insert(boy3);
guys.insert(boy4);
Происходит ошибка... В общем выводит так.

1 - 4 - 3 - 2
Код
ruslan
nikolay 
victor 
vlad
код вывода такой
C++
1
2
3
4
5
6
7
    // вывод списка на экран guys
    guys.go_first();
    for(int i = 1;i<=guys.size();i++){
        cout << guys.show() << endl;
        guys.go_next();
    }
    cout << endl;
Код самого insert
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void my_list::insert(char* str){
//Вставляет запись за текущей.
        nodes* new_node = new nodes;
        strcpy(new_node->data,str);
        if(position != NULL){
                new_node->next = position->next;
                position->next = new_node;
        } else {
                new_node->next = new_node;
                position = head = new_node;
        }
        count++;
}
Что не так, не знаете? найти не могу!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2011, 18:12     Кольцевой односвязный список
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Delya
0 / 0 / 0
Регистрация: 25.04.2011
Сообщений: 3
25.04.2011, 18:12     Кольцевой односвязный список #20
можете помочь примерно с такой задачей?
Yandex
Объявления
25.04.2011, 18:12     Кольцевой односвязный список
Ответ Создать тему

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

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