数据结构与算法学习笔记 之 程杰《大话数据结构》数据结构篇_大话数据结构+程杰

数据结构与算法学习笔记 之 程杰《大话数据结构》数据结构篇

第一章 数据结构绪论

1. 数据项：数据不可分割的最小单位。在数据结构课程中，把数据项定义为最小单位，有助于我们更好地解决问题。但是真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。
2. 数据对象：是性质相同的数据元素的集合，是数据的子集。其中，性质相同是指数据元素具有相同数量和类型的数据项。
3. 结构：各个组成部分相互搭配和排列的方式。
4. 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
5. 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

第二章 算法

1. 算法的设计要求：正确性、可读性、健壮性、高效率和低存储量。

2. 算法的特征：有穷性、确定性、可行性、输入、输出。

3. 最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

4. 在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。

5. 算法时间复杂度：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。【注：这种用大写O()来体现时间复杂度的记法，称为大O记法】

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

7. 常用的时间复杂度所耗费的时间从小到大依次是：

   O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

8. 对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

9. 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

第三章 线性表

1. 数组的长度是存放线性表的存储空间的长度，存储分配后一般不变；线性表的长度是线性表中数据元素的个数，是变化的。

2. “->” 主要用于指向结构体、C++中的class等含有子数据的指针用来取子数据。

struct Data
{
   
    int a,b;
};
struct Data* p; //定义结构体指针
struct Data A = {
   1,2};
p = &A;
int x;
x = p->a; //取出p所指向的结构体中，包含的数据项a赋值给x
		  //由于 p->a==A.a, 故 x=1
1
2
3
4
5
6
7
8
9
10
11
12

3. 线性表的顺序存储结构：在存、读数据时，不管是哪个位置，时间复杂度都是O(1) ; 而插入或删除数据时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。
4. 线性表的链式存储结构：

（1）假设 p 是指向线性表第 i 个元素的指针，则用 p->data 表示结点 ai 的数据域，p->data 的值是一个数据元素，而结点 ai 的指针域可以用 p->next 来表示，p->next 的值是一个指针，指向第 i+1 个元素。综上有：若 p->data = ai，则 p->next->data = a(i+1)

