算法与数据结构课程教学大纲.doc

西南科技大学本科课程教学大纲算法与数据结构课程教学大纲【课程编号】：22119426【英文译名】：Algorithm and Data Structure【适用专业】：电子信息工程、自动化、生物医学工程、通信工程等专业【学 分 数】：2【总 学 时】：32【实践学时】：8一、本课程教学目的和课程性质算法与数据结构是计算机软件学科中重要的理论和技术基础课，目前它也是信息类各专业的一门重要选修课程。本课程的教学目的是通过学习、研究和分析各种数据的逻辑结构，让学生充分理解数据在计算机中的存储形式，即物理结构。在此基础上，学生能设计和选择出适合相应数据的管理及操作算法，以便于编写出健壮高效的应用程序。本门课程的开展，将为培养具有素质好、技术强的软件高级工程技术人才做准备。二、本课程的基本要求通过学习本门课程，学生应该了解典型的数据结构与算法的关系；应该具有结合实际应用，设计出高效算法和数据结构的能力。 1、熟悉各种基本数据结构的定义，性质和特点；2、掌握各种基本数据结构的逻辑结构和存储结构及重点算法；3、初步掌握算法分析的技巧以及如何根据实际问题设计出一个高效率算法；4、初步具备结合专业应用，将数据结构知识用于专业程序设计中的能力。三、本课程与其它课程的关系前修课程：计算机文化基础、C语言程序设计后续课程：软件工程、网络编程等四、课程内容1、数据结构与算法的基本概念内容体系：数据结构与算法的概念以及它们之间的关系。知识点：数据结构的概念和基本术语；基本数据类型；数据抽象和抽象数据类型；算法描述与分析。重点：数据结构的概念；算法分析。难点：抽象数据类型；算法分析。2、线性表内容体系：简单数据结构线性表的结构与操作实现。知识点：线性数据结构的特点；线性表的逻辑结构；线性表的顺序存储结构；线性链表；线性表的应用举例。重点：线性表的逻辑结构和存储结构。难点：单链表的建立和操作算法。3、堆栈和队列内容体系：堆栈和队列的逻辑特征与操作实现。知识点：堆栈的抽象数据类型；堆栈的表示和实现；表达式求值方法；队列的抽象数据类型及定义；链队列和循环队列；堆栈和队列的应用。重点：堆栈与队列的特点；堆栈与队列的应用。难点：循环队列；堆栈与队列的应用。4、串内容体系：字符串的操作函数及存储实现。知识点：串的逻辑结构和定义；串的存储结构和基本操作；串的应用。重点：串的应用。难点：串操作函数的应用。5、树及二叉树内容体系：二叉树的性质和基本操作与应用。知识点：树的定义和基本操作；二叉树的定义，基本操作，存储结构及性质；二叉树的遍历；树的存储结构，树的遍历；哈夫曼树及编码；树的应用举例。重点：二叉树的遍历；最优二叉树和哈夫曼编码；树的应用。难点：二叉树的应用（哈夫曼算法）。6、图内容体系：图的逻辑结构与物理结构；图的应用。知识点：图的定义和术语；图的存储结构，图的遍历；图的连通性，最短路径；图的应用举例。重点：图的存储结构；图的连通性，最短路径；图的应用。难点：图的应用（最小生成树、关键路径以及最小路径的实现）。7、查找内容体系：数据查找的分类及实现。知识点：顺序查找，有序表的查找；索引顺序查找，二分查找法；哈希表的建立及查找机制。重点：二分查找法；哈希表的建立及查找机制。难点：哈希查找。8、排序内容体系：数据排序方法实现。知识点：插入排序，快速排序，选择排序；归并排序，堆排序；各种内部排序方法的比较；各种排序方法的应用举例。重点：快速排序；选择排序。难点：快速排序；堆排序。五、教学方法建议理论教学可采用多媒体加适当板书的形式，在课堂中可适当用TC调试一些算法的实现，以展现算法到程序的过程，让学生理解算法与程序的关系，从而做到举一反三。由于本课程的理论比较抽象，可多加些应用实例穿插于课堂中。六、考核方式期末考试闭卷方式。拟采取结构评分方式，总成绩实验成绩 + 期末考试成绩。实验成绩占30%，期末考试占70%。试卷命题以课程教学大纲与知识点范围为依据。七、其它说明可选择一些算法作为作业让学生独立去实现，采用激励与督促手段，随后加以检查和评讲。八、选用教材及主要参考书1、建议教材严伟敏,吴伟民.数据结构.清华大学出版社，19972、参考书1 谭浩强.C程序设计.清华大学出版社，20042 刘卫东,沈官林译.数据结构C+语言描述.清华大学出版社，20043 谈春媛.数据结构.电子工业出版社，19964 严伟敏,吴伟民.数据结构题集（C语言版）.清华大学出版社，2000年九、学时分配课程内容讲课实验大作业小计1、 绪论2 22、 线性表32 53、 栈和队列22464、 串1 35、 数组和广义表2 26、 树和二叉树624107、 图44128、 查找22 49、 排序244合计24816（课外完成）48算法与数据结构课程实验教学计划一、本课程实验教学的目的和要求通过本课程的实验教学，让学生能够加深对课程内容的理解，增加感性认识，提高软件设计、程序编写及工程应用方面的综合能力。二、本课程实验内容体系和实验类型序号实验内容实验类型学时要求1单链表操作设计2必做2栈与队列设计2必做3树和图的应用综合设计2(课外补充2学时)必做4查找与排序的应用综合设计2(课外补充2学时)必做三、实验项目内容安排1、单链表操作实验目的：(1) 理解单链表的存储结构。(2) 掌握单链表的建立、插入和删除等操作过程。(3) 掌握链式存储结构的优点。实验内容及要求：先建立一个单链表，再在给定位置i之后插入一个数据为x的新结点，然后再删除另一个结点，并将它们的操作结果分别输出。用C程序实现该算法。EDCBAHx2、栈与队列实验目的：(1) 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。(2) 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。实验内容：(1) 顺序栈的实现和运算；(2) 顺序队列的实现和运算；(3) 循环队列的实现和运算。3、树和图的应用实验目的：(1) 掌握用二叉树的生成过程；(2) 深入理解二叉树的递归遍历过程；(3) 掌握图的两种类型及其实际工程的图形化方法；(4) 掌握图的存储及其程序实现；(5) 掌握最短路径的算法及实现。实验内容：(1) 编程实现含有n个结点的二叉树的建立和先序遍历。(课内完成)(2) 给定n个城市以及城市间的路径长度，编程求出从某一城市出发到达任意其它城市间的最短路径。(课外完成)4、查找与排序的应用实验目的：(1) 掌握计算机中实现查找的多种算法原理；(2) 掌握折半查找的基本原理和程序实现；(3) 掌握一些基本的排序方法和过程；(4) 掌握简单排序和冒泡排序的思想和方法。实验内容：(1) 对于给定序列（49 38 65 97 76 13 27 79）先进行冒泡排序，再用折半查找法写出查找关键字K分别是21和85的程序。(课内完成)(2) 对关键字序列（49