手机版

2010年西藏自治区数据要领基础(11)

发布时间:2021-06-11   来源:未知    
字号:

2010年西藏自治区数据要领基础

}
else
{ s=q; /*找与P结点值相同的结点*/
q=q->next;
}
p=p->next;
}
return head;
}

40、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。

41、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。
42、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量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<t->data)pre=t;//前驱指针指向当前结点
else{flag=flase;} //不是完全二叉树
Judgebst (t->rlink,flag);// 中序遍历右子树
}//JudgeBST算法结束


43、约瑟夫环问题(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

2010年西藏自治区数据要领基础(11).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
×
二维码
× 游客快捷下载通道(下载后可以自由复制和排版)
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
注:下载文档有可能出现无法下载或内容有问题,请联系客服协助您处理。
× 常见问题(客服时间:周一到周五 9:30-18:00)