面象对象数据结构

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,版权所有，转载或翻印必究,Page,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,面向对象的数据结构,山西省高校计算机精品课程及优质教学资源,建设与共享研讨会,山西 太原,2008,年,4,月,20,日,问我祖先在何处，山西洪洞大槐树,版权所有，转载或翻印必究,Page,2,山西太原（交城）古郊麻会村,版权所有，转载或翻印必究,Page,3,内容提要,1.,教学内容,2.,数据的定义,3.,抽象数据类型,4.,教学案例,5.,网络教学资源,数据结构在计算机学科中的地位,最重要的主干基础课程,就是,“最”,，没有“之一”,承前启后的重要作用,程序设计能力“质的飞跃”,操作系统、编译器、数据库系统、,网络、软件工程,版权所有，转载或翻印必究,Page,4,版权所有，转载或翻印必究,Page,5,版权所有，转载或翻印必究,Page,6,数据结构与算法实习,概率统计,数据结构与算法,数学分析高等数学,集合论与图论,算法分析与设计,程序设计实习,高等代数线性代数,计算概论,程序设计语言原理,数据库概论,编译原理,操作系统,软件工程,计算机网络,版权所有，转载或翻印必究,Page,7,1.,数据结构课程的主要内容,理论,算法的数学基础,算法的时间和空间度量,抽象,排序、检索等重要问题类的有效算法,重要数据结构技术,设计,算法的选择、实现和测试,版权所有，转载或翻印必究,Page,8,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.,网络教学资源,建立了高质量的,1500ppt, 46,多小时,rm,（全程录像）,还有其他补充录像,标准,C+,模板编写的可执行的源程序代码,9209,代码总行数，非注释行,7498,习题和上机题及其参考答案,BBS,讨论版,(2008,年,4,月数据,),18,万位会员，帖子总数,8375,篇,版权所有，转载或翻印必究,Page,14,版权所有，转载或翻印必究,Page,15,网站内容,概述、前测,知识点详解,动画,习题解、新习题,电子教案,pdf,、视频,扩展资源,参考网站、论文、讲义,版权所有，转载或翻印必究,Page,16,版权所有，转载或翻印必究,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,月,.,清华大学信息学院计算机系、软件学院教材,清华考研第一参考书,版权所有，转载或翻印必究,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(,&,S);,for(i=0; stri!=0; i+) ,switch(stri) ,case (:,case :,case :,Push(,&,S,stri); break;,case ):,case :,case :,if (IsEmpty(,&,S) ,printf(n,右括号多余,!);,return;,else ,GetTop (,&,S,if (Match(ch,stri),Pop(,&,S,else ,printf(n,括号不匹配,!);,return;, /*else*/,/*switch*/,/*for*/,if (IsEmpty(,&,S),printf(n,括号匹配,!);,else 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,右括号多余,!);,return;,else ,GetTop (,/*&*/,S,if (Match(ch,stri),Pop(,/*&*/,S,else ,printf(,“,n,括号不匹配,!);,return;, /*else*/,/*switch*/,/*for*/,if (IsEmpty(,/*&*/,S),printf(n,括号匹配,!);,else printf(n,左括号多余,);,版权所有，转载或翻印必究,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 & item),ListNode *temp;,temp = new ListNode;,/,若无存储空间则异常，程序退出运行,assert(!temp=NULL);,size+;,temp-data = item;,temp-link = top; /,老栈顶指针,top = temp;/,新栈顶指针,版权所有，转载或翻印必究,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,级,这门课程的教材非常好，教材的深度和广度都很不错，由于是主讲老师自己编写的教材，对教材有着深刻的理解，上课时能够将问题讲述得非常清晰，还能够联系实际应用，而不是简单的学习。,课堂的氛围非常的活泼，老师同学们的互动非常的好，老师会经常地提问，而我们在遇到问题时也能够随时地向老师提问,，同学们感觉上课是一种享受，是一种能够学到知识的享受。,版权所有，转载或翻印必究,Page,58,吴珂,06,实验班,她的智慧和汗水凝结在一页页的代码、图示与文字之间，使我们不知不觉间就理解了乍看上去深奥难懂的专业知识。,课程作业的布置也能体现出张老师的心血。每周作业的题目都不多，只有三四道，而题题都是精心设计，有的改自经典问题，有的脱胎于前沿领域，题题都充满挑战却又生动有趣。开放的作业让我获得了创造性思考的机会。,数据结构与算法是计算机专业的基础课，张老师的言传身教让我学到了许多有趣的专业知识和计算机科学的思维方式。,版权所有，转载或翻印必究,Page,59,朱铮，美国微软公司核心操作系统部,99,级复旦大学计算机系,给我印象深刻的是张铭老师所布置的大作业与基础知识的联系非常紧密，却又是业界的前沿问题。,于是我便成了张铭老师在北大以外的学生，跟随北大的课堂进度做课外习题和团队作业。,借助电子邮件，我经常向张老师请教问题，有些问题甚至不在课程范围之内，张老师总是耐心解答。,版权所有，转载或翻印必究,Page,60,陶富民,考研，北大研,07,该课程的内容丰富多彩，讲义制作的十分精致，虽然已经上过该课程，但是仍然能学到不少的新的知识。,不仅在考研论坛上，,许多其他学习论坛上都有人推荐张老师的数据结构视频,。,北京考研的同学，他们中都有不少人慕名到北大课堂里听张老师的讲课。,版权所有，转载或翻印必究,Page,61,2008年4月12日Google检索,约有,197,000,项符合张铭 数据结构的查询结果,约有,42,300,项符合张铭 数据结构 视频的查询结果,版权所有，转载或翻印必究,Page,62,学习参考,三个不同方向的学习参考：,国内,IT,公司：北大张铭老师的教程,国内考试：清华大学严蔚敏教程,国外深造：,MIT,教程,但是，清华大学信息学院计算机系、软件学院采用,C+,数据结构,(,用面向对象方法与,C+,语言描述,),第,2,版,殷人昆主编,清华大学出版社,2007,年,6,月,.,。,版权所有，转载或翻印必究,Page,63,版权所有，转载或翻印必究,Page,64,感谢指导！,张 铭,北京大学信息科学与技术学院,(,教育网,),(,公网,),