面向对象的数据结构

1、面向对象的数据结构面向对象的数据结构 山西省高校计算机精品课程及优质教学资源山西省高校计算机精品课程及优质教学资源建设与共享研讨会山西山西 太原太原 20082008年年4 4月月2020日日 问我祖先在何处，山西洪洞大槐树问我祖先在何处，山西洪洞大槐树 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 2山西太原（交城）古郊麻会村山西太原（交城）古郊麻会村 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 3内容提要内容提要n1. 教学内容教学内容n2. 数据的定义数据的定义n3. 抽象数据类型抽象数据类型n4. 教学案例教学案例n5. 网络教学资源网络教学资源数据结构在

2、计算机学科中的地位数据结构在计算机学科中的地位n最重要的主干基础课程最重要的主干基础课程n就是就是“最最”，没有，没有“之一之一”n承前启后的重要作用承前启后的重要作用n程序设计能力程序设计能力“质的飞跃质的飞跃”n操作系统、编译器、数据库系统、操作系统、编译器、数据库系统、 网络、软件工程网络、软件工程 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 4 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 5 图 4.1 计算机科学技术学科课程体系 专专 业业 基基 础础 课课 专 业 选修 课 学学院院平平台台课课 信息科学技术概论 数学基础数学基础 数学分析 I/II

3、/III, 高等数学 I/II 高等代数 I / II , 线性代数 理论基础理论基础 集合论与图论 代数结构与组合数学 数理逻辑 概率统计 A 算法设计与分析 硬件基础硬件基础 数字逻辑设计 * 数字逻辑设计实验 微机原理 * 微机实验 计算机组织与体系结构 * 计算机组织与体系结构实验 计算机理论计算机理论 理论计算机科学基础 初等数论及其应用 随机过程引论 软件工程软件工程 软件工程 面向对象技术引论 中间件技术导论 软件测试 面向服务的架构 计算机网络计算机网络 计算机网络 Web技术概论 网络与 Web 程序设计 网络协议分析与设计 信息安全引论 计算机体系结构计算机体系结构 汇编程

4、序设计 嵌入式系统概论 数字信号与多媒体处理器 数据管理数据管理 数据库概论 数据库原理与技术 数据仓库与数据挖掘 空间与多媒体数据库 Web 数据管理 自然语言处理自然语言处理 自然语言处理导论语言统计分析 现代信息检索导论 信息检索导论 信息检索导论年数据库概论 数据仓库与数据挖掘 计算智能与知识发现计算智能与知识发现 智能信息处理 机器学习概论 智能信息系统实验 数字媒体与人机交互数字媒体与人机交互 数字媒体技术基础 数字视频处理与分析 计算机图形学 视觉计算与处理 数字化艺术 人机交互 物理基础物理基础 力学(A,B) 电磁学(A,B) 物理 C 程序设计基础程序设计基础 计算概论 程

5、序设计实习 数据结构与算法数据结构与算法 A A 数据结构与算法实习数据结构与算法实习 电子学基础电子学基础 微电子与电路基础 基础电路实验 程序设计程序设计 问题求解与程序设计 Linux 程序设计 Windows 程序设计 Java 程序设计 信息检索导论 信息检索导论年数据库概论 数据仓库与数据挖掘 智能基础智能基础 脑与认知科学 信息论基础 人工智能基础 数值计算方法 信号与系统 软件基础软件基础 编译技术 操作系统 编译实习 操作系统实习 程序设计语言原理 科技交流与写作 先进技术专题 计算机科学技术导论 智能科学技术导论 编译技术 编译实习 操作系统 操作系统实习 计算机网络概论

6、计算机网络实习 数据结构与算法实习 智能感知智能感知 模式识别导论 生物信息处理 数字信号处理 语音信号处理 数字图像处理 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 6数据结构与算法实习数据结构与算法实习概率统计概率统计数据结构与算法数学分析高等数学数学分析高等数学集合论与图论集合论与图论算法分析与设计算法分析与设计程序设计实习程序设计实习高等代数线性代数高等代数线性代数计算概论计算概论程序设计语言原理程序设计语言原理数据库概论数据库概论编译原理编译原理操作系统操作系统软件工程软件工程计算机网络计算机网络 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 71. 数

