2022年数据结构知识点总结 .docx
《2022年数据结构知识点总结 .docx》由会员分享,可在线阅读,更多相关《2022年数据结构知识点总结 .docx(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精品_精品资料_数据结构学问点概括线性表是由 n 0 个数据元素组成的有限序列.其次章 线性表可编辑资料 - - - 欢迎下载精品_精品资料_第一章 概 论数据就是指能够被运算机 识别、储备和加工处理 的信息的载体 .数据元素是数据的 基本单位 ,可以由如干个 数据项 组成. 数据项 是具有独立含义的 最小标识 单位.数据结构的定义:规律结构:从规律结构上描述数据,独立于运算机.线性结构: 一对一关系 .线性结构:多对多关系.储备结构 :是规律结构用运算机语言的实现. 次序储备结构:如数组.链式储备结构 :如链表.索引储备结构 :稠密索引:每 个结点都有索引项.稀疏索引 :每组结点都有索引项.
2、散列储备结构 :如散列表.数据运算.对数据的操作.定义在规律结构上,每种规律结构都有一个运算集合.常用的有: 检索、插入、删除、更新、排序.数据类型:是一个值的集合以及在这些值上定义的一组操作 的总称.结构类型:由用户借助于描述机制定义,是导出类型.抽象数据类型 ADT :是抽象数据的组织和与之的操作.相当于在概念层上描述问题.优点是将数据和操作封装在一起实现了信息隐匿.程序设计的实质是对实际问题挑选一种好的数据结构,设计一个好的算法.算法取决于数据结构.算法是一个良定义的运算过程,以一个或多个值输入,并以一个或多个值输出.评判算法的好坏的因素: 算法是正确的.执行算法的时间.执行算法的储备空
3、间(主要是帮助储备空间).算法易于懂得、编码、调试.时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n 的函数.渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级.评判一个算法的时间性能时,主要标准就是算法的渐近时间复杂度.算法中语句的频度不仅与问题规模有关,仍与输入实例中各元素的取值相关.时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶 O( log2n )、线性阶 O(n)、线性对数阶 O( nlog2n)、平方阶 O( n2 )、立方阶 O( n3)、 k 次方阶 O(nk )、指数阶 O(2n ).空间复杂度:是某个算法的空间耗费,它是该算法所求解问
4、题规模n 的函数.算法的时间复杂度和空间复杂度合称算法复杂度.n=0 是空表.非空表,只能有一个开头结点,有且只能有一个终端结点.线性表上定义的基本运算:构造空表: Initlist ( L )求表长: Listlength (L )取结点: GetNode(L ,i)查找: LocateNode(L, x)插入: InsertList ( L, x, i)删除: Delete(L ,i)次序表是按线性表的规律结构次序依次存放 在一组 的址连续 的储备单元中.在储备单元中的各元素的物理位置 和规律结构 中各结点相邻关系是一样的.的址运算:LOCa( i)=LOCa (1) +( i-1 ) *
5、d .(首的址为 1)在次序表中实现的基本运算:插入:平均移动结点次数为n/2.平均时间复杂度均为O( n).删除:平均移动结点次数为(n-1)/2.平均时间复杂度均为O(n).线性表的链式储备结构中结点的规律次序和物理次序不肯定相同,为了能正确表示结点间的规律关系,在储备每个结点值的同时,仍储备了其后继结点的的址信息(即指针或链 ).这两部分信息组成链表中的结点结构.一个单链表由头指针的名字来命名.单链表运算:建立单链表头插法: s-next=head.head=s.生成的次序与输入次序相反.平均时间复杂度均为O( n).尾插法: head=rear=null . if (head=null
6、 ) head=s.else r-next=s. r=s. 平均时间复杂度均为O(n)加头结点的算法:对开头结点的操作无需特别处理,统一了空表和非空表.查找按序号:与查找位置有关,平均时间复杂度均为O( n).按值:与输入实例有关,平均时间复杂度均为O( n).插入运算: p=GetNode(L , i-1 ).s-next=p-next .p-next=s .平均时间复杂度均为O( n)删除运算: p=GetNode(L , i-1 ).r=p-next . p-next=r-next . free(r).平均时间复杂度均为O(n) 单循环链表是一种首尾相接的单链表,终端结点的指针域指向开头
7、结点或头结点.链表终止条件是以指针等于头指针或尾指针.采纳单循环链表在有用中多采纳尾指针表示单循环链表.优点是查找头指针和尾指针的时间都是O(1),不用遍历整个链表.双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior ,形成两条不同方向的链.由头指针 head 惟一确定.双链表也可以头尾相链接构成双(向)循环链表.双链表上的插入和删除时间复杂度均为O ( 1).次序表和链表的比较:基于空间:次序表的储备空间是静态安排,储备密度为 1.适于线性表事先确定其大小时采纳.链表的储备空间是动态安排,储备密度1.适于线性表长度变化大时采纳.基于时间:次序表是随机储备结
8、构,当线性表的操作主要是查找时 ,宜采纳.以插入和删除操作为主的线性表宜采纳链表做储备结构.如插入和删除主要发生在表的 首尾两端 ,就宜采纳 尾指针 表示的单循环链表 .可编辑资料 - - - 欢迎下载精品_精品资料_第三章 栈和队列栈( Stack)是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底.表串是零个或多个字符 组成的 有限序列 .第四章 串可编辑资料 - - - 欢迎下载精品_精品资料_中无元素时为空栈.栈的修改是按后进先出的原就进行的,我们又称栈为LIFO 表( Last In First Out ).通常栈有次序栈和链栈两种储备结构.栈的基
9、本运算有六种:构造空栈: InitStack (S)判栈空: StackEmpty( S)判栈满: StackFull (S)进栈: Push(S,x)退栈: Pop( S)取栈顶元素: StackTop(S)在次序栈中有“上溢”和“下溢”的现象.“上溢”是 栈顶指针指出栈的外面是出错状态.“下溢”可以表示栈为空栈,因此用来作为掌握转移的条件.次序栈中的基本操作有六种: 构造空栈判栈空判栈满进栈退栈取栈顶元素链栈就没有上溢的限制,因此进栈不要判栈满.链栈不需要在头部附加头结点,只要有链表的头指针 就可以了.链栈中的基本操作有五种: 构造空栈判栈空进栈退栈取栈顶元素队列(Queue)是一种运算受
10、限的线性表,插入在表的一端进行,而删除在表的另一端进行,答应删除的一端称为队头( front ),答应插入的一端称为队尾(rear) ,队列的操作原就是先进先出的,又称作FIFO 表( First In First Out ) . 队列也有次序储备和链式储备两种储备结构.队列的基本运算有六种:置空队: InitQueue(Q)判队空: QueueEmpty(Q)判队满: QueueFull(Q)入队: EnQueue( Q,x)出队: DeQueue(Q)取队头元素: QueueFront(Q)次序队列的 “假上溢” 现象: 由于头尾指针不断前移, 超出向量空间. 这时整个向量空间及队列是空的
11、却产生了“上溢”现象.为了克服“假上溢”现象引入循环向量的概念,是把向量空间形成一个头尾相接的环形,这时队列称循环队列.判定循环队列是空仍是满,方法有三种:一种是另设一个布尔变量来判定.其次种是少用一个元素空间,入队时先测试( rear+1)%m = front )? 满:空.第三种就是用一个计数器记录队列中的元素的总数.队列的链式储备结构称为链队列,一个链队列就是一个操作受限的单链表.为了便于在表尾进行插入(入队)的操作,在表尾增加一个尾指针,一个链队列就由一个头指针和一个尾指针唯独的确定.链队列不存在队满和上溢的问题.在链队列的出队算法中,要留意当原队中只有一个结点时,出队后要同进修改头尾
12、指针并使队列变空.空串:是指长度为零的串,也就是串中不包含任何字符(结点).空白串:指串中包含 一个或多个空格字符的串.在一个串中任意个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串.子串在主串中的序号就是指子串在主串中首次显现的位置.空串是任意串的子串,任意串是自身的子串.串分为两种: 串常量在程序中只能引用不能转变.串变量的值可以转变.串的基本运算有:求串长 strlen( char*s)串复制 strcpy(char*to ,char*from )串联接 strcat(char*to ,char*from )串比较 charcmp(char*s1 ,char*s2)字符定位
13、strchr( char*s, charc)串是特别的线性表(结点是字符) ,所以串的储备结构与线性表的储备结构类似.串的次序储备结构简称为次序串.次序串又可按储备安排的不同分为:静态储备安排:直接用定长的字符数组来定义.优点是涉及串长的操作速度快,但不适合插入、链接操作.动态储备安排:是在定义串时不安排储备空间,需要使用时按所需串的长度安排储备单元.串的链式储备就是用 单链表的方式 储备串值,串的这种链式储备结构简称为链串.链串与单链表的差异只是它的结点数据域为单个字符.为明白决“储备密度”低的状况,可以让一个结点储备多个字符,即结点的大小.次序串上子串定位的运算:又称串的“模式匹配”或“串
14、匹配”,是在主串中查找出子串显现的位置.在串匹配中,将主串称为目标(串) ,子串称为模式(串) .这是比较简洁懂得的,串匹配问题就是找出给定模式串P 在给定目标串 T中首次显现的有效位移或者是全部有效位移.最坏的情形下时间复杂度是O( n-m+1) m),假如 m 与 n 同阶的话就它是 O( n2).链串上的子串定位运算位移是结点的址而不是整数第五章 多维数组数组一般用次序储备的方式表示.储备的方式有:行优先次序,也就是把数组逐行依次排列.PASCAL 、C列优先次序,就是把数组逐列依次排列.FORTRAN的址的运算方法:按行优先次序排列的数组:LOCa(ij ) =LOCa(11)+( i
15、-1 ) *n+ (j-1 ) *d.按列优先次序排列的数组:LOCa(ij ) =LOCa(11)+( j-1 ) *n+ (i-1 ) *d.矩阵的压缩储备:为多个相同的非零元素安排一个储备空间.对零元素不安排空间.特别矩阵的概念:所谓特别矩阵是指非零元素或零元素分布有肯定规律的矩阵.稀疏矩阵的概念:一个矩阵中如其非零元素的个数远远小于零元素的个数,就该矩阵称为稀疏矩阵.特别矩阵的类型:对称矩阵:满意 a(ij )=a( ji ).元素总数 n(n+1)/2.I=max (i,j),J=min( i,j ),LOCa(ij )=LOC (sa0 )+(I* ( I+1 )/2+J)*d.三
16、角矩阵: 上三角阵: k=i* ( 2n-i+1 ) /2+j-i ,LOCa( ij ) =LOC ( sa0)+k*d.下三角阵: k=i* ( i+1 ) /2+j ,LOCa (ij ) =LOC ( sa0)+k*d.对角矩阵: k=2i+j ,LOCa ( ij ) =LOC ( sa0) +k*d.稀疏矩阵的压缩储备方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起,用这些结点组成的一个线性表来表示.但这种压缩储备方式将失去随机储备功能.加入行表记录每行的非零元素在三元组表中的起始位置,即带行表的三元组表.可编辑资料 - - - 欢迎下载精品_精品资料_第六章
17、树树是 n 个结点的有限集合 ,非空时必需满意:只有一个称为根的结点.其余结点形成m 个不相交的子集,并称根的子树.可编辑资料 - - - 欢迎下载精品_精品资料_根是开头结点.结点的子树数称度.度为0 的结点称叶子(终端结点) .度不为 0 的结点称分支结点(非终端结点).除根外的分支结点称内部结点.有序树是子树有左,右之分的树.无序树是子树没有左,右之分的树.森林是m 个互不相交的树的集合. 树的四种不同表示方法: 树形表示法. 嵌套集合表示法. 凹入表示法广义表表示法.二叉树的定义:是 n0 个结点的有限集,它是空集(n=0)或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的
18、二叉树组成.二叉树不是树的特别情形,与度数为2 的有序树不同.二叉树的 4 个重要性质:二叉树上第 i 层上的结点数目最多为2(i-1 )( i 1).深度为 k 的二叉树至多有( 2k )-1 个结点( k1).在任意一棵二叉树中,如终端结点的个数为n0,度为 2 的结点数为 n2,就 n0=n2+1 .具有 n 个结点的完全二叉树的深度为int (log2n ) +1.满二叉树是一棵深度为k,结点数为( 2k )-1 的二叉树.完全二叉树是满二叉树在最下层自右向左去处部分结点. 二叉树的次序储备结构就是把二叉树的全部结点依据层次次序储备到连续的储备单元中.(储备前先将其画成完全二叉树)树的
19、储备结构多用的是链式储备.BinTNode 的结构为 lchild|data|rchild ,把全部 BinTNode 类型的结点,加上一个指向根结点的 BinTree 型头指针就构成了二叉树的链式储备结构,称为二叉链表.它就是由根指针root 唯独确定的.共有 2n 个指针域, n+1 个空指针.依据拜访结点的次序不同可得三种遍历:先序遍历(前序遍历或先根遍历),中序遍历(或中根遍历) 、后序遍历(或后根遍历).时间复杂度为 O(n).利用二叉链表中的 n+1 个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针,这些附加的指针就称为 “线索”,加上线索的二叉链表就称为线索链表.线索
20、使得查找中序前趋和中序后继变得简洁有效,但对于查找指定结点的前序前趋和后序后继并没有什么作用.树和森林及二叉树的转换是唯独对应的.转换方法: 树变二叉树:兄弟相连,保留长子的连线.二叉树变树:结点的右孩子与其双亲连.森林变二叉树:树变二叉树,各个树的根相连.树的储备结构: 有双亲链表表示法:结点data | parent,对于求指定结点的双亲或祖先非常便利,但不适于求指定结点的孩子及后代.孩子链表表示法:为树中每个结点data | next 设置一个孩子链表 firstchild ,并将 data | firstchild 存放在一个向量中.双亲孩子链表表示法:将双亲链表和孩子链表结合.孩子兄
21、弟链表表示法:结点结构leftmostchild |data | rightsibing ,附加两个分别指向该结点的最左孩子和右邻兄弟的指针域.树的前序遍历与相对应的二叉树的前序遍历一样.树的后序遍历与相对应的二叉树的中序遍历一样.树的带权路径长度是树中全部叶结点的带权路径长度之和.树的带权路径长度最小的二叉树就称为最优二叉树(即哈夫曼树) .在叶子的权值相同的二叉树中,完全二叉树的路径长度最短.哈夫曼树有 n 个叶结点,共有 2n-1 个结点,没有度为 1 的结点,这类树又称为严格二叉树.变长编码技术可以使频度高的字符编码短,而频度低的字符编码长,但是变长编码可能使解码产生二义性.如00、0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年数据结构知识点总结 2022 数据结构 知识点 总结
限制150内