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

Односвязный список - C++

Восстановить пароль Регистрация
 
iparafin
0 / 0 / 0
Регистрация: 15.12.2010
Сообщений: 17
22.11.2011, 17:23     Односвязный список #1
Задание: Необходимо реализовать односвязный список. В качестве информационной части элемента выступают координаты точки. Необходимо реализовать следующие функции: добавление нового элемента в конец списка, очистка памяти от эл-ов списка, и функция вычисления площади многоугольника, вершинами которого являются точки в списке. В последнем случае функция предполагает гарантию того, что в списке больше двух элементов и эти точки образуют выпуклый многоугольник.В качестве проверки взять квадрат с левым углом (0,1) и правым нижним (1,0).
Осталось только написать формулу вычисления площади , не могу справиться. помогите!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
 
lab3.cpp
 
#include "stdafx.h"
#include "Spisok.h"
#include <iostream>
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    chudoSpisok spis;
    spis.init();
    cout<<"square is "<<spis.square()<<endl;
    spis.remove_list();
    return 0;
}
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
     Spisok.h
#ifndef MY_SPISOK
#define MY_SPISOK
 
class chudoSpisok
{
    typedef struct {
    int x,y;
    }POINT;
 
    typedef POINT ETYPE; 
    struct elem { ETYPE data; 
    elem *next;
    int *x, *y;
    };
 
    elem *p, *q;
    int *x, *y;
    int n;
 
    chudoSpisok* next;
 
public: 
     void init ();
     void add(int x,int y);
     void remove_list();
     float square();
};
#endif
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
Spisok.cpp
#include "stdafx.h"
#include "Spisok.h"
#include <iostream>
using namespace std;
 
 
void chudoSpisok::add(int x,int y)
    {
    q=new elem;
    q->data.x=x;
    q->data.y=y;
    q->next=p;
    p=q;
    }
 
    void chudoSpisok::init()
     {
         p=NULL;
        do{
        cout<<"Enter number of angles:";
        cin>>n;
        }while(n<3);
        int x;int y;
        for(int i=1;i<=n;i++){
            cout<<"Enter coordinates of "<<i<<" point:";
            cin>>x>>y;
            add(x,y);
        }
    }
 
     void chudoSpisok:: remove_list()
     {
        while(q->next != NULL){
            p=q;
            q=q->next;
            delete p;
        }
        q=q->next;
        delete p; 
    }
 
     [B]float chudoSpisok:: square()[/B]
     {
         elem *A; elem *B; elem *C ; 
         float S=0.0f;
         
         A=p ;
         B=p->next ;
         C=B->next ;
 
     while (B !=NULL &&  C !=NULL) {
             //S += square();
         A=B;
         B=C;
         C=C->next;
     }
    
    return S;
     }
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.11.2011, 17:23     Односвязный список
Посмотрите здесь:

Односвязный список C++
C++ Односвязный список
C++ Односвязный список
C++ Односвязный список
Односвязный список C++
Односвязный список C++
Односвязный список C++
C++ Односвязный список
C++ Односвязный список
C++ Односвязный список
C++ Односвязный список

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
golatin
263 / 220 / 42
Регистрация: 12.10.2011
Сообщений: 318
Завершенные тесты: 1
22.11.2011, 18:38     Односвязный список #2
Если многоугольник выпуклый, то площадь считается, как сумма треугольников из какой-либо точки.
Т.е. если последовательность {0,1,2,....,N}, то S=S012+S023+...+S0(N-1)N.

Сложнее доказать, что многоугольник выпуклый:
1)из каждой точки надо провести прямую, параллельную проходящей через две соседние точки, и сравнить - все ли точки с одной стороны или нет? (доказать выпуклость => найти площадь)
или
2)найти для каждой из точек многоугольника площадь подобным образом и сравнить - площадь одна и та же? (найти площади => доказать выпуклость)
iparafin
0 / 0 / 0
Регистрация: 15.12.2010
Сообщений: 17
06.12.2011, 08:25  [ТС]     Односвязный список #3
Ничего не понял.
Лучше примерно набросайте как это выглядит в коде. у меня с теорией не очень и визуалочкой тоже)
golatin
263 / 220 / 42
Регистрация: 12.10.2011
Сообщений: 318
Завершенные тесты: 1
06.12.2011, 18:16     Односвязный список #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Формула треугольника по трем координатам:

http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{\Delta abc}=\frac{1}{2}\begin{vmatrix} {x}_{a}  {y}_{a}  1 \\  {x}_{b}  {y}_{b}  1 \\  {x}_{c}  {y}_{c}  1 \end{vmatrix}=\frac{\begin{vmatrix}{x}_{a}({y}_{b}-{y}_{c})+{x}_{b}({y}_{c}-{y}_{a})+{x}_{c}({y}_{a}-{y}_{b})\end{vmatrix}}{2}=\frac{\begin{vmatrix}\\ ({x}_{b}-{x}_{a})({y}_{c}-{y}_{a})-({x}_{c}-{x}_{a})({y}_{b}-{y}_{a})\end{vmatrix}}{2}

Пишешь функцию по вычислению площади треугольника, что-то типа такого
C++
1
2
3
4
float square_of_triangle(float x_A,float y_A,float x_B,float y_B,float x_C,float y_C)
{
    return fabs((x_B-x_A)*(y_C-y_A)-(x_C-x_A)*(y_B-y_A))/2;
}
Затем вторую функцию для вычисления суммы площадей треугольников, в качестве точек передаешь элементы односвязного списка, т.е.:


poly={(0;0),(0;1),(1;1),(2;0),(1;-1)}

http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(0;0)}={S}_{(0;0),(0;1),(1;1)}+{S}_{(0;0),(1;1),(2;0)}+{S}_{(0;0),(2;0),(1;-1)}=0.5+1.0+1.0=2.5

Затем, тоже самое вычисляешь для следующей точки (0;1):

http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(0;1)}={S}_{(0;1),(1;1),(2;0)}+{S}_{(0;1),(2;0),(1;-1)}+{S}_{(0;1),(1;-1),(0;0)}=0.5+1.5+0.5=2.5

Затем, тоже самое вычисляешь для следующей точки (1;1):

http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(1;1)}={S}_{(1;1),(2;0),(1;-1)}+{S}_{(1;1),(1;-1),(0;0)}+{S}_{(1;1),(0;0),(0;1)}=1.0+1.0+0.5=2.5
.......
и так до точки (1;-1)

http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(1;-1)}=...=2.5

Если http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(0;0)}={S}_{poly(0;1)}={S}_{poly(1;1)}=...={S}_{poly(1;-1)}=2.5, то данный многоугольник выпуклый и его площадь равна http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(0;0)}.
Если, хотя бы, в одном месте http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{{a}_{i}}\neq {S}_{{a}_{j}}, то данный многоугольник не является выпуклым(пример: poly={(0;0),(2;2),(1;0),(2;-2)} => http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(0;0)}={S}_{(0;0),(2;2),(1;0)}+{S}_{(0;0),(1;0),(2;-2)}=1.0+1.0=2.0, но http://www.cyberforum.ru/cgi-bin/latex.cgi?{S}_{poly(2;2)}={S}_{(2;2),(1;0),(2;-2)}+{S}_{(2;2),(2;-2),(0;0)}=2.0+4.0=6.0>2.0 ).
iparafin
0 / 0 / 0
Регистрация: 15.12.2010
Сообщений: 17
07.12.2011, 08:49  [ТС]     Односвязный список #5
ёк макарёк...
Yandex
Объявления
07.12.2011, 08:49     Односвязный список
Ответ Создать тему
Опции темы

Текущее время: 21:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru