数据结构知识点总结讲课稿.doc

《数据结构知识点总结讲课稿.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构知识点总结精品文档数据结构学习总结壹、研究对象及基本概念首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。一、从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。线性表、栈、队列、串

2、、数组线性结构:树结构图结构逻辑结构非线性结构二、从存储结构划分顺序结构链式结构索引结构物理结构散列结构各自的定义及特点：1、顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。收集于网络，如有侵权请联系管理员删除精品文档1、链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.插入、删除灵活(不必移动节点，只要改变节

3、点中的指针)。查找结点时链式存储要比顺序存储慢。3、索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。索引项的一般形式一般是关键字、地址。4、散列存储：又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。特点：散列是能一种快速实现访问的存储方式。三、操作算法1、算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。2、五个重要特性：（1）有穷性；（2）确定性；（3）可行性；（

4、4）输入；（5）输出。3、算法设计要求：（1）正确性；（2）可读性；（3）健壮性；（4）效率与低存储量需求。效率的度量：算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。存储空间度量：一个程序的空间复杂度是指运行完一个程序所需内存的大小。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。四、一些基本概念1.数据数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由

5、计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。2.数据元素收集于网络，如有侵权请联系管理员删除精品文档数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。4.数据对象性质相同的元素的集合叫做数据对象。贰、线性结构一、线性表1.1[定义]线性表是由n(n≥0)个相同类型的元素组成的有序集合。记为：(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。②a

6、i为线性表中的元素，类型定义为elemtype③a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1

7、ai∈Elementset,i=1,2,…,n,n≥0}R={H}H={

8、ai-1,ai∈D,i=2,…,n}操作：设L的型为LIST线性表实例，x的型为elemtype的元素实例，p为位置变量。所有操作描述为：收集于网络，如有侵

9、权请联系管理员删除精品文档①Insert(x,p,L)②Locate(x,L)③Retrieve(p,L)④Delete(p,L)⑤Previous(p,L),Next(p,L)⑥MakeNull(L)⑦First(L)⑧End(L)1.2线性表的实现：①顺序表：把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。特点：元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来

10、表示。②单链表：一个线性表由若干个结点组成，每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域，这样就形成一个