Сформировать список ребер графа по заданной матрице инцидентности - C++ - Ответ 4735889

#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
struct spis
{
    int nom;
    int vst;
    int vnd;
    spis *aft;
    spis *unt;
}
;
 
 
int **input_kb(int *n)
{
    int i,j,**mas;
    system("cls");
    cout<<"Введите колличество вершин  ";
    cin>>*n;
    if (*n<1) {system("cls");cout<<"Вы ввели неверное число вершин\nбб";getch();exit(1);}
    mas=new int*[*n];
    for (i=0;i<*n;i++)  
        mas[i]=new int[*n];
    system("cls");
    cout<<" Ввод матрицы инцидентности:\n";
    for (i=0;i<*n;i++)
        for (j=0;j<*n;j++)
            {
                cout<<"Введите элемент "<<i<<" : "<<j<<"   ";
                cin>>mas[i][j];
            }
system("cls");
return mas;
}
int **input_fl(int *n)
{
    int i,j,**mas;
    char wron[255];
    FILE *f;
    system("cls");
    cout<<"Введите имя файла, он должен находиться в папке данной программы\n";
    cin>>wron;
    system("cls");
    if ((f=fopen(wron,"r"))==NULL)
    {
        cout<<"Не удается открыть файл";
        getch();
        exit(1);
    }
    else
    {fscanf(f,"%d",n);
    mas=new int*[*n];
    for (i=0;i<*n;i++)  
    mas[i]=new int[*n];
    for (i=0;i<*n;i++)
        for (j=0;j<*n;j++)
            fscanf(f,"%d",&mas[i][j]);
    }
    fclose(f);
return mas;
}
spis *create_spis(int *n,int **mas,int *no)
{
   int i,j,k;
   spis *first,*an,*head;
   for (i=0;i<*n;i++)    
        for (j=i;j<*n;j++)
            if (mas[i][j]!=0)
        for (k=0;k<mas[i][j];k++)
        {
             if (*no==0)
                 {
                 first=new spis;
                 head=first;
                 head->unt=NULL;
                 }
             else {
                   first->aft=new spis;
                   an=first;
                   first=first->aft;
                   first->unt=an;
                  }
             first->nom=++*no;
             first->vst=i;
             first->vnd=j;
             first->aft=NULL;       
         }
return head;
}
 
spis *lat(spis *head)
{   
    spis *first;
    first=head;
    if (first!=NULL)
    while(first->aft!=NULL)
        first=first->aft;
    return first;
}
int koll_vo(spis *head)
{
    int k=0;
    spis *first;
    first=head;
    while (first!=NULL)
    {   
        first=first->aft;
        k++;
    }
    return k;
}
 
void viv_org_sp(spis *head)
{
    spis *first=head;
    cout<<"\n\nСписок ребер:";
    while (first!=NULL)
    {
    cout<<"\nномер ребра:  "<<first->nom<<"; номера вершин соединенных ребром: "<<first->vst<<" "<<first->vnd;   
    first=first->aft;
    }       
}
int ser_min(int *n,spis *head,int numb)
{
    int *sm,i;
    spis *first;
    first=head;
    sm=new int[*n];
    for (i=0;i<*n;i++)
         sm[i]=0;
    for (i=0;i<numb;i++)
    {
       ++sm[first->vst];
       ++sm[first->vnd];
       first=first->aft;
    }
    int min=sm[0],imin=0;
    for (i=0;i<*n;i++)
        if (sm[i]>min)
     {
         min=sm[i];
         imin=i;
     }
delete[]sm;
return imin;
}
spis *delete_re(spis *hed,int no,int min,spis *later)
{
    int i;
    spis *todel,*first;
    first=hed;
for (i=0; i<no;i++)
    if ((first->vst==min) || (first->vnd==min))
    {
        
        if ((first==hed) && (first==later))
        {
            todel=hed;
            delete todel;
            hed=NULL;
        }
        else
        if (first==hed)
        {
            todel=hed;
            if (hed!=later)
            {   
            hed=hed->aft;
            hed->unt=NULL;
            }
            if (first!=later)first=first->aft;
            delete todel;
        }
        else
        if(first==later)
        {
            todel=first;
            later=first->unt;
            first->unt->aft=NULL;
            delete todel;
            
        }
        else
        {
            first->unt->aft=first->aft;
            first->aft->unt=first->unt;
            todel=first;
            if (first!=later)first=first->aft;
            delete todel;
            
        }
    }
    else first=first->aft;
return hed;
}
 
