《数据结构》重点知识汇总

《《数据结构》重点知识汇总》由会员分享，可在线阅读，更多相关《《数据结构》重点知识汇总（16页珍藏版）》请在金锄头文库上搜索。

1、v数据结构学问点概括第一章概 论数据就是指能够被运算机识别 、储备 和加工处理 的信息的载体 ；精品word 可编辑资料 - - - - - - - - - - - - -学习必备欢迎下载时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶 O（log2n ）、线性阶O（n）、线性对数阶O（nlog2n ）、平方阶O（n2 ）、立方阶 O（ n3 ）、k 次方阶 O（ nk）、指数阶 O（ 2n ）；空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n 的函数；数据元素是数据的基本单位 ，可以由如干个 数据项 组成；数据项 是具有独立含义的最小标识 单位；数据结构的定义：规律结构：

2、从规律结构上描述数据，独立于运算机；线性结构： 一对一关系 ；线性结构：多对多关系； 储备结构 ：是规律结构用运算机语言的实现；次序储备结构：如数组； 链式储备结构 ：如链表； 索引储备结构 ：稠密索引：每 个结点都有索引项； 稀疏索引 ：每 组结点都有索引项； 散列储备结构 ：如散列表；数据运算；对数据的操作；定义在规律结构上，每种规律结构都有一个运算集合；常用的有： 检索 、插入、删除、更新、排序；数据类型：是一个值的集合以及在这些值上定义的一组操作 的总称；结构类型：由用户借助于描述机制定义，是导出类型；抽象数据类型ADT ：是抽象数据的组织和与之的操作；相当于在概念层上描述问题；优点是

3、将数据和操作封装在一起实现了信息隐匿；程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法； 算法取决于数据结构；算法是一个良定义的运算过程，以一个或多个值输入，并以一个或多个值输出；评判算法的好坏的因素： 算法是正确的；执行算法的时间；执行算法的储备空间（主要是帮忙储备空间）；算法易于懂得、编码、调试；时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n 的函数；渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级；评判一个算法的时间性能时，主要标准就是算法的渐近时间复杂度；算法中语句的频度不仅与问题规模有关，仍与输入实例中各元素的取值相关；算法的时间复杂

4、度和空间复杂度合称算法复杂度；其次章线性表线性表是由n0 个数据元素组成的有限序列；n=0 是空表；非空表，只能有一个开头结点，有且只能有一个终端结点；线性表上定义的基本运算：构造空表： Initlist （L ）求表长： Listlength （ L ）取结点： GetNode（ L ，i）查找： LocateNode（L ，x）插入： InsertList （L ， x，i ）删除： Delete（ L ，i）次序表是按线性表的规律结构次序依次存放 在一组 地址连续 的储备单元中； 在储备单元中的各元素的物理位置 和规律结构 中各结点相邻关系是一样的；地址运算：LOCa （i） =LOCa

5、 （ 1）+ （i-1 ）*d ；（首地址为1）在次序表中实现的基本运算：插入：平均移动结点次数为n/2；平均时间复杂度均为O（ n）；删除：平均移动结点次数为（n-1 ） /2；平均时间复杂度均为O（ n）；线性表的链式储备结构中结点的规律次序和物理次序不愿定相同，为了能正确表示结点间的规律关系，在储备每个结点值的同时，仍储备了其后继结点的地址信息（即 指针或链 ）；这两部分信息组成链表中的结点结构；一个单链表由头指针的名字来命名；单链表运算：建立单链表头插法：s-next=head；head=s；生成的次序与输入次序相反；平均时 间复杂度均为O（ n）；尾插法： head=rear=nul

6、l； if （head=null ） head=s； else r-next=s；r=s； 平均时间复杂度均为 O（ n）加头结点的算法：对开头结点的操作无需特殊处理，统一了空表和非空表；第 1 页，共 13 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习必备欢迎下载查找按序号：与查找位置有关，平均时间复杂度均为O（ n）；按值：与输入实例有关，平均时间复杂度均为O（ n）；插入运算： p=GetNode （ L，i-1 ）；s-next=p-next ；p-next=s ；平均时间复杂度均为 O（n）删除运算： p=

7、GetNode （ L，i-1 ）；r=p-next ；p-next=r-next ；free（r）；平均时间复杂度均为 O（n）单循环链表是一种首尾相接的单链表，终端结点的指针域指向开头结点或头结点；链表终止条件是以指针等于头指针或尾指针；接受单循环链表在有用中多接受尾指针表示单循环链表；优点是查找头指针和尾指针的时间都是O（1），不用遍历整个链表；双链表就是双向链表， 就是在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior，形成两条不同方向的链；由头指针head 惟一确定；双链表也可以头尾相链接构成双（向）循环链表；双链表上的插入和删除时间复杂度均为O （ 1）；次序表和链表

