数据结构课程知识点梳理汇总.docx

《数据结构课程知识点梳理汇总.docx》由会员分享，可在线阅读，更多相关《数据结构课程知识点梳理汇总.docx（26页珍藏版）》请在优知文库上搜索。

1、数据结构第一章:绪论1.概念：数据:所有能被计算机输入并且识别处理的符号的集合（数值性+非数值-视频,声音,图用数据元素:数据的基本单位.也叫记录数据项:数据的最小单位.EG-学生记录是数据元素,姓名,学号,性别是数据项.数据对象:具有相同性质的数据元素的集合.例如整数集合.*性质相同:具有相同类型和数量的数据项.数据类型:值+操作,三种:原子类型,结构类型抽象数据类型（ADT）ADT-抽象数据类型:抽象,与具体如何在计算机表示无关,用（数据对象,数据关系,基本操作集）定义.包括数行嗨关系,基本操作.*数据类型VS抽象数据类型:前者表示值+操作,例如c中整形,通常有厂家提供的已经实现的数据结构

2、,而后者表示数学模型+操作,仅仅取决于逻辑特性,于具体的实嬲7表示无关,只要其数学特性不变就不影响使用.-联系:本质相同,但是后者不局限于已经实现了的数据类型,还包括用户自定义的数据类型.一作用:ADT对用户透明（提供接口）,而不必了解实现细节.数据结构:具有一种或多种特定关系的数据元素的集合.包括三方面:逻辑结构,存储结构,数据运算.（算法的设计取决于逻辑结构,而算法的实现依赖于存储结构.）* 数据逻辑结构,数据元素,数据项在计算机中的映像为:存储结构,结点,数据域.* *数据运算=对数据定义的一组操作,定义在逻辑结构,实现依赖于存储结构.* -若逻辑结构相同,存储结构不同-数据结构不同*

3、-若逻辑结构相同&存储结构相同,但是运算不同-数据结构不同：EG:睇以物都相同,但是由于其运薪金不同称为不同的数据结构.-若逻辑结构相同,运算相同,存储结构不同-数据结构运算效率不同.数据结构评价准则：1.是否刻画了问题的基本特征.2.是否容易实现.选择数据结构考虑的因素：（存储时间量和空间量）：-A:TB:SA:包括:输入数据总量;编译时间;取指令执行时间;重复执行的次数.数据结构基本操作於力翻实现应用程序与存储程序的独立.数据结构研究内容:在非数值计算程序设计问题中,研究计算机的操您对家操作对象之间的走熬及其操作的学科.数据类型VS数据结构:前者可以看成是已经实现了的数据结构.并非所有数据

4、结构都具有插入,删除,查找三种运算,如栈和队列不具备查找.数据结构三要素：A:逻辑结构:线性+非线性：线性结构（一对一）：一般线性表+受限线性表（栈,队列）+推广线性表（数组,广义表）或者栈,队列,串,线性表）非线性结构:集合+树形结构（一般树,二叉树）（一对多）+图形结构（有向图,无向图）（多对多）更具体的分类:线性结构,集合树,图/网状结构.B:存储结构（物理结构）:数据元素的表示和关系的表示:（内存）顺序存储:优点:随机存取缺点:只能整块存储,外部碎片链式存储:优点:无碎片缺点:只能顺序存取,每个元素占用额外空间.索引存储:优点检索速度快缺点:索引表占用较多存储空间,修改索引表耗时.散列

