实用算法前三章笔记

发表于 | 分类于
字数统计: 2,432

CH0

参考书：

  • 《程序员实用算法》
  • 《编程珠玑》(第二版)
  • 《算法导论》

课前：阅读代码并验证其性能，调研STL库

课后：加深对算法设计思想的理解。(自己理解了一个问题跟用自己的话向别人解释是有很大区别的)

本课程的重点：依据问题定义、输入数据的特征和要求输出的数据的特征，分析广泛的解决方案（数据结构+算法），并选择最佳的解决方案

CH1 绪论

重点：算法的概念、算法与相关术语的关联
难点：算法时间复杂度的估算

什么是算法：

  • 描述了特定问题的有限求解步骤；
  • 指为了解决特定问题，而操作数据的方式；
  • 指求解问题的策略

五大特征：有穷性、确定性、可行性、零或多个输入、一或多个输出

五大要求：正确性、可读性、健壮性、高效率、低存储

程序： 指为计算机处理问题而编制的一组指令

算法 + 数据结构 = 程序

数据结构

  • 性质相同的数据元素的有限集合及其上的关系的有限集合（数据+结构）
  • 是描述现实世界实体的数据模型及其上的操作在计算机上的表示和实现
  • 包括逻辑结构和存储结构/物理结构

数据类型：系统定义的int, char等，用户自定义的struct类型。也可采用typedef将类型名重命名，以增加代码的可读
性。

数据结构的选择是与具体问题以及相应的约束密切相关的。

而且有时候采用一些特殊的存储结构，可以使得解决算法相当巧妙。

时间复杂度

一般我们用大O来进行比较，但是这只是一个大致的比较，在相差比较大的时候很有用。如果两个算法的大O是一样，则还要从实际运算时间去比较，因为可能有的语句涉及到了调用，本身需要多步执行，这样在实际运行的时候就会有很大的差异。

另外数据本身的规律也会影响时间复杂度，如在排序算法中经常会比较最好和最坏情况。

空间复杂度

内存 + 栈空间

经典的节省空间方法：bitmap

通过在C++中对分配空间后的地址进行计算，可得知每次分配的内存实际上都是大于数据类型本身的大小的。在这里，是直接算的首末地址的差值，注意与用sizeof的时候涉及的数据对齐问题相区别。

申请1~8B：实际分配32B；申请9~16B：实际分配40B；申请17~24B：实际分配48B。申请分配内存空间1次，额外开销为： 24~31B

由此看见，每一次分配内存实际都会有额外的开销，会降低Cache的存储密度从而降低算法的执行性能，同时内存的分配和销毁也是一个耗时的工作。要尽量减少分配内存的次数，可以用内存池等方法来解决。

代码优化

  • 尽量减少输入输出
    • 扩展缓冲区
  • 减少函数调用的次数
  • 限制计算密集型操作（浮点运算，除法运算）；
  • 确定最耗时的操作，并提高其性能
    • 可用测量和跟踪工具（如， Profiler，AQTime）

影响选择算法的决定性因素

  • 问题时间和空间的约束
  • 存何种信息，数据结构
  • 输入输出数据的特征

CH2 线性表

参考: 实用算法第2章 编程珠玑 1.4 13.4

重点：理解线性表的逻辑特点；掌握线性表两种存储结构的特点、实现（C定义）及其基本操作的实现、适用范围；掌握算法的描述方法：伪代码和算法流程图；会粗略分析算法的时间复杂度（三种情况下）和内存开销。

难点：对于给定的应用需求——设计数据结构的一般过程

  1. 判断是否需要用到DS？——操作对象为：取值为同种类型的很多数据，且这些数据间存在某种关系 或者 某些共性操作
  2. 判断是否适合用线性表来刻画同类数据之间的关系？（逻辑结构）——被操作的数据之间没有天然的一对多 和 多对多的关系 ；对已存储的数据进行处理时，处理顺序 有明显的唯一的先后次序关系
  3. 设计线性表的存储结构（包括：存储哪些数据（包括数据类型和取值）？顺序存储/链式存储的选择？） （数据+存储结构）——取决于数据处理时的最频繁操作，为静态操作，还是动态操作？
  4. 编码实现数据的存储结构—— 学会画图设计DS并实现
  5. 利用线性表的基本操作来解决问题

四类数据结构：

  • 集合：元素间无任何关系，即关系集合是空集： S={} 如C中的枚举
  • 线性：1:1
  • 树形：1:n
  • 图形：n:n

图形渲染的例子： 红 —— 线性 紫—— 树形

基本操作

  • 创建空的线性表
  • 销毁已有线性表
  • 查找直接后继和直接前驱
  • 插入一个元素
  • 删除一个元素

