南邮ACM程序设计与算法第5讲.ppt

ACM程序设计与算法 班 级 ：仙林校区2009级竞赛培训同学 任课教师 ：陈 志 上课地点和时间 理论：教3－101：星期3 （18:30开始） 实践：（仙林）计算中心 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 第5讲:ACM竞赛之数据结构 5.5 图 结构（邻接表） typedef struct lnode *glink; struct lnode{ int v; //边的另一个顶点 glink next; //邻接表指针 } typedef struct graph *Graph; struct graph{ int n; int e; glink *adj; //邻接表数组 }Lgraph; 陈志老师（南邮ACM竞赛教练） 南京邮电大学计算机学院 联系方式 电话：138-139-30027 电邮：acm@njupt.edu.cn 线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。 树形结构：数据元素之间存在一对多关系。 图状结构：数据元素之间存在多对多的关系。每个结点前驱和后继的数目都不同。 集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。 (a)集合结构 (b)线性结构 (c)树形结构 (d)图状结构 四种基本的结构关系 5.1 队列（Queue） 队列的示意图 Q=(a0,a1,…,an-1) a0 a1 … an-1 front rear 入队 出队 5.1 队列（Queue） 卡片游戏 桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1～n。当至少还剩两张牌时进行以下操作：把第一张扔掉，然后把新的第一张放到整叠牌的最后。 输入n，n≤1000000。 输出每次扔掉的牌，以及最后剩下的牌。 样例输入：7 样例输出：1 3 5 7 4 2 6 5.1 队列（Queue） 卡片游戏 #includestdio.h const int MAXN = 50; int queue[MAXN]; int main() { int i, n, front, rear; scanf(%d, n); for (i = 0; i n; i++) queue[i] = i+1; front = 0; rear = n; while (front rear) { printf(“%d ”, queue[front++]); //格式有待改进 queue[rear++] = queue[front++]; } return 0; } 5.1 队列（Queue） 卡片游戏 #includecstdio #includequeue using namespace std; queueint q; int main() { int n, front, rear; scanf(%d, n); for (int i = 0; i n; i++) q.push(i+1); while (!q.empty()) { printf(%d , q.front()); //格式有待改进 q.pop(); q.push(q.front()); q.pop(); } return 0; } 5.2 堆栈（Stack） a0 a1 … ai … an-1 入栈 出栈 bottom