轻松学章数据结构.pptxVIP

第21章数据结构在计算机系统中，信息是以数据的形式处理的。在开发程序的时候，如何选择不同的数据结构，会直接影响到算法的选择和效率。要提高数据处理效率，且节省存储空间，如何组织数据就成了关键问题。而数据结构用来反映一个数据的内部构成，即数据由哪些成分构成，以什么方式构成，是什么结构。数据结构就是研究数据的逻辑结构和物理结构，以及它们之间的相互关系，并对这种结构定义相应的运算。

21.1线性表及其应用数据结构在计算机中有两种不同的表示方式，即顺序结构和非顺序结构，分别对应着顺序存储结构和链式存储结构。顺序存储结构，就是在存储器中以元素之间的相对位置来表示其之间的逻辑关系。链式存储结构是指在每个元素中增加一个指针，用于表示元素之间的逻辑关系。在数据结构中，线性表是由n个元素（结点）组成的有限序列，其格式如下。(a1,a2,a3…an)//n为顺序表的长度

21.2链表及其应用链表是指用任意的一组存储单元来存放线性表的结点，这些存储单元可以是连续的，也可以是不连续的，分布在内存中的任意位置上。正是因为这种特性，需要在存储链表的每个结点值的时候，存储其直接后继的地址，而这个地址通常是由指针来实现的。由此可以看出，链表的结点是由两部分构成，如图21-1所示。其中，数据用于存放结点的值，指针用于存放后继结点的地址。由于开始结点没有直接前驱，所以需要设置一个head指针指向开始结点，而由于结束结点没有后继，所以指针设为NULL，如图21-2所示。

21.3堆栈及其应用在前面章节的讨论中可知，局部变量的存储是放在堆栈当中，那什么是栈呢？不同于线性表，栈是限制在表的一端，进行插入和删除运算的线性表，进行插入和删除的这一端称为栈顶，另一端称为栈底，当表中没有元素时称为空栈。对栈中元素操作需要遵循后进先出的原则（LIFO），因此每次删除即出栈的元素应是栈顶元素，如图21-3所示。由于栈是操作受限的线性表，所以在栈上的操作包括构造栈、销毁栈、清空栈、计算栈长度、取栈顶元素、元素压栈和元素弹栈。

21.4队列及其应用队列也是一种运算受限的线性表。与栈不同，在表的一端进行插入，而在另一端进行删除。删除的一端称为队头，插入的一端称为队尾。队列的特性很像现实生活中所常见的排队，先进入队列的人先离开队列，也就是常说的先进先出（FIFO），队列的操作需要依据先进先出的原则进行，如图21-4所示。队列上的操作包括构造队列、销毁队列、清空队列、计算队列长度、取对头元素、元素入队和元素出队。

21.5特殊矩阵、广义表及其应用特殊矩阵就是相同元素或者零元素分布有一定规律的矩阵。对称矩阵、三角矩阵都属于特殊矩阵。下面来介绍对称矩阵的压缩。对于任意给定的下标(i,j)，可以惟一确定其在数组中存放的位置，相反，若给出数组中存储位置，则可以推断出其存储元素的下标，如图21-5所示。广义表又称列表，是线性表的推广，形式如下。LS=(a1,a2,a3,…,an)

21.6二叉树及其应用二叉树是一种特殊的树型结构，如图21-6所示，其有以下特点。具有惟一的一个根结点。每个结点至多有两个子树。子树有左右之分，顺序不能颠倒。（a）完全二叉树（b）满二叉树

21.7散列结构及其应用散列结构是指元素的存储位置和元素的关键字之间有一个确定的关系f，使得每个关键字与惟一的一个存储位置相对应。在查找的时候，用函数f得出给定关键字K的f(K)，若记录中存在K，则一定存放在f(K)位置上。

21.8图及其应用图结构的存储一般分为两种：邻接链表和邻接矩阵。图21-8中，有向图的两种存储方式如图21-9所示。图21-8无向图和有向图图21-9有向图的邻接链表和邻接矩阵

21.9小结本章简单介绍了数据结构中的基本内容，简单讨论了线性结构的线性表和队列的插入及删除操作，也描述了树和图等非线性结构特点。这些结构对解决实际应用问题具有重要的作用，读者可以在此基础上对数据结构进行深入的学习。