ACM程序员大赛讲座

会计学1ACM程序员大赛讲座二、运算符1、按位运算

&、|、^、~、<<、>>2、算术运算

++、--、*、/、%3、条件运算

&&、||、！4、转义符

\ddd(8进制)、\xhh(16进制)第2页/共48页第1页/共48页三、格式化输入/输出1、printf(“格式控制字符”，表达式1，….，表达式n)

%d、%i--------有符号10进制整型

%x、%X------无符号16进制整型

%o--------------无符号8进制整型

%u--------------无符号10进制整型

%c--------------字符型

%s--------------字符串

%f--------------浮点型(10进制小数形式)%e、%E------浮点型(指数形式)

第3页/共48页第2页/共48页三、格式化输入/输出2、输出有符号整数

%[-][+][width][.precision]d

-：表示左对齐，缺省时是右对齐；

+：输出正数时，在数前加上+号；

width：对于无符号整数，表示输出整数的最小域宽（即占屏幕的多少格），若实际宽度超过了width，则按实际宽度输出；

.precision：针对无符号整数，表示至少要输出precision位，如果整数的位数大于precision，则按实际位数输出，否则在左边的空位上补0。第4页/共48页第3页/共48页三、格式化输入/输出main(){inta=123;longL=34567;printf("a=%d\n",a);printf("a=%6d\n",a);printf("a=%6.4d\n",a);printf("a=%-6d\n",a);printf("a=%+6d\n",a);printf("L=%ld",L);}运行结果：a=123a=123a=0123a=123a=+123L=34567第5页/共48页第4页/共48页三、格式化输入/输出3、输出无符号整数

