第一部分 C语言程序设计

三、1.日期可按YID格式表示，这里: Y是年(四位数), M是月(二位数), D是日(二位数。例如，1月30日可表示为0130。12月31日可表示为1231。日期的另一种表示方式是YK格式，这里: Y是年(四位数), K是这一天在Y年中的序号(3位数。序号从1开始).例如，1月30日可表示为030，2月5日可表示为 036， 3月5日可表示为065,等等。

按下面的要求写一个函数，把一个YMD格式的日期转换为YK格式的日期:

函数原型:long date convert(long ymd)

功能说明:把YMD格式的日期转换为YK格式的日期.

参数说明:ymd一个 YnD格式的日期(其中的年份21900).

返回值: YMD格式的日期ynd转换成的YK格式的日期。

说明: 可以调用函数leap来判断y年是否是闰年(不必定义该函数):

函数原型:int leap(int y)

功能说明:判断y年是否是闰年。

参数说明:y 年份(y≥1900).

返回值: y年是闰年1； 否则0。

【分析】

众所周知，闰年2月有29天，非闰年2月28天。难点在于统计m月d日是y年的第几天，也就是前m-1个月的天数和+上d

【代码】

#include<stdio.h>int leap(int y){return y%4==0&&y%100!=0||y%400==0;}long date_convert(long ymd){int M[12]={31,28+leap(ymd/10000),31,30,31,30,31,31,30,31,30,31}; //每个月有多少天int i,day=ymd%100;//day统计天数序号,初始为本月天数for(i=ymd/100%100-2;i>=0;--i)day+=M[i];//前m-1个月的天数和return ymd/10000*1000+day;}int main(){printf("%d\n",date_convert(0828));}

三、2.

【代码】

#include<stdio.h>#include<string.h>#define L 130typedef struct {int length;char value[L];}LNUM;int add(LNUM a,LNUM b,LNUM *c){int i,next=0; //next进位变量for(i=L-1;i>=L-a.length||i>=L-b.length;--i){char x=a.value[i]+b.value[i]+next;c->value[i]=x%10;next=x/10;}if(i==0&&next>0)//将要溢出return 1;if(next>0)c->value[i--]=next;//最高位需要进位c->length=L-i-1;for(;i>=0;i--)c->value[i]=0; //高位补0,其实这一步没有必要，因为c->length记下了有效位数return 0;}///以下是本地测试代码，不要写在试卷上。试卷上只写add函数void input(LNUM *c) //输入一个大数{scanf("%s",c->value);c->length = strlen(c->value);int i;for(i=0;i<c->length;++i) //将数字移动到数组尾部，使各位数与[L-1]对齐c->value[i+L-c->length] = c->value[i]-'0';for(i=0;i<L-c->length;++i) //前缀清零c->value[i]=0;}void output(LNUM *c)//输出一个大数{int i;for(i=L-c->length;i<L;++i)printf("%d",c->value[i]);printf("\n");}int main(){LNUM a,b,c;input(&a);input(&b);add(a,b,&c);output(&c);}

第二部分 数据结构

二、写函数

【第1题】

利用层次遍历，增设同步队列id[]，保存结点编号。

#include<stdio.h>#include<stdlib.h>#define ElemType int#define MaxSize 501struct BTNode{ElemType data;struct BTNode *lchild,*rchild;};void tree_convert(struct BTNode *t,ElemType C[]){struct BTNode *p, *Q[MaxSize]; //定义队列Qint k,id[MaxSize],front=0,rear=0; //与Q同步的队列id, front队头，rear队尾下一个for(k=0;k<MaxSize;k++)C[k]=-1; //初始化Q[rear]=t;id[rear++]=0; //根结点对应C[0]while(front<rear){p=Q[front];//取队头结点k=id[front++]; //取队头编号C[k]=p->data; //结点赋值if(p->lchild){Q[rear]=p->lchild; //左孩子入队id[rear++]=k*2+1;}if(p->rchild){Q[rear]=p->rchild; //右孩子入队id[rear++]=k*2+2;}}}

【第2题】

依据深度优先搜索的特点：遇到未访问点则优先访问它。用栈来存储父结点，模拟深搜即可。

#include<stdio.h>#include<stdlib.h>#define ElemType int#define MaxSize 501//定义邻接表struct ENode{int adjVex;struct ENode *next;}; //链表结点struct Graph{struct ENode *adjNext[MaxSize];int vexNum; //点数}; //邻接表void init(struct Graph *G,int n) //初始化一个n点图{G->vexNum=n;int i;for(i=0;i<n;i++)G->adjNext[i]=NULL;}void addedge(struct Graph *G,int u,int v) //u->v单向边{struct ENode *p=(struct ENode*)malloc(sizeof(struct ENode));p->adjVex = v;p->next = G->adjNext[u];G->adjNext[u]=p; //头插法}//题目求一棵生成树，前提是图连通void visit_stack(struct Graph *G,int start) //非递归深度优先遍历{struct ENode *p;int top=0, S[MaxSize]; //S栈int now, vis[MaxSize]={0}; //访问过的点标记为1,初始为全0S[top++]=start; //起点入栈vis[start]=1; //起点标记已访问while(top>0){now=S[top-1]; ///取栈顶p=G->adjNext[now];while(p && vis[p->adjVex])p=p->next;if(p){printf("< %d - %d >\n",now, p->adjVex); //输出这条边vis[p->adjVex]=1;S[top++]=p->adjVex; //入栈以便下一步深搜}else{top--;//已无未访问子结点，出栈}}}int main(){struct Graph G;int n,u,v;printf("请输入点数:");scanf("%d",&n);init(&G,n);printf("请依次输入无向边u-v（0<=u,v<n,输入-1 -1结束）:\n");while(scanf("%d%d",&u,&v),u!=-1&&v!=-1){addedge(&G,u,v);addedge(&G,v,u);}visit_stack(&G,0);}