数据结构概述

数据结构概述(参考资料,严蔚敏的数据结构.高一凡把书中的伪算法全部用代码写了出来)

数据结构定义:

• 如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序),而执行的相应操作,这个相应的操作也叫算法.
• 数据结构 = 个体 + 个体的关系
• 算法 = 对存储数据的操作
• 解析:如果要存储一个一万个元素的数组,可能没有那么大的连续的存储空间,如果不能存储,那么就谈不上操作.那么解决这种问题就要靠链表来存储.

算法:

• 解题的方法和步骤
  衡量算法的标准:
  1.时间复杂度.大概程序要执行的次数,而非执行的时间.(为什么是次数,而不是时间?因为每台机器的处理能力不一样 .所以不能用时间来算)
  2.空间复杂度.算法执行过程中大概所占用的最大内存
  3.难易程度.算法要别人能够看懂,不能只有自己可以看懂
  4.健壮性.不能给一个非法的数据程序就挂掉了

      数据结构的地位:数据结构是软件中最核心的课程
      程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语
  

什么是栈,什么是堆:

所谓的栈内存和堆内存并不是内存里面有一块区域叫栈,有一块区域叫堆.所谓的栈内存和对内存实际上指的是分配内存的算法不一样,如果是以压栈出栈的方式分配的内存,就叫栈内存.如果是以堆排序的方式分配的内存就叫堆内存

预备知识:

• 指针:
  指针的重要性:指针式 C语言的灵魂
  定义:地址(内存单元的编号,从0开始的非负整数,对于32位的处理器来说范围是: 0~FFFFFFFF (0~4G-1)
  指针:指针就是地址,地址就是指针
  指针变量是存放内存单元地址的变量
  指针的本质是一个操作受限的非负整数(不能进行算术运算,只有在特定的时候(如果两个指针变量指向的是同一块连续空间中的不同存储单元)能做相减的运算)

• 结构体:
  为什么会出现结构体: 为了表示一些复杂的数据类型,而普通变量无法满足要求
  什么叫结构体:结构体是用户根据实际需要自己定义的复合数据类型
  如何使用结构体:

struct Student{
    int sid;
    char name[200];
    int age;
};
两种方式: struct Student st = {1000,”zhangsan”,20};
struct Student *pst = &st;
1.st .sid
2.pst—>sid (pst 所指向的结构体变量中的 sid 这个成员)

注意事项:
1.结构体变量不能加减乘除,但是可以相互赋值
2.普通结构体变量和结构体指针变量作为函数传参的问题(结构体形参时,一般要传地址,因为传结构体变量内存开销会大)

• 动态内存的分配与释放:
  动态构造一维数组
  malloc() 函数返回的是分配的内存的首地址
  假设动态构造一个int型数组 int *p = (int *)malloc(int len);
  1、 malloc只有一个int型的形参，表示要求系统分配的字节数
  2、 malloc函数的功能是请求系统len个字节的内存空间，如果请求分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL
  3、 malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实 际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此malloc前面必须加（数据类型 *）,表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。如:int *p = (int *)malloc(50);表示将系统分配好的50个字节的第一个字节的地址转化为int *型的地址，更准确的说是把第一个字节的地址转化为四个字节的地址，这样p就指向了第一个的四个字节，p+1就指向了第2个的四个字节,p+i就指向了第i+1个的4个字节。p[0]就是第一个元素， p[i]就是第 i+1个元素 double *p = (double *)malloc(80); 表示将系统分配好的80个字节的第一个字节的地址转化为double *型的地址，更准确的说是把第一个字节的地址转化为8个字节的地址，这 样p就指向了第一个的8个字节，p+1就指向了第2个的8个字节，p+i就指向了第i+1个的8个字节。p[0]就是第一个元素， p[i]就是第 i+1个元素
  4、 free（p)释放p所指向的内存，而不是释放p本身所占用的内存

• 号外: CPU不能直接访问硬盘,内存是 CPU 唯一能够访问的大容量存储设备.当然了 CPU 内部还有寄存器可以访问.

CPU 是如何与内存打交道的?

• CPU 和内存是通过三根总线来交互的:
  即地址总线(寻址,即要对那块内存进行处理,对于32位的处理器来说,内存的最大地址就是2的32次方-1 也就是4G,所以如果处理器是32位的那么用8G 的内存也是没有效果的,因为超出4G 的内存将不会被访问的到),
  控制总线(读或者写),
  数据总线(传输数据,CPU 把内部数据写到内存,或者将内存中的数据读到 CPU)

模块一:线性结构(把所有的结点用一根直线穿起来)

• 连续存储[数组]
  1.什么叫做数组:元素类型相同,大小相等
  2.数组的优缺点

