"程序设计与数据结构"教学大纲

课程名称:程序设计与数据结构英文名称:ProgramDesignandDataStructure学时:96学分:6课程类型:必修课程性质:专业基础课适用专业:自动化(交通信息工程及控制)先修课程:计算机科学与编程导论开课学期:第1、2学期开课院系:信息科学与技术学院一、课程的教学目标与任务本课程培养学生较熟练地掌握C语言程序设计的基本技能,掌握各种基本数据结构和算法.
通过本课程的学习,掌握C语言基础知识;掌握简单算法和数据结构的基本设计方法;掌握复杂数据结构(例如栈和队列以及链表)的含义并能简单应用,建立程序设计的思想,培养学生的问题解决能力和实际编程能力;了解并初步掌握当前软件行业公认的程序设计风格和编程实践.

学生应掌握各种基本数据结构的概念、实现方法及涉及的基本算法,并能用这些数据结构和算法解决相关的应用问题,为进一步学习相关学科打下坚实的基础.
通过本课程的学习.

重点是阐述程序设计思想和各种数据结构及其相关算法,培养学生分析问题和使用程序和数据结构解决问题的能力.

二、本课程与其它课程的联系和分工"计算机科学与编程导论"是本课程的先修课程.
具体分工是:由计算机科学与编程导论课程建立对计算机的基本认识,了解软件的构成及分类,了解程序的运行原理和过程;由本课程介绍程序设计基础和软件开发方法,C语言的基本语法和语义(包括变量、简单数据类型、表达式和语句、输入和输出基础、顺序、条件和循环控制结构、函数定义、函数调用和参数传递等关于程序设计的基本要素),基本数据结构和算法,使用C语言进行程序设计的方法以及使用程序解决问题的方法.

与本课程关联的有相同学期开设的"程序语言设计实验"独立实验课,此外,为增强软件开发能力,在短二期设置相应的能力训练实践课程"软件基础训练".

本课程为计算机学科的多个后续课程打下基础,如计算机网络、课外创新实践等.

三、课程内容及基本要求第一部分:C语言程序设计(一)计算机与程序设计概述(2学时)主要内容:(1)计算机软件分类(2)计算机语言(3)程序执行的原理和过程(4)软件开发方法1.
基本要求了解计算机软件的分类以及计算机语言的分类;理解程序执行的原理和过程;了解基本的软件开发方法和应用软件的开发方法.

2.
重点、难点重点:程序执行的原理和过程由于在《计算机科学与编程导论》课程中已经讲授了基本的计算机概念和软件的基础知识,因此这里仅需进行内容回顾,并重点讨论程序执行原理和过程,介绍软件开发方法.

(二)C程序基础(2学时)主要内容:(1)字符集、保留字集、标识符、算符等基本词法元素(2)变量声明和数据类型(3)可执行语句(4)键盘输入和屏幕输出等输入/输出基础(5)运算符与表达式(6)C预处理:include、define(7)C程序的一般形式1.
基本要求记住C所用的字符集和保留字,了解C的基本数据类型;明确常量、变量与字面量的含义;掌握运算符的使用、表达式的含义和计算过程;掌握用标准函数实现输入和输出的基本方法;掌握各类可执行语句的使用;了解C编译器的基本工作过程和各类预编译语句的使用;能熟练运用上述基本元素进行简单的C程序设计.

2.
重点、难点重点:基本数据类型、运算符与表达式、基本的输入和输出处理、语句由于这是第一门程序设计课程,因此需要让学生深入理解变量、表达式的内涵,掌握C程序的一般形式,并建立良好的编程风格.

(三)基本程序控制结构(8学时)主要内容:(1)控制结构(2)条件语句:if语句和switch语句;嵌套if语句和多选项决策(3)循环语句:for语句;do-while语句;嵌套循环1.
基本要求了解什么是控制结构;掌握基本的程序控制结构(包括顺序结构、条件选择和循环结构)及其执行流程;掌握不同程序控制结构的C语言实现;掌握嵌套的程序控制结构及其执行流程;熟练使用C语言控制结构设计程序.