5、存储:优点:检索,删除增加节点速度快.缺点:可能出现元素存储单元冲突,解决冲突增加开销.C:数据运算.逻辑结构vs存储结构：前者独立于后者,一种逻辑结构可以用多种存储结构.逻辑结构表示逻辑关系-数据元素的关联方式/辘关奏,存储结构是逻辑结构在计算机中的表示.数据结构研究的内容涉及三方面：1.数据如何组织2.数据如何存储3.数据的运算如何实现.2.算法:程序设计=算法+数据结构算法是对特定问题求解步骤的描述,计算机中是指令的有限序列,其中的指令表示一个/多个操作.算法具有以下5大特性：有穷性(在实际可接受时间内执行完成),确定性(没有歧义),可行性(可以通过已经实现的基本运算执行),输入(O-N

6、),输出(I-N).*算法满足有穷性,但是程序不一定满足(如OS监控程序),算法可以用计算机程序描述,但是不是说所有算法都必须用程序描述.*：算法设计输入参数设置为非引用型形参,输出参数设置为引用型形参.好的算法目标：正确性:正确的解决问题(对于非法输入能够满足规格说明的输出)可读性:容易理解健壮性:非法数据,合法反应效率&低存储量(花小钱,办大事)效率度量:时间复杂度:事前估计：频度:一个语句在算法中重复执行的次数,T(n)=Pindu.时间复杂度:T(N)的数量级=算法基本运算(最深层循环内的语句的频度)T(N)=O(f(n)影响因素:A:问题规模NB彳寺输入元素性质通常考虑最坏时间复杂度

7、.空间复杂度:算法耗费的内存空间Sn=O(g(n).算法所需解磔量占用的内存空间.原地工作:算法所需辅助空间是常量,OQ）计算方法:递归算法:由算法推出励飒懑闻求解.影响一个算法的时间效率主要因素:事先估计运行时间考虑因素：A:问题规模-待解决问题的数量B:算法执行的基本操作次数.算法VS存储结构：富病即雌网上好的存储结构可以提高算法效率.求解问题的步骤:建立ADT（运算描述）一设计合理的存储结构（运算实现）一设计算法数据运算与采用何种存储结构相关,算数/赋值/关系运算三类.算法的比较:两个算法上俄一般是采用平均时间复杂度,而一个算法分析通常采用孱妤时间复杂度.第二章:线性表1 .线性表：定义

8、:n个相同数据类型的数据元素的有限序列.可以为空.特点:线性性质:除了al,每个都有唯一的直接前驱,除了an,每个都有唯一的直接后驱.性质:个数有限,每一个元素占用空间相同,各元素排序有先后.线性表长度VS数组长度:前者是元素个数,后者是预先分配的存放线性表的存储空间的长度.前者小于等于后者.线性表VS一维数组:前者要求所有元素连续存储,后者不必.前者有就IW操作,后者为留行故元素.有序表:有一定Jl质序的线性表.2 .顺序表:线性表的顺序存储:采用数组存放元素C=ZPi(Ci)基本操作:插入操作(i=(1.n+1)平均移动n/2删除操作(i=(1.n)-平均移动(nl)2按值查找(i=(1.

9、n)平均比较次数(n+1)/23 ,顺序存储vs链式存储优缺点：顺序：存储密度大,内部物理地址相邻Iiiiiiiiiiiiiiiiiiiiiiiiiii储指针Iiiiiiiiiiiiiiiiiiiiiiiii储区域.存储空间秘邮筑随机读取或Jl质序读取适合于静态操作插入,删除移动将近一半元素一般用数组存储,实现容易可以折半查找-分配方式：静态:预先分配空间大小难以确定.动态:需要移动大量元素.查找才由入,删除T(N):链式：历解点物理地址不一定嬲无碎片现象,但是需要存储空间来存每个结点内占用一片用维存存储空间秘碑濠只能顺序读取适合动态如:删除元素,移动元素等动态操作方便运用于各种逻辑结构的存储

10、表示需要指针支持指针不可折半查找.分配灵活,高效.按值:无序-T=O(N)T=O(N)有序-T=0(1.0G2N)(折半查找)按序号:T=OQ)插入移动(ai-an=n-i+l个)i属于土刀删除移动(ai+l-an=n-i个)i属于。,用一比较:顺序访问所有结点:O(N)O(N)4 .为什么引入链式存储?-在插入删除操作以提高效率.5 .单链表;用头指针1.标识一个单链表,空表:1.=NU1.1.有头结点-头指针就等于-用头绿能循铲标说单链表,无头结点-用首结点指针标识.删除P结点后继结点T=O；判空(有头结点:1.TneXt=NU1.1.)头结点-目的:为了操作和运算上的方便头结点:数据域可

11、有可无,指针域-指向第一个元素结点.空表头结点指针域=NU1.1.头结点VS头指针：不管带不带头结点,头指针都是指向表中第一个结点，头结点是带头结点链表中的第一个结点.头结点优点:A:使得链表任何节点都有前驱结点,就礴A操作方猿和表其他位置操作一致；遍历:必须从头结点开始才能遍历整个表.B:无论链表是否空,头指针都是指向头结点的非空指针.如果含头结点任何插入都不合圜快结点指针的值6 .单链表:操作:1.头指针,s新的结点:(二表示赋值尸二表示判定)建立+查找+插入+删除：头插法(逆序H=O(N)代码:s-data=x;snext=lnext;lneXt=S 尾插法(增加一个尾指针r):T=O(

12、N)代码:S-data=x;rnext=s;r=s(r指针指向$即r指向新的表尾结点) 按序号直找:找到第i个结点为止：(含头结点XT=O(N)代码:1.nOde*p=1.-next初始化P指针;While(P&jvi)P=PTnext;j+Returnp;按值查找:T=C)(N)带头节点：代码:1.nOde*p=1.-next初始化P指针;While(P!=Null&pdata!=e)P=PTneXtretuenp; 插入操作:有P结点,节点b插入s结点.T=O(N)一将X插入第i个位置.代码:P=GETE1.EM(1.,i-l)找到第i个结点的前驱结点;STneXt=PTnext;pnex

13、t=s;注意:语句不可颠倒,试着自行分析.君姆S侬自m 删除结点:在p,q节点,节点c删除q节点T=O(N)-删除第i个结点.代码:P=GETE1.EM(1.,i-l)找到第i-1个结点的位置;PTneXt=q-nexree(q);求表长度:表的长度不将兴绿点-对于含头结点和不含头结点算法不同.7.双链表:插入删除结点算法T=C)(I)一为什么？-目比使德司以双向遍历,快速访问已知结点前后结点.-两个指针:PriOr,next与单链表区别:只是增加了一个Prior指针.双链表在插入删除过程中需要修改prior指针,关键在于:修改过程中不断链.与单链表相比,存储密度小.便于找到前驱,后继结点.A

14、:操作:在指定结点后进行操作: 插入:在P所指结点（结点*p）和结点C之间插入结点*s.T=O代码:snext=pnext;Pnextprior=s;S-Prior=p;pneXt=S关镇:.第一句第二句必须在第四句之前，试分析为什么?（否则:STneXt=S,s-prior=公 删除删除结点*p的后继结点*q：T=OQ）代E马:PTneXt=qnext;qnext-PriOr=p;nee（可以交换顺序）8彳盾环单链表:尾结点*r的next域指向1.一与单链表区别:表中最后一个节点指针域不是NU1.1.,而是揭娱结点一特点:表中无NU1.1.节点;判空条件（有头结点）:买结点励韵溟百等型指针-

15、设尾指针:对于表头,尾操作T=O（I）.一不带头节点判空:1.=NU1.1.;尾结点:PTneXt=1.-从表中任意节点都可以遍历整个链表.9 .循环双链表：区别:头结点的Prior指针指向表尾.-判别条件:尾结点*p-p11ext=1.;空袭头结点的PriMneXt均等于1.（1.next=1.-prior=1.）10 .静态链表：一借助数组描述线性表的链式存储结构.一与链表区别:指针是结点的相对地址（数组下标）一作用:适用于没有指针的高级语言中.-特点插入删除同动态链表,只需改指针,不用移动元素.无嬲苴的瘫难以确定表长.11 .表的合并算法：n,m长度的有序表利用二朝琥法合成一个有序表,T=5h）11V.12 .总结:各种表操作T荟萃:T=O(X)顺