void viv_sp_af_fl(spis *head,int min)
{
    spis *first;
    first=head;
    FILE *f;
    if ((f=fopen("output.txt","w"))!=NULL)
    {
    fprintf(f,"Номер вершины с максимальной степенью = %d",min);
    if (head!=NULL)
    {
    fprintf(f,"\nСписок ребер без инцидентных вершине с минимальной степенью:");
    while (first!=NULL)
    {
      fprintf(f,"\nномер ребра:  %d; номера вершин соединенных ребром: %d  %d\n",first->nom,first->vst,first->vnd);  
      first=first->aft;
    }   
    }
    else fprintf(f,"\nСписок удалён полностью");
    }
fclose(f);
}
 
void cleaning(int **mas,spis *head)
{
    spis *todel;
    delete[]mas;
    while (head!=NULL)
    {
      todel=head;
      head=head->aft;
      delete todel;
    }
}
void output_mat(int **mas,int n)
{
    int i,j;
    cout<<"Матрица инцидентности:";
    for (i=0;i<n;i++)
    {
        cout<<"\n";
        for (j=0;j<n;j++)
            cout<<mas[i][j]<<"\t";
    }
}
//Функция проверки матрицы инцидентности
//В функцию входят указатель на массив; переменная n, отвечающая за количество вершин 
void chk_mass(int **mas,int n)
{
int i,j;
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            if ((mas[i][j]!=mas[j][i]) | (mas[i][j]<0) | (mas[i][j]>1))
            {system("cls");cout<<"Матрица инцидентности введена неверно";getch();exit(1);}
 
            
 
}
//Функция вывода системных сообщений
int sys_mess()
{
    cout<<"данная программа принимает матрицу инцидентности\nсоздает список ребер графа, по заданной матрице\nпоказывает номер вершины с максимальной степенью\nудаляет из списка ребра инцидентные вершине с максимальной степенью\nвыводит результаты на экран,а так же в файл";
        getch();
    system("cls");
return 0;
}
void rename(spis *head)
{
    spis *first=head;
    int h=1;
    while (first!=NULL)
    {
     first->nom=h++;
     first=first->aft;
    }
}
 
//Основная функция(main)
int main()
{
   setlocale(LC_ALL, "rus");
   int n,**mas,no=0,min;
   char vod;
   sys_mess(); 
   cout<<"Для ввода матрицы из файла введите     f\nДля ввода матрицы с клавиатуры введите k\n";
   cin>>vod; 
   switch (vod)
       {
   case 'k': mas=input_kb(&n); break;
   case 'f': mas=input_fl(&n); break;
   default: {cout<<"Неверный ввод\nбб";getch();exit(1);}
       }
   chk_mass(mas,n);
   output_mat(mas,n);
   spis *hed,*later;
   hed=create_spis(&n,mas,&no);
   later=lat(hed);
   viv_org_sp(hed);
   min=ser_min(&n,hed,no);
   cout<<"\n\nНомер вершины с максимальной степенью = "<<min<<"\n";
   hed=delete_re(hed,no,min,later);
   later=lat(hed);
   if (hed!=NULL) rename(hed);
   if (hed!=NULL) viv_org_sp(hed);
   else cout<<"\nСписок полностью удалён";
   viv_sp_af_fl(hed,min);
   cleaning(mas,hed);
return 0;
}