“数据结构”课程总结

第一篇：“数据结构”课程总结

“数据结构”课程总结

计算机科学与技术专业从1994年开始为我校专科生开设“数据结构”课程，2004年开始为本科生开设这门课程。由于本门课程的教学从教材、讲授、实验指导都体现了先进的教育理念，该课程的教学体系科学、完整，教学手段与方法先进，课程特色鲜明，2006年被评为赤峰学院本科层次精品课。几年来，数据结构课题组成员从以下几个方面对本门课程进行了建设和改革。

一、课程建设指导思想、定位和特色 1．学科地位

“数据结构”是计算机科学与技术专业的一门学科基础课，是本专业和相关专业必修课。本课程的教学目标是培养学生通过理解、分析和研究计算机处理的数据对象的特性，从而选择适当的数据结构、存储结构和相应的算法，并熟练掌握算法的时间分析和空间分析技巧。“数据结构”还是计算机科学与技术专业部分专业课的先导课，如“数据库原理与应用”、“计算机操作系统”、“计算机编译原理”和“面向对象的程序设计”等。所以本课程的教学效果将直接影响到学生对其它后续专业课的学习，因此，该课程在专业建设的地位十分重要。

“数据结构”是一门应用性很强的课程，本课程要求学生在掌握各种数据结构，特别是存储结构和有关算法的基础上，通过大量的上机实例把难以理解的、抽象的概念转化为计算机能够正确运行的程序，从而提高学生运用所学知识解决实际问题的能力。2．课程特色

根据课程建设的规划和我系实际，我们针对《数据结构》课程教学开展讨论，并就实验、图书资料等方面进行建设。在不断的教学实践中，我们按照精品课建设要求，积极探索，积累了丰富的教学经验。

采用国内经典教材，结合前沿的研究领域和最新科研动态，丰富教学内容，让学生了解数据结构的实际应用价值。

采用课堂教学与大作业相结合，上机实践为补充的教学模式，培养学生的创业创新素质和团队协作精神。

二、教师队伍建设

1．良好的学缘结构

任课教师的业务水平和教学水平是影响课程建设质量的重要因素。为此，我们不断加强师资队伍建设，特别注重青年教师和实验指导教师的培养。在担任该课程教学任务的5名教师中，教授1名、副教授2名、讲师2名，学历结构为硕士4人、学士1人，45岁以下3人，35岁以下2人。本教师梯队学历层次较高，职称、年龄结构合理，便于本门课程的建设和发展。

2．加强学术交流，不断提高团队整体教学和科研水平

在教学过程中，我们采取了互相听课，举行公开课、观摩课等方式，经常交流教书育人和教学改革方面的经验，不断提高任课教师的教学水平和学术水平。

以范体贵教授为学科带头人的教学研究梯队，具有丰富的教学经验和高昂的教学热情，同时具备较高的教学研究和科学研究水平。教学梯队成员在搞好教学的同时，积极申报承担各级各类教学研究和科学研究课题，并参加国内外相关学科的科研、教学等方面的学术交流活动。选派范体贵、门爱华两位老师参加全国计算机年会和全国数据库学术会议，与国内其他高校著名学者进行了教学、科研等方面的交流，学到许多宝贵的经验和方法。

注重与其他高校的合作和交流，学习其他院校好的教学经验和方法。选派主讲教师门爱华老师到清华大学计算机系做访问学者，访学期间门老师听取了本课程的讲授，经常与讲授本门课程的资深教授严蔚敏老师、殷仁昆老师进行交流、学习。二位老师都给予了具体的指导和建议，为我校本门课程的改革和发展提供了有利的帮助。请国内著名高校学者来我系讲学传授经验，在教学、科研等方面给予具体的指导。2008年10月清华大学著名数据库专家冯建华教授来我系讲学，课题组成员与冯教授进行了深入的交流，在教学和科研方面都有很大的收获。

3．开展科学研究，积极申请科研立项

数据结构课题小组成员积极进行相关领域的科学研究，几年来发表相关论文30余篇，承担自治区级科研项目四个，赤峰市科技局科研项目一个，院级项目一个，其中3个项目已经完成并通过验收。目前在研的一个科研项目是与清华大学合作申请的计算机前沿领域研究课题，相信通过该项目的研究和合作，对我系的科研工作会起到极大的促进作用，同时能够使我系科研水平上一个新的台阶。课题组成员经过几年的努力，在各方面都取得了一些成绩。范体贵、门爱华、张国祥、王玉红四位教师分别获得“赤峰学院课堂教学质量优秀奖”，范体贵、门爱华两位教师多次获得“赤峰学院科研成果优秀奖”的奖励。王玉红老师获得“毕业实习优秀指导教师“称号，门爱华老师2007年、2008年连续获得“毕业论文优秀指导教师”奖励。

建立了良好的人才培养制度，在学校和系里的大力支持下，鼓励现有教师提高学历与引进高学历教师相结合，经过几年的建设，已经形成了一支以中青年为主的学科梯队。积极鼓励中青年教师到国内名校进修或攻读硕士、博士学位，门爱华、董洁、王玉红分别考取了东北大学和辽宁工程技术大学的硕士研究生，已圆满完成学业并获得硕士学位。

三、教学内容、教材建设

1．理论环节教学内容及学时分配

“数据结构”是计算机科学课程体系中核心课程之首，作为学科的专业基础课，具有承上启下的重要作用。对应于学科中问题求解的理论、抽象和设计的方法论，本课程内容体系结构分为概念表述、构建数据模型、设计算法三个层面，突出数据组织方法与处理技术，贯穿程序设计和软件工程新思想和新观点。理论学时设置为72学时。

2.实践环节教学内容及学时分配

上机实践和课程设计重在培养学生软件设计的综合能力。在基本的课程实习基础上,自2001年起开设了数据结构课程设计，使课程的实践环节总学时数增加到60学时。提出了课程设计的规范要求，突出关键技术要点，贯穿基本技能训练主线，加强实践能力培养。

通过课程设计的训练，突出构造性思维训练的特征，提高了学生组织数据与进行编写大型程序能力，使学生更好地理解和掌握了算法设计所需的技术，为专业学习打下良好的基础。课程设计题目（动态更新、完善）：航空客运订票系统；电梯模拟；简单行编辑程序；工资管理系统；医院排队看病活动的模拟；学籍管理系统；图书管理系统等。3．教材建设

教材建设是课程建设的重要环节。为此，根据教学大纲和本课程的发展需要，在本课程教材的选用上注重教材的先进性和科学性，我们选用了清华大学出版社严蔚敏教授等编写的《数据结构》（C语言版）作为教材，本书内容丰富、体系结构严谨、概念清晰、易学易懂，也是多所院校指定的考研参考教材，完全适合我系计算机科学与技术、信息与计算科学专业学生的需要。任课教师则多方面参考相关教材，选择部分编写精彩的内容充实到教案中。任课教师们广泛阅读相关文献，了解该领域前沿知识，并且在授课过程中介绍给学生，以开阔学生的视野，拓宽学生的知识面。同时，根据教材内容和实际教学要求，编写了《数据结构上机指导与习题就解答》，并正式出版了《数据结构实验教程》一书，该书作为自治区教育厅统编教材已在各高校广泛使用。

四、教学方法和教学手段

1．教学方法

在教学方法上，讲课、讨论和专题讲座等多种形式并用，以科学、生动灵活的讲授方式传授知识，培养学生的创造思维。教师在认真组织课堂讲授，注意各环节正常运行的同时，还针对不同的教学内容采取不同的方法进行讲解，做到课程内容既条理清晰、深入浅出，又重点突出、特色鲜明。教学内容灵活，既有必讲的内容，也有针对不同专业需要和特点选讲的内容。

通过布置适量的课后习题，使学生能够进一步巩固和提高对课上所学知识的领悟和应用能力。我们在选择习题时，一方面注重三基（基本理论，基本方法，基本技能）知识的掌握，另一方面也充分考虑知识的灵活应用，使学生能多角度、多方法地解决问题，既锻炼他们的系统性思维，又提高分析解决问题的能力。每两周安排一次习题课，由指导教师集中解决同学课上课下遇到的问题。

上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成必不可少的一个教学环节，也是对课堂教学效果的一种检验。通常，实习题中的问题比平时的习题复杂得多，也更接近实际。实习题注重原理与应用的结合，目的让学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能。同时，通过实践能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的作用。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，可以多人合作，有利于一整套软件工程规范的训练和科学作风的培养。此外，实践环节中有很重要的一点，就是机器是比任何教师都严格的主考官。

2．教学手段

为了适应现代化教学的需求，我们在传统教学的基础上，充分利用现代科学技术，广泛应用多媒体教学课件和教学软件。将授课内容制作成了图文并茂的多媒体课件，利用多媒体技术对数据结构辅之以形象的动画，动态演示抽象的复杂数据结构的变化，用板书补充某些推导过程并完成和学生互动的内容，改变了以前课堂教学单调的弊病，激发了学生的学习兴趣。使用多媒体技术还可以直接在课堂上演示算法的实现过程，让学生熟悉算法实现的环境和方法，增强了该门课的实践性，提高了课堂授课效率和教学质量，取得了满意的教学效果。教师们为了更好地适应社会的发展和改革的需要，本着强化算法的思想，在现有数据结构内容的基础上，补充了新的算法，拓宽了学生的知识面。

五、课程建设取得的成果

1．教学科研论文

1）The Boundary Element Analysis for The Thermal Conduction of The Thermal Equipment。Proceedings of International Conference on Computational Physics, Rinton Press, US,(2005)199-202（SCI）

2）基于访问控制列表的路由器防火墙在网络安全中的应用研究。计算机与网络 24,(2004)52-53(核刊)3）信息系统在企业现代化管理中的应用。《商场现代化（学术版）》，2005.2 25-26(核刊)4）可信网络基本概念与基本属性研究。《赤峰学院学报 》2007.5 5）基于包过滤技术路由器防火墙在网络安全中的研究。《计算机应用研究》,2007,vol23 6）Research on The Architecture of Tru-Network。2008 International Symposium on Information science and Engineering 7）路由器防火墙对冲击波、震荡波病毒的过滤研究。《赤峰学院学报》 2005.1 67-68 8）菲涅耳圆孔衍射的数值模拟。《赤峰学院学报》 2006.1 9）复杂轴承流体动力学特性的边界元分析。《润滑与密封》 2006.3(核刊 EI核心刊源)10）三叶轴承流体动力学特性的边界元分析。《润滑与密封》 2006.5(核刊 EI核心刊源)11）164-182Hf核的低能谱和电磁跃迁的相互作用玻色子模型。《高能物理与核物理》 28(12),(2004)119-122(核刊, SCI收录)12）基于访问控制列表的路由器防火墙在网络安全中的应用研究。《计算机与网络》 2004.24 13）赤峰学院校园网路由器、交换机的选型及远程登录。《赤峰教育学院学报》2004.5 81-82 14）《XML数据库存储策略综述》 《计算机科学》 2005年9月（核刊）15）《XML数据库结构连接算法之研究》《计算机科学》 2007年6月（核刊）16）《XML中XPath包含关系判定算法》《内蒙古大学学报》2008年10月（核刊）17）《基于关系数据库的XML数据的存储研究》《赤峰学院学报》 2006年 3 月 18）《XML数据库模式匹配算法研究》 《赤峰学院学报》 2007年 5月 19）《Internet蠕虫的分析与研究》 《赤峰学院学报》 2005年 4月 20）《如何防止外部网络的攻击》 《赤峰学院学报》 2004年2月 21）《射频IC卡消费系统的设计与实现》 《赤峰学院学报》 2008年10月 22）《XPath片断的分析与研究》 《赤峰学院学报》 2008年1月 23）《一种基于层次结构的XML编码技术》 中国教育信息化》 2009年4月（核刊）24）《VC++实现图形、数据库应用系统的思路》赤峰教育学院学报 2002年第2月 25）《基于IP组播的多媒体会议系统的设计》 赤峰教育学院学报 2002年6月 26）论文《个性化WINDOWS系统“开始”菜单》赤峰教育学院学报 2003年4月 27）浅谈DEBUG程序的主要命令用法 赤峰学院学报 2007年5月 28）powerpoint技巧在课件制作中的妙用 赤峰学院学报 2006年1月 29）浅谈用MASM运行汇编程序 赤峰学院学报 2005年 1月 30）XML数字签名浅析 赤峰学院学报 2008年 5月 31）《网络层的静态路由选择综述》 赤峰学院学报 2005年3月 32）《离散数学在计算机教学中的作业》 赤峰学院学报 2008年1月 33）《基于模拟退火算法的油井工矿数据挖掘的应用研究》

赤峰学院学报2009年1月

2.教研课题

1）赤峰学院校园网项目 赤峰学院 2002年-2003年（已验收）2）基于IP网QOS动态控制研究 内蒙教育厅 2005年-2007年（已结题）3）基于结构索引XML模式匹配方法研究 内蒙教育厅 2005年—2007年（已结题）4）XML数据库研究 赤峰学院 2006年—2008年（已结题）5）CAI系统中知识个性化组织与导航研究 内蒙教育厅 2003年-2005年（已结题）6）XML安全数据发布关键问题研究 内蒙教育厅 2009年—2010年（在研）3.教学获奖

1）范体贵、门爱华、张国祥、王玉红分别获赤峰学院2005、2006年、2007年、2008年“课堂教学质量优秀奖”；