• 离散存储[链表]
  定义: n个结点离散分配, 彼此通过指针相连, 每个结点只有一个前驱结点,每个结点只有一个后续结点,首结点没有前驱结点,尾节点没有后续结点.
  专业术语:
  1.首结点:第一个有效的结点
  2.尾结点:最后一个有效的结点
  3.头结点:第一个有效结点之前的那个结点,头结点并不存放有效数据,加头结点的目的主要是为了方便对链表的操作
  4.头指针:指向头结点的指针变量
  5.尾指针:指向尾结点的指针变量
  头结点—>首结点—> ……结点......—>尾结点

结点

struct Node{
     int data;//数据域
     struct Node *pNode; 指针域
}

每一个链表的结点都会有数据域和指针域
如果希望通过一个函数来对链表进行处理,我们至少需要接受链表的哪些参数? 只需要一个参数:头指针.因为我们通过头指针可以推算出链表的其他所有参数

• 分类:
  1.单链表:
  2.双链表:每一个结点有两个指针域
  3.循环链表:能通过任何一个结点找到其他所有的结点
  4.非循环链表:
• 算法:
  狭义的算法是与数据的存储方式密切相关的, 广义的算法是与数据的存储方式无关.
  1.遍历:
  2.查找:
  3.清空:
  4.销毁:
  5.求长度:

6. 排序:
7. 删除结点:
   8.插入结点:

• 泛型:利用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的
• 数据的存储结构有几种:
  1.线性: 连续存储[数组]
  优点: 存取元素效率非常高
  缺点: 插入删除元素效率低, 需要大块连续的内存块,通常受存储空间的限制,事先需要知道数组的长度
  2.离散存储[链表]
  优点:存储空间没有限制,插入删除元素效率高
  缺点: 存取速度很慢,
• 线性结构的两种常见应用之一 栈:
  定义:一种可以实现”先进后出”的存储结构,栈类似于箱子
  分类:
  静态栈
  动态栈
  算法:
  出栈
  压栈
  应用:
  函数调用
  中断
  表达式求值 (例如求32+5/6-4 ,这个就会用到两个栈,一个栈用来存储-、/、+、 另一个栈用来存储4、6、5、2、3)
  内存分配
  缓冲处理
  迷宫
• 线性结构的两种常见方式之二 队列:
  定义:一种可以实现”先进先出”的存储结构
  分类:
  链式队列 (用链表实现的)
  静态队列 (用数组实现的)
  静态队列通常都必须是循环队列,

循环队列的讲解:
1.静态队列为什么必须是循环队列
2.循环队列需要几个参数来确定
需要两个参数来确定,front 和 rear
3.循环队列各个参数的含义
两个参数场合不同的含义.建议初学者先记住,然后慢慢体会:
1).队列初始化
front 和 rear 的值都是零
2).队列非空
front 代表的是队列的第一个元素
rear 代表的是队列的最后一个有效元素的下一个元素
3).队列空
front 和 rear 的值相等,但不一定是零
4.静态队列入队伪算法讲解
两步完成:
1.将值存入r 所代表的位置
2.错误写法 r = r+1
正确的写法是: r = (r+1)%数组的长度

image.png
5.循环队列出队伪算法讲解
f = (f+1)%数组的长度
6.如何判断循环队列是否为空
如果 front 和 rear 的值相等,则该队列就一定为空
7.如何判断循环队列是否已满
两种方式:1.多增加一个标志参数(一般不用)
2.少用一个元素(通常使用这种方式) ,如果r和f紧挨着,则队列已满
if ( (r+1)%数组的长度 == f ) 已满;
else 不满;
队列算法:
入队
出队
队列的具体应用: 所有和时间有关的操作都有队列的影子
专题:递归
定义:一个函数自己直接或间接调用自己

image.png

• 递归满足的三个条件:
  1.递归必须得有一个明确的终止条件
  2.该函数所处理的数据规模必须在递减
  3.这个转化必须是可解的

• 递归和循环:
  递归:
  易于理解
  速度慢
  存储空间大
  循环:
  不易理解
  速度快
  存储空间小

                     1.1+2+3+4+…100的和
                      2.求阶乘
                      3.汉诺塔
                      4.走迷宫
  

• 递归的应用:
  树和森林就是以递归的方式定义的
  树和图的很多算法都是以递归来实现的
  很多数学公式就是以递归的方式定义的
  斐波拉契序列:1 2 3 5 8 13 ...

模块二:非线性结构

树

• 树定义
  专业定义:
  1.有且只有一个称为跟的结点
  2.有若干个互不相交的子树,这些树本身也是一颗树
  通俗定义:
  1.树是由结点和边组成
  2.每个结点只有一个父节点但是可以有多个子节点
  3.但有一个节点例外,该节点没有父节点,此节点称为根节点
  专业术语:
  1.节点
  2.父节点
  3.子节点
  4.子孙
  5.堂兄弟
  6.深度:从根节点到最底层结点的层数成为深度,根节点是第一层
  7.叶子节点:没有子节点的节点
  8.非终端结点:实际就是非叶子节点
  9.度:子节点的个数称为度

