变换为(xp， xp＋1, ? , xn-1 ,x0 , x1,?, xp-1)。
8、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;
AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)
{visited [v]=1; num++; //访问的顶点数＋1
if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p)
{if (visied[p->adjvex]==0) dfs (p->adjvex); p=p->next;} //while
visited[v]=0; num--; //恢复顶点v }//dfs
void JudgeRoot()
//判断有向图是否有根，有根则输出之。 {static int i ;
for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
9、约瑟夫环问题（Josephus问题）是指编号为1、2、?，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，?，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。 #include
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(\ free(p);
k1=pre->next; /*新的报数起点*/ }
printf(\输出最后一个结点*/ free(k1); }
main()
{linklist head,p,r; int n,s,m,i; printf(\ scanf(\ printf(\ scanf(\ printf(\ scanf(\
if (n<1) printf(\ 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); /*调用函数*/ } }
10、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0 typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）
// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）
{ Judgebst（t->llink,flag）；// 中序遍历左子树
if（pre==null）pre=t；// 中序遍历的第一个结点不必判断
else if（pre->data
11、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。 void Platform (int b[ ], int N)
//求具有N个元素的整型数组b中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i {while(i if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)； }// Platform 12、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧） 有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用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 13、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。 14、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。 void Platform (int b[ ], int N) //求具有N个元素的整型数组b中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i {while(i if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)； }// Platform 15、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。 typedef struct {BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack; stack s[],s1[];//栈，容量够大 BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0) {while(bt!=null &&bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。 for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t; for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝ while(top!=0 && s[top].tag==1) top--; //退栈 if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//ｑ、p无公共祖先 ｝//结束Ancestor
相关推荐：
loading