数据结构课程的知识体系和教学实践

第一篇：数据结构课程的知识体系和教学实践

数据结构课程的知识体系和教学实践－－张铭 许卓群 杨冬青 唐世渭

一、数据结构知识体系

计算机科学已经深入应用到各个领域，不仅有效地解决了各种工程和科学计算中的数值计算问题，而且也有效地解决了许多文本处理、信息检索、数据库管理、图像识别、人工智能等非数值的数据处理问题。数据结构有助于程序员更有效地组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际需要。

数据结构是计算机学科的重要分支研究领域。数据结构和算法在计算机学科中的地位十分重要，其他计算机科学领域及有关的应用软件都要使用到各种数据结构。数据结构是算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程的先行课程。语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表，多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等。

美国IEEE和ACM的教学计划CC2001把《算法与数据结构》列入计算机以及信息技术相关学科专业的本科必修基础课程。在我国，《数据结构》已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构更是必须透彻地掌握的重要基础。

1．数据的逻辑结构、存储结构和运算

从字面上来看，数据结构就是指数据间的相互关系。具体到计算机环境，谈到任何一种结构时，都自然地联系着作用在这种类型的数据上的运算（即函数），为了在计算机上执行这些运算，我们有必要把这些数据以某种方式存储在计算机中。因此，我们可以认为，所谓数据结构，就是由某种逻辑关系组织起来的一批数据，按一定的存储方法被存储于计算机中，并在这些数据上定义了一个运算的集合。也就是说，数据结构具有三个方面：数据的逻辑结构、数据的存储结构和数据的运算。

常见逻辑关系有：线性结构、树形结构、图结构和文件结构。其中，线性结构是最简单的数据结构，例如，程序设计语言中往往都会介绍的线性表（包括数组和链表）、栈、队列、向量、字符串等。其中，字符串就是每个结点都是单个字符的线性表。实际上多维数组和广义表也是线性结构的推广。另外，文件其本质也是线性结构，不过由于存储在外存中，对文件数据的访问速度非常慢，因此，仔细研究文件结构和基于文件的外排序也是很有必要的。二叉树和树是非常重要的数据结构，其应用十分灵活而广泛。二叉树可以看作是树的特例。例如，语言编译中要用到语法树，操作系统有目录树，数据库系统需要用索引树等进行数据管理，而在人工智能领域，需要用到搜索树等。许多真实世界的问题都可以图来抽象地定义。例如，一张交通图可以用数据结构的图来形象化地表示：用结点表示城市，用边表示连接城市的高速公路；Web网页的关系也可以表示为图：Web网页作为结点，网页之间的链接作为边。图是一种最通用的逻辑结构，实际上，图树二叉树线性表。

常见的存储方法有：顺序方法、链接方法、索引方法、散列方法。其中，索引存储又分为线性和树形两种。文件结构的索引则往往用树形结构。

对于一种数据结构，往往需要定义一些运算。例如，建立数据结构、清除数据结构、插入一个新数据元素、删除某个数据元素、修改某个数据元素、排序、检索等。作为最常用的算法，排序和检索历来是数据结构讨论中的重点问题。排序算法最能够体现算法的魅力，它对算法速度要求非常高，其中内排序主要考虑的是怎样减少关键码之间的比较次数和记录交换次数，以提高排序速度。可以证明所有基于比较的排序算法的时间代价是Θ(nlog n)，这也是排序问题的时间代价；而外排序则考虑外存的特性，尽量减少访外操作，以提高排序速度。检索则考虑怎样提高检索速度，这往往是与存储方法有关的。例如，我们可以利用索引存储来加快检索。散列表、B树和B+树等高效的数据结构都具有极好的检索性能。

2．算法的效率问题

每一种数据结构与其相关的算法都有时间、空间开销和效率等问题。每当面临一个新的设计问题时，设计者都应该要权衡时间空间开销，设计出更有效的数据结构和算法，以适应问题的需要。

基本问题包括：对于给定的一类问题，最好的算法是什么？需要多少存储空间和时间？空间与时间的折衷方案是什么？存取数据最好的方法是什么？最好算法的最坏情况是什么？平均来说，算法的运行好到何种程度？算法一般化到何种程度——即什么类型的问题可以用类似的方法处理？

这就涉及到算法分析技术，许多数据结构教材都揉合了一些基本的算法分析技术，这有助于读者根据问题的性质选择合理的数据结构，并对时间空间复杂性进行必要的控制。

3．抽象数据类型

事实上，数据结构的三个侧面，以数据的逻辑结构和数据的运算定义更为重要。因为很多时候人们并不关心数据的存储结构和运算的具体实现。1983年Aho等人把数据结构的存储与实现细节剥离，定义了抽象数据类型（简称“ADT”）的概念。抽象数据类型是定义了一组运算的数学模型。例如栈结构，栈中元素的数学特性(即逻辑结构)表现为线性表，它们是有序的；栈的主要运算是进栈(push)、出栈(pop)、判栈空(isEmpty)等。这里我们并不涉及栈的存储方式以及栈中元素的类型等。这种抽象的数据类型可以在较高级的算法中直接引用，而不用考虑它的实现细节。这就使得设计者可以在不同的设计阶段采用不同的抽象数据类型作为设计的基础，在适当的抽象层次上考虑程序的结构和算法，从而很好地支持了逻辑设计和物理实现的分离，支持封装和信息隐蔽。

大多数教材都是以数据的逻辑结构为主线，顺序介绍线性结构、树形结构、图结构和文件结构。在介绍每种数据结构时，再讨论其存储结构以及相关的算法。例如对于线性表，如果考虑到存储，可以分为数组和链表；考虑到运算的特殊性，则可以分为向量、栈和队列。对于一些比较重要的算法，再列出单独的章节来讨论，例如排序、检索、索引、存储管理等。

二、数据结构的教学目的

Peter J．Denning等人认为，计算机学科分为理论、抽象、设计这三个形态。我们把数据结构课程所涉及的主要方面整理为：

1.理论

(1)算法的数学基础。例如，有关图论、组合论等，特别是递归、递推、归纳等分析方法。(2)算法的时间和空间度量。2．抽象(1)排序、检索等重要问题类的有效算法，以及最好、最差和一般性能的分析比较。

(2)重要数据结构技术，例如分治法(二分检索、快速排序、归并排序)、贪心算法（Huffman编码、Prim算法、Kruskal算法、Dijstra算法）、动态规划（Prim算法、Dijstra算法、Floyd算法、最佳二叉搜索树）、栈的引用（深度优先周游）、队列的应用（广度优先周游）。3．设计

(1)掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法及其主要的算法，例如线性结构（包括一维数组、链表、栈、队列、字符串等）、二叉树、树、图、文件；

(2)排序、检索、索引等重要问题类的算法的选择、实现和测试。例如，各种排序方法的实验时间比较，散列、倒排索引、B树等应用。(3)存储管理的实现与测试。例如可利用空间表、无用单元收集、伙伴系统。

数据结构这门课程不仅仅要让学生掌握那些链表、树、图是如何实现的。设置这门课程有三个目的：第一个目的是让学生懂得“数据结构＋算法＝程序”；第二个目的是培养数据抽象的能力；第三个目的是使得学生把数据结构和算法理论与编程实践相结合，能够在实际的工程实践中灵活地予以应用。

在达到前两个目的时，学生就基本具备了解决现实未知问题的能力，再辅以必要的综合上机项目训练，可以达到第三个目的。

总而言之，通过数据结构课程的教学，学生需要掌握以下四个方面的知识和能力：（1）掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法、主要的算法，例如线性结构、二叉树、树、图、文件；（2）掌握并简单应用常用的排序、检索和索引算法和方法；（3）掌握基本的算法设计和分析技术，并对自己设计的数据结构和算法进行简单的分析；（4）在进行程序设计、调试、测试的课程项目训练（即上机实习训练）过程中，要求学生综合应用所学到的数据结构和算法知识，学会分析研究数据对象的特性，以便选择合适的数据结构和存储结构以及相应的算法，合理地组织数据、有效地表示数据、有效地处理数据，书写的程序结构清楚、正确易读，提高程序设计的质量。

三、数据结构教材编写思路

北京大学计算机系许卓群、张乃孝、杨冬青、唐世渭于1987年编写的《数据结构》（高等教育出版社出版）曾被很多高校计算机专业用为数据结构课程教材。该书已重印多次，并于1992获得教育部教材优秀奖和国家教材优秀奖。随着计算机技术的发展和应用，很多读者建议教材要能及时体现新的教学内容，建设配套的教学资源，并希望在算法的伪代码编码风格方面，由类PASCAL改为类C++语言。

针对这些建议，结合北京大学计算机科学与技术专业数据结构课程建设的实际情况，许卓群、杨冬青、唐世渭、张铭等多年从事《数据结构》教学和研究的教师一起新编了《数据结构与算法》教材。新书以中国计算机科学与技术学科教程CCC2002和美国IEEE和ACM的教学计划CC2001所规定的基本知识点为主要内容，同时参考并吸收了国内外最新数据结构教材的优点。主要编写原则和编写大纲的考虑如下。

1．新编《数据结构与算法》教材的主要编写原则

 以中国计算机科学与技术学科教程CCC2002和美国IEEE和ACM的教学计划CC2001所规定的基本知识点为主要内容。

 考虑采用最广为程序员所使用的C++语言作为算法描述语言，从而使得抽象数据类型(ADT)的概念得到更自然的体现，更本质地体现数据结构的思想，而且所定义的数据结构类能够方便地被重用。

 为了保证教材的易读性，尽量回避C/C++中比较麻烦的内容，例如C的指针的指针的指针等折磨人的东西，C++的类的继承、虚函数等。 使用参数化的模板（template），从而提高算法中数据类型的通用性，支持高效的代码重用。在后面的章节中，尽量使用STL(Standard Template Library，标准C++类库)所提供的栈、队列等基本数据结构。 删掉逆转链周游二叉树、Robson周游算法、Siklossy周游算法、关键路径等内容，并增加Patricia树、伸展树等复杂树结构，k-d树、PR四分树、R*树等空间数据结构。

 每章中均提供适量的综合上机实习题（即项目实习）。 为了配合教材的使用，我们将编写概念清晰、内容充实的多媒体演示讲稿以及用标准C++模板编写的可执行的源程序代码，同时建设了课程教学网站。

2．新编教材大纲的考虑

考虑到数据结构这门课程基本知识点的划分，根据我们多年教学经验，作者对新编教材的内容做了精心的安排。新书以中国计算机科学与技术学科教程CCC2002中的PF3基本数据结构、AL1算法分析基础、AL3基本算法为核心内容，分为基本数据结构、排序和检索、高级数据结构三个部分。第一部分（共6章）从逻辑结构的角度系统地介绍各种基本数据结构，即概论、线性表(包括向量、栈和队列)、字符串、二叉树、树和图。概论讨论了数据结构的定义、抽象数据类型和基本的算法分析技术。第二部分（共4章）从算法的角度讨论排序、检索和索引算法，索引算法新增加了关于文本文件的倒排索引，倒排索引是当前信息检索和搜索引擎技术的关键技术。考虑到计算机学科的应用性以及学生灵活应用数据结构解决实际问题的需要，第三部分（共2章）介绍了数据结构的高级主题，例如广义表和稀疏矩阵等更复杂的线性表结构，Trie结构、AVL树、伸展树等复杂树结构，k-d树、PR四分树、R*树等空间数据结构，把存储管理作为线性结构的典型应用予以介绍，把决策树和博弈树作为树型结构的典型应用加以介绍。最后附录布置了一个学期综合上机实习题“搜索引擎”，并简单介绍了其中涉及的图搜索、倒排索引等技术。

其中第一部分是最基本的内容，教师可以根据学生的程度选择第二部分、第三部分一些内容来讲解。该教材能够适应不同读者的学习需要以及教师的教学安排，特别为教师安排上机实习提供了极大的方便。

四、教学策略

数据结构课程中，既有很多灵活的与离散数学（尤其是图论、组合数学）有关的证明题，又有大量算法设计题。而且该课程对程序设计能力的要求很高，需要学生动手编写实习题以应用并掌握数据结构知识。对于计算机专业的学生来说，学习《数据结构》之前应该先修《计算引论》（或称“计算概论”，“计算机文化基础”）、《面向对象程序设计实习》、《集合论与图论》这三门课程。对于只有“计算概论”基础的非计算机专业的学生，可以适当减少数学证明的要求，不要求设计比较复杂的算法。

为做好“数据结构”这门重要主干基础课程的教学工作，作者以热忱的工作态度、以科研工作的钻研精神认真投入教学研究，投入了大量精力和时间，建立了全新的教学体系，尽力完善各个教学环节。

1.启发式教学，培养学生的创造性思维和主动学习精神

在数据结构教学中，对于每种数据结构都从其数学特性入手，先介绍其抽象数据类型，然后再讨论其不同的存储方法。与学生一起讨论研究不同存储方法的可能算法，结合算法分析来讨论各种存储方法和算法的利弊，摒弃那些不适宜的方法。这样，充分调动了学生思维积极性，学到了数据结构的思维方法以及从事科研的基本方法。

2.与科研结合，在教学中引进新的理论和技术内容

尽量把科研中涉及到的与《数据结构》课程相关的新理论和技术、优秀论文介绍给学生，拓展了教学内容。例如，给学生讲解“搜索引擎”中的数据结构技术（主要涉及到图搜索、排序和索引技术），讲解当前网络和数据库的研究热点“XML（扩展标记语言）”。

3.加强实践环节的训练

北京大学计算机系历来十分重视实践环节的训练。《数据结构》课程一直为每学期4学分/每周4学时，每位学生的上机实习时间每学期约80小时。从2003届北京大学信息学院计算机专业的学生开始，《数据结构》将改为两门课程，即《算法与数据结构》和《数据结构实习》，在同一个学期讲授，分别为每学期3学分/每周3学时，每学期2学分/每周2学时。改革的目的主要是加强上机实践，每位学生的数据结构上机实习时间增加为每学期120小时。

数据结构是一门理论和实践结合比较紧密的课程，每周都布置6道书面作业或小程序实习（全学期约70道），每个学期布置6道大的上机实习题（其中最后一道是2-3人合作的学期综合上机实习题，例如“搜索引擎”、“XML数据管理”等）。组织助教认真检查习题和上机题，并编写了参考答案公布在网上。

4.采用新的教育技术，提高教学效果； 建立了一个高质量的课程网站http://db.pku.edu.cn/mzhang/ds/index.htm。网站主要内容有：多媒体演示讲稿、标准C++模板编写的可执行的源程序代码、习题和上机题及其参考答案。课程网站还有一个BBS讨论版，每个学期都会有约700个数据结构主题讨论。教员每周都组织助教讲解习题中的问题和难点，并组织学生讨论习题和上机题中的问题、以及各种不同解法及其效率。

5.严格要求，教书育人，培养好学风。

为了防止学生抄袭上一届的作业和上机题，每一届都重新布置新的书面习题和上机题。另外，还要求学生在提交的书面作业、电子版程序和报告中，都写上“诚实代码”——“我XXX真诚地保证：我自己独立地完成了整个作业和程序从分析、设计到编码的所有工作。我没有抄袭任何其他人的作业。”学生纷纷反映这种自己以人格保证的形式，大大减少了抄袭现象。

五、结束语

作者试用新教材给电子商务专业学生授课，把最基本的内容安排在前6章讲解完，然后简单介绍了第7章的内排序，其他内容让感兴趣的学生自学。该专业的学生们反映课程内容非常充实，知识点掌握得很牢固。在给北大信息学院计算机专业的二年级本科生试用新教材时，在接近一半的学期课程时间就讲完了前6章，重要的章节都可以安排比较综合的上机实习题；在开始讲解排序与检索的同时，可以开始安排学期综合上机实习题；最后第11-12章比较高级的数据结构内容只是讲座性的内容，没有上机实习的压力，而学生也面临期末考始复习了。从学生评估以及系领导对往届学生的调查情况来看，到了高年级以后，学生们都反映数据结构是知识拓展非常广、非常有用的课程。

作者希望，通过数据结构的学习，学生们能养成严谨的科学作风，学到科学的思维方法，提高设计高质量程序的能力，奠定扎实的软件开发基础。

第二篇：《数据结构》课程教学反思

《数据结构》课程教学反思

(2006-10-02 20:31:34)转载▼

教学反思，是教师以自己的教学活动过程为思考对象，对自己的某种教学行为、决策以及由此产生的结果进行审视和分析的活动。实践证明，由教师本人对教学实践及其成败得失进行反思，有利于教师及时总结自己的教学经验，培养教师学习、研究的意识，促使教师更好地实现教学理论与教学实践的结合，提高教师的教学能力与水平。

以上是一段从网络摘抄的语句，其实对教学反思是怎样一回事认识并不是很深刻，就像学生前些日子询问的说课，懂得说课，但并不知道怎样跟学生解释什么是说课，只记得一句从网络上看到的话“授课主要是怎样讲，说课主要是为什么这样讲”。

要对上一个月的教学进行反思，是上星期就一直想进行的事情，但始终觉得找不到充实的时间或者是找不到很好的思路。要进行教学反思，主要还应该是对《数据结构》课程的反思，毕竟它是一门基础、核心的专业课程，而且也是系里第一次的开课。

对课程的反思：

1、很重要。数据结构是几乎所有软件方向专业课的基础，学C语言让你知道了什么是编程，而数据结构告诉你该怎么去编程。用网上一个例子来说，数据结构让你知道怎样从一个地方到另一个的路，而C语言等让你知道选择什么样的交通工具去走这些路，你不懂得去北京的路，给神六你坐也到达不了。

2、很多点。既然培养数据的处理能力，又要培养算法设计思路，还要培养实际的应用能力。有点兼顾不过来，理解算法思想倒是能达到的要求，但在实际应用能力的培养上，存在难度。

3、很难学。教师艰难的教，学生吃力的学。理解算法的思想，但如何放到实际中始终是难题，教师难找到合适的方法，学生接受能力有限，经验受制，受程序语言不熟练等影响。

对教师的反思：

1、经验不足。毕竟刚从大学毕业回来，教学经验欠缺，且系里也是第一次开这样的课程。对数据结构这门课本身理解不透，特别在实践方面接触较少，进行过的无非是大学时一些作业。因此在教师教学方法和学生接受能力间找一个结合点是一直苦苦探索的问题，直到现在仍是没有一个明确有方向。

2、目标过大。接受这个可以说是苦差的教学任务后，其实我的有埋怨过，但我更多是考虑如何去实现某些目标。让学生理解数据结构的算法思想，培养学生算法设计的思路，加强数据结构的实用性。从一个月的教学情况，目标定得过高了，特别是实践环节上，过高估计自己的教学能力，也过高估计学生的学习能力。但我直到现在，特别是在实践上，我找不到说服自己放弃的理由，毕竟总觉得学习了思想，不能在编程上实现，或者说是学会了例子，不会变通，算不上学会。我怀疑教学目标，但又放不开手。

3、时间欠缺。由于教学任务的限制，上机实践时间比较少，是以对学生把所学的思想转化为算法进而转化为程序的指导不足。一个月才开了一次实践课，本来已经足够，但对学生的实际情况来说，这还是很欠缺的。

对学生的反思：

1、思想重视不够。首先，作为师范生不重视这些难度偏深的课程；其次，作为计算机学生不重视这些偏向理论的课程；再次，在难学面前退却，没有足够的学习兴趣、信心和耐心。特别在对待操作作业上，一个月过去，第一次的作业完成几乎为零。

2、语言能力较差。尽管上学期学习了C语言，不说程序设计能力，且说C语言的基础知识掌握都是较差的。还是那句，把实践当成了死记硬背来考试，把知识当成了例子来学习。欠缺独立思考，欠缺独立编程。

3、自主协作不行。不能自觉的进行学习，什么都要教师在课堂上讲，或者只局限于课本，不懂得利用网络或参考书进行知识的拓展。也没有形成协作学习的氛围，同学间的交流不够，论坛学习的方法不懂。这归于两个原因，一个自觉性问题，一个班级氛围问题。

4、素质起点不好。这是我一直不想谈及的问题，毕竟我反复的强调过，他们大专生和本科生差别不大，在大学里都是一个新的起点，但在突出的个体上可以这样考虑，从整体上差异总还会存在的。尽管我承认这差异，但我依然否定他们说的智商等先天因素，这些只会是借口。我说的差异，首先就是自觉性，这一点在他们过分追求自由中散失；其次是空闲时间的自由度，学校安排课程过多，时间上和精力上有限；再次是学习氛围，那种泡图书馆和学术争论的氛围欠缺；最后是课程的关联大，一些关联课程如C语言掌握得较差。

对教学的展望：

1、能尽量在课堂教学中贯穿操作实践，引导学生把算法结合数据结构形成程序，但受时间限制较大，只能尽量起到牵引作用，一切还看学生课余时间进行。

2、督促完成第一次作业，毕竟数据结构的思想很多都体现在这次线性表实践作业中，能真正独立思考去完成，对以后课程的学习，相对会轻松很多。接着再进行更高一层次的，利用这些算法去解决实际的问题。

3、引导学生形成自主学习能力的自我培养及协作学习的氛围形成。毕竟这两个能力是计算机专业学生培养的重点之一。

4、细化目标，毕竟这门课是难学的，逐步进行目标，首先，让学生了解数据结构的逻辑特点，各种操作的算法思想；其次，让学生运用编程语言编写程序实现这些算法；最后，把这些编程思想和设计思路运用到实际应用中解决问题。

5、加强师生交流，了解学生想法，了解学生遇到的问题，更好的有目的的教学。

以此为反思，但愿能更好的进行以后的教学！

第三篇：课程感想-数据结构

