Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
1

Удаление нулевых элементов из матрицы

01.04.2017, 20:49. Показов 784. Ответов 17
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Есть матрица, которая реализована в виде двумерного связного списка, и состоит из значений 0,1,2. Нужно реализовать сохранение нулевых элементов в непарных столбцах и соответственно удаление в парных. В результате должна выйти зубчатая матрица.
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
#include <iostream>
#include <cstdlib>
#include<ctime>
struct list2d
{
    list2d *next, *prev, *down;
    int data;
 
    list2d() : next(), prev(), down(), data()
    {
    }
};
 
void print_list2d(struct list2d* head)
{
    struct list2d *current_row = head, *current_cell = NULL;
    while (current_row)
    {
        current_cell = current_row;
        while (current_cell)
        {
            std::cout << current_cell->data << " ";
            current_cell = current_cell->next;
        }
        std::cout << std::endl;
        current_row = current_row->down;
    }
}
 
void delete_list2d(struct list2d* head)
{
    struct list2d *current_row = head, *current_cell = NULL, *to_delete;
    while (current_row)
    {
        current_cell = current_row->next;
        while (current_cell)
        {
            to_delete = current_cell;
            current_cell = current_cell->next;
            delete to_delete;
        }
        to_delete = current_row;
        current_row = current_row->down;
        delete to_delete;
    }
}
 
int main()
{
    unsigned int size;
 
    std::cout << "Enter a matrix size: " << std::endl;
    std::cin >> size;
 
    std::cout << "Matrix: " << std::endl;
    struct list2d* current_row = NULL, *head = new struct list2d();
    current_row = head;
 
    for (unsigned int i = 0; i < size; ++i)
    {
        struct list2d *current_cell = current_row;
        for (unsigned int j = 0; j < size; ++j)
        {
            current_cell->data = rand() % 3;
            if (j != size - 1)
            {
                current_cell->next = new struct list2d();
                current_cell->next->prev = current_cell;
                current_cell = current_cell->next;
            }
        }
 
        if (i != size - 1)
        {
            current_row->down = new struct list2d();
            current_row = current_row->down;
        }
    }
 
    struct list2d *str1 = head, *str2 = head->down;
    while (str2)
    {
        struct list2d *cell1 = str1->next, *cell2 = str2->next;
        while (cell1)
        {
            cell1->down = cell2;
            cell1 = cell1->next;
            cell2 = cell2->next;
        }
        str1 = str2;
        str2 = str2->down;
    }
 
    print_list2d(head);
    delete_list2d(head);
 
    system("Pause");
    return EXIT_SUCCESS;
}
Собственно сохранение нулевых элементов в непарных столбцах и соответственно удаление в парных не выходит сделать. Буду благодарен за подсказки или примеры.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.04.2017, 20:49
Ответы с готовыми решениями:

Найти сумму положительных элементов матрицы А, количество нулевых элементов матрицы B
• Даны матрицы A, B. Найти сумму положительных элементов матрицы А, количество нулевых элементов...

Удаление нулевых элементов
Доброе время суток, помогите написать программу - Из массива заданного пользователем, удалить...

Найти произведение элементов матрицы в строках не содержащих нулевых элементов
Дана вещественная прямоугольная матрица. Определить: Произведение элементов в тех строках, которые...

Найти сумму положительных элементов матрицы и количество нулевых элементов
Есть матрица (7,4). Найти сумму положительных элементов матрицы и количество нулевых элементов....

17
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
01.04.2017, 21:49 2
Тут есть одна тонкость. Пусть например одна из строк матрицы имеет вид 1 0 0 2, и нам нужно удалить первый ноль (так как он стоит в чётном столбце). Но если мы его удалим, то оставшаяся часть строки сдвинется влево, и в результате второй ноль встанет на место первого. Вопрос: нужно ли его тоже удалить, поскольку он теперь стоит в чётном столбце, или нет, поскольку изначально он стоял в нечётном? Лично я склоняюсь ко второму варианту.
0
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
01.04.2017, 22:01  [ТС] 3
Не нужно, так как он был в нечётном
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
01.04.2017, 22:11 4
Предлагаю решить задачу в два прохода. На первом проходе помечаем каждый нулевой элемент в чётных столбцах, присваивая ему например 42. На втором проходе удаляем все элементы, равные 42.

