程序设计与数据结构.docx

《程序设计与数据结构.docx》由会员分享，可在线阅读，更多相关《程序设计与数据结构.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、总学时 学时，讲课 学时。课时安排学环节教学时数课程内容讲课课论 课上机计第一部份：语言程序设计-计算机与程序设计概述二程序基础三基本程序结构四数组与字符串五函数与模块化编程六结构体与共用体七动态数据结构（指针）八文件处理第二部份：数据结构一绪论二线性表三栈和队列四串五数组和广义表六树七图八查找九排序.实践环节：独立实验课程：程序语言设计实验（第 学期）实践内容：软件基础训练（短 学期）教学方法和建议程序设计和数据结构是计算机专业的基础课，注重理论教学更注重上机实践。教学过程 中应加强应用举例和作业讲评环节，使学生切实掌握基本的程序设计技术。五、考核方式平时作业笔试闭卷。各教学环节占总分的比例

2、第一部份：语言程序设计：平时作业：，期末笔试：第二部份：数据结构：平时作业占 ，期末考试成绩占六、推荐教材与参考资料教材乔林，计算机程序设计基础，北京：高等教育出版社，第版， 年 月严蔚敏、吴伟民编著数据结构 语言版，北京：清华大学出版社， 。严蔚敏、吴伟民、米宁编著数据结构题集 语言版，北京：清华大学出版社,参考资料万波等语言详解，北京：人民邮电出版社，。谭浩强著程序设计（第三版），北京：清华大学出版社，。张铭等编著 数据结构与算法，北京：高等教育出版社，。著（数据结构算法与应用）北京：机械工业出版社，。著（）（数据结构与算法一 版第二版），北京：清华大学出版社，。著，数据结构 语言描述一一

3、应用标准模版库（第 版），陈君译，北京：清华大学出版社，著,构与算法分析语言描述（第 版），冯舜玺译，北京：机械工业出版社,论课程建立对计算机的基本认识，了解软件的构成及分类，了解程序的运行原理和过程； 由 本课程介绍程序设计基础和软件开辟方法， 语言的基本语法和语义(包括变量、简单数 据类型、表达式和语句、输入和输出基础、顺序、条件和循环控制结构、函数定义、函数 调用和参数传递等关于程序设计的基本要素)，基本数据结构和算法，使用 语言进行 程序设计的方法以及使用程序解决问题的方法。与本课程关联的有相同学期开设的“程序语言设计实验”独立实验课，此外，为增强软 件开辟能力，在短二期设置相应的能力