2.
重点、难点重点:条件结构和循环结构的基本形式及执行流程难点:if语句的匹配原则;循环语句的结束条件和执行次数;复合控制结构的流程.
可以采用流程图来阐述不同控制结构的执行流程,便于学生理解.

这部分内容需特别加强应用举例.
(四)数组与字符串(6学时)主要内容:(1)声明和引用数组及数组下标(2)多维数组(3)字符数组与字符串(4)字符串库函数的使用1.
基本要求掌握声明数组和引用数组的语法;掌握数组初始化的方法;掌握C语言数组下标的特殊性;了解多维数组的声明及引用语法;掌握字符数组与字符串的区别;掌握初始化字符串变量的方法;掌握常用的字符串操作库函数.

2.
重点、难点重点:声明数组和引用数组的语法;字符串的特殊性;字符串操作库函数的使用.

难点:数组的存储和访问方法;C语言数组下标的特殊性;字符串与字符数组的区别.

(五)函数与模块化编程(10学时)主要内容:(1)函数的基本概念(2)函数的定义、声明和调用(3)参数传递和变量的作用域(4)递归(5)标准函数或预定义函数(6)模块化编程1.
基本要求了解函数是过程抽象的基本形式,掌握函数的定义、声明和调用方法;了解函数、变量等先声明后引用的一般原则;理解参数传递的内涵,了解函数操作的对象的不同形式、作用域和使用方法;了解递归函数的运行过程,掌握递归函数的编写方法;掌握标准函数或预定义函数的使用方法;理解模块化编程的内涵并掌握自顶向下设计的方法.

2.
重点、难点重点:函数的定义、声明和调用,参数传递,变量(数据)的作用域,递归函数的运行过程和递归函数的编写,标准函数的使用;模块化编程的意义难点:参数传递,尤其是数组作为函数参数;变量的作用域;递归函数的运行过程和递归函数的编写.

这部分内容需特别加强应用举例.
(六)结构体与共用体(联合)(6学时)主要内容:(1)结构体的声明及数据程远引用(2)共用体的声明与使用(3)共用体与结构体的区别1.
基本要求掌握结构类型的定义和使用,了解联合数据类型的定义和使用;理解共用体与结构体的区别.

2.
重点、难点重点:结构类型的定义和应用.
这部分内容需特别加强应用举例.
(七)动态数据结构(指针)(8学时)主要内容:(1)指针的概念及其含义以及如何使用指针引用变量(2)指针运算的意义及其使用(3)动态内存分配(4)使用指针实现链表、二叉树等动态数据结构1.
基本要求理解指针其实是一个内存地址;掌握如何通过指针引用变量;理解只恨运算的意义及合法性;掌握分配内存和回收内存的方法;了解如何使用指针实现链表等动态数据结构.

2.
重点、难点重点:指针的概念及其含义了;使用指针变量的方法;指针运算的含义.
难点:指针是C语言中初学者比较难以理解和掌握的一个问题,需要从指针的本质来阐明它的实际意义及使用方法;使用指针实现动态数据结构是一种高效的方法,但也是初学者容易犯错误的地方,需要特别加强引用举例.

(八)文件处理(6学时)主要内容:(1)文件指针变量(2)文件的打开与关闭、打开文件的不同方式(3)文件读写和定位1.
基本要求了解磁盘文件的不同组织形式;掌握打开文件的不同方式和关闭文件的方法;掌握读写文件和在文件中定位的方法.

2.
重点、难点重点:文件的打开方式;文件读写和定位.
第二部分:数据结构(一)数据结构的基本概念(2学时)主要内容:数据结构的概念,包括数据、数据元素、结构;逻辑结构和物理结构的概念和区别;抽象数据类型的概念、表示和实现;算法的概念、特性、设计要求;算法性能评价方法,大O记法.
基本要求应了解数据结构的基本含义、课程所研究的主要内容,了解四类基本结构:集合、线性结构、树形结构、图状结构.
掌握逻辑结构和物理结构的定义与区别,了解两类存储结构:顺序存储结构和链式存储结构.
掌握抽象数据类型ADT的定义、表示和实现.
掌握算法的定义、特性、设计要求和性能度量方法,包括时间复杂度和空间复杂度,能用大O记法表示时间、空间复杂度.

