知识库

2015西藏自治区C语言版入门

网站:知识库   来源:网络收集

1、我们用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(il) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k); }// Platform 2、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图 中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回 路(找到一条即可)。

(注:图中不存在顶点到自己的弧) 有向图判断回路要比无向图复杂。

利用深度优先遍历,将顶点分成三 类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问 完。

下面用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);}

2015自治区C语言版入门

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 3、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺 序连成一个单链表,表头指针为head。

二叉树按二叉链表方式存储, 链接时用叶子结点的右指针域来存放单链表指针。

分析你的算法的时、 空复杂度。

4、题目中要求矩阵两行元素的平均值按递增顺序排序,由于每行元素 个数相等,按平均值排列与按每行元素之和排列是一个意思。

所以应先 求出各行元素之和,放入一维数组中,然后选择一种排序方法,对该数 组进行排序,注意在排序时若有元素移动,则与之相应的行中各元素也 必须做相应变动。

void Translation(float *matrix,int n) //本算法对n×n的矩阵matrix,通过行变换,使其各行元素的平均值按 递增排列。

{int i,j,k,l; float sum,min; //sum暂存各行元素之和 float *p, *pi, *pk; for(i=0; i

2015自治区C语言版入门

{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;} sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和. }//if }//for i free(p); //释放p数组. }// Translation [算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动) 较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时 间复杂度为O(n2). 5、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用 llink-rlink法存储。

6、因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的 最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时, 则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至 后序遍历完毕,则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree p=bt,l[],s[]; //l, s是栈,元素是二叉树结点指针,l中保 留当前最长路径中的结点 int i,top=0,tag[],longest=0; while(p || top>0) { while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向 下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时,才查看 路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} //保留当前最长路径到l栈,记住最高栈顶指针,退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝 向下 }//while(p!=null||top>0) }//结束LongestPath 7、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序 插入到辅助向量d[1..n]前半部和后半部(注:向量d可视为循环表),

2015自治区C语言版入门

其原则为,先将r[l]赋给d[1],再从r[2] 记录开始分二路插入。

编写 实现二路插入排序算法。

8、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下 面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成 一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺 的语句。

#define MAX 100 typedef struct Node {char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv) { TNODE *root; if(argc<3) exit 0; strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); } TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr; char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______; for((2)_______ ; rposllink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } 9、 二叉树的层次遍历序列的第一个结点是二叉树的根。

实际上,层次 遍历序列中的每个结点都是“局部根”。

确定根后,到二叉树的中序序 列中,查到该结点,该结点将二叉树分为“左根右”三部分。

若左、右 子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中

2015自治区C语言版入门

只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根 或右子树的根。

这样,定义一个全局变量指针R,指向层次序列待处理 元素。

算法中先处理根结点,将根结点和左右子女的信息入队列。

然 后,在队列不空的条件下,循环处理二叉树的结点。

队列中元素的数据 结构定义如下: typedef struct { int lvl; //层次序列指针,总是指向当前“根结点”在层 次序列中的位置 int l,h; //中序序列的下上界 int f; //层次序列中当前“根结点”的双亲结点的指针 int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。

n是二 叉树的结点数 {if (n<1) {printf(“参数错误\n”); exit(0);} qnode s,Q[]; //Q是元素为qnode类型的队列,容量足够大 init(Q); int R=0; //R是层次序列指针,指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结 点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点 数据 for (i=0; ilchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==n-1) //根结点无右子树,遍历序列的1—n-1是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子 树有关信息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树

2015自治区C语言版入门

有关信息入队列 } while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子 树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++) if (in[i]==level[s.lvl]) break; p=(bitreptr)malloc(sizeof(binode)); //申请 结点空间 p->data=level[s.lvl]; p->lchild=null; p->rchild=null; // 填写该结点数据 if (s.lr==1) father->lchild=p; else father->rchild=p; //让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; //处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==s.h) {p->rchild=null; //处理无右子女 s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子 树有关信息入队列 } }//结束while (!empty(Q)) return(p); }//算法结束 10、矩阵中元素按行和按列都已排序,要求查找时间复杂度为 O(m+n),因此不能采用常规的二层循环的查找。

可以先从右上角 (i=a,j=d)元素与x比较,只有三种情况:一是A[i,j]>x, 这情况下 向j 小的方向继续查找;二是A[i,j]

否则,若下标已超出范围,则查找失败。

void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.

2015自治区C语言版入门

相关内容
  • 2015西藏自治区C语言版基础

    2015西藏自治区C语言版基础

    2015西藏自治区C语言版基础...

  • 2015年西藏自治区C++语言版入门

    2015年西藏自治区C++语言版入门

    2015年西藏自治区C++语言版入门...

  • 2015年西藏自治区C++语言版基础

    2015年西藏自治区C++语言版基础

    2015年西藏自治区C++语言版基础...

  • 2015年上半年西藏自治区C++语言版入门

    2015年上半年西藏自治区C++语言版入门

    2015年上半年西藏自治区C++语言版入门...

  • 2015西藏自治区C语言版高级

    2015西藏自治区C语言版高级

    2015西藏自治区C语言版高级...

  • 2015西藏自治区C语言版深入

    2015西藏自治区C语言版深入

    2015西藏自治区C语言版深入...

  • 2015西藏自治区C语言版加强

    2015西藏自治区C语言版加强

    2015西藏自治区C语言版加强...

  • 2015年上半年西藏自治区C++语言版基础

    2015年上半年西藏自治区C++语言版基础

    2015年上半年西藏自治区C++语言版基础...

  • 2015内蒙古自治区C语言版入门

    2015内蒙古自治区C语言版入门

    2015内蒙古自治区C语言版入门...

  • 2014西藏自治区C语言版入门

    2014西藏自治区C语言版入门

    2014西藏自治区C语言版入门...

  • 网友在搜
  • qt入门教程详细讲解版
  • kindle入门版
  • php从入门到精通第4版
  • c语言入门教学
  • c 入门经典第7版 pdf
  • c语言入门学习
  • c语言快速入门
  • 荣耀战魂入门版
  • 易语言入门教程完整版
  • 悉尼到堪培拉大巴 最短 小笑话 王俊凯动态桌面壁纸 teddy bear song denied party sy6288中文资料 linux 设置gbk编码 yotaphone2root纯净版 It will take before afriendly dolphin over the hill翻译 client翻译 绿袖子元若蓝歌词 sportivo 成都间奏吉他谱 kfr 35gw a8t920h a1 katerina hartlova 车 thinkpadt570和530 老师与学生 vr测试视频 beats耳机有电流声 college admission 下巴截骨前移 职工规章制度 武警8741部队历史 摄魂猎手凯隐技能 华硕p8p67evo步进 146t.com 杭州市文物局 脑梗塞中医治疗 css网站制作 漫威infinity war 彼尔德 matlab fill命令 suntrain cf帮帮福利中心抽奖 阿斯顿马丁db11车钥匙 studio怎么导入jar包 猪生的孩子图片 人体模特布娃娃 全集 jdk8 temporalfield 中国崛起的震撼欧洲 hyperx骇客神条 ldh release kit

    All Right Reserved 知识库

    声明:本站内容源于网络,出于传递更多信息之目的,并不意味着赞同其观点或证实其描述。文章内容仅供参考,请咨询相关专业人士。

    如果无意之中侵犯了您的版权,或有意见、反馈或投诉等情况 网站地图 网站栏目