Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.51/67: Рейтинг темы: голосов - 67, средняя оценка - 4.51
vaselo
19 / 19 / 5
Регистрация: 17.10.2010
Сообщений: 247
1

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

06.04.2011, 19:57. Просмотров 12119. Ответов 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
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;//находим последний ссылаем его на новодобавленный
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2011, 19:57
Ответы с готовыми решениями:

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

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

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

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

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

23
Vladimir.
158 / 158 / 48
Регистрация: 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) ??
1
vaselo
19 / 19 / 5
Регистрация: 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 элемент - надо сохранить изменение - передаю его по-ссылке.
и структура описана в самом верху
0
Vladimir.
158 / 158 / 48
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 20:51 4
3. если я изменил указатель на 1 элемент - надо сохранить изменение - передаю его по-ссылке.
пример вызова функции покажите пожалуйста =)
0
vaselo
19 / 19 / 5
Регистрация: 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;
     }
 }
0
Vladimir.
158 / 158 / 48
Регистрация: 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;
3
VladSharikov
22 / 22 / 7
Регистрация: 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 ? За что отвечают ее элементы?
0
ForEveR
В астрале
Эксперт С++
7995 / 4754 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
25.04.2011, 00:53 8
VladSharikov, Nodes - узел списка.
Оператор -> - косвенная адрессация. Доступ к элементам через указатель.
mylist::mylist() - консруктор по-умолчанию.

Методы объявлены в классе, но описываются вне класса. Это хорошая практика для нешаблонных классов.
1
VladSharikov
22 / 22 / 7
Регистрация: 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();! Не пишите как, хочу додуматься как, просто тыкните в какую сторону думать!

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

position - текущая позиция? значит этой командой текущей позиции присваиваем указатель на предыдущий элемент? (или на следующий?!)
0
ForEveR
В астрале
Эксперт С++
7995 / 4754 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
25.04.2011, 16:21 14
VladSharikov, Следующий. Кстати записи отнюдь не эквивалентны. И вообще вторая запись некорректна.
0
VladSharikov
22 / 22 / 7
Регистрация: 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 то написать "Конец листа".
Почему не вывелась надпись?
0
ForEveR
В астрале
Эксперт С++
7995 / 4754 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
25.04.2011, 16:44 16
VladSharikov, Возможно position никогда не становится NULL... Вообще если список кольцевой - то это абсолютно логично.
По сути position == NULL, когда в списке нет ничего. В других случаях оно не может быть равным NULL.
0
VladSharikov
22 / 22 / 7
Регистрация: 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 минуту
Вопрос из той же оперы? Возможно ли узнать где мы находимся сейчас в данный момент? Или мы всегда находимся в конце списка?
И да... с массивами было проще
0
ForEveR
В астрале
Эксперт С++
7995 / 4754 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
25.04.2011, 16:50 18
VladSharikov, Вообщем на несколько элементов назад вернуться невозможно, ибо список односвязный. Исключительно на несколько элементов вперед. НО если учитывать что он кольцевой, тогда теоретически возможно прохождение всего списка до головы и проход далее. Но проход назад в односвязном списке по идее не соответствует его концепции. А функция да, верная по-моему.

position это и есть место где мы находимся в данный момент...
0
VladSharikov
22 / 22 / 7
Регистрация: 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++;
}
Что не так, не знаете? найти не могу!
0
Delya
1 / 1 / 0
Регистрация: 25.04.2011
Сообщений: 3
25.04.2011, 18:12 20
можете помочь примерно с такой задачей?
1
25.04.2011, 18:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2011, 18:12

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

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

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


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

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

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