大话数据结构读书笔记

开始

此博客为《大话数据结构》这本书的读书笔记,方便日后复习使用。

第二章 算法

算法定义

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

算法的特性

算法应有一个或多个输入,且有一个或多个输出。算法在执行有限的步骤后,自动结束而不会出现无限循环,并且每个步骤在可接受的事件完成。算法的每一步骤都具有确定的含义,不会出现二义性。算法的每一步都必须是可行的,也就是说,每一步都能通过执行有限次数完成。

算法设计的要求

正确性

算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案。

可读性

算法设计的另一个目的是为了便于阅读,理解和交流。

健壮性

当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。

时间效率高和存储量低

时间效率指的是算法执行时间,对于同一个问题,如果有多个算法能够解决,执行时间短的算法效率高,执行时间长的效率低。存储需求指的是算法在执行过程中需要的最大存储空间,主要指的是算法程序运行时所占用的内存或外部硬盘存储空间。

函数的渐进增长

给定两个函数 f(n) 和 g(n),如果存在一个整数 N,使得对于所有的 n > N,f(n) 总是比 g(n) 大,那么,我们说 f(n) 的渐进增长快于 g(n)。

算法时间复杂度

算法时间复杂度定义

在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度,也就是算法的时间量度,记住:T(n) = O(f(n))。 它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。

推倒大 O 阶方法

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

得到的结果就是大 O 阶。

O(1) 常数阶,O(logn) 对数阶,O(n) 线性阶,O(n的平方) 平方阶 …..等等

第三章 线性表

线性表的定义

零个或多个数据元素的有限序列。

若将线性表记为 (a1,….,a-1,ai,a+1,…,an),则表中 ai-1 领先于 ai,ai 领先于 ai+1,称 ai-1 是 ai 的直接前驱元素,ai+1 是 ai 的直接后继元素。

线性表元素的个数 n(n >= 0) 定义为线性表的长度,当 n = 0 时,称为空表。

线性表的顺序存储结构

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

1
2
3
4
5
6
7
8
9
10
11

//存储空间初始分配量
#define MAXSIZE 20
//ElemType 类型根据实际情况而定,这里暂定 int
typedef int ElemType;
typedef struct{
//数组存储数据元素,最大值为 MAXSIZE
ElemType data[MAXSIZE]
//线性表当前长度
int lenght;
}SqList;

线性表的操作

获取操作

1
2
3
4
5
6
7
8
9
10
11
12
13

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

Status GetElem(SqList L,int i,ElemType *e){
if(L.length == 0 || i < 1 || i > L.length) return ERROR;
*e = L.data[i-1]
return OK;
}

插入操作

  1. 如果插入位置不合理,抛出异常。
  2. 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量。
  3. 从最后一个元素开始向前遍历到第 i 个位置,分别将它们都向后移动一个位置。
  4. 将要插入元素填入 i 处。
  5. 表长加 1。
1
2
3
4
5
6
7
8
9
10
11
12
13

Status ListInsert(SqList *L,int i,ElemType e){
int k;
if(L->length == MAXSIZE) return ERROR;
if(i < 1 || i > L->length+1) return ERROR;
if(i <= L->lenght){
for(k=L->length-1;k>=i-1;k--)
L->data[k+1] = L->data[k];
}
L->data[i-1] = e;
L->length++;
return OK;
}

删除操作

  1. 如果删除位置不合理,抛出异常。
  2. 取出删除元素。
  3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
  4. 表长减 1。
1
2
3
4
5
6
7
8
9
10
11
12
13

Status ListDelete(SqList *L,int i,ElemType *e){
int k;
if (L->length == 0) return ERROR;
if (i < 1 || i > L->length) return ERROR;
*e = L->data[i-1];
if(i < L->length){
for(k = i;k < L->length; k++)
L->data[k-1] = L->data[k];
}
L->length--;
return OK;
}

线性存储结构的优缺点

优点

  1. 无须为表示表中之间的逻辑关系而增加额外的存储空间。
  2. 可以快速的存取表中任一位置的元素。

