面向对象数据结构.ppt

面向对象的数据结构,张 铭,北京大学信息科学与技术学院 /mzhang/ds/ /pkujpk/course/sjjg/ 山西省高校计算机精品课程及优质教学资源 建设与共享研讨会 山西 太原 2008年4月20日,问我祖先在何处，山西洪洞大槐树,北京大学信息学院 版权所有，转载或翻印必究 Page 2,山西太原（交城）古郊麻会村,北京大学信息学院 版权所有，转载或翻印必究 Page 3,内容提要,1. 教学内容 2. 数据的定义 3. 抽象数据类型 4. 教学案例 5. 网络教学资源,数据结构在计算机学科中的地位,最重要的主干基础课程 就是“最”，没有“之一” 承前启后的重要作用 程序设计能力“质的飞跃” 操作系统、编译器、数据库系统、 网络、软件工程,北京大学信息学院 版权所有，转载或翻印必究 Page 4,北京大学信息学院 版权所有，转载或翻印必究 Page 5,北京大学信息学院 版权所有，转载或翻印必究 Page 6,数据结构与算法实习,概率统计,数据结构与算法,数学分析高等数学,集合论与图论,算法分析与设计,程序设计实习,高等代数线性代数,计算概论,程序设计语言原理,数据库概论,编译原理,操作系统,软件工程,计算机网络,北京大学信息学院 版权所有，转载或翻印必究 Page 7,1. 数据结构课程的主要内容,理论 算法的数学基础 算法的时间和空间度量 抽象 排序、检索等重要问题类的有效算法 重要数据结构技术 设计 算法的选择、实现和测试,2. 数据结构的定义,数据的逻辑结构 图树二叉树线性表 数据的存储结构 顺序方法、链接方法 索引方法、散列方法 数据的运算 增、删、查、改、排序、检索,北京大学信息学院 版权所有，转载或翻印必究 Page 9,3. 抽象数据类型ADT,抽象数据类型是定义了一组运算的数学模型 把数据结构的存储与实现细节剥离 在适当的抽象层次上考虑程序的结构和算法 封装和信息隐蔽,北京大学信息学院 版权所有，转载或翻印必究 Page 10,栈的抽象数据类型,template class Stack / 栈的元素类型为ELEM Stack(int s); /创建栈的实例 Stack(); /该实例消亡 void Push(ELEM item); / item压入栈顶 ELEM Pop(); / 返回栈顶内容，并从栈顶弹出 ELEM GetTop(); / 返回栈顶内容，但不弹出 void MakeEmpty(); / 变为空栈 Boolean IsEmpty(); / 返回真，若栈已空 Boolean IsFull(); / 返回真，若栈已满 ;,北京大学信息学院 版权所有，转载或翻印必究 Page 11,北京大学信息学院 版权所有，转载或翻印必究 Page 12,4. 实践环节的训练,数据结构与算法， 3学分/周3学时 每周布置3-4道书面作业或小程序实习 数据结构与算法实习，2学分/周2学时 一个学期6-8道ACM竞赛题 3-5道综合上机实习题 上机实习时间，120小时/学生,北京大学信息学院 版权所有，转载或翻印必究 Page 13,5. 网络教学资源,建立了高质量的 /mzhang/ds/ /pkujpk/course/sjjg/ 1500ppt, 46多小时rm（全程录像） 还有其他补充录像 标准C+模板编写的可执行的源程序代码 9209代码总行数，非注释行7498 习题和上机题及其参考答案 BBS讨论版(2008年4月数据) 18万位会员，帖子总数8375 篇,北京大学信息学院 版权所有，转载或翻印必究 Page 14,北京大学信息学院 版权所有，转载或翻印必究 Page 15,网站内容,概述、前测 知识点详解 动画 习题解、新习题 电子教案 pdf、视频 扩展资源 参考网站、论文、讲义,北京大学信息学院 版权所有，转载或翻印必究 Page 16,/computer/teachercenter/teacherdetail?userid=zhangm,/,北京大学信息学院 版权所有，转载或翻印必究 Page 17,新教材,张铭、王腾蛟、赵海燕，数据结构与算法，高等教育出版社，2008年6月国家级“十一五”规划教材 书号: ISBN 978-70-4-023961-4 张铭、赵海燕、王腾蛟、宋国杰，数据结构与算法实验教程，高等教育出版社，2009年6月国家级“十一五”规划教材,老教材,许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，2004年 7月。 张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，2005年 9月。 书号: ISBN 7-04-017829-X,北京大学信息学院 版权所有，转载或翻印必究 Page 18,参考教材,1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MTI Press. 高等教育出版社影印。 2. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印，2003年1月。 3. Sartaj Sahni, Data Structures, Algorithms, and Applications in C+. 机械工业出版社影印版。 4. William Ford ， Data Structure with C+，清华大学出版社影印版,参考教材,5. 数据结构(用面向对象方法与C+语言描述)第2版,殷人昆主编, 清华大学出版社,2007年6月. 清华大学信息学院计算机系、软件学院教材 清华考研第一参考书 /learn/courseinfo.jsp?course_id=50125,北京大学信息学院 版权所有，转载或翻印必究 Page 21,教学讨论1,算法描述语言 自然语言 类Pascal 类C 类C+ 类Java 尺有所长、寸有所短,括号匹配,问题：检查程序文件中的括号是否匹配 括号包括：,(,),. 算法思想 逐个读入字符，忽略非括号字符 如果是左括号，记下来 如果是右括号，检查是否与最近读入的左括号匹配；如果不匹配，则匹配失败 重复上述过程，如果读到文件尾部时，没有未匹配的左括号留下，则匹配成功，否则，匹配失败,北京大学信息学院 版权所有，转载或翻印必究 Page 22,自然语言描述的算法,采用栈保存中间数据 (1) 从左至右扫描表达式, 读取字符c (2) 如果c是非括号字符, 继续步骤1 (3) 否则, 如果c是左括号, 则入栈; (4) 如果c是右括号, 则与栈顶元素比较 若栈空(右括号富余), 或左右括号匹配不匹配，则结束 否则，符号目前还匹配, 则继续扫描步骤1 (5) 如果遇到扫描符, 则判断栈是否空 空, 则说明匹配 否则, 说明左括号富余,北京大学信息学院 版权所有，转载或翻印必究 Page 23,北京大学信息学院 张铭编写 版权所有，转载或翻印必究 Page 24,4,*,x,*,2,a,+,-,）,c,（,北京大学信息学院 版权所有，转载或翻印必究 Page 25,语言描述，C+代码和注释,1. 语言描述和注释足够表达思想； 2. 代码段可以培养学生严谨的算法表述能力； 算法分析教材的太抽象 3. C+ 非常适宜于表达抽象数据类型 C+, Java是主流的编程语言 简化了输入输出,北京大学信息学院 版权所有，转载或翻印必究 Page 26,计算机过时技能TOP10,1.Cobol 、2. Nonrelational DBMS（非关系数据库管理系统） 3. Non-IP networks（非IP网络）、4. CC:Mail 5. ColdFusion 6. C 语言设计 7. PowerBuilder、8. CNE（NetWare认证工程师） 9. PC网络管理员、10. OS/2,北京大学信息学院 版权所有，转载或翻印必究 Page 27,抽象数据类型,抽象数据类型 实质为“逻辑结构 + 运算/操作” 隐蔽了存储实现细节 上层算法以一致的形式调用底层数据结构 例如在STL C+中 Stack.push(x) 顺序栈，链式栈 上层调用语句不需要改变,北京大学信息学院 版权所有，转载或翻印必究 Page 28,纯C语言的栈抽象数据类型？,InitStack(S) ClearStack(S) IsEmpty(S) IsFull(S) Push(S,x) Pop(S,x) GetTop(S,x),北京大学信息学院 版权所有，转载或翻印必究 Page 29,C顺序栈的进栈操作,typedef struct StackElementType elemStack_Size; /*用来存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标*/ SeqStack; int Push(SeqStack * S, StackElementType x) if (S-top= Stack_Size) return(FALSE); /*栈已满*/ S-top+; S-elemS-top=x; return(TRUE); ,北京大学信息学院 版权所有，转载或翻印必究 Page 30,C顺序栈的出栈操作,int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*栈为空*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改栈顶指针 */ return(TRUE); ,北京大学信息学院 版权所有，转载或翻印必究 Page 31,C链栈定义,typedef struct node StackElementType data; struct node *next; LinkStackNode; typedef LinkStackNode *LinkStack;,北京大学信息学院 版权所有，转载或翻印必究 Page 32,C链栈的进栈操作,int Push(LinkStack top, StackElementType x) /* 将数据元素x压入栈top中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode); if (temp=NULL) return(FALSE); /* 申请空间失败 */ temp-data=x; temp-next=top-next; top-next=temp; /* 修改当前栈顶指针 */ return(TRUE); ,北京大学信息学院 版权所有，转载或翻印必究 Page 33,C链栈的出栈操作,int Pop(LinkStack top, StackElementType *x) /* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */ LinkStackNode * temp; 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( else ,GetTop ( ,北京大学信息学院 版权所有，转载或翻印必究 Page 35,链栈：C版本括号匹配算法,void BracketMatch(char *str) LinkStack S; int i; char ch; InitStack(/* else ,GetTop (/* ,北京大学信息学院 版权所有，转载或翻印必究 Page 36,C数据类型的问题,1. 在同一个程序中，如果栈的StackElementType 不同 需要定义不同的栈 2. 从顺序栈改为链式栈 上层调用语句一定要改变 程序中所有的变量定义都需要修改 函数参数传递也要改变 3. 最严重的问题 勉强用结构化的C来描述ADT, 造成学生的困惑,北京大学信息学院 版权所有，转载或翻印必究 Page 37,用C+讲授数据类型的好处,1. 在同一个程序中，如果栈的StackElementType 不同 不需要定义不同的栈, template 程序中所有的变量定义都不需要修改 2. 从顺序栈改为链式栈 只需要改变对头文件的引用, 程序代码完全不变 真正的软件复用 真正的抽象数据类型ADT 3. 最大的好处 给学生更好的抽象能力训练, 并且与主流技术一致,北京大学信息学院 版权所有，转载或翻印必究 Page 38,C+栈的抽象数据类型,template class Stack / 栈的元素类型为ELEM Stack(int s); /创建栈的实例 Stack(); /该实例消亡 void Push(ELEM item); / item压入栈顶 ELEM Pop(); / 返回栈顶内容，并从栈顶弹出 ELEM GetTop(); / 返回栈顶内容，但不弹出 void MakeEmpty(); / 变为空栈 Boolean IsEmpty(); / 返回真，若栈已空 Boolean IsFull(); / 返回真，若栈已满 ;,北京大学信息学院 版权所有，转载或翻印必究 Page 39,C+顺序栈,template class Stack private: ELEM *ElmList; / 存放数据元素的指针变量 int top; / 栈顶在的位置，即下标值 / 当新元素压入或栈内容弹出，top值随之增减 int maxsize; / 栈的最大长度 /构建栈的实例，向量空间长度为size public: Stack(int size); ;,北京大学信息学院 版权所有，转载或翻印必究 Page 40,压入栈顶,template void Stack:Push(ELEM item) /判非栈满，否则栈溢出，退出运行 assert(!IsFull(); top+; /栈顶 ElmListtop=item; ,北京大学信息学院 版权所有，转载或翻印必究 Page 41,从栈顶弹出,template ELEM Stack:Pop() /判栈非空，否则断言栈空异常， /退出运行 assert(!IsEmpty(); return ElmListtop-; ,北京大学信息学院 版权所有，转载或翻印必究 Page 42,顺序栈：压入栈顶,template void Stack:Push(ELEM item) assert(!IsFull(); / 栈满，则退出 top+; / 栈顶指针移位 ElmListtop=item; ,北京大学信息学院 版权所有，转载或翻印必究 Page 43,顺序栈：从栈顶弹出,template ELEM Stack:Pop() assert(!IsEmpty(); / 栈空，则退出 return ElmListtop-; ,北京大学信息学院 版权所有，转载或翻印必究 Page 44,C+链式栈,template struct ListNode ELEM data; ListNode * link; ; template class Stack private: ListNode *top; int size; / Count number of elements public: Stack(int sz = LIST_SIZE) top = NULL; size = 0; ,北京大学信息学院 版权所有，转载或翻印必究 Page 45,链式栈：压入栈顶,void Push(const ELEM / 新栈顶指针 ,北京大学信息学院 版权所有，转载或翻印必究 Page 46,链式栈：从栈顶弹出,ELEM Pop() /判栈非空，否则断言栈空异常，程序退出 assert(!IsEmpty(); ELEM result = top-data; /暂存栈顶内容 ListNode * temptr; temptr = top; /老栈顶指针 top = top-link ; /新栈顶指针 size-; delete temptr; /释放空间 return result; /返回的是弹出内容 ,北京大学信息学院 版权所有，转载或翻印必究 Page 47,C+版本括号匹配算法,void BracketMatch(char *str) Stack S; int i; char ch; / 自动初始化 for(i=0; stri!=0; i+) switch(stri) case (: case : case : S.Push(stri); 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,教学讨论2,算法和数据结构的关系？ 基本数据结构和算法的重现？ 怎样训练综合能力？ 实践教学？ 怎样减少抄袭？,天网公司总裁 雷凯 北大94级,张老师在整个课程的教学中，通过其精心选择的课程教材，认真精辟的课堂讲解，引人入胜的案例分析，巧妙的教学思路设计，丰富系统的训练方法，和细致入微的与学生互动教学，真正的体现了一位导师给每一位渴望知识的学生“授之以渔”的教学精神，将数据结构与算法的知识和精髓由一本本经典的理论著作，转化成学生所需要的，活生生有实践意义的知识，深深地印在了每一位学生的心里。,北京大学信息学院 版权所有，转载或翻印必究 Page 49,徐颖北大94本，00硕 2003级美国斯坦福大学计算机系博士WebVLDB、CIKM、PODS,我进入斯坦福的第一个学期就选择了直接考试，而且惊喜地发现，算法与数据结构考试的知识点和张铭老师在北大开设课程的讲授内容十分一致，所以张铭老师的课程讲义和录像就成为我的主要复习资料,北京大学信息学院 版权所有，转载或翻印必究 Page 50,陈华97本，01硕 酷讯公司总裁,张老师给我们年级带了计算引论和数据结构。这两门课程共同的特就是创造性思维的刺激和超强度的大项目实习 张老师在计算引论给我们打下了雄厚的Pascal结构化程序设计功底。数据结构课程采用了张老师翻译的面向对象C+版数据结构与算法分析新教材 由于是主讲老师亲自翻译的教材，她对教材有着深刻的理解，上课时能够将问题讲述得非常清晰。我们在张老师带领下，几周内从Pascal转换到C+，对我们以后很快接受新理论、新技术，是一种很好的锻炼,北京大学信息学院 版权所有，转载或翻印必究 Page 51,梅俏竹北大99级 UIUC计算机系博士生 SIGKDD、SIGIR、WWW，ACM TKDD,记得当年数据结构的大实习作业是设计并实现一个简单的搜索引擎。 而当时只不过是2000年，现在搜索引擎的巨头Google远未上市，百度则刚刚成立，微软和雅虎甚至还没开始研发自己的搜索引擎。 北大的本科生课程实习就能有这样的前瞻性的问题绝对是值得称道的。 大家都不约而同地提到数据结构这门课程对自己的影响。归结起来，大家都认为张铭老师的“数据结构与算法课程”内容细致实用，讲授深入浅出，课程实习精巧而具前瞻性，对培养学生分析和解决问题，创造性思考，和团队合作的能力都有很好的作用,北京大学信息学院 版权所有，转载或翻印必究 Page 52,银平00本，04硕，助教 酷讯公司,张铭老师课堂上引导以及深刻讲解让我对这门课程产生了浓厚兴趣，并极大的训练了我的思维能力。数据结构的几个大的实习让我打下了坚实的算法与工程基础。 这门课程几乎年年都有所变动，如降低作业的数量但提高作业的质量，将实习课程分离，采用ACM的题目等等。,北京大学信息学院 版权所有，转载或翻印必究 Page 53,赵翔宇01本，05硕，助教,最重要的是，我们要看同学们做作业的时候是否是独立完成，张老师的诚实代码宣言相信每一个选过这门课的同学都会牢记在心中，先成人，再成才，这也是张老师在上这门课时教给我们很重要的一点。 无论平时的研究、项目，还是求职，甚至以后的工作生涯，我们都会体会到数据结构和算法的重要性。 在今年的求职过程中，无论碰到怎样复杂的数据结构题，我都能轻松应付，因为在解题前，我对自己有信心，我有张老师为我打下的深厚基础。,北京大学信息学院 版权所有，转载或翻印必究 Page 54,Honor Code（诚实代码保证）,/ 我真诚地保证： / 我自己独立地完成了整个程序从分析、设计到编码的所有工作。 / 如果在上述过程中，我遇到了什么困难而求教于人， / 那么，我将在程序实习报告中详细地列举我所遇到的问题， / 以及别人给我的提示。 / 在此，我感谢 XXX, , XXX对我的启发和帮助。 / 我的程序里中凡是引用到其他程序或文档之处， / 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, / 我都已经在程序的注释里很清楚地注明了引用的出处。 / 我从未没抄袭过别人的程序，也没有盗用别人的程序， / 不管是修改式的抄袭还是原封不动的抄袭。 / ,北京大学信息学院 版权所有，转载或翻印必究 Page 55,李逸男北大03级 香港科技大学博士 本科两篇SIGMOD07 Demo论文,起着承前启后的重要作用。 在张老师的悉心指导和严格要求下，经过数据结构课程的理论和实践的磨练，同学们从刚刚会写简单的程序，迅速“升级”为能够完成各种复杂系统设计和实现的计算机高手。我们在随后的各种课程中完成的迷你操作系统、编译器、数据库系统等课程设计，很大深度依赖于在数据结构这门课程所打下的坚实的理论基础和动手能力。 国际最前沿的研究成果其实往往就是对相对基本的数据结构和算法在某些特殊应用背景进行的一些有针对性的优化和扩展，而这些相对基本的数据结构在张老师的课程中绝大多都有涉及，还有一些是张老师在课堂上加入的一些扩展内容。 细细回想起来，很多现在已经非常熟悉的知识还都是在张老师的数据结构课上打下的基础。,北京大学信息学院 版权所有，转载或翻印必究 Page 56,李浩源北大04级 2005年ACM/ICPC 全球第十一名 2006年ACM/ICPC 全球第十三名 即将赴美国Cornell攻读计算机博士学位,数据结构还有一个很大的特色就是它不单单讲授理论内容，张老师还配套开设了数据结构实习课程，以锻炼提高学生的实践能力。 在实习课上，同学把理论课上的很多算法得以实现，上课更加积极的讨论。 大家在欢乐的气氛下达到了理论与实践水平共同提高目的，日后同学之间谈起来，都很怀念。,北京大学信息学院 版权所有，转载或翻印必究 Page 57,柳明海北大04级,这门课程的教材非常好，教材的深度和广度都很不错，由于是主讲老师自己编写的教材，对教材有着深刻的理解，上课时能够将问题讲述得非常清晰，还能够联系实际应用，而不是简单的学习。 课堂的氛围非常的活泼，老师同学们的互动非常的好，老师会经常地提问，而我们在遇到问题时也能够随时地向老师提问，同学们感觉上课是一种享受，是一种能够学到知识的享受。,北京大学信息学院 版权所有，转载或翻印必究