unit1.~cpp

通过builder实现的数据结构各种算法 由于本人编程技术还没成熟

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
//创建一个矩阵结构
const int nmax=100;                 //规定矩阵的大小
int e;
int numjie=0;
struct juzhen{                      //做一个矩阵结构
int data[nmax+1];
int adjmat[nmax+1][nmax+1];         //0号单元不用
int n,e;                            //n和e用来记录定点数与边数
} mat_graph;
//---------------------------------------------------------------------------
//生成邻接矩阵
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Label10->Caption="";
if(StrToInt(Edit1->Text)<=100){     //限制输入过大
juzhen *ga;                         //设置矩阵指针
ga=&mat_graph;
int i,j,e,w;
ga->n=StrToInt(Edit1->Text);
for(i=1;i<=StrToInt(Edit1->Text);i++) ga->data[i]=i;      //设置表头为1,2,3....
for(i=1;i<=StrToInt(Edit1->Text);i++)
 {
 for(j=1;j<=StrToInt(Edit1->Text);j++)
 ga->adjmat[i][j]=0;
 }
for(i=1;i<=StrToInt(Edit1->Text);i++)        //输出矩阵
 {
 for(j=1;j<=StrToInt(Edit1->Text);j++)
  {
  Label10->Caption=Label10->Caption+ga->adjmat[i][j]+"   ";
  }
 Label10->Caption=Label10->Caption+"\r\n";
 numjie=StrToInt(Edit1->Text);
 }
}
else ShowMessage("输入数据过大");
}
//---------------------------------------------------------------------------
//对邻接矩阵的元素进行负值
void __fastcall TForm1::Button3Click(TObject *Sender)
{
 juzhen *ga;
 ga=&mat_graph;
 int i,j;
 if(Edit2->Text!=""&&Edit3->Text!=""&&Edit4->Text!="")    //判断是否有输入参数
 {
 e++;                                                     //边数增加
 ga->adjmat[StrToInt(Edit2->Text)][StrToInt(Edit3->Text)]=StrToInt(Edit4->Text);
 ga->e=e;                                                //对邻接矩阵进行负值
 Label10->Caption="";
 for(i=1;i<=numjie;i++)                                //把负值后的矩阵重新显示
 {
 for(j=1;j<=numjie;j++)
  {
  Label10->Caption=Label10->Caption+ga->adjmat[i][j]+"   ";
  }
 Label10->Caption=Label10->Caption+"\r\n";
 }
 }
 else ShowMessage("请输入参数");
}
//---------------------------------------------------------------------------
//生成邻接表
typedef struct node * pointer;
struct node {                 //边表节点
int no;                       //邻接点域
pointer next;                 //链域
};
typedef struct {
int data;                     //定点信息
int in;                       //记录节点入度情况，为拓扑排序做准备
pointer first;                //边表头指针
} headtype;
struct biao{
headtype adjlist[nmax+1];     //定点表,0号单元不用
int n,e;                      //顶点数和边数
} lk_graph;
//---------------------------------------------------------------------------
//由矩阵生成邻接表
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 Label11->Caption="";
 biao *gb;                   //创建表指针
 gb=&lk_graph;
 juzhen *ga;
 ga=&mat_graph;
 int i,j,n,e;                //i,j为循环负值备用,n为节点数,e为边数
 pointer p;
 n=numjie;
 gb->n=n;
 for(i=1;i<=n;i++) {
 gb->adjlist[i].data=i;               //对定点表进行负值
 gb->adjlist[i].first=NULL;           //初始化
 gb->adjlist[i].in=0;                 //初始化
  for(j=1;j<=numjie;j++)
  {
   if(ga->adjmat[j][i]!=0) (gb->adjlist[i].in)++;   //设置每个点的入度数
  }
 }
 e=0;
 for(i=1;i<=numjie;i++) {                                      //输出邻接表
  Label11->Caption=Label11->Caption+"v"+gb->adjlist[i].data;
  for(j=1;j<=numjie;j++) {
  if(ga->adjmat[i][j]!=0){                      //判断元素不空,创建新节点
  e++;
  p=new node;
  p->no=j;
  p->next=gb->adjlist[i].first;                   //对新节点负值
  gb->adjlist[i].first=p;
  Label11->Caption=Label11->Caption+"->"+p->no;        //显示邻接表
  }
  }
 Label11->Caption=Label11->Caption+"\r\n";
 }
 gb->e=e;        
}
//---------------------------------------------------------------------------
int visited_a[100];            //标记数组用来存放节点是否访问过
void dfs(juzhen x,int v)       //dfs算法函数，x为形参，v为出发点
{
 juzhen *gg;                   //矩阵元素指针
 gg=&x;
 int j;
 Form1->Label4->Caption=Form1->Label4->Caption+"v"+v+"  ";
 Form1->Label9->Caption=Form1->Label9->Caption+"v"+v+"  ";
 visited_a[v]=1;        //使biaoji=1表示该节点访问过
 for(j=1;j<=numjie;j++)
 {
  if(gg->adjmat[v][j]>0&&!visited_a[j])      //矩阵元素非0，又没访问过，则递归
  {
   dfs(x,j);
  }
 }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{
 Label4->Caption="";                    //对label4进行清空
 int b;
 for(b=1;b<100;b++)                      //给标记函数赋初值
 {
  visited_a[b]=0;
 }
 dfs(mat_graph,1);                       //出发点我们假设为一
 Label9->Caption="";
}
//---------------------------------------------------------------------------
//创建队列结构
const int maxsize=100;
typedef struct
{
 int data[maxsize];
 int front,rear;
}sqqueue;
//初始化：
void init_sqqueue(sqqueue *sq)
{
 sq->front=sq->rear=0;
}
//判队空
int empty_sqqueue(sqqueue *sq)
{
 if(sq->rear==sq->front) return 1;
 else return 0;
}
//取队头
int gethead_sqqueue(sqqueue *sq,int *x)
{
 if(sq->rear==sq->front) return 0;
 else
 {*x=sq->data[(sq->front+1)%maxsize];
  return 1;
 }
}
//入队
int en_sqqueue(sqqueue *sq,int x)
{
 if((sq->rear+1)%maxsize==sq->front)return 0;
 else
 {
  sq->rear=(sq->rear+1)%maxsize;
  sq->data[sq->rear]=x;
  return 1;
 }
}
//出队
int de_sqqueue(sqqueue *sq,int *x)
{
 if(sq->rear==sq->front)   return 0;
 else
 {
  sq->front=(sq->front+1)%maxsize;
  *x=sq->data[sq->front];
  return 1;
 }
}
//---------------------------------------------------------------------------
int visited_b[100];             //标记bfs算法的元素是否被访问过
void bfs(juzhen y,int v)        //创建bfs函数
{
 juzhen *g;                      //使用顺序队列
 g=&y;
 int j;
 sqqueue Q;
 init_sqqueue(&Q);
 Form1->Label4->Caption=Form1->Label4->Caption+"v"+v+"  ";    //访问出发点
 visited_b[v]=1;
 en_sqqueue(&Q,v);
 while(!empty_sqqueue(&Q))                    //如果队列不为空，循环
 {
  de_sqqueue(&Q,&v);
  for(j=1;j<=numjie;j++)
  {
   if(g->adjmat[v][j]>0&&!visited_b[j])
   {        //矩阵元素不为0，又没有访问过
   Form1->Label4->Caption=Form1->Label4->Caption+"v"+j+"  ";         //输出该节点
   visited_b[j]=1;                            //修改访问信息
   en_sqqueue(&Q,j);
   }
  }
 }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button6Click(TObject *Sender)
{
 int b;
 for(b=1;b<100;b++)
 {
  visited_b[b]=0;                             //为标记函数赋初值
 }
 Label4->Caption="";                          //清空label4
 bfs(mat_graph,1);        
}
//---------------------------------------------------------------------------
typedef struct node_lk * pointer_lk;         //pointer_lk为链栈节点指针类型
struct node_lk
{
 int data;
 pointer_lk next;
};
typedef struct
{
 pointer_lk top;
}lkstack;
//初始化栈函数
void init_lkstack(lkstack *ls)
{
 ls->top=NULL;
}
//判断栈空函数
int empty_lkstack(lkstack *ls)
{
 if(ls->top==NULL) return 1;
 else return 0;
}
//进栈函数
void push_lkstack(lkstack *ls,int x)
{
 pointer_lk p;
 p=new node_lk;
 p->data=x;
 p->next=ls->top;
 ls->top=p;
}
//退栈函数
int pop_lkstack(lkstack *ls,int *x)
{
 pointer_lk p;
 if(ls->top==NULL) return 0;
 else
 {
  p=ls->top;
  *x=p->data;
  ls->top=p->next;
  delete p;
  return 1;
 }
}
//---------------------------------------------------------------------------
//创建拓扑排序函数
int topsort(biao z)
{
 biao *gc;                        //gc为指向有向邻接表的指针
 gc=&z;
 lkstack s;                       //使用链栈方式为函数的结构算法
 pointer p;
 int m,i,v;
 init_lkstack(&s);
 for(i=1;i<=numjie;i++)             //做一个循环先把入度为0的节点进栈
 {
  if(gc->adjlist[i].in==0) push_lkstack(&s,i);
 }
 m=0;
 while(!empty_lkstack(&s))         //当栈不为空时进栈
 {
  pop_lkstack(&s,&v);
  Form1->Label5->Caption=Form1->Label5->Caption+v+"  ";
  m++;
  p=gc->adjlist[v].first;
  while(p!=NULL)                   //将v点的各出边的终点w的入度域减1，若为0入栈
  {
   gc->adjlist[p->no].in--;
   if(gc->adjlist[p->no].in==0) push_lkstack(&s,p->no);
   p=p->next;
  }
 }
 if(m<numjie)
 Form1->Label5->Caption=Form1->Label5->Caption+"图中有环,不能拓扑排序";
 else return 1;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button7Click(TObject *Sender)
{
 topsort(lk_graph);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button11Click(TObject *Sender)
{
 Label9->Caption="";                         //把Label9清空
 int visited_c[100];                         //标记节点是否访问过
 int i,count;
 for(i=1;i<=numjie;i++) visited_c[i]=0;
 count=0;
 for(i=1;i<=numjie;i++)
 {
  if(!visited_c[i])
  {
  count++;
  Label9->Caption=Label9->Caption+"第"+count+"个连通分量:";
  dfs(mat_graph,i);
  Label9->Caption=Label9->Caption+"\r\n";
  }
 }
 Label4->Caption="";                         //清空Label4的内容
}
//---------------------------------------------------------------------------
//做一个求简单路径的算法
void list(int star,int termini)
{
 int i,j;
 juzhen *si;
 si=&mat_graph;
 int map[101][101];//用位图法记录该路径是否访问过
 for(i=1;i<=100;i++)
 {
  for(j=1;j<=100;j++) map[i][j]=0;
 }
 for(i=1;i<=numjie;i++)
 {
  if(si->adjmat[star][i]!=0&&map[star][i]==0)
  {
   map[star][i]=1;           //表示该路径已经被访问了
   if(i==termini) Form1->Label8->Caption="有简单路径或回路";
   else list(i,termini);
  }
 }
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button9Click(TObject *Sender)
{
 Label8->Caption="";
 list(StrToInt(Edit5->Text),StrToInt(Edit6->Text));
 if(Label8->Caption=="")  Label8->Caption="无简单路径";
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button10Click(TObject *Sender)
{
 Label8->Caption="";
 if(Edit7->Text!="")
  list(StrToInt(Edit7->Text),StrToInt(Edit7->Text));
 if(Label8->Caption=="")  Label8->Caption="无简单回路";
}
//---------------------------------------------------------------------------
//做一个逆拓扑函数
void ni_top(juzhen z)
{
 juzhen *ss;
 ss=&z;
 int tmp[100][100];           //临时矩阵，把表的矩阵赋值给他，保护表的原数据
 int ji[100];          //用来检查该行的行号有无被输出过
 int i,j,k,mm,zero;
 for(i=1;i<=numjie;i++)
 {
  for(j=1;j<=numjie;j++) tmp[i][j]=ss->adjmat[i][j];
  ji[i]=0;
 }
 for(mm=1;mm<=numjie;mm++)          //输出数量如果达到节点数，停止
 {
  for(i=1;i<=numjie;i++)      //一行行进行扫描
  {
   zero=0;
   for(j=1;j<=numjie;j++)
   {
    if(tmp[i][j]==0)  //每行一个个数扫描，数为0则zero自增
    {
     zero++;
     if((zero==numjie)&&(!ji[i]))        //如果全行等于0
     {
      ji[i]=1;                     //改变被访问标记
      Form1->Label5->Caption=Form1->Label5->Caption+"v"+i+"   ";   //输出全部为0的行号
      for(k=1;k<=numjie;k++)  tmp[k][i]=0;  //垂直取消可到输出点的路径
     }
    }
    else break;
   }
  }
 }
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button8Click(TObject *Sender)
{
 Label5->Caption="";
 ni_top(mat_graph);
}
//---------------------------------------------------------------------------