4、训练实践课程“软件基础训练”。本课程为计算机学科的多个后续课程打下基础，如计算机网络、课外创新实践等。三、课程内容及基本要求第一部份：语言程序设计(一)计算机与程序设计概述(学时)主要内容：()计算机软件分类()计算机语言()程序执行的原理和过程()软件开辟方法基本要求了解计算机软件的分类以及计算机语言的分类；理解程序执行的原理和过程；了解基本 的软件开辟方法和应用软件的开辟方法。重点、难点重点：程序执行的原理和过程由于在计算机科学与编程导论课程中已经讲授了基本的计算机概念和软件的基础知 识，因此这里仅需进行内容回顾，并重点讨论程序执行原理和过程，介绍软件开辟方法。二 程序基础(学时主要内容：

5、()字符集、保留字集、标识符、算符等基本词法元素()变量声明和数据类型()可执行语句()键盘输入和屏幕输出等输入 输出基础()运算符与表达式() 预处理：、() 程序的普通形式基本要求记住 所用的字符集和保留字，了解 的基本数据类型； 明确常量、变量与字面量的含 义；掌握运算符的使用、表达式的含义和计算过程；掌握用标准函数实现输入和输出的基本 方法；掌握各类可执行语句的使用；了解 编译器的基本工作过程和各类预编译语句的使用； 能熟练运用上述基本元素进行简单的程序设计。重点、难点重点： 基本数据类型、运算符与表达式、基本的输入和输出处理、语句由于这是第一门程序设计课程，因此需要让学生深入理解变量

6、、表达式的内涵，掌握 程序的普通形式，并建立良好的编程风格。三 基本程序控制结构(学时主要内容：()控制结构()条件语句： 语句和 语句；嵌套 语句和多选项决策()循环语句：语句；语句嵌套循环基本要求了解什么是控制结构；掌握基本的程序控制结构(包括顺序结构、条件选择和循环结构) 及其执行流程；掌握不同程序控制结构的 语言实现；掌握嵌套的程序控制结构及其执行流 程；熟练使用语言控制结构设计程序。重点、难点重点：条件结构和循环结构的基本形式及执行流程难点：语句的匹配原则；循环语句的结束条件和执行次数；复合控制结构的流程。可以采用流程图来阐述不同控制结构的执行流程，便于学生理解。这部份内容需特殊加强

7、应用举例。四数组与字符串(学时主要内容：()声明和引用数组及数组下标()多维数组()字符数组与字符串()字符串库函数的使用基本要求掌握声明数组和引用数组的语法；掌握数组初始化的方法；掌握 语言数组下标的特殊 性；了解多维数组的声明及引用语法；掌握字符数组与字符串的区别；掌握初始化字符串变 量的方法；掌握常用的字符串操作库函数。重点、难点重点：声明数组和引用数组的语法；字符串的特殊性；字符串操作库函数的使用。难点：数组的存储和访问方法；语言数组下标的特殊性；字符串与字符数组的区别。五函数与模块化编程(学时主要内容：()函数的基本概念()函数的定义、声明和调用()参数传递和变量的作用域()递归()

8、标准函数或者预定义函数()模块化编程基本要求了解函数是过程抽象的基本形式，掌握函数的定义、声明和调用方法；了解函数、变量 等先声明后引用的普通原则；理解参数传递的内涵，了解函数操作的对象的不同形式、作用 域和使用方法；了解递归函数的运行过程，掌握递归函数的编写方法；掌握标准函数或者预 定 义函数的使用方法；理解模块化编程的内涵并掌握自顶向下设计的方法。重点、难点重点：函数的定义、声明和调用，参数传递，变量(数据)的作用域，递归函数的运行 过程和递归函数的编写，标准函数的使用；模块化编程的意义难点：参数传递，特别是数组作为函数参数；变量的作用域；递归函数的运行过程和递 归函数的编写。这部份内容需

9、特殊加强应用举例。六结构体与共用体(联合)(学时)主要内容：()结构体的声明及数据程远引用()共用体的声明与使用()共用体与结构体的区别基本要求掌握结构类型的定义和使用，了解联合数据类型的定义和使用；理解共用体与结构体的 区别。重点、难点重点：结构类型的定义和应用。这部份内容需特殊加强应用举例。七 动态数据结构(指针)(学时主要内容：()指针的概念及其含义以及如何使用指针引用变量()指针运算的意义及其使用()动态内存分配()使用指针实现链表、二叉树等动态数据结构基本要求理解指针其实是一个内存地址；掌握如何通过指针引用变量；理解只恨运算的意义及合 法性；掌握分配内存和回收内存的方法；了解如何使用

10、指针实现链表等动态数据结构。重点、难点重点：指针的概念及其含义了；使用指针变量的方法；指针运算的含义。难点：指针是 语言中初学者比较难以理解和掌握的一个问题，需要从指针的本质来阐 明它的实际意义及使用方法；使用指针实现动态数据结构是一种高效的方法，但也是初学者 容易犯错误的地方，需要特殊加强引用举例。八文件处理(学时)主要内容：()文件指针变量()文件的打开与关闭、打开文件的不同方式()文件读写和定位基本要求了解磁盘文件的不同组织形式；掌握打开文件的不同方式和关闭文件的方法；掌握读写 文件和在文件中定位的方法。重点、难点重点：文件的打开方式；文件读写和定位。第二部份：数据结构一数据结构的基本概

11、念(学时)主要内容：数据结构的概念，包括数据、数据元素、结构；逻辑结构和物理结构的概念和区别；抽象数据类型的概念、表示和实现；算法的概念、特性、设计要求； 算法性能评价方法，大 记法。. 基本要求应了解数据结构的基本含义、课程所研究的主要内容，了解四类基本结构：集合、 线性结构、树形结构、图状结构。掌握逻辑结构和物理结构的定义与区别了解两类存 储结构：顺序存储结构和链式存储结构。掌握抽象数据类型 的定义、表示和实现。掌握算法的定义、特性、设计要求和性能度量方法，包括时间复杂度和空间复杂度，能用大记法表示时间、空间复杂度。.重点与难点重点：数据结构的定义，四类基本结构；逻辑结构和物理结构的区别，

12、两类存储结构； 的定义；算法的性能度量方法。难点：逻辑结构、物理结构的区别；时间复杂度的定义与大 表示法。（二）线性表（学时）主要内容：线性表的概念与基本运算；线性表的顺序表示和实现；线性表的链式表示和实现，包括单链表、静态链表、循环链表、双向链表；线性表的应用： 一元多项式的表示与相加。基本要求掌握线性表的概念和基本运算，能用基本运算实现一些应用。熟练掌握顺序表的表 示，理解随机存取的含义，掌握顺序表的基本算法，包括插入、删除、查找。熟练掌握 链式存储的表示和实现，理解头指针、头结点的含义，掌握单链表、静态链表、循环链 表、双向链表的概念和基本运算实现，包括插入和删除。重点与难点重点：线性表

13、的概念；顺序表的表示、特点，插入、删除操作的实现与复杂度分析；链 式表示的特点，各种链表的概念，插入、删除操作的实现。难点：顺序表与链表的特性对照与选取，插入、删除操作的实现。（三）栈和队列（学时）主要内容：栈的概念、基本运算；栈的两种实现：顺序栈和链栈，入栈与出栈操作的实现；栈的应用，特殊是栈与函数调用、递归的关系；队列的概念、基本运算；队列的两种实现：链队列和循环队列，入队列和出队列操作的实现。基本要求掌握栈的基本概念：后进先出的特点、栈底、栈顶。熟练掌握顺序栈和链栈的表示 方法，入栈、出栈操作的实现。了解栈的几种应用，如数制转换、括号匹配的检验、行 编辑程序、迷宫求解、表达式求值。理解栈

14、在函数调用与递归实现中的重要作用，会写 递归程序。掌握队列的概念：先进先出的特点、队头、队尾。熟练掌握链队列、循环队 列的表示方法，入队列、出队列操作的实现，理解循环队列设计的初衷。重点与难点 重点：栈的概念与特点；顺序栈和链栈的表示，入栈和出栈的实现；栈与函数调用和递 归实现的关系；队列的概念与特点；链队列与循环队列的表示，入队列、出队列的实现。 难点：栈与函数调用、递归的关系；循环队列的设计初衷与基本运算实现。（四）串（学时）主要内容：串的概念与基本运算；串的三种表示与实现：定长顺序串、堆分配顺序串、块链串；串的模式匹配算法：算法与 算法。基本要求掌握串的基本概念：子串、主串、位置；掌握串

15、的基本运算。掌握三种表示方法： 定长顺序存储、堆分配顺序存储、块链存储。掌握朴素的模式匹配算法 算法和改进 的模式匹配算法 算法，理解改进的思路。重点与难点重点：串的概念，与线性表的区别；基本运算；三种表示方法；算法； 算法。难点： 算法。（五）数组和广义表（学时）主要内容：数组的定义；数组的顺序表示和实现；矩阵的压缩存储；广义表基本要求掌握数组的定义，理解数组与线性表的区别。熟练掌握数组的顺序表示和实现，特 别是高维数组的两种顺序存储方法：行序为主序与列序为主序。掌握特殊矩阵的压缩存 储，包括对称矩阵、三角矩阵和对角矩阵。掌握稀疏矩阵的压缩存储方法。掌握广义表 的定义和基本运算，了解广义表的

16、存储结构。重点与难点重点：数组的定义和存储；特殊矩阵的压缩存储；广义表的定义与运算。难点：高维数组的顺序存储方法；特殊矩阵的压缩存储方法。（六）树和二叉树（学时）主要内容：树的定义与基本术语；二叉树的定义、基本性质、存储结构;二叉树的遍历与线索化；树与森林的存储、遍历，及与二叉树的转化；树的应用：树与等价类；树的应用：最优二叉树（树）。基本要求掌握树的定义与基本术语：结点、度、叶子、孩子、双亲、兄弟、层次、深度；掌 握二叉树的定义和基本性质，掌握基本性质的证明方法；掌握二叉树的顺序存储和链式 存储两种实现方法，理解两者的合用场合；熟练掌握二叉树的遍历方法：先序、中序和 后序遍历；掌握二叉树的线

17、索化，理解线索化的作用和意义；掌握树的存储方法：双亲 表示法、孩子表示法、孩子兄弟表示法；掌握树、森林与二叉树的转化方法；掌握树与 森林的遍历方法；掌握用树实现等价类的方法；掌握树的构造方法与用途。重点与难点重点：二叉树的定义、性质与存储结构；二叉树的遍历；树与森林的存储与遍历。难点：二叉树遍历的非递归算法实现；由先序、中序遍历序列确定二叉树与森林的方法； 树的构造方法。（七）图（学时）主要内容：图的定义和术语；图的存储结构：邻接矩阵、邻接表、十字链表、邻接多重表；图的遍历：深度优先搜索和广度优先搜索；图的连通分量与最小生成树；拓扑排序与关键路径算法；最短路径算法：算法和 算法。基本要求掌握图

18、的定义与术语：顶点、边、弧、有向图、无向图、邻接点、简单路径、回路、 连通图、连通分量、生成树；掌握图的存储结构：邻接矩阵、邻接表、十字链表、邻接 多重表；熟练掌握图的深度优先搜索和广度优先搜索遍历方法；掌握最小生成树的构造 方法： 算法和 算法；掌握拓扑排序算法和关键路径的求法；掌握单源最短 路径算法算法和任两点间的最短路径算法算法。重点与难点重点：图的各种存储结构；图的遍历算法；最小生成树构造算法；拓扑排序算法；关键 路径求法；最短路径算法。难点：邻接矩阵和邻接表的定义与特性；最短路径算法。（八）查找（学时）主要内容：查找的概念；静态查找表：顺序查找、折半查找、索引查找；动态查找表：二叉排

19、序树、平衡二叉树、树；哈希表基本要求掌握查找的基本概念：关键字、查找、平均查找长度；掌握顺序查找、折半查找与 索引查找的概念、实现与性能分析方法；掌握二叉排序树的概念、实现与性能分析方法； 理解平衡二叉树的设计思路；了解 树的定义与实现方法；掌握哈希表的设计思路、哈 希函数的构造方法、处理冲突的方法和性能分析方法。重点与难点重点：顺序查找、折半查找、二叉排序树的定义、实现和性能分析；哈希表的定义、哈 希函数构造方法、处理冲突方法。难点：平衡二叉树的实现； 树的实现；各种查找方法的性能分析。（九）排序（学时）主要内容：排序的基本概念；插入排序：直接插入、折半插入、路插入、希尔排序；交换排序：起泡

20、排序、快速排序；选择排序：简单选择排序、树形选择排序与堆排序；归并排序与基数排序；各种内部排序算法的比较；外部排序基本要求掌握排序的基本概念：稳定与不稳定、内部与外部排序；掌握各种插入排序算法的 思路、实现与性能评价：直接插入、折半插入、 路插入、希尔排序；掌握起泡排序、 快速排序的思路、实现与性能评价；掌握简单选择排序、堆排序的思路、实现与性能评 价；掌握归并排序、基数排序的思路、实现与性能评价；掌握各种内部排序算法的性能 比较与选取方法；了解外部排序的思路与基本方法。重点与难点重点：直接插入排序、希尔排序；起泡排序、快速排序；简单选择排序、堆排序；归并 排序；基数排序；各种内部排序算法的性能分析与比较。难点：希尔排序；快速排序；堆排序；各种内部排序算法的性能分析。四、教学安排及方式