首页 > 代码库 > c++的自学笔记

c++的自学笔记

2024-11-08 19:48:01   202人阅读

     好久好久没有写代码，写博客了，今天把学习笔记直接粘贴在上面

#include<stdio.h>

#include<string.h>
#include<stdlib.h>
#define MAXVEX 40
#define INFINITY  20000 
typedef struct
{
int No;//序号
char name[20];//名字
int X;//显示图地点的横坐标
int Y;//显示图地点的纵坐标
char introduce[100];//介绍
}Vextype;//顶点类型


typedef struct
{
int arc[MAXVEX][MAXVEX];//边集合
Vextype vex[MAXVEX];//顶点集合
int vexnum;//顶点数
int arcnum;//边数
}AdjMatrix;//邻接矩阵


typedef struct ArcNode
{
int adjvex;
int weight;
    struct ArcNode *next;
}ArcNode;//邻接表的结点
typedef struct VertexNode
{
int No;//序号
char name[20];//名字
int X;//显示图地点的横坐标
int Y;//显示图地点的纵坐标
char introduce[100];//介绍
ArcNode *head;
}VertexNode;//邻接表的表头顶点
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum;
int arcnum;
}AdjList;//邻接表




int D[MAXVEX+1];
int visited[MAXVEX+1];
int a[1000][1000]={0};//记录所有路径


int Locate(AdjMatrix *G,char name[]);
int Create1(AdjMatrix *G);
void Display1(AdjMatrix *G);
void save(AdjMatrix *G);
AdjMatrix * load(AdjMatrix *G);
void Search(AdjMatrix *G);
void Add(AdjMatrix *G);
void Dell(AdjMatrix *G);
void Dijkstra(AdjMatrix *G,int start,int end,int dist[],int path[][MAXVEX]);
void Shortcut(AdjMatrix *G);
void Prim(AdjMatrix *G,int start);
void MiniSpan(AdjMatrix *G);
//根据地名确定地点序号
int Locate(AdjMatrix *G,char name[])
{
int i;
for(i=1;i<=G->vexnum;i++)
{
if(!strcmp(name,G->vex[i].name))
return i;
}
return -1;
}



int Create1(AdjMatrix *G)
{
int i,j,k,weight;
char place[20];
printf("输入西邮西区导游图的景点数和线路数:\n");
scanf("%d,%d",&G->vexnum ,&G->arcnum );
fflush(stdin);
for(i=1;i<=G->vexnum ;i++)
for(j=1;j<=G->vexnum ;j++)
G->arc [i][j]=INFINITY;//初始化
printf("输入西邮西区导游图%d个景点信息:\n",G->vexnum );
for(i=1;i<=G->vexnum ;i++)
{
printf("No%d个景点:\n",i);
G->vex [i].No =i;
printf("景点名:");
scanf("%s",G->vex [i].name );
fflush(stdin);
printf("景点位置:");
scanf("%d,%d",&G->vex [i].X ,&G->vex [i].Y );
fflush(stdin);
printf("输入景点简介:");
scanf("%s",G->vex [i].introduce );
}
printf("输入导游图中%d条路线:\n",G->arcnum );
    for(k=0;k<G->arcnum ;k++)
{
printf("No%d条路线:\n",k+1);
printf("起始景点:");
scanf("%s",place);
i=Locate(G,place);
printf("\n终点景点:");
scanf("%s",place);
j=Locate(G,place);
printf("\n距离:");
scanf("%d",&weight);
G->arc [i][j]=weight;
G->arc [j][i]=weight;
}
save(G);
return 1;
}


void Display2(AdjMatrix *G)//显示图的布局
{
int i,j,k,l,m=0,n=0;
printf("\t\t\t西邮西区布局图\n\n");
for(i=1;i<=G->vexnum;i++)
{
if(m<=G->vex [i].X )
m=G->vex [i].X;
if(n<=G->vex [i].Y )
n=G->vex [i].Y;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
l=0;
for(k=1;k<=G->vexnum ;k++)
  if(i==(G->vex [k].X) &&j==(G->vex [k].Y))
  {
 printf("%s",G->vex [k].name );
 l=1;
  }
  if(l==0)
  printf("    ");
}
printf("\n");
}
}