8、的比较：基于空间： 次序表的储备空间是静态支配，储备密度为1；适于线性表事先确定其大小时接受；链表的储备空间是动态支配，储备密度1；适于线性表长度变化大时接受；基于时间：次序表是随机储备结构，当线性表的操作主要是查找时 ，宜接受；以插入和删除操作为主的线性表宜接受链表做储备结构；如 插入 和删除 主要发生在表的首尾两端 ，就宜接受 尾指针 表示的 单循环链表 ；第三章栈和队列栈（ Stack）是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶， 另一端称为栈底； 表中无元素时为空栈；栈的修改是按后进先出的原就进行的，我们又称栈为LIFO 表（ Last In First O

9、ut ）；通常栈有次序栈和链栈两种储备结构；栈的基本运算有六种：构造空栈： InitStack （S）判栈空：StackEmpty（ S）判栈满：StackFull （S）进栈：Push（S，x ）退栈：Pop（S）取栈顶元素： StackTop（ S）在次序栈中有“上溢”和“下溢”的现象；“上溢”是 栈顶指针指出栈的外面是出错状态 ； “下溢”可以表示栈为空栈，因此用来作为把握转移的条件；次序栈中的基本操作有六种：构造空栈判栈空判栈满进栈退栈取栈顶元素链栈就没有上溢的限制，因此进栈不要判栈满；链栈不需要在头部附加头结点，只要有 链表的头指针 就可以了；链栈中的基本操作有五种： 构造空栈判栈空

10、进栈退栈取栈顶元素队列 （ Queue）是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，答应删除的一端称为队头（ front ），答应插入的一端称为队尾（rear） ，队列的操作原就是先进先出的，又称作 FIFO 表（ First InFirst Out ） .队列也有次序储备和链式储备两种储备结构；队列的基本运算有六种：置空队： InitQueue （ Q）判队空： QueueEmpty（ Q）判队满： QueueFull （ Q）入队： EnQueue（Q， x）出队： DeQueue（Q）取队头元素： QueueFront（Q）次序队列的“假上溢”现象：由于头尾指针不

11、断前移，超出向量空间；这时整个向量空间及队列是空的却产生了“上溢”现象；为了克服 “假上溢” 现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列；判定循环队列是空仍是满，方法有三种：一种是另设一个布尔变量来判定；其次种是少用一个元素空间，入队时先测试（rear+1）%m = front ）？ 满：空；第三种就是用一个计数器记录队列中的元素的总数；队列的链式储备结构称为链队列，一个链队列就是一个操作受限的单链表；为了便于在表尾进行插入（入队）的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯独地确定；第 2 页，共 13 页 - - - - - -

12、- - - -链队列不存在队满和上溢精品word 可编辑资料 - - - - - - - - - - - - -学习必备欢迎下载位移或者是全部有效位移；最坏的情形下时间复杂度是O（ n-m+1） m），假如 m 与 n的问题； 在链队列的出队算法中，要留意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空；同阶的话就它是O（n2 ）；链串上的子串定位运算位移是结点地址而不是整数第五章多维数组第四章串串是 零个 或多个字符 组成的 有限序列 ；空串：是指长度为零的串，也就是串中不包含任何字符（结点）；空白串：指串中包含一个 或多个 空格字符的串； 在一个串中任意个连续字符组成的子序列称

13、为该串的子串，包含子串的串就称为主串； 子串在主串中的序号就是指子串在主串中首次显现的位置；空串是任意串的子串，任意串是自身的子串；串分为两种：串常量在程序中只能引用不能转变；串变量的值可以转变；串的基本运算有：求串长 strlen（char*s）串复制 strcpy（char*to ，char*from ）串联接 strcat （char*to ，char*from ）串比较 charcmp（char*s1， char*s2）字符定位 strchr （ char*s，charc）串是特殊的线性表（结点是字符），所以串的储备结构与线性表的储备结构类似；串的次序储备结构简称为次序串；次序串又可按

14、储备支配的不同分为：静态储备支配：直接用定长的字符数组来定义；优点是涉及串长的操作速度快，但不适合插入、链接操作；动态储备支配： 是在定义串时担心排储备空间，需要使用时按所需串的长度支配储备单元；串的链式储备就是用单链表的方式 储备串值， 串的这种链式储备结构简称为链串；链串与单链表的差异只是它的结点数据域为单个字符；为明白决“储备密度”低的状况，可以让一个结点储备多个字符，即结点的大小；次序串上子串定位的运算：又称串的“模式匹配”或“串匹配”，是在主串中查找出子串显现的位置；在串匹配中，将主串称为目标（串），子串称为模式（串） ；这是比较简洁懂得的，串匹配问题就是找出给定模式串P 在给定目标串T 中首次显现的有效数组一般用次序储备的方式表示；储备的方式有：行优先次序，也就是把数组逐行依次排列；PASCAL 、C列优先次序，就是把数组逐列依次排列；FORTRAN地址的运算方法：按行优先次序排列的数组：LOCa（ ij ）=LOCa （11）+（ i-1 ）*n+ （j-1 ） *d.按列优先次序排列的数组：LOCa（ ij ）=LOCa（ 11）+（ j-1 ）*n+ （i-1 ） *d.矩阵的压缩储备：为多个相同的非零元素支配一个