数据结构基础讲义学习教案

1、会计学1数据结构数据结构(sh j ji u)基础讲义基础讲义第一页，共45页。第1页/共45页第二页，共45页。算法+数据结构(sh j ji u) = 程序设计 处理问题的策略给出问题的数学模型编制出的指令集处理问题用计算机问题问题(wnt)(wnt)构建数学模型构建数学模型程序实现程序实现第2页/共45页第三页，共45页。第3页/共45页第四页，共45页。 第4页/共45页第五页，共45页。 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查找、排序、插入、删除、修改等数据的运算：查找、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序

2、存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构第5页/共45页第六页，共45页。物理(wl)结构第6页/共45页第七页，共45页。第7页/共45页第八页，共45页。第8页/共45页第九页，共45页。执行次数函数执行次数函数阶阶非正式术语非正式术语12O(1)常数阶2n+3O(n)线性阶3n2+2n+1O(n2)平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(nlogn)nlogn阶6n3+2n2+3n+4O(n3)立方阶2nO(2n)指数阶第9页/共45页第十页，共45页。平方(pngfng)阶: O(n2)第10页/共45页第十一页

3、，共45页。第11页/共45页第十二页，共45页。第12页/共45页第十三页，共45页。头指针头指针a0a1an1( a )( b )第13页/共45页第十四页，共45页。头指针头指针a0a1an1( a )( b )第14页/共45页第十五页，共45页。第15页/共45页第十六页，共45页。第16页/共45页第十七页，共45页。第17页/共45页第十八页，共45页。第18页/共45页第十九页，共45页。队列(duli)的顺序存储第19页/共45页第二十页，共45页。队列(duli)的链式存储第20页/共45页第二十一页，共45页。第21页/共45页第二十二页，共45页。第22页/共45页第二

4、十三页，共45页。专业术语专业术语含义含义根也叫根结点(没有前驱)叶子也叫终端结点(没有后继)森林指m棵不相交的树的集合(例如删除A后的子树个数)有序树结点各子树从左至右有序，不能互换（左为第一）无序树结点各子树可互换位置双亲 即上层的那个结点(直接前驱) parent孩子即下层结点的子树 (直接后继) child兄弟同一双亲下的同层结点（孩子之间互称兄弟）sibling堂兄弟即双亲位于同一层的结点（但并非同一双亲）cousin祖先即从根到该结点所经分支的所有结点子孙即该结点下层子树中的任一结点结点也叫节点，即树的数据元素结点的度、树的度结点挂接的子树数、所有结点度中的最大值结点的层次从根到该

5、结点的层数（根结点算第一层）终端结点即度为0的结点，即叶子 分支结点除树根以外的结点（也称为内部结点）树的深度(或高度)指所有结点中最大的层数(从根节点到最低层的结点层数)第23页/共45页第二十四页，共45页。第24页/共45页第二十五页，共45页。第25页/共45页第二十六页，共45页。第26页/共45页第二十七页，共45页。第27页/共45页第二十八页，共45页。第28页/共45页第二十九页，共45页。第29页/共45页第三十页，共45页。完全(wnqun)二叉树存储第30页/共45页第三十一页，共45页。二叉链存储(cn ch)第31页/共45页第三十二页，共45页。三叉链存储(cn

6、ch)第32页/共45页第三十三页，共45页。遍历是指按某条搜索路线遍访每个结点且不重复（又称周游），遍历是树结构插入、删除、修改、查找和排序运算(yn sun)的前提，是二叉树一切运算(yn sun)的基础和核心。牢记一种约定，对每个结点的查看都是“先左后右”。 遍历方式遍历方式特点特点先序遍历(先根遍历，DLR)根 - 左子树 - 右子树中序遍历(中根遍历，LDR)左子树 - 根 - 右子树后序遍历(后根遍历，LRD)左子树 - 右子树 - 根第33页/共45页第三十四页，共45页。第34页/共45页第三十五页，共45页。二叉树的动态创建和释放二叉树的递归遍历计算二叉树叶子节点数目(shm)计算二叉树高度第35页/共45页第三十六页，共45页。第36页/共45页第三十七页，共45页。第37页/共45页第三十八页，共45页。顺序查找(ch zho)二分查找(ch zho)第38页/共45页第三十九页，共45页。第39页/共45页第四十页，共45页。冒泡选择(xunz)插入排序第40页/共45页第四十一页，共4