伤城文章网 > 韩语学习 > 2013年吉林省数据库入门摘要

2013年吉林省数据库入门摘要


1、设 T 是一棵满二叉树,编写一个将 T 的先序遍历序列转换为后序遍历序列的递归算法。 2、约瑟夫环问题(Josephus 问题)是指编号为 1、2、?,n 的 n(n>0)个人按顺时针方向 围坐成一圈,现从第 s 个人开始按顺时针方向报数,数到第 m 个人出列,然后从出列的下一 个人重新开始报数,数到第 m 的人又出列,?,如此重复直到所有的人全部出列为止。现要 求采用循环链表结构设计一个算法,模拟此过程。 #include<stdlib.h> typedef int datatype; typedef struct node {datatype data; struct node *next; }listnode; typedef listnode *linklist; void jose(linklist head,int s,int m) {linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1 为报数的起点*/ while (count!=s) /*找初始报数起点*/ {pre=k1; k1=k1->next; count++; } while(k1->next!=k1) /*当循环链表中的结点个数大于 1 时*/ { p=k1; /*从 k1 开始报数*/ count=1; while (count!=m) /*连续数 m 个结点*/ { pre=p; p=p->next; count++; } pre->next=p->next; /*输出该结点,并删除该结点*/ printf("%4d",p->data); free(p); k1=pre->next; /*新的报数起点*/ } printf("%4d",k1->data); /*输出最后一个结点*/ free(k1); } main() {linklist head,p,r; int n,s,m,i; printf("n="); scanf("%d",&n); printf("s=");

scanf("%d",&s); printf("m=",&m); scanf("%d",&m); if (n<1) printf("n<0"); else {/*建表*/ head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n; r=head; for (i=n-1;i>0;i--) /*建立剩余 n-1 个结点*/ { p=(linklist)malloc(sizeof(listnode)); p->data=i; p->next=head; head=p; } r->next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ } } 3、 假设以邻接矩阵作为图的存储结构, 编写算法判别在给定的有向图中是否存在一个简单有 向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可) 。 (注:图中不存在顶点 到自己的弧) 有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但 其邻接点未访问完;已访问且其邻接点已访问完。下面用 0,1,2 表示这三种状态。前面已提 到,若 dfs(v)结束前出现顶点 u 到 v 的回边,则图中必有包含顶点 v 和 u 的回路。对应程 序中 v 的状态为 1,而 u 是正访问的顶点,若我们找出 u 的下一邻接点的状态为 1,就可以输 出回路了。 void Print(int v,int start ) //输出从顶点 start 开始的回路。 {for(i=1;i<=n;i++) if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i) ,且顶点 i 的状态为 1。 {printf(“%d”,v); if(i==start) printf(“\n”); else Print(i,start);break;}//if }//Print void dfs(int v) {visited[v]=1; for(j=1;j<=n;j++ ) if (g[v][j]!=0) //存在边(v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2; }//dfs void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited 数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0;

for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i); }//find_cycle


搜索更多“2013年吉林省数据库入门摘要”

网站地图

All rights reserved Powered by 伤城文章网 5xts.com

copyright ©right 2010-2021。
伤城文章网内容来自网络,如有侵犯请联系客服。zhit325@126.com