Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
52 / 56 / 34
Регистрация: 14.03.2014
Сообщений: 776
1

Сортировка структуры

20.10.2015, 17:04. Просмотров 470. Ответов 13
Метки нет (Все метки)

Всем привет. Нужна помощь при сортировке. Во время сортировки углов нужно так же отсортировать их координаты чтобы каждая координата соответствовала своему углу до сортировки. У самого получился какой то бред с выходом за границы массива. double b[], double c[] массивы хранящие координаты x и y соответственно, а double *a массив хранящий углы.

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
#include<iostream>
#include<stack>
#include<algorithm>
#include<windows.h>
#include<cmath>
#include<cstdlib>
 
using namespace std;
const double PI = 3.14159265;
 
//============================================//
 
struct hull
{
    int x;
    int y;
};
 
 
void Sort(double *a, double b[], double c[], const int n)
{
    
    int k = 0, u = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            
            if (a[j] > a[i])
            {
                double l = a[i];
                a[i] = a[j];
                a[j] = l;
 
            }
            else
                k++;
            
        }
        u++;
    }
    cout <<"k ="<< k - u << endl;
    for (int i = 0; i < n; i++)
    {
        if ((i + k - u) >(n - 1))
            k = fabs(k - i + 1);
        else
            k = k - u;
        cout << a[i] << " координата х " << b[i + k] << endl;
    }
    /*for (int j = 0; j < n; j++)
    {
        cout << "number " << j << " ";
        cout << a[j] << " " << b[j] <<  endl;
 
    }  */
 
}
int main()
{
    setlocale(0, "");
    int N;
    std::cout << "Введите количество точек: ";
    std::cin >> N;
 
    hull *ps = new hull[N];
 
    for (int i = 0; i < N; i++)
    {
        std::cin >> (ps + i)->x;
        std::cin >> (ps + i)->y;
 
    }
    double y0 = ps->y;
    double x0 = ps->x;
 
    for (int i = 0; i < N; i++)
    {
        if ((ps + i)->y < y0)
        {
            y0 = (ps + i)->y;
            x0 = (ps + i)->x;
 
        }
 
    }
    double *x = new double[N];
    double *y = new double[N];
 
    double *ps2 = new double[N];
    for (int i = 0; i < N; i++)
    {
        ps2[i] = atan2(((ps + i)->y) - y0, ((ps + i)->x) - x0) * 180 / PI;
        x[i] = (ps + i)->x;
        y[i] = (ps + i)->y;
 
    }
    for (int i = 0; i < N; i++)
        cout << ps2[i] << endl;
 
    Sort(ps2, x, y, N);
 
    /*int j;
    for (j = 0; j < N; j++)
    {
    cout << "number " << j << " ";
    cout << ps2[j] << endl;
 
    } */
 
 
    delete[] y;
    delete[] x;
 
    delete[] ps2;
    delete[] ps;
    system("pause");
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.10.2015, 17:04
Ответы с готовыми решениями:

Структуры. Сортировка массива структуры
Здравствуйте! В чем моя ошибка?? Нужно отсортировать массив структуры по возрастанию среднего...

Структуры. Сортировка
Всем привет! Подскажите пожалуйста, если я создал структуру с тремя компонентами:...

Сортировка структуры
Отсортировать структуру по желанию пользователя. 1. Вывести на экран книги в алфавитном порядке с...

Сортировка структуры
Привет всем. Возникла проблема с лабой никак не могу понять, что от не так. Задание звучит так....

13
Dimension
580 / 448 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
20.10.2015, 17:12 2
пузырьковую сортировку напишите и когда обмениваете углы там же меняйте и координаты
0
469 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
20.10.2015, 17:17 3
А почему просто не сделать структуру, содержащую в себе все элементы?
C++
1
2
3
4
5
6
struct Name
{
    double angle;
    double x;
    double y;
};
И по полю Угол(angle) произвести сортировку структур.
0
52 / 56 / 34
Регистрация: 14.03.2014
Сообщений: 776
20.10.2015, 17:26  [ТС] 4
SuperKir
т.е тогда нужна в этом:
C++
1
2
double *x = new double[N];
double *y = new double[N];
отпадет?
0
Dimension
580 / 448 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
20.10.2015, 17:33 5
нет ,хранить данные то надо ,для структуры выделить придется
0
469 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
20.10.2015, 17:37 6
Dimension, что, простите?
Senarist, тебе нужно будет только N структур задать, не более. Дальше уже заполнять их поля
C++
1
2
3
Name *Param = new Name[N]; //name в данном случае имя структуры
for (int i=0; i<N; i++)
    cin >> Param[i].angel >> Param[i].x >> Param[i].y;
Ну а дальше обычная сортировка (тем же пузырьком), где буферной переменной будет переменная типа стуктуры.
0
52 / 56 / 34
Регистрация: 14.03.2014
Сообщений: 776
20.10.2015, 17:41  [ТС] 7
C++
1
hull *ps = new hull[N];
Так вот для структуры. То что выше это просто чтобы удобнее с координатами было работать.

Добавлено через 3 минуты
SuperKir Эмм.. так мне ток надо координаты вводить а угол считается на основе самой нижней точки по y, и каждой последующей. Обход грэхэма пытаюсь реализовать.
0
469 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
20.10.2015, 17:47 8
Senarist, Так, давай тогда по порядку. (Честно, не охото разбирать весь код).

1. Вводим кол-во точек
2. Выделяем память под N координат (x,y) этих точек
3. Заполняем координаты.

Что происходит далее?
0
52 / 56 / 34
Регистрация: 14.03.2014
Сообщений: 776
20.10.2015, 18:01  [ТС] 9
Далее берем самую первую структуру и начинаем искать минимальную из всех по y.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
double y0 = ps->y;
    double x0 = ps->x;
 
    for (int i = 0; i < N; i++)
    {
        if ((ps + i)->y < y0)
        {
            y0 = (ps + i)->y;
            x0 = (ps + i)->x;
 
        }
 
    }
Далее ищем углы из этой точки во все остальные: (ps2 хранит углы в градусах)
C++
1
2
3
4
double *ps2 = new double[N];
    for (int i = 0; i < N; i++)
    {
        ps2[i] = atan2(((ps + i)->y) - y0, ((ps + i)->x) - x0) * 180 / PI;
далее соответствующие координаты заносим в массив:
C++
1
2
x[i] = (ps + i)->x;
y[i] = (ps + i)->y;
Хотя наверное можно и было оставаться со структурой

Далее
Начинаем сортировку
C++
1
Sort(ps2, x, y, N);
Сортируем по возрастанию угла:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Sort(double *a, double b[], double c[], const int n)
{
    
    //int k = 0, u = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            
            if (a[j] > a[i])
            {
                double l = a[i];
                a[i] = a[j];
                a[j] = l;
 
            }
Но поскольку мы углы отсортировали, их координаты (соответствующие углу) стали не в том порядке. Вот в это проблема. Чтобы по углу мы могли знать координаты.
0
Dimension
580 / 448 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
20.10.2015, 18:16 10
в 12 строчке когда начинаете переставлять углы ,точно так же координаты переставляйте
C++
1
2
3
4
5
6
7
if (a[j] > a[i])
{
 swap(a[i],a[j]);
 swap(b[i],b[j]);
  swap(c[i],c[j]);
                
}
1
469 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
20.10.2015, 18:18 11
Цитата Сообщение от Senarist Посмотреть сообщение
Сортируем по возрастанию угла:
Ладно, судя по коду, очень много лишнего, ну да ладно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
if (a[j] > a[i])
{
    double l = a[i];
    a[i] = a[j];
    a[j] = l;
    double buf = x[i];
    x[i] = x[j];
    x[j] = buf;
    buf = y[i];
    y[i] = y[j];
    y[j] = buf;
}
1
52 / 56 / 34
Регистрация: 14.03.2014
Сообщений: 776
20.10.2015, 18:28  [ТС] 12
SuperKir Спасибо. Можете конкретно что я лишнего сделал. Буду редактировать
0
469 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
20.10.2015, 18:47 13
Цитата Сообщение от Senarist Посмотреть сообщение
SuperKir Спасибо. Можете конкретно что я лишнего сделал. Буду редактировать
Зачем вводить лишние массивы x,y, если у нас есть готовые структуры, чем мы и можем воспользоваться.
Не особо понял, что и зачем ты сортировал, поэтому убрал лишнее (для себя, оставил только сортировку)

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
#include "iostream"
 
using namespace std;
const double PI = 3.14159265;
 
//============================================//
 
struct hull
{
    int x;
    int y;
};
 
 
void Sort(double *a, hull *b, const int n)
{
 
    int k = 0, u = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
 
            if (a[j] > a[i])
            {
                double l = a[i];
                a[i] = a[j];
                a[j] = l;
                hull buf = b[i];
                b[i] = b[j];
                b[j] = buf;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << " координаты х,y: [" << b[i].x << "," << b[i].y << "]" << endl;
}
 
int main()
{
    setlocale(0, "");
    int N;
    cout << "Введите количество точек: ";
    cin >> N;
 
    hull *ps = new hull[N];
 
    for (int i = 0; i < N; i++)
        cin >> ps[i].x >> ps[i].y;
 
    double x0 = ps->x;
    double y0 = ps->y;
 
    for (int i = 0; i < N; i++)
    {
        if (ps[i].y < y0)
        {
            y0 = ps[i].y;
            x0 = ps[i].x;
        }
 
    }
 
    double *ps2 = new double[N];
    for (int i = 0; i < N; i++)
        ps2[i] = atan2(ps[i].y - y0, ps[i].x - x0) * 180 / PI;
 
    for (int i = 0; i < N; i++)
        cout << ps2[i] << endl;
 
    Sort(ps2, ps, N);
 
    delete[] ps2;
    delete[] ps;
 
    system("pause");
    return 0;
}
Да и это можно сократить
1
52 / 56 / 34
Регистрация: 14.03.2014
Сообщений: 776
20.10.2015, 22:19  [ТС] 14
SuperKir а можешь подсказать если знаешь: как проверить образуют ли 3 точки левый поворот? Это обход Грэхема (если вдруг знаешь такое). Везде описан алгоритм который вроде понятен но как проверять какой поворот не ясно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.10.2015, 22:19

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Сортировка и структуры
Задача : &quot;Имеется список 10 политических деятелей. Каждый из 100 опрошенных называет трех...

Сортировка структуры
Есть структура struct v{ string one; string two; int three; }; Подскажите как...

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

сортировка структуры.
Возникла проблема при сортировке. возможно в коде есть и моя ошибка. ну суть в том, что он не...


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

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

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