缺点

  1. 插入和删除操作需要移动大量元素。
  2. 当线性表长度变化较大时,难以确定存储空间的容量。
  3. 造成存储空间的”碎片”。

线性表的链式存储结构

为了表示每个数据元素 ai 与其直接后继续元素 ai+1 之间的逻辑关系,对数据元素 ai 来说,除了存储本身信息之外,还需要存储一个指示其直接后继的消息(即直接后继的存储位置)。我们把存储数据元素消息的域称为 数据域,把存储直接后继位置的域称为指针域。指针域中存储的消息被称作指针或链。这两部分信息组成数据元素 ai 的存储映象,称为节点(Node)。

n 个节点(ai 的存储映象)链接成一个链表,即为线性表(a1,a2,…,an)的链式存储结构,因为此链表的每个节点中只包含一个指针域,所以叫做单链表。

链表中第一个节点的存储位置叫做头指针。

头指针与头结点区别

头指针

  1. 头指针是指链表中指向第一个节点指针,若链表有头结点,则是指向头结点的指针。
  2. 头指针具有标识作用,所以常用头指针冠以链表的名字。
  3. 无论链表是否为空,头指针均不为空,头指针是链表的必要元素,

头节点

  1. 头节点是为了操作的统一和方便而设立的,放在第一个元素的节点之前,其数据域一般无意义(也可存储链表的长度)。
  2. 有了头结点,对在第一元素节点前插入节点和删除第一节点,其操作与其他节点的操作就统一了。
  3. 头节点不一定是链表必须要素。

线性表链式存储结构代码描述

1
2
3
4
5
6

typedef struct Node{
ElemType data;
struct Node *next;
} Node;
typedef struct Node *LinkList;

单链表的读取

  1. 声明一个指针 p 指向链表第一个节点,初始化 j 从 1 开始。
  2. 当 j < 1 时,就遍历链表,让 p 的指针向后移动,不断指向一下个节点,j 累加 1.
  3. 若到链表末尾 p 为空,则说明第 i 个节点不存储。
  4. 否者查找成功,返回节点 p 的数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Status GetElem(LinkList L,int i,ElemType *e){
int j;
LinkList p;
p = L->next;
j = 1;
while(p && j<i){
p = p->next;
++j;
}
if(!p||j>i) return ERROR;
*e = p->data;
return OK;
}

单链表的插入

  1. 声明一个指针 p 指向链表头节点,初始化 j 从 1 开始。
  2. 当 j < 1 时,就遍历链表,让 p 的指针向后移动,不断指向下一个节点,j 累加 1。
  3. 若到链表末尾 p 为空,则说明第 i 个节点不存在。
  4. 否则查找成功,在系统生成一个空节点 s。
  5. 将数据元素 e 赋值给 s->data。
  6. 单链表的插入标准语句 s->next = p->next p->next=s。
  7. 返回成功。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Status ListInsert (LinkList *L,int i,ElemType e){
int j;
LinkList p,sl
p = *L;
j = 1;
while(p && j<i){
p = p->next;
++j;
}
if(!p||j>i)return ERROR;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}

单链表的删除

  1. 声明一个指针 p 指向链表头结点,初始化 j 从 1 开始。
  2. 当 j < 1 时,就遍历链表,让 p 的指针向后移动,不断指向下一个节点,j 累加 1。
  3. 若到链表末尾 p 为空,则说明第 i 个节点不存在。
  4. 否则查找成功,将欲删除的节点 p->next 赋值给 q。
  5. 单链表的删除标准语法 p->next = q -> next;
  6. 将 q 节点中的数据赋值给 e,作为返回。
  7. 释放 q 节点。
  8. 返回成功。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Status ListDelete(LinkList *L,int i,ElemType *e){
int j;
LinkList p,q;
p = *L;
j = 1;
while(p->next && j < i){
p = p->next
++j;
}
if(!(p->next) || j >i) return ERROR.
q = p->next;
p->next = q->next;
*e = q->data;
free(q)
return OK;
}

