大话数据结构读书笔记

一、数据结构绪论

• 逻辑结构与物理结构
  • 逻辑结构：集合、线性（一对一）、树（一对多）、图（多对多）
  • 物理结构：顺序存储结构、链式储存结构
• 抽象数据类型 （Abstract Data Type,ADT）：是指一个数学模型及定义在该模型上的一组操作 >　标准格式
  　　　 ADT 　抽象数据类型名
  　　　 Date 数据元素之间的逻辑定义
  Operation
  操作 1
  初始条件
  操作结果描述
  操作 2
  ……
  操作 3
  ……
  endADT

二、算法

• 算法特性：输入输出、确定性、又穷性、可行性
• 算法要求：正确性、健壮性、可读性、时间效率高和存储量低
• 算法时间复杂度
  • 推导大 O 阶方法

    1.用常数 1 取代运行时间中所有加法常数 2.在修改后的运行函数中，只保留最高位 3.如果最高阶项存在且不是 1，则去除与这个项相乘的常数
    得到的结果是大 O 阶

三、线性表

• 定义：零个或多个数据元素的有限序列
• 抽象数据结构

  ADT 线性表
  Data ：
  线性表的数据对象集合为{a1，a2，……，an}，每个元素的类型均为 DataType。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。      
  Operation：

InitList(&l)

操作结果：构造一个空的线性表 L

DestroyList(&l)

初始条件：线性表已存在         
操作结果：销毁线性表 L

ClearList(&l)

初始条件：线性表已存在         
操作结果：置线性表 L 为空表

ListEmpty(L)

初始条件：线性表已存在      
  操作结果：若线性表 L 为空表，则返回 TRUE，否则返回 FALSE

ListLenght(L)

初始条件：线性表已存在         
操作结果：返回线性表 L 数据元素个数

GetElem(L,i,&e)

初始条件：线性表已存在（1≤i≤ListLenght(L)）        
操作结果：用 e 返回线性表 L 中第 i 个数据元素的值

locatElem(L,e,comare())

初始条件：线性表已存在,comare()是数据元素判定函数         
操作结果：返回线性表 L 中第 1 个与 e 满足关系 comare()的数据元素的位序

PriorElem(L,cur_e,&pre_e)

初始条件：线性表已存在         
操作结果：若 cur_e 是线性表 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义

NextElem(L,cur_e,&)

初始条件：线性表已存在         
操作结果：若 cur_e 是线性表 L 的数据元素，且不是第最后一个，则用 next_e 返回它的后继，否则操作失败，next_e 无定义

ListInsert(&L,i,e)

初始条件：线性表已存在（1≤i≤ListLenght(L)+1）        
操作结果：在线性表 L 中第 i 个数据元素之前插入新元素 e，L 长度加 1

ListDelete(&L,i,&e)

初始条件：线性表已存在（1≤i≤ListLenght(L)）        
操作结果：删除线性表 L 中第 i 个数据元素，用 e 返回其值，L 长度减 1

ListTraverse(L,visit())

初始条件：线性表已存在         
操作结果：依次对线性表 L 的每个数据元素调用 visit()函数，一旦 visit()失败，则操作失败}ADT List

• 顺序储存结构代码
  #define MAXSIZE 20
  typedef int ElemType；
  typedef struct{
  ElemType data[MAXSIZE];
  int length;
  }SqList;

单链表、静态链表、循环链表、双向链表

• 单链表
• 单链表储存结构代码

  typedef struct node{
  ElemType data；
  struct Node *next；
  } Node；
  typedef struct Node *LinkList；

• 静态链表（早期没有指针，用数组代替指针）
• 静态链表的储存结构代码

  #define MAXSIZE 1000
  typedef struct{
  Elemtype data；
  int cur；/_游标_/
  }Component,StaticLinkList[MAXSIZE];

  头指针存放备用链表（后面空闲空间）第一个节点下标
  数组最后一个元素的cur用来存放头结点（第一个插入元素的下标）

