《程序设计与数据结构教学大纲》由会员分享，可在线阅读，更多相关《程序设计与数据结构教学大纲（11页珍藏版）》请在金锄头文库上搜索。
1、“程序设计与数据结构”教学大纲课程名称：程序设计与数据结构 英文名称：Program Design and Data Structure 学 时：96 学 分：6课程类型：必修 课程性质：专业基础课适用专业：自动化（交通信息工程及控制） 先修课程：计算机科学与编程导论开课学期：第1、2学期 开课院系：信息科学与技术学院一、课程的教学目标与任务本课程培养学生较熟练地掌握C语言程序设计的基本技能，掌握各种基本数据结构和算法。通过本课程的学习，掌握C语言基础知识；掌握简单算法和数据结构的基本设计方法；掌握复杂数据结构（例如栈和队列以及链表）的含义并能简单应用，建立程序设计的思想，培养学生的问题解决能
2、力和实际编程能力；了解并初步掌握当前软件行业公认的程序设计风格和编程实践。学生应掌握各种基本数据结构的概念、实现方法及涉及的基本算法，并能用这些数据结构和算法解决相关的应用问题，为进一步学习相关学科打下坚实的基础。通过本课程的学习。重点是阐述程序设计思想和各种数据结构及其相关算法，培养学生分析问题和使用程序和数据结构解决问题的能力。二、本课程与其它课程的联系和分工“计算机科学与编程导论”是本课程的先修课程。具体分工是:由计算机科学与编程导论课程建立对计算机的基本认识，了解软件的构成及分类，了解程序的运行原理和过程；由本课程介绍程序设计基础和软件开发方法，C语言的基本语法和语义（包括变量、简单数
3、据类型、表达式和语句、输入和输出基础、顺序、条件和循环控制结构、函数定义、函数调用和参数传递等关于程序设计的基本要素），基本数据结构和算法，使用C语言进行程序设计的方法以及使用程序解决问题的方法。与本课程关联的有相同学期开设的“程序语言设计实验”独立实验课，此外，为增强软件开发能力，在短二期设置相应的能力训练实践课程“软件基础训练”。本课程为计算机学科的多个后续课程打下基础，如计算机网络、课外创新实践等。三、课程内容及基本要求第一部分：C语言程序设计（一）计算机与程序设计概述（2学时）主要内容：（1）计算机软件分类（2）计算机语言（3）程序执行的原理和过程（4）软件开发方法1.基本要求了解计算
4、机软件的分类以及计算机语言的分类；理解程序执行的原理和过程；了解基本的软件开发方法和应用软件的开发方法。2.重点、难点重点：程序执行的原理和过程由于在计算机科学与编程导论课程中已经讲授了基本的计算机概念和软件的基础知识，因此这里仅需进行内容回顾，并重点讨论程序执行原理和过程，介绍软件开发方法。(二) C程序基础（2学时)主要内容：（1）字符集、保留字集、标识符、算符等基本词法元素（2）变量声明和数据类型（3）可执行语句（4）键盘输入和屏幕输出等输入/输出基础（5）运算符与表达式（6）C预处理：include、define（7）C程序的一般形式1.基本要求记住C所用的字符集和保留字，了解C的基本
5、数据类型；明确常量、变量与字面量的含义；掌握运算符的使用、表达式的含义和计算过程；掌握用标准函数实现输入和输出的基本方法；掌握各类可执行语句的使用；了解C编译器的基本工作过程和各类预编译语句的使用；能熟练运用上述基本元素进行简单的C程序设计。2.重点、难点重点： 基本数据类型、运算符与表达式、基本的输入和输出处理、语句由于这是第一门程序设计课程，因此需要让学生深入理解变量、表达式的内涵，掌握C程序的一般形式，并建立良好的编程风格。(三) 基本程序控制结构（8学时)主要内容：（1）控制结构（2）条件语句：if语句和switch语句；嵌套if语句和多选项决策（3）循环语句：for语句；do-whi
6、le语句;嵌套循环1.基本要求了解什么是控制结构；掌握基本的程序控制结构（包括顺序结构、条件选择和循环结构）及其执行流程；掌握不同程序控制结构的C语言实现；掌握嵌套的程序控制结构及其执行流程；熟练使用C语言控制结构设计程序。2. 重点、难点重点：条件结构和循环结构的基本形式及执行流程难点：if语句的匹配原则；循环语句的结束条件和执行次数；复合控制结构的流程。可以采用流程图来阐述不同控制结构的执行流程，便于学生理解。这部分内容需特别加强应用举例。(四) 数组与字符串（6学时)主要内容：（1）声明和引用数组及数组下标（2）多维数组（3）字符数组与字符串（4）字符串库函数的使用1.基本要求掌握声明数
7、组和引用数组的语法；掌握数组初始化的方法；掌握C语言数组下标的特殊性；了解多维数组的声明及引用语法；掌握字符数组与字符串的区别；掌握初始化字符串变量的方法；掌握常用的字符串操作库函数。2. 重点、难点重点：声明数组和引用数组的语法；字符串的特殊性；字符串操作库函数的使用。难点：数组的存储和访问方法；C语言数组下标的特殊性；字符串与字符数组的区别。(五) 函数与模块化编程（10学时)主要内容：（1）函数的基本概念（2）函数的定义、声明和调用（3）参数传递和变量的作用域（4）递归（5）标准函数或预定义函数（6）模块化编程1.基本要求了解函数是过程抽象的基本形式，掌握函数的定义、声明和调用方法；了解
8、函数、变量等先声明后引用的一般原则；理解参数传递的内涵，了解函数操作的对象的不同形式、作用域和使用方法；了解递归函数的运行过程，掌握递归函数的编写方法；掌握标准函数或预定义函数的使用方法；理解模块化编程的内涵并掌握自顶向下设计的方法。2.重点、难点重点：函数的定义、声明和调用，参数传递，变量（数据）的作用域，递归函数的运行过程和递归函数的编写，标准函数的使用；模块化编程的意义难点：参数传递，尤其是数组作为函数参数；变量的作用域；递归函数的运行过程和递归函数的编写。这部分内容需特别加强应用举例。(六) 结构体与共用体（联合）（6学时）主要内容：（1）结构体的声明及数据程远引用（2）共用体的声明与
9、使用（3）共用体与结构体的区别1.基本要求掌握结构类型的定义和使用，了解联合数据类型的定义和使用；理解共用体与结构体的区别。2.重点、难点重点：结构类型的定义和应用。这部分内容需特别加强应用举例。(七) 动态数据结构（指针）（8学时)主要内容：（1）指针的概念及其含义以及如何使用指针引用变量（2）指针运算的意义及其使用（3）动态内存分配（4）使用指针实现链表、二叉树等动态数据结构1.基本要求理解指针其实是一个内存地址；掌握如何通过指针引用变量；理解只恨运算的意义及合法性；掌握分配内存和回收内存的方法；了解如何使用指针实现链表等动态数据结构。2.重点、难点重点：指针的概念及其含义了；使用指针变量
10、的方法；指针运算的含义。难点：指针是C语言中初学者比较难以理解和掌握的一个问题，需要从指针的本质来阐明它的实际意义及使用方法；使用指针实现动态数据结构是一种高效的方法，但也是初学者容易犯错误的地方，需要特别加强引用举例。(八) 文件处理（6学时）主要内容：（1）文件指针变量（2）文件的打开与关闭、打开文件的不同方式（3）文件读写和定位1.基本要求了解磁盘文件的不同组织形式；掌握打开文件的不同方式和关闭文件的方法；掌握读写文件和在文件中定位的方法。2.重点、难点重点：文件的打开方式；文件读写和定位。第二部分：数据结构(一) 数据结构的基本概念（2学时） 主要内容：(1) 数据结构的概念，包括数据
11、、数据元素、结构；(2) 逻辑结构和物理结构的概念和区别；(3) 抽象数据类型的概念、表示和实现；(4) 算法的概念、特性、设计要求；(5) 算法性能评价方法，大O记法。1 基本要求应了解数据结构的基本含义、课程所研究的主要内容，了解四类基本结构：集合、线性结构、树形结构、图状结构。掌握逻辑结构和物理结构的定义与区别,了解两类存储结构：顺序存储结构和链式存储结构。掌握抽象数据类型ADT的定义、表示和实现。掌握算法的定义、特性、设计要求和性能度量方法，包括时间复杂度和空间复杂度，能用大O记法表示时间、空间复杂度。2 重点与难点重点：数据结构的定义，四类基本结构；逻辑结构和物理结构的区别，两类存储
12、结构；ADT的定义；算法的性能度量方法。难点：逻辑结构、物理结构的区别；时间复杂度的定义与大O表示法。（二）线性表（6学时）主要内容：(1) 线性表的概念与基本运算；(2) 线性表的顺序表示和实现；(3) 线性表的链式表示和实现，包括单链表、静态链表、循环链表、双向链表；(4) 线性表的应用：一元多项式的表示与相加。1. 基本要求掌握线性表的概念和基本运算，能用基本运算实现一些应用。熟练掌握顺序表的表示，理解随机存取的含义，掌握顺序表的基本算法，包括插入、删除、查找。熟练掌握链式存储的表示和实现，理解头指针、头结点的含义，掌握单链表、静态链表、循环链表、双向链表的概念和基本运算实现，包括插入和
13、删除。2. 重点与难点重点：线性表的概念；顺序表的表示、特点，插入、删除操作的实现与复杂度分析；链式表示的特点，各种链表的概念，插入、删除操作的实现。难点：顺序表与链表的特性对比与选取，插入、删除操作的实现。（三）栈和队列（4学时）主要内容：(1) 栈的概念、基本运算；(2) 栈的两种实现：顺序栈和链栈，入栈与出栈操作的实现；(3) 栈的应用，特别是栈与函数调用、递归的关系；(4) 队列的概念、基本运算；(5) 队列的两种实现：链队列和循环队列，入队列和出队列操作的实现。1. 基本要求掌握栈的基本概念：后进先出的特点、栈底、栈顶。熟练掌握顺序栈和链栈的表示方法，入栈、出栈操作的实现。了解栈的几
14、种应用，如数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值。理解栈在函数调用与递归实现中的重要作用，会写递归程序。掌握队列的概念：先进先出的特点、队头、队尾。熟练掌握链队列、循环队列的表示方法，入队列、出队列操作的实现，理解循环队列设计的初衷。2. 重点与难点重点：栈的概念与特点；顺序栈和链栈的表示，入栈和出栈的实现；栈与函数调用和递归实现的关系；队列的概念与特点；链队列与循环队列的表示，入队列、出队列的实现。难点：栈与函数调用、递归的关系；循环队列的设计初衷与基本运算实现。（四）串（2学时）主要内容：(1) 串的概念与基本运算；(2) 串的三种表示与实现：定长顺序串、堆分配顺序串、
15、块链串；(3) 串的模式匹配算法：BF算法与KMP算法。1. 基本要求掌握串的基本概念：子串、主串、位置；掌握串的基本运算。掌握三种表示方法：定长顺序存储、堆分配顺序存储、块链存储。掌握朴素的模式匹配算法BF算法和改进的模式匹配算法KMP算法，理解改进的思路。2. 重点与难点重点：串的概念，与线性表的区别；基本运算；三种表示方法；BF算法；KMP算法。难点：KMP算法。（五）数组和广义表（4学时）主要内容：(1) 数组的定义；(2) 数组的顺序表示和实现；(3) 矩阵的压缩存储；(4) 广义表1. 基本要求掌握数组的定义，理解数组与线性表的区别。熟练掌握数组的顺序表示和实现，特别是高维数组的两种顺序存储方法：行序为主序与列序为主序。掌握特殊矩阵的压缩存储，包括对称矩阵、三角矩阵和对角矩阵。掌握稀疏矩阵的压缩存储方法。掌握广义表的定义和