%[-][#][width][.precision][l]u|o|x|X

#：表示以8进制形式输出数据(%o)时，在数字前输出0；当以16进制形式输出数据(%x或%X)时，在数字前输出0x或0X；第6页/共48页第5页/共48页三、格式化输入/输出main(){inta=-1;unsignedu=32767;unsignedlongL=65535<<2;printf("a=%u:a=%d\n",a,a);printf("u=%o\n",u);printf("u=%x:u=%X\n",u,u);printf("u=%#o:u=%#X\n",u,u);printf("L=%lx\n",L);printf("L=%#.8lX\n",L);}运行结果：

a=65535:a=-1u=77777u=7fff:u=7FFFu=077777:u=0X7FFFL=3fffcL=0X03FFFC第7页/共48页第6页/共48页三、格式化输入/输出4、实数的输出

%[-][+][#][width][.precision][l][L]f|e|E|g|G

.precision：规定输出实数时，小数部分的位数；

l：输出double型数据(缺省时也是输出double型数据)；

L：输出longdouble型数据；

#：必须输出小数点；第8页/共48页第7页/共48页三、格式化输入/输出main(){doublef=2.5e5;printf("123456789123456789\n");printf("f=%15f\n",f);printf("f=%-15.0f\n",f);printf("f=%#15.0f\n",f);printf("f=%+15.4f\n",f);printf("f=%15.4e\n",f);}运行结果：

123456789123456789f=250000.000000f=250000f=250000.f=+250000.0000f=2.5000e+05第9页/共48页第8页/共48页三、格式化输入/输出5、字符和字符串的输出

%[-][width]c%[-][width][.precision]s.precision：表示只输出字符串的前precision个字符；第10页/共48页第9页/共48页三、格式化输入/输出main(){charch='A';printf("ch=%c\n",ch);printf("ch=%3c\n",ch);printf("ch=%-3c\n",ch);printf("%s\n","ABCD");printf("%6s\n","ABCD");printf("%6.3s\n","ABCD");}运行结果：Ch=ACh=ACh=AABCDABCDABC第11页/共48页第10页/共48页三、格式化输入/输出6、scanf(“格式控制字符串”，变量1地址，…，变量n地址)

例：scanf(“%d”,&a);

格式控制字符的一般形式：

%[*][width][l]Type

width：是无符号整数，表示输入数据所占的宽度；*:

表示输入的数据不会赋值给相应的变量；

l:

表示输入长整型数据(%ld,%lu,%lx,%lo)和double型数据(%lf,%le)；第12页/共48页第11页/共48页三、格式化输入/输出

scanf函数规定，当输入一项数据时，遇到以下情况scanf认为该数据输入结束：

1）遇到空格、回车、Tab键；

2）指定的宽度结束；如：scanf(“%3d”,&a)；输入1234，a的值将是123；

3）遇非法输入；如：scanf(“%d”,&a)；如果用户输入12a3，a的值将是12；

4）当用%c输入字符型数据时，可显示字符、空格、回车以及其它转义字符都是有效输入；如：scanf(“%c%c%c”,&a,&b,&c)；

第13页/共48页第12页/共48页三、格式化输入/输出Scanf(“%c%c”,&c1,&c2)；aAScanf(“%d,%d”,&x,&y)；12，-23Scanf(“%s%s”,&x,&y)；aaAA第14页/共48页第13页/共48页四、文件操作1、文件的打开与关闭

FILE*fopen(char*filename,char*mode);intfclose(FILE*fp);intfeof(FILE*fp);

mode：由两类字符组成，一类字符表示打开文件的类型，t---文本文件，b---二进制文件；另一类字符是操作类型，r---读，w---写，a---追加，+---可读可写；第15页/共48页第14页/共48页四、文件操作2、文件的读写

intfscanf(FILE*fp，char*format，v1,…,vn)；

intfprintf(FILE*fp，char*format，e1,…en)；

intfgetc(FILE*fp)；

intfputc(intc，FILE*fp);char*fgets(char*s，intn，FILE*fp);

从fp中读n-1个字符===>s，最后补‘\0’

int*fputs(char*s，FILE*fp);

正确，返回写入文件的实际字符数；错误，则返回EOF（-1）;

第16页/共48页第15页/共48页四、文件操作unsignedfwrite(void*ptr，unsignedsize，unsignedn，FILE*fp);size---写入文件的每个数据所占用的字节数，通常用sizeof(…)形式；正确，返回n值，错误，返回NULL（0）unsignedfread(void*ptr，unsignedsize，unsignedn，FILE*fp);第17页/共48页第16页/共48页四、文件操作3、文件的定位

voidrewind(FILE*fp);

将文件指针置于fp所指向的文件头;

intfseek(FILE*fp，longoffset，intfrom);

offset：从from开始的偏移字节数，+--（->）

----(<-)0—不动

from：SEEK_SET(0)、SEEK_CUR(1)、SEEK_END(2)

longftell(FILE*fp);

返回当前位置指针的值，如出错，ftell返回-1；第18页/共48页第17页/共48页五、指针1、一级指针

int*p;char*pstr;2、数组指针（指向二维数组的指针）

inta[2][3]={{1,2,3},{4,5,6}};int(*p)[3];p=a;a[i][j]等价于p[i][j]3、指针数组

inta[3];

int*p[3];p[0]=&a[0];p[1]=&a[1];p[2]=&a[2];第19页/共48页第18页/共48页五、指针4、二级指针

inta;int*p;int**pp;

p=&a;pp=&p;5、指针与动态分配

void*malloc(unsignedintsize);char*pstr;pstr=(char*)malloc(10*sizeof(char));if(pstr==NULL){分配不成功}

free(pstr);第20页/共48页第19页/共48页五、指针6、指针作为函数的返回值

int*getdata(intnum){int*p;intk;

p=(int*)malloc(num*sizeof(int));if(p!=NULL)for(k=0;k<num;k++)scanf(“%d”,&p[k]);returnp;}int*getdata(intnum){staticinta[100];intk;if(num>100)returnNULL;for(k=0;k<num;k++)scanf(“%d”,&a[k]);returna;}第21页/共48页第20页/共48页五、指针7、指针函数

int*getdata(intnum);8、函数指针

int(*pf)(inta);

例：intgetmax(intx,inty){return(x>y?x:y);}voidmain(){int(*pf)(int,int);inta;pf=getmax;a=(*pf)(3,2);printf(“a=%d”,a);}第22页/共48页第21页/共48页六、常用函数1、intgetch(void);2、intgetche(void);3、sizeof(expression)/sizeof(type);4、break/continue;5、memset(void*s,intc,size_tn)6、void*malloc(size_tsize);7、voidfree(void*block);8、strcpy(char*dest,constchar*src);带‘\0’第23页/共48页第22页/共48页六、常用函数9、strncpy(char*dest,constchar*src,size_tmaxlen);不带‘\0’10、memcpy(void*dest,contvoid*src,size_tn);不带‘\0’11、movmem(void*src,void*dest,unsignedlength);带‘\0’12、strcat(char*dest,constchar*src);带‘\0’13、strncat(char*dest,constchar*src,size_tmaxlen);带‘\0’14、char*strchr(constchar*s,intc);

找到返回其指针，否则null15、intstrcmp(constchar*s1,constchar*s2);16、intstrncmp(constchar*s1,constchar*s2,size_tmaxlen);第24页/共48页第23页/共48页六、常用函数17、char*strstr(constchar*s1,constchar*s2)18、strset(char*s,intch);19、char*strupr(char*str);20、doubleatof(constchar*nptr);21、intatoi(constchar*nptr);22、longatol(constchar*nptr);23、char*itoa(intvalue,char*string,intradix);24、intrandom(intnum);24、sprintf(char*buffer,constchar*format,……);第25页/共48页第24页/共48页六、常用函数例如：将整数123“000123”charbuffer[7];inta=123;sprintf(buffer,”%6.6d”,a);25、intisalpha(intx);26、intislower(intx);27、intisupper(intx);28、intisdigit(intx);29、inttolower(intx);30、inttoupper(intx);第26页/共48页第25页/共48页七、堆栈1、定义：限定仅只能在表尾端进行插入和删除的线性表。栈顶：表尾端被称之为栈顶。栈底：和表尾相对应的另一端，称之为栈底。2、栈的表示：

·顺序表示的堆栈：

Typedefstruct{ SElemType*base;//栈底元素的位置或下标

SElemType*top;//栈顶元素的位置或下标

intstacksize;//栈的空间大小或栈内结点个数

}sqstack; ·基本操作：iniStack(sqstack&s); push(sqstack&s,SElemTypee);//将e的数据场之值插入栈顶， //必须判是否上溢。

pop(sqstack&s,SElemType&e);//取栈顶元素的数据值至变量e //，必判栈空吗？。AB初态AB出栈ABCC进栈第27页/共48页第26页/共48页七、堆栈2、栈的表示：

·顺序表示的堆栈的实现：basetop空栈base==top是栈空标志stacksize=4topAbasebasetopABABCtopbasetopbaseABCD注意： 因为base==top是栈空标志，所以 top指针只能指示真正的栈顶元素之上的数组 元素的下标地址。否则造成矛盾。栈满时的处理方法： 1、报错。返回操作系统。 2、分配更大的空间，作为栈的存储空间。将 原栈的内容移入新栈。3120第28页/共48页第27页/共48页七、堆栈2、栈的表示：

·顺序表示的栈的程序实现：#defineSTACK_INIT_SIZE 100;#defineSTACK_INCREMENT10;IniStack(sqstack&s){s.base=(SElemType*)malloc(STACK_INIT_SIZE)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.base;//nullstackflags.stacksize=STACK_INIT_SIZE;returnOK;}//initstack;012STACK_INIT_SIZE-1s.base数组s.base[0],s.base[1],……s.base[STACK_INIT_SIZE-1]第29页/共48页第28页/共48页七、堆栈2、栈的表示：

·顺序表示的栈的程序实现push操作：Statuspush(sqstack&s,SElemTypee){If(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)* sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;//s.stacksize+=STACKINCREMENT;*s.top++=e;returnOK;}//push;//相当于：*s.top=e;s.top++两条指令;realloc(ptr,size):将ptr指向的存区长度改变为size,size比原先大，必须进行移动，且返回指向新存区的指针。012979899ptr0129899107108109ptr第30页/共48页第29页/共48页七、堆栈2、栈的表示：

·顺序表示的栈的程序实现pop操作：Statuspop(sqstack&s,SElemType&e){If(s.top==s.base)returnERROR;e=*--s.top;returnOK;}//pop//相当于：s.top--;e=*s.top两条指令;第31页/共48页第30页/共48页七、堆栈3、栈的应用：

(1)数制转换：10进制和8进制之间的数的转换程序。(1348)10=

(2504)104052voidconversion(){iInitStack(S);scanf(%d,N);while(N){Push(S,N%8);N=N/8;}while(!Stackempty){Pop(S,e);printf(“%d”,e);}第32页/共48页第31页/共48页七、堆栈3、栈的应用：

(2)

代码生成：编译程序的输入是后缀表示的算术表达式，输出是汇编语言代码。目标机器有一个寄存器以及以下操作，操作数或者是一个标识符或者是一个存储器地址。

L------将操作数载入寄存器（Load）；

A------将寄存器的值加上操作数（Add）；

S------将寄存器的值减去操作数（Sub）；

M------将寄存器的值乘以操作数（Mul）；

D------将寄存器的值除以操作数（Div）；

N------将寄存器的值求反（Not）；

ST----将寄存器的值保存在操作数位置（STore）；一个算术操作用运算结果替换寄存器的值。临时存储地址可通过形如“$n”（n是一个数字）的操作数由汇编程序分配。

1、输入输入文件由一些合法的后缀表达式组成。每个占一行。表达式算子是单个字母，算符是通常的算术运算符（+，-，*，\）以及一元取反运算符（@）。第33页/共48页第32页/共48页七、堆栈2、输出必须是满足以下要求的汇编语言代码：（1）每行一个操作，操作助记符与操作数（如果有的话）由一个空格隔开；（2）必须用一个空行隔开相继的表达式的汇编代码；（3）在汇编代码中必须保持原来算子的顺序；（4）一遇到算符就必须产生汇编代码；（5）使用尽可能少的临时存储空间（在满足上述条件的基础上）；（6）对于表达式中的每一个算符，必须产生尽可能少的操作（在满足上述条件的基础上）3、样例输入（1）AB+CD+EF++GH+++（2）AB+CD+-4、样例输出（1）LAABST$1LCADST$2LEAFA$2ST$2LGAHA$2A$1

（2）LAABST$1LCADNA$15、程序见--------Compile.cpp第34页/共48页第33页/共48页八、图图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；

E

是G的边集合，是有穷集。有向图：无向图：完全图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；若

n个顶点的无向图有

n(n-1)/2条边,

称为无向完全图若

n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge1、图的基本术语第35页/共48页第34页/共48页2、图的存储表示-----邻接矩阵（数组）表示法建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：v1v2v3v5v4v4A例1—无权图：邻接矩阵：A.Edge=（

v1v2

v3v4v5

）v1v2v3v4v500

0

0000

0000

0000000000000001

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10第36页/共48页第35页/共48页2、图的存储表示-----邻接矩阵（数组）表示法例2—有权图：第37页/共48页第36页/共48页一顶点到其余各顶点3.求最短路径两种常见的最短路径问题：一、单源最短路径—用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）任意两顶点之间第38页/共48页第37页/共48页单源最短路径(Dijkstra算法)目的：

设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。例1：源点从F→A的路径有4条：①F→A：24②F→B→A：5＋18=23③F→B→C→A：5+7+9=21④

F→D→C→A：25+12+9=36又：从F→B的最短路径是哪条？从F→C的最短路径是哪条？第39页/共48页第38页/共48页v0(v0,v1)10源点终点

最

短路

径路径长度(v0,v1,v2)(v0,v3,v2)(v0,v3)30

v1

v2

v3

v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例2：6001234

509070讨论：计算机如何自动求出这些最短路径？(v0,v1,v2,v4)60第40页/共48页第39页/共48页Dijkstra（迪杰斯特拉）算法算法思想：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（v0,u）,然后对其余各条路径进行适当调整：若在图中存在弧（u,vk），且（v0,u）+（u,vk）<（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。在调整后的各条路径中，再找长度最短的路径，依此类推。总之，按路径“长度”递增的次序来逐步产生最短路径第41页/共48页第40页/共48页算法描述：（1）设A[n][n]为有向网的带权邻接矩阵，A[i][j]表示弧（vi，vj)的权值，S为已找到从源点v0出发的最短路径的终点集合，它的初始状态为{v0}.辅助数组dist[n]为各终点当前找到的最短路径的长度，它的初始值为：dist[i]＝A[v0,i]//即邻接矩阵中第v0行的权值（2）选择u，使得

dist[u]＝min{dist[w]|w∈V-S}//w是S集之外的顶点

//dist[u]是从源点v0到S集外所有顶点的弧中最短的一条

S=S∪{u}

//将u加入S集（3）对于所有不在S中的终点w，若

dist[u]+A[u,w]<dist[w]//即(v0,u)＋(u,w)<(v0,w)则修改dist[w]为：

dist[w]＝dist[u]+A[u,w]（4）重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。第42页/共48页第41页/共48页算法的C语言程序voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D)

{

//用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v],//若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。

//final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径

intv，w，i，j，min;Statusfinal[MAX_VERTEX_NUM];

for(v=0;v<G.vexnum;++v)

{final[v]=FALSE;D[v]=G.arcs[v0][v].adj;for(w=0;w<G.vexnum;++w)P[v][w]=FALSE;//设空路径

if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}

}第43页/共48页第42页/共48页

D[v0]=0;final[v0]=TRUE;//初始化,v0顶点属于S集

for(i=1;i<G.vexnum;++i)

//其余G.vexnum-1个顶点

{//开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集

min=INFINITY;//当前所知离v0顶点的最近距离

for(w=0;w<G.vexnum;++w)if(!final[w])//w顶点在V-S中

if(D[w]<min){v=w;min=D[w];}//w顶点离v0顶点更近

final[v]=TRUE;//离v0顶点最近的v加入S集

for(w=0;w<G.vexnum;++w)

//更新当前最短路径及距离

{if(!final[w]&&min<INFINITY&&G.arcs[v][w].adj<INFINITY&&(min+G.arcs[v][w].adj<D[w])){//修改D[w]和P[w],w∈V-SD[w]=min+G.arcs[v][w].adj;for(j=0;j<G.vexnum;++j)P[w][j]=P[v][j];P[w][w]=TRUE;//P[w]=P[v]+[w]}

}

}}第44页/共48页第43页/共48页(v0,v2)+(v2,v3)<(v0,v3)终点

从v0到各终点的dist值和最短路径v1v2v3v4v5vjS之外的当前最短路径之顶点60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}60{v0,v4,v3,v5}5540312100603010102050s{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}10{v0,v2}∞

30{v0,v4}100{v0,v5}∞∞∞∞例3：v2v4v3v5100{v0,v5}012345dist[w]012345与最小生成树的不同点：路径可能是累加的！10{v0,v2}50{v0,v4,v3}30{v0,v4}第4