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

Разобрать устройство двусвязного списка - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Наследование http://www.cyberforum.ru/cpp-beginners/thread760190.html
Доброе дня, прошу вас помочь в решение данной задачи. Написать программу, демонстрирующую работу с объектами двух типов: Т1 и Т2, для чего создать систему соответствующих классов. Каждый объект...
C++ Работа с подматрицей Программа формирует матрицу из случайных чисел, в программу вводятся размеры подматрицы этой матрицы (счет идет от левого верхнего угла), программа определяет минимальный элемент в введенной... http://www.cyberforum.ru/cpp-beginners/thread760171.html
C++ Шаблон массива указателей на заголовки списков
Вот само задание: "Шаблон структуры данных - массив указателей на заголовки списков. Элемент списка содержит указатель на строку (При включении последним предусмотреть ограничение длины текущего...
Удалить из массива элементы встречающиеся менее трёх раз C++
Дан массив целочисленный N. Удалить из массива элементы встречающиеся менее трёх раз, и вывести размер полученного массива и его содержимое. Добавлено через 34 минуты #include<iostream>...
C++ Создать массив структур. Дана информация о пяти комнатах в общежитии. (borland) http://www.cyberforum.ru/cpp-beginners/thread760135.html
Создать массив структур и выполнить задание согласно своему варианту. 3. Дана информация о пяти комнатах в общежитии. Структура имеет вид: фамилии, номер комнаты, факультет, площадь. Вывести...
C++ Организация вывода списка При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val - предназначен для хранения элемента списка, n - для указателя на структуру,... подробнее

Показать сообщение отдельно
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
13.01.2013, 11:56
помогал в свое время с тем же вопросом вот
код
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
#include <iostream>
using namespace std;
 
struct Elem
{
    Elem *prev, *next;
    char *data;
};
 
typedef Elem* List;
 
List create() //создать список
{
    List l=new Elem; //выделяем память для списка
    l->data=""; //делаем пустую строку
    l->next=0; //указатель на следующий нулевой
    l->prev=0; //указатель на предыдущий - нулевой
    return l;
    /*сформировали заглавное звено списка*/
}
 
void add(List l, char* _data) //добавить елем
{
    if (!l->next) //если список пуст
        l->next->next=l->next->prev=l->next=new Elem; //создаем элемент и сразу зацикливаем его сам на себя (присваивание справа на лево)
    else
    {
        Elem* old_tail=l->next->prev; //сохраняем старый
        l->next->prev=l->next->prev->next=new Elem; //выделяем память (это будет новый хвост),хвост привязываем к последнему элементу, а потом к первому
        old_tail->next->prev=old_tail; //привязываем старый хвост к новому
        l->next->prev->next=l->next; //привязываем голову к хвосту
    }
    l->next->prev->data=_data; //заполняем хвост (выполняется в любом случае)
}
 
bool is_empty(List l) //пустой?
{
    return !l->next; //ну тут ясно. если указатель на следующий нулевой, вернем правду иначе ложь
}
 
int  how_many_with_equal_neighbours(List l) //сколько эл-тов с одинаковыми соседями?
{
    if (!l->next) return 0;
    Elem* tail=l->next->prev;//сохранили хвост
    int i=0;
    do {
     l=l->next;
     i+=(strcmp(l->next->data , l->prev->data)?0:1);
    }
    while ((l!=tail));
    /* эквивалентно:
    while (l!=tail)
    {
        if (!strcmp(l->next->data, l->prev->data) i++;
        l=l->next;
    }*/
    return i;
}
 
bool equal_to_next_exists(List l) //существует ли элемент равный следующему?
{
    if (!l->next) return false;
    Elem* tail=l->next->prev;
    while ((l=l->next) && strcmp(l->data,l->next->data) && l!=tail);
    /*эквивалентно:
    while (l!=tail)
    {
        l=l->next;
        if (!strcmp(l->data,l->next->data)) break;
    }*/
    return l!=tail || strcmp(l->data,l->next->data); //если не дошли до конца, или же если дошли, но последний равен первому
}
 
void inverse_between(List l, char* el) //переставить в обратном порядке между первым и последним вхождениями
{
    if (l->next==l->next->prev) return; //если список зациклен сам на себе, то там один элемент. если список пуст то оба указателя равны нулю
    Elem *first=0, *last=0, *tail=l->next->prev;
    while (l!=tail)
    //нахождение первого и последнего вхождения:
    {
        l=l->next; //переходим к след. элементу
        if (!strcmp(l->data,el)) //если нашли строку
            if (!first) first=l; //если первое вхождение не найдено, то первое вхождение = этому звену
            else last=l; //иначе последнее вхождение = этому звену
    }
    if (!last) return; //если нету последнего вхождения, то елемент встречается один раз, так что выходим
    char* temp;
    while (first!=last && first->next!=last) //1е условие - если у нас нечетное кол-во эл-тов между first и last, 2е условие - если четное.
    {
        //передвигаем указатели навстречу друг другу
        first=first->next;
        last=last->prev;
        //меняем элементы местами
        temp=first->data;
        first->data=last->data;
        last->data=temp;
    }
}
 
void write(List l, std::ostream& out) //написать в поток (cout по умолчанию, но можно использовать файловые потоки)
{
    Elem* tail=l->next->prev;
    while (l!=tail)
    {
        l=l->next;
        out<<l->data<<'\n';
    }
}
 
int main()
{
    printf("Fill the list with 10 elements:\n");
    List list=create();
    add(list,"mm");
    for (int i=1; i<=4; i++)
    {
        char* el=new char[255];
        //если объявим снаружи цикла, адрес строки будет всегда один и тот же, и все элементы списка будут одинаковыми
        scanf("%s",el); //читаем с консоли
        add(list,el); //добавляем в список
    }
    printf("\nYour list:\n");
    write(list,cout); //выводим список в консоль
    if (!is_empty(list))
    {
        printf("Count of elements with equal neighbours: %d\n", how_many_with_equal_neighbours(list));
        printf("Element that equals to his right neighbour "+(equal_to_next_exists(list))?"exists":"does not exist\n");
        printf("Input string: ");
        char* str=new char[255];
        scanf("%s",str);
        inverse_between(list,str);
        printf("\n\nIf at least two \"%s\" are in list, the elements between first and last \"%s\" will be inverted",str,str);
        write(list,cout);
    }
    else printf("The list is empty");
    system("pause");
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.