数据结构(1).doc

我对数据结构的认识 数据结构主要介绍一些常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的算法实现、并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件、和计算机硬件之间的一门计算机专业的核心课程，他是计算机程序设计、数据库、操作系统、编译原理及人工智能等重要基础，广泛的应用于信息学、系统工程等各种领域。 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据结构之间存在一种或多种特定关系的数据元素的集合，数据结构=数据元素+关系（结构），在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素之间的关系称为结构。根据数据元素之间的不同特性，通常有四类基本结构：集合、线性结构、树形结构、图状结构。四种关系是元素之间的逻辑关系，又称为逻辑结构。 数据元素之间在计算机中有两种不同的表示方法：顺序存储和链式存储，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。以下就是我对数据结构书中一些定义的总结（1） 数据 数据时信息的载体，是对客观事物的符号表示。（2） 数据结构 数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构是指数据之间的关系，及数据的组织形式。（3） 元素之间的逻辑关系，称为数据的逻辑结构。（4） 数据元素及其关系在计算机存储内的表示，称为数据的存储结构。（5） 线性结构是指数据元素之间存在“一对一”关系的逻辑结构。（6） 非线性结构是指数据元素之间存在“一对一”或“一对多”关系的逻辑结构。（7） 线性表 线性表示具有相同数据类型的n（n=0）个数据元素的有限序列。其逻辑特征反映了节点间一对一的关系，是一种线性结构。（8） 顺序表 用一组地址连续的存储单元依次顺序存储线性表的数据元素（相邻结存放相邻的物理位置），称为顺序表，它是一种随机存储结构，可以通过公式计算结点的存取地址。（9） 单链表 点链表的每个节点都有两个域，一个数据域和一个指针域，称之为单链表。（10） 双链表 以链表形式存储的线性表，其结点包含一个数据域和两个指针域，称之为双链表。（11） 循环链表 若线性链表的最后一个结点的指针指向头结点，使得链表头尾节点相连，就构成了循环链表。（12） 存储密度 结点数据本身所占的存储量与结点结构实际分配的存储量的比值，顺序表的存储密度为1，链表结构存储密度小于1。（13） 栈 只允许一端插入或删除操作的线性表称为栈。其最大特点是“先进后出”。（14） 顺序栈 采用顺序存储结构的栈为顺序栈。（15） 链栈 采用链式存储结构的栈称为链栈。（16） 队列 只允许在一端进行插入，另一端进行删除操作的线性表称为队列，其最大特点是“先进先出”。（17） 顺序队列 采用顺序存储结构的队列称为顺序队列。（18） 链队列 采用链式存储结构的队列称为链队列。（19） 循环队列 为了解决顺序队列中“假溢出”现象，将队列的存储空间想象成为一个首尾相连的环（即把对头元素和队尾元素链接起来），存储在其中的队列称为循环队列。（20） 字符串 由零个或多个字符组成的有限序列称为字符串（简称串）（21） 空白串 有一个或多个空格组成的串称为空白串（也称空格串）。（22） 空串 长度为零的字符串称为空串（23） 顺序串 串的顺序存储结构简称为顺序串。（24）链式串 串的链式存储结构简称为顺序串。（25）模式匹配 子串的定位运算又称为匹配模式。（26）结点 树的结点包含一个数据及若干指向其子树的分枝。（27）结点的度 结点所拥有的子树数称为该结点的度。（28）树的度 树中各结点度的最大值称为该树的度。（29）二叉树 一棵非空的二叉树，每个结点至多只有两棵子树，分别称为左子树和右子树，左右子树的次序不能任意交换，且左右子树分别又是一棵二叉树。（30）哈夫曼树 带权路径长度最小的二叉树，即最优二叉树，也成为哈夫曼树。（31）有向图 在一个图中，如果每条边都有方向，则称该图有向图。（31）无向图 在一个图中，如果每条边都没有方向，则称该图为无向图。（32）完全有向图 在一个有向图中，如果任意两顶点间都有方向互为相反的两条弧线相连接，则称该图为有向完全图。（33）最小生成树 若无向连通图是一个网，则它的所有生成树中必有一棵边的权之和为最小的生成树，简称为最小生成树。 栈堆栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。栈的主要特点是“先进后出”。堆栈的插入操作也称为进栈或入栈，堆栈的删除操作称为出栈或退栈，允许插入或删除的一端称栈顶，不允许插入或删除的一端称为栈底，顺序栈用一片连续的存储空间来存储栈中的数据元素，链栈是链式存储结构的栈。栈顶An . . .栈底 A2 A1队列队列是一种特殊的线性表，是一种只允许在表的一端进行插入操作而另一端进行删除操作的线性结构队列是一种特殊的线性表。是一种只允许在表的一端进行插入操作而另一端进行删除操作的线性结构。队列上可进行的主要操作有插入和删除，可通过使用数组或链接列表来实现队列，一个使用循环数组实现的队列能克服线型数组实现的队列的空间利用率问题，使用链式结构实现的队列也称为链队列。串串是在应用程序中使用的最频繁的数据类型之一，字符串简称串，是一种特殊的线性表其特殊性在于串的数据元素是一个个的字，长度为零的串称为空串，它不包含任何的字符，仅由一个或多个空格组成的串称为空白串。串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常在子串中首次出现时，该子串字符对应的主串中的序号定义为子串在主串中的序号。串提供的基本运算有：串比较、求子串、求串的长度、串连接、串定位、串插入、串删除。因为串是一种特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符，所以存储时有一些特殊的技巧。数组数组是由n（n=1）个相同类型的数据元素组成的有限序列，数组中的数据是按顺序存储在一块地址连续的内存单元中，数组可以看做是线性表的推广，一维数组为按顺序存储的线性表，二维数组为数据元素类型为一维数组的线性表.三维数组为数据元素类型为二维数组的数据表，以此类推。矩阵在科学算法和工程应用中被广泛使用，矩阵用二维数组来表示，在某些特殊的情况下，经常会出现一些阶数很高的矩阵，其中含有很多相同的元素或者零元素，为了节省存储空间，经常需要对这些矩阵进行压缩存储。需要进行压缩存储的矩阵有两种：特殊矩阵和稀疏矩阵，对特殊矩阵进行压缩存储时，矩阵中值相同的元素只分配一个存储空间，零元素不存储。对稀疏矩阵进行压缩存储时需要存储非零元素值的同时还要存储非零元素在矩阵中的位置，即非零元素的行数和列数，也就是在存储某个元素比如a值的同时，还需要存储该元素所在的行数i和列数j，这样就构成了三元组（I,j,aij）的线性表。在存储稀疏矩阵的三元线性表时，可以用稀疏矩阵的三元组顺序表存储，也可以用十字链表存储，稀疏矩阵的三元组顺序表除了存储三元组外，还应该存储矩阵行数和列数和总的非零元素数目，这样才能唯一的确定一个矩阵。十字链表为稀疏矩阵的每一行和列设置一个单独的链表。稀疏矩阵的每一个非零元素同时包含在两个链表中，十字链表的头指针指向链表的头结点。二叉树 二叉树的5种形态左子树（1） (2) (3) （4）右子树（5）右子树左子树满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。A CBFED GKJIH 一棵完全二叉树左孩子、右孩子、双亲 树中一个结点的子树的结点的根结点称为这个结点的孩子，这个结点称为它孩子的双亲，具有同一个双亲的孩子结点互称兄弟。结点的层数，规定树的根结点的层数为1，其余结点的层数等于它的双亲结点层数加1.排序交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止，应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕，常用的排序方法有直接选择排序和堆排序。归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序列，在内部排序中，