• 树分类
  一般树:任意一个节点的子节点的个数都不受限制
  二叉树:任意一个结点的子节点个数最多有两个,且子节点位置不可以更改(左子树和右子树顺序不可更改)
  二叉树的分类:
  1.一般二叉树
  2.满二叉树:在不增加树的层数的前提下,无法再多添加一个结点的二叉树就是满二叉树
  3.完全二叉树:如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树
  森林:n个互不相交的树的集合

• 树的存储
  二叉树的存储
  1.连续存储[完全二叉树]:
  优点:查找某个节点的父节点和子节点(也包括判断有没有)速度很快
  缺点:耗用内存空间过大
  2.链式存储:
  一般树的存储
  双亲表示法:求父节点方便
  孩子表示法:求子节点方便
  双亲孩子表示法:求父节点和子节点都很方便

• 二叉树表示法
  把一个普通树转化成二叉树来存储
  具体表示方法:设法保证任意一个结点的,左指针域指向它的第一个孩子,右指针域指向它的堂兄弟,只要能满足此条件,就可以把一个普通树转化为二叉树,一个普通树转化成的二叉树一定没有右子树

• 森林的存储:
  森林的存储就是把森林先转化成完全二叉树,然后再存储,森林转化成完全二叉树的过程如下:把 A 当做完全二叉树的根节点,树 A 没有子节点,所以树 A没有左子树,但是 A有兄弟(树 B)所以, A有右子树(B) ,B 有子节点(C,D,E) ,所以 B 有左子树(C);C 没有子节点,但是有兄弟结点(D),所以 C没有左子树,但是有右子树(D);D没有子节点,但是有兄弟节点(E),所以 D 没有左子树,但是有右子树(E);E 有子节点(F),没有兄弟节点,所以 E有右子树 F, 但没有左子树; 对于结点 B, 由于 B 有兄弟结点 G, 所以 B 有右子树 G;G 有子节点 K,没有兄弟节点,所以 G 有左子树K;K 有子节点 M, 但是 K 没有兄弟结点,所以 K 有右子树M;M有子节点,没有兄弟结点,所以 M 有左子树 L;L 没有子节点,但是有兄弟结点N,所以 L 有右子树N;N没有子节点,但是有兄弟结点 Q, 所以 N 没有左子树,但是有右子树 Q;Q没有子节点,但是有兄弟结点 F,所以 Q 没有左子树,但是有右子树 F;

森林转化成二叉树总量的来说就是:如果一个节点有子节点,就把该子节点当做该节点的左子树,如果有兄弟节点,就把兄弟节点,当做该节点的右子树.
下图是有A, B, C 为根节点的数组成的森林,

image.png

树的操作

• 二叉树的操作
  遍历:
  先序遍历（先访问根节点）
  根节点排最先，然后同级先左后右
  中序遍历（中间访问根结点）
  先左后根最后右
  后序遍历（最后访问根结点）
  先左后右最后根

已知两种遍历序列求原始二叉树:

已知先序和中序 或者 已知后序和中序 才可以唯一的推出一个二叉树,但是已知先序和后序是不能推出一个二叉树的
例子:
示例1:
先序: ABCDEFGH
中序: BDCEAFHG
求后序: DECBHGFA
示例2:
先序: ABDGHCEFI
中序: GDHBAECIF
求后序: GHDBEIFCA
示例3:
中序: BDCEAFHG
后序: DECBHGFA
求先序: ABCDEFGH

• 一般树的存储
  连续存储[完全二叉树]
  链式存储
• 森林的存储
  连续存储[完全二叉树]
  链式存储
• 应用:
  树是数据库中数据组织一种重要形式
  操作系统字符京城的关系本身就是一棵树
  面向对象语言中类的继承关系
  赫夫曼树

模块三: 查找和排序

• 折半查找

• 排序
  冒泡排序:(第一个和第二个比较,第二个和第三个比较,第三个和第四个比较,第四个和第五个比较....)
  插入排序:(把第二个插入第一个某个位置,使前两个有序,把第三个插入前两个的某个位置,使前三个有序,把第四个插入前三个的某个位置,使前四个有序)
  选择排序:(从所有的数据中找一个最小的出来,放在第一个位置,然后从剩下的数据中找出最小的放在第二个位置,然后从剩下的数据中找出最小的数据放在第三个位置)
  快速排序:(是对冒泡排序的一种改进,通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归
  归并排序:(归并是先是两个两个排,使两个有序,然后再四个四个排,使四个有序,….,整体排一次,使整体有序)

• 排序和查找的关系
  排序是查找的前提
  排序是重点

• 再次讨论什么是泛型: 同一种逻辑结构,无论该逻辑结构物理存储是什么样子的,我们可以对它执行形同的操作

• 面向过程与面向对象的区别:
  面向过程侧重于算法,面向对象侧重于解决问题