2）门爱华2007年、2008年连续获的“毕业论文优秀指导教师”奖励； 3）王玉红2007年获院级“毕业实习优秀实习指导教师”奖励；

4）2009年《数据结构课程教学和实践》课题”获赤峰学院“优秀教学成果二等奖”。

数据结构课程组 2009年5月14日

第二篇：数据结构与算法课程总结[模版]

数据结构与算法课程学习总结报告

11计本一班 许雪松 1104013018

数据结构与算法是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。总的来说感触还是比较深的，刚开始上的时候还蛮简单的，越到后面感觉越难，算法也更复杂了，有时候甚至听不懂，老师上课时讲的也蛮快的，所以只能靠课下下功夫了。下面是我对本学期学习这门课的总结。

一、数据结构与算法知识点

第一章的数据结构和算法的引入，介绍了数据和数据类型、数据结构、算法描述工具、算法和算法评价四个方面的知识。

第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的概念，重点在于串的模式匹配。

第三章主要介绍的是线性逻辑结构的数据在链接存储方法下数据结构链表的相关知识。主要是单链表、循环链表的数据类型结构、数据结构、基本运算及其实现以及链表的相关应用问题，在此基础上介绍了链串的相关知识。在应用方面有多项式的相加问题、归并问题、箱子排序问题和链表在字符处理方面的应用问题等。本章未完全掌握的是循环链表的算法问题和C的描述。

第四章介绍在两种不同的存储结构下设计的堆栈，即顺序栈和链栈的相关知识，了解堆栈的相关应用，掌握应用堆栈来解决实际问题的思想及方法。本章主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。本章堆栈算法思想较为简单，所以能较好掌握。

