第二章 常用的数据结构
数据结构的重要性:
在进行程序设计时,对于要处理的一类数据,程序员必须选择一种数据结构来进行这类数据的添加,修改,删除,存储等操作. 如果在选择数据结构时做了错误的决定,那么程序执行起来可能非常低效,如果选错了数据类型,后果不堪设想.
数据结构的分类:
基本数据类型: 整数,浮点,布尔,字符 结构化数据类型: 字符串,数组,指针,列表,文件 抽象数据类型: 堆栈
数据结构加上算法等于高效的可执行程序 精心选择的数据结构可以带来最优效率的算法,数据结构的选择至关重要!
数组
数组结构其实就是紧密相连的可数内存,数组的下标从内存的起始位置的第几区块.
数组分为: 一维数组, Score[0]*5 二维数组, number = [[11,12,13],[22,24,26],[33,35,37]] 多维数组, arr = [ [ [11,22,33],[44,55,66] ], [ [77,88,99],[12,12,12] ] ]
链表
许多相同数据类型的数据项按特定规则排序而成的线性表.
特点 各个数据项在计算机内存中的位置是不连续且随机存放的. 优点 数据的插入与删除都非常方便,有新数据加入就向系统申请一块内存空间, 数据被删除就把这块内存空间还给系统. 加入和删除都不需要移动大量的数据. 缺点 设计数据结构比较麻烦,并且查找数据时也无法像静态数据(如数组)那样可随机读取数据,必须按序查到该数据为止.
动态分配内存空间 最常使用的就是单向链表,单向链表基本上由数据字段和指针两个元素组成,指针会指向下一个元素在内存中的地址. 单向链表的第一个节点是链表头指针,最后一个节点的指针为None,表示链表尾,不指向任何地方. 单向链表的所有结点都知道下一个节点在哪,但是不知道前一个结点的位置. 因此,在单向链表的所有操作中,第一个结点指针就显得尤为重要.只要知道表头指针就可以遍历整个链表,进行添加删除操作. 除非必要不可移动表头指针.
堆栈
堆栈是一组具有相同数据类型的组合,具有后进先出的特性. 所有的操作都是在堆栈的顶端进行的. 堆栈是抽象型数据类型(ADT) 基本操作 create 创建一个空堆栈 push 把数据压入堆栈顶端,并返回新堆栈 pop 从堆栈顶端弹出数据,并返回新堆栈 isEmpty 判断堆栈是否为空堆栈,是则返回true,不是则返回false full 判断堆栈是否已满,是则返回true,不是则返回false
队列
先进先出的数据结构,和堆栈一样都是有序线性表的抽象数据类型(ADT) 拥有加入和删除两种基本操作,而且使用front和rear两个指针来分别指向队列的前端和末尾. 基本操作 create 创建空队列 add 将新数据加入队列末尾,返回新队列 delete 删除队列前端的数据,返回新队列 front 返回队列前端的值 empty 若队列为空,返回true,否则返回false
树
树形结构是非线性结构,操作系统和数据库管理系统都是树形结构 用来描述节点与节点之间的层次关系 由一个或一个以上的结点组成,特殊节点为root 每个节点可以代表一些数据和指针组合而成的记录 其余节点可以分为n>=0个互斥的集合, 每个子集本身也是一种树形结构及此根节点的子树.

一颗合法的树可以互相连接,但是不能形成无出口的环路
专有名词: 度数:结点的子树个数 层数:树的层数 高度:树的最大层数 树叶:终端结点 父节点:上一层结点 子节点:下一层结点 祖先:节点路径上的所有节点 子孙:节点下的任意节点 兄弟节点: 非终端节点:除终端节点以外的节点 同代:相同层数的节点 森林:n>=颗互斥树的集合
二叉树 一般的树形结构在内存中的存储形式以链表为主. data|link1|link2| |linkn 对于n叉树来说.因为每个节点的个数都不同,所以我们必须要为每个节点预留存放n个连接字段的最大存储空间.这种n叉树十分浪费存储空间. n叉树有m个节点,链接浪费率为{m*(n-1)+1}/m*n n=2时,二叉树的链接浪费率为1/2 n=3时,三叉树的链接浪费率为2/3 n=4时,四叉树的链接浪费率为3/4 当n=2时链接浪费率最低,所以为了改进存储空间浪费的特点,我们常用二叉树结构来取代其他的树形结构 二叉树是一个由有限节点所组成的集合,此集合可以为空集合,或由一个树根及其左右两个子树所组成.(二叉树最多只能有两个子节点) llink|data|rlink 二叉树与一般树的区别: 树不可以是空集合,二叉树可以 树的度数为d>=0,二叉树的度数为[0,2] 树的子树之间没有次序,二叉树有次序,分为左子树和右子树,互斥.
图
讨论两个顶点之间是否连通, 在连接两顶点之间加上权值(成本,开销),这类图称为"网络".
无向图(A,B) 有边但是没有方向 V = {A,B,C,D} E = {(A,B),(C,D),(B,C),(A,D)}
有向图<A,B> 有边有方向 V = {A,B,C,D} E = {<A,B>,<C,D>,<B,C>,<A,D>}
哈希表
…