数据结构课程教学大纲

数据结构课程教学大纲课程英文名称Data Organization课程编号学分:（实验）050060032+16学时:

3.0

一、课程教学对象数学与计算科学学院信息与计算科学专业的本科学生

二、课程性质及教学目的课程性质本课程是数学与计算科学学院信息与计算科学本科专业的核心专业课课程包括理论教学（32学时）和课内实验（16学时）两个环节目的和任务使学生获得计算机科学各领域的数据结构知识及有关的应用软件所要用到的各种数据结构知识；从数据结构及其实现的角度系统地学习和掌握常用基本数据结构及其不同的实现方法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同算法实现的原则和方法，为后继课程的学习打下良好的基础，掌握常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算♦法知识；提高软件设计和编程技能学会初步对不同的存储结构和相应算法的对比，有一定的算法改进能力通过学习本门课程，学生应该了解典型的数据结构与算法的关系；应该具有结合实际应用，设计出高效算法和数据结构的能力；初步具备结合专业应用，将数据结构知识用于专业程序设计中的能力本课程是一门实践性较强的课程学生应结合理论教学的进度，通过对本课程的知识传递、算法设计和上机实践的训练，进一步加深对数据结构和算法的理解，培养学生的数据抽象能力、逻辑思维能力和程序设计的能力，提高分析问题和解决问题的能力和实际动手能力该课程概念性、实践性很强，教学中强调理论联系实际，并结合现代计算机技术，在教学方法与手段方面进行改革

三、对先修知识的要求C++程序设计、离散数学等

四、课程的主要内容、基本要求和学时分配建议（总学时数:理论课32学时）知识点要求课外学习要求知识模块学时学习方式

1、绪论

1.1数据结构的基本概念C课堂讲授

11.2算法计算法分析C课堂讲授

12、线性表

2.1线性表的逻辑结构B1课堂讲授

2.2线性表的顺序存储结构及实现A课堂讲授

12.3线性表的链接存储结构及实现A课堂讲授

12.4顺序表和单链表的比较B课堂讲授

12.5线性表的其他存储方式C课堂讲授

12.6应用举例C课堂讲授

13.1栈A1课堂讲授

3、特殊线性表

3.2队列B课堂讲授1栈、队列和串

3.3串B课堂讲授

13.4应用举例C1课堂讲授

4、广义线性

4.1多维数组B课堂讲授

14.2矩阵的压缩存储B课堂讲授1表——多维数

4.3广义表B课堂讲授1组和广义表

4.4应用举例C课堂讲授

15、树和二叉

5.1树的逻辑、存储结构B课堂讲授1树

5.2二叉树的逻辑结构B课堂讲授

15.3二叉树的存储结构及实现A1课堂讲授

5.4应用举例C1课堂讲授

6、图

6.1图的逻辑结构B1课堂讲授

6.2图的存储结构及实现A课堂讲授

16.3图的连通性B课堂讲授

16.4应用举例C课堂讲授

17、查找技术

7.1概述C1课堂讲授

7.2线性表的查找技术A课堂讲授

17.3树表的查找技术B课堂讲授

17.4散列表的查找技术A课堂讲授

8、排序技术

8.1插入排序A课堂讲授

18.2交换排序B1课堂讲授

8.3选择排序A课堂讲授

18.4归并排序C课堂讲授1

五、建议使用教材及参考书I、理论课教材王红梅，胡明，王涛等.数据结构（C++版）[M].北京清华大学出版社，

2005.

72、实验课教材王红梅，胡明，王涛等.数据结构（C++版）学习辅导与实验指导[M].北京清华大学出版社，

2005.

93、主要参考书

[1]严蔚敏，吴伟民.数据结构[M].北京清华大学出版社,1997

[2]齐得昱.数据结构与算法[M].北京清华大学出版社，2003

[3]辛运帏，刘憬等.数据结构与算法[M].北京高等教育出版社,2006

[4]傅清祥，王晓东.算法与数据结构[M].北京电子工业出版社，2001

[5]陈慧南.数据结构与算法一C++语言描述.[M].高等教育出版社，2005

六、课程考核方式以闭卷考试为主，结合平时成绩和上机实验报告评定成绩其中平时成绩占10%含作业和考勤，上机实验报告占20%,期末笔试考试成绩占70%

七、课内实验环节及要求16学时实验项目实验内容实验目的及要求学时序号1基础实验21在一维整型数组中顺序1比较顺序查找最好、最坏和查找与给定值相等的元素平均的时间性能2在一个数组中确定第k2比较解决相同问题的不同小的元素至少采用两种方算法的时间性能法求解2线性表实验21建立含有若干个元素的1掌握线性表的的顺序及链顺序表接存储结构2用头插法或尾插法建2验证顺序表、单链表及其基立带头结点的单链表本操作的实现3对已建立的顺序表、3掌握数据结构及算法的程序实现的基本方法单链表实现插入、删除、查找等基本操作32特殊线性表——栈、队1建立一个空栈，对已建1掌握栈的顺序存储、队列的列和串实验立的栈进行插入、删除、取链接存储及串的顺序存储结构栈顶元素等基本操作2掌握栈、队列、串的操作特2建立一个空队列，对已性建立的队列进行插入、删除、3掌握基于顺序栈、链队列及取队头元素等基本操作顺序串的基本操作的实现方法3创建两个串，采用顺序存储，并实现串的插入、删除、求子串等基本操作4广义线性表——多维21建立一个n*n的对称矩1掌握对称矩阵的压缩存储数组和广义表实验方法及寻址方法阵，并用一维数组存储2采用头尾表示法建立广2掌握广义表的逻辑结构、头尾表示法存储结构及其基本操义表并求其深度作在头尾表示法上的实现方法5树和二叉树实验21采用孩子兄弟表示法建1掌握树的逻辑结构及孩子立一棵树，并实现树的前序兄弟存储结构遍历操作2掌握基于树的孩子兄弟存2建立一颗含有n个结点储结构的遍历方法的二叉树，采用二叉链表存3掌握二叉树的逻辑结构及储，前序或中序、后序遍二叉链表存储结构历该二叉树4掌握基于二叉链表存储的二叉树的遍历操作的实现6图实验21建立一个无向图的邻接1掌握图的逻辑结构、邻接矩矩阵存储，对其进行深度优阵存储结构及邻接表存储结构先、广度优先遍历2掌握图在邻接矩阵存储结2建立一个有向图的邻接构下和邻接表存储结构下遍历表存储结构，对其进行深度算法的实现优先、广度优先遍历7查找技术试验21对给定的数组，利用顺1掌握顺序查找算法、折半查序查找算法，查找数组中与找算法的基本思想、实现方法及给定值相等的元素时间性能2对给定的一组无序序歹2掌握二叉排序树的定义、特IJ,建立一颗二叉排序树，并性、建立方法及查找性能，并实对建立的二叉排序树实现查现基于二叉排序树的查找技术找操作3掌握散列查找的基本思想、3对给定的一组整数和散闭散列表的构造方法、散列技术列函数，采用线性探测法处的查找性能及线性探测处理冲理冲突构造散列表，并设计突的方法一个查找算法，验证查找性能8排序技术试验2对一组数据分别进行直接插1掌握直接插入排序算法、起入排序、起泡排序和简单选泡排序算法和简单选择排序算择排序法的基本思想、实现方法2验证以上算法的时间性能。