-
绪章绪论
“数据结构”是计算机程序设计中一门重要的理论技术基础课程，它不仅是计算机学科的核心课程，而且也是其他理工科专业的热门选修课。“数据结构”不仅涉及计算机硬件(特别是编码理论、存储装置和存取方法等)的研究范围，而且和计算机软件的研究有密切的关系。“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。著名计算机科学家沃思教授提出的公式：程序 = 算法 + 数据结构，也说明了数据结构的重要性。
-
●0.1课程简介
由王欣欣，冷玉池老师与大家共同学习，使用课本《数据结构实现教程》（C语言版）西安电子科技大学出版社出版。
-
●0.2数值计算和非数值计算应用问题
通过解决数值，非数值数据应用问题的分析，介绍了什么是数据结构。
-
●0.3什么是数据结构
通过解决数值，非数值数据应用问题的分析，介绍了什么是数据结构。
-
●0.4抽象数据类型和head1-1.h
讲解什么是抽象数据类型
，并介绍本书中的每章都要用的头文件head1_1.h。 -
●0.5基本概念和术语
对一些常用的概念和术语如数据，数据元素，数据对象，数据结构的逻辑结构及二元组表示进行介绍，这些概念和术语在以后的章节中会多次出现
-
●0.6编程---什么是引用参数&
介绍减少C语言编程的指针使用，提高编程效率，在Vs2010,vc+6.0编程环境下，可以使用引用符号&，介绍引用运算符&的使用方法。
-
●0.7算法和算法分析
算法与数据结构和程序的关系非常密切。进行程序设计时，先确定相应的数据结构，然后再根据数据结构和问题的需要设计相应的算法。只从特性、要求和时间复杂度等三个方面对算法进行介绍
-
第一章线性表
线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系是指数据元素之间的位置关系.本章介绍了线性表的概念，逻辑性质，抽象数据类型表示及其顺序存储结构，链式存储结构，并对相应存储方式的初始化、插入、删除等基本操作及其编程进行了详细深入讲解，最后介绍了其它线性表。
-
●1.1线性表的类型定义
介绍了线性表的概念，逻辑性质，抽象数据类型表示。
-
●1.2线性表的顺序存储的表示及其编程实现
介绍线性表的顺序存储结构，并用C语句进行表示，并介绍了C语言的动态分配函数。
-
●1.3线性表的顺序存储基本操作的编程实现
介绍顺序表的基本操作，如顺序表的初始化操作，插入，删除操作等，并用C语言对其编程实现，分步讲解C语句，并对宏定义，sizeof（），realloc（）函数等进行重点讲解。
-
●1.4顺序表应用综合举例
利用已实现的顺序表的运算组合可以实现其他更复杂的功能。
-
●1.5线性表的链式存储结构的表示和编程实现
介绍线性表的链式存储结构，介绍用线性表链式存储的基本操作，如插入操作，删除操作等，并用C语言对其表示实现，并分步讲解C语句，对其中的函数，头节点，地址域中地址的修改等语句等进行重点讲解。
-
●1.6单链表表应用综合举例
利用已实现的单链表的运算组合可以实现其他更复杂的功能。
-
●1.7双向链表
介绍双向链表的链式存储结构，介绍其基本操作，如插入操作，删除操作等，并用C语言对其表示实现，并分步对重点难点语句进行讲解。
-
●1.8循环链表和双向循环链表
循环链表和双向循环链表的定义，特征，判断表空的条件等。
-
●1.9线性表的应用--数字钟游戏的编写
线性表的应用--数字钟游戏的编写
-
●1.10实验编程---约瑟夫环问题
学会使用顺序表来解决算法的有关问题
-
第二章栈和队列
栈和队列是两种常用的数据结构，它们的逻辑结构与线性表相同，它们的特点在于线性运算受到了限制。如果对线性表中的数据按“后进先出”的规则进行操作，这种线性表结构叫做“栈”。如果对线性表中的数据按“先进先出”的规则进行操作，这种线性表结构叫做“队列”，因此，“栈”和“队列”这两种数据结构是运算受限制的线性表。
-
●2.1栈的定义
栈的逻辑定义，栈是一端操作受限的线性表，只在线性表的一端进行插入和删除操作，另一端不动。
-
●2.2栈的抽象数据类型定义
栈是一种数据结构，加上一组基本操作，就构成了栈的抽象数据类型。栈的抽象数据类型定义。
-
●2.3顺序栈
顺序栈即栈的顺序存储结构。用一组地址连续的存储单元依次存放自栈底至栈顶的数据元素，这种顺序存储方式实现的栈称为顺序栈。栈的顺序存储编程实现及其初始化操作及入栈操作编程实现。
-
●2.4链栈
用线性表的链式存储结构实现的栈称为链栈。链栈的操作易于实现，通常用单链表表示。栈的链式存储结构的表示及栈插入删除基本操作的编程实现。
-
●2.5栈的应用举例
栈在生活中应用广泛，在数制的转换中用到栈这个数据结构，这节以十进制和八进制的转换为例讲解栈数据结构的应用及编程实现。
-
●2.6队列的定义
队列的定义，性质，抽象数据类型表示，基本操作简介。还介绍了双端队列，及输入输出受限的双端队列。
-
●2.7顺序队
队列是一种先进先出的线性表(First In First Out，FIFO)，它只允许在表的一端进行插入操作，而在表的另一端进行删除操作，是一种运算受限制的线性表。队列的顺序存储表示及顺序队和循环队的工作原理。
-
●2.8链队
使用链式存储的队称为链队。链队的初始化操作，链队的插入及删除操作。
-
●2.9实验编程---十进制和其它进制的转换
使用顺序栈解决数值转换问题
-
第三章串
串(即字符串)是一种特殊的线性表，它的数据元素是单个字符。在计算机非数值处理的对象中，字符串数据是经常处理的对象，如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事务处理程序中，顾客的姓名、地址、货物的产地、名称等，一般也是作为字符串数据处理的；信息检索系统、文字编辑程序、问答系统、自然语言翻译系统都是以字符串数据作为处理对象的。在C语言中，有字符变量、字符串常量，但没有专门的字符串变量。这一章把串作为一个独立的数据结构概念加以研究，介绍串的存储结构及基本运算。
-
●3.1串和线性表的比较
串和线性表两种线性结构的比较。
-
●3.2串的定义及抽象数据类型定义
串的定义及抽象数据类型定义
-
●3.3串定长存储表示及实现
串定长存储表示及串基本算法的定长表示编程实现。
-
●3.4串的堆分配存储表示及实现
串的堆分配存储表示及插入算法编程实现。
-
●3.5实验编程---串操作的实现
顺序存储下串操作的实现
-
第四章树和二叉树
树是一种重要的非线性数据结构，直观地看，它是数据元素(在树中称为结点)按分支关系组织起来的结构，很像自然界中的树。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树型象地表示。树在计算机领域中也有广泛的应用，如在编译源程序时，可用树表示源程序的语法结构，在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述，如满二叉树、完全二叉树、排序二叉树。
-
●4.1树的基本概念
树的定义，树的特点及树的基本术语
-
●4.2二叉树
二叉树的定义，性质，两种特殊的二叉树及其二叉树的存储表示。
-
●4.3二叉树的遍历
遍历的定义，对二叉树的遍历及其三种遍历方法，并由遍历序列构造二叉树。
-
●4.4树和森林
介绍几种基本的树的存储方式，即双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。设定一定规则，就可用二叉树结构表示树和森林，本节讨论树和森林与二叉树之间的转换方法。
-
●4.5哈夫曼树
哈夫曼(Huffman)树，也称最优树，是一类带权路径长度最短的树，有着广泛应用。学会构造哈夫曼树及哈夫曼编码。
-
●4.6实验编程---先序中序遍历二叉树
学会使用二叉链表，采用递归发构造二叉树和遍历二叉树
-
第五章图
图(Graph)是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树型结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中的多个元素相关，但只能和上一层中的一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。因此，图的应用相当广泛，在自然科学、社会科学和人文科学等许多领域都有着非常广泛的应用。
-
●5.1图的基本概念
图由非空的顶点(Vertex)集合和描述顶点之间的关系——边(Edge)或弧(Arc)的集合组成。本节学习图的术语。
-
●5.2图的存储结构
图是一种复杂的数据结构，顶点之间是多对多的关系，即任意两个顶点之间都可能存在联系。所以无法用顶点在存储区的位置关系来表示顶点之间的联系，即顺序存储结构不能完全存储图的信息，但可以用数组来存储图的顶点信息。要存储顶点之间的关系可以使用链式存储结构或者二维数组。在实际应用中，应根据具体的图和需要进行操作设计恰当的结点结构和表结构。图的存储结构有多种，常用的有邻接矩阵、邻接表和十字链表等。
-
●5.3图的遍历
图的遍历是指从图中的某个顶点出发，按照某种顺序访问图中的每个顶点，使每个顶点被访问一次且仅被访问一次。图的遍历与树的遍历操作功能相似。图的遍历有深度优先遍历和广度优先遍历两种方式，它们对图和网都适用。
-
●5.4图的应用
许多应用问题都是一个求无向连通网的最小生成树问题。构造最小生成树的方法有许多种，典型的方法有两种，一种是普里姆(Prim)算法，一种是克鲁斯卡尔(Kruskal)算法。
-
●5.5实验编程---图的深度优先遍历
采用邻接矩阵，对图进行深度优先遍历和广度优先遍历
-
第六章查找
在日常生活中经常需要进行查找。比如，在英汉词典中查找某个英文单词的中文解释，在图书馆中查找一本书等。查找是为了得到某个信息而进行的工作。
在程序设计中，查找是对数据结构中的记录(和排序一样，在查找中把数据元素称为记录)进行处理时经常采用的一种操作。查找又称检索，是计算机科学中的重要研究课题之一，其目的就是从确定的数据结构中找出某个特定的记录。查找在程序中耗时最多，因此，一个好的查找方法会大大提高程序的运行速度。 -
●6.1基本概念和术语
查找(Search)是在数据结构中确定是否存在关键字等于给定关键字的记录的过程。学习查找的基本概念和术语。
-
●6.2静态查找表
由于静态查找不需要在静态查找表中插入或删除记录，静态查找表的数据结构是线性结构。本节介绍顺序查找，折半查找算法和索引顺序表的查找。
-
●6.3哈希表
哈希表(Hash Table)就是这样一种查找表，记录的关键字与记录存放位置之间的映射函数叫哈希函数。因此，哈希表是通过哈希函数来确定记录存放位置的一种数据结构。本节学习如何建立哈希表，及处理表冲突的方法。
-
●6.4实验编程---查询学生信息管理系统
顺序表下的顺序查找
-
第七章排序
排序(Sorting)是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。本章讲了排序算法的特性，主要讲解内部排序的各种排序方法。
-
●7.1排序的基本概念
排序(Sorting)是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序分为两类：内部排序和外部排序。为了便于读者理解，记录序列中只列出关键字部分，设待排序记录的关键字均为整数，则在以后讨论的大部分算法中，待排记录的数据类型也都介绍了。
-
●7.2插入排序---直接插入排序
直接插入排序(基于顺序查找)是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。本节介绍直接插入排序的算法及C语言编写。
-
●7.3插入排序---折半插入排序
在有序表中确定插入位置，还可以通过二分有序表的方法来确定插入位置，由此进行的插入排序称为折半插入排序。本节介绍折半排序算法及C语言编程。
-
●7.4插入排序---希尔排序
希尔排序又称缩小增量排序，是1959年由D. L. Shell提出来的，较前述几种插入排序方法有较大的改进。本节介绍希尔排序算法
-
●7.5交换排序---冒泡排序
本节介绍冒泡排序算法
-
●7.6交换排序---快速排序
本节介绍交换排序---快速排序算法
-
●7.7选择排序---简单选择排序
选择排序---简单选择排序
-
●7.8选择排序---树形选择排序
选择排序---树形选择排序
-
●7.9选择排序---堆排序
选择排序---堆排序
-
●7.10二路归并排序
堆排序举例
-
●7.11实验编程---学生信息管理系统中的排序
对记录项进行排序