数据结构(C语言版)

数据结构概述

数据结构是一门研究非数值运算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。抽象数据类型由数据对象,数据对象关系集和基本操作集。

  • 数据:在计算机科学中指所有能输入计算机中并被计算机程序处理的符号的总称。
  • 数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。如一本书的数目信息为一个数据元素,而一个数据元素又有许多数据项组成。数据项是不可分割的最小单位。
  • 数据对象:性质相同的数据元素的集合,是数据的一个子集。
  • 数据结构:是相互之间存在一种或多种特定关系的数据元素的结合。通常有四种基本结构:集合、线性结构、树形结构、图状结构或网状结构。

算法

算法有5个重要特性:有穷性、确定性、可行性、输入、输出。
算法设计的要求有:正确性、可读性、健壮性、效率与低存储需求。
算法效率的度量:

  • 时间复杂度:一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记做T(n) = O(f(n)
  • 空间复杂度,本书空间复杂度作为算法所需存储空间的度量,记做S(n) = O(f(n))

线性表

线性表是最常用且最简单的一种数据结构。一个线性表是N个数据元素的有限序列。

线性表的顺序表示和实现

线性表的顺序表示指用一组地址连续的存储单元依次存储线性表的数据元素(如数组等)。假设有a1~an个元素顺序组成线性表,要在ai处添加/删除一个元素,则必须移动n-i个元素。则该算法移动元素次数的期望为(n-1)/2和n/2,则算法的时间复杂度是O(n)。

线性链表

  • 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。每个数据元素称为一个结点,包含两个域:数据域、指针域。整个链表的存取必须从头指针开始,且最后一个结点的指针域为null
  • 循环链表是另一种形式的链式存储,其特点是表总最后一个结点指向第一个结点。
  • 双向链表,为克服单链表单向性的缺点,可利用双向链表,一个结点有两个指针域。

栈和队列

从数据结构看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,是操作受限的线性表。

栈(注意递归问题)

栈是限定仅在表尾进行插入或删除操作的线性表。即后进先出。表尾端有其特殊含义,称为栈顶,表头端称为栈底。插入元素叫入栈,删除栈底元素叫做出栈。栈的应用为迷宫求解问题、表达式求值(寄存运算符栈、寄存操作数栈)、实现递归(如求二叉树深度、N!)等。

队列

队列是一种先进先出的线性表。允许插入的一端叫做队尾,允许删除的一端称为队首。常用于排队的情况。

  • 链队列,即用链表表示的队列,一个队列需要两个分别指向队头和队尾的指针。
  • 循环对列。在循环链表的基础上,加上队首指针和队尾指针。

字符串

字符串是由零个或多个字符组成的有限序列,一般即为s = 'a1a2a3……an'
字符串在机内有三种表示方法:

  • 定长顺序存储表示,对字符串长度有限制。类似于线性表的顺序存储结构,用一组地址连续的存储单元存储字符串的字符序列。
  • 堆分配存储表示,对字符串长度没有限制。特点是以一组地址连续的存储单元存放字符串序列,但其存储空间是程序执行过程中动态分配的。
  • 串的块链存储表示。

数组和广义表

数组

数组一旦被定义,它的维数和维界就不再改变,即结构中的数据元素个数和元素间的关系不再变动。除了结构初始化和销毁外,只能存取元素和修改元素值。

矩阵的压缩存储

在数值分析中,常出现一些阶数很高的矩阵,同时矩阵中有很多相同的元素或者零元素(即稀疏矩阵),为了节省存储空间,可以对这类矩阵进行压缩存储。即:为多个值相同的元只分配一个存储空间(0元不分配空间)。采用三元组(x,y,value)顺序表对矩阵进行压缩。

广义表

广义表是线性表的推广。广义表LS的定义是一个递归的定义,如:LS=(a1(a2(a3,a4,a5)))
广义表非空时,称第一个元素a1为LS的表头,称其余元素组成的表是LS的表尾。表头可能是原子,也可能是列表。由于广义表中的数据元素可以具有不同的结构,因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可以由一个结点表示。广义表需要两种结构的结点,原子结点和表结点。一个表结点可由三个域组成:标志域、指示表头的指针域和知识表尾的指针域。一个原子结点需要:标志域和值域。

树和二叉树

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用。

树是n个结点的有限集,在任意一颗非空树中:1.有且仅有一个特定的称为根的结点。2.当n>1时,其余几点可分为m个互不相交的有限集,其中每个集合本身又是一棵树,并且被称为子树。结点拥有的子树数称为结点的度,度为0的根节点称为叶子或终端结点,不为0的结点称为非终端节点或分支结点。结点的子树的根称为该结点的孩子(child),该结点称为孩子的双亲(parent),同一个双亲的孩子之间称为兄弟(sibling)。树中结点的最大层次称为树的深度。根节点为第一层。
森林是m颗互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。

二叉树

二叉树是另一种树型结构,其特点是每个结点至多只有两颗子树,且二叉树的子树有左右之分,其次序不能任意颠倒。
一颗深度为k且有2的k次方减一个结点的二叉树称为满二叉树。从上到下,从左到右为满二叉树所有结点编号的称为完全二叉树。二叉树存储结构如下:

  • 顺序存储结构:仅适用于完全二叉树
  • 链式存储结构:二叉树的链表中的结点至少包含三个域:数据域和左右指针域,有时还要有双亲域。

遍历二叉树和线索二叉树

  • 遍历二叉树:按某条搜索路径巡访每个结点,且只访问一次。有先(根)序遍历、中序遍历和后序遍历。
  • 线索二叉树:对一个非线性结构进行线性化操作。一般链表存储结构为:左孩子指针域、数据、右孩子指针域。添加两个标志域:ltag、rtag。若结点有左子树,则ltag为0,lchild指示左孩子,否则,ltag为1,lchild指示前驱,若结点有右子树,则ltag为0,lchild指示右孩子,否则,ltag为1,lchild指示后继。

树和森林

树常用的存储结构:

  • 双亲表示法:每个结点中包含两项:数据和双亲结点指示。
  • 孩子表示法:每个结点可能有多棵树,则可用多重链表,即每个结点有多个指针域指向孩子。
  • 孩子兄弟表示法:又称二叉树表示法。链表中结点的两个链域分别指向该结点的每第一个孩子结点和下一个兄弟结点。

赫夫曼树及其应用

赫夫曼(Huffman)树,又称最优树,是一类带权路径长度最短的树,有着广泛的应用。带权路径长度可用wi*深度。

  • 构造赫夫曼树的方法为:选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树。新的二叉树的根节点的权值为左右子树上根节点的权值之和。
  • 赫夫曼编码:利用以上方法构造二叉树,并对其编码。如A(0) B(10) C(110) D(111)

图中的数据元素称为顶点,两个顶点之间的关系称为弧,弧有方向就称图为有向图,否则称无向图。顶点的度是和此顶点关联的顶点的个数。图的存储结构有:

  • 数组表示法:n个顶点,则为n*n维数组,0表示无关系,1表示有关系。
  • 邻接表:对图中每个顶点建立一个单链表,指向该顶点指向的所有的其他顶点。
  • 十字链表和邻接多重表。

图的遍历分为:深度优先搜素、广度优先搜素

查找

查找表是由同一类型的数据元素构成的集合。查找表分为静态查找表(查找是否存在、检索特定元素的属性)、动态查找表(查找并添加/删除)。
关键字:可唯一标识一个记录。次关键字可识别若干记录。

静态查找表

  1. 顺序表的查找。顺序表指顺序表或线性链表。顺序查找为从表中最后一个记录开始,逐个进行查找。O(n)
  2. 有序表的查找。折半查找,类似于二叉树。O(logn)
  3. 静态树表的查找。每条记录的查找概率不相等,根据权重选择折半记录。
  4. 索引顺序表的查找。记录是分块存储的,通过索引记录表可到达相应的块,再通过顺序查找进行查找。

动态查找表

  1. 二叉排序树。左子树<根节点<右子树。可能出现二叉树左右严重不平衡。平均二叉树的平均查找长度和logn是等数量级的。
  2. 平衡二叉树。平衡因子为左子树的深度减去右子树的深度。所有结结点的平衡因子都应该是-1、0、1。保持平衡可以通过更改根节点来实现。O(logn)
  3. B-树和B+树
  4. 键树,又称数字查找树。

哈希表

在查找时,如果可以根据一个对应关系,找到给定值K的像f(K),则不需要进行比较便可以直接取得所查记录。这个关系f称为哈希函数,这种表称为哈希表。

哈希函数的构造方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等。

内部排序

插入排序

  1. 直接插入排序:第i趟直接插入排序的操作为:在还有i-1个记录的有序子序列r[1……i-1]中插入一个记录r[i]以后,编程含有i个记录的有序子序列,插入位置查找的方法为从最大值/最小值开始进行依次判断。移动次数约为四分之n的平方。O(n2)
  2. 折半插入排序。仅减少了关键字间的比较次数,而记录的移动次数不变。O(n2)
  3. 2-路插入排序。是在折半插入的基础上再改进,即从两边排序。移动次数约为八分之n的平方。
  4. 表插入排序。使用链表,仅改变存储结构,不移动记录。O(n2)

  5. 希尔排序。先将整个待排记录分割为若干个子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对整体记录进行一次直接插入排序。它的时间是所取增量序列的函数,可以降低时间复杂度。

快速排序

  1. 起泡排序:左右比较,大的放后面,一轮下来,最大值排最后。依次可得次大值,最终得到排序序列。需进行n(n-1)/2次移动,并做等数量级的记录移动。O(n2)
  2. 快速排序是对起泡排序的一种改进。通过一趟排序,将待排数据分割成独立的两部分,在进行排序。分割方法可以为比第一个大的放右边,否则放左边。o(nlogn),并且被认为是在同数量级排序方法中,平均性能最好。

选择排序

  1. 简单选择排序法:把第一个数与其他所有数比较,获取最小值。然后排第二个……
  2. 树型选择排序、堆排序、归并排序等。

其他排序

归并排序、基数排序等

排序方法 平均情 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
堆排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(1) 不稳定
归并排序 O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n) 稳定
快速排序 O(n*log(n)) O(n*log(n)) O(n^2) O(1) 不稳定