重点与难点重点:数据结构的定义,四类基本结构;逻辑结构和物理结构的区别,两类存储结构;ADT的定义;算法的性能度量方法.

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

重点与难点重点:线性表的概念;顺序表的表示、特点,插入、删除操作的实现与复杂度分析;链式表示的特点,各种链表的概念,插入、删除操作的实现.

难点:顺序表与链表的特性对比与选取,插入、删除操作的实现.
(三)栈和队列(4学时)主要内容:栈的概念、基本运算;栈的两种实现:顺序栈和链栈,入栈与出栈操作的实现;栈的应用,特别是栈与函数调用、递归的关系;队列的概念、基本运算;队列的两种实现:链队列和循环队列,入队列和出队列操作的实现.
基本要求掌握栈的基本概念:后进先出的特点、栈底、栈顶.
熟练掌握顺序栈和链栈的表示方法,入栈、出栈操作的实现.
了解栈的几种应用,如数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值.
理解栈在函数调用与递归实现中的重要作用,会写递归程序.
掌握队列的概念:先进先出的特点、队头、队尾.
熟练掌握链队列、循环队列的表示方法,入队列、出队列操作的实现,理解循环队列设计的初衷.

重点与难点重点:栈的概念与特点;顺序栈和链栈的表示,入栈和出栈的实现;栈与函数调用和递归实现的关系;队列的概念与特点;链队列与循环队列的表示,入队列、出队列的实现.

难点:栈与函数调用、递归的关系;循环队列的设计初衷与基本运算实现.

(四)串(2学时)主要内容:串的概念与基本运算;串的三种表示与实现:定长顺序串、堆分配顺序串、块链串;串的模式匹配算法:BF算法与KMP算法.
基本要求掌握串的基本概念:子串、主串、位置;掌握串的基本运算.
掌握三种表示方法:定长顺序存储、堆分配顺序存储、块链存储.
掌握朴素的模式匹配算法BF算法和改进的模式匹配算法KMP算法,理解改进的思路.

重点与难点重点:串的概念,与线性表的区别;基本运算;三种表示方法;BF算法;KMP算法.

难点:KMP算法.
(五)数组和广义表(4学时)主要内容:数组的定义;数组的顺序表示和实现;矩阵的压缩存储;广义表基本要求掌握数组的定义,理解数组与线性表的区别.
熟练掌握数组的顺序表示和实现,特别是高维数组的两种顺序存储方法:行序为主序与列序为主序.
掌握特殊矩阵的压缩存储,包括对称矩阵、三角矩阵和对角矩阵.
掌握稀疏矩阵的压缩存储方法.
掌握广义表的定义和基本运算,了解广义表的存储结构.

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

重点与难点重点:二叉树的定义、性质与存储结构;二叉树的遍历;树与森林的存储与遍历.

难点:二叉树遍历的非递归算法实现;由先序、中序遍历序列确定二叉树与森林的方法;Huffman树的构造方法.

(七)图(10学时)主要内容:图的定义和术语;图的存储结构:邻接矩阵、邻接表、十字链表、邻接多重表;图的遍历:深度优先搜索和广度优先搜索;图的连通分量与最小生成树;拓扑排序与关键路径算法;最短路径算法:Dijkstra算法和Flody算法.
基本要求掌握图的定义与术语:顶点、边、弧、有向图、无向图、邻接点、简单路径、回路、连通图、连通分量、生成树;掌握图的存储结构:邻接矩阵、邻接表、十字链表、邻接多重表;熟练掌握图的深度优先搜索和广度优先搜索遍历方法;掌握最小生成树的构造方法:Prim算法和Kruskal算法;掌握拓扑排序算法和关键路径的求法;掌握单源最短路径算法Dijkstra算法和任两点间的最短路径算法Flody算法.

重点与难点重点:图的各种存储结构;图的遍历算法;最小生成树构造算法;拓扑排序算法;关键路径求法;最短路径算法.

