文档介绍：该【数据结构基础讲义 】是由【wxq362】上传分享，文档一共【46】页，该文档可以免费在线阅读，需要了解更多关于【数据结构基础讲义 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构
--肖兴贵
传智播客
第1页,共46页。
1概要
2线性表
3栈和队列
4树和二叉树
5查找和排序
主要内容
第2页,共46页。
算法+数据结构=程序设计
处理问题的策略
给出问题的数学模型
编制出的指令集
处理问题用计算机
问题
构建数学模型
程序实现
第3页,共46页。
例1求小红C语言和数据结构两门语言的考试的平均成绩成绩和总成绩。全省的呢?
例2酒店管理中的客房分配问题。
例3煤气管道的铺设问题。
等等……
例子中的数学模型正是数据结构要讨论的问题。
第4页,共46页。
数据结构是一门讨论"描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现"的学科。
(数据结构)
(存储实现)
。(算法)
通俗点讲,数据结构研究的是数据的存储和操作。
第5页,共46页。
数据的逻辑结构
数据的存储结构
数据的运算:查找、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队列
树形结构
图形结构
第6页,共46页。
逻辑结构
物理结构
第7页,共46页。
数学模型
集合和关系
数据和信息
数据元素
数据项
关键码
抽象数据类型
第8页,共46页。
算法是特定问题求解步骤的描述,在计算机中表现为指令的有限序列,算法是独立存在的一种解决问题的方法和思想。对于算法而言,语言并不重要,重要的是思想。
数据结构和算法的关系:数据结构是专门研究数据的存储问题,而对存储后的数据进行相应的操作就是算法。
第9页,共46页。
我们通过大O表示法来表示算法的效率:时间复杂度、空间复杂度。规则如下:
(1)只关注最高次项,常数项和次要项忽略;
(2)时间复杂度是指最坏时间复杂度;
(3)只有常数项记做1。
执行次数函数
阶
非正式术语
12
O(1)
常数阶
2n+3
O(n)
线性阶
3n2+2n+1
O(n2)
平方阶
5log2n+20
O(logn)
对数阶
2n+3nlog2n+19
O(nlogn)
nlogn阶
6n3+2n2+3n+4
O(n3)
立方阶
2n
O(2n)
指数阶
第10页,共46页。