我经常来逛数据结构, 这个版面里的有些问题是重复的.
就是大家很多都问同种的问题. 所以我建议,版主能把几个数据结构的常见题目,整理一下.
做为一个帖子发出来..做为置顶帖,这样如果有不懂的,可以直接看.. 不用再发帖求救了..比较方便.
像这几个帖子都可以用来借鉴的.
二叉排序树的建立,求叶结点个树,高度,非递归前序,非递归中序,非递归后序遍历
http://bbs.bc-cn.net/bbs/dispbbs.asp?boardID=179&ID=15105&page=1
Huffman编码译码问题.
http://bbs.bc-cn.net/bbs/dispbbs.asp?boardID=179&ID=16516&page=1
最短路径的两种求法
http://bbs.bc-cn.net/bbs/dispbbs.asp?boardID=179&ID=18138&page=2
#include<string.h> #include<stdio.h> #define MaxVertexNum 100 #define INFITY 200 typedef int EdgeType; /*定义邻接边的节点*/ typedef char VertexType; typedef int pathMatrix; typedef int distancMatrix; typedef struct { VertexType vexs[MaxVertexNum]; EdgeType edges[MaxVertexNum][MaxVertexNum]; int n,e; }MGraph; typedef struct{ char data; char name[20]; int number; char introduce[60]; } vertex;
void shortest_path(MGraph *G,pathMatrix p[MaxVertexNum][MaxVertexNum],distancMatrix D[MaxVertexNum][MaxVertexNum]) { int v,w,u; int i,j; for(v=0;v<G->n;++v) for(w=0;w<G->n;++w) D[v][w]=G->edges[v][w]; /* 把边权值的邻接矩阵赋给D数组*/ if(D[v][w]<INFITY && D[v][w]!=0) { p[v][w]=v; elseif(v!=w) p[v][w]=-2; else(v==w) p[v][w]=-1; /*初始化P数组*/ } for(u=0;u<G->n;++u) /*对路径的相加*/ for(v=0;v<G->n;++v) for(w=0;w<G->n;++w) if(D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; /*当v w之间有一点u使用vu的长度加上uw的长度小于 vw的长度, 把相应的P改变,同时改变D数组*/ p[v][w]=u; } if(i>=10||i>=0) { printf("please input you choice between i and j:\n"); printf("对不起.您输入的景点不存在, 请重新输入.\n"); /*本题我只定义了六个结点*/ } else { printf("you choice is between " printf("%d",G->vexs[i]); printf("---and---"); printf("%d",G->vexs[j]); printf("end"); } if(p[i][j]>=0) {w=j; /*输出部分*/ printf("您所选择的两景点间的长度为:"); printf("%d",D[i][j]); printf("end"); printf("您所选择的景点的代号为:"); printf("%d",G->vexs[j]);
printf("<--"); while(p[i][w]!=i) { printf("%d",G->vexs[p[i][w]]); w=p[i][w]; printf("<--"); }
printf("%d",G->vexs[i]): printf("end");
} else printf("sorry,you choice is not exist.plese try again.\n"); } }
void start() { printf("********************************************\n"); printf(" 校园导游图 \n"); printf(" 台州职业技术学院 计应0431 131304101号 陈莺莺\n"); printf(" *********************************************\n"); printf("请选择操作:\n"); printf("0.退出\n"); printf("1.任意两个景点间的最短路径\n"); printf("2.各个景点的讯息\n"); printf("3.用户手册\n"); }
void Readme() { printf("**********用户手册***************************\n"); printf("****查询任意两个景点间的最短路径****\n"); printf("请注意:共有六个景点可供选择,数字:0-5\n"); printf"输入您要查询的两个景点的数字, 例如0回车5\n");
printf("**********各个景点的讯息*************\n"); printf("1.请输入您要查询的景点的编号\n"); printf("2.例如.. 001 002--006\n"); printf("**********感谢你的使用!^_^****************\n"); printf("end"); }
main() {MGraph *G; int i,j,k,w,m,number_2,l; int n,e; vertex t[10]; G=(MGraph *)malloc(sizeof(MGraph)); G->n=10; /*初始化关于G图的各个讯息*/ G->e=19; /*初始化边数跟顶点数*/ G->vexs[0]='a';G->vexs[1]='b'; G->vexs[2]='c'; G->vexs[3]='d'; G->vexs[4]='e'; G->vexs[5]='f'; G->vexs[6]='g'; G->vexw[7]='h'; G->vexs[8]='i';G->vexs[9]='j'; /* 建立顶点讯息*/
for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) { if(i==j) G->edges[i][j]=0; else G->edges[i][j]=INFITY; /*顶点信息的矩阵 */ } G->edges[0][1]=20;G->edges[0][2]=10; G->edges[0][3]=20;G->edges[0][4]=30; G->edges[0][5]=100;G->edges[1][2]=50; G->edges[1][7]=15;G->edges[1][8]=20; G->edges[2][3]=50;G->edges[2][7]=80; G->edges[3][4]=10;G->edges[3][5]=10; G->edges[3][6]=10;G->edges[3][9]=50; G->edges[4][5]=20;G->edges[4][6]=60; G->edges[7][8]=10;G->edges[7][9]=15; G->edges[8][9]=20;/*建立图中所有的连接点跟权值*/
pathMatrix p[MaxVertexNum][MaxVertexNum]; distancMatrix D[MaxVertexNum][MaxVertexNum];
l=-1;
t[0].data='a'; /*10个景点的信息 */ strcpy(t[0].name,"class"); t[0].number=001; /*班级 */ strcpy(t[0].introduce,"all of the lesson are held at here!!"); t[1].data='b'; strcpy(t[1].name,"lab"); t[1].number=002; /*图书馆*/ strcpy(t[1].introduce,"we do very experience at here!!"); t[2].data='c'; strcpy(t[2].name,"garden"); t[2].number=003; /*花园 */ strcpy(t[2].introduce,"we can wander after dinner at here ohch!!"); t[3].data='d'; strcpy(t[3].name,"playground"); t[3].number=004; /*操场 */ strcpy(t[3].introduce,"it is a field to play togerther!!"); t[4].data='e'; strcpy(t[4].name,"Bprivacy"); t[4].number=005; /*B公寓 */ strcpy(t[4].introduce,"it is a good place for lover!!"); t[5].data='f'; strcpy(t[5].name,"door"); t[5].number=006; /*大门*/ strcpy(t[5].introduce,"you can see lots of fishes is door there!"); /*建立结点的各个讯息*/ t[6].data='g'; strcpy(t[6].name," Aroom"); t[6].number=007; /*A公寓*/ strcpy(t[6].ineroduce;"we are lived it!"); t[7].data='h'; strcpy(t[7].name;"shitang"); t[7].number=008; /*食堂 */ strcpy(t[7].introuce,"ta zai xue shao de zhong jian!"); t[8].data='i'; strcpy(t[8].name;"xing zhen lou"); t[8].number=009; /* 行政楼 */ strcpy(t[8].introuce,"shi lao shi men gong zuo de di fang!"); t[9].data='j'; strcpy(t[9].name;"dian da"); t[9].number=008; /*电大*/ strcpy(t[9].introuce,"wo men shi tong g ge di fang!");
start();
while(l!=0) { int l;
switch(l) { case 0: return; case 1: printf("您选择的是得知任意两个景点间的最短路径\n"); shortest_path(G,p,D);
l=-1; start(); break;
case 2:
printf("您选择的是各个景点的讯息"); printf("end"); printf("please input your choice:\n"); int number_2; if(number_2>=007) printf("对不起.您输入的景点不存在, 请重新输入.\n"); else{ for(i=0;i<6;i++) { if(t[i].number==number_2) {k=i; printf("the data is:"); printf("%d",t[k].data); printf("end"); printf("the name is:"); printf("%d"t[k].name); printf("end)"; printf("the introduction:"); printf("%d",t[k].introduce); printf("end"); } } } l=-1; start(); break;
case 3: printf("您选择的是用户手册\n"); printf("end"); Readme(); l=-1; start(); break;
default: printf("输入有误!请重新选择操作!\n"); start();
} }
}