《ACM实验新人指导》由会员分享，可在线阅读，更多相关《ACM实验新人指导（222页珍藏版）》请在金锄头文库上搜索。
1、1ACM/ICPCACM/ICPC 实验指导实验指导2前前 言言ACM 的全称是 Association for Computing Machinery（美国计算机学会） ，建立于 1947 年，是世界上第一个计算机教育和科研的组织，也是最有影响的计算机组织。如今，ACM 已经有超过 8 万个成员，主要活动包括一些专题的兴趣小组与一系列高水平的学术会议， 还有一些面向不同层次的学术竞赛，ACM/ICPC 就是其中之一。 ACM/ICPC（ACM International Collegiate Programming Contest） ，即 ACM 国际大学生 程序设计竞赛，是由 ACM 提供
2、给大学生的一个展示和提高解题与编程能力的机会。赛事 由各大洲区域预赛和全球总决赛两个阶段组成。各预赛区第一名自动获得参加全球总决赛 的资格。决赛安排在每年的 3-4 月举行，而区域预赛一般安排在上一年的 9-12 月举行。一 个大学可以有多支队伍参加区域预赛，但只能有一支队伍参加全球总决赛。决赛的颁奖仪 式将和计算机界权威的学术奖图灵奖的颁奖仪式同时进行。全球总决赛第一名将获得 奖杯一座。另外，成绩靠前的参赛队伍也将获得金、银和铜牌。而解题数在中等以下的队 伍会得到确认但不会进行排名。ACM/ICPC 竞赛的历史可以上溯到 1970 年，当时在美国德克萨斯 A 指向 double 类型的指针定
3、义为： double *p_double; 指向 char 类型的指针定义为： char *p_char; 指针类型在 C 语言中有着广泛而灵活的应用，本节并不一一例举。在 ACM/ICPC 中， 其主要应用在“链表”数据结构中。 除了以上的基本数据类型之外，C 语言还提供三种复合数据类型：数组、结构体和共 用体。由于“共用体”在 ACM/ICPC 竞赛中极少使用，因此本节只讲解数组与结构体。 数组是一个单一数据类型的集合，通常可以理解为数列。数组声明时需要指定元素个 数，也可以进行部分或全部的初始化。以整型数组为例，要声明一个含有 100 个元素的 int 型数组 array_int，语法如
4、下： int array_int100; 数组下标从 0 开始，因此对此数组访问时只能采用 099 这 100 个数作为数组下标，9超出此范围即产生数组越界，此种错误在调试阶段不易发现，但提交到 Judge 之后可能产 生 Run time error 错误。 此种语法未对数做进行初始化，因此数组各元素的初始值不确定。 若要将此数组中的所有元素初始化为 0，可以采用如下语法： int array_int100=0; /需要注意的是，仅初始化为 0 时可以采用此种语法 若要对此数组中的前 10 个元素进行初始化，可采用如下语法： int array_int100=1,2,3,4,5,6,7,8,
5、9,10 此时，数组中的后 90 个元素均初始化为 0。 另外，声明数组时，也可以采用初始化列表来指定数组的规模，如： int array_int = 1,2,3,4,5 此时，数组 array_int 的规模为 5。在竞赛解题中，为了避免数组越界，不推荐采用此 种形式进行声明。 特别地，C 语言中采用字符数组来表示字符串，并以空字符0作为字符串的结束标志。结构体与数组类似，也是一种包含多个变量的数据结构，不同的是，结构体中的各个 变量并不需要为同一种数据类型，其语法为： struct struct_nametype para_name;type para_name; 通常可以使用关键字 ty
6、pedef 将结构体定义为某种自定义的数据类型，语法如下： typedef struct type_name; 结构体在 ACM/ICPC 中主要作为用户自定义数据类型使用，可以对树、图等数据结构 的节点中所需要的数据进行整合，改善程序结构。特别地，在“链表”数据结构中，结构 体的作用更是不可替代，以 int 作为数据元素的链表结点定义如下： typedef struct int element;struct node* next; node;1.2 表达式表达式表达式由一个或多个操作数构成，是程序设计的基本单位。本节主要讲解赋值表达式、 逻辑表达式、问号表达式和逗号表达式。 赋值表达式用来对
7、变量赋值，其语法为： 变量名=表达式； 从语法可以看出赋值表达式是可以嵌套的，整个表达式的值即为最右面的表达式的值， 例如：int a,b;10a=b=10; 在 C 语言中，有一类特殊的赋值表达式，用来对变量进行快捷的自增/减/乘/除。下面 以自增为例进行说明: 表达式 a += 2 表示的含义是 a = a+2; 相应的，其他自运算赋值运算符为：-=，*=，/=。逻辑表达式表达的是某件事情的真或假，由于 C 语言中没有布尔量，因此用 0 表示假， 非 0 值表示真。C 语言中用于比较大小的逻辑运算符有：，=，y ? x : y ;逗号表达式的语法为：表达式 1，表达式 2，表达式 3，.
8、，表达式 n 使用逗号表达式时，需要注意一下三点： (1) 逗号表达式的运算过程为：从左往右逐个计算表达式。 (2) 逗号表达式作为一个整体，它的值为最后一个表达式（即表达式 n）的值。 (3) 逗号运算符的优先级别在所有运算符中最低。1.3 分支语句分支语句C 语言提供 if else 和 switch case 两种分支语句。 if else 语句的含义同其英文字面意思相同，表示如果那么否则句型，其语法 如下： if(逻辑表达式)语句 1; else语句 2;.11 当逻辑表达式值为 true 时，执行以语句 1 为首的块。当逻辑表达式的值为 false 时，执 行以语句 2 为首的块。如
9、果不需要在表达式值为 false 时执行特别的语句，else 子句可以省 略。当有多个 if else 嵌套时，else 与最近的 if 匹配。如果语句块中只包含一条语句，则“” 可以省略，整条语句可以简写为： if(逻辑表达式)语句 1； else语句 2； 这样书写是有弊端的：调试程序时，若发现语句 1 和语句 2 后面还应当添加相应的语 句，则有可能直接添加到语句 1 和语句 2 后面而忘记添加块标记符号“”而导致程序错 误。因此 if else 的简写形式推荐采用如下的形式进行书写： if(逻辑表达式) 语句 1； else 语句 2；例题 1：健康饲料 为了饲养出更加健康的奶牛，Fa
10、rmer John 决定对幼年奶牛与成年奶牛喂给不同的饲料。 已知 10 个月以下的奶牛属于幼年奶牛，大于 10 个月的奶牛属于成年奶牛。幼年奶牛饲料 的价格为￥5.0/公斤，成年奶牛饲料的价格为￥3.0/公斤。若已知奶牛的年龄（用月份表示） ，如何得到其饲料的单价呢？ 解题：可以采用 if else 语句进行判断，例程如下：int age; double price; if(agelink; /*初始时，令 p 指向第一个元素结点，i 为元素计数器*/ while (p i+; if (p /*存在第 k 个元素且指针 p 指向该元素结点*/ return NULL; /*第 k 个元素不存
11、在*/ /*Find_List*/单链表的插入运算。 int Insert_List (LinkList L, int k, int elem) /*L 为带头结点单链表的头指针*/ /*将元素 elem 插入表中的第 k 个元素之前，若成功则返回 0，否则返回1*/ /*将元素 elem 插入第 k 个元素之前等同于将元素插入在第 k1 个元素之后*/ LinkList p,q; if (k = = 1) p = L; /*元素 elem 插入在第 1 个元素之前*/ else p = Find_List(L,k1); /*查找表中的第 k1 个元素并令 p 指向该元素结点*/ if (!p
12、) return 1; /*表中不存在第 k1 个元素*/ q = (NODE *)malloc(sizeof(NODE); if (!q) return 1; q-data = elem; q-link = p-link; p-link = q; /*元素 elem 插入第 k1 个元素之后*/ return 0; /* Insert_List */ 单链表的删除运算。 int Delete_List (LinkList L, int k) /*L 为带头结点单链表的头指针*/ /*删除表中的第 k 个元素结点，若成功返回 0，否则，返回1*/ /*删除第 k 个元素，相当于令第 k1 个元
13、素结点中的指针指向第 k+1 个元素的结点*/ LinkList p,q; if (k = = 1) p = L; /*删除第一个元素结点*/ else p = Find_List(L,k1); /*查找表中的第 k1 个元素并令 p 指向该元素结点*/ if (!p) return 1; /*表中不存在第 k1 个元素*/ q = p-link; /*令 q 指向待删除的第 k 个元素结点*/20p-link = q-link; free(q); /*删除结点并释放结点空间*/ return 0; /* Delete_List */ 线性表采用链表作为存储结构时，只能顺序地访问元素。但其优点
14、是插入和删除操作 不需要移动元素。根据结点中指针信息的实现方式，还有其他几种链表结构。 双向链表：每个结点包含两个指针，指明直接前驱和直接后继元素，可在两个方向上 遍历其后及其前的元素。 循环链表：表尾结点的指针指向表中的第一个结点，可从表中任意结点开始遍历整个 链表。 静态链表：借助数组来描述线性表的链式存储结构。 若双向链表中结点的 front 和 next 指针域分别指示当前结点的直接前驱和直接后继， 则在双向链表中插入结点*s 时指针的变化情况如图中 (a)所示，其操作过程可表示为： s - front = p - front;p - front - next = s; /*或者表示为
15、 s - front - next = s;* /s - next = p; p - front = s; 在双向链表中删除结点时指针的变化情况如图所示，其操作过程可表示为： p - front - next = p - next; p - next - front = p - front;aapspbcbc(a)双链表中插入结点(b)双链表中删除节点 双链表中插入和删除节点时指针的变化2.2 栈栈栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最 后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来） 。栈是只能在某一端插入和删除的特殊线性表
16、。用桶堆积物品，先堆进来的压在底下， 随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是 不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈 底。插入一般称为进栈（PUSH） ，删除则称为退栈（POP） 。 栈也称为后进先出表。栈一 般使用数组实现，并设置一个栈顶指针 TOP。1、进栈（PUSH）算法若 TOP时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则 溢出；不满则作） ；置 TOP=TOP+1（栈指针加，指向进栈地址） ；21S(TOP)=X，结束（X 为新进栈的元素） ；2、退栈（POP）算法若 TOP0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢； 不空则作)；X=S(SOP)， （
