《《数据结构》课程教学大纲(三套)》由会员分享，可在线阅读，更多相关《《数据结构》课程教学大纲(三套)（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程教学大纲（三套）数据结构课程教学大纲（三套）数据结构数据结构课程教学大纲（课程教学大纲（36/36 课时）课时）一、课程的性质和任务一、课程的性质和任务数据结构是计算机及应用专业中一门重要的专业基础课程，在计算机软件的各个领域中均会使用到数据结构的有关知识。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打开厚实的基础。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：在基础方面，要求学员掌握常用数据结构的基本概念及其不同的实现方法；在技能
2、方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。二、课程的基本要求二、课程的基本要求本课程的教学基本要求如下：本课程要求理论必须与上机实践操作相结合，多做题和调试算法，实现算法。实践项目只利用课堂时间是不够的，必须提前布置给学生。通过本课程的学习与实践，学生应达到：1、掌握数据结构的基本概念和基本理论；2、熟练掌握顺序表、链表、队列、栈、树以及二叉树、图等基本数据结构的设计和分析；3、熟练地掌握常用算法（递归、遍历、查找、排序）的知识；4、能对所求解的问题进行分析，抽象出
3、逻辑结构，选择合适的存储结构，定义所需的运算，设计相应的算法；5、对算法进行分析和评价。三、教学内容三、教学内容（一）理论教学（一）理论教学序序 号号单单 元元主要内容主要内容教学要求教学要求学学 时时1绪论理论 教学数据结构的基本概念（数据、数据元素、数 据类型和数据结构、逻辑结构、存储结构） 2算法描述和算法评价了解数据的逻辑结构和物 理结构，算法的基本概念 ；掌握算法复杂度的概念 及分析方法 22线性 表理论 教学1线性表的概念及运算 2顺序表及基本运算 3单链表及基本运算 4循环链表和双链表 5顺序存储结构与链式存储结构的比较熟练掌握：线性表的基本 运算；单链表和循环链表 的结构特点、
4、基本运算并 能设计简单算法43栈和 队列理论 教学1栈和队列的概念及运算； 2栈和队列的顺序、链接存储 3栈和队列的插入、删除算法及其应用熟练掌握栈和队列的特征、 基本运算并能设计简单算 法44串理论 教学1串及其运算、串的存储结构； 熟练掌握串的逻辑结构、 存储结构25树理论 教学树的定义和表示； 二叉树的定义、重要性质、存储结构和运算；二叉树的遍历、线索、排序； 二叉树与树和森林的转换； 树的应用： 二叉排序树、哈夫曼树及其应用熟练掌握： 1.树形结构的基本概念和 术语； .二叉树定义和存储结构；.二叉树的遍历次序及算 法66图理论 教学图的定义和术语 图的存储结构 图的建立和遍历 图的生
5、成树 最短路径 图的遍历、图的生成算法熟练掌握图的存储结构和 遍历算法，以及生成最小 生成树的方法6序序 号号单单 元元主要内容主要内容教学要求教学要求学学 时时7查找理论 教学1查找的基本概念 2顺序查找、 3索引查找 4树表查找(二叉排序树定义及查找，二叉 平衡树的定义) 5散列查找熟练掌握顺序查找、二分 查找、分块查找、二叉排 序树查找的基本思想和算 法；散列法基本思想、散 列函数的常用构造方法及 解决冲突方法68排序理论 教学1排序的基本概念 2插入排序（直接插入排序、折半插入排序、 希尔排序） 3交换排序（冒泡排序、快速排序） 4.选择排序（简单选择排序、*堆排序） 5各种排序方法比
6、较熟悉各种内部排序方法的 基本思想和特点；各种排 序方法的优缺点、时、空 性能和适用场合6理论教学36 学 时 合 计 72 实践教学36（二）实践环节（二）实践环节序序 号号单单 元元主要内容主要内容教学要求教学要求学学 时时1绪论实践项目分析算法的时间复杂度，并用程序验证。例如：求下列算法段的语句频度for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;掌握分析算法段的语句频度及时间复杂度，并用程序加以验证22线性表实践项目设计一个通信录信息管理程序, 程序要求用结构体定义记录，用单链表存放数据，并具有如下功能：打开文件（读入文件中记录到链表） ；添加、插入
7、、删除、查找一个记录；显示所有记录；存盘（保存链表中记录到文件）和退出。利用单链表的各种运算的算法来解决实际问题；要求学生自己查阅 C 语言书本，调试完善实践项目。43栈和队列实践项目1、栈和队列的顺序存储结构的所有操作算法的实现；2、栈和队列的链式存储结构的所有操作算法的实现；掌握栈和队列的实际应用44串实践项目串中字符及子串的查找和匹配掌握串的实际应用2序序 号号单单 元元主要内容主要内容教学要求教学要求学学 时时5树实践项目用模块化的方法设计一个程序进行二叉树的建立和遍历。主菜单中包括如下功能选项：1.建立二叉树 2.先序非递归遍历 3.先序递归遍历 4.中序递归遍历 5.后序递归遍历，
8、求叶节点数6.退出主要掌握二叉树的几种遍历的递归算法，先序的非递归遍历算法66图实践项目用模块化的方法设计一个程序建立无向图的邻接表并遍历该图。主菜单中包括如下功能选项：1 建立无向图的邻接表 2 按深度优先遍历 3 按广度优先遍历 4 退出掌握图的生成和遍历算法67查找实践项目用模块化的方法编一程序测试顺序查找、折半查找、杂凑查找三种算法。其功能菜单如下：1 顺序查找 2 折半查找 3 杂凑查找 0 退出写出顺序查找、折半查找（二分查找）的算法并调试通过68排序实践项目用模块化的方法编一程序测试几种排序算法的运行时间。其功能菜单如下：1 选择排序 2 冒泡排序 3 希尔排序 4 快速排序0
9、退出写出几种插入排序算法、交换排序算法和简单选择排序算法并调试6理论教学36 学 时 合 计 72 实践教学36四、课时分配四、课时分配数据结构课程共 4 学分，课内 72 学时，其中理论课 36 学时，上机 36学时。五、大纲说明五、大纲说明本课程必须理论与上机实践操作相结合，并要教、学、练相结合，讲清基本概念，指出知识要点、重点和难点，并通过实例分析解决算法难点；要求学生认真预习、认真听课、认真思索、认真做实验，通过对算法的编程实现来提高学生的理解和动手能力。由于内容多、难度大，要特别注重精讲多练，实践项目一定要提前布置给学生，启发学生独立思考、调动学生的主观能动性，鼓励学生多提问题、共同
10、探讨和解决问题。重点：线性表的存储和运算；栈和队列的运算；二叉树的遍历和线索，哈夫曼树及应用，二叉排序树；图的生成树，最短路径；散列查找和树表查找；几种排序算法及排序过程。难点：链表的运算；后序遍历二叉树；线索二叉树；最短路径等。六、考核方式六、考核方式理论考核与实践考核相结合，理论考核（主要考基本概念、基本理论、基本算法, 闭卷考试）占 40；实践考核（主要是平时布置的实践项目）占40；平时（出勤、作业、课堂提问等）占 20%。七、参考教材七、参考教材教材：教材：数据结构(C 语言版) ， 邵增珍 杨品林 编著 ， 清华大学出版社，2012 年 9 月。参考教材参考教材: :1.数据结构-用
11、 C 语言描述 唐策善、李龙澍、黄刘生 高等教育出版社 1995 2.数据结构(C 语言篇)习题与解析 李春葆 清华大学出版社 2000 3.数据结构（C 语言版） 严蔚敏、吴伟民 清华大学出版社 1997数据结构数据结构 A课程教学大纲（课程教学大纲（56/16 课时）课时）Data Structure A课程代码：课程性质：专业基础理论课/必修适用专业：信息计算、信息安全开课学期：5总学时数：72总学分数：4.5编写年月： 修订年月： 执 笔：高学军、刘科峰、李小英一、课程的性质和目的一、课程的性质和目的数据结构是信息与计算科学专业的一门重要专业基础课程。当用计算机来解决实际问题时，就要涉
12、及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在信息与计算科学专业中具有举足轻重的作用。二、课程教学内容及学时分配二、课程教学内容及学时分配第 1 章 绪论 （4 学时）理解数据、数据元素和数据项的概念及其相互间的关系。理解数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现。掌握简单的算法分析方法。本章知识点为：数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和
13、实现方法；描述算法的类 C 语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。第 2 章 线性表 （10 学时，2 个学时实验上机）理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双向(循环)链表的结构特点和在其上施加的插入、删除等操作。掌握稀疏多项式在线性表的两种存储结构上的实现方法。本章知识点为：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构(顺序的和链式的) 上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。第 3 章 栈和队列
14、（6 学时，2 个学时实验上机）理解栈和队列的定义、特征及在其上所定义的基本运算。掌握在两种存储结构上对栈和队列所施加的基本运算的实现。熟练掌握循环队列和链队列的基本操作实现算法，尤其是队满和队空的描述方法。本章知识点为：抽象数据类型栈的定义；栈的表示和实现；栈的应用；抽象数据类型队列的定义；链队列；循环队列。第 4 章 串 （4 学时，2 个学时实验上机）熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。掌握串的堆存储结构以及在其上实现串操作的基本方法。本章知识点为：串的数据类型定义；串的三种存储表示：定长顺
15、序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；第 5 章 数组和广义表 （6 学时，2 个学时实验上机）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法。本章知识点为：数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构和广义表的操作。第 6 章 树和二叉树 （12 学时，2 个学时实验上机）深刻理解树的定义、性质
16、及其存储方法，熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树的三种遍历方法，并能写出该三种遍历的算法；会完成树、森林与二叉树间的相互转换；理解哈夫曼树的构造方法，并能对给定的数据集合构造出哈夫曼树。本章知识点为：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构、与二叉树的转换、遍历；树的多种应用。第 7 章 图 （12 学时，2 个学时实验上机）理解图的基本概念及术语，掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按 Prim 算法构造最小生成树；了解并掌握拓扑排序、关键路径、最短路径的算法思想。本章知识点为：图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接
