数据结构知识点(含算法)

《数据结构知识点(含算法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、概念总结第一章概论1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K,R)结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系3.数据类型a.基本数据类型整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char

2、）、指针类型（pointer）b.复合数据类型复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多）5.四种基本存储映射方法：顺序、链接、索引、散列6.算法的特性：通用性、有效性、确定性、有穷性7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化8.渐进算法分析a．大Ο分析法：上限，表明最坏情况b．Ω分析法：下限，表明最好情况c．Θ分析法：当上限和下限相同时，表明平均情况第二章线性表1.线性结构的基本特征a.集合中必存

3、在唯一的一个“第一元素”b.集合中必存在唯一的一个“最后元素”c.除最后元素之外，均有唯一的后继d.除第一元素之外，均有唯一的前驱2.线性结构的基本特点:均匀性、有序性3.顺序表a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度b.线性表中任意元素的存储位置：Loc(ki)=Loc(k0)+i*L（设每个元素需占用L个存储单元）c.线性表的优缺点：优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样缺点：空间难以扩充d.检索：ASL=【Ο（1）】e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（

4、n）】f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】4.链表4.1单链表a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等b.带头结点的怎么判定空表：head和tail指向单链表的头结点c.链表的插入（q->next=p->next;p->next=q;）【Ο（n）】d.链表的删除（q=p->next;p->next=q->next;deleteq;）【Ο（n）】e.不足：next仅指向后继，不能有效找到前驱4.2双链表a.增加前驱指针，弥补单链表的不足b.带头结点的怎么判定空表:head和tail指向单链表的头结点c

5、.插入：（q->next=p->next;q->prev=p;p->next=q;q->next->prev=q;）d.删除：（p->prev->next=p->next;p->next->prev=p->prev;p->prev=p->next=NULL;deletep;）4.3顺序表和链表的比较4.3.1主要优点a.顺序表的主要优点没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利b.链表的主要优点无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况4.3.2应用场合的选择a.不宜使用顺序表的场合经常插入删除时，不宜使用顺序表；线性表的

6、最大长度也是一个重要因素b.不宜使用链表的场合当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择第三章栈与队列1.栈a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种b.应用：1）数制转换while(N){N%8入栈；N=N/8;}while(栈非空){出栈；输出；}2）括号匹配检验不匹配情况：各类括号数量不同；嵌套关系不正确算法：逐一处理表达式中的每个字符ch：ch=非括号：不做任何处理ch=左

7、括号：入栈ch=右括号：if(栈空)returnfalseelse{出栈，检查匹配情况，if(不匹配)returnfalse}如果结束后，栈非空，返回false3）表达式求值3.1中缀表达式：计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右3.2后缀表达式：<表达式>::=<项><项>+

8、<项><项>－

9、<项><项>::=<因子><因子>*

10、<因子><因子>/

11、<