7、据结构课程的主要内容数据结构课程的主要内容n理论理论n算法的数学基础算法的数学基础n算法的时间和空间度量算法的时间和空间度量n抽象抽象n排序、检索等重要问题类的有效算法排序、检索等重要问题类的有效算法n重要数据结构技术重要数据结构技术n设计设计n算法的选择、实现和测试算法的选择、实现和测试 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 82. 数据结构的定义数据结构的定义n数据的逻辑结构数据的逻辑结构n图图 树树 二叉树二叉树 线性表线性表n数据的存储结构数据的存储结构n顺序方法、链接方法顺序方法、链接方法n索引方法、散列方法索引方法、散列方法 n数据的运算数据的运算n增、删、查

8、、改、排序、检索增、删、查、改、排序、检索存存储储数据数据结构结构逻逻辑辑运运算算 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 93. 抽象数据类型抽象数据类型ADTn抽象数据类型是定义了一组运算抽象数据类型是定义了一组运算的数学模型的数学模型n把数据结构的存储与实现细节剥把数据结构的存储与实现细节剥离离n在适当的抽象层次上考虑程序的在适当的抽象层次上考虑程序的结构和算法结构和算法n封装和信息隐蔽封装和信息隐蔽 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 10栈的抽象数据类型栈的抽象数据类型 template class Stack/ 栈的元素类型为栈的元素类型

9、为ELEMStack(int s); /创建栈的实例创建栈的实例Stack(); /该实例消亡该实例消亡 void Push(ELEM item);/ item压入栈顶压入栈顶 ELEM Pop(); / 返回栈顶内容，并从栈顶弹出返回栈顶内容，并从栈顶弹出 ELEM GetTop(); / 返回栈顶内容，但不弹出返回栈顶内容，但不弹出 void MakeEmpty();/ 变为空栈变为空栈 Boolean IsEmpty(); / 返回真，若栈已空返回真，若栈已空 Boolean IsFull(); / 返回真，若栈已满返回真，若栈已满; 版权所有，转载或翻印必究版权所有，转载或翻印必究 P

10、age 11 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 124. 实践环节的训练实践环节的训练n数据结构与算法数据结构与算法， 3学分学分/周周3学时学时n每周布置每周布置3-4道书面作业或小程序实习道书面作业或小程序实习n数据结构与算法实习数据结构与算法实习，2学分学分/周周2学时学时 n一个学期一个学期6-8道道ACM竞赛题竞赛题n3-5道综合上机实习题道综合上机实习题n上机实习时间，上机实习时间，120小时小时/学生学生 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 135. 网络教学资源网络教学资源n建立了高质量的建立了高质量的 n1500ppt, 46

11、多小时多小时rm（全程录像）（全程录像）n还有其他补充录像还有其他补充录像n标准标准C+模板编写的可执行的源程序代码模板编写的可执行的源程序代码n9209代码总行数，非注释行代码总行数，非注释行7498n习题和上机题及其参考答案习题和上机题及其参考答案 nBBS讨论版讨论版(2008年年4月数据月数据)n18万位会员，帖子总数万位会员，帖子总数8375 篇篇 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 14 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 15网站内容网站内容n概述、前测概述、前测n知识点详解知识点详解n动画动画n习题解、新习题习题解、新习题n电子教

12、案电子教案npdf、视频、视频n扩展资源扩展资源n参考网站、论文、讲义参考网站、论文、讲义 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 16 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 17新教材新教材n张铭、王腾蛟、赵海燕，张铭、王腾蛟、赵海燕，数据结构与数据结构与算法算法，高等教育出版社，高等教育出版社，2008年年6月月国家级国家级“十一五十一五”规划教材规划教材n书号书号: ISBN 978-70-4-023961-4n张铭、赵海燕、王腾蛟、宋国杰，张铭、赵海燕、王腾蛟、宋国杰，数数据结构与算法实验教程据结构与算法实验教程，高等教育出，高等教育出版社，版

13、社，2009年年6月月国家级国家级“十一五十一五”规划教材规划教材老教材老教材n许卓群、杨冬青、唐世渭、张铭，许卓群、杨冬青、唐世渭、张铭，数据结构与算法数据结构与算法，高等教育出，高等教育出版社，版社，2004年年 7月。月。n张铭、赵海燕、王腾蛟，张铭、赵海燕、王腾蛟，数据结数据结构与算法学习指导与习题解构与算法学习指导与习题解析析，高等教育出版社，高等教育出版社，2005年年 9月。月。n书号书号: ISBN 7-04-017829-X 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 18参考教材参考教材n1. Thomas H.Cormen, Charles E.Leise

14、rson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MTI Press. 高等教育出版社影印。高等教育出版社影印。n2. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社电子工业出版社影印，影印，2003年年1月。月。n3. Sartaj Sahni, Data Structures, Algorithms, and Applications in C+. 机机械工业出版社影印版。械工业出版社影印版。 n4. William

15、Ford ， Data Structure with C+，清华大学出版社影印版清华大学出版社影印版 参考教材参考教材n5. 数据结构数据结构(用面向对象方法与用面向对象方法与C+语言描述语言描述)第第2版版,殷人昆主编殷人昆主编, 清华大学出版社清华大学出版社,2007年年6月月.n清华大学信息学院计算机系、软件学院教材清华大学信息学院计算机系、软件学院教材n清华考研第一参考书清华考研第一参考书 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 21教学讨论教学讨论1n算法描述语言算法描述语言n自然语言自然语言n类类Pascaln类类Cn类类C+n类类Javan尺有所长、寸有所短尺

16、有所长、寸有所短括号匹配括号匹配n问题：检查程序文件中的括号是否匹配问题：检查程序文件中的括号是否匹配n括号包括：括号包括：,(,),.n算法思想算法思想n逐个读入字符，忽略非括号字符逐个读入字符，忽略非括号字符n如果是左括号，记下来如果是左括号，记下来n如果是右括号，检查是否与最近读入的左括号如果是右括号，检查是否与最近读入的左括号匹配；如果不匹配，则匹配失败匹配；如果不匹配，则匹配失败n重复上述过程，如果读到文件尾部时，没有未重复上述过程，如果读到文件尾部时，没有未匹配的左括号留下，则匹配成功，否则，匹配匹配的左括号留下，则匹配成功，否则，匹配失败失败 版权所有，转载或翻印必究版权所有，转

17、载或翻印必究 Page 22自然语言描述的算法自然语言描述的算法采用栈保存中间数据采用栈保存中间数据n(1) 从左至右扫描表达式从左至右扫描表达式, 读取字符读取字符cn(2) 如果如果c是非括号字符是非括号字符, 继续步骤继续步骤1n(3) 否则否则, 如果如果c是左括号是左括号, 则入栈则入栈; n(4) 如果如果c是右括号是右括号, 则与栈顶元素比较则与栈顶元素比较n若栈空若栈空(右括号富余右括号富余), 或左右括号匹配不匹配，则结束或左右括号匹配不匹配，则结束n否则，符号目前还匹配否则，符号目前还匹配, 则继续扫描步骤则继续扫描步骤1n(5) 如果遇到扫描符如果遇到扫描符, 则判断栈是

18、否空则判断栈是否空n空空, 则说明匹配则说明匹配n否则否则, 说明左括号富余说明左括号富余 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 23张铭张铭编写编写 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 244* x*2a+-）c（ 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 25语言描述，语言描述，C+代码和注释代码和注释n1. 语言描述和注释足够表达思想；语言描述和注释足够表达思想；n2. 代码段可以培养学生严谨的算法代码段可以培养学生严谨的算法表述能力；表述能力；n算法分析教材的太抽象算法分析教材的太抽象n3. C+n非常适宜于表达抽象数据类

19、型非常适宜于表达抽象数据类型nC+, Java是主流的编程语言是主流的编程语言n简化了输入输出简化了输入输出 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 26计算机过时技能计算机过时技能TOP10 n1.Cobol 、2. Nonrelational DBMS（非关系数据库管理系统）（非关系数据库管理系统） n3. Non-IP networks（非（非IP网络）、网络）、4. CC:Mail n5. ColdFusion n6. C 语言设计语言设计 n7. PowerBuilder、8. CNE（NetWare认证工程师）认证工程师） n9. PC网络管理员、网络管理员、1

20、0. OS/2 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 27抽象数据类型抽象数据类型n抽象数据类型抽象数据类型n实质为实质为“逻辑结构逻辑结构 + 运算运算/操作操作”n隐蔽了存储实现细节隐蔽了存储实现细节n上层算法以一致的形式调用底层数据结构上层算法以一致的形式调用底层数据结构n例如在例如在STL C+中中nStack.push(x)n顺序栈，链式栈顺序栈，链式栈n上层调用语句不需要改变上层调用语句不需要改变 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 28纯纯C语言的栈抽象数据类型？语言的栈抽象数据类型？nInitStack(S) nClearStack

21、(S) nIsEmpty(S) nIsFull(S) nPush(S,x) nPop(S,x) nGetTop(S,x) 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 29C顺序栈的进栈操作顺序栈的进栈操作ntypedef struct StackElementType elemStack_Size; /*用来存放栈中元素的一维数组用来存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标用来存放栈顶元素的下标*/ SeqStack;nint Push(SeqStack * S, StackElementType x) if (S-top= Stack_Size

22、) return(FALSE); /*栈已满栈已满*/ S-top+; S-elemS-top=x; return(TRUE); 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 30C顺序栈的出栈操作顺序栈的出栈操作int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*栈为空栈为空*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改栈顶指针修改栈顶指针 */ return(TRUE); 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 31C链栈定义链栈定义

23、typedef struct node StackElementType data; struct node *next; LinkStackNode; typedef LinkStackNode *LinkStack; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 32C链栈的进栈操作链栈的进栈操作int Push(LinkStack top, StackElementType x) /* 将数据元素将数据元素x压入栈压入栈top中中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackN

24、ode); if (temp=NULL) return(FALSE); /* 申请空间失败申请空间失败 */ temp-data=x; temp-next=top-next; top-next=temp; /* 修改当前栈顶指针修改当前栈顶指针 */ return(TRUE); 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 33C链栈的出栈操作链栈的出栈操作int Pop(LinkStack top, StackElementType *x) /* 将栈将栈top的栈顶元素弹出，放到的栈顶元素弹出，放到x所指的存储空间所指的存储空间中中 */ LinkStackNode * te

