?? 新建 文本文檔.txt
字號:
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include<conio.h>
#include<iostream>
#define MAX_VERTEX_NUM 20 /*最大頂點數*/
#define INFINITY 32767 /*最大值*/
#define STACK_INIT_SIZE 100 //棧的最大空間
#define STACKINCREMENT 20 //棧的追加空間單位
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define OUTPLACE -1
typedef int Status;
typedef int VertexType;
typedef int InfoType;
typedef int SElemType;
typedef struct{
SElemType *base; /*棧底指針*/
SElemType *top; /*棧頂指針*/
int stacksize; /*棧的大小*/
}SqStack;
typedef struct ArcNode{
int adjvex; /*該弧所指向的頂點的位置*/
struct ArcNode *nextarc; /*指向一下條弧的指針*/
InfoType info; /*該弧相關信息*/
}ArcNode;
typedef struct VNode{
VertexType data; /*頂點信息*/
ArcNode *firstarc; /*指向第一條依附該頂點的弧的指針*/
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum; /*圖當前的頂點數和弧數*/
int kind; /*圖的種類標志*/
}ALGraph;
int indegree[MAX_VERTEX_NUM];
Status InitStack(SqStack &S) //初始化棧
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack &S,SElemType &e) //取棧頂元素
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
Status Push(SqStack &S,SElemType e1) //進棧操作
{
if(S.top-S.base>=S.stacksize){
S.base=(SElemType *)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e1;
return OK;
}
Status Pop(SqStack &S,SElemType &e) //出棧操作
{
if(S.top==S.base) return ERROR;
e=*(--S.top);
return OK;
}
Status StackEmpty(SqStack S) //判空操作
{
if(S.top==S.base)
return 1;
else
return 0;
}
int LocateVex(ALGraph &G,VertexType v) /*返回頂點v在G中下標*/
{
int i;
for(i=0;i<G.vexnum;i++)
if(v==G.vertices[i].data) return i;
return -1;
}
ALGraph Build_ALG_DN() /*創建一個有向網*/
{ ALGraph G;
int i,j,k,v1,v2;
ArcNode *p=NULL,*q=NULL;
for(i=0;i<MAX_VERTEX_NUM;i++)
G.vertices[i].firstarc=NULL; /*初始化*/
printf("請輸入頂點數:");
scanf("%d",&G.vexnum); /*輸入頂點數*/
if(G.vexnum<0)
{
printf("錯誤\n");
return G;
}
printf("請輸入邊數:");
scanf("%d",&G.arcnum); /*輸入邊數*/
if(G.arcnum<0)
{
printf("錯誤\n");
return G;
}
for(i=0;i<G.vexnum;i++) /*輸入頂點序列*/
{
printf("請輸入頂點信息: ");
scanf("%d",&G.vertices[i].data);
}
for(i=0;i<G.arcnum;i++) /*輸入邊的信息*/
{
printf("請輸入邊的信息(v1,v2):");
scanf("%d,%d,%d",&v1,&v2);
j=LocateVex(G,v1),k=LocateVex(G,v2); /*獲取v1和v2在G中的位置*/
if(j<0||k<0||j==k)
{
printf("ERROR!!\n");
i--;continue;
} /* 如果頂點輸入錯誤，繼續 */
p=(ArcNode *)malloc(sizeof(ArcNode)); /*分配結點*/
p->adjvex=k; p->nextarc=NULL;
if(!G.vertices[j].firstarc) G.vertices[j].firstarc=p; /*p是v1的第一條弧*/
else {
for(q=G.vertices[j].firstarc;q->nextarc;q=q->nextarc); /*找到鏈表的最后一個結點*/
q->nextarc=p;
}
}
return G;
}
Status Insert_Vertex_ALGraph(ALGraph &G) /*插入一個頂點*/
{
char a;
char c;
c='y';
while(c=='y')
{
printf("請輸入頂點信息:");
scanf("%d",&a);
G.vertices[G.vexnum++].data=a; /*插入頂點，頂點數加1*/
printf("你還要插入頂點嗎？(y/n)?");
scanf("%s",&c);
}
return OK;
}
Status Insert_Arc_ALGraph(ALGraph &G) /*插入一條邊*/
{
int j,k;
char v1,v2,c;
ArcNode *p,*q;
c='y';
while(c=='y') /*判斷是否插入邊*/
{
printf("請輸入邊的信息(v1,v2):");
scanf("%d,%d,%d",&v1,&v2); /*輸入邊的信息（頂點)*/
j=LocateVex(G,v1); k=LocateVex(G,v2);
if(j<0||k<0||j==k){printf("ERROR!!\n"); continue;} /*如果頂點不屬于G，繼續*/
p=(ArcNode *)malloc(sizeof(ArcNode)); /*分配一個結點*/
p->adjvex=k; p->nextarc=NULL;
if(!G.vertices[j].firstarc) G.vertices[j].firstarc=p; /*如果v1沒有邊，插入為第一條邊*/
else /*如果v1有邊，將新邊插到最后一個結點后*/
{
for(q=G.vertices[j].firstarc;q->nextarc;q=q->nextarc);
q->nextarc=p;
}
G.arcnum++;
printf("你還要插入邊嗎?(y/n)");
scanf("%s",&c);
}
return OK;
}
Status FindInDegree(ALGraph G,int indegree[]) //對有向圖的各個頂點求入度
{
int i,k;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
{
if(G.vertices[i].firstarc)
{
p=G.vertices[i].firstarc;
k=p->adjvex;
indegree[k]=1;
while(p->nextarc)
{
p=p->nextarc;
k=p->adjvex;
++indegree[k];
}//while
}//if
}//for
return OK;
}
Status TopologicalSort(ALGraph &G)
{ //輸出有向圖無環圖的拓撲有向序列，若有回路，返回錯誤。
int i,count,k;
ArcNode *p;
SqStack S;
FindInDegree(G,indegree); //對各頂點求入度
InitStack(S);
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) Push(S,i); //0入度頂點進棧
count=0;
while(!StackEmpty(S)) //棧非空
{
Pop(S,i);
printf(" %d ",G.vertices[i].data);
count++; //輸出i號頂點，計數加一
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(--indegree[k])) Push(S,k); //i號頂點的每一個鄰接點入度減一，若減后為零，入棧
}//for
}//while
if(count<G.vexnum) return ERROR; //如果輸出的頂點數小于圖的頂點數，則有向圖內有環，返回錯誤
else return OK;
}
int main()
{
int i;
int c=1;
ALGraph G;
ArcNode *p;
printf("本程序將建立一個用鄰接表方式存儲的有向圖，可以進行插入頂點或邊的操作，\n可以輸出有向圖的信息或輸出該有向圖的拓撲有向序列。\n請按任意鍵繼續\n");
getch();
system("cls");
printf("1.創建有向圖：(第一次請先執行這一步!)\n");
system("cls");
printf("========創建有向圖==========\n");
printf("所有的輸入都為整數，邊的輸入方式為輸入該邊由哪個頂點指向哪個頂點，\n兩個頂點用“,”隔開。\n");
G=Build_ALG_DN();
printf("請按任意鍵繼續選擇操作。\n");
getch();
while(c!=0)
{
system("cls");
printf("1.插入頂點\n");
printf("2.插入邊\n");
printf("3.輸出有向圖的信息（頂點和邊）\n");
printf("4.輸出有向圖的拓撲有向序列\n");
printf("0.退出\n");
printf("請選擇你要進行的操作:");
scanf("%d",&c);
switch(c)
{
case 1:
system("cls");
printf("========插入頂點===========\n");
Insert_Vertex_ALGraph(G); /*插入頂點*/
printf("請按任意鍵繼續選擇操作。\n");
getch();
break;
case 2:
system("cls");
printf("========插入邊==========\n");
Insert_Arc_ALGraph(G); //插入邊
printf("請按任意鍵繼續選擇操作。\n");
getch();
break;
case 3:
system("cls");
printf("========輸出有向圖=========\n");
for(i=0;i<G.vexnum;i++) //輸出頂點的信息
{
printf("%d ",G.vertices[i].data);
}
printf("\n");
for(i=0;i<G.vexnum;i++) //輸出邊的信息
{
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
printf("%d-->%d ",G.vertices[i].data,G.vertices[p->adjvex].data);
}
printf("\n");
printf("\n請按任意鍵繼續選擇操作。\n");
getch();
break;
case 4:
system("cls");
printf("========輸出有向圖的拓撲有向序列===========\n");
if(!TopologicalSort(G))
printf("\n有向圖中有回路，錯誤\n");
printf("\n請按任意鍵繼續選擇操作。\n");
getch();
break;
case 0:
break;
default:
printf("\n你的選擇是錯誤的！\n");
getch();
break;
}//switch
}//while
printf("\n歡迎下次再來……^_^\n");
getch();
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -