南邮ACM算法与数据结构设计(2010-2011-2第4讲)

《南邮ACM算法与数据结构设计(2010-2011-2第4讲)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、陈老师（南邮ACM竞赛教练）南京邮电大学计算机学院联系方式电话：138-139-30027电邮：acm@njupt.edu.cnACM算法与数据结构设计班级：仙林校区ACM选修班上课地点和时间理论：教2－402：星期3（18:30开始）实践：（仙林）计算中心课程安排1、课堂授课第2、3、4、6、8、10、11、13周星期三晚第5大节，教室为教2-402。【内容】第1讲:ACM/ICPC概述第2讲:竞赛平台与工具第3讲:竞赛语言基础第4讲:数据结构设计第5讲:高效算法设计第6讲:数学求解方法第7讲:STL求解设计2、上机训练第5、9、12、14周星期二晚

2、第5大节，计算中心A机房训练平台：http://acm.njupt.edu.cn第4讲:ACM竞赛之数据结构设计线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。树形结构：数据元素之间存在一对多关系。图状结构：数据元素之间存在多对多的关系。每个结点前驱和后继的数目都不同。集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。(a)集合结构(b)线性结构(c)树形结构(d)图状结构四种基本的结构关系第4讲:ACM竞赛之数据结构设计4.1队列（Queue）队列的示意图Q=(a0,a1,…,an-1)a0a1…an-1fron

3、trear入队出队第4讲:ACM竞赛之数据结构设计4.1队列（Queue）卡片游戏桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1～n。当至少还剩两张牌时进行以下操作：把第一张扔掉，然后把新的第一张放到整叠牌的最后。输入n，n≤1000000。输出每次扔掉的牌，以及最后剩下的牌。样例输入：7样例输出：1357426第4讲:ACM竞赛之数据结构设计4.1队列（Queue）卡片游戏#includeconstintMAXN=50;intqueue[MAXN];intmain(){inti,n,front,rear;scan

4、f("%d",&n);for(i=0;i#includeusingnamespacestd;queueq;intmain(){intn,front,rear;scanf("%d",&

5、n);for(inti=0;i

6、顺序编号为1～n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移入C，就不能再回到A了；一旦从C移入B，就不能回到C了。换句话说，在任意时刻，只有两种选择：A→C和C→B样例输入5123455541236654321样例输出YesNoYes第4讲:ACM竞赛之数据结构设计4.2堆栈（Stack）铁轨#includeconstintMAXN=1000+10;intn,targ

7、et[MAXN];intmain(){while(scanf("%d",&n)==1){intstack[MAXN],top=0;intA=1,B=1;for(inti=1;i<=n;i++)scanf("%d",&target[i]);intok=1;while(B<=n){if(A==target[B]){A++;B++;}elseif(top&&stack[top]==target[B]){top--;B++;}elseif(A<=n)stack[++top]=A++;else{ok=0;break;}}printf("%s",ok?"Yes

8、":"No");}return0;}第4讲:ACM竞赛之数据结构设计4.2堆栈（Stack）铁