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