《数据结构与算法》是计算机科学技术等电子信息类专业的核心主干基础课程。课程依据美国最新ACM/IEEE CC2005课程体系和中国教育部CCC2006学科规范制定了先进的课程体系。设计研究启发式教学案例,培养创新意识和主动学习意识,课程以问题求解为导向,培养和提高学生理论、抽象、设计的能力,强调实践和创新能力。从逻辑、存储、运算的角度组织数据结构与算法,培养了学生独立地实现常用基本数据结构的抽象数据类型,注重实践能力和工程能力的培养,并建立起数据结构与算法设计和问题求解的知识体系。
课程采用主持教师的国家十五教材和配套的实验教材,建设了立体化的网络教学环境。课程小组在多年教学积累的基础上,新编写了国家十一五教材(2008年6月出版),并正在编写十一五实验教程。所出版的教材和自主开发的网络教学平台课程在国内产生了比较广泛的影响和良好的示范作用。课程采用现代化的教学手段,通过多媒体动画课件和网络教学促进了师生的交流与互动。课程的重要特色,就是实习大项目,融合当前最新理论和技术,非常有前瞻性,学生受到创新思维能力训练、工程能力训练令其在后来的研究和工作中受益良多。
课程网站为学生提供全方位的学习辅导支持,尤其是细化到知识点的课程知识体系导航。整个网站的内容十分丰富,除知识点和电子课件外,还有46小时课程全程录像、ACM在线算法测试、学生论坛等内容。
本课程在国内有很大的影响。2008年5月18日通过Google检索,“约有137,000项符合张铭 数据结构的查询结果”,“约有34,700项符合张铭 数据结构 视频的查询结果”。
张铭教授主持本课程,与4名副教授一起主讲。课程5位主讲教师都拥有博士学位,目前都主持着多项国家科研项目,科研和教学能力强,发表了高水平的学术论文,在历次教学效果调查中均获学生好评。教学组聘请学术造诣深、教学经验丰富的许卓群、杨冬青两名老教授担任教学指导工作,并且配备硕士和博士研究生29人参与课程答疑和教学系统的技术支持,保证学生理论和实践学习的质量。
课程负责人:张 铭 教 授
- 张铭、王腾蛟、赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。
- 许卓群、杨冬青、唐世渭、张铭,《数据结构与算法》,高等教育出版社,2004年7月。
- 张铭、赵海燕、王腾蛟,《数据结构与算法习题指导》,高等教育出版社,2005年8月。
- Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press, 2nd edition, 2001. 高等教育出版社影印。
美国IEEE和ACM的教学计划CC2005和教育部计算机教指委 “计算机科学与技术专业规范”2006都明确地把“程序设计”、“算法与数据结构”列入计算机以及信息技术相关学科专业的本科必修基础课程。教育部计算机专业教指委“中国计算机本科专业发展战略研究报告”、“计算机科学与技术专业规范”等明确地强调了实践教学和学生动手能力培养的重要性。数据结构是计算机系的本科核心课程之一,上承计算引论(或计算概论)与程序设计实习,下启高级算法和计算理论,向来是计算机本科教学的重中之重。
作为一门重要的专业必修课程,“数据结构与算法”课程既是对以往课程的深入和扩展,也是为将来更加深入地学习其他专业课程打下基础。课程中所学习的排序问题的算法,以及基本的树、图等数据结构,是计算机科学的基本功。B+树、Hash等高级数据结构,也是数据库、操作系统、编译原理、计算机网络等后续课程的基础。
“数据结构与算法”介绍基本数据结构、基本算法分析技术、排序、检索和索引技术。对常用的基本数据结构,讨论相应的存储实现技术和经典算法,并通过算法时间空间的效率分析,介绍时空权衡的原则。对常用的各种经典排序算法深入讨论其时间和空间开销。介绍文件管理和外排序技术,以及常见的检索和索引技术。通过该课程的学习,学生将基本掌握数据结构和算法的设计分析技术,提高程序设计的质量;根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。
一、数据结构与算法A(实验班)
1.课程基本情况
学院设定 | 课程编号 | 04830540 | ||||||||||||
课程名称 | 数据结构与算法A(实验班) | |||||||||||||
Data Structure And Algorithm A | ||||||||||||||
开课时间 | 一年级 | 二年级 | 三年级 | 四年级 | ||||||||||
秋 | 春 | 夏 | 秋 | 春 | 夏 | 秋 | 春 | 夏 | 秋 | 春 | 夏 | |||
适用院系 | 信息学院全体学生 | |||||||||||||
课程定位 | 骨干基础课,必修课 | |||||||||||||
学分 | 3学分 | |||||||||||||
总学时 | 54学时 | |||||||||||||
先修课程 | 计算引论,程序设计实习,集合论与图论,概率统计A | |||||||||||||
后续课程 | 数据结构与算法实习,程序设计语言原理 | |||||||||||||
教 师 设 定 |
教学方式 |
本课程是“数据结构与算法A”替代课程,针对基础比较好、学习能力突出、学有余力的实验班学生设置。课程将加大“数据结构与算法A”的深度和广度,提供更多的研究和讨论机会,因材施教、培养领袖人才。以课堂讲授为主,同时借助网络教学平台,拓展课堂讲授的相关知识,便于同学自主学习、巩固课堂所学内容。另外,组织3次以上的独立习题课(6小时),针对学生作业中出现年的典型问题进行深入探讨。鉴于数据结构与算法是与实践紧密结合的课程,配合理论教学,将加强上机实习的训练,通过合理、有效地设计上机题目,改进作业评核方式,调动学生的积极性,启发引导学生掌握基础理论并能创新应用,增强学生综合运用有关知识的能力。 | ||||||||||||
课时分配 |
3(课堂教学)+1(教学实验)/周 | |||||||||||||
考核方式 |
平时(书面作业、课堂测试)20%,上机(+报告)15%,期中20%,期末20%,高级数据结构20%,考勤和态度5%。期中、期末考试,全学院的“数据结构与算法A”和“数据结构与算法A(实验班)”统一出题、统一阅卷。平时作业和上机作业由各班根据专业要求灵活掌握,教员协调给出成绩。注重综合能力的考评,平时表现突出、上机实践能力较强的可以得到奖励加分。 | |||||||||||||
主要教材 |
|
|||||||||||||
参考资料 |
|
|||||||||||||
其它信息 |
2.教学目的和要求
1)掌握并巩固基础数据结构知识:线性表、树、图等常用的数据结构和算法的设计分析技术;常用的排序、检索算法及其时间空间开销;对算法复杂性进行必要分析和控制。
2)理解编译栈的工作原理,熟习用栈消除递归的算法框架,并解决相关应用问题。
3)初步掌握稀疏矩阵、广义表等高级线性结构技术,了解Trie结构、AVL树等高级树形结构。
4)对抽象数据类型有深入的理解,能根据所求解问题的性质选择合理的数据结构,设计并完成处理海量数据的复杂应用系统。
3.课程特色
“数据结构与算法”是一门重要的计算机类骨干基础课程。其主要目的是使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式,比较不同数据结构和算法的特点。通过学习,使学生能够提高用计算机解决实际问题的能力。
本课程针对实验班的学生,将以问题求解为主线,从问题抽象、数据抽象和算法抽象的角度来组织数据结构与算法的设计,指导学生建立数学模型、使用不同的数据结构不同的算法分别去解决问题,最后去探讨各种数据结构和算法的优缺点,同时让学生学会怎么样根据实际问题来取舍数据结构和算法,并且在时间复杂度和空间复杂度之间进行平衡。
在讲授过程中,将调动学生的积极性,采取研究式的学习方法。有些较基础的内容采用学生综述、答辩、小测验的形式,培养学生的自学能力。引导学生跟踪数据结构与算法的前沿应用技术,引入研读论文并作报告的讨论班形式,培养学生的捕捉新理论、新技术的科研能力。
最后的合作大实习题由学生自己提出,并组织团队完成。由助教引导讨论,从需求分析、模块设计、编程实践、调试测试各个阶段进行引导,加强学生们综合应用数据结构和算法知识的能力。
本课程将通过设置的课程网站提供课堂讲义和最新的参考材料。
4 .课程内容摘要和知识点
|
章节 |
课时 |
内容摘要和知识点 |
重要性 |
1
|
数据结构和算法简介 |
2 |
数据结构定义(逻辑结构、存储结构、运算)抽象数据类型算法及其算法度量和评价(大O表示法及其运算规则) | 难度▃▄▅重要性
★★★★★ |
2 |
线性表、栈和队列 |
8 |
线性表(向量、链表)栈和队列(顺序、链接)、栈的应用根据专业选讲递归到非递归的转换机制和方法 | 难度▃▄▅▆重要性
★★★★ |
3 |
字符串 |
4 |
字符串抽象数据类型,存储表示和类定义字符串的运算字符串的模式匹配 | 难度▃▄▅▆▇重要性
★★★ |
4 |
二叉树 |
10 |
二叉树的概念及性质,二叉树的抽象数据类型二叉树的周游二叉树的存储实现
二叉检索树、堆与优先队列、Huffman编码树 ★非递归深度优先周游二叉树和穿线二叉树 |
难度▃▄▅▆▇重要性
★★★★★ |
5 |
树与森林 |
4 |
树的概念,森林与二叉树的等价转换,树的抽象数据类型树的周游树的链式存储,树的顺序存储 | 难度▃▄▅▆重要性
★★★★ |
6 |
图 |
8 |
图的基本概念,图的抽象数据类型,图的存储结构图的周游(深度优先、搜索、广度优先、拓扑排序)最短路径问题,最小支撑树(Prim算法、Kruskal算法) | 难度▃▄▅▆重要性
★★★★★ |
7 |
内排序 |
8 |
排序问题的基本概念,三种简单排序算法(插入排序、冒泡排序、选择排序)Shell排序,快速排序,归并排序,堆排序,基数排序★各种排序算法的理论和实验时间代价的讨论以及排序问题的下限的研究 | 难度▃▄▅▆▇重要性
★★★★★ |
8 |
文件管理和外排序 |
2 |
外排序的特点二路外排序置换选择排序 | 难度▃▄▅▆重要性
★★★ |
9 |
检索 |
4 |
检索的基本概念基于线性表的检索基于集合的检索
散列方法 |
难度▃▄▅▆重要性
★★★★ |
10 |
索引技术 |
2 |
倒排索引B+树等动态索引组织★红黑树 | 难度▃▄▅▆重要性
★★★ |
11 |
高级数据结构 |
2 |
广义表字符树★AVL树
★伸展树 |
难度▃▄▅▆▇重要性
★★★ |
张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年 6月。普通高等教育“十一五”国家级规划教材 |
- 张铭、王腾蛟、赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。
- 张铭、赵海燕、王腾蛟,《数据结构与算法习题指导》,高等教育出版社,2005年8月。
- 许卓群、杨冬青、唐世渭、张铭,《数据结构与算法》,高等教育出版社,2004年7月。
- 张铭,刘晓丹译。《数据结构与算法分析》(C++两版、Java版)。电子工业出版社2002年6月C++第二版,2001年1月Java版,1998年8月C++第一版。译自:Clifford A.Shaffer, A practical Introduction to Data Structures and Algorithm Analysis, Prentice Hall。
- 殷人昆等, 数据结构(用面向对象方法与C++语言描述)第2版, 清华大学出版社,2007年6月。
- 廖明宏等,《数据结构与算法-(第4版)》,高等教育,2007年11月。
- 耿国华等,《数据结构--C语言描述》,高等教育出版社,2006年1月。
- 王晓东等,《数据结构(C语言版)》,电子工业出版社,2007年7月。
- 刘大有等,《数据结构/面向21世纪课程教材》,高等教育出版社。
- 张乃孝, 裘宗燕.《 数据结构——C++与面向对象的途径》, 北京:高等教育出版社,2001
- 严蔚敏, 吴伟民. 《数据结构——C语言版》, 北京:清华大学出版社,2001
- Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 2nd edition, 2001. 高等教育出版社影印。
- M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印,2003年1月。
- B. Kernighan & R. Pike , The Practice of Programming, Addison-Wesley, 1999. (中译本:《程序设计实践》,裘宗燕译,机械工业出版社,2000年8月。