При удалении нужно аккуратно перенастроить все указатели, в том числе указатель вышестоящего элемента.
Поскольку у нас есть указатель вниз, но нет указателя вверх, это нужно учитывать при обходе матрицы. Сначала удаляем помеченные элементы из верхней строки. Затем делаем цикл по строкам, от верхней до предпоследней, но удаляем не сам элемент, а нижестоящий.
0
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
01.04.2017, 22:19  [ТС] 5
Интересный вариант, спасибо
а не могли бы код набросать?если не трудно конечно.
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
01.04.2017, 22:27 6
Не трудно, но лень. По крайне мере сегодня.
Там много мелкой возни с указателями, но принципиально ничего трудного нет.
0
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
01.04.2017, 22:32  [ТС] 7
а в плане памяти предложенный вами алгоритм как?
я ведь не сказал, основная цель задания - экономное хранение в памяти матриц и экономное использование памяти
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
01.04.2017, 22:34 8
Цитата Сообщение от TRRx Посмотреть сообщение
а в плане памяти предложенный вами алгоритм как?
Ну, мы же не создаём элементы, а удаляем. Так что дополнительная память расходоваться не будет.
Причём удаляем физически, с помощью delete, так что память будет только освобождаться.
1
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
01.04.2017, 23:14  [ТС] 9
а как при первом проходе определить чётная строка или нет?
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
01.04.2017, 23:17 10
Цитата Сообщение от TRRx Посмотреть сообщение
а как при первом проходе определить чётная строка или нет?
Наверное всё же столбец.

Проще всего завести счётчик столбцов (например k). Если k%2 == 0, то столбец чётный, если == 1, то нечётный (или наоборот, смотря как считать столбцы, с нуля или с единицы).
1
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
02.04.2017, 14:16  [ТС] 11
В теории всё вроде ясно, а на практике не выходит
Буду благодарен, если найдёте завтра время и силы помочь, а то я уже 2 дня сижу и всё безуспешно, а в понедельник сдавать.

Добавлено через 13 часов 19 минут
-up

Добавлено через 1 час 24 минуты
-up
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
02.04.2017, 14:43 12
Первая часть - помечаем элементы для удаления
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
list2d *p, *q;
int j;
 
for (p = head, j = 1; p; p = p->next, j++)
{
    if (j % 2 == 1) // пропускаем нечётные столбцы
        continue;
 
    for (q = p; q; q = q->down)
    {
        if (q->data == 0)
            q->data = -1;
    }
}
Добавлено через 18 минут
Вторая часть (концепция немного изменилась)
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
// удаляем помеченные элементы, не меняя указатели down
for (list2d *p = head; p; p = p->down)
{
    list2d *q = p;
    while (q)
    {
        list2d *next = q->next;
        if (q->data == 42)
            // удаяем элемент из двусвязного списка,
            // не обращая внимания на указатель q->down
            remove_element(q);
        q = next;
    }
}
 
// Обновляем связи down между строками
for (p = head; p->down; p = p->down)
{
    list2d *q1 = p;
    list2d *q2 = p->down;
    for (; q1; q1 = q1->next)
    {
        q1->down = q2;
        if (q2)
            q2 = q2->next;
    }
}
Функцию remove_element напишите сами, она удаляет элемент из одномерного двусвязного списка.
0
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
02.04.2017, 15:00  [ТС] 13
Спасибо, а удаление через delete или меняя указатели?
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
02.04.2017, 15:23 14
Цитата Сообщение от TRRx Посмотреть сообщение
удаление через delete или меняя указатели?
И
0
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
12.04.2017, 15:49  [ТС] 15
-up
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
12.04.2017, 15:58 16
Цитата Сообщение от TRRx Посмотреть сообщение
-up
Появились новые вопросы?
0
0 / 0 / 1
Регистрация: 29.11.2015
Сообщений: 99
12.04.2017, 15:59  [ТС] 17
Скорее, не новые, а старые. Не выходит функция remove
0
1272 / 1029 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
12.04.2017, 16:07 18
Цитата Сообщение от TRRx Посмотреть сообщение
Не выходит функция remove
Это не вопрос.

Добавлено через 4 минуты
Большая коллекция решенных задач
Там есть в том числе удаление элементов из двусвязного списка.
0
12.04.2017, 16:07
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.04.2017, 16:07
Помогаю со студенческими работами здесь

Определить количество нулевых элементов в тех строках матрицы, которые не содержат положительных элементов
Дана целочисленная прямоугольная матрица. Определить: 1) Количество нулевых элементов в тех...

Удалить из матрицы те строки, для которых количество ненулевых элементов больше количества нулевых элементов в строке
помогите пожалуйста написать вот такую задачу: Дана целочисленная квадратная матрица порядка 5....

Удаление нулевых строк/ столбцов из матрицы
Добрый день! помогите написать код, желательно на С Тема: многомерные массивы Выделить память...

Удаление нулевых элементов
Здравствуйте. Нужно написать программу. Задан размер массива целых чисел и значения его элементов....


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru