#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
//十字链表存储有向图
#define MAX_VERTEX_NUM 20
typedef int VertexType;
typedef struct ArcBox
{
int tail_vertex;
int head_vertex;
ArcBox *tail_link;//共一个tail的下一条边
ArcBox *head_link;//共一个head的下一条边
// InfoType *info;
int weight;
} ArcBox, *PArcBox;
typedef struct VexNode
{
VertexType data;
ArcBox *firstin;//以该点为head
ArcBox *firstout;//以该点为tail
} VexNode;
typedef struct OLGraph
{
VexNode xlist[MAX_VERTEX_NUM];
int vernum, arcnum;
} OLGraph;
typedef struct AArr
{
int tail;
int head;
// InfoType *info;
} AArr;
//利用参数使得可以在别处定义输入数据，而不是象书上那样scanf逐个输入
void CreateDG(OLGraph &g, int vnum, int anum,AArr aarr[])
{
g.vernum = vnum;
g.arcnum = anum;
int i;
for(i=0; i<vnum; i++)
{
g.xlist[i].data = i;
g.xlist[i].firstin = NULL;
g.xlist[i].firstout = NULL;
}
for(i=0; i<anum; i++)
{
int tail = aarr[i].tail;
int head = aarr[i].head;
//将边插入对应的两个链表中，头结点之后
PArcBox parcbox = (PArcBox) malloc(sizeof(ArcBox));
parcbox->head_vertex = head;
parcbox->tail_vertex = tail;
parcbox->head_link = g.xlist[head].firstin;
g.xlist[head].firstin = parcbox;
parcbox->tail_link = g.xlist[tail].firstout;
g.xlist[tail].firstout = parcbox;
}
}
//得到G,调用上面的方法
void GetDG(OLGraph &g)
{
// 1 3
// 0 4
// 2
int vnum = 5;
int anum = 7;
AArr aarr[7]={0,1,0,2,0,4,1,4,1,3,2,4,4,3};
CreateDG(g,vnum,anum,aarr);
}
int GetFirstOutAdj(OLGraph &g, int vex)
{
PArcBox tem = g.xlist[vex].firstout;
if(tem == NULL)
{
return -1;
}
else
{
return tem->head_vertex;
}
}
int GetNextOutAdj(OLGraph &g, int tail_vex, int cur)
{
PArcBox tem = g.xlist[tail_vex].firstout;
while(tem!=NULL && tem->head_vertex!=cur)
{
tem = tem->tail_link;
}
if(tem->tail_link != NULL)
{
return tem->tail_link->head_vertex;
}
else
{
return -1;
}
}
//在进入这个函数之前已经保证肯定没访问过，所以不需要再在函数内部判断了
//注意visited单独用if判断，另外就是对于几个函数接口的理解，数据结构的熟悉
void DFS(OLGraph &g, int vex, int visited[])
{
visited[vex] = 1;
printf("%d\t", g.xlist[vex].data);
for(int tem=GetFirstOutAdj(g,vex); tem>=0; tem=GetNextOutAdj(g,vex,tem))
{
if(visited[tem] == 0)
{
DFS(g, tem, visited);
}
}
}
//DFS的外层封装
//void DFSTraverse(OLGraph &g, int *visited)
//从这个例子知道了变量作用域极小化的意义和指针作为参数传递的注意事项
//一定要杜绝未定义的指针变量，一定要保证在某个地方让它有所指，如果在外部只是一个声明
//则应该在函数内部做改变，所以应该用引用或者指向指针的指针传递
void DFSTraverse(OLGraph &g)
{
int i;
int *visited = (int*) malloc(g.vernum*sizeof(int));
for(i=0; i<g.vernum; i++)
{
visited[i] = 0;
}
for(i=0; i<g.vernum; i++)
{
if(visited[i] == 0)
{
DFS(g, i, visited);
}
}
delete visited;
}
//////////////////////////////////////////////
typedef int QueueType;
typedef struct QNode
{
QueueType data;
QNode *next;
} QNode, *PQNode, *MyQueue;
void InitQueue(MyQueue &pqnode)
{
//构造头结点就相当于初始化了
pqnode = (MyQueue) malloc(sizeof(QNode));
pqnode->data = -1;
pqnode->next = NULL;
}
void EnQueue(MyQueue q, QueueType qt)
{
PQNode insert_ele = (PQNode) malloc(sizeof(QNode));
insert_ele->data = qt;
insert_ele->next =NULL;
PQNode tem;
for(tem = q; tem->next!=NULL; tem=tem->next)
{
}
tem->next = insert_ele;
}
QueueType DeQueue(MyQueue q)
{
if(q->next == NULL)
{
printf("Queue is empty!\n");
getchar();
exit(1);
}
else
{
PQNode tem =q->next;
QueueType qt = tem->data;
q->next = tem->next;
free(tem);
return qt;
}
}
int IsEmptyQueue(MyQueue q)
{
if(q->next == NULL)
{
return 1;
}
else
{
return 0;
}
}
//////////////////////////////////////////////
//关键是访问时机把握：入队而不是出队,另外与递归算法不同的是用队是否为空来驱动
//其实是visited的改变时机，入队就表示已经访问过了，无论是否打印，与后序遍历类似
void BFSTraverse(OLGraph &g)
{
int i;
MyQueue queue;
InitQueue(queue);
int *visited = (int*) malloc(g.vernum*sizeof(int));
for(i=0; i<g.vernum; i++)
{
visited[i] = 0;
}
//外面的大循环是考虑了子图
for(i=0; i<g.vernum; i++)
{
if(visited[i] == 0)
{
EnQueue(queue, i);
visited[i] = 1;
// printf("%d\t",g.xlist[i].data);
while(!IsEmptyQueue(queue))
{
int tem = DeQueue(queue);
printf("%d\t",g.xlist[tem].data);
for(int adj=GetFirstOutAdj(g,tem); adj>=0; adj=GetNextOutAdj(g,tem,adj))
{
if(visited[adj]==0)
{
EnQueue(queue, adj);
visited[adj] = 1;
// printf("%d\t",g.xlist[adj].data);
}
}
}
}
}
delete visited;
}
/////////////////////////////////////////////Dijkstra
typedef struct WeightAArr
{
int tail;
int head;
int weight;
} WeightAArr;
void CreateDGWeight(OLGraph &g, int vnum, int anum, WeightAArr waarr[])
{
g.vernum = vnum;
g.arcnum = anum;
int i;
for(i=0; i<vnum; i++)
{
g.xlist[i].data = i;
g.xlist[i].firstin = NULL;
g.xlist[i].firstout = NULL;
}
for(i=0; i<anum; i++)
{
int tail = waarr[i].tail;
int head = waarr[i].head;
//将边插入对应的两个链表中，头结点之后
PArcBox parcbox = (PArcBox) malloc(sizeof(ArcBox));
parcbox->head_vertex = head;
parcbox->tail_vertex = tail;
parcbox->weight = waarr[i].weight;
//这里与十字链表有所不同，没有inout之分，head，tail只是为了区分，没有含义
parcbox->head_link = g.xlist[head].firstin;
g.xlist[head].firstin = parcbox;
parcbox->tail_link = g.xlist[tail].firstout;
g.xlist[tail].firstout = parcbox;
}
}
int GetArcWeight(WeightAArr *arr, int len, int i, int j)
{
int k;
for(k=0; k<len; k++)
{
if(j==arr[k].head&&i==arr[k].tail)
{
return arr[k].weight;
}
}
if(k == len)
{
return -1;
}
}
//这个程序结构与PRIM是一致的，判断条件不同，有一个累加而已，另外路径处理使用了vector
//说到底也是一种动态规划，每个结点保持当前情况下到该点的最短距离，路径递增与鸽巢理论
void DIJ(OLGraph &g, WeightAArr warr[])
{
const int MAX = 1000;
int *cost = new int[g.vernum];
int *visited = new int[g.vernum];
vector<int> *path = new vector<int>[g.vernum];//0位元素无效，从1开始
// WeightAArr *min_tree = new WeightAArr[g.vernum-1];
int i;
for(i=0; i<g.vernum; i++)
{
cost[i] = MAX;
visited[i] = 0;
}
visited[0] = 1;
int w;
for(w=GetFirstOutAdj(g,0); w>=0; w=GetNextOutAdj(g,0,w))
{
cost[w] = GetArcWeight(warr,g.arcnum, 0, w);
path[w].push_back(0);
}
for(i=1; i<g.vernum; i++)
{
int min_cost = MAX+1;
int min_vex;
for(int j=1; j<g.vernum; j++)
{
if(cost[j] < min_cost && visited[j]==0)
{
min_cost = cost[j];
min_vex = j;
}
}
visited[min_vex] = 1;
//在末尾存储对应该点的min_cost
path[min_vex].push_back(min_cost);
//利用prim的架构，计算cost无误，在计算path时有错
for(w=GetFirstOutAdj(g,min_vex); w>=0; w=GetNextOutAdj(g,min_vex,w))
{
if((GetArcWeight(warr,g.arcnum, min_vex, w)+cost[min_vex])<cost[w] && visited[w]==0)
{
cost[w] = GetArcWeight(warr,g.arcnum, min_vex, w)+cost[min_vex];
//如果有变化需要把原路径清除，完全更新一遍！
path[w].erase(path[w].begin(),path[w].end());
for(vector<int>::iterator it=path[min_vex].begin(); it!=path[min_vex].end()-1; ++it)
{
path[w].push_back(*it);
}
path[w].push_back(min_vex);
}
}
}
for(i=1; i<g.vernum; i++)
{
printf("path of %d:\t",i);
for(vector<int>::iterator it=path[i].begin(); it!=path[i].end(); ++it)
{
printf("%d ", (*it));
}
printf("\n");
}
delete []path;
}
//////////////////////////////////////////////////////////////TopologicalSort
void TopologicalSort(OLGraph &g)
{
int vnum = 6;
int anum = 8;
AAr
DS.rar_ trie_TRIE_site:www.pudn.com_二叉树 注释_图 数据结构
版权申诉
97 浏览量
2022-09-20
15:03:31
上传
评论
收藏 26KB RAR 举报
DS.rar （11个子文件） 
ThreadBiTree.cpp 6KB BitTree.cpp 11KB Sort.cpp 7KB map_udg.cpp 10KB Trie.cpp 5KB HuffmanTree.cpp 5KB SearchBST.cpp 6KB
www.pudn.com.txt 218B KeyTree.cpp 9KB map_dg.cpp 16KB SortRadix.cpp 4KB资源评论
