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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Наследование http://www.cyberforum.ru/cpp-beginners/thread760190.html
Доброе дня, прошу вас помочь в решение данной задачи. Написать программу, демонстрирующую работу с объектами двух типов: Т1 и Т2, для чего создать систему соответствующих классов. Каждый объект должен иметь идентификатор (в виде произвольной строки символов) и одно или несколько полей для хранения состояния объекта (один класс является потомком другого). Клиенту (функции main) должны быть...
C++ Работа с подматрицей Программа формирует матрицу из случайных чисел, в программу вводятся размеры подматрицы этой матрицы (счет идет от левого верхнего угла), программа определяет минимальный элемент в введенной подматрице и присваивает его значение всем элементам вне подматрицы. Простите если криво объяснила. #include <iostream> #include <locale.h> #include <iomanip> #include <math.h> #include <ctime> ... http://www.cyberforum.ru/cpp-beginners/thread760171.html
C++ Шаблон массива указателей на заголовки списков
Вот само задание: "Шаблон структуры данных - массив указателей на заголовки списков. Элемент списка содержит указатель на строку (При включении последним предусмотреть ограничение длины текущего списка и переход к следующему)". Я решил сначала сделать сам шаблон списка и узла, перегрузил операторы вывода списка на экран, а также ввода/вывода узла списка. Все отлично работает. //шаблон...
Удалить из массива элементы встречающиеся менее трёх раз C++
Дан массив целочисленный N. Удалить из массива элементы встречающиеся менее трёх раз, и вывести размер полученного массива и его содержимое. Добавлено через 34 минуты #include<iostream> #include<Windows.h> #include "time.h" #include "stdlib.h" using namespace std; void main() {
C++ Создать массив структур. Дана информация о пяти комнатах в общежитии. (borland) http://www.cyberforum.ru/cpp-beginners/thread760135.html
Создать массив структур и выполнить задание согласно своему варианту. 3. Дана информация о пяти комнатах в общежитии. Структура имеет вид: фамилии, номер комнаты, факультет, площадь. Вывести данные о комнатах по заданному факультету, а также количество комнат на этом факультете.
C++ Организация вывода списка При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val - предназначен для хранения элемента списка, n - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание: typedef struct nd { float val; ... подробнее

Показать сообщение отдельно
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 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");
}
 
Текущее время: 12:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru