登录 | 注册
精品课程点击排行榜  >>  数据结构与算法
课程简介 教师队伍  

■ 课程简介
课程名称： 数据结构与算法 一级学科：  08 工学
二级学科： 0806 电气信息类 教学层次：  本科
负责教师： 廖明宏 学校名称：  哈尔滨工业大学
院系名称：   申报状态：  已获奖
申报级别： 省级 申报文件下载：  无下载文件
获奖名称： 获奖年度：  2006
主页地址： http://cst.hit.edu.cn/dsa/ 是否交换：  否
浏览次数： 12056 网上评论：  没有相关评论
课程介绍：

4-2理论课和理论（含实践）课教学内容
4-2-1结合本校的办学定位、人才培养目标和生源情况，说明本课程在专业培养目标中的定位与课程目标

哈尔滨工业大学是国家“985工程”重点建设的9所大学之一，其办学定位是世界知名高水平大学，人才培养目标是培养精英型人才，哈工大的生源都来自全国各地优秀的高中毕业生。计算机科学与技术学科是国家的重点学科、省重点学科，同时也是哈工大重点建设的18个重点学科之一，我们的人才培养理念是“研究型、个性化、精英式”人才。作为计算机科学与技术专业的核心课程，《数据结构与算法》在人才培养目标的定位上起到举足轻重的作用。它是计算机专业的专业基础课，因此课程的目标是通过理论学习和实践活动，使学生系统地掌握数据结构的基本思想和算法设计的基本方法，通过培养面向问题求解的能力提高学生的创新能力。

4-2-2知识模块顺序及对应的学时

数据结构与算法总学时64，讲课学时52，实验学时12。

教学上以激发学生求知欲望为主线，从数据的定义入手，让学生首先了解计算机就是用来处理数据的，数据的不同组织形式会影响问题的求解效率，让学生了解到数据结构的重要性，从而积极探索数据的表示方法，增加学习的兴趣。

绪论及算法基础（4学时），主要介绍了数据结构的基本概念和术语及基本表示方法；数据结构在软件系统中的作用；课程的研究和学习内容；算法好坏的衡量标准，如何分析时间复杂性和空间复杂性。

通过介绍在计算机内数据的基本表示方法，引出了基本的数据结构：线性表（4学时），栈，队列（4学时），串和数组（2学时），这一部分主要介绍线性结构一对一的关系，同时又提出来现实生活中还有许多一对多的关系。

这种非线性关系又应该如何表示，也就引出了树结构：树和二元树的定义，二元树的性质，二元树的逻辑结构与存储结构（2学时），如何将非线性结构转换成线性结构，就引出了二元树的遍历算法（4学时），树的存储与遍历算法，森林与二元树的转换（2学时），树的应用（4学时）。

数据之间还有多对多的更复杂的数据关系又应该如何表示呢？这时就开始介绍图结构。主要介绍了图的基本定义及存储方法（2学时），图的搜索算法（4学时），图的基本应用：最小生成树，拓扑分类、关键路径、最短路径等（6学时）。此时数据的基本表示方法已介绍完毕。

下面就要介绍这些数据存储的一些应用，也是一些经典算法的介绍，查找（线性查找，折半查找、分块查找、二元查找树、平衡树、B树、散列法查找）（6学时），排序（简单分类、快速分类、归并分类，堆分类、基数分类）（4学时）。最后介绍外部分类与文件（2学时）。

实验12学时，包括：

  1. 线性表实验（3学时）：

    主要内容：顺序和链式存储的线性表、栈、队列的建立、查找、插入、删除等算法的设计。

    实验目的：掌握线性基本数据结构的设计与实现。

  2. 二元树的建立与遍历（3学时）：

    主要内容：顺序结构和链式结构表示的二元树的建立方法，对建立的树进行三种非递归遍历，或利用遍历算法完成一些基本问题。

    实验目的：掌握非线性结构的存储方案及遍历算法，并能实现简单的应用。

  3. 图的建立与搜索（3学时）：

    主要内容：在计算机中建立给定的图的存储方案，并按要求对图进行先深和先广搜索。

    实验目的：掌握图的存储方法，并能简单的应用。

  4. 查找与排序（3学时）：

    主要内容：建立二元查找树，并实现查找、删除操作；利用学过的排序算法对给定序列进行排序，并分析各类排序算法的效率。

    实验目的：利用学过的数据结构进行简单的算法设计。

4-2-3课程的重点、难点及解决办法

课程的重点：

  1. 掌握数据结构的逻辑结构、存储结构及数据操作三方面的概念及相互关系。
  2. 熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，掌握栈和队列在两种存储结构上实现的基本操作。
  3. 串上实现的模式匹配算法。
  4. 掌握二元树的遍历算法及其有关应用。
  5. 图的存储结构和遍历算法。
  6. 掌握顺序查找、二分查找，二元查找树上查找以及散列表上查找的基本思想和算法实现。
  7. 掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程。

课程的难点：

  1. 算法复杂性的分析方法。
  2. 能够有效算法解决与线性表相关的应用问题及循环队列中对边界条件的处理。
  3. 设计算法解决与树或二元树相关的应用问题。
  4. 有关图论的算法、二元查找树的删除算法。
  5. 四种排序算法的实现。

解决方案：

算法的复杂性问题是对算法的效率进行分析，通过给出顺序结构、循环结构、递归调用等算法，说明各语句、各结构的分析方法，最后得出结论。线性表、树、图的基本结构与算法的学习，从数据结构的逻辑结构入手，逐步讨论其基本操作、存储结构及具体实现；从简单的数据结构入手逐步讨论复杂的数据结构，让学生了解现实中的实例如何抽象成数学模型，数学模型如何在计算机中表示，基本操作如何实现等，在课堂中通过例题，展示基本操作是怎样应用到简单算法设计中；在每章结束后利用大作业锻炼学生的理论与实际相结合的能力。比如学完线性表的知识，就设计了“模拟机场飞机起降系统”，学完树的内容就设计“如何在信号传输中解决信号衰减问题”，学完图的内容就设计“校园导游图问题”。

4-2-4实践教学的设计思想与效果（不含实践教学内容的课程不填）

1．实践教学的设计思想

实践教学是课程学习的重要环节，我们的设计思想是：以个性化培养为基础，以创新能力培养为目标系统设计实践教学内容。具体地：

（1）理性实践。注意引导学生利用所学理论、技术和方法解决实际问题，在这些理论、技术和方法指导下进行实践（实验和课程设计），即理性实践，使学生在理论与实践的每次循环中体会感到欣喜和成就感。提高了学习兴趣，增强了信心，达到了巩固基础知识和知识综合运用能力不断提高的目的。

（2）培养面向问题求解能力的实践教学。面向问题求解能力是学生创新能力培养的基础。我们在实践课程中增加了设计型实验和课程设计，锻炼了学生综合运用所学理论知识解决复杂问题的实际能力。主要实现方案是在第二课堂和课程设计中，我们给学生这样的问题：要求学生把学过知识用上，设计一个系统模拟食堂售饭系统，统计每天中午学生在食堂停留的时间。这种没有具体要求，只有问题的思想，会充分调动学生的积极性，积极思考，把问题解决。

（3）实践教学与科研、专业相结合。课程设计指导教师大都来自科研一线，学生课程设计题目选自指导教师研究方向与本课程有关的部分。使学生提前受到科学研究方法的熏陶，训练提高了学生查阅资料和文献能力，锻炼了科技论文撰写作能力。

（4）加强个性化指导，按大纲基本要求不同的学生不同的难度，能力强的学生题就多一些难一些，能力差的同学就要求完成基本的内容，所以为每15名学生配备一名指导教师，针对性进行辅导。

（5）累加式考核。考核形式采用答辩方式，最后成绩由下列四方面组成：程序设计30%、设计作品20%、报告撰写40%和答辩表现10%。锻炼了学生的表达能力和科学报告能力。

2．实践教学效果

（1）通过对学生的个性化培养，学生的学习热情得到极大的激发，其创新能力得到很好的培养。许多学生在三年级时就进入了实验室和研究中心的学生俱乐部。

（2）通过实践环节的“程序设计、设计作品、报告撰写和答辩表现”四个方面的考核，使学生更好地理解课堂教学内容，拓展知识面，延伸和扩展了课堂教学。全面地培养了学生的素质，提高了学生的抽象能力、思维能力、算法和数据结构的设计与分析能力、科学报告的撰写和表达能力。

（3）课程设计与指导教师的科研方向相结合，不仅使学生能够较早地了解计算机科学的最新发展方向和课学研究的方法，而且能够学会如何利用所学知识解决实际问题的能力。学生对教材没涉及的内容自己去查资料，完成相应的数据结构设计，锻炼了文献查阅能力和科研能力。

?
4-3教学条件（含教材使用与建设；促进学生主动学习的扩充性资料使用情况；配套实验教材的教学效果；实践性教学环境；网络教学环境）
???

一、教材使用与建设

本课程使用的主教材是2000 年6月第三版的《数据结构与算法基础》（郭福顺，廖明宏等编著），是21世纪高等学校计算机专业规划教材。

此教材从1977年开始时郭福顺老师的讲义发展来的。1989年正式出版了 Pascal语言版的《数据结构》，该教材在国内首次采用抽象数据型的观点组织的，由此，于1992年获得第二届机械电子工业部电子类专业优秀教材二等奖。作为《数据结构》配套教材，我们于1991年由电子工业出版社出版了《数据结构实践教程》。

在2000年，第三版更名为《数据结构与算法基础》，在数据结构内容的基础上增加算法的介绍、算法分析以及算法设计等内容，使算法与数据结构有机的融合。同时被列入是21世纪高等学校计算机专业规划教材。

我们建设的《数据结构与算法》课程被评为2005年度教育部－微软精品课程建设项目，教材《数据结构与算法》被列为教育部“十一五”规划教材。

二、学习扩充性资料的使用情况

为了促进学生的主动学习，我们补充的学习资料有：

  1. 教学网站：http://cst.hit.edu.cn/datastructure；
  2. 自编并出版了《数据结构实践教程》；
  3. 多媒体电子教案的纸制版和网络版；
  4. 数据结构与算法课程实验指导书的纸制版和网络版；
  5. 数据结构与算法课程设计指导书的纸制版和网络版；
  6. 此外，国外优秀的经典教材，如：

    (1) Data Structures and Progeram Design in C++，Robert L. Kruse Alexander J. Ryba 高等教育出版社；
    (2) 数据结构、算法与应用——C++ 语言描述 （美）Sartaj Sahni 著，机械工业出版社；
    (3) C 算法，第三版（第二卷 图算法），Algorithms in C, (美)Robert Sedgewick 著。

这些补充资料与主教材一起，形成了多种媒体的、立体化教学和学习资料体系。不仅扩大了学生的眼界，而且对学生的思维能力的培养、实践水平的提高很有帮助，很受学生欢迎。

三、实验教学效果与实验教学环境

  1. 实践环节教材与学科发展同步。哈工大在计算机科学与技术学科在全国处于领先地位。我们充分发挥学科和科研优势，以课程的基本理论、技术和方法与各个科研方向紧密结合来设计课程实践环节（课程实验和课程设计）教材的内容，并随着学科的发展不断地更新，始终保持与学科的同步。

  2. 个性化指导与分类培养。除了主讲教师之外，实践环节指导教师还精选了个研究中心和研究所的在职博士生和优秀的博士生。每15名学生配一个实践指导教师。在课程实践环节中，发挥学科和科研优势，在注重课程的基本原理、技术和方法的实际应用的同时，逐步引导学生熟悉和体会科学研究的一般过程和科学研究方法。此外，根据学生的学习情况，在实验方面采取了基本内容实验与综合设计型实验相结合的方法，进行个性化的辅导和分类培养，接受能力强的同学多做，一般的同学完成基本内容，让每个学生都能感受到学习的成果，取得了很好的教学效果。

  3. 现代化的实践教学环境。实验教学环境良好，能充分保证教学需要。计算机学院软件实验中心面积约2000平方米，有1000台P4以上的微机全部联入Internet，各种配套设备若干台。实验课在计算机学院软件实验中心完成。每个实验均有实验指导材料及实验项目管理卡片，并提供有业余时间的开放实验室。除专门辅导外，还给学生提供了大量的基础练习，推荐了经典的数据结构网站和自己的教学网站，学生可以在宿舍和实验室上网访问和答疑。

  4. 全方位的综合能力考核方案。课程的考核采用累加式的考核方法，废除了“一次定论”的考核制度，并且逐步地增加实践环节的考核比重。课程实验的考核由三部分组成：“程序设计、测试分析和设计报告”；课程设计的考核包括四部分：“程序设计，设计作品，报告撰写和答辩表现”。通过累加式、不同角度的考核，使学生的综合素质得到了很好的培养和体高。

四、网络教学环境

为课程配备了专门的服务器，设计开发了课程教学网站，教学网站可以提供全方位的辅导，包括教学大纲、实验大纲、课程设计大纲、示范性教学设计、学习指导、电子教案、在线测试、习题库和学生论坛等。

学生可以通过课程教学网站进行课后学习、自测、提问、课件的下载，作业、实验和课程设计的选题和结果提交等。

教师可以对课程资源（如电子课件、实验和课程设计内容等）和学生的作业、实验、课程设计等进行管理。

?
4-4教学方法与教学手段（含多种教学方法灵活使用的形式与目的；教育技术应用与教学改革）
???

一、采用双主线来贯穿教学内容的教学方法

鉴于《数据结构与算法》的内容特点，本课程形成了一套独特的教学理念，即在课程讲授中采用双主线教学形式，其中一条是显式的主线，而另外一条是隐藏在第一主线背后的，需要不断强调的、深入认识的主线。

第一条主线就是对数据结构的学习和认识，具体表现为从简单数据结构(线性结构)到复杂数据结构(图结构)的认识过程。为了这一主线的清晰性，本课程以ADT为核心将各类数据结构的共性问题提取出来，加以讲授。例如，在课程讲授过程中，依次将线性结构(包括一般的线性表、栈、队列、串、数组、广义表等)，树结构(包括一般的树、二元树、森林、树的若干变形等)，图结构(包括无向图、有向图等)的ADT形式化的定义给出。并通过对其数学结构、逻辑性质、相关操作及物理实现的深入剖析，进而揭示各类数据结构的纵向区别和横向联系，形成对本课程的宏观认识。（需加链接到课程讲义）

第二条主线就是应用数据结构基本知识、基本原理来解决实际问题的能力培养，这一部分在课程教学上主要体现为数据结构应用实例的剖析以及经典问题(如查找和排序)的数据结构求解，其教学方法可以采用灵活多样的方法，如课堂剖析、大作业、网上讨论、课程设计等等。例如，针对本课程的这一特点，提出了面向问题的课程设计教学模式（需加链接到文章计算机教育2006，2），并在课程设计中给出了大量需要综合应用各类基本数据结构才能完成的问题，如在传感器网络的单机模拟设计中，其中综合应用集合、数组、队列、图等多种数据结构。（需加链接到课程设计报告样例）

依照人们接受知识的规律，在具体教学过程上，我们主要围绕第一主线展开，由浅入深、自顶向下、先表后里、逐步细化，从数据结构的逻辑结构入手，逐步讨论其基本操作、存储结构及具体实现；从简单的数据结构入手逐步讨论复杂的数据结构，为第二主线的展开打下基础。第二主线的教学采用归纳式学习法，通过在大量内容基础上的总结，引导学生逐步构建根据数据结构基本原理解决实际问题的能力。最终达到知识的灵活应用，为后续课程，以及将来的研究和实际工作打下坚实的基础。两条主线相辅相承，共同深化。

二、在课程教学中贯彻“探索型”和“能力型”教学模式

在本课程的教学过程中，我们正努力将传统的知识型、原理型、展示型授课方法转变为激励探索型和能力培养型教学模式。

在激励学生的探索精神方面，我们主要采用了如下手段：

  1. 在课堂上和课堂外引入课程重点内容的思考题、学科的前沿问题、或一些科研问题供学生讨论，并组织博士助教参与讨论或邀请科研专家对问题进行剖析。例如，鼓励学生在课外收集新兴数据结构，对其进行理论分析并给出演示算法，然后组织讨论。
  2. 在讲授具体课程内容时，对某些方法(尤其是有一定历史意义的算法)，除讲解其基本原理以外，还对当时的分析过程、设计过程给予分析，以激发学生对问题的探索精神。例如，在讲解哈夫曼树时，将哈夫曼提出哈夫曼树的历史过程给予重现，鼓励学生对提出问题、解决问题的能力。

在培养学生能力方面，我们主要采用了如下手段：

  1. 加强实践能力的培养。由于数据结构与算法课程作为计算机软件系列课程中的一门核心课程，我们在本课程的教学过程中，时刻注意加强对数据结构的实践能力和操作能力的培养，在教学中辅以大量的习题、上机实验、综合设计等。同时，我们也十分注重数据结构对其它软件系列课程的支撑作用，即注重培养学生应用数据结构知识解决计算机问题的能力。例如，在课程设计中，就安排有应用数据结构模拟操作系统、进行数字图像处理等方面的训练。
  2. 加强解决问题能力的培养。表现为对分析问题能力的培养，主要是通过在教学中加强数学建模意识的建立得以完成；对问题求解能力的培养，主要靠多做精炼；对求解结果表达能力的培养，主要通过实验报告的撰写、课程设计报告的撰写加以培养，帮助学生形成良好的行文素养。

三、以多媒体讲义和课程教学网站为中心来构建立体化、信息化的教育手段

在教学过程中，本课程也始终注意学生主动探索能力的激发。为此，我们采用了诸如数字化、信息化、多媒体等多种现代辅助教学手段，主要包括如下四个部分：

1. 多媒体电子教案

通过多媒体电子教案可以更加合理的组织讲授内容、条理清晰、加大信息量。另外通过课堂上的多媒体演示也可以使重点问题的剖析形象化，如在图的先广遍历中，通过对队列变化过程的动态演示可以建立对算法的深刻认识，课堂实践证明这样做可以取得良好的效果。

2. 课程教学网站

课程教学网站除可以帮助正常的教学环节外，还在网站上不断引入专题讨论、课程前沿内容、趣味讨论等多种形式激发学生的探索。

3. 算法动态演示系统

为建立对典型算法的直观认识，该系统给出了数据结构典型算法的动态演示。主要包括诸如图的搜索、各种排序算法、各种查找算法的动态演示等。

4. 网上习题库

为加强学生对课程各部分内容的理解和掌握，网上题库可以对学生进行全面细致的训练。

四、加大了教学方法、作业以及考试制度等方面的改革

在教学方法的改革上，本课程组进行了坚持不懈的努力，产生了大量的辅导书集和教学研究文章。同时，我们还在教学方法上不断探索，提出了学科前沿式、科研激励式、问题驱动式、创新思维式等多种教学模式，并将其应用到教学实践中。

在作业方面，改革了传统的知识型、训练型作业内容，引入了综合型、趣味型、能力型、思考型、科研型等多种类型的作业内容。另外，除在课堂上讲解一些共性问题外，我们还积极的组织对作业内容课外讨论，并邀请研究工作者针对某些专题的讲座和讨论。

在考试制度方面，改革了“一次定论”的考核制度，考试以学生完成日常作业和实验环节为必要条件，期末考试采用笔试方式。成绩评定由三部分组成：期末笔试占总成绩的70%；平时作业占总成绩的10%；实验占总成绩的20%。另外，本课程还引入了免试制度，即如果能够提出一个具有较大意义的创新时，学生可以免试，直接取得优秀的成绩，以鼓励学生对课程内容的积极探索。
关于我们 | 版权声明 | 汇款方式 | 会员注册 | 招聘信息 高等学校教学资源网 CopyRight©2004 版权所有
  京ICP证070553号   京ICP备10040123号-8   京公网安备: 1101081957