• 循环链表
  将单链表中的终端结点的指针端由空指针改为指向头结点，链表就形成了一个环
• 双向链表
  • 双向链表的储存结构代码

    typedef Struct DulNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
    }DulNode,\*DuLinkList;

四、栈与队列

栈

• 栈的定义：限定仅在表尾进行插入和删除操作的线性表
• 栈的抽象数据类型 > ADT 栈（stack）
  Data ：
  同线性表
  Operation：

InitStack（*S）

初始化操作，建立一个空栈*S

DestroyStack（*S）

若栈存在，则销毁它

ClearStack（*S）

将栈清空

StackEmpty（*S）

若栈为空，则返回 true，反之返回 false

GetTop（S，*e）

若栈存在且非空，用 e 返回栈顶元素

Push（*S，e）

若栈存在，插入新元素 e 到栈 S 中并成为栈顶元素

Pop（S，e）

删除栈 S 中栈顶元素，并用 e 返回其值

StackLengh（S）

返回栈 S 的元素个数
endADT

• 栈的顺序存储结构

  typedef int SElemType；
  typedef struct{
  SElemtype data[MAXSIZE];
  int top;
  }SqStack；

• 两栈共享空间

typedef struct{
SElemType data[MAXSIZE];
int top1;
int top2;
}sqDoubleStack；

判断是否满栈

top1+1==top2

• 栈的链式存储结构

  typedef struct StackNode{
  SElemType data;
  struct StackNode *next;
  }StackNode,*LinkStackPtr;
  
     typedef struct LinkStack{
        LinkStack top;
        int count;
     }LinkStack；

• 栈的应用：
  四则运算表达式求值：后缀表示法(逆波兰表示法)。

队列

• 队列的定义：只允许在一端进行插入操作，而在另一端进行删除操作的线性表
• 队列的抽象数据类型

  ADT 队列（Queue）
  Data ：
  同线性表
  Operation：

InitQueue（*Q）

初始化操作，建立一个空队列*Q

DestroyQueue（*Q）

若队列存在，则销毁它

ClearQueue（*S）

将队列清空

QueueEmpty（*Q）

若队列为空，则返回 true，反之返回 false

GetHead（Q，*e）

若队列存在且非空，用 e 返回队头元素

EnQueue（*Q，e）

若队列 Q 存在，插入新元素 e 到队列 Q 中并成为队尾元素

DeQueue（Q，e）

删除队列 Q 中队头元素，并用 e 返回其值

QueueLengh（Q）

返回队列 Q 的元素个数
endADT

• 循环队列
  _ 定义：队列头尾相接
  _ 循环队列顺序存储结构
  typedef int QElemType；
  typedef struct{
  QElemType data[MAXSIZE];
  int front;
  int rear;
  }SqQueue;

  队列满的条件是
  ###### （rear+1）%QueueSize == front

• 队列的链式储存结构
  typedef int QElemType；
  typedef struct QNode{
  QElemType data；
  struct QNde *next；
  }QNode,*QueuePtr;
  typedef struct{
  QueuePtr font,rear;
  }LinkQueue；

五、串

• 串的定义：串是由零个或多个字符组成的有限序列，又名叫字符串
• 串的抽象数据结构

  ADT 串（string）
  Data
  串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
  Operation

StrAssign( &T, chars )

初始条件：chars 是字符串常量。     
操作结果：生成一个其值等于 chars 的串 T。

StrCopy( &T, S )

初始条件：串 S 存在。     
操作结果：由串 S 复制得串 T。

StrEmpty( S )

初始条件：串 S 存在。     
操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。    StrCompare( S, T )     
初始条件：串 S 和 T 存在。     
操作结果：若 S>T，则返回值>0；若 S=T，则返回值=0；若 S<T，则返回值<0。

StrLength( S )

初始条件：串 S 存在。     
操作结果：返回 S 的元素个数，称为串的长度。

ClearString( &S )

初始条件：串 S 存在。     
操作结果：将 S 清为空串。

Concat( &T, S1, S2 )

