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進制小數(shù)形式)%e、%E------浮點型(指數(shù)形式)

第3頁/共48頁第2頁/共48頁三、格式化輸入/輸出2、輸出有符號整數(shù)

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

-：表示左對齊，缺省時是右對齊；

+：輸出正數(shù)時，在數(shù)前加上+號；

width：對于無符號整數(shù)，表示輸出整數(shù)的最小域寬（即占屏幕的多少格），若實際寬度超過了width，則按實際寬度輸出；

.precision：針對無符號整數(shù)，表示至少要輸出precision位，如果整數(shù)的位數(shù)大于precision，則按實際位數(shù)輸出，否則在左邊的空位上補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、輸出無符號整數(shù)

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

#：表示以8進制形式輸出數(shù)據(jù)(%o)時，在數(shù)字前輸出0；當以16進制形式輸出數(shù)據(jù)(%x或%X)時，在數(shù)字前輸出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、實數(shù)的輸出

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

.precision：規(guī)定輸出實數(shù)時，小數(shù)部分的位數(shù)；

l：輸出double型數(shù)據(jù)(缺省時也是輸出double型數(shù)據(jù))；

L：輸出longdouble型數(shù)據(jù)；

#：必須輸出小數(shù)點；第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：是無符號整數(shù)，表示輸入數(shù)據(jù)所占的寬度；*:

表示輸入的數(shù)據(jù)不會賦值給相應的變量；

l:

表示輸入長整型數(shù)據(jù)(%ld,%lu,%lx,%lo)和double型數(shù)據(jù)(%lf,%le)；第12頁/共48頁第11頁/共48頁三、格式化輸入/輸出

scanf函數(shù)規(guī)定，當輸入一項數(shù)據(jù)時，遇到以下情況scanf認為該數(shù)據(jù)輸入結束：

1）遇到空格、回車、Tab鍵；

2）指定的寬度結束；如：scanf(“%3d”,&a)；輸入1234，a的值將是123；

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

4）當用%c輸入字符型數(shù)據(jù)時，可顯示字符、空格、回車以及其它轉義字符都是有效輸入；如：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，F(xiàn)ILE*fp);char*fgets(char*s，intn，F(xiàn)ILE*fp);

從fp中讀n-1個字符===>s，最后補‘\0’

int*fputs(char*s，F(xiàn)ILE*fp);

正確，返回寫入文件的實際字符數(shù)；錯誤，則返回EOF（-1）;

第16頁/共48頁第15頁/共48頁四、文件操作unsignedfwrite(void*ptr，unsignedsize，unsignedn，F(xiàn)ILE*fp);size---寫入文件的每個數(shù)據(jù)所占用的字節(jié)數(shù)，通常用sizeof(…)形式；正確，返回n值，錯誤，返回NULL（0）unsignedfread(void*ptr，unsignedsize，unsignedn，F(xiàn)ILE*fp);第17頁/共48頁第16頁/共48頁四、文件操作3、文件的定位

voidrewind(FILE*fp);

將文件指針置于fp所指向的文件頭;

intfseek(FILE*fp，longoffset，intfrom);

offset：從from開始的偏移字節(jié)數(shù)，+--（->）

----(<-)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、數(shù)組指針（指向二維數(shù)組的指針）

inta[2][3]={{1,2,3},{4,5,6}};int(*p)[3];p=a;a[i][j]等價于p[i][j]3、指針數(shù)組

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、指針與動態(tài)分配

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

free(pstr);第20頁/共48頁第19頁/共48頁五、指針6、指針作為函數(shù)的返回值

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、指針函數(shù)

int*getdata(intnum);8、函數(shù)指針

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頁六、常用函數(shù)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頁六、常用函數(shù)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頁六、常用函數(shù)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頁六、常用函數(shù)例如：將整數(shù)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;//棧的空間大小或棧內結點個數(shù)

}sqstack; ·基本操作：iniStack(sqstack&s); push(sqstack&s,SElemTypee);//將e的數(shù)據(jù)場之值插入棧頂， //必須判是否上溢。

pop(sqstack&s,SElemType&e);//取棧頂元素的數(shù)據(jù)值至變量e //，必判?？諉?？。AB初態(tài)AB出棧ABCC進棧第27頁/共48頁第26頁/共48頁七、堆棧2、棧的表示：

