Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "pch.h"
- #include <stdio.h>
- #include <string.h>
- #include <malloc.h>
- #include <math.h>
- #include <time.h>
- #include <stdlib.h>
- const double MAX = 1000;
- typedef struct Link {
- int i; //индекс
- double ves; //вес ребра
- struct Link *next;
- }Link;
- typedef struct Item {
- int name;
- int x;
- int y;
- double d;
- Item *pred;
- Link *first;
- }Item;
- typedef struct Graf {
- int size; //размер вектора
- int n; //количество вершин
- struct Item *head;
- }Graf;
- const char *msgs[] = { "0. Quit", "1. Add_top", "2. Add_rib", "3. Find", "4. Delete", "5. Show", "6. File_in", "7. File_out", "8. Random_Generation" }; // список альтернатив
- const int NMsgs = sizeof(msgs) / sizeof(msgs[0]);
- int dialog(const char *msgs[], int); // выбор номера альтернативы
- int D_Add_top(Graf *);
- int D_Add_rib(Graf *);
- int D_Find(Graf *);
- int D_Delete(Graf *);
- int D_Show(Graf *);
- int D_File_in(Graf*);
- int D_File_out(Graf *);
- int D_Random_Generation(Graf *);
- int insert(Graf *, int, int, int);
- void deletee(Graf *, int, int);
- int FileOpenFlag = 0;
- void rand_gen(Graf *, int, int);
- void deleteall(Graf* graf);
- int(*fptr[])(struct Graf *) = { NULL, D_Add_top, D_Add_rib, D_Find, D_Delete, D_Show, D_File_in, D_File_out, D_Random_Generation };
- int getInt(int *pn)
- {
- const char *errmsg = "";
- int n;
- do {
- puts(errmsg);
- errmsg = "Illegal integer; enter once more";
- n = scanf_s("%d", pn, 4);
- if (n < 0) // обнаружен конец файла
- return 0;
- scanf_s("%*[^\n]"); // игнорирование всех символов до конца строки
- scanf_s("%*c"); // игнорирование символа кнца строки
- } while (n == 0);
- return 1;
- }
- char *getStr()
- {
- char *ptr = (char *)malloc(1);
- char buf[81];
- int n, len = 0;
- *ptr = '\0';
- do {
- n = scanf_s("%80[^\n]", buf, 81);
- if (n < 0) {
- free(ptr);
- ptr = NULL;
- continue;
- }
- else
- if (n)
- {
- len += strlen(buf);
- ptr = (char *)realloc(ptr, len + 1);
- strncat_s(ptr, len + 1, buf, len);
- }
- } while (n > 0);
- scanf_s("%*c"); //удалить последний символ строки
- return ptr;
- }
- int dialog(const char *msgs[], int N)
- {
- const char *errmsg = "";
- int rc;
- int i, n;
- do {
- puts(errmsg);
- errmsg = "You are wrong. Repeate, please!";
- // вывод списка альтернатив
- for (i = 0; i < N; ++i)
- puts(msgs[i]);
- puts("Make your choice: --> ");
- n = getInt(&rc); // ввод номера альтернативы
- if (n == 0) // конец файла - конец работы
- rc = 0;
- } while (rc < 0 || rc >= N);
- return rc;
- }
- void add_info(Item* curr, int name, int x, int y)
- {
- curr->name = name;
- curr->x = x;
- curr->y = y;
- curr->d = MAX;
- curr->pred = NULL;
- }
- int find_notexist_empty(Graf* graf, int name, int x, int y)
- {
- int i, buf = -1;
- for (i = 0; i < graf->size; ++i)
- {
- if (graf->head[i].name == name)
- {
- puts("Top with this name is already exist with");
- return buf;
- }
- if (graf->head[i].name != -1 && graf->head[i].x == x)
- if (graf->head[i].y == y)
- {
- puts("Top with this cords is already exist with");
- return buf;
- }
- if (graf->head[i].name == -1)
- {
- buf = i;
- graf->n++;
- return buf;
- }
- }
- graf->size += 1;
- graf->n += 1;
- graf->head = (Item*)realloc(graf->head, (i + 1) * sizeof(Item));
- graf->head[graf->size - 1].first = NULL;
- buf = graf->size - 1;
- return buf;
- }
- int insert(Graf *graf, int name, int x, int y)
- {
- int p = find_notexist_empty(graf, name, x, y);
- if (p != -1)
- {
- add_info(&(graf->head[p]), name, x, y);
- return 1;
- }
- else
- return 0;
- }
- int D_Add_top(Graf *graf)
- {
- int x, y, rc, n;
- int name;
- puts("Enter name: -->");
- n = getInt(&name);
- if (n == 0)
- return 0;
- puts("Enter x cord: -->");
- n = getInt(&x);
- if (n == 0)
- return 0; // конец файла
- puts("Enter y cord: -->");
- n = getInt(&y);
- if (n == 0)
- return 0; // конец файла
- rc = insert(graf, name, x, y); // вставка элемента в таблицу
- if (rc)
- {
- printf("Top was added with name: %d \n", name);
- }
- return 1;
- }
- void transfer(Item* p_r, Item* p_l, Link* p_e, int i)
- {
- int d;
- double h;
- Link *buf_p_e = p_e->next;
- p_e->next = (Link*)malloc(sizeof(Link));
- d = p_e->i;
- h = p_e->ves;
- p_e->i = i;
- p_e->ves = sqrt(pow((p_r->x - p_l->x), 2) + pow((p_r->y - p_l->y), 2));
- p_e = p_e->next;
- p_e->i = d;
- p_e->ves = h;
- p_e->next = buf_p_e;
- }
- int work_add_pathway(Item* p_r, Item* p_l, int p, int q) {
- if (p_r->first == NULL)
- {
- p_r->first = (Link*)malloc(sizeof(Link));
- p_r->first->i = q;
- p_r->first->next = NULL;
- p_r->first->ves = sqrt(pow((p_r->x - p_l->x), 2) + pow((p_r->y - p_l->y), 2));
- return 1;
- }
- Link *p_e = p_r->first;
- for (; p_e->next != NULL; p_e = p_e->next) {
- if (p_e->i == q) {
- return 2;
- }
- if (p_e->i > q) {
- transfer(p_r, p_l, p_e, q);
- return 1;
- }
- }
- if (p_e->next == NULL) {
- if (p_e->i == q) {
- return 2;
- }
- if (p_e->i > q)
- {
- transfer(p_r, p_l, p_e, q);
- return 1;
- }
- else
- {
- p_e->next = (Link*)malloc(sizeof(Link));
- p_e = p_e->next;
- p_e->i = q;
- p_e->ves = sqrt(pow((p_r->x - p_l->x), 2) + pow((p_r->y - p_l->y), 2));
- p_e->next = NULL;
- return 1;
- }
- }
- return 0;
- }
- int add_rib(Graf* graf, int top1, int top2)
- {
- int i, j, p, q, f1 = 0, f2 = 0;
- for (i = 0; i < graf->size; ++i)
- {
- if (graf->head[i].name == top1)
- {
- p = i;
- f1 = 1;
- }
- }
- if (f1 != 1)
- {
- puts("Top1 hasn't found.");
- return 0;
- }
- for (j = 0; j < graf->size; ++j)
- {
- if (graf->head[j].name == top2)
- {
- q = j;
- f2 = 1;
- }
- }
- if (f2 != 1)
- {
- puts("Top2 hasn't found.");
- return 0;
- }
- int n = work_add_pathway(&(graf->head[p]), &(graf->head[q]), top1, top2);
- if (n == 1)
- return 1;
- if (n == 2)
- return 2;
- return 0;
- }
- int D_Add_rib(Graf* graf)
- {
- int t1, t2;
- int n, l;
- puts("Enter name 1st top: -->");
- n = getInt(&t1);
- if (n == 0)
- return 0;
- puts("Enter name 2nd top: -->");
- n = getInt(&t2);
- if (n == 0)
- return 0;
- l = add_rib(graf, t1, t2);
- if (l==1)
- puts("Rib was created successfully.");
- if (l==2)
- puts("Rib is already exist.");
- return 1;
- }
- void dell_one(Graf *graf, int k)
- {
- Link *p_e = graf->head[k].first;
- while (p_e != NULL)
- {
- Link *p_e_del = p_e;
- p_e = p_e->next;
- free(p_e_del);
- }
- }
- void deletee(Graf *graf, int k, int nm)
- {
- int j, g;
- // удаляем связи
- for (j = 0; j < k; j++)
- {
- if (graf->head[j].first)
- {
- Link *p_e = graf->head[j].first;
- if (p_e->next == NULL)
- {
- if (p_e->i == nm)
- {
- graf->head[j].first = NULL;
- free(p_e);
- }
- }
- else
- {
- if (p_e->i == nm)
- {
- graf->head[j].first = p_e->next;
- p_e->next = NULL;
- free(p_e);
- }
- else
- {
- for (; p_e->next != NULL; p_e = p_e->next)
- {
- if (p_e->next->i == nm)
- {
- Link *p_e_del = p_e->next;
- p_e->next = p_e_del->next;
- p_e_del->next = NULL;
- free(p_e_del);
- }
- if (p_e->next == NULL)
- break;
- }
- }
- }
- }
- }
- for (g = (k + 1); g < graf->size; g++)
- {
- if (graf->head[g].first)
- {
- Link *p_e = graf->head[g].first;
- if (p_e->next == NULL)
- {
- if (p_e->i == nm)
- {
- graf->head[g].first = NULL;
- free(p_e);
- }
- }
- else
- {
- if (p_e->i == nm)
- {
- graf->head[g].first = p_e->next;
- p_e->next = NULL;
- free(p_e);
- }
- else
- {
- for (; p_e->next != NULL; p_e = p_e->next)
- {
- if (p_e->next->i == nm)
- {
- Link *p_e_del = p_e->next;
- p_e->next = p_e_del->next;
- p_e_del->next = NULL;
- free(p_e_del);
- }
- if (p_e->next == NULL)
- break;
- }
- }
- }
- }
- }
- //удаляем вершину
- dell_one(graf, k);
- graf->head[k].first = NULL;
- graf->head[k].name = -1;
- graf->n--;
- }
- int D_Delete(Graf *graf)
- {
- int n, nm, i, k = -1;
- int name;
- puts("Enter top name: -->");
- n = getInt(&name);
- if (n == 0)
- return 0;
- nm = name;
- for (i = 0; i < graf->size; i++)
- {
- if (graf->head[i].name == name)
- k = i;
- }
- if (k != -1)
- {
- deletee(graf, k, nm);
- puts("Ok");
- }
- else
- puts("Top hasn't found");
- return 1;
- }
- void show(Graf *graf)
- {
- if (graf->n == 0)
- puts("Graf wasn't found");
- int i;
- for (i = 0; i < graf->size; ++i)
- {
- if (graf->head[i].name != -1)
- {
- printf("%d (%d;%d) --> ", graf->head[i].name, graf->head[i].x, graf->head[i].y);
- Link *p_e = graf->head[i].first;
- if (p_e)
- {
- for (p_e; p_e->next != NULL; p_e = p_e->next)
- printf("%d (weight = %f), ", p_e->i, p_e->ves);
- printf("%d (weight = %f)\n", p_e->i, p_e->ves);
- }
- else
- {
- printf("Null\n");
- }
- }
- }
- }
- int D_Show(Graf *graf)
- {
- show(graf);
- return 1;
- }
- Graf init()
- {
- Graf *graf = (Graf*)malloc(sizeof(Graf));
- graf->size = 0;
- graf->n = 0;
- graf->head = NULL;
- return *graf;
- }
- int sort(Graf *line)
- {
- int i, n;
- Item *buf = (Item*)malloc(sizeof(Item));
- n = line->size;
- for (i = 0; i < n - 1; i++) //сортировка массива
- {
- for (int j = n - 1; j > i; j--)
- {
- if (line->head[j - 1].d > line->head[j].d)
- {
- buf->name = line->head[j - 1].name;
- buf->x = line->head[j - 1].x;
- buf->y = line->head[j - 1].y;
- buf->d = line->head[j - 1].d;
- buf->pred = line->head[j - 1].pred;
- buf->first = line->head[j - 1].first;
- line->head[j - 1].name = line->head[j].name;
- line->head[j - 1].x = line->head[j].x;
- line->head[j - 1].y = line->head[j].y;
- line->head[j - 1].d = line->head[j].d;
- line->head[j - 1].pred = line->head[j].pred;
- line->head[j - 1].first = line->head[j].first;
- line->head[j].name = buf->name;
- line->head[j].x = buf->x;
- line->head[j].y = buf->y;
- line->head[j].d = buf->d;
- line->head[j].pred = buf->pred;
- line->head[j].first = buf->first;
- }
- }
- }
- return 0;
- }
- Item Extract_min(Graf *line, int size)
- {
- Item *res = (Item*)malloc(sizeof(Item));
- res->name = line->head[0].name;
- res->x = line->head[0].x;
- res->y = line->head[0].y;
- res->d = line->head[0].d;
- res->pred = line->head[0].pred;
- res->first = line->head[0].first;
- line->head[0] = line->head[size - 1];
- line->head[0].name = line->head[size - 1].name;
- line->head[0].x = line->head[size - 1].x;
- line->head[0].y = line->head[size - 1].y;
- line->head[0].d = line->head[size - 1].d;
- line->head[0].pred = line->head[size - 1].pred;
- line->head[0].first = line->head[size - 1].first;
- line->head[size - 1].d = (MAX+1);
- line->head[size - 1].name = -1;
- line->n--;
- sort(line);
- return *res;
- }
- double Dijkstra(Graf *graf, int t1, int t2)
- {
- int n, name, m = 0, i, l = 0, j, x, y, g, p, h, v = -1, q, b, k, f1=0, f2=0;
- double w;
- Item *u = (Item*)malloc(sizeof(Item));
- n = graf->size;
- for (g = 0; g < graf->size; ++g)
- {
- if (graf->head[g].name == t1)
- {
- p = g;
- f1 = 1;
- }
- }
- if (f1 != 1)
- {
- puts("Top1 hasn't found.");
- return -2;
- }
- for (j = 0; j < graf->size; ++j)
- {
- if (graf->head[j].name == t2)
- {
- q = j;
- f2 = 1;
- }
- }
- if (f2 != 1)
- {
- puts("Top2 hasn't found.");
- return -2;
- }
- Graf line = init();
- Graf S = init();
- for (i = 0; i < n; i++)
- {
- name = graf->head[i].name;
- x = graf->head[i].x;
- y = graf->head[i].y;
- if (name != -1)
- insert(&line, name, x, y);
- }
- for (h = 0; h < n; h++)
- {
- name = graf->head[h].name;
- Link *p_e = graf->head[h].first;
- for (; p_e != NULL; p_e = p_e->next)
- {
- k = p_e->i;
- add_rib(&line, name, k);
- }
- }
- line.head[p].d = 0;
- sort(&line);
- while (line.n != 0)
- {
- *u = Extract_min(&line, line.size);
- insert(&S, u->name, u->x, u->y);
- S.head[l].d = u->d;
- S.head[l].pred = u->pred;
- S.head[l].first = u->first;
- S.n++;
- Link *p_l = S.head[l].first;
- for (; p_l != NULL; p_l = p_l->next)
- {
- b = p_l->i;
- for (int z = 0; z < line.size; ++z)
- {
- if (line.head[z].name == b)
- v = z;
- }
- if (v != -1 && (line.head[v].d > (S.head[l].d + p_l->ves)))
- {
- line.head[v].d = S.head[l].d + p_l->ves;
- line.head[v].pred = &S.head[l];
- sort(&line);
- }
- v = -1;
- }
- l++;
- }
- for (int y = 0; y < graf->size; ++y)
- {
- if (S.head[y].name == t2)
- k = y;
- }
- w = S.head[k].d;
- if (w != MAX)
- {
- while (S.head[k].pred)
- {
- printf("%d <--", S.head[k].name);
- S.head[k] = *S.head[k].pred;
- }
- printf("%d\n", S.head[k].name);
- }
- return w;
- }
- int D_Find(Graf* graf) {
- int t1, t2, n;
- double x;
- puts("Enter top1: -->");
- n = getInt(&t1);
- if (n == 0)
- return 0;
- puts("Enter top2: -->");
- n = getInt(&t2);
- if (n == 0)
- return 0;
- x = Dijkstra(graf, t1, t2);
- if (x == -2)
- return 1;
- if (x == MAX)
- {
- printf("There is no path");
- return 1;
- }
- printf("The shortest path from %d to %d: %f", t1, t2, x);
- return 1;
- }
- Graf read_graf(FILE* file) {
- Graf graf = init();
- fseek(file, 0, SEEK_SET);
- int size;
- if (fread(&size, sizeof(int), 1, file) == 1) {
- int i;
- for (i = 0; i < size; ++i) {
- int x, y, name = 0;
- if (fread(&name, sizeof(int), 1, file) == 1 &&
- fread(&x, sizeof(int), 1, file) == 1 &&
- fread(&y, sizeof(int), 1, file) == 1) {
- insert(&graf, name, x, y);
- }
- int k;
- while (fread(&k, sizeof(int), 1, file) == 1) {
- if (k == -1)
- break;
- else
- add_rib(&graf, name, k);
- }
- }
- }
- return graf;
- }
- int D_File_in(Graf *graf) {
- //Путь к файлу
- puts("Put file name!");
- char *graf_path = getStr();
- if (&graf_path == NULL)
- {
- printf("Wrong filename or EOF. ");
- return 0;
- }
- //Открытие файла
- FILE *bfp = NULL;
- fopen_s(&bfp, graf_path, "r+b");
- if (!bfp)
- printf("No file with this path");
- //Работа с файлом
- if (bfp) {
- *graf = read_graf(bfp);
- D_Show(graf);
- fclose(bfp);
- printf("File was cloased");
- }
- else
- printf("Something gone wrong, check access permissions.");
- FileOpenFlag = 1;
- return 1;
- }
- int write_graf(Graf *graf, FILE* file) {
- fseek(file, 0, SEEK_SET);
- if (graf->size == 0)
- return 0;
- fwrite(&graf->size, sizeof(int), 1, file);
- int i;
- const int end_key = -1;
- for (i = 0; i < graf->size; ++i) {
- fwrite(&graf->head[i].name, sizeof(int), 1, file);
- fwrite(&graf->head[i].x, sizeof(int), 1, file);
- fwrite(&graf->head[i].y, sizeof(int), 1, file);
- Link *p_e = graf->head[i].first;
- for (; p_e != NULL; p_e = p_e->next)
- fwrite(&p_e->i, sizeof(int), 1, file);
- fwrite(&end_key, sizeof(int), 1, file);
- }
- return 1;
- }
- int D_File_out(Graf *graf) {
- //Путь к файлу
- puts("Put file name!");
- char* graf_path = getStr();
- if (&graf_path == NULL) {
- printf("Wrong filename or EOF. ");
- return 0;
- }
- //Открытие файла
- FILE* bfp = NULL;
- fopen_s(&bfp, graf_path, "r+b");
- if (!bfp)
- fopen_s(&bfp, graf_path, "w+b");
- //Работа с файлом
- if (bfp) {
- if (!write_graf(graf, bfp))
- printf("Something gone wrong. Start again pls.");
- fclose(bfp);
- printf("File was cloased");
- }
- else
- printf("Something gone wrong, check access permissions.");
- FileOpenFlag = 0;
- return 1;
- }
- int D_Random_Generation(Graf *graf) {
- int k1, k2, n;
- puts("Enter how many tops you want to add: -->");
- n = getInt(&k1);
- if (n == 0)
- return 0;
- puts("Enter how many rib you want to add: -->");
- n = getInt(&k2);
- if (n == 0)
- return 0;
- rand_gen(graf, k1, k2);
- return 1;
- }
- int TF_gen() {
- int p = rand();
- while (p > 10) {
- p /= 10;
- }
- if (p < 6)
- p = 1;
- else
- p = -1;
- return p;
- }
- void rand_gen(Graf *graf, int num1, int num2) {
- int i, n, x, y, name;
- for (i = 0; i < num1; )
- {
- n = 0;
- while (n == 0) {
- x = (rand() * rand() * time(NULL) % (num1 + graf->size))* TF_gen();
- y = (rand() * rand() * time(NULL) % (num1 + graf->size))* TF_gen();
- name = (rand() * rand() * time(NULL) % (num1 + graf->size))* TF_gen();
- n = insert(graf, name, x, y);
- }
- ++i;
- }
- int k1, k2;
- for (i = 0; i < num2; ) {
- n = 0;
- while (n == 0) {
- k1 = 0;
- k2 = 0;
- while (k1 == 0 || k2 == 0)
- {
- k1 = rand() * rand() * time(NULL) % graf->size;
- k2 = rand() * rand() * time(NULL) % graf->size;
- }
- n = add_rib(graf, k1, k2);
- }
- ++i;
- }
- }
- void deleteall(Graf* graf)
- {
- int i;
- for (i = 0; i < graf->size; ++i)
- {
- dell_one(graf, i);
- graf->head[i].pred = NULL;
- }
- free(graf->head);
- graf->head = NULL;
- }
- int main() {
- Graf graf = init();
- int rc;
- while (rc = dialog(msgs, NMsgs))
- if (!fptr[rc](&graf))
- break;
- //if (FileOpenFlag)
- //D_File_out(&graf);
- deleteall(&graf);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement