《面向对象数据结构讲课资料》由会员分享，可在线阅读，更多相关《面向对象数据结构讲课资料（64页珍藏版）》请在金锄头文库上搜索。
1、面向对象的数据结构,张 铭,北京大学信息科学与技术学院 山西省高校计算机精品课程及优质教学资源 建设与共享研讨会 山西 太原 2008年4月20日,问我祖先在何处，山西洪洞大槐树,北京大学信息学院 版权所有，转载或翻印必究 Page 2,山西太原（交城）古郊麻会村,北京大学信息学院 版权所有，转载或翻印必究 Page 3,内容提要,1. 教学内容 2. 数据的定义 3. 抽象数据类型 4. 教学案例 5. 网络教学资源,数据结构在计算机学科中的地位,最重要的主干基础课程 就是“最”，没有“之一” 承前启后的重要作用 程序设计能力“质的飞跃” 操作系统、编译器、数据库系统、 网络、软件工程,北京
2、大学信息学院 版权所有，转载或翻印必究 Page 4,北京大学信息学院 版权所有，转载或翻印必究 Page 6,数据结构与算法实习,概率统计,数据结构与算法,数学分析高等数学,集合论与图论,算法分析与设计,程序设计实习,高等代数线性代数,计算概论,程序设计语言原理,数据库概论,编译原理,操作系统,软件工程,计算机网络,北京大学信息学院 版权所有，转载或翻印必究 Page 7,1. 数据结构课程的主要内容,理论 算法的数学基础 算法的时间和空间度量 抽象 排序、检索等重要问题类的有效算法 重要数据结构技术 设计 算法的选择、实现和测试,北京大学信息学院 版权所有，转载或翻印必究 Page 8,2
3、. 数据结构的定义,数据的逻辑结构 图树二叉树线性表 数据的存储结构 顺序方法、链接方法 索引方法、散列方法 数据的运算 增、删、查、改、排序、检索,北京大学信息学院 版权所有，转载或翻印必究 Page 9,3. 抽象数据类型ADT,抽象数据类型是定义了一组运算的数学模型 把数据结构的存储与实现细节剥离 在适当的抽象层次上考虑程序的结构和算法 封装和信息隐蔽,北京大学信息学院 版权所有，转载或翻印必究 Page 10,栈的抽象数据类型,template class Stack / 栈的元素类型为ELEM Stack(int s); /创建栈的实例 Stack(); /该实例消亡 void Pu
4、sh(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-
5、8道ACM竞赛题 3-5道综合上机实习题 上机实习时间，120小时/学生,北京大学信息学院 版权所有，转载或翻印必究 Page 13,5. 网络教学资源,建立了高质量的 1500ppt, 46多小时rm（全程录像） 还有其他补充录像 标准C+模板编写的可执行的源程序代码 9209代码总行数，非注释行7498 习题和上机题及其参考答案 BBS讨论版(2008年4月数据) 18万位会员，帖子总数8375 篇,北京大学信息学院 版权所有，转载或翻印必究 Page 14,北京大学信息学院 版权所有，转载或翻印必究 Page 15,网站内容,概述、前测 知识点详解 动画 习题解、新习题 电子教案 pdf
6、、视频 扩展资源 参考网站、论文、讲义,北京大学信息学院 版权所有，转载或翻印必究 Page 16,北京大学信息学院 版权所有，转载或翻印必究 Page 17,新教材,张铭、王腾蛟、赵海燕，数据结构与算法，高等教育出版社，2008年6月国家级“十一五”规划教材 书号: ISBN 978-70-4-023961-4 张铭、赵海燕、王腾蛟、宋国杰，数据结构与算法实验教程，高等教育出版社，2009年6月国家级“十一五”规划教材,老教材,许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，2004年 7月。 张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，2005年
7、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 Structure
8、s, Algorithms, and Applications in C+. 机械工业出版社影印版。 4. William Ford ， Data Structure with C+，清华大学出版社影印版,参考教材,5. 数据结构(用面向对象方法与C+语言描述)第2版,殷人昆主编, 清华大学出版社,2007年6月. 清华大学信息学院计算机系、软件学院教材 清华考研第一参考书 ,北京大学信息学院 版权所有，转载或翻印必究 Page 21,教学讨论1,算法描述语言 自然语言 类Pascal 类C 类C+ 类Java 尺有所长、寸有所短,括号匹配,问题：检查程序文件中的括号是否匹配 括号包括：,(,
9、),. 算法思想 逐个读入字符，忽略非括号字符 如果是左括号，记下来 如果是右括号，检查是否与最近读入的左括号匹配；如果不匹配，则匹配失败 重复上述过程，如果读到文件尾部时，没有未匹配的左括号留下，则匹配成功，否则，匹配失败,北京大学信息学院 版权所有，转载或翻印必究 Page 22,自然语言描述的算法,采用栈保存中间数据 (1) 从左至右扫描表达式, 读取字符c (2) 如果c是非括号字符, 继续步骤1 (3) 否则, 如果c是左括号, 则入栈; (4) 如果c是右括号, 则与栈顶元素比较 若栈空(右括号富余), 或左右括号匹配不匹配，则结束 否则，符号目前还匹配, 则继续扫描步骤1 (5)
10、 如果遇到扫描符, 则判断栈是否空 空, 则说明匹配 否则, 说明左括号富余,北京大学信息学院 版权所有，转载或翻印必究 Page 23,北京大学信息学院 张铭编写 版权所有，转载或翻印必究 Page 24,4,*,x,*,2,a,+,-,）,c,（,北京大学信息学院 版权所有，转载或翻印必究 Page 25,语言描述，C+代码和注释,1. 语言描述和注释足够表达思想； 2. 代码段可以培养学生严谨的算法表述能力； 算法分析教材的太抽象 3. C+ 非常适宜于表达抽象数据类型 C+, Java是主流的编程语言 简化了输入输出,北京大学信息学院 版权所有，转载或翻印必究 Page 26,计算机过
11、时技能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) 顺序栈，链式栈 上层调用语句
12、不需要改变,北京大学信息学院 版权所有，转载或翻印必究 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, StackEl
13、ementType 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
14、 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); i
15、f (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(t