//显示信息
void Display1(AdjMatrix *G)//显示景点信息
{
int i,j;
printf("\n\t\t\t景点简介\n");
for(i=1;i<=G->vexnum ;i++)
{
printf("景点序号:%d\n",G->vex [i].No );
printf("景点名称:%s\n",G->vex [i].name );
printf("景点简介:%s\n",G->vex [i].introduce );
for(j=1;j<=G->vexnum ;j++)
{
if(G->arc [i][j]!=INFINITY)
{
printf("%s-->%s:%dm\n",G->vex [i].name ,G->vex [j].name ,G->arc [i][j]);
}
}
}
}
void save(AdjMatrix *G)//将数据保存到文件中
{
FILE *fp;
int i,j;
if((fp=fopen("数据.txt","w"))==NULL)
{
printf("无法打开文件!\n");
return;
}
fprintf(fp,"%d %d\n",G->vexnum ,G->arcnum );
for(i=1;i<=G->vexnum ;i++)
{
  fprintf(fp,"%d\n",G->vex [i].No );
  fprintf(fp,"%s\n",G->vex [i].name );
  fprintf(fp,"%d %d\n",G->vex [i].X ,G->vex [i].Y );
  fprintf(fp,"%s\n",G->vex [i].introduce );
}  
for(i=1;i<=G->vexnum ;i++)
  for(j=1;j<=G->vexnum ;j++)
{
 fprintf(fp,"%d ",G->arc [i][j]);
}
  fprintf(fp,"\n");
fclose(fp);
}




AdjMatrix * load(AdjMatrix *G)//将文件信息读出
{
FILE *fp;
int i,j;
if((fp=fopen("数据.txt","r"))==NULL)
{
printf("无法打开文件!");
return NULL;
}
    fscanf(fp,"%d %d\n",&G->vexnum ,&G->arcnum );
for(i=1;i<=G->vexnum ;i++)
{
  fscanf(fp,"%d\n",&G->vex [i].No );
  fscanf(fp,"%s\n",G->vex [i].name );
  fscanf(fp,"%d %d\n",&G->vex [i].X ,&G->vex [i].Y );
  fscanf(fp,"%s\n",G->vex [i].introduce );
}  
for(i=1;i<=G->vexnum ;i++)
  for(j=1;j<=G->vexnum ;j++)
{
 fscanf(fp,"%d ",&G->arc [i][j]);
}
fclose(fp);
return G;

}


void Search(AdjMatrix *G)//查找景点的信息
{
int No,i,j;
char place[20];
printf("输入查找的景点:");
scanf("%s",place);
No=Locate(G,place);
printf("景点状况为:\n");
for(i=1;i<=G->vexnum ;i++)
{
if(i==No)
{
printf("序号为:%d\n",G->vex[i].No );
printf("景点名为:%s\n",G->vex [i].name );
printf("景点介绍:%s\n",G->vex [i].introduce );
for(j=1;j<=G->vexnum ;j++)
{
if(G->arc [i][j]!=INFINITY)
printf("-->%s:%dm\n",G->vex [j].name ,G->arc [i][j]);
}
}
}

}
//添加新路线
void Add(AdjMatrix *G)
{
   char place[20];
   int start,end,weight;
   printf("输入加入新路线的起点地点:");
   scanf("%s",place);
   start=Locate(G,place);
   printf("终点地点:");
   scanf("%s",place);
   end=Locate(G,place);
   printf("距离:");
   scanf("%d",&weight);
   if(G->arc [start][end]==INFINITY&&G->arc [end][start]==INFINITY)
   {
  G->arc [start][end]=weight;
       G->arc [end][start]=weight;
       G->arcnum ++;
   }
   save(G);
}
//撤销旧路线
void Dell(AdjMatrix *G)
{
   char place[20];
   int start,end;
   printf("输入撤销的起点地点:");
   scanf("%s",place);
   start=Locate(G,place);
   printf("终点地点:");
   scanf("%s",place);
   end=Locate(G,place);
   if(G->arc [start][end]!=INFINITY||G->arc [end][start]!=INFINITY)
   {
     G->arc [start][end]=INFINITY;
     G->arc [end][start]=INFINITY;
     G->arcnum --;
   }
   save(G);
}


