常用数据结构及其存储

《常用数据结构及其存储》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第21讲常用数据结构及其存储大学计算机基础第三部分计算机专业理论介绍[主要内容]21.1算法21.2数据结构的基本概念21.3线性表21.4栈与队列21.5树与二叉树21.1算法定义：是对特定问题求解步骤的一种描述。或者说，是为求解某问题的方法和步骤。特征：有穷性确定性有效性零个或多个输入一个或多个输出例如：一元二次方程求根算法。键盘输入系数送到a,b,c中start计算出两个根放在x1、x2中显示x1、x2中存放的数据end算法复杂度评价一个算法优劣的主要标准是：算法的执行效率与存储需求算法的效率：指的是时间复杂度（TimeComplexity）存储需求：指的是空

2、间复杂度（SpaceComplexity）一般情况下，算法中的基本操作重复操作执行的次数是问题规模n的某个函数f(n)，算法的时间复杂度记做：T(n)=O(f(n))21.2数据结构的基本概念数据与数据结构数据:是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合。数据元素:是数据的基本元素，即数据集合中的个体。数据项:具有独立意义的最小数据单位。数据对象:具有相同特性的数据元素的集合，是数据的子集。数据结构:互相之间存在着一种或多种关系的数据元素的集合。数据的逻辑结构集合线性结构树形结构图状或网状结构数据的存储结构一、顺序存储结构主要特点

3、：所有元素所占的存储空间是连续的；各个元素在存储空间中是按逻辑顺序依次存放的；元素可随机存取，但插入、删除运算不便，会引起大量结点的移动。二、链式存储结构主要特点：存储数据结构的存储空间可以不连续；各结点的存储顺序与元素之间的逻辑关系可以不一致，元素之间的逻辑关系由指针域来确定；插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。数据的运算检索：在数据结构里查找满足一定条件的结点插入：往数据结构里增加新的结点删除：把指定的结点从数据结构里去掉更新：修改指定结点的一个或多个域的值排序：保持线性结构的结点序列里结点数不变，将结点按某种指定的顺序重新排列21.3

4、线性表线性表是最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列。（a1，a2，…，an）顺序表：指用顺序存储结构存储的线性表。链表：用链式存储结构存储的线性表。栈和队列：是对线性表的插入、删除运算可以发生的位置加以限制的两种特殊的线性表。顺序表各种高级语言里的一维数组就是用顺序方式存储的线性表，因此常用一维数组称呼顺序表。若顺序表中结点个数为n，则：插入一个结点平均需要移动之结点个数为n/2，算法的时间复杂度是O(n)；删除一个结点平均需移动结点个数为（n-1）/2，算法的时间复杂度是O(n)。链表线性链表（单链表）：删除算法的时间复杂度为O(n)，其

5、主要执行时间是搜索删除位置。循环链表：指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环（如下图）。…结点1结点2结点n21.4栈和队列栈：是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。表中无元素即空栈。栈中有元素a1,a2,…,an，如下页图所示，称a1为栈底元素。新元素进栈要置于an之上，删除或退栈先对an进行，即“后进先出”（LIFO）的操作原则;栈的物理存储可以用顺序存储结构或链式存储结构;栈的运算还有取栈顶元素，检查栈是否为空，清除等。栈的插入和删除ABACBABAFEBAATO

6、PTOPTOPTOPTOPTOPan…a2a1进栈出栈栈底栈结构(3)(1)(2)(5)(4)(6)栈顶队列队列：是限定所有的插入都在表的一端进行，所有的删除都在表的另一端进行的线性表。进行删除的一端叫队头，进行插入的一端叫队尾，如下页图所示。在队列中，新元素总是加入到队尾，每次删除的总是对头元素，即当前“最老的”元素，这就是“先进先出”（FIFO）的操作原则。队列的物理存储可以用：顺序存储结构，也可用链式存储结构。队列的示意图出队列a1a2a3…an入队列队头队尾队列的插入和删除示例21.5树与二叉树树形结构是一类重要的非线性结构，树和二叉树是最常见的树形结构。树（T

7、ree）:是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，…，Tm，每个子集又是一棵树，称作这个根的子树（subtree）。树形结构的常用术语结点的度（Degree）：一个结点的子树的个数。树的度：树中各结点的度的最大值。树叶（Leaf）：度为0的结点。分支结点：度不为0的结点。双亲（Parent）、子女（Child）：结点的各子树的根称作该结点的子女；相应的该结点称作其子女的双亲。兄弟（Sibling）：具有相同双亲的结点互为兄