第一篇：数据结构DS复习_章节教案（模版）
《数据结构》课程授课教案
课程名称：数据结构 英文名称：Data Structure 学时数及学分：64＋32学时
4＋1学分 授课班级：2005级2班
教材名称及作者、出版社、出版时间：
《数据结构（C语言版）》，严蔚敏 吴伟民，北京：清华大学出版社，2004
一、课程的目的、要求和任务
《数据结构》是计算机专业的一门必修的核心基础课程。是计算机程序设计的重要理论技术基础，它对理论和实践的要求都相当高，具有相当的难度，且内容较多。
本课程旨在讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构在计算机中的存储结构，以及进行各种非数值运算的方法，让学生学习、分析和研究计算机加工数据对象的特性，掌握数据的组织方法，以便选择合适的数据的逻辑结构和存储结构，设计相应的操作运算。在计算机应用领域中，尤其是在系统软件和应用软件的设计和应用中都要用到各种数据结构，这对提高软件设计和程序编制水平都有很大的帮助。
二、课程主要教学内容
本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。
1.掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法；
2.掌握各种主要数据结构的特点、机内表示、处理数据的算法设计，以及算法分析、组织、处理数据的理论和方法，建立良好的编程风格；培养数据的抽象能力。
三、课程教学重点与难点
1.教学重点：线性表、栈、队列、二叉树、图典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法思想。2.教学难点：各种数据结构的应用和进行操作实现。
四、参考书
1.《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，2006年7月 2.《数据结构与算法设计》,王晓东,电子工业出版社,2002.3 3.《数据结构（C语言篇）习题与解析》,李春葆, 清华大学出版社 4.《数据结构学习指导与典型题解》，朱占立等编著，西安交通大学出版社 5.《数据结构题集（C语言版）》, 严蔚敏
吴伟民, 清华大学出版社 6.《数据结构》 殷人昆 编著, 清华大学出版社
7.《数据结构》 张选平雷永梅, 机械工业出版社，2002.1 第一章 绪论
1.教学内容(1)(2)(3)(4)2.数据结构的基本概念和术语； 数据的逻辑结构、存储结构； 抽象数据类型在软件设计中的意义；
算法的概念和算法的时间和空间复杂度分析。
教学目的及要求(1)(2)(3)(4)掌握数据结构的基本概念，理解数据结构和算法的关系； 抽象数据类型的表示和实现； 类C语言描述算法的机制； 掌握算法复杂性分析的方法和技巧。本课程的主要内容；
数据结构的基本概念和术语，抽象数据类型，算法和算法的时间复杂度分析 抽象数据类型的表示和实现 算法的时间复杂度分析；
讲授数据结构课程的主要内容以及在软件分析和设计中意义； 讲授抽象数据类型在软件设计中的意义； 讲授算法的概念和算法的时间复杂度分析方法； 例题讲解算法的时间复杂度分析方法； 作业
对于重点和难点，通过例题讨论讲解。3.教学重点(1)(2)
4.教学难点(1)(2)
5.教学思路与教学方法(1)(2)(3)(4)(5)(6)
6.习题与思考题(1)填空题
a）数据的逻辑结构可形式地用一个二元组B＝(D，S)来表示，其中D是_____，S是_____。b）存储结构可根据数据元素在机器中的位置是否连续分为_____，_____。c）算法的基本要求有_____，_____，_____，_____，_____。d）度量算法效率可通过_____，_____两方面进行。(2)简述下列术语：
a）数据、数据元素、数据对象、数据结构 b）数据的存储结构、逻辑结构； c）数据类型和抽象数据类型(3)(4)举例说明一下数据结构和算法的关系。
试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。
例如：求下列算法的时间复杂度：
i=1;
while(i<=n)
i=i*3;答：O（logn）
第二章 线性表（8学时）
1.教学内容(1)线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算；(2)线性表的顺序存储结构、a）特点；
b）基本操作的实现算法（初始化、插入、删除、查找等）；(3)线性表的链式存储结构及基本操作的实现算法；
a）线性链表的特点、类型定义，以及基本操作（初始化、插入、删除、查找等）的实现算法；
b）循环链表、双向链表的定义、特点及操作的实现。
2.教学目的及要求(1)(2)(3)掌握线性表的逻辑特点；
掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。
掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。(4)循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。(5)3.领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能 教学重点(1)(2)(3)4.(1)(2)5.线性表的定义和抽象数据类型；顺序和链式存储结构； 顺序表的设计；
链表（单链表、循环链表、双向链表）的设计。顺序表操作的算法设计，以及单链表操作的算法设计； 完整应用程序的结构 教学难点
教学思路与教学方法(1)(2)讲授本章节的基本概念，先逻辑结构，后存储结构； 讲授各存储结构下操作实现的主要思想；(3)(4)(5)6.在C++开发环境下，计算机演示完整应用程序的结构，以及编辑、编译和运行的方法；
例题讲解；对于重点和难点，通过程序演示，作业来突出。
辅助手段：多媒体演示＋板书
习题与思考题（见PPT课件，并完成实验二的实验题目）
教学内容(1)(2)(3)(4)(5)栈的基本概念、特点，与一般线性表的区别；
栈顺序表示和实现、链式表示和实现；
栈的典型应用：数制转换问题；括号匹配问题；栈与递归； 队列的基本概念、特点，与一般线性表的区别；
顺序队列、顺序循环队列、链式队列、队列应用；优先级队列。理解栈的概念；
掌握顺序栈和链式栈的设计方法；
理解队列的概念，掌握顺序循环队列和链式队列的设计方法； 了解栈和队列的应用方法，掌握栈和队列的基本应用。第三章 栈和队列（8学时）
1.2.教学目的及要求(1)(2)(3)(4)
3.教学重点(1)(2)顺序栈和链栈的设计方法、典型应用； 顺序循环队列和链式队列的设计方法。栈和队列的实现；
应用栈实现表达式的求值；
顺序队列的假溢出现象，顺序循环队列的队空和队满判断方法。
课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。(2)(3)(4)对算法的实现要求采用VC++ 开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。
每次下课前布置若干思考题，待下次上新课前进行提问，或完成课堂练习，加强互动。
根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。4.教学难点(1)(2)(3)
5.教学思路与教学方法(1)
6.1.习题与思考题（见PPT课件，并完成实验三的实验题目）教学内容 第四章 串（2学时）(1)(2)(3)2.(1)(2)(3)(4)3.(1)(2)4.5.串的基本概念、存储结构（顺序存储、链式存储）、顺序存储结构下基本操作的实现算法；
串的模式匹配：Brute-Force算法。
联系C语言中串的存储方法及串函数，并围绕两种基本存储结构进行分析。了解串类型的抽象数据类型定义； 熟悉串的有关概念，串和线性表的关系；
了解串的表示和实现（串的各种存储结构，比较它们的优、缺点，从而学会在何时选用何种存储结构为宜）；
理解串的两种模式匹配算法的思想、实现及时间复杂度的分析；
串的存储结构； 了解串的模式匹配。教学目的及要求
教学重点
教学难点
教学思路与教学方法(1)(2)(3)以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；
课后做习题，并课外上机实验，练习基本操作的实现及模式匹配的实例训练，以巩固课堂所学知识点。板书设计：
a）以文字描述为主，要点及关键词用不同颜色标注； b）涉及有关存储结构、算法时，通过示意图描述；(4)提问：
a）空串和空白串有无区别？
b）回顾：C语言中串的存储方法及有关串函数。
6.习题与思考题（见PPT课件，并完成实验四的实验题目）
第五章 数组和广义表（6学时）
1.教学内容(1)(2)(3)(4)2.数组的定义及其实现机制；
特殊矩阵（包括n阶对称矩阵、n阶三角矩阵）的压缩存储方法； 稀疏矩阵的压缩存储方法：三元组顺序表、十字链表，以及稀疏矩阵实现转置和相加运算；
广义表的结构特点、基本操作及其存储表示方法
教学目的及要求(1)(2)理解了解数组的逻辑结构和存储表示；掌握数组在以行/列为主的存储结构中的地址计算方法；
掌握特殊矩阵的压缩存储方式及下标变换公式；(3)(4)了解稀疏矩阵压缩存储方法的特点和适用范围，理解以三元组表示的稀疏矩阵进行矩阵运算采用的处理方法；
掌握广义表的结构特点极其存储表示方法，以及对非空广义表进行分解的两种分析方法；
(5)3.(1)(2)(3)(4)4.5.(1)(1)(2)(3)(4)了解广义表的递归算法设计。
稀疏矩阵的三元表存储表示及稀疏矩阵转置的两种实现方法。多维数组的表示和实现； 特殊矩阵的压缩存储； 稀疏矩阵的压缩存储。
稀疏矩阵的十字链表的定义和建立算法。
从具体的矩阵实例出发，先分析其特点，然后围绕以上知识点进行讲述。以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；
课后做习题，并上机实验，练习特殊矩阵、稀疏矩阵的压缩存储方法，以巩固课堂所学知识点。板书设计：
a）以文字描述为主，要点及关键词用不同颜色标注； b）对压缩存储方法通过示意图描述；
c）对于实例，通过链接到VC环境下实际运行。教学重点
教学难点
教学思路与教学方法
(5)(6)(7)重点突出：通过课堂强调与透彻分析，课后练习进行。
难点解决：通过实例讲解，并在VC环境下实际运行实例，使学生真实体会算法设计全过程。师生互动设计：
a）提问：数组与线性表的区别与联系？ b）回顾：线性表的两种存储结构表示方法。
6.1.习题与思考题（见PPT课件，并完成实验四的实验题目）教学内容(1)(2)(3)二叉树的定义和性质，性质的应用
二叉树的存储结构（特别是二叉链表存储结构）
二叉树的各种遍历算法（先序、中序、后序、层次）及其应用；能根据先序和中序，中序和后序确定一棵二叉树。(4)(5)线索二叉树的建立、遍历的基本思想，能画出按先序、中序、后序遍历次序建立的线索二叉树；
二叉树的应用—哈夫曼树，哈夫曼编码； 第六章 树和二叉树（10学时）(6)2.(1)(2)(3)3.(1)(2)(3)4.树和二叉树之间的转换 树与二叉树的基本概念； 二叉树的性质与存储结构；
掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现。二叉树的性质、二叉树的存储结构；
二叉树的遍历算法和二叉树遍历算法的应用； 哈夫曼树在编码方面的应用方法。教学目的及要求
教学重点
教学难点(1)(2)二叉树的性质以及利用这些性质分析问题的方法； 二叉树问题的遍历算法设计分析和实现。
讲授本章节的基本概念，先逻辑结构，后存储结构； 讲授各存储结构下的实现的主要思想； 计算机演示存储结构下的实现； 例题讲解； 作业
辅助手段：多媒体演示
对于重点和难点，通过程序演示，作业来突出。5.教学思路与教学方法(1)(2)(3)(4)(5)(6)(7)
6.习题与思考题（见PPT课件，并完成实验五的实验题目）
第七章 图（10学时）
1.教学内容(1)(2)2.(1)(2)(3)(4)(5)(6)(7)3.图的基本概念、图的存储结构；
图的程序实现、图的遍历、最小生成树、最短路径等。了解图的定义和术语
掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法； 理解图的深度和广度遍历方法和算法设计方法； 了解图的连通性问题极其判断；
理解最小生成树的概念、普里姆算法和克鲁斯卡尔算法； 有向无环图极其应用（拓扑排序和关键路径）；
了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算法。教学目的及要求
教学重点(1)(2)(3)图的邻接矩阵和图的邻接表存储结构； 图的深度和广度遍历方法； 普里姆算法和克鲁斯卡尔算法。4.5.教学难点(1)(1)(2)(3)(4)(5)(6)图操作的实现方法。
课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量；
图中的概念很多，采取先讲实例应用，再总结概念定义的方法学习效果会好些；
对重点和难点算法的核心部分通过板书进行详细讲解。
对算法的实现要求采用VC++开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。
每次下课前布置若干思考题，待下次上新课前进行提问。
根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。教学思路与教学方法
6.习题与思考题（见PPT课件，并完成实验六的实验题目）
第八章 查找（8学时）
1.教学内容(1)(2)(3)(4)顺序查找、二分查找、索引顺序查找算法；
二叉排序树的查找、插入与删除算法；了解二叉平衡树的基本概念 常用的哈希函数的设计方法：除留余数法、直接定址法、数字分析法；哈希冲突解决方法：开放地址法、链表法。
哈希表的完整设计过程，包括：哈希表的构建、元素的插入与删除、哈希表查找效率。
2.教学目的及要求(1)掌握静态查找表的四种查找方法（顺序查找、折半查找、静态树表、索引查找）的实现；(2)(3)3.掌握动态查找表（二叉排序树、二叉平衡树、B-和B+树、键树）的构造和查找方法；
掌握哈希表构造方法，哈希表的查找以及衡量查找效率的平均查找长度的讨论。教学重点(1)(2)(3)4.5.二分查找；
二叉排序树的查找； 哈希表查找。
教学难点(1)(1)哈希表中哈希函数的设计与哈希冲突解决方法。以课堂多媒体教学为主，辅助以黑板进行绘图分析； 教学思路与教学方法(2)(3)课后完成上机实验，练习二分查找、二叉排序树查找及哈希表查找的算法设计，以巩固课堂所学知识点。板书设计：
a）以文字描述为主，要点及关键词用不同颜色标注； b）对查找、插入与删除等算法通过示意图描述； c）对于实例，通过链接到VC环境下实际运行。
(4)(5)(6)重点突出：通过课堂强调与透彻分析，课后练习进行。
难点解决：通过不同类型的实例讲解，使学生理解并掌握常用的哈希函数设计方法以及哈希冲突的解决方法，并总结其优、缺点。师生互动设计：
a）实例分析中引导学生参与算法设计；
b）提问：在每一种哈希函数的设计方法及哈希冲突的解决方法讲解后，引导并提问学生此类方法的优、缺点及解决途径。
6.1.习题与思考题（见PPT课件，并完成实验七的实验题目）教学内容(1)(2)排序算法的性能指标；
插入排序、选择排序、交换排序、归并排序、基数排序的算法设计与应用。第九章 内部排序（8学时）
2.教学目的及要求(1)(2)掌握排序的基本概念和排序算法的评判标准；
掌握如下排序的算法基本思想和设计方法，以及算法分析。a）直接插入排序 b）希尔排序 c）直接选择排序 d）堆排序 e）快速排序 f）二路归并排序 g）基数排序
3.4.5.教学重点(1)希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想； 教学难点(1)(1)(2)(3)(4)堆排序、快速排序、二路归并排序和基数排序的算法设计方法。讲授本章节的基本概念，先逻辑结构，后存储结构； 讲授各存储结构下的实现的主要思想； 计算机演示存储结构下的实现； 例题讲解； 教学思路与教学方法(5)(6)(7)6.作业
辅助手段：多媒体演示
对于重点和难点，通过程序演示，作业来突出。
习题与思考题（见PPT课件，并完成实验七的实验题目）。
第二篇：湖州师范学院数据结构DS大作业
求真学院
数据结构课程设计大作业
20142832班
题
目： 专
业： 学生姓名： 学
号 指导教师 完成日期：
排序效率的比较 计算机科学与技术
邵
斌
湖州师院求真学院信息工程系
目录一、二、三、四、五、六、七、实验内容概述...............................................................................................................................1 实验目的概述...............................................................................................................................1 解题思路的描述...........................................................................................................................1 源程序清单...................................................................................................................................1 程序调试及测试结果...................................................................................................................8 结论...............................................................................................................................................9 参考文献.....................................................................................................................................10
I
此处写大作业题目（宋体三号，居中）
【内容摘要】
200至300字左右，楷体BG2312五号
【关键字】XXXX，XXXXX，XXXXX，XXXXX(3到5个)数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。
关键字：排序 逻辑运算 数据结构 时间复杂度
【Abstract】
中文摘要的翻译，五号，Times New Roman
【Key words】XXXXX，XXXXX，XXXXX，XXXXX Data structure is the way of computer storage and organization data.A data structure is a data element and a set of data elements that have one or more specific relationships between each other.Typically, carefully selected data structures can be brought to a higher running or storage efficiency, processing a variety of problems.The program is written in C language, it fully reflects the concept of data structure and algorithm charm.The program is implanted in a variety of sorting methods, these sorting algorithms have the characteristics of each algorithm, the use of a variety of algorithms to achieve the same effect, is the so-called “all roads lead to Rome”.And, the program also collects the running time of each algorithm, through the time of the comparison, for the user to pick out two kinds of optimization of the sorting method.Keywords: sorting logic operation data structure time complexity
一、实验内容概述
对于直接插入排序、选择排序、冒泡排序、Shell排序、快速排序和堆排序等几种常见的排序算法进行练习，并且比较各算法在不同长度数据下的优劣。
要求：（１）被排序的对象由计算机随机生成，长度分别取２０，１００，５００三种。
（２）程序中要有对各种排序算法的比较，具体为比较次数和移动次数的统计。
（３）对课设的结果做比较分析
二、实验目的概述
1.巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力；
2.通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作；
3.锻炼学生的动手能力与培养其独立思考的能力。
三、解题思路的描述
这是一个算法性能评价的程序，重点在于算法的性能评价上。实现排序功能可以有多种方法，判断一个算法性能好坏的标准主要有时间复杂度和空间复杂度。在当今系统资源相对充足的计算机系统中，时间复杂度便成为最主要的评价标准。
对于每一个排序算法，都应当有两个返回值：比较次数和移动次数。这里采用指针传递地址的方式，通过修改形参的地址从而可以改变实参的值。每个排序算法中除了含被排序对象指针外，还有两个整型变量指针，用于传递算法执行过程中的比较次数和移动次数。
取定一种排序对象的长度，由计算机产生一定量的伪随机数后，主函数调用各个排序子函数，但由于排序对象也是指向一维数组的指针，在调用一次一种排序算法后，通过形参对指针的改变，被排序对象已经是有序的了。当再次调用其他函数时有可能使比较和移动次数达到最大或最小，就失去了比较的意义。因此，本程序中采用了子函数另开辟空间，参数只起到一个复制值的作用，在每个子函数结束前用delete()来释放申请排序对象的指针，避免程序出现内存耗尽的情况。
四、源程序清单
主要包括： #include
void number(){ srand(time(0));int i,t;printf(“随机数长度：n”);printf(“ 1.长度为20n”);printf(“ 2.长度为100n”);printf(“ 3.长度为500n”);printf(“输入序号选择长度:”);scanf(“%d”,&t);switch(t){ case 1: n=20;for(i=1;i<=n;i++){ a[i]=rand()%1000+1;//1-1000的随机数
}break;case 2: n=100;for(i=1;i<=len;i++){ a[i]=rand()%1000+1;}break;case 3:n=500;for(i=1;i<=len;i++){ a[i]=rand()%1000+1;}break;} for(i=1;i<=len;i++)b[i]=a[i];printf(“随机生成的%d个数如下：n”,len);for(i=1;i<=len;i++){ printf(“%d ”,a[i]);} printf(“n”);} typedef struct{ int key;//关键字
}RecordNode;//排序结点类型 typedef struct{ RecordNode *record;int n;//排序对象的大小 //srand函数是初始化随机数的种子 }ElemType;//排序对象的类型 直接排序
void InsertSort(ElemType A[], int n){ int i, j;ElemType x;for(i=1;i x = A[i];//准备插入第i个元素 for(j=i-1;j>=0;j--){ //从第i-1个开始往前找插入点 if(x.stn < A[j].stn)A[j+1]=A[j];else break;} A[j+1]=x;//插入 } for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} 直接选择排序 void SelectSort(ElemType A[], int n){ int i, j, k;ElemType x;for(i=0;i<=n-2;i++){ //每一趟选择最小元素并与A[i]交换 k=i;for(j=i+1;j<=n-1;j++)//查找最小元素的下标 if(A[j].stn void BubbleSort(ElemType A[], int n){ int i, j, flag;//flag为交换标记 ElemType x;for(i=1;i<=n-1;i++){ // 最多n-1趟排序flag=0;//假设本次没有交换 for(j=n-1;j>=i;j--)//第i 趟 if(A[j].stn < A[j-1].stn){ flag=1;//出现交换 x=A[j];A[j]=A[j-1];A[j-1]=x;} if(flag==0)return;} for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } Shell排序 void ShellSort(ElemType A[ ], int n,int dk) { int i,j,temp;ElemType x; for(i=dk;i 快速排序 void QuickSort(ElemType A[ ], int s, int t){ //递归算法，对区间 A[s] ～A[t] 进行快速排序 int i=s+1, j=t;ElemType temp, x = A[s];//第一个为基准元素 while(i<=j){ while(i<=j && A[i].stn <= x.stn)i++;//从左到右 while(i<=j && A[j].stn >= x.stn)j--;//从右到左 if(i < j){ temp=A[i];A[i]=A[j];A[j]=temp;i++;j--;} for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } if(s!=j){ //交换基准元素 A[s]=A[j];A[j]=x;} if(s void CreatHeap(ElemType A[], int n){ int i;for(i =(n–2)/2;i >= 0;i--)Sift(A, n, i);//调整A[i..n-1]使之为一个堆 } void Sift(ElemType A[], int n, int i){ // 调整A[i..n-1]成为一个堆（它的左右子树已是一个堆）ElemType x=A[i];int j = 2 * i + 1;// j为i的左孩子 while(j <= n-1){ // i有左子树 if(j +1 < n && A[j].stn < A[j+1].stn)j++;// 使j指向左右孩子中排序码大的孩子 if(x.stn < A[j].stn){ //使j指向左右孩子中排序码大的孩子 A[i]=A[j];i=j;j=2*i+1;} else break;} A[i]=x;} void HeapSort(ElemType A[], int n){ //A为待排序表，n为表的长度 int i;ElemType x； CreatHeap(A, n);// 把A建成一个堆 for(i = n-1;i >= 1;i--){ x = A[0];//第0个元素与第i个元素交换 A[0] = A[i];A[i] = x;Sift(A, i, 0);//调整A[0..i-1]使之为一个堆 } for(i=1;i<=n;i++){ printf(“%d ”,a[i]);} printf(“n”);printf(“n”);printf(“比较次数：%d次n”,i);printf(“移动次数：%d次n”,j);} } Void main(){ int i,j,n,N=20;cout<<“ 各排序方法选择结果：n”;ElemType A[20];for(j=0;j 算法的时间复杂度是什么？算法的空间复杂度是什么？为什么？ 插入排序：稳定，时间复杂度 O(n^2)O(n2)选择排序：不稳定，时间复杂度 O(n^2)O(n2)冒泡排序：稳定，时间复杂度 O(n^2)O(n2)希尔排序：不稳定，时间复杂度平均时间 O(nlogn)最差时间O(n^s)1 程序调试及测试结果 主要包括： 选择长度为20的随机数，六种方法排序的结果。 从比较次数和移动次数可大致看出各排序方法的效率高低，后三种明显优于前三种 六、结论 主要包括： 随机数产生方法：srand(time(0))就是给这个算法一个启动种子，也就是算法的随机种子数，有这个数以后才可以产生随机数,用1970.1.1至今的秒数，初始化随机数种子。Srand是种下随机种子数，你每回种下的种子不一样，用Rand得到的随机数就不一样。为了每回种下一个不一样的种子，所以就选用Time(0)，Time(0)是得到当前时时间值（因为每时每刻时间是不一样的了）。 进行函数的参数传递时，如果传入一个地址，比传入一个struct效率要高，因为少了一个拷贝过程。待改进的地方：很多步骤有重复用到，如把数组b赋值给a，定义Ccnt，Rcnt等，可以做个初始化的函数调用，省去重复的代码。可以增加其他排序方法进行效率比较。 七、参考文献 [1] 唐国民, 王国钧.数据结构 [M].北京:清华大学出版社, 2013: 213-238 [2] 张乃孝.算法与数据结构——C语言描述[M].北京: 高等教育出版社, 2002 [3] 唐国民，王智群.C语言程序设计[M].北京:清华大学出版社, 2009:107-115 [4] 唐国民, 王国钧.数据结构实验教程 [M].北京:清华大学出版社, 2013: 195-207 说明： 标为M的是书籍 标为D的为学位论文 标为J的为期刊 标为C的为会议论文 指导教师：邵 斌 日期：2016/6/5 实验成绩： 《数据结构》教案 课程性质和任务 本课程是计算机专业的主要专业基础课程之一。本课程的参考教学时数为54学时，实际讲课学时为35，实验学时为16。其主要内容包括顺序表、链表、栈、队、串、树和图的结构，以及查找和排序技术。通过本课程的教学，使学生理解计算机软件系统所必须的数据结构及算法的内部逻辑，掌握在软件工程中大量存在的查找和排序技术，并通过大量的上机实习，实现各种数据结构的算法，以便为后续课程的学习提供专业基础知识，同时增强学生编制程序的能力。 课程教学目标 通过本课程的学习，应达到以下目标： 深刻理解数据结构中线性表、栈、队和链的概念、算法及其基本应用。 理解树的基本概念，学会建立二叉树，并在二叉树上进行查找、插入和删除等各种运算。 理解图的基本结构和算法，了解图的路径问题。 熟练掌握几种重要的内部排序和查找技术，了解外部排序的一般过程。 能熟练地运用C语言，准确、清晰地编制与本课程有关的算法，并能上机调试通过。 新疆农业大学数据结构课程教案 第一讲 绪论(对应教材p1—p17) 一、教学目的和要求 要求掌握数据结构中基本概念的定义，理解数据结构研究的主要内容，了解抽象数据类型的表示和实现，理解算法评价的两个指标。 二、授课主要内容 1.数据结构研究的主要内容 2.数据结构中涉及的基本概念 3.算法的概念、描述方法以及评价标准 三、教学重点难点 数据结构中的基本概念、算法的概念、描述方法以及评价标准 四、授课内容和方法 【口述】当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 一、什么是数据结构 我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。 1、举例说明 图书馆的书目检索自动化问题----计算机处理的对象之间存在着线性关系，称为线性的数据结构。 人机对奕问题----计算机处理的对象是一个个格局。所有可能出现的格局是一棵倒置的树。 多岔路口交通灯的管理问题----数学模型是图的数学结构。 【由以上举例引出下列结论：】 非数值计算问题的数学模型是表、树和图之类的数据结构。【总结出定义】 数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。（三个要素：对象、关系及操作（运算）） 2、《数据结构》课程的介绍 1968年美国克努特教授开创了数据结构的最初体系： 数据的逻辑结构和存储结构及其操作。 数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。 二、基本概念和术语 1、数据 数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机 加工的“原料”。 数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。 2、数据对象、数据结构 数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构的形式定义：数据结构是一个二元组 Data_Structure=(D,S)其中，D 是数据元素的有限集，S 是D上关系的有限集。 例：复数 Complex=(C,R)例：课题小组 Group=(P,R)P={T,G1,„,Gn,S11,„,Snm}1≤n≤3，1≤m≤2，R={R1,R2} R1={ ① 逻辑结构：数据元素之间的逻辑关系。 ② 存储结构(物理结构)：数据元素及其关系在计算机存储器的表示。用于表示数据元素的位串称之为元素或结点。用于表示数据项的位串称之为数据域。 ③ 数据的运算：对数据施加的操作。 算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。 3、数据的两种存储结构： 顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。 链式存储结构：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，通常要借助于语言的指针类型来描述。 * 4、数据类型、抽象数据类型 数据类型:是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。 原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。 抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型： ① 原子类型:变量的值是不可分解的。 ② 固定聚合类型:变量的值由确定数目的成分按某种结构组成。③ 可变聚合类型:其值的成分数目不确定。 抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。 （D，S，P） D是数据对象，S是D上的关系集，P是对D的基本操作。 格式： ADT 抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 }ADT 抽象数据类型名。 数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 例： ADT Triplet{ 数据对象：D={e1，e2,e3 |e1,e2,e3∈Elemset(定义了关系运算的某个集合)} 数据关系：R1={〈e1,e2>, InitTriplet(&T,v1,v2,v3)DestroyTriplet（&T）Get（T,i,&e）Put(&T,i,e)IsAscending(T)IsDescending(T)Max(T,&e) Min(T,&e) }ADT Triplet 多形数据类型:是其值的成分不确定的数据类型。 三、抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 1、类C语言 精选了C 的一个子集，扩充修改，增强了语言的描述功能。 预定义常量和类型 数据结构的表示：存储结构用类型（typedef）定义来描述。 数据元素类型约定为ElemType. 基本操作的算法用函数描述： 函数类型 函数名（函数参数表）{ //算法说明 语句序列 }//函数名 增加了引用调用的参数传递方式。 赋值语句、选择语句、循环语句、结束语句、输入输出语句、注释语句 基本函数 逻辑运算约定 例：Triplet的表示和实现 //采用动态分配的顺序存储结构 Typedef ElemType * Triplet://由InitTriplet分配三个元素存储空间 //基本操作的函数原型说明 Status InitTriplet(Triplet &T,ElemType v1, ElemType v2, ElemType v3)Status DestroyTriplet（&T）Status Get（T,i,&e）Status Put(&T,i,e)Status IsAscending(T)Status IsDescending(T)Status Max(T,&e)Status Min(T,&e)//基本操作的实现 Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //构造三元组T，依次置T 的三个元素的处值为v1,v2和v3。 T=(ElemType)malloc(3*sizeof(ElemType));//分配三个元素的存储空间 If(!T)exit(OVERFLOW);//分配存储空间失败 T[0]=v1;T[1]=v2;T[2]=v3;return OK;}//InitTriplet Status DestroyTriplet（Triplet &T）{ //销毁三元组T。······ }//Min 四、算法和算法分析 1、算法（Algorithm） 是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五个重要特性：有穷性、确定性、可行性、输入、输出 2、算法设计的要求 正确性、可读性、健壮性和效率与低存储量要求 3、算法效率的度量 算法时间是由控制结构和原操作的决定的。做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），T（n）=O（f（n）） 它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长绿相同。 语句的频度：是该语句重复执行的次数。 例：求两个n阶方阵的乘积C=A×B，其算法如下： #define n 100 void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n]){ int i,j,k for(i=1;i<=n;++i)n+1 for(j=1;j<=n;++j)n*(n+1) C[i][j]=0;n2 for(k=1;k<=n,k++)n2(n+1) 3C[i][j]=C[i][j]+a[i][k]*b[k][j];n } } T(n)=2n3+3n2+2n+1 3limT(n)/ n=2 T(n)=O(n3)例： （a）{++x;s=0;}（b）for(i=1;i<=n;++i){++x;s+=x;}（c）for(j=1;j<=n;++j)for(k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的语句的频度分别为1,n和n2 时间复杂度是O(1),O(n)和O(n2)。时间复杂度有时与输入有关。 4、算法的存储空间需求 空间复杂度：S（n）=O（f（n）） 五、作业布置 复习回顾c语言中关于结构体和指针部分的内容，以便于后期学习。 六、教学后记 按2 学时讲完。 以前教学中反映出学生对抽象数据类型掌握不好，结构体知识基本不懂，所以要求学生课下自学，下次课抽1学时学习结构体和指针。 学生读程序能力差，循环嵌套分析不出执行次数。考虑布置了一道题目练习。 数据结构教案(供本科学生使用) 实验一 预备实验 1、实验目的 (1)练习C语言指针的用法 (2)练习C语言结构体的用法(3)练习C语言文件的用法 (3)理解时间复杂度分析的基本方法 2、实验内容 (1)用指针方式编写程序：从键盘输入N（比如10）个整形数据，并存入数组，要求将N个数中最大的数与第一个数交换；将其中最小的数最后一个数交换。熟练掌握用指针访问数据的方法。 (2)有M 个学生，每个学生的数据包括学号、姓名、三门课的成绩、平均分。要求从键盘依次输入M 个学生的学号、姓名、三门课的成绩，自动计算三门课的平均分数，并输出M 个学生的数据。复习C语言中结构体类型的定义及访问形式。 （3）将以上（1）、（2）中的数据存入数据文件进行相同的操作。复习语言课中文件的的使用。 （4）将本实验中所复习的知识，灵活应用到数据结构课程及实验中。 3、要求 （1）不写实验报告 （2）每位同学必须做完并经过检查方可。(3)时间两周，占课内2学时。 1--1 保密承诺书 致：（以下统称“贵方”） 本人姓名 居民身份证号码： 户籍地址： 通讯住址： 鉴于，本人在贵方任职，并获得贵方支付的相应报酬，本人就任职期间及离职以后保守贵方商业秘密的有关事项，出具本保密承诺书。承诺内容如下： 第一条本人确认，贵方商业秘密包括但不限于：1）有关贵方经营状况：包括但不限于投资前研究报告、可行性研究报告；与客户、合作伙伴的意向、合同、协议、章程等法律文件的内容；谈判方案、内容、会谈纪要、决议；业务渠道、供货来源、销售渠道、客户名单、中介单位；产品成本、交易价格、利润率；销售策略、方案；为客户制作的策划方案、咨询服务工作成果、设计方案以及设计图纸。2）有关贵方的生产状况：包括但不限于概念、专门技术、工艺、方法、设计、系统、方案、电路图、成本数据、计算机程序、公式、模式、开发或实验资料及贵方电脑、网络资料、生产配方等。3）有关贵方的财务状况：包括但不限于财务帐簿、报表；工资、奖金、福利分配方案；贵方的盈亏状况；银行帐号及存款等各种财 务资料；4）有关贵方的人事状况：包括但不限于企业人员档案资料；贵方内部重大人事变动；管理人员的个人信息；招聘裁员计划。5）有关贵方的重大决策与行动计划：包括但不限于投资计划、收购、兼并、合并、清算、破产、分立计划；准备进行的诉讼、仲裁行动；或未公开审理的诉讼、仲裁；企业形象设计，广告计划、活动安排。 本人确认，本承诺书之规定不妨碍贵方受有关商业秘密、商标、专利、著作权等知识产权法律之保护；本人在任职期间编制的、使用或持有的、与贵方有关的任何文件资料（包括但不限于所有往来书信、客户名单、笔记、备忘录、计划、图纸、设计、手册）、模具或样本均属于贵方所有。本人须在贵方要求时及在任职期完结时将上述文件（包括正本与副本）、模具和样本交还贵方或当场销毁，本人不得保留上述文件的任何复制文件。 本人确认，上述商业秘密无论以任何形式存放及价值如何，均视为其不为公众知悉、能够给贵方带来利益，并且已经由贵方采取了保密措施；本人确认贵方每月工资支付时已将贵方支付给本人的保密费用含于本人工资中发放，即本人基本工资中已包含了该保密费用项目。另外，本人确认贵方每月另行向本人支付了保密费用人民币_______元；本人声明，本人对此保密事项非常清晰，自愿受其约束，任何情况下，本人不就本保密费用是否足够提出任何异议。 第二条本人承诺，未经贵方同意，不得以泄露、告知、公布、发布、出版、传授、转让或者其他任何方式使任何第三方（包括不得知悉该项秘密的贵方其他职员）知悉属于贵方或者虽属于他人但贵方承诺有保密义务的秘密信息，也不得在履行职务之外使用这些秘密信息。 第三条本人承诺无论因何种原因离职，离职之后仍对本人在贵方任职期间接触、知悉的属于贵方或者虽属于第三方但贵方承诺有保密义务的秘密信息，承担如同任职期间一样的保密义务和不擅自使用有关秘密信息的义务。本人离职后承担保密义务的期限为无限期保密。 第四条本人承诺，在为贵方履行职务时，不得擅自使用为贵方所掌握且有保密义务的属于他人的商业秘密信息，亦不得擅自实施可能侵犯他人知识产权的行为。若本人违反上述任何一项承诺而导致贵方遭受第三方的侵权指控时，本人应当承担贵方因该侵权事宜而支付的一切费用；贵方因此而承担侵权赔偿责任的，有权向本人追偿。上述因诉讼发生之费用和侵权赔偿可以从本人的工资报酬中扣除。 第五条本人承诺，本人在贵方任职期间，非经贵方事先同意，不在与贵方生产、经营同类产品或提供同类服务的其他企业、事业单位、社会团体内担任任何职务包括股东、合伙人、董事、监事、经理、职员、代理人、顾问等，或者自己开业生产或经营同类产品，从事与贵方有竞争关系的同类业务，本人离职之后两年内仍负有前款的义务。本人确认贵方每月工资支付时已将贵方支付给本人的竞业限制补偿费用已含于本人基本工资中发放，即本人基本工资中已包含了该补偿费用项目。另外，本人确认贵方每月另行向本人支付了竞业限制费用人民币_______元；本人声明，本人对此竞业限制非常清晰，自愿受其约束，任何情况下，本人不就本竞业限制费用是否足够提出任何异议。 第六条本承诺书中的贵方，包括但不限于贵方、贵方的关联企业，具体企业名称：。 第七条本承诺书中的离职是指以任何一方明确表示解除或终止劳动关系。本人拒绝领取工资或停止履行职务的行为，视为提出辞职。 第八条本人若违反上述承诺中的任一项条款，贵方均有权不经预先告知立即解除与本人的聘用关系，同时本人应立即停止违约行为。本人承诺，若本人违反承诺内容，贵方可向本人追究责任。若因本承诺书所述保密或竞业限制事项而引起的法律纠纷或争议，贵方有权向公安机关报案或向人民法院提起诉讼。 第九条若本人违反上述保密或者竞业限制条款任一项条款的，应向贵方支付违约金五十万元；若因此给贵方造成损失而违约金不足以赔偿的，按所造成的经济损失赔偿；该违约金或赔偿金不包含本人给第三方所造成的损失。 第十条本人确认，在签署本承诺前已仔细审阅过承诺书的内容，并完全了解承诺书各条款的法律含义。本人确认本承诺书的法律效力向前的时间一直追及到本人入职贵方之日。本承诺书自本人签字之日起即生效。 特具此保密承诺书，以资严格遵守。 承诺人（签字）： 签署日期：年月日第三篇：数据结构讲稿-第一次课-DS绪论
第四篇：ds实验教案1
第五篇：保密承诺书 DS
点击咨询 