//用Dijkstra算法求起点到终点最短路线
void Dijkstra(AdjMatrix *G,int start,int end,int dist[],int path[][MAXVEX])
{
int mindist,i,j,k,t=1;
for(i=1;i<=G->vexnum ;i++)
{
dist[i]=G->arc [start][i];
if(G->arc [start][i]!=INFINITY)
 path[i][1]=start;
}
path[start][0]=1;
for(i=2;i<=G->vexnum ;i++)
{
mindist=INFINITY;
for(j=1;j<=G->vexnum ;j++)
  if(!path[j][0]&&dist[j]<mindist)
  {
  k=j;
  mindist=dist[j];
  }
  if(mindist==INFINITY)
  return;
  path[k][0]=1;
  for(j=1;j<=G->vexnum ;j++)
  {
  if(!path[j][0]&&G->arc [k][j]<INFINITY&&dist[k]+G->arc [k][j]<dist[j])
  {
  dist[j]=dist[k]+G->arc [k][j];
  t=1;
  while(path[k][t]!=0)
  {
  path[j][t]=path[k][t];
  t++;
  }
  path[j][t]=k;
  path[j][t+1]=0;
  }
  }
}
for(i=1;i<=G->vexnum ;i++)
 if(i==end)
 break;
 printf("%s-->%s的最短路径为:从%s",G->vex [start].name ,G->vex [end].name ,G->vex [start].name );
 for(j=2;path[i][j]!=0;j++)
 printf("-->%s",G->vex [path[i][j]].name );
 printf("-->%s的距离为%dm\n",G->vex [end].name ,dist[i]);
}


//寻找最佳路线
void Shortcut(AdjMatrix *G)
{ 
char place[20];
int start,end;
int dist[MAXVEX],path[MAXVEX][MAXVEX]={0};
printf("输入起始景点:");
scanf("%s",place);
start=Locate(G,place);
printf("输入终点景点:");
scanf("%s",place);
end=Locate(G,place);
    Dijkstra(G,start,end,dist,path);
}






//采用Prim算法求得最佳布网方案
void Prim(AdjMatrix *G,int start)
{
struct
{
int adjvex;
int lowcost;
}closedge[MAXVEX];
int i,e,k,m,min;
closedge[start].lowcost=0;
for(i=1;i<=G->vexnum ;i++)
if(i!=start)
{
closedge[i].adjvex=start;
closedge[i].lowcost=G->arc [start][i];
}
for(e=1;e<=G->vexnum -1;e++)
{
min=INFINITY;
for(k=1;k<=G->vexnum ;k++)
{
if(closedge[k].lowcost!=0&&closedge[k].lowcost<min)
{
m=k;
min=closedge[k].lowcost;
}
}
printf("从%s--%s:%dm\n",G->vex [closedge[m].adjvex].name ,G->vex [m].name ,closedge[m].lowcost);
closedge[m].lowcost=0;
for(i=1;i<=G->vexnum ;i++)
 if(i!=m&&G->arc [m][i]<closedge[i].lowcost)
 {
 closedge[i].lowcost=G->arc [m][i];
 closedge[i].adjvex=m;
 }
}
}




//查询最佳布网方案
void MiniSpan(AdjMatrix *G)
{
char place[20];
int start;
printf("输入起始景点:");
scanf("%s",place);
start=Locate(G,place);
Prim(G,start);
}