初始条件：串 S1 和 S2 存在。     
操作结果：用 T 返回由 S1 和 S2 联接而成的新串。

SubString( &Sub, S, pos, len )

初始条件：串 S 存在，1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1     
操作结果：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。

Index( S, T, pos )

初始条件：串 S 和 T 存在，T 是非空串，1≤pos≤StrLength(S)。     
操作结果：若主串 S 中存在和串 T 值相同的子串，则返回它在主串 S 中第 pos 个字符之后第一次出现的位置；否则函数值为 0。

Replace( &S, T, V )

初始条件：串 S，T 和 V 存在，T 是非空串。     
操作结果：用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串。    ###### StrInsert( &S, pos, T )     
初始条件：串 S 和 T 存在，1≤pos≤StrLength(S)+1。     
操作结果：在串 S 的第 pos 个字符之前插入串 T。

StrDelete( &S, pos, len )

初始条件：串 S 存在，1≤pos≤StrLength(S)-len+1。     
操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串。

DestroyString( &S )

初始条件：串 S 存在。     
操作结果：串 S 被销毁。
}
endADT

• 串的匹配
• 朴素匹配算法
  一个一个匹配
• kmp 模式匹配算法
  算法思想：利用已经匹配过的数据，创建一个 next 数组。避免重复遍历
  难点：理解 next 数组

六、树

• 树的定义

• 树是 n 个结点的有限集。n=0 时称为空树。在任何一棵非空树：
  （1）有且仅有一个特定的称为根的结点
  （2）当 n>1 时，其余结点可分为 m（m>0）个互不相交的有限集 t1、t2、……、tm，其中每一个集合本身又是一棵树，并且称为根的子树

• 结点的度：结点拥有的子树数，度为零的称为叶节点（终端结点）

  树的度是节点的度的最大值

• 结点的层次从根开始定义，根为第一层，树中结点的最大层次称为树的深度（高度）

• 树的抽象数据类型

  ADT 树（tree）
  Data

  树是由一个根节点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
  

  Operation
  endADT

