求一个关于“图、树”的数据结构代码源程序
急需，完整版的，包括头文件，在下还不知道到底运行结果会是什么样子的，难道真的可以编出树型结构或者图形结构吗？（貌似很欠扁很欠抽，但如果用编译器可以编出来，那么，也算是一种创新吧）
[解决办法]
树，图貌似只是个存储结构吧
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef char TElemType;
typedef char SElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode* lchild, *rchild;
} BiTNode, *BiTree;
// 栈的数据结构
typedef struct stack
{
BiTree top[STACK_INIT_SIZE];
int stacksize;
}SqStack;
// 二叉树的数据结构
//构造一个空栈S
Status InitStack(SqStack &S)
{
S.stacksize =0;
return OK;
}
// 插入元素e为新的栈顶元素
Status Push(SqStack &S, BiTree e)
{
S.top[S.stacksize] =e;
S.stacksize++;
return OK;
}
// 若栈S为空，则返回TRUE，否则返回FALSE
Status IsStackEmply(SqStack S)
{
if(S.stacksize==0)
return TRUE;
else
return FALSE;
}
// 若栈不为空，则删除S的栈顶元素，用e返其值，并返回OK，否则返回ERROR
BiTree Pop(SqStack &S)
{
if(IsStackEmply(S))
return ERROR;
BiTree p=S.top[S.stacksize-1];
--S.stacksize;
return p;
}
// 按先序次序输入二叉树中结点的值(一个字符),#字符表示空树,构造二叉链表表示的二叉树T
Status CreateBiTree(BiTree& T)
{
char ch;
ch = getchar();
getchar();//这里注意，如果是在VC6.0的话就需要，
//如果是在VS2010的话就不需要，这里是因为回车的原因，用来吃掉回车符
if (ch == '#')
T = NULL;
else
{
if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
}
// 递归前序遍历
Status RecursivePreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
if (T)
{
Visit(T->data);
RecursivePreOrderTraverse(T->lchild, Visit);
RecursivePreOrderTraverse(T->rchild, Visit);
}
return OK;
}
//递归中序遍历
Status RecursiveInOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
if(T)
{
RecursiveInOrderTraverse(T->lchild,Visit);
Visit(T->data);
RecursiveInOrderTraverse(T->rchild,Visit);
}
return OK;
}
//递归后序遍历
Status RecursivePostOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
if(T)
{
RecursivePostOrderTraverse(T->lchild,Visit);
RecursivePostOrderTraverse(T->rchild,Visit);
Visit(T->data);
}
return OK;
}
// 非递归前序遍历
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
BiTree p;
BiTree pre;
SqStack S;
p = T;
InitStack(S); //初始化栈
while (p
[解决办法]
(!IsStackEmply(S))) //当前子树未处理完
{
if (p) //当前未遇空结点
{
if (!Visit(p->data)) //处理当前子树根结点
return ERROR; //处理当前子树根结点时出错
Push(S, p); //结点压栈
p = p->lchild; //继续向左子树前进
}
else
{
pre=Pop(S);
p = pre->rchild; //弹出栈顶结点，处理其右子树
}
}
return OK;
}
Status Visit(TElemType e)
{
printf("%c ", e);
return OK;
}
int main()
{
BiTree T;
CreateBiTree(T);
printf("先序递归遍历结果:");
RecursivePreOrderTraverse(T, Visit);
printf("\n");
printf("先序非递归遍历结果:");
PreOrderTraverse(T, Visit);
printf("\n");
printf("递归中序遍历为:");
RecursiveInOrderTraverse(T,Visit);
printf("\n");
printf("递归后序遍历为:");
RecursivePostOrderTraverse(T,Visit);
printf("\n");
return 0;
}
#include <stdio.h>
#define MAX_VERTEX_NUM 20
#define INFINITY 127 //最大值
typedef char VertexType;
typedef struct Queue
{
int data;
struct Queue *link;
};
struct Queue *head=NULL,*tail=NULL;
typedef char VertexType;
typedef enum GrahpKind
{
DG,DN,UDG,UDN //分别为有向图，有向网，无向图，无向网
};
typedef struct ArcCell
{
int adj;
int *Info;
};
typedef struct MGraph
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
struct ArcCell AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//领接矩阵
int vexnum,arcnum; //图的当前顶点或弧数
enum GraphKind kind; //图的种类标志
};
int Visit[MAX_VERTEX_NUM];
struct MGraph graph;
struct MGraph *CreateAdjMatrixDG() //以领接矩阵构造有向图
{
struct MGraph *G;
int LocateVex(struct MGraph *G,VertexType c);
int i,j,k;
VertexType v1,v2;
G=&graph;
printf("请输入结点数目\n");
scanf("%d",&G->vexnum);
printf("请输入弧的数目\n");
scanf("%d",&G->arcnum);
G->kind=DG;
for (i=0;i<G->vexnum;i++)//初始化顶点信息
{
printf("请输入顶点信息\n");
scanf("\n%c",&G->vexs[i]);
}
for(i=0;i<MAX_VERTEX_NUM;i++)
for(j=0;j<MAX_VERTEX_NUM;j++)
G->AdjMatrix[i][j].adj=INFINITY;//初始化领接矩阵
for(i=0;i<G->arcnum;i++)
{
printf("请输入弧尾\n");
scanf("\n%c",&v1);
printf("请输入弧头\n");
scanf("\n%c",&v2);
k=LocateVex(G,v1);
j=LocateVex(G,v2);
G->AdjMatrix[k][j].adj=1;
}
return G;
}
void BFSTraverse(struct MGraph *G)//广度优先遍历
{
int i,w,u;
void EnQueue(int data);
int DeQueue();
for(i=0;i<G->vexnum;i++)
Visit[i]=0;
for(i=0;i<G->vexnum;i++)
{
if(!Visit[i])
{
printf("%c->",G->vexs[i]);
Visit[i]=1;
EnQueue(i);
while(head!=NULL)
{
u=DeQueue();
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
{
if(!Visit[w])
{
Visit[w]=1;
printf("%c->",G->vexs[w]);
EnQueue(w);
}
}
}
}
}
}
void DFS (struct MGraph *G,int v)
{
int w;
int NextAdjVex(struct MGraph *G,int i,int w);
int FirstAdjVex(struct MGraph *G,int i);
if(!Visit[v])
printf("%c->",G->vexs[v]);
Visit[v]=1;
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if(!Visit[w])
DFS(G,w);
}
}
void DFSTraverse(struct MGraph *G)
{
void DFS (struct MGraph *G,int v);
int i;
for (i=0;i<G->vexnum;i++)
Visit[i]=0;
for(i=0;i<G->vexnum;i++)
DFS(G,i);
}
int LocateVex(struct MGraph *G,VertexType c)
{
int i;
for(i=0;i<G->vexnum;i++)
{
if(G->vexs[i]==c)
break;
}
return i;
}
int NextAdjVex(struct MGraph *G,int i,int w)//找到领接的下一个顶点,i代表当前结点在数组中的位置
{
int j;
if(w==G->vexnum-1)
return -1;
else
{
for (j=w+1;j<=G->vexnum-1;j++)
{
if(G->AdjMatrix[i][j].adj==1)
return j;
}
}
return -1;
}
int FirstAdjVex(struct MGraph *G,int i)//找到领接的下一个顶点,i代表当前结点在数组中的位置
{
int j;
for(j=0;j<G->vexnum;j++)
{
if(G->AdjMatrix[i][j].adj==1)
return j;
}
return -1;
}
void EnQueue(int data)
{
struct Queue *node;
node=(struct Queue *)malloc(sizeof(struct Queue));
if(node==NULL)
{
printf("Space allocated failed\n");
exit(0);
}
if(head==NULL)
{
head=node;
tail=node;
node->data=data;
node->link=NULL;
}
else
{
tail->link=node;
node->link=NULL;
node->data=data;
tail=node;
}
}
int DeQueue()
{
struct Queue *temp=NULL;
int c;
if(head==NULL)
{
printf("队列为空，不能出队\n");
return -1;
}
else
{
temp=head;
c=temp->data;
head=head->link;
free(temp);
return c;
}
}
void main ()
{
struct MGraph *G;
struct MGraph *CreateAdjMatrixDG();
void DFSTraverse(struct MGraph *G);
G=CreateAdjMatrixDG();
DFSTraverse(G);
printf("\n");
BFSTraverse(G);
printf("\n");
}
#include <iostream>
#define MAX_SIZE 16
#define INFINITY 10240
using namespace std;
bool buildGraph(int graph[MAX_SIZE][MAX_SIZE],int &n);//build a new graph
bool dijkstra(const int graph[MAX_SIZE][MAX_SIZE],const int n,int *dist,int *road,const int sourcePoint);
void floyed(int dist[MAX_SIZE][MAX_SIZE],const int graph[MAX_SIZE][MAX_SIZE],int path[MAX_SIZE][MAX_SIZE],const int n);
//dijkstra agrilothm
void check(const int graph[MAX_SIZE][MAX_SIZE],const int n);
void printPath_mid(int path[MAX_SIZE][MAX_SIZE],int i,int j);
void printPath_pre(int road[MAX_SIZE],int start,int end);
int main()
{
int chart[MAX_SIZE][MAX_SIZE];//all initialize to 0
int num = 0;//store the totall point
//initialze to a big integer
for (int i=0;i<MAX_SIZE;i++)
for (int j=0;j<MAX_SIZE;j++)
chart[i][j] = INFINITY;
//build a new graph , store it in chart .
buildGraph(chart,num);
check(chart,num);
return 0;
}
void check(const int graph[MAX_SIZE][MAX_SIZE],const int n)
{
char djk_floy;
while (djk_floy != 'Q' && djk_floy != 'q')
{
int start = 1;
cout<<"\n\t\t\tPlease input your choice \n\t\t\tuse Dijkstra or Floyed(D/F)?:";
cin>>djk_floy;
switch (djk_floy)
{
case 'D':
case 'd':
int road[MAX_SIZE];
int distance[MAX_SIZE];
while (start != -1)
{
//input the choice to computer the shortest distacce
cout<<"\n\n\n\t\t\tplease input the start point:\n\t\t\t";
cin>>start;
system("cls");
if (start<0
[解决办法]
start>=n)
{
//if input error ,again
cout<<"\n\n\nInvalide input of start point !:\n";
continue ;
}
dijkstra(graph,n,distance,road,start);
cout<<"\n\n\n\n\t\tthe shortest distance from "<<start<<" to others is :\n\t";
for (int k=0;k<n;k++)//print the menu .
cout<<"\t"<<k;
cout<<"\n\t\t";
for (int a=0;a<n;a++)//print the brefe menu
if (distance[a] < INFINITY) cout<<distance[a]<<"\t";
else cout<<"∞\t";
cout<<endl;
int tmp;
for (int k = 0;k < n;k++)
{
//print the shortest road !
tmp = road[k];
cout<<"\nThe road from "<<start<<" to "<<k<<" is :\t D( ";
if (distance[k] < INFINITY) cout<<distance[k]<<" ) \t";
else cout<<"∞ ) \t";
cout<<start<<" -> ";
printPath_pre(road,start,k);
/*for (;tmp != start;)
{
//print the middle path
cout<<tmp<<" <- ";
tmp = road[tmp];
}*/
cout<<k<<endl;
}
}
break;
case 'F':
case 'f':
int dist[MAX_SIZE][MAX_SIZE];
int path[MAX_SIZE][MAX_SIZE];
floyed(dist,graph,path,n);
while (start != -1)
{
//input the choice to computer the shortest distacce
cout<<"\n\n\n\t\t\tplease input the start point:\n\t\t\t";
cin>>start;
system("cls");
if (start<0
[解决办法]
start >=n)
{
//if input error ,again
cout<<"\n\n\nInvalide input of start point !:\n";
continue ;
}
//use the dijkstra agrilothm to computer
cout<<"\n\n\n\n\t\tthe shortest distance from "<<start<<" to others is :\n\t";
for (int k=0;k<n;k++)//print the menu .
cout<<"\t"<<k;
cout<<"\n\t";
for (int a=0;a<n;a++)//print the menu .
if (dist[start][a] < INFINITY) cout<<dist[start][a]<<"\t";
else cout<<"∞\t";
cout<<endl;
for (int k = 0;k < n;k++)//print the shortest distance .
{
cout<<"\nThe shortest roat from "<<start<<" to "<<k<<" is : ( ";
if (dist[start][k] < INFINITY) cout<<dist[start][k]<<" )\t";
else cout<<"∞ )\t";
cout<<start<<" -> ";
printPath_mid(path,start,k);
cout<<k<<endl;
}
}
break;
case 'Q':
case 'q':
break;
default:
system("cls");
cout<<"Input error ! exit";
}
}
}
//function : build a tree ,and change the totall number
//parement: the chart ,and the totall number
//return : if succeed ,then ,return true.else false
bool buildGraph(int graph[MAX_SIZE][MAX_SIZE],int &n)
{
int sum = -1;
cout<<"\n\n\n\n\n";
while (sum < 0
[解决办法]
sum > MAX_SIZE)
{
//错误处理，输入节点总数
cout<<"\t\t\tplease input the totall point :\n\t\t\t\t\t";
cin>>sum;
system("cls");
if (sum < 0
[解决办法]
sum > MAX_SIZE)
cout<<"\n\n\n\n\n\t\tInvalide input !"
"integer should between 0 to "<<MAX_SIZE<<endl;
}
n = sum;
int start = 1;//start point
int end = 0;//end poitn
int value = 0;//the value or the length
cout<<"\n\n\n\n\n\t\tInput the edges and the value(end by -1 * *)\n";
cout<<"\t\t\tfrist element:start\n\t\t\t"
"second element:end\n\t\t\tlastpoint:values"<<endl;
while (start != -1)
{
//loop
cout<<"edges :";
cin>>start>>end>>value;
if (start > -1 && start < MAX_SIZE && start != end)
if (end > -1 && end < MAX_SIZE)
{
//
graph[start][end] = value;
continue;
}
cout<<"\t\tsorry ! invalid input type ,please input again !\n";
}
system("cls");
cout<<"\n\n\n\t\t\tThe builded new graph is :\n\n\t";
for (int i=0;i< n;i++)
{
//loop to print the grath.
for (int j=0;j< n;j++)
if (graph[i][j] < INFINITY)
cout<<graph[i][j]<<"\t";
else
cout<<"∞\t";
cout<<endl<<"\n\t";
}
return true;
}
//function : computer the shortest distance of two road
//parement : the grath ,totall number of point
// , the distination array to store the distance
//return type :if succeed ,then ,return true.else false
bool dijkstra(const int graph[MAX_SIZE][MAX_SIZE],const int n,int *dist,int *road,const int sourcePoint)
{
bool source[MAX_SIZE];//initialize the frist point to
int tmp_shortest = sourcePoint;
for (int i=0;i < n;i++)
{
source[i] = false ;//initialize to false
dist[i] = graph[sourcePoint][i];//initialize to the frist row
road[i] = sourcePoint;
}
source[sourcePoint] = true;//the source point ,add to the S
for (int i = 0;i < n; i++)
{
for (int j = 0;j < n; j++)//find the shortest dist from the V -S
if (source[j] == false)
if (dist[j] <= dist[tmp_shortest])
tmp_shortest = j;
source[tmp_shortest] = true;//add it to the source ,S
int tmp=0;
for (int k= 0;k < n;k++)
{
if (source[k] == false)
{
//update the distance !
if (dist[k] > (dist[tmp_shortest] + graph[tmp_shortest][k]) )
{
dist[k] = dist[tmp_shortest] + graph[tmp_shortest][k];
road[k] = tmp_shortest;
}
tmp = k;
}
}
tmp_shortest = tmp;
}
//for(
return true ;
}
//function : computer the shortest distance between each two road
//parement : the array to store the distance the grath ,totall number of point
// , the distination array to store the distance
//return type :void
void floyed(int dist[MAX_SIZE][MAX_SIZE],const int graph[MAX_SIZE][MAX_SIZE],int path[MAX_SIZE][MAX_SIZE],const int n)
{
//initialize
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
dist[i][j] = graph[i][j];
path[i][j] = -1;
}
for (int k=0;k<n;k++)
{
//frist loop
for (int i=0;i<n;i++)//second loop
for (int j=0;j<n;j++)//last loop
if (dist[i][k]+dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k]+dist[k][j];
path[i][j] = k;
}
//update the shortest distance if there is a middle point .
}
}
//function : print the point between i and j; 递归打印所有中间节点
//parement : 路劲表path，两个节点i ,j。
//return type :void
void printPath_mid(int path[MAX_SIZE][MAX_SIZE],int i,int j)
{
int tmp = path[i][j];
if (tmp != -1)
{
printPath_mid(path,i,tmp);
cout<<tmp<<" -> ";
printPath_mid(path,tmp,j);
}
return ;
}
//function : print the point between i and j; 递归打印所有中间节点
//parement : 路劲表path，下标。
//return type :void
void printPath_pre(int road[MAX_SIZE],int start,int end)
{
if(road[end] != start)
{
printPath_pre(road,start,road[end]);
cout<<road[end]<<" -> ";
}
}