AdjList *Strange(AdjMatrix *G)//将邻接矩阵转化为邻接表
{
int i,j;
AdjList *G1;
    ArcNode *p;
G1=(AdjList *)malloc(sizeof(AdjList));
G1->arcnum =G->arcnum ;
G1->vexnum =G->vexnum ;
for(i=1;i<=G->vexnum ;i++)
{
G1->vertex [i].head=NULL;
}
for(i=1;i<=G->vexnum ;i++)
{
       G1->vertex [i].No =G->vex [i].No;
  strcpy(G1->vertex [i].name ,G->vex [i].name );
  G1->vertex [i].X =G->vex [i].X ;
  G1->vertex [i].Y =G->vex [i].Y ;
  strcpy(G1->vertex [i].introduce ,G->vex [i].introduce) ;
}
for(i=1;i<=G->vexnum;i++)
{
for(j=1;j<=G->vexnum ;j++)
{
if(G->arc [i][j]!=INFINITY)
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex =j;
p->weight =G->arc [i][j];
p->next =G1->vertex [i].head ;
G1->vertex [i].head =p;
}
}
}
return G1;
}










void print(AdjList *G1)
{
int i;
ArcNode *p;
for(i = 1; i <= G1->vexnum; i++)
{
p = G1->vertex[i].head;
printf("%d\n",G1->vertex [i].No );
        printf("%s\n",G1->vertex [i].name );
printf("%d %d\n",G1->vertex [i].X ,G1->vertex [i].Y );
        printf("%s\n",G1->vertex [i].introduce );
while(p)
{
printf(" --> <%d, %d>", p->adjvex, p->weight);
p = p->next;
}
printf("\n");
}
}
















void DelVex(AdjMatrix *G)//删除结点
{
FILE *fp;
int i,j,k,l=0;
char name[20];
printf("输入要删除的景点名:");
scanf("%s",name);
k=Locate(G,name);
for(i=1;i<=G->vexnum ;i++)
{
if(G->arc [k][i]!=INFINITY)
{
l=l+1;
}
}
for(i=1;i<=G->vexnum ;i++)
{
for(j=1;j<=G->vexnum ;j++)
{
if(i==k||j==k)
{
G->arc [i][j]=-1;
}
}
}
if((fp=fopen("数据.txt","w"))==NULL)
{
printf("无法打开文件!\n");
return;
}
fprintf(fp,"%d %d\n",G->vexnum -1,G->arcnum -l);
for(i=1;i<=G->vexnum ;i++)
{
if(i!=k)
{
     fprintf(fp,"%d\n",G->vex [i].No );
     fprintf(fp,"%s\n",G->vex [i].name );
     fprintf(fp,"%d %d\n",G->vex [i].X ,G->vex [i].Y );
     fprintf(fp,"%s\n",G->vex [i].introduce );
}
}  
for(i=1;i<=G->vexnum ;i++)
  for(j=1;j<=G->vexnum ;j++)
  {
  if(G->arc[i][j]!=-1)
    fprintf(fp,"%d ",G->arc [i][j]);
}
  fprintf(fp,"\n");
  fclose(fp);
}








void AddVex(AdjMatrix *G)
{
int i,j,k;
i=G->vexnum +1;
printf("输入要增加的景点序号:");
    scanf("%d",&G->vex [i].No );
fflush(stdin);
printf("输入要增加的景点名:");
scanf("%s",G->vex [i].name );
fflush(stdin);
printf("输入要增加的景点坐标:");
scanf("%d,%d",&G->vex [i].X ,&G->vex [i].Y );
fflush(stdin);
printf("输入要增加的景点介绍:");
scanf("%s",G->vex [i].introduce );
G->vexnum =i;
for(k=1;k<=G->vexnum ;k++)
{
for(j=1;j<=G->vexnum ;j++)
{
if(k==i||j==i)
G->arc [k][j]=INFINITY;
}
}
save(G);
}






