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

Структура, граф. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
GAME
 Аватар для GAME
22 / 22 / 3
Регистрация: 31.10.2009
Сообщений: 199
23.12.2009, 23:56     Структура, граф. #1
Вопщем задание такое.
Написать прогу , которая находит наименьший путь из одной точки в другую .

Изначально было дано 5 точек .
[IMG]http://***********/F/i056.***********/0912/55/8d0ecf40be54.jpg[/IMG]

Вопщем они соидинены стрелочками. Неважно как . (ну я нарисовал так) Главное чтобы из каждой точки можно было попасть в каждую. (Можно не на прямую).
Вот. у стрелочки соединяющей 2 точки - есть длина пути . целое число . Ну вопщем для начала нужно сделать функцию , которая бы искала наименьший путь между выбранными точками .

------
Изначально будет дано только 5 точек . расстояния должен ввести юзер .
Классы не знаем ещё , так что структуру заюзать.щас сам подумаю , напишу , что получилось .
Интересны ваши мысли . Т.к. надо сделать будет и ещё добавление , удаление точек .

Добавлено через 21 минуту
Вот. Объявить структуры мона так.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct Point
{
    unsigned int *num;
    char *name;
    Point *next;
};
 
typedef struct Road
{
    unsigned int *l;
    Point *from;
    Point *to;
    Road *next;
};
Point - "точка" , где num - номер точки , name - имя . (В кружочке поимя номера имя будет ещё)
Road - "стрелочка" , где *from -откуда, *to - куда , *l - длинна пути . и указатели на следущую.

Пока сё)

Добавлено через 27 минут
Так. Вот функция добавления точки. Добавление в конец - по принципу очереди .

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
Point *add_point(Point *p,unsigned int num,char *name)
{
    if (!p) 
    {
        p=add_memP();
        p->num=num_write(num);
        p->name=str_write(name);
        p->next=NULL;
    }
    else 
    {
        p->next=add_point(p->next,num,name);        
    }   
    return p;
}
 
Point *add_memP(void)
{
    return (Point *) malloc(sizeof(Point));
}
 
char *str_write(char *s)
{
    char *p;
    p=(char *) malloc(strlen(s)+1);
    strcpy(p,s);
    return p;
}
 
unsigned int *num_write(unsigned int n)
{
    unsigned int *p;
    p=(unsigned int *) malloc(sizeof(n));
    *p=n;
    return p;
}

Тут с помощью add_memP , выделяем место в памяти под новую структуру , и с помощью num_write и str_write записываем в это место номер и имя .

Добавлено через 26 минут
Вот. функция добавления дороги(стрелочки О_о)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Road *add_road(Road *p,Point *f,Point *t,unsigned int l)
{
    if (!p) 
    {
        p=add_memR();
        p->l=num_write(l);      
        p->from=f;
        p->to=t;
        p->next=NULL;
    }
    else 
    {
        p->next=add_road(p->next,f,t,l);        
    }   
    return p;
}


Вот значиться весь код который пока есть .

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
//
 
#include "stdafx.h"
#include <conio.h>
#include <stdio.h>
#include <windows.h>
 
 
typedef struct Point
{
    unsigned int *num;
    char *name;
    Point *next;
};
 
typedef struct Road
{
    unsigned int *l;
    Point *from;
    Point *to;
    Road *next;
};
 
 
Point *add_point(Point *p,unsigned int num,char *name);
Road *add_road(Road *p,Point *f,Point *t,unsigned int l);
unsigned int *num_write(unsigned int n);
char *str_write(char *s);
void dialog();
Point *add_memP(void);
Road  *add_memR(void);
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    dialog();
    return 0;
}
 
 
void dialog()
{
    Point *ptp;
    Road *ptr;
    char name[20];
    unsigned int num;
    int n;
    ptp=NULL;
    ptr=NULL;
    n=0;
    while(n!=5)
    {
        scanf("%s",name);
        scanf("%i",&num);
        ptp=add_point(ptp,num,name);
        n++;
    }
    ptr=add_road(ptr,ptp,ptp->next,5);
    Sleep(1);
}
 
 
Point *add_point(Point *p,unsigned int num,char *name)
{
    if (!p) 
    {
        p=add_memP();
        p->num=num_write(num);
        p->name=str_write(name);
        p->next=NULL;
    }
    else 
    {
        p->next=add_point(p->next,num,name);        
    }   
    return p;
}
 
Road *add_road(Road *p,Point *f,Point *t,unsigned int l)
{
    if (!p) 
    {
        p=add_memR();
        p->l=num_write(l);      
        p->from=f;
        p->to=t;
        p->next=NULL;
    }
    else 
    {
        p->next=add_road(p->next,f,t,l);        
    }   
    return p;
}
 
 
 
Point *add_memP(void)
{
    return (Point *) malloc(sizeof(Point));
}
 
Road *add_memR(void)
{
    return (Road *) malloc(sizeof(Road));
}
 
char *str_write(char *s)
{
    char *p;
    p=(char *) malloc(strlen(s)+1);
    strcpy(p,s);
    return p;
}
 
unsigned int *num_write(unsigned int n)
{
    unsigned int *p;
    p=(unsigned int *) malloc(sizeof(n));
    *p=n;
    return p;
}
Ну это так. Вобщем главное - заданы 5 точек и пути ( как на рис. напр.) и расстояния . Точек может быть мноогоо. Не обяз пять - это как пример

Дайте алгоритм хотябы , или примерный код программы которая ищет кротчайший путь между двумя точками.

Добавлено через 17 часов 37 минут
Ап теме !!!! помогите пазязя )))) Алгоритм то вроде и простой а реализация , хз ... ничего адекватного в голову пока не пришло .

Добавлено через 6 часов 26 минут
Хэй !!! помогайте мну))) ну никак функцию поиска кротчайшего пути не написать =(((

Вот удаление написал.

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
Point *del_point(Point *p)
{
    free(p->name);
    free(p->num);
    p->name=NULL;
    p->num=NULL;
    return p;
}
 
Road *del_road(Road *p, Point *pp)
{
    if(p->from==pp || p->to==pp)
    {
        free(p->l);
        p->l=NULL;
        p->from=NULL;
        p->to=NULL;
    }
    if(p->next) p->next=del_road(p->next,pp);
    return p;
}
 
Point *trash_outP(Point *p)
{
    if (p->name && p->next)
    {
        p->next=trash_outP(p->next);
    }
    else
    {
        if(!p->name && p->next) p=p->next;      
    }
    if(p->next) p->next=trash_outP(p->next);
    if(!p->next) return p;
}
 
Road *trash_outR(Road *p)
{
    if(p->l)
    {
        if(p->next)
        {
            if(!p->next->l) p->next=trash_outR(p->next->next);
            else p->next=trash_outR(p->next);
        }
        else return p;
    }
    else
    {
        p=trash_outR(p->next);
    }
    return p;   
}
По 2е функции удаления (дороги и точки)
И по 2е функции выброса пустых мест после удаления (из середины напр или из начала).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2009, 23:56     Структура, граф.
Посмотрите здесь:

C++ Граф
Граф C++
C++ Граф
Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл C++
C++ Структура, доступная из всех файлов проекта ("глобальная" структура)
C++ В текстовом файле структура – информация о компьютерах. Структура с полями: название, стоимость.
C++ Структура DateTime, битовая структура
C++ Структура «База», сущности «Универсам» и «Продукты», структура «Товар»

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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