会计学基本概念数据结构(shùjùjiéɡòu)集合结构(jiégòu)：仅同属一个集合线性结构(jiégòu):一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)（1）R=(D,S)D={a,b,c,d,e,f}S={<a,e>,<b,c>,<c,a>,<e,f>,<f,d>}物理结构(jiégòu)亦称存储结构(jiégòu)，是数据的逻辑结构(jiégòu)在计算机存储器内的表示（或映像）。它依赖于计算机。时间复杂度和空间复杂度如何(rúhé)表示？特别说明：如果无论算法规模怎样变化(biànhuà)，其执行时间为一常数，则该算法的时间复杂度为O(1)./第2章线性表一、线性表（linear_list）线性表是n个数据元素的有限(yǒuxiàn)序列，记为：L=（a1,a2,…,an）线性表的顺序存储结构(jiégòu)二.插入(chārù)和删除操作1.插入(chārù)运算INSERT（L,i,b）插入(chārù)前：L=（a1,...,ai-1,ai,...,an）插入(chārù)后：L=（a1,...,ai-1,b,ai,...,an）线性表上的基本运算插入运算含义：将元素e插入到线性表：(a1,a2,…,ai-1,ai,…,an)中，构成新的线性表(a1,a2,…,ai-1,e,ai,…,an)，满足ai-1≤e≤ai,(其中≤为比较关系),即不破坏原线性关系。表的长度为n+1将元素e插入到元素ai-1之后，ai-1的直接后继和ai的直接前驱就改变了，需要在顺序表的存储(cúnchǔ)结构上反映出来。2.删除(shānchú)运算DELETE（L,i）删除(shānchú)前：L=（a1,...,ai-1,ai,ai+1,...,an）删除(shānchú)后：L=（a1,...,ai-1,ai+1,...,an）线性表顺序存储结构的特点(1).逻辑(luójí)上相邻的元素，其物理位置也相邻；(2).可随机存取表中任一元素；(3).必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构；(4).插入删除时，需移动大量元素，平均移动元素为n/2。顺序表的基本运算的复杂度插入T(n)=O(n)，S(n)=O(1)删除T(n)=O(n)，S(n)=O(1)线性表的链式表示(biǎoshì)和实现单链表的表示(biǎoshì)和实现单链表上的插入运算(第i个位置(wèizhi)上插入新的结点)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)链表的优缺点优点：插入、删除时无须移动元素，只需修改指针根据需要申请存储空间，且不要求连续的存储空间缺点：对表中的元素只能进行顺序访问用指针指示元素之间的逻辑关系（直接前驱(qiánqū)、后继），存储空间利用率低head双向链表上的删除操作(cāozuò)(删除第i个结点)第3章栈和队列(duìliè)二、队列的概念队列（Queue）是限定仅在一端插入(chārù),另一端删除的线性表。允许插入(chārù)的一端叫队尾(rear),允许删除的一端叫队头(front),不含元素的空表称为空队列队列的运算特性是先进先出(FirstInFirstOut--FIFO)插入(chārù)、删除操作第4章串第5章数组和广义(guǎngyì)表第6章树与二叉树树的基本术语1.树的结点:包含一个DE和指向其子树的所有分支;2.结点的度:一个结点拥有的子树的个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))含义:树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子(háizi)为第二层,若某结点为第k层,则其孩子(háizi)为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换.二叉树性质(扩展要求(yāoqiú)掌握各性质的推论)性质1.在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2.深度为k的二叉树至多有2k-1个结点(k≥1)。（深度一定，二叉树的最大结点数也确定）性质3.二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1性质4.结点数为n的完全二叉树，其深度为└log2n┘+1性质5.在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树的根；否则(i>1)，结点i的双亲(shuāngqīn)为结点└i/2┘。⑵2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；否则