当前位置:首页 >> 初中教育 >>

第01章 绪论(C++)


数据结构(C++版) 数据结构( 版
(第2版) 版

叶核亚

数据结构( 数据结构(C++版)(第2版) 版 版
第1章 绪论 第2章 线性表 第3章 串 第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 排序 第10章 综合应用设计 第11章 Visual C++集成开

发环境

第1章 绪论 章
1.1 数据结构的基本概念 1.2 算法 目的:勾勒数据结构课程的轮廓。 目的:勾勒数据结构课程的轮廓。 要求:掌握数据结构基本概念 数据结构基本概念, 要求:掌握数据结构基本概念,理解抽象数 据类型概念; 据类型概念;熟悉算法设计和分析方 法。 重点:数据的逻辑结构和存储结构。 重点:数据的逻辑结构和存储结构。 难点:抽象数据类型,算法分析。 难点:抽象数据类型,算法分析。

《数据结构(C++版)(第2版)》

1.1 数据结构的基本概念
1.1.1 为什么要学习数据结构 1.1.2 什么是数据结构 1.1.3 数据类型与抽象数据类型

《数据结构(C++版)(第2版)》

1.1.1 为什么要学习数据结构
软件设计是计算机学科各个领域的核心。 软件设计是计算机学科各个领域的核心。 软件设计时要考虑的首要问题是数据的表 组织和处理方法。 示、组织和处理方法。数据结构设计和算 法设计是软件系统设计的核心。 法设计是软件系统设计的核心。 数据结构十算法=程序 程序” “数据结构十算法 程序”。

《数据结构(C++版)(第2版)》

1.1.2 什么是数据结构
数据( 数据(data) ) 数据元素( 数据元素(data element) 、数据项 ) (data item) ) 关键字( 关键字(key) 、主关键字(primary key) ) 主关键字( ) 数据结构( 数据结构(data structure)指数据元素之 ) 间存在的关系。 间存在的关系。

《数据结构(C++版)(第2版)》

1. 数据的逻辑结构
线性结构: ① 线性结构:数据元素只有一个前驱数据元素和一个后 继数据元素。 继数据元素。 树结构:每个数据元素只有一个前驱数据元素, ② 树结构:每个数据元素只有一个前驱数据元素,可有 零个或若干个后继数据元素。 零个或若干个后继数据元素。 图结构: ③ 图结构:每个数据元素可有零个或若干个前驱数据元 零个或若干个后继数据元素。 素,零个或若干个后继数据元素。

《数据结构(C++版)(第2版)》

① 线性结构
表1.1 学生信息表
学 号 姓 名 王红 张明 吴宁 秦风 年 18 19 18 17 龄

20020001 20020002 20020003 20020004

《数据结构(C++版)(第2版)》

② 树 结 构

《数据结构(C++版)(第2版)》

③ 图结构
图1.3 南京飞往昆明的航班路线图

《数据结构(C++版)(第2版)》

2. 数据的存储结构
① 顺序存储结构 ② 链式存储结构

线性表(A,B,C,D)的两种存储结构 图1.4 线性表 的两种存储结构
《数据结构(C++版)(第2版)》

3. 数据操作
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 初始化。 初始化。 判断是否空状态。 判断是否空状态。 求长度:统计元素个数。 求长度:统计元素个数。 包含:判断是否包含指定元素。 包含:判断是否包含指定元素。 遍历:按某种次序访问所有元素, 遍历:按某种次序访问所有元素,每个元素只 被访问一次。 被访问一次。 取值:获取指定元素值。 取值:获取指定元素值。 置值:设置指定元素值。 置值:设置指定元素值。 插入:增加指定元素。 插入:增加指定元素。 删除:移去指定元素。 删除:移去指定元素。
《数据结构(C++版)(第2版)》

1.1.3 数据类型与抽象数据类型
1. 数据类型(data type)是指一个类型和 数据类型( ) 定义在这个类型上的操作集合。 定义在这个类型上的操作集合。 2. 抽象数据类型(Abstract Data Type, 抽象数据类型( , ADT)是指一个逻辑概念上的类型和这个 ) 类型上的操作集合。 类型上的操作集合。

《数据结构(C++版)(第2版)》

ADT Set
{ 数据:集合中有n( 数据:集合中有 (n≥0)个数据元素,元素类型为 )个数据元素,元素类型为T 操作: 操作: bool isEmpty(); //判断集合是否为空 判断集合是否为空 int length(); //返回集合的元素个数 返回集合的元素个数 bool contain(T x); //判断集合是否包含指定元素 判断集合是否包含指定元素x 判断集合是否包含指定元素 bool add(T x); //增加指定元素 增加指定元素x 增加指定元素 bool remove(T x); //移去首次出现的指定元素 移去首次出现的指定元素x 移去首次出现的指定元素 void clear(); //清空集合元素 //清空集合元素 void print(); //输出集合中所有元素 输出集合中所有元素 bool equals(Set s); //比较当前集合与集合 是否相等 比较当前集合与集合s是否相等 比较当前集合与集合 bool containAll(Set s); //判断当前集合是否包含集合 中的所有元素 判断当前集合是否包含集合s中的所有元素 判断当前集合是否包含集合 bool addAll(Set s); //增加集合 中的所有元素,集合并 增加集合s中的所有元素 增加集合 中的所有元素, bool removeAll(Set s); //移去那些也包含在集合 中的元素,集合差 移去那些也包含在集合s中的元素 移去那些也包含在集合 中的元素, bool retainAll(Set s); //仅保留那些也包含在集合 中的元素 仅保留那些也包含在集合s中的元素 仅保留那些也包含在集合 }

《数据结构(C++版)(第2版)》

1.2 算法
1.2.1 什么是算法 1.2.2 算法分析 1.2.3 算法设计

《数据结构(C++版)(第2版)》

1.2.1 什么是算法
1. 算法定义
① ② ③ ④ ⑤ 有穷性 确定性 输入 输出 可行性

2. 算法设计目标
① ② ③ ④ ⑤ 正确性 可读性 健壮性 高时间效率 高空间效率

《数据结构(C++版)(第2版)》

3. 算法描述
采用伪码描述顺序查找算法如下: 采用伪码描述顺序查找算法如下: 元素 search(关键字 key) 关键字 { e = 数据序列的第一个元素 数据序列的第一个元素; while (数据序列未结束 && e的关键字不是 的关键字不是key) 数据序列未结束 的关键字不是 e = 数据序列的下一个元素 数据序列的下一个元素; 返回查找到的元素或查找不成功标记; 返回查找到的元素或查找不成功标记 }
《数据结构(C++版)(第2版)》

4. 算法与数据结构

图1.6 线性表插入操作
《数据结构(C++版)(第2版)》

1.2.2 算法分析
1. 度量算法的时间效率
算法的时间效率指算法的执行时间随问题规模的 增长而增长的趋势, 增长而增长的趋势,通常采用时间复杂度来度量算法 的时间效率。 的时间效率。 T(n)=O(f(n))

2. 度量算法的空间效率
空间复杂度指算法在执行时为解决问题所需要的 额外内存空间,不包括输入数据所占用的存储空间。 额外内存空间,不包括输入数据所占用的存储空间。 S(n)=O(f(n))
《数据结构(C++版)(第2版)》

表1.2 时间复杂度随n变化情 况的比较
时间复杂度 O(1) O(log2n) O(n) O(nlog2n) O(n2) n=8(23) 1 3 8 24 64 n=10 1 3.322 10 33.22 100 n=100 1 6.644 100 664.4 10000 n=1000 1 9.966 1000 9966 106

《数据结构(C++版)(第2版)》

【例1.1】 算法时间复杂度分析。 】 算法时间复杂度分析。
1. 一个简单语句的时间复杂度为O(1)。 。 一个简单语句的时间复杂度为
int count=0;

2.

一个循环的时间复杂度为O(n)。 。 一个循环的时间复杂度为
int n=8, count=0; for (int i=1; i<=n; i++) count++;

3.

时间复杂度为O(log )的循环语句 的循环语句。 时间复杂度为O(log2 n)的循环语句。
int n=8, count=0; for (int i=1; i<=n; i*=2) count++;

4.

时间复杂度为O( 的二重循环。 时间复杂度为 n2)的二重循环。 的二重循环
int n=8, count=0; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) count++;
《数据结构(C++版)(第2版)》

【例1.1】 算法时间复杂度分析。 】 算法时间复杂度分析。
5. 时间复杂度为O(n×log2n)的二重循环。 × 的二重循环。 时间复杂度为 的二重循环
int n=8, count=0; for (int i=1; i<=n; i*=2) for (int j=1; j<=n; j++) count++; 时间复杂度为O(n×log2n)。 循环次数为 n × (log 2 n + 1) 。时间复杂度为 × 。

6.

时间复杂度为O( 的二重循环 的二重循环。 时间复杂度为 n)的二重循环。
int n=8, count=0; for (int i=1; i<=n; i*=2) for (int j=1; j<=i; j++) count++; log 2 n 时间复杂度为O( 。 总的循环次数为 ∑ 2 i = 1 + 2 + 4 + L + 2 log2 n = 2n ? 1 。时间复杂度为 n)。
i =0

《数据结构(C++版)(第2版)》

1.2.3 算法设计
【例1.2】 交换两个变量值问题讨论。 】 交换两个变量值问题讨论。
main()函数 中的变量 swap()函数 中的变量 i j x y 1 2 i变量的地址 j变量的地址 i j x y 2 1 i变量的地址 j变量的地址 (b) 交换结果
《数据结构(C++版)(第2版)》

(a) 指针类型参数传递地址

【例1.3】 求两个整数的最大公约 】 数。
1. 质因数分解法 2. 更相减损术
“以少减多,更相减损,求其等也,以等数约之。 以少减多,更相减损,求其等也,以等数约之。 等数约之,即除也, 等数约之,即除也,其所以相减者皆等数之重 故以等数约之。 叠,故以等数约之。” : (91,49)=(42,49)=(42,7)=7。 。

3. 欧几里德(Euclid)的辗转相除法 欧几里德( )
gcd(91,49)=gcd(49,42) =gcd(42,7)=gcd(7,0)=7
《数据结构(C++版)(第2版)》

【例1.4】 数组的顺序查找算法。 】 数组的顺序查找算法。
1. 顺序查找算法 2. 已排序数据序列的顺序查找算法

《数据结构(C++版)(第2版)》

【例1.5】 排序算法及其必要性。 】 排序算法及其必要性。
1. 2. 3. 4. 排序算法的必要性 直接插入排序 直接选择排序 任意数据类型T需 任意数据类型 需 要重载某些运算符

《数据结构(C++版)(第2版)》


相关文章:
第01章 绪论
第01章 绪论(C++) 26页 1财富值 第01章 绪论01 30页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
第01章 绪论
第01章 绪论2 68页 2财富值 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 5财富值 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值喜欢...
第01章 绪论
第01章 绪论2 68页 2财富值 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 5财富值 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值喜欢...
第01章 绪论
第01章 绪论2 68页 1下载券 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 2下载券 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1下载券 第01...
第01章 绪论
第01章 绪论2 68页 2财富值 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 5财富值 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值喜欢...
第01章 绪论
第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
第01章 绪论
第01章 绪论2 68页 2财富值 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 5财富值 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值喜欢...
第01章 绪论
第01章 绪论2 68页 2财富值 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 5财富值 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值喜欢...
第01章 绪论
第01章 绪论2 68页 2财富值 第01章 绪论1 66页 免费 第01章 绪论 19页 19页 5财富值 第01章绪论1 34页 免费 第01章 绪论(C++) 26页 1财富值喜欢...
第01章 绪论
第01章 绪论_教育学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 第01章 绪论_教育学_高等教育_教育专区。第1章 绪论 一、选择题 1. 算法的计算...
更多相关标签:
智慧树绪论章单元测试 | 绪论章单元测试 | 第一章 绪论 | 第一章 职业道德绪论 | 论文第一章绪论写什么 | 绪论可以作为第一章吗 | 硕士论文第一章绪论 | 旅游规划 第一章绪论 |