第五章主要介绍顺序存储和链接存储方法下的两种队列、顺序（循环）队列和链队列的数据结构、基本运算及其性能分析以及应用。顺序队列(重点是循环队列）和链队列的概念、数据类型描述、数据结构和基本运算算法及其性能分析等。本章同堆栈有点类似，算法思想较为简单，所以能较好掌握；但难点重在循环队列队空、队满的判断条件问题。

第六章“特殊矩阵、广义表及其应用”将学习数组、稀疏矩阵和广义表的基本概念，几种特殊矩阵的存储结构及其基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。本章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。

第七章二叉树及其应用。分为二叉树的基本概念、二叉树存储结构、二叉树的遍历算法、线索二叉树、二叉树的应用（哈夫曼树、二叉排序树、堆和堆排序、基本算法）。基本算法包括二叉树的建立、遍历、线索化等算法。在此基础上，介绍二叉树的一些应用问题，包括哈夫曼编码问题、（平衡）二叉排序树问题和堆排序问题等。

第八章说的是树和森林，首先我们要知道树与二叉树是不同的概念。课本介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。

第九章“散列结构及其应用”是逻辑结构“集合型”的数据元素在散列存储方法下的数据结构及其应用知识内容。主要介绍散列函数的概念、散列结构的概念、散列存储结构的概念---散列表、散列函数和散列表中解决冲突的处理方法---开放定址法、链地址法以及散列表的基本算法及其性能分析。本章概念较为多，所以掌握不太好。

第十章图及其应用。分为图的概念、图的存储结构及其基本算法、图的遍历及算法、有向图的连通性和最小生成树、图的最小生成树、非连通图的生成森林算法、最短路径、有向无环图及其应用。

二、对各知识点的掌握情况

我对各知识点的掌握情况总结如下：

对于第一章对数据结构的概念理解颇深，大概是每次都要谈论到吧。对算法的时间性能，空间性能基本了解。这些在后面的章节都会有运用。第二章本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。本章未掌握的为希尔排序、快速排序、归并排序的时间复杂度分析。第三章，对链表掌握还好，对其数据结构进行了分析，有循环链表，掌握的不是很好，对其中一些用法不熟练。第四章堆栈，本章堆栈算法思想较为简单，所以能较好掌握，但表达式计算问题未掌握好的。第五章的循环队列队空、队满的判断条件问题掌握的不是很好。第六章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。第七章对二叉树掌握较好，其概念，存储，遍历有很好的掌握。就是对二叉排序树有点生疏，它的生成算法不是很会。第八章树树与二叉树之间的转换，森林与二叉树的转换算法思想基本掌握。第九章散列的一些知识，没有深入学习，大概了解了散列存储结构散列表，散列函数，冲突的处理方法。第十章了解了图的逆邻接表的存储结构，关键路径求解算法未能掌握好，不能灵活运用图的不同数据结构和遍历算法解决复杂的应用问题。

三、学习体会

刚刚接触这门课时，看到课本中全是算法，当时就晕了，因为我的C语言学的不好，我担心会影响这门课的学习，后来上课时老师说学习这门课的基础是C语言，所以我当时就决定一定要好好补补，争取不被拖后腿，在学习这门课的期间，也遇到了不少问。但是通过学习数据结构与算法，让我对程序有了新的认识，也有了更深的理解。同时，也让我认识到，不管学习什么，概念是基础，所有的知识框架都是建立在基础概念之上的，所以，第一遍看课本要将概念熟记于心，然后构建知识框架。并且，对算法的学习是学习数据结构的关键。在第二遍看课本的过程中，要注重对算法的掌握。对于一个算法，读一遍可能能读懂，但不可能完全领会其中的思想。掌握一个算法，并不是说将算法背过，而是掌握算法的思想。我们需要的是耐心。每看一遍就会有这一遍的收获。读懂算法之后，自己再默写算法，写到不会的地方，看看课本想想自己为什么没有想到。对算法的应用上，学习算法的目的是利用算法解决实际问题。会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。

四、对课程教学的建议

1、课程课时较紧，课堂上的练习时间较少，讲解的东西越多，头脑有时就很混乱。

2、感觉上课时的气氛不是很好，虽然大部分人都在听，可是效果不是很好。所以希望老师能在授课中间能穿插一些活跃课堂氛围的话题，可以是大家都非常关心的一些内容，这样既让大家能在思考之余有一个放松，也能够提高学生的学习积极性和学习效率。

3、学习的积极性很重要，有时候我们花了很长时间去写实验报告，也很认真的去理解去掌握，可是最后实验报告可能就只得了一个C，抄的人反而得A，这样的话很容易打击学生的积极性，在后面的实验报告中没动力再去认真写。所以希望老师能在这方面有所调整。

4、虽然讲课的时间很紧，但是还是希望老师能在讲述知识点的时候能运用实际的调试程序来给我们讲解，这样的话能让我们对这些内容有更深刻的印象和理解。

第三篇：数据结构课程总结.[小编推荐]

●数据:能够被计算机识别、存储和加工处理的信息的载体。

●数据元素:数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。

●数据结构的定义: ●逻辑结构:从逻辑结构上描述数据,独立于计算机。线性结构:一对一关系。线性结构:多对多关系。

●存储结构:是逻辑结构用计算机语言的实现。顺序存储结构:如数组。链式存储结构:如链表。索引结构:索引表。散列存储结

构:如散列表。

●对数据的操作:定义在逻辑结构上,每种逻辑结构都有一个运算集合。常用的有:检索、插入、删除、更新、排序。

●数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。原子类型:简单类型,由语言提供。结构类型:由用户借助

于描述机制定义,是导出类型。

●程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。

●算法是一个自定义的计算过程,以一个或多个值输入,并以一个或多个值输出。

●评价算法的好坏的因素:算法是正确的;执行算法的时间;执行算法的存储空间;算法易于理解、编码、调试。

●时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。渐近时间复杂度:是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。

●算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。●时间复杂度按数量级递增排列依次为:常数阶、对数阶、线性阶、线性对数阶、平方阶、立方阶、……k次方阶、指数阶。

●空间复杂度:是某个算法的空间耗费,它是该算法所求解问题规模n的函数。●算法的时间复杂度和空间复杂度合称算法复杂度。

●线性表是由n≥0个数据元素组成的有限序列。n=0是空表;非空表,只能有一个开始结点,有且只能有一个终端结点。

●线性表上定义的基本运算:构造空表:Initlist;求表长:Listlength;取结点:GetNode;查找:LocateNode;插入:InsertList;删

除:Delete。

●顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结

点相邻关系是一致的。地址计算:? ●在顺序表中实现的基本运算:插入:平均移动结点次数为?;平均时间复杂度均为?。删除:平均移动结点次数为?;平均时间复杂

度均为?。

●线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同,为了能正确表示结点间的逻辑关系,在存储每个结点值的同时，还存储了其后继结点的地址信息。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。

●单链表运算:建立单链表(头插法:生成的顺序与输入顺序相反。平均时间复杂度均为?。尾插法:平均时间复杂度均为?。加

头结点的算法:对开始结点的操作无需特殊处理,统一了空表和非空表。查找(按序号:与查找位置有关,平均时间复杂度均为?。

按值:与输入实例有关,平均时间复杂度均为。插入运算:p=GetNode;s-next=p-next;p-next=s;平均时间复杂度均为?,删除运算:平均时间复杂度均为? ●单循环链表是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。

采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O?,不用遍历整个链表。

●双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针

head惟一确定。双链表也可以头尾相构成双循环链表。双链表上的插入和删除时间复杂度均为O?。

●顺序表和链表的比较: ●基于空间:顺序表的存储空间是静态分配,存储密度为1;适于线性表事先确定其大小时采用。链表的存储空间是动态分配,存储

密度1;适于线性表长度变化大时采用。

●基于时间:顺序表是随机存储结构,当线性表的操作主要是查找时,宜采用。以插入和删除操作为主的线性表宜采用链表做存储

结构。若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。

●栈是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底。表中无元素时为空栈。栈 的修改是按后进先出的原则进行的,我们又称栈为LIFO表。通常栈有顺序栈和链栈两种存储结构。

●栈的基本运算有六种:构造空栈:InitStack,判栈空:StackEmpty,判栈满:StackFull,进栈:Push,退栈:Pop,取栈顶元素: StackTop ●在顺序栈中有“上溢”和“下溢”的现象。“上溢”是栈顶指针指出栈的外面是出错状态。“下溢”可以表示栈为空栈,因此用来作为控制

转移的条件。

●顺序栈中的基本操作有六种:构造空栈,判栈空,判栈满,进栈,退栈,取栈顶元素 ●链栈则没有上溢的限制,因此进栈不要判栈满。链栈不需要在头部附加头结点,只要有链表的头指针就可以了。

●链栈中的基本操作有五种:构造空栈,判栈空,进栈,退栈,取栈顶元素 ●队列是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,允许删除的一端称为队头,允许插入的一端称

为队尾,队列的操作原则是先进先出的,又称作FIFO表.队列也有顺序存储和链式存储两种存储结构。

●队列的基本运算有六种:置空队:InitQueue,判队空:QueueEmpty,判队满:QueueFull,入队:EnQueue,出队:DeQueue,取

队头元素:QueueFront ●顺序队列的“假上溢”现象:由于头尾指针不断前移,超出向量空间。这时整个向量空间及队列是空的却产生了“上溢”现象。为了克

服“假上溢”现象引入循环向量的概念,是把向量空间形成一个头尾相接的环形,这时队列称循环队列。

●判定循环队列是空还是满,方法有三种:一种是另设一个布尔变量来判断;第二种是少用一个元素空间,入队时先测试%m=front? 满:空;第三种就是用一个计数器记录队列中的元素的总数。

●队列的链式存储结构称为链队列,一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入的操作,在表尾增加一个尾

指针,一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中,要注意当原队中只有一个结点时,出队后要同进修改头尾指针并使队列变空。

●串是零个或多个字符组成的有限序列。

●概念空串:是指长度为零的串,也就是串中不包含任何字符。空白串:指串中包含一个或多个空格字符的串。在一个串中任意

个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。

空串是任意串的子串,任意串是自身的子串。

●串分为两种:串常量在程序中只能引用不能改变;串变量的值可以改变。●串的基本运算有:求串长strlen,串复制strcpy,串联接strcat,串比较charcmp,字符定位strchr。串是特殊的线性表,所以串的存

储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。●顺序串又可按存储分配的不同分为:静态存储分配:直接用定长的字符数组来定义。优点是涉及串长的操作速度快,但不适合插

入、操作。动态存储分配:是在定义串时不分配存储空间,需要使用时按所需串的长度分配存储单元。

●串的链式存储就是用单链表的方式存储串值,串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单

个字符。为了解决“存储密度”低的状况,可以让一个结点存储多个字符,即结点的大小。

●顺序串上子串定位的运算:又称串的“模式匹配”或“串匹配”,是在主串中查找出子串出现的位置。在串匹配中,将主串称为目标, 子串称为模式。这是比较容易理解的,串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是Om,假如m与n同阶的话则它是O。链串上的子串定位运算位移是结点地址而不是整数。

●数组一般用顺序存储的方式表示。

●存储的方式有:行优先顺序,也就是把数组逐行依次排列。PASCAL、C。列优先顺序,就是把数组逐列依次排列。FORTRAN ●地址的计算方法:按行优先顺序排列的数组:LOC(a=?.。按列优先顺序排列的数组:LOC(a=?.矩阵的压缩存储:为多

个相同的非零元素分配一个存储空间;对零元素不分配空间。

●特殊矩阵的概念:所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。

●稀疏矩阵的概念:一个矩阵中若其非零元素的个数远远小于零元素的个数,则该矩阵称为稀疏矩阵。

●特殊矩阵的类型:对称矩阵:三角矩阵:上三角阵,下三角阵,对角矩阵k=f(I,j, ●广义表是n个元素的有限序列,其中的元素是原子或者是一个广义表。广义表表头和表尾的概念: ●广义表有两种表示法,一种是括号表示法,一种是图形表示法。

●广义表有两个特殊的基本运算:取表头head:取表中的第一个数据元素,不能对空表操作。取表尾tail;取除表头外,其余数据元

素构成的子表,不能对空表操作

●树是n个结点的有限集合,非空时必须满足:只有一个称为根的结点;其余结点形成m个不相交的子集,并称根的子树。根是开始

结点;结点的子树数称度;度为0的结点称叶子;度不为0的结点称分支结点;除根外的分支结点称内部结点;●有序树是子树有左,右之分的树;无序树是子树没有左,右之分的树;森林是m个互不相交的树的集合;●树的四种不同表示方法:树形表示法;嵌套集合表示法;凹入表示法;广义表表示法。

●二叉树的定义:是n≥0个结点的有限集,它是空集或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树

组成。二叉树不是树的特殊情形,与度数为2的有序树不同。二叉树的4个重要性质: ●二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。

●树的存储结构多用的是链式存储。二叉树的链式存储结构,称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域, n+1个空指针。

●根据结点的次序不同可得三种遍历:先序遍历,中序遍历、后序遍历。时间复杂度为。

●利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针,这些附加的指针就称为“线索”,加

上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效,但对于查找指定结点的前序前趋和后序后继并没有什么作用。

●树和森林及二叉树的转换是唯一对应的。二叉树变树:结点的右孩子与其双亲连。森林变二叉树:树变二叉树,各个树的根相连。

转换方法? ●树的存储结构:有双亲链表表示法:孩子链表表示法:双亲孩子链表表示法:孩子兄弟链表表示法: ●树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致。

●树的带权路径长度?最优二叉树?完全二叉树?哈夫曼树及其性质，●变长编码技术可以使频度高的字符编码短,而频度低的字符编码长,但是变长编码可能使解码产生二义性。如00、01、0001这三

个码无法在解码时确定是哪一个,所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀,这种码称为前缀码。哈夫曼树的应用。

●图的逻辑结构特征就是其结点的前趋和后继的个数都是没有限制的,即任意两个结点之间之间都可能相关。

●图,有向图,无向图,简单路径,简单回路,网络等及其性质。

●图的存储结构:邻接矩阵表示法:适合稠密图。无向邻接矩阵是对称的。有向行是出度,列是入度。建立邻接矩阵算法的时间是

O,其时间复杂度为O。邻接表表示法:适合稀疏图。时间复杂度为O,空间复杂度为O。

●图的遍历:深度优先遍历:借助于邻接矩阵的列。使用栈保存已结点。广度优先遍历:借助于邻接矩阵的行。使用队列保存已结

点。

●生成树的定义:最小生成树:Prim算法的时间复杂度为O与边数无关适于稠密图。Kruskal算法的时间复杂度为O,主要取决于边

数,较适合于稀疏图。

●最短路径的算法:Dijkstra算法,时间复杂度为O。

●拓扑排序:无前趋的顶点优先:每次输出一个无前趋的结点并删去此结点及其出边,最后得到的序列即拓扑序列。无后继的结点

优先:每次输出一个无后继的结点并删去此结点及其入边,最后得到的序列是逆拓扑序列。

●关于排序

●关键字项,关键字。

●排序是使文件中的记录按关键字递增次序排列起来。●基本操作:比较关键字大小;改变指向记录的指针或移动记录。

●存储结构:顺序结构、链表结构、索引结构。经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方

法是稳定的,否则排序算法是不稳定的。

●排序过程中不涉及数据的内、外存交换则称之为“内部排序”,反之,若存在数据的内外存交换,则称之为外排序。

●内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序和分配排序。

●评价排序算法好坏的标准主要有两条:执行时间和所需的辅助空间,另外算法的复杂程序也是要考虑的一个因素。

●插入排序:直接插入排序;逐个向前插入到合适位置;哨兵有两个作用;作为临变量存放R[i];是在查找循环中用来监视下标变量j是否

越界;直接插入排序是稳定排序。时间复杂度为O ?比较次数为/2;移动次数为?。希尔排序:等间隔的数据比较并按要求顺序排列,最后间隔为1;希尔排序是就地的不稳定排序。时间复杂度为O,比较次数为;移动次数为;●交换排序:冒泡排序:自下向上确定最轻的一个。自上向下确定最重的一个。冒泡排序是就地的稳定排序。时间复杂度为O?比

较次数为?;移动次数为?;快速排序:以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合。

重复直到排序完成。快速排序是不稳定排序。时间复杂度为O?比较次数为?。●选择排序:直接选择排序;选择最小的放在比较区前;直接选择排序不稳定排序。时间复杂度为O?。比较次数为?。堆排序:建堆: 按层次将数据填入完全二叉树,从int处向前逐个调整位置。然后将树根与最后一个叶子交换值并断开与树的连接并重建堆,直到全断开。堆排序是就地不稳定的排序,时间复杂度为O,不适宜于记录数较少的文件。

●归并排序:先两个一组排序,形成/2组,再将两组并一组,直到剩下一组为止。归并排序是非稳定排序,时间复杂度是O? ●基数排序:从低位到高位依次对关键字进行箱排序。基数排序是非就稳定的排序,时间复杂度是O?。

●各种排序方法的比较和选择: ●

1、待排序的记录数目n;n较大的要用时间复杂度为O的排序方法;●

2、记录的大小;记录大最好用链表作为存储结构,而快速排序和堆排序在链表上难于实现;●

3、关键字的结构及其初始状态;●

4、对稳定性的要求;●

5、语言工具的条件;●

6、存储结构;时间和辅助空间复杂度。●关于查找

●查找的同时对表做修改操作则相应的表称之为动态查找表,否则称之为静态查找表。

●衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数。

线性表查找的方法：顺序查找：逐个查找，ASL=？;二分查找：取中点 int 比较，若小就比左区间，大就比右区间。用二叉判定树 表示。ASL=？;分块查找：要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引 表。

二叉排序树定义是二叉排序树是空树或者满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的 值;若它的右子树非空，则右子树上所有结点的值均大于根结点的值;左、右子树本身又是一棵二叉排序树。

二叉排序树的插入、建立、删除的算法平均时间性能是

O？。二叉排序树的删除操作可分三种情况进行处理：*P 是叶子，则直接删除*P，即将*P 的双亲*parent 中指向*P 的指针域置空即可。*P 只有一个孩子*child，此时只需将*child 和*p 的双亲直接连接就可删去*p。*p 有两个孩子，则先将*p 结点的中序后继结点的数 据到*p，删除中序后继结点。

关于 B-树。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。常见的散列 函数构的造方法：平方取中法,除余法,相乘取整法,随机数法。

处理冲突的方法：开放定址法：一般形式为?，开放定址法要求散列表的装填因子 α≤1。开放定址法类型：线性探查法，二次探查 法，双重散列法。拉链法：是将所有关键字为同义词的结点在同一个单链表中。拉链法的优点：拉链法处理冲突简单，且无堆积现象;链表上的结点空间是动态申请的适于无法确定表长的情况;拉链法中 α 可以大 于 1，结点较大时其指针域可忽略，因此节省空间;拉链法构造的散列表删除结点易实现。

拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。

第四篇：《数据结构》课程教学大纲

《数据结构》课程教学大纲

Data Structure 执笔人：

编写日期：

一、课程基本信息

1.课程编号：

2.课程性质/类别： 必修课 / 专业主干课

3.学时/学分： 48 学时（另实验16学时）/ 4 学分

4.适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业

二、课程教学目标及学生应达到的能力

数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。

三、课程教学内容与基本要求

（一）绪论（3 学时）1．主要内容：

（1）介绍什么是数据结构；

（2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；

（3）抽象数据类型的表示与实现；

（4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。2．基本要求

（1）了解学习数据结构的重要性；

（2）掌握数据结构的定义及相关概念和术语；（3）了解抽象数据类型的定义、表示与实现方法；（4）理解算法的概念、特点并掌握度量其效率的基本方法。3．自学内容：

类C语言的书写规范。

（二）线性表（6 学时）1．主要内容：

（1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等；（2）线性表顺序存储表示和基本操作的实现；（3）线性表的链式存储表示和基本操作的实现；

（4）稀疏多项式的抽象数据类型定义、表示和加法的实现。2．基本要求

（1）掌握线性表的定义和特点；

（2）熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法；

（3）熟练掌握单链表、循环链表、双向链表三种链表的表示，以及单链表的查找、插入、删除、创建等实现算法。

3．自学内容：

静态链表。

（三）栈和队列（5 学时）1．主要内容：

（1）栈和队列的结构特性和抽象数据类型定义；（2）栈和队列的顺序存储表示和实现；（3）栈和队列的链式存储表示和实现；（4）栈和队列在程序设计中的应用。2．基本要求

（1）掌握栈和队列两种抽象数据类型的特点；

（2）掌握栈的两种存储表示和实现，特别注意栈满栈空的条件；（3）掌握队列的两种存储表示和实现，特别注意队满队空的条件；（4）了解递归算法与栈的关系。3．自学内容：

链栈，离散事件模拟

（四）串（3 学时）1．主要内容：

（1）串的抽象数据类型定义；

（2）串的表示和实现: 定长顺序存储结构和堆分配存储结构；（3）串的各种基本操作的实现及其应用；（4）串的模式匹配操作。2．基本要求

（1）熟悉串的一些基本操作的定义，并能利用基本操作实现串的其它操作；（2）掌握串的定长顺序存储结构以及基本操作的实现；（3）掌握串的堆分配存储结构以及基本操作的实现；（4）掌握串的简单模式匹配算法，理解KMP算法。3．自学内容：

串操作的应用实例。

（五）数组和广义表（4 学时）1．主要内容：

（1）数组的抽象数据类型定义及其顺序表示和实现；（2）特殊矩阵和稀疏矩阵的压缩存储；（3）广义表的抽象数据类型定义和存储结构。2．基本要求

（1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；（2）掌握对特殊矩阵进行压缩存储时的下标变换公式；

（3）熟悉稀疏矩阵的三元组顺序表存储结构下的一般转置和快速转置算法；了解十字链表等存储结构；

（4）掌握广义表的结构特点、取表头表尾操作，及其存储表示方法。3．自学内容：

采用十字链表存储结构创建稀疏矩阵。

（六）树和二叉树（10 学时）1．主要内容：

（1）树的抽象数据类型定义和基本术语；

（2）二叉树的抽象数据类型定义、性质和存储结构；（3）二叉树的遍历；

（4）线索二叉树的定义、遍历及线索化二叉树；

（5）树的存储结构、树和森林的遍历以及与二叉树的转换；（6）Huffman树及其应用。2．基本要求

（1）掌握树型结构的特点和基本术语；

（2）熟练掌握二叉树的性质，了解相应的证明方法；

（3）了解二叉树的顺序存储结构和链式存储结构，熟练掌握二叉链表存储结构；（4）熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法，能灵活运用遍历算法实现二叉树的其他操作；

（5）熟练掌握二叉树的线索化过程，以及在中序线索二叉树上找结点的前驱与后继的方法；

（6）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；（7）了解Huffman树的特性，掌握建立Huffman树和Huffman编码的方法。3．自学内容：

先序、后序遍历二叉树非递归算法，层次遍历二叉树算法。

（七）图（9 学时）1．主要内容：（1）图的定义和术语；

（2）图的四种存储结构：数组表示法（邻接矩阵）、邻接表、十字链表和邻接多重表；（3）图的两种遍历策略：深度优先遍历和广度优先遍历；（4）图的连通性和最小生成树；

（5）有向无环图及其应用：拓扑排序和关键路径；（6）最短路径问题。2．基本要求

（1）熟悉图的定义和术语；

（2）了解图的存储结构，熟练掌握数组表示法（邻接矩阵）和邻接表存储表示；（3）熟练掌握图的深度优先遍历和广度优先遍历算法；（4）掌握无向连通带权图的最小生成树求解算法；

（5）了解有向无环图、AOV网、AOE网及其在实际中的应用，熟悉拓扑排序算法和关键路径算法；

（6）熟悉两种最短路径问题求解算法。3．自学内容：

树的先根遍历算法与图的深度优先遍历算法比较；

树的层次遍历算法与图的广度优先遍历算法比较。

（八）查找（4 学时）1．主要内容：

（1）查找的基本概念和相关术语；

（2）静态查找表：顺序查找、折半查找和索引顺序表查找；（3）动态查找表：二叉排序树的查找、插入和删除；（4）哈希表。2．基本要求

（1）了解查找的作用，熟悉相关术语；

（2）熟练掌握顺序查找、折半查找和索引顺序表查找；（3）熟练掌握二叉排序树的特性、构造和查找方法；

（4）熟练掌握哈希表的构造方法，特别是哈希函数和处理冲突方法的选取；（5）通过分析等概率下的平均查找长度来衡量各种查找方法的效率。3．自学内容：

平衡二叉树。

（九）内部排序（4 学时）1．主要内容：

（1）排序的基本概念和相关术语；

（2）插入排序：直接插入排序、折半插入排序和希尔排序；（3）交换排序：起泡排序和快速排序；（4）选择排序：简单选择排序和堆排序；（5）归并排序：二路归并排序；（6）基数排序：链式基数排序；（7）各种内部排序方法的比较讨论。2．基本要求

（1）了解排序作用，熟悉相关术语；

（2）掌握多种排序的基本思想、算法特点和排序过程，分析它们的时间复杂度、空间复杂度和稳定性。

3．自学内容：

二路插入排序、表插入排序和树形选择排序。

四、教学安排建议

1.作业练习 完成每章的教学后进行布置习题，使用教材配套的《数据结构题集（C语言版）》。尽量选择基础的并且加注了标记的题，应注重于精，而不要求多。要求积极独立完成所布置的习题，建议安排至少六次。

2.案例分析

可参考选择以下一些案例：（1）学生通讯录管理系统，（2）表达式求值问题（3）交通咨询系统，等。3.专题研讨

可参考选择以下一些：（1）最小生成树问题（2）航班信息查询与检索系统，（3）内部排序算法比较，等。

4.实验安排

为了达到理论与实际应用的结合，让学生能将所学知识应用于实际问题的求解中，培养学生的实际动手能力，从而加深对概念及所学知识的理解，灵活、牢固掌握教材内容，提高程序设计及解决实际问题的能力，实验环节的安排非常重要。

建议实验安排为八次，共16学时，分别如下：

实验1 线性表的顺序存储结构的实现(2学时)

实验2 线性表的链式存储结构的实现(2学时)

实验3 栈的算法实现(2学时)

实验4 队列的算法实现(2学时)

实验5 串类型及操作(2学时)

实验6 二叉树的建立与遍历(2学时)

实验7 图的建立与遍历(2学时)

实验8 查找与排序(2学时)注：教师可根据教学实际情况（如：学生情况及学时情况等），适当调整实践教学内容及学时分配。

五、课程考核

1.考核形式及成绩评定办法

本课程考核形式为：平时成绩占40%，期末考试成绩占60%。其中平时成绩的结构分包括：课堂表现10%、平时作业10%和实验20%，期末考试为闭卷笔试考试：120分钟，卷面分满分100分。期末考试成绩低于50分者，本课程成绩按不及格论处。

2.本课程考核的基本要求

课堂表现10%：包括课堂考勤和课堂提问，如果缺课课时达到本课程教学时数的1/3，则取消考试资格。

平时作业10%：根据上交次数及完成情况进行评定。

实验20%：根据各次实验完成情况及实验报告成绩进行评定。

期末考试60%：本课程的期末考试考核内容主要包括线性表、栈与队列、串、数组与广义表、树与二叉树、图、查找和内部排序。其中，线性表、二叉树、图、查找和内部排序内容为考核的重点。

六、本课程与其它课程的先行后续关系

先行课程：《高级程序设计语言》、《离散数学》

后续课程：《操作系统》、《编译原理》、《数据库理论》、《算法分析与设计》等

七、建议教材及教学参考书

1.教材：

严蔚敏，吴伟民编著，《数据结构（C语言版）》，清华大学出版，2012.5 严蔚敏，吴伟民编著，《数据结构题集（C语言版）》，清华大学出版，2012.5 2.参考书：

[1] 许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，2004.[2] 徐孝凯，《数据结构简明教程》，清华大学出版社，1995 [3] 陈文博，朱青，《数据结构与算法》，机械工业出版社，1996 [4] 李云清，杨庆红，揭安全编著，《数据结构》（C语言版），人民邮电出版社，2007.[5] 杨秀金主编，《数据结构》，西安电子科技大学出版社，2002.[6] 李廉治，姜文清，郭福顺，《数据结构》，大连理工大学出版社，1989

[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989

[10] [美]S巴斯《计算机算法：设计和分析引论》朱洪等译，复旦大学出版社，1985

第五篇：数据结构课程教学大纲

数据结构课程教学大纲

一、课程基本概况

课程名称：数据结构

课程名称（英文）： Data Structures

课程编号：B09042

课程总学时：60（其中，讲课48，实验12）

课程学分：3

课程分类：专业选修课

开设学期：4

适用专业：计算机网络工程本科

先修课程：集合论，图论，高级语言（结构或记录，指针）

后续课程：数据库，编译原理，操作系统等

二、课程的性质、目的和任务

数据结构是计算机专业的一门核心专业课程，是软件课程中非常重要的一门课程，在整个专业教学中占有十分重要的地位，是一门理论性非常强的课程。通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性，数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。

三、主要内容、重点及深度

本门课程共60学时，其中理论教学48学时，实验教学12学时。其中，理论教学部分：

第一章

绪论

（一）目的要求

了解数据结构的意义与发展过程、数据结构在计算机科学中的作用、学习本课程的目的、任务及要求。理解数据结构的基本概念；算法设计；掌握算法的时间和空间复杂度。

（二）教学内容 本章知识点：

1.相关的基本概念(掌握)；

2.算法五大要素(掌握)；

3.计算语句频度和估算算法时间复杂度的方法（掌握）。

（三）重点与难点

重点：数据结构的定义；算法的描述方法。

难点：数据结构的定义；算法与程序的区别；时间复杂度及其计算。

第二章

线性表

（一）目的要求

掌握线性表的逻辑结构；线性表的存储结构及操作的实现；理解一元多项式的表示；

（二）教学内容 本章知识点：

1.线性表的逻辑结构(掌握)；2.线性表的存储结构(掌握)；

3.线性表在顺序结构和链式结构上实现基本操作的方法(掌握)；

4.从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合(掌握)。

（三）重点与难点

重点：线性表的概念；线性表的顺序存储结构、链式存储结构及其常用算法。难点：链式存储结构及其常用算法；双向循环链表。

第三章 栈和队列

（一）目的要求

掌握栈的定义，表示及实现；表达式求值；栈与递归过程；队列的定义、表示及实现。

（二）教学内容 本章知识点： 1.栈和队列的特点(掌握)；

2.在两种存储结构上栈的基本操作的实现(掌握)； 3.循环队列和链队列的基本运算(熟练掌握)； 4.递归算法执行过程中栈状态的变化过程(掌握)。

（三）重点与难点

重点：堆栈和队列的概念；递归的定义；循环队列和链队列的基本运算。难点：递归的编程实现；循环队列和链队列的基本运算。

第四章 串

（一）目的要求

了解串的逻辑结构，存储结构；掌握串操作的实现(重点难点BF和KMP算法)串的应用。

（二）教学内容 本章知识点：

1.串的七种基本运算的定义（了解）；

2.利用这些基本运算来实现串的其它各种运算的方法(掌握)； 3.在顺序存储结构上实现串的各种操作的方法(掌握)；

4.KMP算法，熟悉NEXT函数和改进NEXT函数的定义和计算(掌握)； 5.串名的存储映象和在堆存储结构实现串操作的方法(理解)。

（三）重点与难点 重点：串定义和存储方法；串的操作 难点：串操作实现方法

第五章 数组和广义表

（一）目的要求

掌握数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法。

（二）教学内容 本章知识点：1.数组在以行为主的存储结构中的地址计算方法(掌握)； 2.矩阵实现压缩存储时的下标变换(掌握)；

3.理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法(掌握)；

4.广义表的定义及其存储结构，学会广义表的表头，表尾分析方法(掌握)； 5.学习编制广义表的递归算法(掌握)。

（三）重点与难点

重点：多维数组元素存储地址的计算；稀疏矩阵的三元组表示；广义表的存储定义、操作。难点：稀疏矩阵的三元组表示；广义表的存储定义、操作。

第六章 树和二叉树

（一）目的要求

了解树的基本概念；理解二叉树的性质和存储结构；遍历二叉树和线索二叉树；理解树的存储结构和遍历；集合的一种表示方法；掌握哈夫曼树及其应用；

（二）教学内容 本章知识点： 1.二叉树的结构特点(理解)；

2.二叉树的各种存储结构的特点及适用范围(掌握)； 3.按各种次序遍历二叉树的递归和非递归算法(掌握)；

4.二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法(掌握)； 5.树的各种存储结构及其特点(掌握)； 6.编写树的各种运算的算法(掌握)；

7.建立最优二叉树和哈夫曼编码的方法(掌握)。

（三）重点与难点 重点：二叉树的概念、性质；二叉树的遍历方式；构造二叉排序树。难点：二叉树的遍历方式；二叉排序树的构造方法；二叉树的线索化。

第七章 图

（一）目的要求

理解图的基本概念；图的存储结构；掌握图的遍历及应用{最小生成树，最短路径等}；拓扑排序和关键路径。

（二）教学内容 本章知识点： 1.熟悉图的各种存储结构；

2.了解实际问题与采用何种存储结构和算法有密切联系(掌握)； 3.遍历图的递归和非递归算法(掌握)；

4.应用图的遍历算法求各种简单路径问题（比如，最小生成树、最短路径、拓扑排序、关键路径等）(掌握)。

（三）重点与难点

重点：图的存储结构；图的遍历 难点：图遍历的算法；

第八章

动态存储管理

（一）目的要求

了解边界标识法和伙伴系统；无用单元收集和紧缩；

（二）教学内容 本章知识点：

1.存储器分配策略和算法（了解）；

2.无用单元收集时的标志算法（了解）。

（三）重点与难点

存储器分配策略和算法、无用单元收集时的标志算法

第九章

查找

（一）目的要求

了解静态查找表(顺序表，有序表，索引顺序表)；动态查找表(二叉排序树，平衡二叉树，B-树和B+树)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教学内容 本章知识点：

1.顺序查找、折半查找和索引查找的方法、应用(掌握)；

2.二叉排序树的构造方法(掌握)；

3.二叉平衡树的建立方法(掌握)；

4.B-树，B+树和键树的特点以及它们的建立过程（理解）；

5.哈希表的构造方法(掌握)；

6.按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度；

7.哈希表在查找不成功时的平均查找长度的计算方法(掌握)。

（三）重点与难点

重点：二叉排序树的构造方法、二叉平衡树的建立方法；哈希表的构造、应用；

难点：二叉排序树的构造及应用；哈希表的构造方法；查找的平均长度。

第十章

内部排序

（一）目的要求

掌握插入排序、交换排序(起泡排序，快速排序)、选择排序(简单选择，树形选择，堆)、归并排序、基数排序等算法。

（二）教学内容 本章知识点：

1.各种排序方法的特点并能灵活应用(掌握)； 2.各种方法的排序过程(掌握)；

3.各种排序方法的时间复杂度分析(掌握)。

（三）重点与难点

重点：各种排序方法的特点及其应用；实现排序的各种算法。难点：各种排序算法的时间复杂度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握败者树和多路平衡归并的实现；置换--选择排序；最佳归并树。

（二）教学内容 本章知识点：

1.外部排序的两个过程(理解)；

2.外排过程中所需进行外存读/写次数的计算方法(掌握)；

3.败者树的建立过程(掌握)；

4.实现多路归并的算法(掌握)；

5.置换-选择排序的过程(掌握)；

6.最佳归并树的构造方法（熟悉）；

7.按最佳归并树的归并方案进行平衡归并时，外存读/写次数的计算方法(掌握)。

（三）重点与难点

重点：外部排序过程和实现方法；多路并归算法及其实现； 难点：最佳并归树的构造方法及其应用。

实践教学部分：上机实验分4个专题，每个专题可提供2~4个难度不等的题目供选。

实验一

停车场管理系统

（一）实验内容 以栈模拟车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。

（二）实验过程 编程实现实验内容。

（三）实验教学基本要求

通过实例，使学生掌握栈和队列两种特殊的线性结构，掌握栈和队列的特点。实验后学生提交实验报告。

（四）实验设备和材料 计算机。

（五）实验学时 4学时

实验二

教学计划编制问题

（一）实验内容

假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。编制一个教学计划程序。

（二）实验过程编程实现实验内容。

（三）实验教学基本要求

通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。

（四）实验设备和材料 计算机。

（五）实验学时 2学时

实验三

最小生成树问题

（一）实验内容

利用克鲁斯卡尔算法求最小生成树。以文本形式输出树中各条边以及他们的权值。

（二）实验过程 编程实现实验内容

（三）实验教学基本要求

通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。

（四）实验设备和材料 计算机。

（五）实验学时 2学时

实验四

哈希表设计

（一）实验内容

假设人名为中国人的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。

（二）实验过程 编程实现实验内容

（三）实验教学基本要求 掌握索引技术的使用。

（四）实验设备和材料 计算机

（五）实验学时 4学时

五、课程教学的基本要求和主要环节

本课程可采用课堂讲授、课堂讨论、习题课等进行课堂教学;条件允许可采用CAI、电子教案、幻灯片、参观等进行辅助教学;每章布置3~6道习题以巩固教学;在课程后半程，安排3~4个上机实验，让学生应用数据结构的理论、方法，分组设计几个较大的软件，使理论与实际相结合。

考试采用闭卷方式。总成绩由平时成绩和考试成绩组成。平时成绩占30%，考试成绩占70%。

六、本课程与其它课程的联系与分工

先修课包括：集合论，图论，高级语言（结构或记录，指针）；

后续课包括：数据库，编译原理，操作系统等。

七、建议教材与参考教材

《数据结构》（C语言版）

严蔚敏等

清华大学出版社

1997 《数据结构题集》

严蔚敏等

清华大学出版社

1999

《数据结构习题与解析》

李春葆

清华大学出版社

2004

八、负责人

撰稿人：刘景汇、李玉香

审稿人：

系（院）领导：