25、mp; temp=top-next; if(temp=NULL) /*栈为空栈为空*/ return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 释放存储空间释放存储空间 */ return(TRUE); 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 34顺序栈：顺序栈：C版本括号匹配算法版本括号匹配算法void BracketMatch(char *str) SeqStack S; int i; char ch; InitStack(&S); for(i=0; stri!=0; i+) switch(

26、stri) case (: case : case : Push(&S,stri); break; case ): case : case : if (IsEmpty(&S) printf(n右括号多余右括号多余!); return; else GetTop (&S,&ch); if (Match(ch,stri) Pop(&S,&ch); else printf(n括号不匹配括号不匹配!); return; /*else*/ /*switch*/ /*for*/ if (IsEmpty(&S) printf(n括号匹配括号匹配!); e

27、lse printf(n左括号多余左括号多余 ); 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 35链栈：链栈：C版本括号匹配算法版本括号匹配算法void BracketMatch(char *str) LinkStack S; int i; char ch; InitStack(/*&*/S); for(i=0; stri!=0; i+) switch(stri) case (: case : case : Push(/*&*/S, stri); break; case ): case : case : if (IsEmpty(S) printf(n右括号多余

28、右括号多余!); return; else GetTop (/*&*/S,&ch); if (Match(ch,stri) Pop(/*&*/S,&ch); else printf(“n括号不匹配括号不匹配!); return; /*else*/ /*switch*/ /*for*/ if (IsEmpty(/*&*/S) printf(n括号匹配括号匹配!); else printf(n左括号多余左括号多余 ); 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 36C数据类型的问题数据类型的问题n1. 在同一个程序中，如果栈的在同一个程序中

29、，如果栈的StackElementType 不同不同n需要定义不同的栈需要定义不同的栈n2. 从顺序栈改为链式栈从顺序栈改为链式栈n上层调用语句一定要改变上层调用语句一定要改变n程序中所有的变量定义都需要修改程序中所有的变量定义都需要修改n函数参数传递也要改变函数参数传递也要改变n3. 最严重的问题最严重的问题n勉强用结构化的勉强用结构化的C来描述来描述ADT, 造成学生的困惑造成学生的困惑 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 37用用C+讲授数据类型的好处讲授数据类型的好处n1. 在同一个程序中，如果栈的在同一个程序中，如果栈的StackElementType 不同不

30、同n不需要定义不同的栈不需要定义不同的栈, template n程序中所有的变量定义都不需要修改程序中所有的变量定义都不需要修改n2. 从顺序栈改为链式栈从顺序栈改为链式栈n只需要改变对头文件的引用只需要改变对头文件的引用, 程序代码完全不变程序代码完全不变n真正的软件复用真正的软件复用n真正的抽象数据类型真正的抽象数据类型ADTn3. 最大的好处最大的好处n给学生更好的抽象能力训练给学生更好的抽象能力训练, 并且与主流技术一致并且与主流技术一致 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 38C+C+栈的抽象数据类型栈的抽象数据类型 template class Stack/

31、 栈的元素类型为栈的元素类型为ELEMStack(int s); /创建栈的实例创建栈的实例Stack(); /该实例消亡该实例消亡 void Push(ELEM item);/ item压入栈顶压入栈顶 ELEM Pop(); / 返回栈顶内容，并从栈顶弹出返回栈顶内容，并从栈顶弹出 ELEM GetTop(); / 返回栈顶内容，但不弹出返回栈顶内容，但不弹出 void MakeEmpty();/ 变为空栈变为空栈 Boolean IsEmpty(); / 返回真，若栈已空返回真，若栈已空 Boolean IsFull(); / 返回真，若栈已满返回真，若栈已满; 版权所有，转载或翻印必究

32、版权所有，转载或翻印必究 Page 39C+C+顺序栈顺序栈 template class Stack private:ELEM *ElmList; / 存放数据元素的指针变量存放数据元素的指针变量 int top; / 栈顶在的位置，即下标值栈顶在的位置，即下标值 / 当新元素压入或栈内容弹出，当新元素压入或栈内容弹出，top值随之增减值随之增减 int maxsize; / 栈的最大长度栈的最大长度 /构建栈的实例，向量空间长度为构建栈的实例，向量空间长度为size public: Stack(int size); ; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 40压入栈

33、顶压入栈顶 template void Stack:Push(ELEM item)/判非栈满，否则栈溢出，退出运行判非栈满，否则栈溢出，退出运行assert(!IsFull(); top+; /栈顶栈顶ElmListtop=item; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 41从栈顶弹出从栈顶弹出 template ELEM Stack:Pop()/判栈非空，否则断言栈空异常，判栈非空，否则断言栈空异常， /退出运行退出运行assert(!IsEmpty(); return ElmListtop-; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 42顺序栈：

34、压入栈顶顺序栈：压入栈顶 template void Stack:Push(ELEM item)assert(!IsFull(); / 栈满，则退出栈满，则退出top+; / 栈顶指针移位栈顶指针移位ElmListtop=item; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 43顺序栈：从栈顶弹出顺序栈：从栈顶弹出 template ELEM Stack:Pop()assert(!IsEmpty(); / 栈空，则退出栈空，则退出return ElmListtop-; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 44C+C+链式栈链式栈 template st

35、ruct ListNode ELEM data; ListNode * link;template class Stack private: ListNode *top; int size; / Count number of elementspublic: Stack(int sz = LIST_SIZE) top = NULL; size = 0; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 45链式栈：压入栈顶链式栈：压入栈顶 void Push(const ELEM & item) ListNode *temp;temp = new ListNode; / 若无

36、存储空间则异常，程序退出运行若无存储空间则异常，程序退出运行assert(!temp=NULL); size+;temp-data = item;temp-link = top; / 老栈顶指针老栈顶指针top = temp;/ 新栈顶指针新栈顶指针 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 46链式栈：从栈顶弹出链式栈：从栈顶弹出 ELEM Pop() /判栈非空，否则断言栈空异常，程序退出判栈非空，否则断言栈空异常，程序退出assert(!IsEmpty(); ELEM result = top-data; /暂存栈顶内容暂存栈顶内容ListNode * temptr;t

37、emptr = top; /老栈顶指针老栈顶指针top = top-link ; /新栈顶指针新栈顶指针 size-;delete temptr; /释放空间释放空间return result; /返回的是弹出内容返回的是弹出内容 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 47C+版本括号匹配算法版本括号匹配算法void BracketMatch(char *str) Stack S; int i; char ch; / 自动初始化自动初始化 for(i=0; stri!=0; i+) switch(stri) case (: case : case : S.Push(str

38、i); break; case ): case : case : if (S.IsEmpty( ) cout右括号多余右括号多余!; return; else ch = S.GetTop( ); if (Match(ch,stri) ch = S.Pop( ); else cout 括号不匹配括号不匹配!; return; /*else*/ /*switch*/ /*for*/ if (S.IsEmpty( ) cout括号匹配括号匹配!; else cout左括号多余左括号多余 ; 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 48教学讨论教学讨论2n算法和数据结构的关系？算法

39、和数据结构的关系？n基本数据结构和算法的重现？基本数据结构和算法的重现？n怎样训练综合能力？怎样训练综合能力？n实践教学？实践教学？n怎样怎样减少减少抄袭？抄袭？天网公司总裁天网公司总裁 雷凯雷凯北大北大94级级n张老师在整个课程的教学中，通过其张老师在整个课程的教学中，通过其精心选择精心选择的课程教材，认真精辟的课堂讲解，引人入胜的课程教材，认真精辟的课堂讲解，引人入胜的案例分析，巧妙的教学思路设计，丰富系统的案例分析，巧妙的教学思路设计，丰富系统的训练方法，和细致入微的与学生互动教学的训练方法，和细致入微的与学生互动教学，真正的体现了一位导师给每一位渴望知识的学真正的体现了一位导师给每一位

40、渴望知识的学生生“授之以渔授之以渔”的教学精神，将的教学精神，将数据结构与数据结构与算法算法的知识和精髓由一本本经典的理论著作，的知识和精髓由一本本经典的理论著作，转化成学生所需要的，活生生有实践意义的知转化成学生所需要的，活生生有实践意义的知识，深深地印在了每一位学生的心里。识，深深地印在了每一位学生的心里。 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 49徐颖徐颖北大北大94本，本，00硕硕2003级美国斯坦福大学计算机系博士级美国斯坦福大学计算机系博士WebVLDB、CIKM、PODSn我进入我进入斯坦福斯坦福的第一个学期就选的第一个学期就选择了直接考试，而且惊喜地发现，

41、择了直接考试，而且惊喜地发现，算法与数据结构考试的知识点和算法与数据结构考试的知识点和张铭老师在北大开设课程的讲授张铭老师在北大开设课程的讲授内容十分一致内容十分一致，所以张铭老师的，所以张铭老师的课程讲义和录像就成为我的主要课程讲义和录像就成为我的主要复习资料复习资料 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 50陈华陈华97本，本，01硕硕酷讯公司总裁酷讯公司总裁n张老师给我们年级带了张老师给我们年级带了计算引论计算引论和和数据结构数据结构。这两门课程共同的特就是创造性思维的刺激和超强。这两门课程共同的特就是创造性思维的刺激和超强度的大项目实习度的大项目实习n张老师在张老

42、师在计算引论计算引论给我们打下了雄厚的给我们打下了雄厚的Pascal结结构化程序设计功底。构化程序设计功底。数据结构数据结构课程采用了张老师课程采用了张老师翻译的面向对象翻译的面向对象C+版版数据结构与算法分析数据结构与算法分析新教新教材材n由于是主讲老师亲自翻译的教材，她对教材有着深刻由于是主讲老师亲自翻译的教材，她对教材有着深刻的理解，上课时能够将问题讲述得非常清晰。我们在的理解，上课时能够将问题讲述得非常清晰。我们在张老师带领下，张老师带领下，几周内从几周内从Pascal转换到转换到C+，对我们，对我们以后很快接受新理论、新技术，是一种很好的锻炼以后很快接受新理论、新技术，是一种很好的锻

43、炼 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 51梅俏竹梅俏竹北大北大99级级UIUC计算机系博士生计算机系博士生SIGKDD、SIGIR、WWW，ACM TKDDn记得记得当年数据结构的大实习作业是设计并实现一个简当年数据结构的大实习作业是设计并实现一个简单的搜索引擎单的搜索引擎。n而当时只不过是而当时只不过是2000年，现在搜索引擎的巨头年，现在搜索引擎的巨头Google远未上市，百度则刚刚成立，微软和雅虎甚至远未上市，百度则刚刚成立，微软和雅虎甚至还没开始研发自己的搜索引擎。还没开始研发自己的搜索引擎。n北大的本科生课程实习就能有这样的前瞻性的问题绝北大的本科生课程实习

44、就能有这样的前瞻性的问题绝对是值得称道的。对是值得称道的。n 大家都不约而同地提到数据结构这门课程对自己的影大家都不约而同地提到数据结构这门课程对自己的影响。归结起来，大家都认为张铭老师的响。归结起来，大家都认为张铭老师的“数据结构与数据结构与算法课程算法课程”内容细致实用，讲授深入浅出，课程实习内容细致实用，讲授深入浅出，课程实习精巧而具前瞻性，对培养学生分析和解决问题，创造精巧而具前瞻性，对培养学生分析和解决问题，创造性思考，和团队合作的能力都有很好的作用性思考，和团队合作的能力都有很好的作用 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 52银平银平00本，本，04硕，助教

45、硕，助教酷讯公司酷讯公司n张铭老师课堂上引导以及深刻讲解让我张铭老师课堂上引导以及深刻讲解让我对这门课程产生了浓厚兴趣，并极大的对这门课程产生了浓厚兴趣，并极大的训练了我的思维能力。数据结构的几个训练了我的思维能力。数据结构的几个大的实习让我打下了坚实的算法与工程大的实习让我打下了坚实的算法与工程基础。基础。n 这门课程几乎年年都有所变动这门课程几乎年年都有所变动，如降低，如降低作业的数量但提高作业的质量，将实习作业的数量但提高作业的质量，将实习课程分离，采用课程分离，采用ACM的题目等等。的题目等等。 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 53赵翔宇赵翔宇01本，本，0

46、5硕，助教硕，助教n最重要的是，我们要看同学们做作业的时候是否是独最重要的是，我们要看同学们做作业的时候是否是独立完成，立完成，张老师的诚实代码张老师的诚实代码宣言相信每一个选过这门宣言相信每一个选过这门课的同学都会牢记在心中，先成人，再成才，这也是课的同学都会牢记在心中，先成人，再成才，这也是张老师在上这门课时教给我们很重要的一点。张老师在上这门课时教给我们很重要的一点。n无论平时的研究、项目，还是求职，甚至以后的工作无论平时的研究、项目，还是求职，甚至以后的工作生涯，我们都会体会到数据结构和算法的重要性。生涯，我们都会体会到数据结构和算法的重要性。n在今年的求职过程中，无论碰到怎样复杂的数

47、据结构在今年的求职过程中，无论碰到怎样复杂的数据结构题，我都能轻松应付，因为在解题前，我对自己有信题，我都能轻松应付，因为在解题前，我对自己有信心，我有张老师为我打下的深厚基础。心，我有张老师为我打下的深厚基础。 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 54Honor Code（诚实代码保证）n/ 我真诚地保证：我真诚地保证： n/ 我自己独立地完成了整个程序从分析、设计到编码的所有工作。我自己独立地完成了整个程序从分析、设计到编码的所有工作。n/ 如果在上述过程中，我遇到了什么困难而求教于人，如果在上述过程中，我遇到了什么困难而求教于人，n/ 那么，我将在程序实习报告中详

48、细地列举我所遇到的问题，那么，我将在程序实习报告中详细地列举我所遇到的问题，n/ 以及别人给我的提示。以及别人给我的提示。n/ 在此，我感谢在此，我感谢 XXX, , XXX对我的启发和帮助。对我的启发和帮助。n/ 我的程序里中凡是引用到其他程序或文档之处，我的程序里中凡是引用到其他程序或文档之处，n/ 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,n/ 我都已经在程序的注释里很清楚地注明了引用的出处。我都已经在程序的注释里很清楚地注明了引用的出处。n/ 我从未没抄袭过别人的程序，也没有盗用别人的程序，我从未没抄袭过别人的程序

49、，也没有盗用别人的程序，n/ 不管是修改式的抄袭还是原封不动的抄袭。不管是修改式的抄袭还是原封不动的抄袭。 n/ 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 55李逸男李逸男北大北大03级级香港科技大学博士香港科技大学博士本科两篇本科两篇SIGMOD07 Demo论文论文n起着承前启后的重要作用起着承前启后的重要作用。n在张老师的悉心指导和严格要求下，在张老师的悉心指导和严格要求下，经过数据结构课程的理论和经过数据结构课程的理论和实践的磨练，同学们从刚刚会写简单的程序，迅速实践的磨练，同学们从刚刚会写简单的程序，迅速“升级升级”为能为能够完成各种复杂系统设计和实现的计算机高手够

50、完成各种复杂系统设计和实现的计算机高手。我们在随后的各。我们在随后的各种课程中完成的迷你操作系统、编译器、数据库系统等课程设计种课程中完成的迷你操作系统、编译器、数据库系统等课程设计，很大深度依赖于在数据结构这门课程所打下的坚实的理论基础，很大深度依赖于在数据结构这门课程所打下的坚实的理论基础和动手能力。和动手能力。n国际最前沿的研究成果其实往往就是对相对基本的数据结构和算国际最前沿的研究成果其实往往就是对相对基本的数据结构和算法在某些特殊应用背景进行的一些有针对性的优化和扩展，而这法在某些特殊应用背景进行的一些有针对性的优化和扩展，而这些相对基本的数据结构在张老师的课程中绝大多都有涉及，还有

51、些相对基本的数据结构在张老师的课程中绝大多都有涉及，还有一些是张老师在课堂上加入的一些扩展内容。一些是张老师在课堂上加入的一些扩展内容。n细细回想起来，很多现在已经非常熟悉的知识还都是在张老师的细细回想起来，很多现在已经非常熟悉的知识还都是在张老师的数据结构课上打下的基础。数据结构课上打下的基础。 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 56李浩源李浩源北大北大04级级2005年年ACM/ICPC 全球第十一名全球第十一名2006年年ACM/ICPC 全球第十三名全球第十三名即将赴美国即将赴美国Cornell攻读计算机博士学位攻读计算机博士学位n数据结构还有一个很大的特色就

52、是它不单单讲数据结构还有一个很大的特色就是它不单单讲授理论内容，授理论内容，张老师还配套开设了数据结构实张老师还配套开设了数据结构实习课程，以锻炼提高学生的实践能力习课程，以锻炼提高学生的实践能力。n在实习课上，同学把理论课上的很多算法得以在实习课上，同学把理论课上的很多算法得以实现，上课更加积极的讨论。实现，上课更加积极的讨论。n大家在欢乐的气氛下达到了理论与实践水平共大家在欢乐的气氛下达到了理论与实践水平共同提高目的，日后同学之间谈起来，都很怀念。同提高目的，日后同学之间谈起来，都很怀念。 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 57柳明海柳明海北大北大04级级n这门课程的教材非常好，教材的深度和广度都这门课程的教材非常好，教材的深度和广度都很不错，由于是主讲老师自己编写的教材，对很不错，由于是主讲老师自己编写的教材，对教材有着深刻的理解，上课时能够将问题讲述教材有着深刻的理解，上课时能够将问题讲述得非常清晰，还能够联系实际应用，而不是简得非常清晰，还能够联系实际应用，而不是简单的学习。单的学习。 n课堂的氛围非常的活泼，老师同