int total = 0; 


void DFS(AdjMatrix *G,int start, int end, int k)      //深度优先遍历找出两个顶点的所有简单路径 
{
int s;
if(D[k] == end && k <= G->vexnum )
{
for(s = 1; s < k; s++)
printf("%s-->", G->vex [D[s]].name );
printf("%s\n\n", G->vex [D[s]].name );
total++;
}
else
{
s = 1;
while(s <=G->vexnum )
{
if((G->arc [D[k]][s]!=INFINITY) && visited[s] ==0)
{
visited[s] = 1;
D[k+1] = s;
DFS(G,start, end, k+1);
visited[s] = 0;
}
s++;
}
} 
} 


void Allpath(AdjMatrix *G)     //两个顶点间的所有简单路径 
{
int i;
char name[20]; 
int start, end;
char c = ‘y‘;
while(c == ‘y‘)
{
printf("\n\t\t\t初始景点名: ");
scanf("%s", name);
        start=Locate(G,name);
printf("\n\t\t\t最终景点名: ");
scanf("%s" ,name);
end=Locate(G,name);
D[1] = start;     //存储初始顶点 
for(i= 1; i <= G->vexnum ; i++)
visited[i] = 0;     //初始化数组 
visited[start] = 1;     //起始顶点已访问
DFS(G,start, end, 1);
printf("从%s到%s一共有%d条简单路径\n", G->vex [start].name , G->vex [end].name , total);
total = 0;
printf("\n\t\t\t是否继续增加路线(y/n): ");
getchar();
c = getchar();
system("cls");
}
}




void menu()
{
printf("\t\t\t\t***选择菜单***\n\n\n");
printf("\t\t\t***1.显示景点相关信息***\n");
printf("\t\t\t***2.输出任意两景点之间的所有简单路径***\n");
printf("\t\t\t***3.输出任意两景点之间中转次数最少的简单路径***\n");
printf("\t\t\t***4.输出任意两景点之间的最佳路径***\n");
printf("\t\t\t***5.输出最佳布网方案***\n");
printf("\t\t\t***6.增加新路线***\n");
printf("\t\t\t***7.撤销旧路线***\n");
printf("\t\t\t***8.增加新景点***\n");
printf("\t\t\t***9.撤销旧景点***\n");
printf("\t\t\t***10.退出****\n\n");
printf("\t\t\t***请选择:");
}


/*main()
{
AdjMatrix *g;
int i;
char c = ‘y‘;
g=(AdjMatrix *)malloc(sizeof(AdjMatrix ));
printf("\t\t\t欢迎进入西邮西区导航系统!\n");
g=load(g);
Display2(g);
Display1(g);
printf("\t\t\t输入创建地图的方式:\n");
printf("\t\t\t***1.自己创建.***\n");
printf("\t\t\t***2.文件读取.***\n");
scanf("%d",&i);
system("cls");
switch(i)
{
case 1:Create1(g);g=load(g);Display2(g);Display1(g);break;
case 2:g=load(g);Display2(g);Display1(g);break;
}
    while(c==‘y‘)
{
      menu();
 scanf("%d",&i);
 switch(i)
 {
 case 1:Search(g);break;
 case 2:Allpath(g);break;
 case 3:break;
 case 4:Shortcut(g);break;
 case 5:MiniSpan(g);break;
 case 6:Add(g);g=load(g);break;
 case 7:Dell(g);g=load(g);break;
 case 8:AddVex(g);g=load(g);break;
 case 9:DelVex(g);g=load(g);break;
 case 10:break;
 }
        printf("\n\t\t\t是否继续(y/n): ");
getchar();
c = getchar();
system("cls");
        Display2(g);
   Display1(g);
}
}
*/
main()
{
  AdjMatrix *g;
  g=(AdjMatrix *)malloc(sizeof(AdjMatrix ));
  load(g);
  Shortcut(g);
}

c++的自学笔记


联系
我们