以下是数据结构中的有向十字链表的操作
 |
| 文件: |
c_lianbiao.rar |
| 大小: |
4KB |
| 下载: |
下载 | |
//======================
c_struct.h
#define MAX_INFO 20
#define MAX_LIST 10
typedef char strInfo[MAX_INFO];
typedef char ErrMsg[MAX_INFO];
//using namespace std;
//参数声名顺序:遵循从出到进的原则
typedef struct ArcBox{//----->弧结点
int tailvex,headvex; //弧尾、弧头在表头数组中位置(索引)
struct ArcBox *tlink,*hlink; //分别指向弧头相同和弧尾相同的的弧的链域的下一个节点
struct ArcBox *tlink_prior,*hlink_prior;//上一个弧结点
strInfo info; //弧信息 弧名
}ArcBox;
typedef struct VexNode{//---->顶点结点
strInfo data; //顶点名称
ArcBox *firstout,*firstin; //分别指向该顶点的第一条入弧和出弧
}VexNode;
typedef struct OLGraph{//表头列表
VexNode hlist[MAX_LIST];//表头向量
int vexnum,arcnum;//有向图的[顶点数]和[弧数]
int length;//数组的长度
}OLGraph;
//=========================
c_ctrl.h
// c_1.cpp : 定义控制台应用程序的入口点。
#include "stdlib.h"
#include "stdio.h"
#include "dos.h" //clrscr();清屏函数
#include "conio.h"
#include "string.h"
#include "c_struct.h"
//===================firstout对应tlink firstin对应hlink
//********* 返回 c 所在表头的索引,找不到返回 -1 *********//
int LocateVex(OLGraph G,strInfo c)//
{
int i;
for(i=0;i {
if(strcmp(c,G.hlist[i].data)==0)
return i;
}
return -1;
}
//********** 十字链表构造函数,正常返回0,失败返回 -1 **********//
int Inner_InsertArcBox(OLGraph &G,ErrMsg msg=NULL)
{
ArcBox *box=NULL,*temp=NULL,*prior=NULL;
strInfo h,t;
int i,j;
box=(ArcBox *)malloc(sizeof(ArcBox));// 为弧节点分配空间
if(!box)//分置空间失败
{
puts(" ---!!!!!!结点分配失败!!!!!!---");
return -1;//失败返回 -1
}
else
{
box->hlink=NULL;box->tlink=NULL;
box->hlink_prior=NULL;box->tlink_prior=NULL;
printf("请输入[弧尾]和[弧头] <以'空格'或'回车'分隔>:");scanf("%s %s",t,h);getchar();//gets(t);gets(h);
i=LocateVex(G,t);//查找弧尾位置 tailvex 对应firstout
while(i<0) //排错
{
printf("！！！弧头 %s 不存在,请重新输入:",t);gets(t);
i=LocateVex(G,t);//查找弧尾位置 tailvex 对应firstout
}
j=LocateVex(G,h);//查找弧头位置 headvex 对应firstin
while(j<0) //排错
{
printf("！！！弧尾 %s 不存在,请重新输入:",h);gets(h);
j=LocateVex(G,h);//查找弧头位置 headvex 对应firstin
}
printf("请输入[弧名]:");gets(box->info);
box->tailvex=i;//指定尾位置 弧尾 它的tlink指向xlist[i]的firstout这一链的最后一个ArcBox -->设置ArcBox的tailvex域
box->headvex=j;//指定头位置 弧头 它的hlink指向xlist[j]的firstin这一链的最后一个ArcBox -->设置ArcBox的headvex域
if(G.hlist[i].firstout==NULL)
{
G.hlist[i].firstout=box;
}
else//----------->设置ArcBox的tlink域
{
temp=prior=G.hlist[i].firstout;
while(temp->tlink!=NULL){ prior=temp;temp=temp->tlink; }//firstout对应tlink firstin对应hlink
temp->tlink=box;
box->tlink_prior=prior;
temp=NULL;prior=NULL;
}
if(G.hlist[j].firstin==NULL)
{
G.hlist[j].firstin=box;
}
else//----------->设置ArcBox的hlink域
{
temp=prior=G.hlist[j].firstin;
while(temp->hlink!=NULL){ prior=temp;temp=temp->hlink; }
temp->hlink=box;
box->hlink_prior=prior;
temp=NULL;prior=NULL;
}
}
G.arcnum+=1;//添一个弧，计数器要加1
return 0;
}
int CreateDG(OLGraph &G)
{
ArcBox *temp=NULL;
int i,k,vxnum,acnum;
G.length=MAX_LIST;
G.arcnum=0;
G.vexnum=0;
printf("请输入[顶点数]和[弧数]:");
//scanf("%d %d",&G.vexnum,&G.arcnum);getchar();
scanf("%d %d",&vxnum,&acnum);getchar();
puts(" 开构造表头结点......");
for(i=0;i
{
printf("请输入[顶点信息]:");
gets(G.hlist[i].data);
G.hlist[i].firstin=NULL;
G.hlist[i].firstout=NULL;
G.vexnum+=1;
}
printf(" 开始构造链表......\n");
for(k=0;k {
if(Inner_InsertArcBox(G)<0)
{
puts(" ---!!!!!!构造链表失败!!!!!!---");
return -1;
}
}
return 0;//成功返回 0
}//********** 输入链表信息,只输出 firstout *********//
void PrintOLG_out(OLGraph G)
{
ArcBox *box;
int i,j;
for(i=0;i {
j=1;box=NULL;
printf("\n******结点名称:");puts(G.hlist[i].data);//输出顶点结点名称
if(G.hlist[i].firstout!=NULL)//如果有链表
{
box=G.hlist[i].firstout;//引用ArcBox对象
do{
printf("\n--->>第 %2d 个出弧名:%s\n",j,box->info);
printf("弧尾:%s ; ",G.hlist[box->tailvex].data);
printf("弧头:%s \n\n",G.hlist[box->headvex].data);
printf("即从 %s 到 %s\n",G.hlist[box->tailvex].data,G.hlist[box->headvex].data);
box=box->tlink; //firstout对应tlink firstin对应hlink
j++;
}while(box!=NULL);
}
else
{
puts("该结点没出弧!");
}
}
}
//********** 输入链表信息,只输出 firstin *********//
void PrintOLG_in(OLGraph G)
{
ArcBox *box;
int i,j;
for(i=0;i {
j=1;box=NULL;
printf("\n******结点名称:");puts(G.hlist[i].data);//输出顶点结点名称
if(G.hlist[i].firstin!=NULL)//如果有链表
{
box=G.hlist[i].firstin;//引用ArcBox对象
do{
printf("\n--->>第 %2d 个入弧名:%s\n",j,box->info);
printf("弧尾:%s ; ",G.hlist[box->tailvex].data);
printf("弧头:%s \n\n",G.hlist[box->headvex].data);
printf("即从 %s 到 %s\n",G.hlist[box->tailvex].data,G.hlist[box->headvex].data);
box=box->hlink; //firstout对应tlink firstin对应hlink
j++;
}while(box!=NULL);
}
else
{
puts("该结点没入弧!");
}
}
}
//********* 查找方法区 **********************************//
//*********查找弧结点，找到返回 ArcBox，否则返回NULL ***//
ArcBox * Find_ArcBox(OLGraph G)
{
strInfo box_name;
ArcBox *trg_box=NULL;
int i;
printf("请输入要删除弧的名称：");gets(box_name);
for(i=0;i {
//开始在firstin引出的链表中找
if(G.hlist[i].firstin==NULL)
break;//该节点没有后继链表
else
{
trg_box=G.hlist[i].firstin;
if(strcmp(trg_box->info,box_name)==0)//第一个节点是目标
{
return trg_box;
}
while(trg_box->hlink!=NULL)
{
trg_box=trg_box->hlink;
if(strcmp(trg_box->info,box_name)==0)
return trg_box;
}
}//第一轮查找结束
}
for(i=0;i {
if(G.hlist[i].firstout==NULL)
break;//该节点没有后继链表
else
{
trg_box=G.hlist[i].firstout;
if(strcmp(trg_box->info,box_name)==0)//第一个节点是目标
{
return trg_box;
}
while(trg_box->tlink!=NULL)
{
trg_box=trg_box->tlink;
if(strcmp(trg_box->info,box_name)==0)
return trg_box;
}
}
}
return NULL;//找不到就返回NULL
}
//**********查找trg_box的firstin该链的前一个结点**********//
// flag=0，链上的第一个结点即为目标结点，返回NULL
// flag=1，链中的结点，返回ArcBox
// flag=-1，表中不取在，返回NULL
ArcBox * Find_Pre_Firstin_ArcBox(OLGraph G,const ArcBox *trg_box,int & flag)//ArcBox *pre_box=NULL)
{
ArcBox * pre_box=NULL;
int head_num=trg_box->headvex;
if(G.hlist[head_num].firstin==trg_box)
{
flag=0;//第一个结点即为要找的结点时返回值为：0
return NULL;
}
pre_box=G.hlist[head_num].firstin;
do
{
if(pre_box->hlink==trg_box)
break;
else
pre_box=pre_box->hlink;
}while(pre_box!=NULL);
if(pre_box!=NULL)
{
flag=1;//非第一个结点返回： 1
return pre_box;
}
else
{
flag=-1;////没找到返回：-1
return NULL;
}
}
//**********查找trg_box的firstout该链的前一个结点**********//
// flag=0，链上的第一个结点即为目标结点
// flag=1，链中的结点
// flag=-1，表中不取在
ArcBox * Find_Pre_Firstout_ArcBox(OLGraph G,const ArcBox *trg_box,int & flag)//ArcBox *pre_box=NULL)
{
ArcBox * pre_box=NULL;
int tail_num=trg_box->tailvex;
if(G.hlist[tail_num].firstout==trg_box)
{
flag=0;//第一个结点即为要找的结点时返回值为：0
return NULL;
}
pre_box=G.hlist[tail_num].firstout;
do
{
if(pre_box->tlink==trg_box)
break;
else
pre_box=pre_box->tlink;
}while(pre_box!=NULL);
if(pre_box!=NULL)
{
flag=1;//非第一个结点返回： 1
return pre_box;
}
else
{
flag=-1;//没找到返回：-1
return NULL;
}
}
void FindBox(OLGraph G,ErrMsg msg)
{
const ArcBox *box=Find_ArcBox(G);
if(box==NULL)
{
msg="not found";
}
else
{
printf("节点名称：%s\n",box->info);
if(box->hlink_prior!=NULL)
printf("box.hlink_prior.name=%s\n",box->hlink_prior->info);
if(box->tlink_prior!=NULL)
printf("box.tlink.prior.info=%s\n",box->tlink_prior->info);
}
}
//********************************************************//
//********** 插入弧结点,成功返回 0,失败返回 -1 *********//
int InsertArcBox(OLGraph &G)
{
if(Inner_InsertArcBox(G)<0)
{
puts("---!!!!!!插入失败!!!!!!---");
return -1;
}
return 0;
}
//***********删除弧结点,成功返回1，失败返回 -1 *********//
int DelArcBox(OLGraph &G)
{
int flag=-1;
ArcBox *pre_box=NULL;
ArcBox *del_box=Find_ArcBox(G);
if(del_box==NULL)
{
puts("没有找到该弧,请继续操作....");
return -1;
}
pre_box=Find_Pre_Firstin_ArcBox(G,del_box,flag);
switch(flag)
{
case -1:
puts("没有找到该弧,请继续操作....");
return -1;//没有找到要找的弧
case 0:
G.hlist[del_box->headvex].firstin=del_box->hlink;
break;
case 1:
if(del_box->hlink==NULL)
pre_box->hlink=NULL;
else
pre_box->hlink=del_box->hlink;
break;
default:return -1;
}
pre_box=Find_Pre_Firstout_ArcBox(G,del_box,flag);
switch(flag)
{
case -1:return -1;
case 0:
G.hlist[del_box->tailvex].firstout=del_box->tlink;
break;
case 1:
if(del_box->tlink==NULL)
pre_box->tlink=NULL;
else
pre_box->tlink=del_box->tlink;
break;
default:return -1;
}
printf("结点 %s 已被删除!!!\n",del_box->info);
return 1;
}
//********** 插入顶点结点,成功返回 0,失败返回 -1 *********//
int InsertNode(OLGraph &G,ErrMsg msg=NULL)
{
int index;
VexNode *newBase=NULL;
if(G.vexnum>=G.length)//空间不足
{
newBase=(VexNode *)realloc(G.hlist,sizeof(VexNode)*MAX_LIST);
if(!newBase)
{
//G.hlist=newBase;
G.length+=MAX_LIST;
}
else
{
msg="分配结点失败";
return -1;
}
}
else
{
index=G.vexnum;
printf("请输入[顶点信息]:");
gets(G.hlist[index].data);
G.hlist[index].firstin=NULL;
G.hlist[index].firstout=NULL;
G.vexnum+=1;
}
return 0;
}
//********** 删除顶点,成功返回 0,失败返回 -1 *********//
int DelNode(VexNode node)
{
return 0;
}
int ToFile(OLGraph &G,ErrMsg msg)
{
int size,i;
FILE *fp;
//if(fp=fopen("olg.cui","a"))//打开文件成功
//{
//}
//else
i=sizeof(G);
{
fp=fopen("olg.cui","w");
if(!fp)
return -1;
size=fwrite(&G,sizeof(G),sizeof(G)-1,fp);
}
if(fp)
fclose(fp);
return -1;
}
//======================
c_menu.h
void CtlSrc()
{
printf("*******************************************************\n");
printf(" ***********命令选项****************\n");
printf(" 从弧头输出：1\n");
printf(" 从弧尾输出：2\n");
printf(" 插入结点：3\n");
printf(" 删除弧结点：4\n");
printf(" 插入结点：5\n");
printf(" 查找：6\n");
printf(" 保存：9\n");
printf(" 退出：0\n");
printf(" ***********************************\n");
printf("*******************************************************\n");
}
//========================
c_main.cpp
#include "c_ctrl.h"
#include "c_menu.h"
void main()
{
char ch;
ErrMsg errmsg;
OLGraph G;
CtlSrc();
printf(" 开始构造表头信息......\n");
if(CreateDG(G)==0)
puts("创建成功!");
else
puts("创建失败!!!");
do
{
CtlSrc();
ch=getchar();getchar();
switch(ch)
{
case '1':PrintOLG_in(G);break;
case '2':PrintOLG_out(G); break;
case '3':InsertArcBox(G);break;
case '4':DelArcBox(G);break;
case '5':InsertNode(G,errmsg);break;
case '6':FindBox(G,errmsg);break;
case '9':ToFile(G,errmsg);break;
default:puts("请输入正确的选项．．．");
break;
}
}while(ch!='0');
puts("\n按任意键退出...");
getchar();
}
//结构体操作层