·順序表示的堆棧的實現(xiàn)：basetop空棧base==top是?？諛酥緎tacksize=4topAbasebasetopABABCtopbasetopbaseABCD注意： 因為base==top是?？諛酥?，所以 top指針只能指示真正的棧頂元素之上的數(shù)組 元素的下標地址。否則造成矛盾。棧滿時的處理方法： 1、報錯。返回操作系統(tǒng)。 2、分配更大的空間，作為棧的存儲空間。將 原棧的內容移入新棧。3120第28頁/共48頁第27頁/共48頁七、堆棧2、棧的表示：

·順序表示的棧的程序實現(xiàn)：#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數(shù)組s.base[0],s.base[1],……s.base[STACK_INIT_SIZE-1]第29頁/共48頁第28頁/共48頁七、堆棧2、棧的表示：

·順序表示的棧的程序實現(xiàn)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指向的存區(qū)長度改變?yōu)閟ize,size比原先大，必須進行移動，且返回指向新存區(qū)的指針。012979899ptr0129899107108109ptr第30頁/共48頁第29頁/共48頁七、堆棧2、棧的表示：

·順序表示的棧的程序實現(xiàn)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)數(shù)制轉換：10進制和8進制之間的數(shù)的轉換程序。(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)

代碼生成：編譯程序的輸入是后綴表示的算術表達式，輸出是匯編語言代碼。目標機器有一個寄存器以及以下操作，操作數(shù)或者是一個標識符或者是一個存儲器地址。

L------將操作數(shù)載入寄存器（Load）；

A------將寄存器的值加上操作數(shù)（Add）；

S------將寄存器的值減去操作數(shù)（Sub）；

M------將寄存器的值乘以操作數(shù)（Mul）；

D------將寄存器的值除以操作數(shù)（Div）；

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

ST----將寄存器的值保存在操作數(shù)位置（STore）；一個算術操作用運算結果替換寄存器的值。臨時存儲地址可通過形如“$n”（n是一個數(shù)字）的操作數(shù)由匯編程序分配。

1、輸入輸入文件由一些合法的后綴表達式組成。每個占一行。表達式算子是單個字母，算符是通常的算術運算符（+，-，*，\）以及一元取反運算符（@）。第33頁/共48頁第32頁/共48頁七、堆棧2、輸出必須是滿足以下要求的匯編語言代碼：（1）每行一個操作，操作助記符與操作數(shù)（如果有的話）由一個空格隔開；（2）必須用一個空行隔開相繼的表達式的匯編代碼；（3）在匯編代碼中必須保持原來算子的順序；（4）一遇到算符就必須產(chǎn)生匯編代碼；（5）使用盡可能少的臨時存儲空間（在滿足上述條件的基礎上）；（6）對于表達式中的每一個算符，必須產(chǎn)生盡可能少的操作（在滿足上述條件的基礎上）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、圖的存儲表示-----鄰接矩陣（數(shù)組）表示法建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表示各個頂點之間關系）。設圖A=(V,E)有n個頂點，則圖的鄰接矩陣是一個二維數(shù)組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、圖的存儲表示-----鄰接矩陣（數(shù)組）表示法例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）,然后對其余各條路徑進行適當調整：若在圖中存在?。╱,vk），且（v0,u）+（u,vk）<（v0,vk）,則以路徑（v0,u,vk）代替（v0,vk）。在調整后的各條路徑中，再找長度最短的路徑，依此類推。總之，按路徑“長度”遞增的次序來逐步產(chǎn)生最短路徑第41頁/共48頁第40頁/共48頁算法描述：（1）設A[n][n]為有向網(wǎng)的帶權鄰接矩陣，A[i][j]表示?。╲i，vj)的權值，S為已找到從源點v0出發(fā)的最短路徑的終點集合，它的初始狀態(tài)為{v0}.輔助數(shù)組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算法求有向網(wǎng)G的v0頂點到其余頂點v的最短路徑P[v]及帶權長度D[v],//若P[v][w]為TRUE,則w是從v0到v當前求得最短路徑上的頂點。

//final[v]為TRUE當且僅當v∈S,即已經(jīng)求得從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個頂點

{//開始主循環(huán),每次求得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