数据结构与算法.ppt

《数据结构与算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章数据结构与算法1.1算法一、算法的基本概念1、算法：是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时也是明确的，此顺序将在有限次数后终止2、算法的基本特征：可行性确定性有穷性拥有足够的情报（零个或多个输入）一个或多个输出1.1算法2、算法的基本要素（1）算法中对数据的运算和操作（2）算法的控制结构：顺序、选择、循环3、算法设计的基本方法（1）列举法(穷举法)（2）归纳法（3）递推（4）递归（5）减半递推技术（6）回溯法1.1算法二、算法的复杂度1、算法的时间复杂度：指执行算法所需要的计算工作量。由基本运算的执行次数来度量的。算法的工作

2、量=f(n)（1）平均性态（2）最坏情况复杂性2、算法的空间复杂度：指执行这个算法所需要的内存空间。1.2数据结构的基本概念一、数据结构的定义1、数据结构：指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。2、数据结构研究的内容：数据的逻辑结构数据的存储结构对各种数据结构进行的运算（1）数据：对客观事物的符号表示（2）数据元素：数据的基本单位（3）数据对象：性质相同的数据元素的集合，是数据的一个子集1.2数据结构的基本概念3、数据的逻辑结构，定义：对数据元素之间的逻辑结构的描述。一个数据的逻辑结构应包含的信息：表示数据元素的信息表示各数

3、据元素之间的前后件关系所谓数据的逻辑结构，指反映数据之间逻辑关系的数据结构。（1）分类：集合、线性结构、树型结构、图形结构（2）要素：数据元素的集合集合上的关系4、数据的存储结构，定义：数据的逻辑结构在计算机存储空间的存放形式。常用的存储结构：顺序、链接、索引1.2数据结构的基本概念二、数据结构的图形表示结点：数据元素根结点：没有前件的结点终端结点（叶子结点）：没有后件的结点父亲儿子女儿1.2数据结构的基本概念三、线性结构与非线性结构1、空的数据结构：如果在一个数据结构中一个数据元素都没有。2、线性结构：（1）有且只有一个根结点（2）每个结点最多有一个前

4、件，也最多有一个后件3、非线性结构：如果一个数据结构不是线性结构1.3线性表及顺序存储结构一、线性表的定义1、线性表：是n个元素构成的有限序列(a1,a2,…,an)。表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。2、线性表的特征：有且只有一个根结点a1，它无前件有且只有一个终端结点an，它无后件除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。1.3线性表及顺序存储结构二、线性表的顺序存储(存储结构)1、顺序表：用一组地址连续的存储单元依次存储线性表的数据元素。2、顺序存储的基本特征：（1

5、）线性表的所有元素所占的存储空间连续的（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。3、线性的顺序存储结构下可以做以下运算插入、删除、查找、排序、分解、合并、复制、逆转a1a2a3a4a5…an1.3线性表及顺序存储结构顺序表的插入运算1、线性表插入运算：指在表的第i个位置上，插入一个新结点x,使线性表变成长度为n+1的线性表。2、算法平均时间复杂度为O(n)a1a2…ai-1ai…an1.3线性表及顺序存储结构顺序表的删除运算1、线性表删除运算：指将表的第i个结点删除，使线性表变成长度为n-1的线性表。2、算法平均时间复杂度为O(n)a1

6、a2…ai-1ai…an1.4栈和队列1.4栈和队列(采用顺序存储结构或链式存储结构)一、栈及其基本运算1、栈：是只能在表的一端进行插入和删除运算的线性表。插入、删除的这一端为栈顶，另一端为栈底。栈称为先进后出表（FILO）或后进先出表（LIFO）2、栈的顺序存储及其运算：（1）入栈运算：指在栈顶位置插入一个新元素。（2）退栈运算：指取出栈顶元素并赋给一个指定的变量。（3）读栈顶元素：指将栈项元素赋给一个指定的变量。栈具有记忆功能!!1.4栈和队列二、队列及其基本运算1、队列：只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头，允许插入的一端

7、叫队尾。队列也称作先进先出（FIFO）的线性表，或后进后出表（LILO）的线性表。2、队列运算：（1）入队运算：指往队列尾插入一个元素。（2）退队运算：从队列的排头删除一个元素。3、循环队列(采用顺序存储结构)及其运算（1）循环队列：将队列存储空间的最后一个位置绕到第一个位置，开成逻辑上的环状空间1.4栈和队列（2）循环队列运算入队运算：指在循环队列的队尾加一个新元素。退队运算：指在循环队列头位置退出一个元素并赋给指定的变量。1.5线性链表一、线性单链表的结构及其基本运算(线性链表线性单链表双向链表循环链表:属于线性表,采用链式存储结构)1、线性链

8、表：（1）顺序存储结构的线性表的存储的缺点：插入和删除的运算效率很低。插入新的元