2017-2018   数据结构D  

 

            授课教师:周菁                                  课程代号:111036

 

            办公地点:48号楼A907                           上课时间与地点:1-8周周一   13:30-15:10 48号楼A705     
                                                                                                                                                                1-16
周周四     10:10-12:00  48号楼A705

                                                                                                                       上机时间与地点:1-16周周五  13:30-15:10 48号楼A101     
                                                                                                                                                               

 

                    电子邮件: zhoujing@cuc.edu.cn                      

 

 

 

. 课程简介

 用计算机解决任何问题都需要进行数据表示和数据处理,而数据表示和数据处理正是《数据结构》要研究的内容。《数据结构》是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据,正确地设计算法以及对算法的分析和评价。通过本课程的学习,使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,培养基本的、良好的程序设计技能,编制高效可靠的程序,为学习操作系统、编译原理和数据库等课程奠定基础。

    二、课程教学目的和要求                                                                                              

 《数据结构》是一门专业技术基础课。目的就是要培养他们的数据抽象能力,学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据
 
选择适当的逻辑结构、存储结构及实现应用的相应算法,并掌握分析算法的时间和空间复杂度的技术。

    三、教学内容与学时分配 (总学时:80

   第一章:绪论(6时) (课件下载)

     基本知识点:熟悉各名词、术语的含义,掌握基本概念,特别是数据的逻辑结构和存储结构之间的关系;了解抽象数据类型的定义、表示和实现方
   
法;熟悉类
C语言的书写规范,特别要注意值调用和引用调用的区别,输入、输出的方式以及错误处理方式;理解算法五个要素的确切含义;掌握计算语
   
句频度和估算算法时间复杂度的方法。

     重点:数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系;算法的时间复杂度分析。

     难点:分析算法的时间复杂度。

   第二章:线性表(14学时,包含上机实验,下同课件下载

     基本知识点:线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法;在线性表的两类存储结构(顺序存储和链式存储)上实现基
    
本操作;一元多项式的抽象数据类型定义、表示及加法的实现。

     重点:线性表的定义和特点,线性表的存储结构;顺序表和链表的组织方法和算法设计。

     难点:单链表和双链表的各种算法设计。

   第三章:栈和队列(10学时) (课件下载)

     基本知识点:栈和队列的结构特性;在两种存储结构上如何实现栈和队列的基本操作和栈和队列在程序设计中的应用以及如何利用堆栈去模拟递归
    
程序的运行。

     重点: 栈和队列的特点,顺序栈和链栈上基本运算的实现算法;顺序队列、循环队列和链队列上基本运算算法。

     难点:灵活运用栈和队列设计解决应用问题的算法。

   第五章:数组(6学时)课件下载

     基本知识点:数组的类型定义和表示方法;特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。

     重点: 无。

     难点:无。

   第六章:树和二叉树(14学时)课件下载

     基本知识点:二叉树的定义、性质和存储结构;二叉树的遍历和线索化以及遍历算法的各种描述形式;树和森林的定义、存储结构、树和森林与二
   
叉树的转换、遍历;树的多种应用。本章是该课程的重点内容之一。

     重点: 二叉树的性质、二叉树的各种遍历方法及它们所确定的序列之间的关系、二叉树的线索化方法、构造赫夫曼树。

     难点: 二叉树的各种算法,特别是递归算法的设计。

   第七章:图(12学时)课件下载

     基本知识点:图的定义和术语;图的四种存储结构:数组表示法、邻接表、十字链表和邻接多重表;图的两种遍历策略:深度优先搜索和广度优先
   
搜索;图的连通性:连通分量和最小生成树;拓扑排序和关键路径;一类求最短路径问题的解法。

     重点: 图的各种存储结构(数组表示法和邻接矩阵表示法)和遍历算法设计,构造最小生成树,生成最短路径,生成图的关键路径和拓扑排序的应
   
用。

     难点:图的遍历算法和图的各种相关复杂算法的设计。

   第九章:查找(10学时) (课件下载)

     基本知识点:讨论查找表(包括静态查找表和动态查找表)的各种实现方法:顺序表、有序表和哈希表;二叉排序树、平衡二叉树的定义、性质及
其应用;关于衡量查找表的主要操作——查找的查找效率的平均查找长度的讨论。

     重点: 各种顺序表的查找算法和性能分析,构造哈希表、冲突处理和性能分析。

     难点:各种查找算法设计和性能分析。

   第十章:排序(8学时) (课件下载)

     基本知识点:讨论比较各种内部排序方法,插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时
   
间复杂度分析。在每类排序方法中,从简单方法入手,重点讨论性能先进的高效方法(如,插入排序类中的希尔排序、交换排序类中的快速排序、选择
   
排序类中的堆排序等)。

     重点:各种排序算法的性能特点,各种排序算法的比较和选择。

     难点:复杂排序算法的设计。

  总之,要求学生掌握基本概念、重要数据结构、基本算法,掌握各种数据结构的逻辑结构、存储结构和实现算法。根据当前计算机的应用发展举例
 
说明数据结构的描述及应用的实现算法。

 四、建议教材

      严蔚敏,吴伟民编著.《数据结构》(C语言版).清华大学出版社.

 五、参考资料

      [1] 李春葆, 尹为民, 李蓉蓉等编著. 《数据结构教程(3)学习指导》. 清华大学出版社.

[2] 许卓群,杨冬青,唐世渭,张铭编著.《数据结构与算法》. 高等教育出版社.

[3] 高一凡编著.《数据结构算法实现与解析》. 西安电子科技大学出版社.

[4] 汪杰编著.《数据结构经典算法实现与习题解答》. 人民邮电出版社 

     六、考核方式

        平时成绩(30%),包括

·        课堂与实验课出勤

·        作业

期末考试(70%

   七、作业

      关于作业的要求会定期公布在本课程网页上,请同学们在每次课后查看有关信息。完成作业的提交时间(如无特殊说明则一般)为作业布置后一周
     
的《数据结构》课上,例如作业是
2017911 布置的,则该作业的提交时间为 2017918 (如果该日课程取消,则顺延一周),2日内迟
    
交作业将只计入
50%的成绩,超出2日的迟交作业将不记录该次成绩(没有例外)。

     要求:作业应该是每位同学独立分析和思考的结果,在完成过程中大家可以利用工具书以及互联网查阅所需要的信息,但作业本身是个人独创性的
工作,不得抄袭他人的成果或据为己有。如果确有必要提及他人的工作,应该专门注明或给予引用。任何抄袭或剽窃行为将导致该次作业不予计入总成绩。

 

序号

作业布置时间

要求

1

2017.9.14

第一章 绪论  作业题  参考答案

2

2017.9.15

 第二章 线性表 实验题(顺序表)   参考答案

3

 2017.9.22

  第二章 线性表 实验题1(链表1)  参考答案

              实验题2链表2  参考答案

4

 2017.9.25

    第二章 线性表   作业题  参考答案

5

  2017.9.29

    第三章 栈和队列  实验题(顺序栈) 参考答案

6

  2017.10.12

    第三章 栈和队列  作业题 参考答案

7

  2017.10.13

    第三章 栈和队列  实验题(队列)   参考答案

8

  2017.10.20

   第三章 栈和队列  实验题(栈和队列)  参考答案

9

                  2017.10.23 

第五章 数组 实验题1(串)  实验题2(数组) 

10

      2017.11.02

  第六章 树和二叉树 作业题  参考答案

11

 2017.11.03

   第六章 树和二叉树 实验题1 (后序遍历二叉树) 参考答案

12

                          2017.11.15

   第六章 树和二叉树 实验题 2 (中序遍历线索二叉树) 参考答案

13

                   2017.11.17

   第七章   (深度优先遍历) 实验题     参考答案

14

                  2017.11.23

   第七章 作业题  参考答案

15

                         2017.11.24

   第七章   (广度优先遍历) 实验题  参考答案

16

                          2017.12.01

  第九章  查找  (折半查找) 实验题  参考答案

17

                           2017.12.08

  第九章 查找 (二叉排序树) 实验题   参考答案

18

                           2017.12.14

  第十章 排序(二路插入排序)实验题   参考答案

19

                           2017.12.18

  第九章 查找 作业题   参考答案

20

2017.12.22

  第十章 排序(直接插入排序)实验题

 

 

七、通知

    有关课程变更的相关信息会公布在这里,请大家定期查看此处