中国宠物市场调查归纳总结报告　.doc

《中国宠物市场调查归纳总结报告　.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图的邻接表实现迪杰斯特拉算法（C语言）/*迪杰斯特拉算法（狄斯奎诺算法）解决的是从源点到其它所有顶点的最短路径问题*///算法实现：#include#include#defineMAX20#defineMAX_FLOAT_NUM1000/*最大浮点数（假设最大浮点数是1000）*/typedefintinfoType;/*定义边表结点权值的数据的数据类型*/typedefintvertexType;/*定义顶点结点上存储的数据的数据类型*///定义边表结点结构体typedefstructed

2、genode{intadjvertex;//边表结点域infoTypeinfo;//边表结点权值，这里存放的是其父结点到该结点的距离structedgenode*next;//指向下一个邻接点的指针域}EdgeNode;//定义顶点结点结构体typedefstructvertexnode{vertexTypeboolval;/*顶点结点域，这里存放的是该结点是否找到其距源顶点最短路径的标记，若找到最短路径，则该值为1，否则该值为0*/EdgeNode*firstedge;//边表头指针}VertexNode;typedefstr

3、uct{VertexNodeadjlist[MAX];/*邻接表*/intvertexNum;/*顶点数*/intedgeNum;/*边数*/}ALGraph;//adjacencylistgraph:邻接表/**************************************************************函数名称：CreateGraph函数功能：创建邻接表输入：顶点数vertexNum，边数edgeNum输出：指向已创建好的邻接表的指针*********************************

4、*****************************/ALGraph*CreateGraph(intvertexNum,intedgeNum){intk;EdgeNode*p;//声明图的邻接表ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));if(!G){G=NULL;}else{G->vertexNum=vertexNum;G->edgeNum=edgeNum;//建立顶点表for(k=0;kvertexNum;k++){G->adjlist[k].boolval=0;

5、/*boolval值判断该结点到源结点的距离是否是最短距离，是1表示已达最短距离，是0表示还没有达最短距离*/G->adjlist[k].firstedge=NULL;}//建立边表printf("请输入顶点、其邻接顶点和权值信息：");for(k=0;kedgeNum;k++){inti,j;infoTypeinfo;//表现的是边的关系，有多少对就有多少边，所以for循环次数为G->edgeNumscanf("%d,%d,%d",&i,&j,&info);if(i!=j){p=(EdgeNod

6、e*)malloc(sizeof(EdgeNode));p->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=p;p->adjvertex=j;p->info=info;}}}returnG;}/**************************************************************函数名称：dijkstra（迪杰斯特拉/迪斯奎诺）函数功能：实现迪杰斯特拉算法，找出每个顶点到源定点u的最短距离输入：邻接表指针G，源顶点u，记录每个顶点到

7、源顶点的最短距离的数组d[]，到源顶点的最短路径上的前方顶点编号p[]输出：记录每个顶点到源顶点的最短距离的数组d[]，到源顶点的最短路径上的前方顶点编号p[]**************************************************************/voiddijkstra(ALGraph*G,intu,intd[],intp[]){inti,j,t;EdgeNode*pnode;//初始化参数for(i=0;ivertexNum;i++){//G->adjlist[i].boolva

8、l=0;d[i]=MAX_FLOAT_NUM;p[i]=-1;}//更新源顶点直接子结点到源结点的最短距离if(!(pnode=G->adjlist[u].firstedge)){return;}while(pnode){d[pnode->adjvertex]=