转眼间半学期已经过去了，接触数据结构这门课已经八周了。在这一段时间的学习中，我对这门课从刚开始的一窍不通到现在已经可以运用所学的知识解决一定的问题，大致知道了数据结构的思想和作用。

首先对于数据结构，我的认识一直在发生改变，一开始的时候连逻辑结构和物理结构都分不清，到最后能将总表上的内容熟记于心，并加以运用，这样的进步离不开老师的细心教导和同学们的热心帮助。在我的认识中，计算机技术早已经成为新世纪的必修技能。很庆幸我选的专业可以在计算机上有所进阶，为自己在日后的竞争中多添一份筹码。“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已经成为其他理工专业的热门选修课。

在这门课程里，我首先认识了什么是数据、什么是数据结构以及抽象数据类型这些基本的概念，然后开始学习数据结构的抽象数据的部分。线性表是学习的第一站，我逐渐发现，每开启一个新的逻辑结构，就会相应的讲它的存储结构以及相应的运算。在学习线性表的过程中，我弄明白了很多东西，发现了数据结构已经比c语言高出一个高度了更加宏观地去用c语言，c语言就像是处理数据结构的其中一种工具一样。学习完线性表之后，就像有了一个模板，之后的栈和队列是进出的方式有所修改各有特色了。学到树的时候，眼前一亮，觉得这样的类比方式很有意思，有点像高中生物遗传学上的系谱图。二叉树的遍历让我觉得就像小时候玩智力游戏一样，还有二叉树中例如求深度这样的高度提炼规律又是需要我去努力思考认真总结的„„这门课让我第一次觉得大学还真的有题要想的这么费脑子。

老师上课的方式也很有效率。刚开始的时候我被一大堆概念搞晕了，但是想着就是一堆概念而已课下也就没再去细细研究。结果上课老师提问的时候果然没有答上来，之后每次课前课后都要争取做到预习复习，巩固课上学的知识。不过学知识当然也不是为了应付老师的提问，既然选择了智能，以后这条路要走的顺畅，还少不了数据结构的知识。

结课的时候老师布置了几道编程的题目，一开始看到书上题目里直接有代码，就赶紧往c语言的软件里敲，结果发现运行不成，和同学们交流了之后才知道，可能是调取数据库的问题，书上的函数编译器无法识别，于是我发现我们的主要任务是集中火力把书上提供的功能函数的功能写出来，换言之，就是构造出这些个函数然后再使用它们去实现功能。在编程的过程中出现了很多的问题，比如指针本来就是c语言中的灵魂，难点中的难点，在数据结构的编程中几乎全部都要用到指针，让我不得不又翻开c语言的教材去复习指针的相关知识。另外，编出来的程序有时候自己看不出来错误但是编译器就是报错，又请教了班里一些已经完成的同学，在他们的意见指导下，改进自己的代码最终运行成功实现功能了。尤其是二叉树的那道题，因为书上没有讲如何输入二叉树，我就在思考无果之后去查资料，才了解c语言是这样和二叉树联系在一起的。当年创造出数据结构的人真的是非常厉害。经过这次的编程，我觉得自己不仅捡起来了上学期学的c语言，也加深了对数据结构和c语言的理解。我们现在掌握的数据结构的知识，就如同我偶然在图书馆看到数据结构的书架一样，只是这个庞大、精深体系中的冰山一角而已，就像老师说的，编程类的知识，老师只是把你带进门，想要真正掌握还是要自己下很多功夫的。

转眼间数据结构这门课已经接近尾声，很多人都说编程是一条孤独的、枯燥的路，其实我感觉编程还挺好玩，每编一个程序都像是一场斗智斗勇的冒险，一头扎进去就是好几个小时，也会经常和同学分享一下自己的思路或者见解，越学越觉得智慧殿堂无穷无尽。有时候我以为我自己设计的已经比较简洁比较巧妙了，听了别人的更是醍醐灌顶，觉得自己傻透了。

在这一段时间的学习里，我们同学之前互相沟通交流，互相帮助过得也很愉快，和刘老师相处的也非常融洽，希望老师在日后的生活教学中多注意身体，老师在教我们之前生了一场病，如果不是这样，老师上课的风采应该更甚。在以后的学习中，我也会继续探究数据结构的奇妙世界，学无止境，争取在数据的道路上更上一层楼！

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

数据结构课程教学大纲

一、课程基本概况

课程名称：数据结构

课程名称（英文）： 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

八、负责人

撰稿人：刘景汇、李玉香

审稿人：

系（院）领导：

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

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

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