南邮ACM算法与数据结构设计(201020112第4讲)课程.ppt

ACM算法与数据结构设计 班 级 ：仙林校区ACM选修班 上课地点和时间 理论：教2－402：星期3 （18:30开始） 实践：（仙林）计算中心 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 第4讲:ACM竞赛之数据结构设计 4.4 二叉树 层次遍历（Trees on the Level） 处理输入（建立二叉树） const int MAXN = 256; char s[MAXN + 10]; int read_input() { failed = 0; remove_tree(root); root = newnode(); for (;;) { if (scanf(%s, s) != 1) return 0; if (!strcmp(s, ())) break; int v; sscanf(s[1], %d, v); addnode(v, strchr(s, ,)+1); } return 1; } 4.4 二叉树 层次遍历（Trees on the Level） BFS（二叉树遍历） int n = 0, ans[MAXN]; int bfs() { Node* q[MAXN]; int front = 0, rear = 1; q[0] = root; while (front rear) { Node* u = q[front++]; if (!u-have_value) return 0; ans[n++] = u-v; if (u-left != NULL) q[rear++] = u-left; if (u-right != NULL) q[rear++] = u-right; } return 1; } 4.4 二叉树 层次遍历（Trees on the Level） Main（主控程序） int main() { while (read_input()) { n=0; if (!bfs()) failed = 1; if (failed) printf(-1\n); else { for (int i = 0; i n; i++) if (0==i) printf(%d, ans[i]); else printf( %d, ans[i]); printf(\n); } } return 0; } 4.5 图 n1 L1 n2 C