单链表的整表创建

  1. 声明一指针 p 和计数器变量 i。
  2. 随机生成一数字赋值给 p 的数据域 p->data。
  3. 将 p 插入到头节点与前一新节点之间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//头差法
LinkList p;
int i;
srand(time(0));
* L = (LinkList)malloc(sizeof(Node));
(*L) -> next = NULL;
for(i = 0; i < n; i++){
p = (LinkList)malloc(sizeof(Node));
p->data =rand()%100+1;
p->next = (*L) -> next;
(*L)->next = p;
}

//尾插法

LinkList p,r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(i=0;i<n;i++){
p = (Node * )malloc(sizeof(Node))
p->data = rand()%100+1;
r->next=p;
r = p;
}
r->next = NULL;

单链表的整表删除

  1. 声明一节点 p 和 q。
  2. 将第一个节点赋值给 p。
  3. 循环: 将下一个节点赋值给 q,释放 p,将 q 赋值给 p。
1
2
3
4
5
6
7
8
9
10
11
12

Status ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;
return OK;
}

单链表结构与顺序存储结构优缺点

存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据。
  • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。

时间性能

  • 查询
    • 顺序存储结构 O(1)
    • 单链表 O(n)
  • 插入和删除
    • 顺序存储结构需要平均移动表长一半的元素,时间为 O(n)
    • 单链表在线出某位置的指针后,插入和删除时间仅为 O(1)

控件性能

  • 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢。
  • 单链表不需要分配存储控件,只要有就可以分配,元素个数也不受限制。

第六章 树

树的定义

树是 n 个节点的有限集。n = 0 时称为空树。在任意一个课空树中:有且仅有一个特定的称为根的节点,当 n > 1 时,其余节点可分为 m 个互不相交的有限集,其中每一格集合本身又是一颗树,并且称为根的子树。

节点分类

节点拥有的子树称为节点的度。度为 0 节点称为叶子节点或终端节点,度不为 0 的节点称为非终端节点或分支节点。除了根节点之外,分支节点也称为内部节点。树的度是树内各节点的度的最大值。

节点间的关系

节点的子树的根称为该节点的孩子,该节点称为孩子的双亲。同一个双亲的孩子之间互称兄弟,节点的祖先是从根到该节点所有分支上的所有节点。以某节点为根的子树中的任一节点都称为该节点的子孙。

树的其他相关概念

节点的层次从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的节点互为堂兄弟。树中节点的最大层次称为树的深度或高度。如果将树中节点的各子树看成从左至右是有次序的,不能互换的,这称该树为有序树,否者称为无序树。森林是 m 颗互补相交的树的集合。

线性结构

  1. 第一个数据元素:无前驱
  2. 最后一个数据元素:无后继
  3. 中间元素:一个前驱一个后继

树结构

  1. 根节点:无双亲,唯一
  2. 叶节点,无孩子,可以多个
  3. 中间节点:一个双亲多个孩子

树的存储结构

双亲表示法

使用一组连续空间存储树的节点,每个节点中,使用一个指示器指示其双亲节点在数组中的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//树的双亲表示法

#define MAX_TREE_SIZE 100
//数节点的数据类型
typedef int TElemType;
//节点结构
typedef struct PTNode{
//节点数据
TElemType data;
//双亲位置
int parent;
} PTNode;

//树结构
typedef struct{
//节点数组
PTNode nodes[MAX_TREE_SIZE]
//根的位置和节点数
int r,n;
} PTREE;
孩子表示法

把每个节点的孩子节点排列起来,以单链表作存储结构,则 n 个节点有 n 个孩子链表,如果是叶子节点则此单链表 为空,然后 n 个头指针有组成一个线性表,采用顺序存储结构,存放进一个一维数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//树的孩子表示法结构定义
#define MAX_TREE_SIZE 100

//孩子节点
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;
孩子兄弟表示法