难点:邻接矩阵和邻接表的定义与特性;最短路径算法.
(八)查找(6学时)主要内容:查找的概念;静态查找表:顺序查找、折半查找、索引查找;动态查找表:二叉排序树、平衡二叉树、B树;哈希表基本要求掌握查找的基本概念:关键字、查找、平均查找长度;掌握顺序查找、折半查找与索引查找的概念、实现与性能分析方法;掌握二叉排序树的概念、实现与性能分析方法;理解平衡二叉树的设计思路;了解B-树的定义与实现方法;掌握哈希表的设计思路、哈希函数的构造方法、处理冲突的方法和性能分析方法.

重点与难点重点:顺序查找、折半查找、二叉排序树的定义、实现和性能分析;哈希表的定义、哈希函数构造方法、处理冲突方法.

难点:平衡二叉树的实现;B-树的实现;各种查找方法的性能分析.
(九)排序(6学时)主要内容:排序的基本概念;插入排序:直接插入、折半插入、2-路插入、希尔排序;交换排序:起泡排序、快速排序;选择排序:简单选择排序、树形选择排序与堆排序;归并排序与基数排序;各种内部排序算法的比较;外部排序基本要求掌握排序的基本概念:稳定与不稳定、内部与外部排序;掌握各种插入排序算法的思路、实现与性能评价:直接插入、折半插入、2-路插入、希尔排序;掌握起泡排序、快速排序的思路、实现与性能评价;掌握简单选择排序、堆排序的思路、实现与性能评价;掌握归并排序、基数排序的思路、实现与性能评价;掌握各种内部排序算法的性能比较与选取方法;了解外部排序的思路与基本方法.

重点与难点重点:直接插入排序、希尔排序;起泡排序、快速排序;简单选择排序、堆排序;归并排序;基数排序;各种内部排序算法的性能分析与比较.

难点:希尔排序;快速排序;堆排序;各种内部排序算法的性能分析.
四、教学安排及方式总学时96学时,讲课96学时.
1.
课时安排教学环节教学时数课程内容讲课习题课讨论课上机参观或看录像小计第一部分:C语言程序设计(一)计算机与程序设计概述22(二)C程序基础222(三)基本程序结构828(四)数组与字符串646(五)函数与模块化编程10610(六)结构体与共用体626(七)动态数据结构(指针)848(八)文件处理646第二部分:数据结构(一)绪论22(二)线性表66(三)栈和队列44(四)串22(五)数组和广义表44(六)树88(七)图1010(八)查找66(九)排序662.
实践环节:独立实验课程:《程序语言设计实验》(第1学期)实践内容:《软件基础训练》(短I学期)3.
教学方法和建议程序设计和数据结构是计算机专业的基础课,注重理论教学更注重上机实践.
教学过程中应加强应用举例和作业讲评环节,使学生切实掌握基本的程序设计技术.

五、考核方式平时作业+笔试(闭卷).
各教学环节占总分的比例:第一部分:C语言程序设计:平时作业:20%,期末笔试:80%;第二部分:数据结构:平时作业占20%,期末考试成绩占80%.
六、推荐教材与参考资料教材(1)乔林,《计算机程序设计基础》,北京:高等教育出版社,第2版,2008年1月(2)严蔚敏、吴伟民编著《数据结构(C语言版)》,北京:清华大学出版社,2003.

(3)严蔚敏、吴伟民、米宁编著《数据结构题集(C语言版)》,北京:清华大学出版社,2003参考资料(1)万波等《C语言详解》,北京:人民邮电出版社,2007.
(2)谭浩强著《C程序设计》(第三版),北京:清华大学出版社,2005.
(3)张铭等编著《数据结构与算法》,北京:高等教育出版社,2008.
(4)SartajSahni著《DataStructures,Algorithms,andApplicationinC++》(数据结构算法与应用)北京:机械工业出版社,2003.
(5)AdamDrozdek著《DataStructuresandAlgorithmsinC++》(SecondEdition)(数据结构与算法-C++版第二版),北京:清华大学出版社,2003.
(6)WilliamFord,WilliamTopp著,DataStructureswithC++UsingSTL,数据结构C++语言描述——应用标准模版库(STL)(第2版),陈君译,北京:清华大学出版社,2003.

(7)MarkAllenWeiss著,DataStructuresandAlgorithmAnalysisinC,数据结构与算法分析——C语言描述(第2版),冯舜玺译,北京:机械工业出版社,2004.