• 树的存储结构

  • 双亲表示法
    #define MAX*TREE_SIZE 100
    typedef int ElemType;
    typedef struct PTNode{
    TElemType data；
    int parent；
    }PTNode；
    typedef struct
    {
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;/*根的位置和结点数_/
    }PTree;
  • 孩子表示法
    #define MAX_TREE_SIZE 100
    typedef int ElemType;
    typedef struct CTNode{
    int child；
    struct CTNode *next；
    }*ChildPtr；
    typedef struct
    {
    TElemType data；
    ChildPtr firstchild；
    }CTBox;
    typedef struct
    {
    CTbox nodes[MAX_TREE_SIZE];
    int r,n;
    }CTree;

    线性表储存结点元素，孩子链表的孩子结点 child 是数据域，储存某结点在表头数组中的下标。next 是指针域，用来存储指向某结点的下一个孩子的指针

  • 孩子兄弟表示法
    typedef int ElemType;
    typedef struct CSNode{
    TElemType data；
    struct CSNode firstchild，rightsib；
    }CSNode，*CSTree；

• 二叉树

  • 定义
    是 n 个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个跟结点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

  • 存储结构

    • 顺序储存结构
      从根节点开始遍历二叉树，遇到没有则置空
    • 二叉链表
      typedef struct BiTNode{
      TElemType data；
      struct BiTNode lchild，rchild；
      } BiTNode，*BiTree；

  • 遍历二叉树

    • 定义：从根节点出发，按照一定的次序依次访问二叉树中所有结点，使得每个结点被访问依次且仅被访问依次
    • 前序遍历

      根左右

    • 中序遍历

      左根右

    • 后序遍历

      左右根

  • 线索二叉树
    _ 定义：二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化
    _ 二叉树的线索存储结构
    typedef enum{Link,Thread} PointerTag;
    typedef struct BiThrNode
    {
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    PointerTag LTag;
    PointerTag RTag;
    } BiThrNode,_BiThrTree;
    _ 中序遍历线索化
    void InThreading(BiThrTree p）
    {
    if(p)  {  
     InThreading(p->lchild);//左子树线索化   
      if(!p->lchild){
    p->LTag=Thread;
    p->lchild=pre;}//前驱线索   
      if(!pre->rchild){
    pre->RTag=Thread;
    pre->rchild=p;}//后续线索    
    pre=p; //保持 pre 指向 p 的前驱    
    InThreading(p->rchild);//右子树线索化  
     }
    }//InThreading

    因为此时 p 结点的后继还没有访问到，因此只能对它的前驱界限 pre 的右指针 rchild 做判断，if（！pre->rchild）表示如果为空，则 p 就是 pre 的后继，于是 pre->rchild=p，并且设置 pre->RTag=Thread,完成后继结点的线索化

• 赫夫曼树

  • 定义 带权路径长度 wpl 最小的二叉树称为赫夫曼树（最优二叉树）
  • 算法描述

七、图

• 图的定义

  • 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E),其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合
  • 有向边（弧）：顶点 vi 到 vj 有方向，则称这条边为有向边
  • 简单图：不存在顶点到其自身的边，且同一条边不重复出现，则为简单图
  • 无向（有向）完全图：任意两个顶点之间都存在边
  • 权：与图的边或弧相关的数
  • 网：带权的图

• 回路（环）：第一个顶点到最后一个顶点相同的路径

• 简单路径：顶点不重复出现的路径

• 连通图：图中任意两个顶点都是连通的

• 连通分量：无向图中的极大连通子图

• 强连通图：在有向图中，对于每一对 vi，vj 从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图中的极大连通子图称做有向图的强连通分量。

• 图的抽象数据结构

  ADT 图（Graph）
  Data
  顶点的有穷非空集合和边的集合
  Operation
  endADT

• 图的储存结构

  • 邻接矩阵
    typedef char VertexType;
    typedef int EdgeType;
    #define MAXVEX 100
    #define INFINITY 65355
    typedef struct{
    VertexType vexs[MAXVEX];/顶点数组/
    EdegeType arc[MAXVEX][maxvex];
    int numVertexes,numEdges;
    }MGraph;

  • 邻接表

    与上一章的孩子表示法思路相同

         typedef char VertexType;
         typedef int EdgeType;
    
         typedef struct EdgeNode{
          int adjvex； /*邻接点域，存储该顶点的对应下标*/
          EdgeType weight；/*存储权值*/
          struct EdgeNode *next;
         }EdgeNode；
    
         typedef struct VertexNode{
          VertexType data；
          EdgeNode  firstedge；
         }VertexNode,AdjList[MAXVEX];
    
         typedef struct{
          AdjList adjList;
          int numVertexes,numEdges;
         }GraphAdjList;
    

  • 边集数组

边集数组]XO.png

 * 十字链表

【data、firstin、firstout】【tailvex、headvex、headlink、taillink】

十字链表

容易求得顶点的出度和入度

• 邻接多重表
  

邻接多重表

• 图的遍历
  • 深度优先遍历
    从图中某个顶点 v 出发，访问此顶点，然后从 v 的未被访问的邻接点出发，深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到（邻接表）
  • 广度优先遍历
    类似于树的前序遍历（队列）
• 最小生成树
  • （普里姆）prim 算法
  • （克鲁斯卡尔）kruskal 算法
• 最短路径
  • （地杰斯特拉）dijkstr 算法
  • （弗洛伊德）floyd 算法
• 拓扑排序

八、查找

• 顺序表查找
• 有序表查找
  • 有序查找
  • 斐波那契查找
  • 插值查找
• 线性索引查找
  • 稠密查找
  • 到排查找
  • 分块索引
• 二叉排序树
• 平衡二叉树
• 多路查找树（B 树）
• 散列表查找（哈希表）概述
• 散列函数构造方法
• 处理散列冲突方法
• 散列表的查找实现 #九、排序
• 冒泡排序
• 简单选择排序
• 直接插入排序
• 希尔排序
• 堆排序
• 归并排序
• 快速排序