任意一颗树,它的节点的第一个孩子如果存在就是为一个,它的有兄弟如果存在就是唯一的。因此,我们设置两个指针,分别指向该节点的第一个孩子和此及接待你的有兄弟。

1
2
3
4
5

typedef struct CSNode{
TElemType data;
struct CSNode *firstchild,*rightsib;
} CSNode,*CSTree;

二叉树的定义

二叉树是 n 个节点的有限集合,该集合或者为空集,或者由一个根节点和两颗互补相交的,分别称为根节点的左子树和右子树的二叉树组成。每个节点最多有两颗子树,左子树和右子树是有顺序的,次序不能任意颠倒,即使树中某节点只有一颗子树,也要区分它是左子树还是右子树。

所有的节点只有左子树的二叉树叫左斜树,所有节点只有右子树的二叉树叫做右斜树,这两者统称为斜树。

在一颗二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

在一颗具有 n 个节点的二叉树按层序编号,如果编号为 i 的节点与同样深度满二叉树中编号 i 的节点在二叉树中位置完全相同,则这颗二叉树称为完全二叉树。满二叉树一定是一颗完全二叉树,而完全二叉树不一定是满二叉树。

完全二叉树的特点:

  1. 叶子节点只能出现在最下层
  2. 最下层的叶子节点一定集中左部连续位置
  3. 倒数第二次,若有叶子节点,一定都在右部连续位置
  4. 如果节点度为 1,则该节点只有左孩子,即不存在只有右子树的情况
  5. 同样节点的二叉树,完全二叉树的深度最小

二叉树的性质

在二叉树的第 i 层上至多有 2 的 i - 1 次方个节点 (i >= 1)。

深度为 k 的二叉树至多有 2 的 k 次方 -1 个节点 (i >= 1)。

对任何一颗二叉树 T,如果其终端节点为 n0,度为 2 的节点数 为 n2,则 n0 = n2 + 1。

具有 n 个节点的完全二叉树的深度为 [log2n] + 1 ([x] 表示不大于 x 的最大整数)

如果对一颗有 n 个节点的完全二叉树的节点按层序编号,对任一节点 i ,如果 i = 1,则节点 i 是二叉树的根,如果 i > 1,则其双亲是节点 [i/2]。如果 2i > n,则节点 i 无左孩子,否者其左孩子是节点 2i。如果 2i+1>n,则节点 i 无右孩子,否者其右孩子是节点 2i+1。

二叉树的存储结构

二叉树的顺序存储结构

将整个二叉树存入到数组中,相应的下标对应其同样的位置。

二叉树的链式存储结构

二叉树每个节点最多有两个孩子,所以为它设计一个数据域和两个指针域。

1
2
3
4
5
6
7
8
9
10

//二叉树的二叉链表节点定义

//节点结构
typedef struct BiTNode{
//节点数据
TElemType data;
//左右孩子指针
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

遍历二叉树

二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中所有节点,使得每个节点被访一次且仅被访问一次。

前序遍历

规则是若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,再前序遍历右子树。

中序遍历

规则是若树为空,则空操作返回,否则从根节点开始(注意并不是先访问根节点),中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树。

倒序遍历

规则是若树为空,则空操作返回,否则从左到右先叶子后节点的方式遍历访问左右子树,最后访问根节点。

层序遍历

规则是若树为空,则空操作返回,否则从树的第一层,也就是根节点开始访问,从上而下的逐层遍历,在同一层中,按从左到右的顺序对节点逐个访问。

前序遍历代码实现
1
2
3
4
5
6
7
8

void PreOrderTraverse(BiTree T){
if(T == NULL)
return;
printf("%c",T->data)
PreOrderTraverse(T->lchild)
PreOrderTraverse(T->rchild)
}
中序遍历代码实现
1
2
3
4
5
6
7
8

void InOrderTraverse(BiTree T){
if(T == NULL)
return;
InOrderTraverse(T->left)
printf("%c",T->data)
InOrderTraverse(T->right)
}