c语言机考参考资料.docx
- 文档编号:2431694
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:37
- 大小:22.93KB
c语言机考参考资料.docx
《c语言机考参考资料.docx》由会员分享,可在线阅读,更多相关《c语言机考参考资料.docx(37页珍藏版)》请在冰点文库上搜索。
c语言机考参考资料
上机参考
1.栈的数据结构与基本函数
1.函数模块
以下栈函数均以栈元素为整型为例,如有需要自行修改!
!
!
!
#include
#include
#include
#defineSTACKINITSIZE100
#defineSTACKINCREMENT10
typedefstruct
{
int*base;
int*top;
intstacksize;
}SqStack;
//以上是栈的数据结构,参数依次为栈底指针,栈顶指针(一直)指向栈顶元素的下一个存储单元
intInitStack(SqStack&S)
{
S.base=(int*)malloc(STACKINITSIZE*sizeof(int));
if(!
S.base)
exit(0);
S.top=S.base;
S.stacksize=STACKINITSIZE;
return0;
}
//以上为/栈的初始化函数
intPush(SqStack&S,inte)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!
S.base)
exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=e;
S.top++;
return0;
}
//以上为入栈函数,传入参数为一个已经初始化的栈类型变量,与一个要入栈的变量。
voidPop(SqStack&S,int&e)
{
if(S.top==S.base)
exit(0);
S.top--;
e=*S.top;
}//以上为出栈函数,传入一个已经初始化的栈类型变量,与用来承接弹出栈元素的变量
2.后缀表达式
#include
#include
#include
#defineSTACKINITSIZE100
#defineSTACKINCREMENT10
typedefstruct
{
int*base;
int*top;
intstacksize;
}SqStack;
//栈的初始化
intInitStack(SqStack&S)
{
S.base=(int*)malloc(STACKINITSIZE*sizeof(int));
if(!
S.base)
exit(0);
S.top=S.base;
S.stacksize=STACKINITSIZE;
return0;
}
template
intPush(SqStack&S,Te)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!
S.base)
exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=e;
S.top++;
return0;
}
template
voidPop(SqStack&S,T&e)
{
if(S.top==S.base)
exit(0);
S.top--;
e=*S.top;
}
intmain()
{
SqStackS1,S2;//S的声明必须在下行字母的前面*******************
inti,j,n,c1,c2;
chare,ch;
charstr[50];
InitStack(S1);
InitStack(S2);
for(i=0;(ch=getchar())!
='\n';i++)
{
str[i]=ch;
}
str[i]='\0';
puts(str);
for(i=0;str[i]!
='\0';)
{
if(str[i]=='')
i++;
if(str[i]!
='*'&&str[i]!
='/'&&str[i]!
='+'&&str[i]!
='-')
{
for(;str[i]!
='';i++)
{
Push(S1,str[i]);
}
n=0;
for(j=0;S1.top!
=S1.base;j++)
{
Pop(S1,e);
n=n+(e-'0')*(pow(10,j));
}
Push(S2,n);
}
else
{
if(str[i]=='*')
{
Pop(S2,c1);
Pop(S2,c2);
c2=c1*c2;
Push(S2,c2);
}
if(str[i]=='+')
{
Pop(S2,c1);
Pop(S2,c2);
c2=c1+c2;
Push(S2,c2);
}
if(str[i]=='-')
{
Pop(S2,c1);
Pop(S2,c2);
c2=c2-c1;
Push(S2,c2);
}
if(str[i]=='/')
{
Pop(S2,c1);
Pop(S2,c2);
c2=c2/c1;
Push(S2,c2);
}
i++;
}
}Pop(S2,n);
printf("%d",n);
system("pause");
return0;
}
程序中数据结构部分需要修改,需要分成char与int两种
3.括号匹配
#include
#include
#defineinitiall5
#defineadditionl2
typedefstruct
{
intcurrentl;//currentlisthelargestcapicityofthisstackatthattime
char*base;
char*top;
}stack;
voidpush(stack&s,chare)
{
if(s.top-s.base>=s.currentl)
{
s.base=(char*)realloc(s.base,(s.currentl+additionl)*sizeof(char));
if(!
s.base)printf("error");
s.top=s.base+s.currentl;
s.currentl+=additionl;
}
*s.top++=e;
}
voidinitialstack(stack&s,inte)
{
s.base=(char*)malloc(e*sizeof(int));
s.top=s.base;
s.currentl=initiall;
}
intmain()
{
inti=1,j=1,a=0;
charc,*pop;
stacks;
initialstack(s,initiall);
for(;;)
{
c=getchar();
if(c=='\n')break;
elseif(c=='('||c==')'||c=='{'||c=='}'||c=='['||c==']')
{a++;
if(c=='('||c=='{'||c=='[')
{
push(s,c);
}
else
{
if(s.top==s.base)
{
printf("wrong:
therearenotenoughleftcharscanbematchedwiththerightones\n");
i=0;
j=0;
break;
}
else
{
pop=s.top-1;
if(*pop=='('&&c==')')s.top--;
elseif(*pop=='{'&&c=='}')s.top--;
elseif(*pop=='['&&c==']')s.top--;
else
{
printf("wrong:
thereareseveralleftcharshavewrongpartners\n");
break;
}
}
}
}
}
if(a==0){printf("pleaseinputincorrectformat");return0;}
elseif(s.base==s.top&&i==1)printf("right\n");
elseif(j==1)printf("wrong:
itislikelythatthereareseveralleftcharsarestillwaitingtobematched\n");
system("pause");
return0;
}
4.数制转换
#include
#include
#defineinitiall1
#defineadditionl1
typedefstruct
{
intcurrentl;
int*base;
int*top;
}stack;
voidpush(stack&s,inte)
{
if(s.top-s.base>=s.currentl)
{
s.base=(int*)realloc(s.base,(s.currentl+additionl)*sizeof(int));
if(!
s.base)printf("error");
s.top=s.base+s.currentl;
s.currentl+=additionl;
}
*s.top++=e;
}
voidinitialstack(stack&s,inte)
{
s.base=(int*)malloc(e*sizeof(int));
s.top=s.base;
s.currentl=initiall;
}
intmain()
{
inta,b;
stacks;
initialstack(s,initiall);
printf("inputainteger");
scanf("%d",&a);
for(;a!
=1;)
{
b=a%2;
a=a/2;
push(s,b);
}
push(s,a);
for(;s.base!
=s.top;)
{
printf("%d",*--s.top);
}
return0;
}
2.各种排序函数
在主函数中把待排序的序列存入数列当中。
调用排序函数时传入参数为:
1.数列首元素地址。
2.待排序列数字个数。
以下排序函数均以此为前提
voidbubblesort(int*p,intl)
{
int*q=p;
inti,j,t,n=0;
for(i=1;i<=l-1;i++)
for(j=1,p=q;j<=l-i;j++,p++)
if(*p>=*(p+1)){t=*p;*p=*(p+1);*(p+1)=t;n=n+1;}
p=q;
for(i=0;i<=l-1;i++,p++)printf("%5d",*p);
}
//以上为冒泡排序
voidschoicesort(int*p,intl)
{
int*q=p;
int*k;
inti;intj;intt;intn=0;
for(i=1;i<=l-1;i++)
for(p=q+i-1,j=1,k=p+1;j<=l-i;j++,k++)
if(*p>=*k){t=*p;*p=*k;*k=t;n=n+1;}
p=q;
for(i=0;i<=l-1;i++,p++)printf("%5d",*p);
}//以上为简单排序
voidinsertsort(int*p,intl)
{
inti,n=0;
int*t;
int*q;
int*k;
int*tail=p+l-1;
for(;tail!
=p;)
{
*(tail+1)=*tail;
tail--;
}
*(tail+1)=*tail;//tail现在为哨兵指针
p=p+1;
q=p+l;//q现在为尾部指针
for(i=1,k=p+1;k!
=q;i++,k++)
{
for(*tail=*k,t=k-1;t!
=tail;t--)
{
if(*t>=*k&&*(t-1)<=*k)
{
while(k!
=t)
{
*k=*(k-1);
k--;
n++;
}
*k=*tail;
break;
}
}
k=p+i;
}
for(;p!
=q;p++)
{
printf("%5d",*p);
}
}
//以上为直接插入排序
int*oqs(int*low,int*high)
{
intreport;
report=*low;
while(low { for(;(low *low=*high; u++; for(;(low *high=*low; u++; } *low=report; u++; returnlow; } //以上为单次快速排序 voidquicksort(int*low,int*high) { int*shuzhou; if(low { shuzhou=oqs(low,high); quicksort(low,shuzhou-1); quicksort(shuzhou+1,high); } }//以上为快排递归函数,传入的是待排序列首元素指针与尾元素指针 3.图的数据结构与函数 1.邻接链表存储数据结构详解 typedefstructnode { intweight; intcode; structnode*next; }node; //node为一个结点类型,每一个结点中有3个域,权重域,编号域和指向下一个结点的指针域 typedefstruct { intcode;//结点的编号 node*head;//该结点头结点指针 intmark; }headlist[MAXPOINT]; //一个数组类型,每个元素有3个域,一个为结点编号域,另一个为该结点所在头结点指针域,还有一个为判断是否被遍历过的标记域 typedefstruct { intnlines;//边数 intnpoints;//顶点数 headlistpointlist; }graph; //图类型,每个graph型中有三个域,边数域,顶点数域,一个各结点头指针域 grapht; 2.邻接链表结构下的深度优先遍历函数 voidDFS(graph&t,inti) { node*n; printf("V%d",t.pointlist[i].code); n=t.pointlist[i].head; t.pointlist[i].mark=1; for(;n->next! =NULL;n=n->next) { if(t.pointlist[n->next->code].mark==0)DFS(t,n->next->code); } }//深度优先遍历的核心递归部分 voidDFSTraverse(graph&t) { inti; for(i=0;i { if(t.pointlist[i].mark==0) DFS(t,i); } } //深度优先遍历外部函数,作用为遍历不同连通分量。 其中注意这里的代码是以顶点编号为零为例的。 如需修改,则改动for循环语句即可。 以下为链表深度优先遍历完整源码 #include #include #include #defineMAXPOINT50//最大顶点个数 typedefstructnode { intweight; intcode; structnode*next; }node; //node为一个结点类型,每一个结点中有3个域,权重域,编号域和指向下一个结点的指针域 typedefstruct { intcode;//结点的编号 node*head;//该结点头结点指针 intmark; }headlist[MAXPOINT]; //一个数组类型,每个元素有3个域,一个为结点编号域,另一个为该结点所在头结点指针域,还有一个为判断是否被遍历过的标记域 typedefstruct { intnlines;//边数 intnpoints;//顶点数 headlistpointlist; }graph;//图类型,每个graph型中有三个域,边数域,顶点数域,一个各结点头指针域 grapht; voidDFS(graph&t,inti) { node*n; printf("V%d",t.pointlist[i].code); n=t.pointlist[i].head; t.pointlist[i].mark=1; for(;n->next! =NULL;n=n->next) { if(t.pointlist[n->next->code].mark==0)DFS(t,n->next->code); } } voidDFSTraverse(graph&t) { inti; for(i=0;i { if(t.pointlist[i].mark==0) DFS(t,i); } } intmain() { node*n; inti,j; printf("输入图的顶点数: "); scanf("%d",&t.npoints); printf("输入图的边数: "); scanf("%d",&t.nlines); for(i=0;i { (t.pointlist)[i].code=i; (t.pointlist)[i].head=(node*)malloc(sizeof(node)); ((t.pointlist)[i].head)->next=NULL; (t.pointlist)[i].head->code=i; (t.pointlist)[i].mark=0; }//各结点的头结点已经建立完毕,且各头结点地址已经依次存在数组t.pointlist[]当中,注意结点编号从零开始 printf("按要求输入图结点之间的关系与权重\n"); for(i=0;i { scanf("%d",&j); n=(t.pointlist)[j].head; for(;n->next! =NULL;n=n->next){} scanf("%d",&j); n->next=(node*)malloc(sizeof(node)); n=n->next; n->code=j; scanf("%d",&n->weight); n->next=NULL; }//现已将图以邻接矩阵的形式存入计算机 DFSTraverse(t); return0; } 以上主函数中采用的均是手动输入法建立头结点以及邻接链表,到时改成文件读取形式即可。 同时,默认顶点编号从0开始。 3.邻接矩阵形式存储图数据结构 typedefintAdjMatrix[MAXPOINT][MAXPOINT];//定义AdjMatrix为一种整数型二维数组类型 typedefstruct { intnlines;//边数 intnpoints;//顶点数 AdjMatrixarcs;//邻接矩阵 }graph;//有向图类型 4邻接矩阵存储下的深度优先遍历 #include #include #include #defineMAXPOINT50//最大顶点个数 intvisited[MAXPOINT];//用来判别顶点是否被访问过的数组 typedefintAdjMatrix[MAXPOINT][MAXPOINT];//定义AdjMatrix为一种整数型二维数组类型 typedefstruct { intnlines;//边数 intnpoints;//顶点数 AdjMatrixarcs;//邻接矩阵 }graph;//有向图类型 intnext(grapht,intj,inti) { intT=0; int*k; for(j=j+1,k=&t.arcs[i][j];k<=t.arcs[i]+t.npoints-1;k++,j++) { if(t.arcs[i][j]==1) { T=j; break; } } returnT; } voidDFS(graph&t,inti)//此处i为开始深度遍历的顶点编号 { intj,w; visited[i-1]=1; printf("%2d",i); for(w=next(t,0,i);w>0;w=next(t,w,i))//此处的next(graph&t,intj,inti)函数为搜索邻接矩阵中从第j个元素开始下一个与i号元素邻接的元素号,若不存在这样的元素则返回0; { if(! visited[w-1])DFS(t,w); } } voidDFSTraverse(graph&t)//深度遍历宏观函数,传入的是一个图类型 { inti; for(i=1;i<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 参考资料