（2）单链表的读取：(核心思想：工作指针后移)

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
Status GetElem(LinkList L,int i,ElemType *e)
{
   
    LinkList p;
    p=L->next; //声明一结点p，指向链表L的第一个结点
    int j=1; 
    //p 不为空或者 j还没有等于i时，循环继续
    while (p && j<i)
    {
   
        p=p->next; //让p指向下一个结点
        ++j;
    }
    if (!p || j>i)
        return ERROR;
    *e=p->data; //取第i个元素的数据
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

要读取第 i 个元素，需要遍历 i-1 次。

5. 单链表的插入与删除：

s->next = p->next;
p->next = s;
1
2

对于单链表的表头和表尾的特殊情况，操作相同：

//单链表第i个数据插入结点
Status ListInsert(LinkList *L,int i,ElemType e)
{
   
    LinkList p,s;
    p = *L; //声明一结点p指向链表第一个结点
    int j=1;
    //p 不为空或者 j还没有等于i时，循环继续
    while (p && j<i)
    {
   
        p = p->next; //将后一个结点的指针域赋给p
        ++j;
    }
    if (!p || j>i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node)); //生成新结点
    s->data = e;
    s->next = p->next;
    p-next = s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6. 单链表的删除：

q = p->next;
p->next = q->next;
1
2

//单链表第 i 个数据删除
Status ListDelete(LinkList *L,int i,ElemType *e)
{
   
    LinkList p,q;
    p = *L;
    int j=1;
    //只要 p->next 不是指向空，而且j<i，就继续循环
    while (p->next && j<i)
    {
   
        p = p->next;
        ++j;
    }
    //如果 p->next 指向空或 j>i
    //注意理解为什么是判断p->next是否为空，因为p=*L是头指针，指向的是头结点而非第一个结点
    if (!(p->next) || j>i)
        return ERROE; //第 i 个元素不存在
    q = p->next;
    p->next = q->next; //q 相当于一个过渡结点
    *e = q->data;
    free(q); //让系统回收过渡结点，释放内存
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7. 单链表的整表创建：

//随机产生n个元素的值，建立带头结点的单链线性表L(头插法)
void CreateListHead(LinkList *L,int n)
{
   
    LinkList p;
    int i;
    srand(time(0)); //初始化随机数种子
	*L = (LinkList)malloc(sizeof(Node));
    //让L的头结点的指针指向NULL，即建立一个带头结点的单链表
    (*L)->next = NULL; 
    for (i=0;i<n;i++)
    {
   
        p = (LinkList)malloc(sizeof(Node)); //生成新结点
        p->data = rand()%100+1; //随机生成100以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//随机产生n个元素的值，建立带头结点的单链线性表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
   
    LinkList p,r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L; //r为尾结点，r会随着循环不断变化结点
    for (i=0;i<n;i++)
    {
   
        p = (Node*)malloc(sizeof(Node)); //生成新结点
        p->data = rand()%100+1;
        r->next = p;
        r = p; //循环改变r，保证r为尾结点
    }
    //循环结束，将链表的尾结点指针域置空，以便之后遍历时确定尾部
    r->next = NULL; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8. 单链表的整表删除：

Status ClearList(LinkList *L)
{
   
    LinkList p,q;
    p = (*L)->next; //p指向第一个结点
    while (p) //没到表尾
    {
   
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL; //头结点指针域置空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

9. 单链表结构与顺序存储结构总结：

（1）若线性表需要频繁查找，很少进行插入和删除操作，宜采用顺序存储结构；若需要频繁插入和删除，宜采用单链表结构。

（2）当线性表中的元素个数变化较大或者根本不知道有多少时，最好用单链表结构，因为这样不需要考虑存储空间的大小问题；而如果事先知道线性表的大致长度，用顺序存储结构效率更高。

10. 静态链表：

（1）用数组描述的链表称为静态链表

（2）总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

11. 循环链表：

（1）将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表

（2）为了使空链表与非空链表的处理一致，我们通常设一个头结点。但并非说循环链表一定要有头结点

（3）在单链表中，拥有头结点，可以用O(1)的时间访问第一个结点，但对于尾结点的访问，却需要O(n)时间；而使用指向终端结点的尾指针来表示循环链表，查找第一个结点和终端结点都很方便

（4）利用尾指针rear 将两个循环链表合并：

p = rearA->next; //保存A表的头结点
rearA->next = rearB->next->next; //将原指向B表的第一个结点（非头结点）赋值给 rearA->next
rearB->next = p; //将原A表的头结点赋值给 rearB->next
free(p);
1
2
3
4

12. 双向链表：

（1）双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域

（2）双向链表的插入：

//顺序是关键：先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
1
2
3
4
5

（3）双向链表的删除：

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
1
2
3

（4）总结：

双向链表相对于单链表来说会更加复杂，由于需记录两份指针，所以在空间上占用较多。不过，由于良好的对称性，它对某个结点的前后结点的操作更加方便，可以有效提高算法的时间性能（用空间换时间）。

第四章 栈与队列

1. 有关栈的概念：

（1）栈是限定仅在表尾（栈底）进行插入和删除操作的线性表(可以类比现实生活中的“手枪弹夹”，是撤销操作的原理

（2）允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称 LIFO结构

2. 两栈共享空间：

（1）其实栈的顺序存储还是挺方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个巨大缺陷，就是必须事先确定数组存储空间大小，万一不够用，就需要编程扩展数组的容量。对于一个栈，我们只能设计出合适大小的数组来满足要求，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。

（2）但事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况，而且只针对两个具有相同数据类型的栈。

3. 栈的链式存储结构：

（1）栈的链式存储结构简称为链栈

（2）如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈；反之，如果元素的变化在可控范围内，建议使用顺序栈。

4. 栈的应用 – 四则运算表达式求值
5. 有关队列的概念：

队列是只允许在一端插入，在另一端删除的线性表，队列是一种先进先出的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头

6. 队列顺序存储与循环队列：

（1）队列顺序存储的不足：我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是对头。所谓的入队列就是在队尾追加一个元素，不需移动任何元素，时间复杂度为O(1)。与栈不同的是，队列元素的出列是在对头，即下标为0的位置，这就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)。

（2）图解关于队列顺序存储结构与循环队列的思索：

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构成为循环队列。

从上面的思索中可以发现，顺序存储的时间性能不高，而循环队列又面临着数组溢出的问题。

7. 队列的链式存储结构：(注意区分头结点和队头结点)

（1）入队：

//插入元素e为Q的新队尾元素
Status EnQueue(LinkQueue *Q,QElemType e)
{
   
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) //存储分配失败
        exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s; //将s设置为新队尾结点
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）出队：

//若队列不为空，删除Q的队头元素，用e返回其值，否则返回ERROR
Status DeQueue(LinkQueue *Q,QElemType *e)
{
   
    QueuePtr p;
    if (Q->front==Q->rear)
        return ERROR;
    p = Q->front->next; //将欲删除的队头结点暂存到p
    *e = p->data; //将欲删除的队头结点的值赋给e
    Q->front->next = p->next; //更新队头结点
    if (Q->rear==p)
        Q->rear = Q->front;
    free(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

8. 循环队列与链队列：

从时间上看，二者的基本操作都是O(1)。从空间上看，循环队列必须有一个固定长度，所以就有了存储元素个数和空间浪费的问题，而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接收。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议使用循环队列，如果无法预估队列的长度，则使用链队列。

第五章 串

1. 有关串的概念：

（1）串是由零个或多个字符组成的有限序列，又名字符串，一般记为 s = “a1a2a3…an”(n>=0)，串中字符数目n称为串的长度，零个字符的串称为空串("")，空格串是只包含空格的串

（2）串中任意个数的连续字符组成的子序列称为子串，包含子串的串称为主串，子串在主串中的位置是子串的第一个字符在主串中的序号

2. 串的抽象数据类型：

（1）串的逻辑结构与线性表类似，不同之处在于串针对的是字符集。对于串的基本操作与线性表是有很大差别的，线性表关注的是单个元素的操作，而串中更多的是查找子串位置，得到指定位置子串、替换子串等操作。

（2）串的模式匹配算法Index：

//若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0
int Index(String S,String T,int pos)
{
   
    int n,m,i;
    String sub;
    if (pos > 0)
    {
   
        n = StrLength(S);
        m = StrLength(T);
        i = pos;
        while (i
1
2
3
4
5
6
7
8
9
10
11
12