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

数据结构知识点总结

数据结构学习总结

壹、研究对象及基本概念

首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。

一、从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。

二、从存储结构划分

各自的定义及特点：

1、顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。

优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。

2、链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.插入、删除灵活 (不必移动节点，只要改变节点中的指针)。查找结点时链式存储要比顺序存储慢。

3、索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。索引项的一般形式一般是关键字、地址。

4、散列存储：又称hash存储，是一种力图将数据元素的存储位置与关键码之

间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码

值决定节点的存储地址。特点：散列是能一种快速实现访问的存储方式。

三、操作算法

1、算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

2、五个重要特性：

（1）有穷性；（2）确定性；（3）可行性；（4）输入；（5）输出。

3、算法设计要求：

（1）正确性；（2）可读性；（3）健壮性；（4）效率与低存储量需求。

效率的度量：

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不

包括这个函数的低阶项和首项系数。

存储空间度量：

一个程序的空间复杂度是指运行完一个程序所需内存的大小。一个算法所需的存储空间用f(n)表示。

S(n)=O(f(n))

其中n为问题的规模，S(n)表示空间复杂度。

四、一些基本概念

1.数据

数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。

2.数据元素

数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。

3.数据项

是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。

4.数据对象

性质相同的元素的集合叫做数据对象。

贰、线性结构

一、线性表

1.1[定义] 线性表是由n(n≥0)个相同类型的元素组成的有序集合。

记为：

( a1,a2,a3,……ai-1,ai,ai+1,…… an )

其中：① n为线性表中元素个数，称为线性表的长度；

当n=0时，为空表，记为（）。

② ai为线性表中的元素，类型定义为elemtype

③ a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1

④线性表是有限的，也是有序的。

抽象数据型线性表：

线性表 LIST = ( D , R)

D = { ai | ai ∈Elementset , i = 1, 2, …, n, n ≥ 0 }

R = { H }

H = { | ai-1, ai ∈ D , i = 2 , … , n }

操作：设L的型为LIST线性表实例，x 的型为elemtype的元素

实例，p 为位置变量。所有操作描述为：

① 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线性表的实现：

①顺序表：

把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。

特点：

元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；

是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。

②单链表：一个线性表由若干个结点组成，每个结点均含有两个域：

存放元素的信息域和存放其后继结点的指针域，这样就形成一个

单向链接式存储结构，简称单向链表或单向线性链表。

结构特点：

逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示；

需要额外空间存储元素之间的关系；非随机存储结构

一些操作：

③双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为双向链表。

优点：

实现双向查找（单链表不易做到）

表中的位置i 可以用指示含有第i 个结点的指针表示。

缺点：空间开销大。

④单向环形链表：在(不带表头结点)的单向链表中，使末尾结点的指