存储结构：顺序表和链表两种方式

健壮性：从数据操作的位置 和 空间是否上溢或下溢 两个方面来考虑

顺序表

在内存中连续存储的线性表 ，用下标来表明线性特征

静态定义：数组
1
2
3
4
5
#define List_Size 100/*分配空间的大小*/
Typedef Struct{
int elem[List_Size ]; /*存储空间*/
int len; /*实际长度*/
}SqList_static;

类似STL:vector

在编译的时候， 系统在函数栈中分配连续的内存空间。当静态顺序表所在的函数执行完毕后，由系统来回收所开辟的内存空间。

缺点：空间分配不够灵活

动态定义：指针
1
2
3
4
5
6
#define List_Size 100 /*分配空间的大小*/
typedef struct{
int *elem; /*顺序表的存储空间*/
int len; /*实际长度*/
int ListSize ; /*当前分配的空间大小*/
} Sqlist;

用malloc() realloc() free() 手动管理空间分配，实现了灵活，但增加了开销——CH1 中的内容可知，每次分配内容都是有额外开销的

malloc原理 关于malloc之后再仔细研究一下

初始化

1
2
3
4
5
6
7
8
9
int InitSqList(SqList *L)//构造一个空的顺序表L
{
L->elem=(int *) malloc(List_Size *sizeof(int));
if (L->elem==NULL)
exit(EXIT_FAILURE);
L->len=0;
L->ListSize =List_Size;
return 1;
}
静态 VS 动态

都是连续的空间，增、删、查的方式一样；区别在于对内存的分配和回收方式上

由此可以看出：数组≠顺序表 并不是只有链表中才能有指针

不要建立 “数组形式即为顺序表，有指针即为链表的刻板印象”

插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListInsert_Sq( SqList &L, int i, ElemType e)
{
// 位置合法性的判断
if ( i<1 || i>L.len +1 ) return 0;
// 上溢时增加空间的分配
if( L.len >= L.listsize)
{
newbase = (ElemType *) realloc(L.elem,
(L.listsize+ LISTINCREMENT)*sizeof(ElemType));
if ( newbase == NULL ) exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
// 插入元素
for ( j = L.len; j >= i; j--) L.elem[j] = L.elem[j-1];
L.elem[i-1] = e;
L.len++;
return 1;
}
删除元素
1
2
3
4
5
6
7
8
Status ListDelete_Sq( SqList &L, int i) {
// 位置合法性的判断
if ( i<1 || i>L.len ) return 0;
// 删除
for ( j = i; j < L.len ; j++) L.elem[j-1] = L.elem[j];
L.len--;
return 1;
}

链表

用链来表明线性特征

1
2
3
4
5
6
struct Node{
int data;
struct Node *next};
};
Typedef struct Node *Link;
Link head;
插入算法
有头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status ListInsert(LinkList &L, int i, ElemType e){
// 有头结点，无须对i为1的插入位置作特殊处理
p = L; j = 0; // 对p,j初始化; *p为L的第j个结点
while( p != NULL && j<i-1){
	p = p->next;
	j++; // 寻找第i-1个结点的位置
}
if( p == NULL || j>i-1) return ERROR;// i小于1或大于表长
s = (LinkList )malloc(sizeof(LNode)); // 生成新结点
if ( s == NULL ) exit(OVERFLOW);// 空间分配不成功，报错返回
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return OK;
}
无头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status ListInsert(LinkList &L, int i, ElemType e) {
// 无头结点，须对i为1的插入位置作特殊处理
if ( i==1){
s = (LinkList )malloc(sizeof(LNode)); // 生成新结点
if ( s == NULL ) exit(OVERFLOW); // 空间分配不成功，报错返回
s->data = e; s->next = L; // 插入到链表L中
L = s; // 修改链头指针L
}else{
p = L; j = 1; // 对p,j初始化; *p为链表的第j个结点
while( p != NULL && j<i-1){
p = p->next;
j++; // 寻找第i-1个结点的位置
}
if( p == NULL || j>i-1) return ERROR;// i小于1或大于表长
s = (LinkList )malloc(sizeof(LNode)); // 生成新结点*s
if ( s == NULL ) exit(OVERFLOW); // 空间分配不成功，报错返回
s->data = e; s->next = p->next; // 插入到链表L中
p->next = s;
}
return OK;
}

区别在于是否对i为1的插入位置作特殊处理 ,实际上是对于第一个结点而言是否有前驱结点

STL:list 是一个双向链表

1
2
3
4
5
6
7
8
9
10
Struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
};
typedef struct Node * Link;
typedef struct {
Link head, tail;
int len;
}DLinkList;