计算机科学导论数据结构与算法PPT课件

程序（存储在存储器中）
输入 8,12,22,3
输3,出8,12,22
冯•诺依曼模型（John Von Neumann1903－1957）
现代计算机都是基于冯•诺依曼模型
1. 4个子系统 2. 程序存储 3. 指令顺序执行
计算机硬件 计算机软件
12
计算机概述——计算机系统分层结构
通信
程序
网络，多台计算机联接在一起，实现信息交换和资 源共享
2
《计算机科学导论》教材
教材 《计算机科学导论》 机械工业出版社 刘艺等译 参考书：
➢ 计算机科学导论，王玲，宋斌编著，清华大学出版社， 2008
➢ 计算机科学导论（第2版），瞿中 等编著，清华大学 出版社， 2007
➢ 计算机科学导论（第7版）（影印版），布鲁克希尔 著，清华大学出版社 ，2004
第10讲：数据库
（第14章）
第11讲：人工智能与计算理论 （第17，18章）
学习建议
内容多，用系统的思想学习，掌握基本概念、 基本原理、基本操作；
听讲与自学相结合，可以快速浏览几本书，有 针对性的上网查阅或图书查阅；
多上机，多实践，提高动手能力
本讲内容
1.1．计算机系统分层结构 1.2．计算机的发展历史 1.3．计算机的分类 1.4．计算机应用
计算机科学导论
第一讲 概述
课程简介
《计算机科学导论》是计算机类各专业全程教学内容的导 引课程，介绍计算机硬件、软件、数据组织和计算理论等方面的 内容，包括编码及计算机体系结构的基本原理、操作系统、计算 机网络、算法、程序设计语言、数据结构和数据库、人工智能以 及计算理论等专业知识的知识点以及与信息技术有关的社会人文 等知识，力求使学生对计算机科学有比较全面的了解。与此同时， 使读者对后续课程的学习有一个概括的了解，为今后的学习打下 良好的基础。

第二十六页，共37页。
Page 26
(5)循环语句 ①while<表达式> { } ②do { }while<表达式>; ③for(<赋初值表达式1>;<条件表达式2>;<步长表达式3>) (6)返回(fǎnhuí)语句 return(<返回(fǎnhuí)表达式>); (7)定义函数语句 (8)调用函数语句
那么(nà me)对应的二元组表示为B=(D,R)，其 中： D={s1,s2,s3,s4,s5,s6 } R={r} r={<s1,s2>,<s2,s3>,<s3,s4>,<s4,s5>,<s5,s6> }
第十页，共37页。
Page 10
用图形可以形象地表示这种数据(shùjù)结构，如图1.2所示，图形中的每 个结点对应着一个数据(shùjù)元素，两结点之间的连线对应着关系中的 一个序偶。
请根据时间复杂度分析法比较高斯和他的 小伙伴们的算法优劣。
第三页，共37页。
Page 3
1.2 知识点学习(xuéxí)——1.2.1 数据结构
1.2.1.1 数据结构相关概念 数据是用符号对现实世界的事物及活动做出
的抽象描述，其中符号可以是文字符号、数 字符号以及(yǐjí)其他规定的符号。 数据元素是数据的根本单位。例如，202102 班点名册中的每个学生记录都是一个数据元 素。数据元素也可称为元素、结点、顶点、 记录等，在计算机中通常被作为一个整体来 进行考虑和处理。
>,<75,82>} r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36

• 空表：表内无元素（长度为0）的表称为空表。 • 表头：称Ls的第1个元素为Ls的表头。 • 表尾：称Ls中除去表头后其余元素构成的表为表尾。
显然，表尾一定是表，但表头不一定。
• 递归表: 若表Ls中某成员含有自己(即Ls)，则称Ls为递归 表。
5
• 深度：Ls的深度Depth(Ls)递归地定义为：
• 元素共享性：在同一广义表中，任一元素（单元素或 表）均可以出现多次，同一元素的多次出现都代表的是 同一个目标，可以认为它们是共享同一目标。对多次出 现的元素，显然可以从不同的位置（路径）访问它们， 因此，具有该特性的表也称再入表(Reentrant List)。
13
§8.1.5 基本操作
广义表兼有线性表和树的 特性，因此，它的基本操 作也兼有线性表和树的一 些操作，此外，还有一些 特有操作，如求表头和表 尾。 求表头和表尾是广义表的 重要操作，通过它们，可 以按递归方法处理广义表， 也可实现一般访问。著名 的人工智能语言LISP和 Prolog其实就是以广义表为 数据结构，通过求表头和 表尾实现对象的操作。
8
错误！未找到引用源。给出了广义表图的一个例子。
显然，广义表图中画出了广义表的所有结点。图中结点
之间的边表示“包含/属于”关系，即若结点A到B有边， 则表示B是A的子表之一（A包含B）。
广义表图与树相似，只是
L
由于存在共享元素，使得
广义表图中某些结点
A
C
DE
的“父亲”不唯一。
B
c de
ab
图 8-0 广义表L（见下式） 的逻辑图L(A(B(a,b)), C(B(a,b), c), D(c,d,e), E(e) )
12
• 元素分层性：如果将广义表中不同出现的元素看作不 同的元素，则广义表是层次结构，即对任一元素，它只 直属层号比它大1的元素。不过，广义表的层次性与树 不同，在树中，任一元素只直属一个元素。

算法的特性
一个好的算法应该具有可读性、正确 性、健壮性、可维护性和高效性等特 性。可读性要求算法易于理解，正确 性要求算法能够正确地解决问题，健 壮性要求算法能够处理异常情况，可 维护性要求算法易于修改和改进，高 效性要求算法在有限的时间内完成计 算任务。
算法的复杂度分析
算法的复杂度分析是评估算法性能的 重要手段。通过对算法的时间复杂度 和空间复杂度进行分析，可以了解算 法在不同情况下的性能表现，从而选 择更合适的算法来解决实际问题。
逻辑模型
逻辑模型是在概念模型的基础上进一步细化的数据模型， 用于描述数据的结构和操作，常见的有关系模型和面向对 象模型。
物理模型
物理模型是对数据在计算机中的存储和访问方式的描述， 包括数据的存储结构、数据的访问方式等。
关系数据库管理系统
关系数据库
关系数据库管理系统
关系数据库是一种基于关系的数据库，它 使用关系表来存储数据，每个表由行和列 组成。
全对于个人隐私保护、企业数据安全以及国安全的属性
计算机安全应具备保密性、完整性、可用性和可控性四个基本属性。
常见的计算机安全威胁
恶意软件
包括病毒、蠕虫、特洛伊木马等，这些软件会在用户不知 情的情况下，在其电脑上安装后门、收集用户信息，甚至 破坏用户数据。
身份盗用
指攻击者利用窃取到的用户个人信息，假冒用户身份进行 违法活动，这种行为会导致用户财产和精神损失。
高级语言
更接近自然语言，易于编写和理解，如C、Java、Python等。
脚本语言
主要用于自动化任务，如Shell脚本、JavaScript等。
编程的基本概念
变量
用于存储数据，可以随时修改。
数据类型
定义变量可以存储的数据类型，如整数、浮点数、 字符串等。

人工智能领域中，数据结构对于机器学习、深度学习等算法的效率至关重要。例如，使用决策树、神经网络等数据结构进行分类、预测等任务。
数据结构在人工智能中的优化可以提升算法的效率和准确性，例如通过使用哈希表实现快速特征匹配，提高图像识别速度。
THANK YOU
定义与分类
添加边、删除边、查找路径等。
基本操作
图中的边可以是有方向的，也可以是无方向的。节点之间可以有多种关系，如邻接、相连等。
特性
社交网络、交通网络、路由协议等。
应用场景
05
排序与查找算法
冒泡排序：通过重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
详细描述
链表的优势在于可以动态调整大小，插入和删除操作仅需修改指针，时间复杂度为O(1)。但链表访问特定元素需要从头部遍历，效率较低。
VS
栈和队列是特殊的线性数据结构，它们遵循特定的操作规则。栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。
详细描述
栈用于保存按照后进先出顺序访问的数据元素，常见的操作有压栈、弹栈和查看栈顶元素。队列用于保存按照先进先出顺序访问的数据元素，常见的操作有入队、出队和查看队首元素。
03
线性数据结构
数组是线性数据结构中的基本形式，它以连续的内存空间为基础，用于存储固定长度的同类型元素。
数组具有固定的长度，可以通过索引直接访问任意元素。它适合于需要快速访问数据的场景，但插入和删除操作需要移动大量元素，效率较低。
详细描述
总结词
总结词
链表是一种线性数据结构，它通过指针链接各个节点，节点包含数据和指向下一个节点的指针。

(1)有且只有一个根结点
(2) 每个节点最多有一个前件,也最多有一个后件.
B 、线形表的顺序存储结构
是计算机中存储线形表的最简单的方法.
两个基本特点:
(1)线形表中所有元素所占的空间都是连续的
(2)线形表中各数据元素在存储空间中是按逻辑顺序
2020/12/10 依次存放的
5
3 、栈及基本运算
(1)栈的概念:
2、二叉树的特点 （1）在第K层上，最多有2k-1（K>=1）个结点
（2）深度为M的二叉树，最多有2M-1个结点（深度指层数）
（3）任何二叉树中，度为0的结点（叶子）总比度为2的结 点多一个
2（020/412）/10 具有n个结点的二叉树，深度至少为[lon2n]+1
9
3、完全二叉树和满二叉树 完全二叉树 是指最后一层外，每一层上的结点数均达到最大值， 在最后一层上只缺少右边的若干结点。 满二叉树 满二叉树是指除最后一层外，每一层上的所有结点有 两个子结点，则在第K层上有2k-1个结点，深度为m的 满二叉树有2m-1个结点。
特点: “先进先出” FIFO 或”后进后出” LILO
队列运算: 入队:从队尾插入 退队:从队头删除
2020/12/10
7
5 、线性链表
(1)概念: 线性表的链式存储结构称为线形链表.
(2)存储原理:
把存储结点分成两部分,第一部分存储数据元素,第二
部分存储下一元素的序号(即存储结点的地址).
(3)特点:
时间复杂度:是指执行算法所需要的计算工作量.
空间复杂度:是指执行算法所需要的内存空间.
存储空间包括:算法程序所占空间,输入原始数据所占空间
执行算法时需要的额外空间.

//按增量序列dlta[0…t-1]对顺序表L作Shell排序
for(k=0；k<t；++k)
dk值依次装在dlta[t]中
ShellSort(L，dlta[k])； //增量为dlta[k]的一趟插入排序
但链表无法“折半”！
折半插入排序的改进——2-路插入排序267
精选课件ppt
15
折半插入排序的算法分析
• 折半查找比顺序查找快，所以折半插入排序 就平均性能来说比直接插入排序要快。
• 在插入第 i 个对象时，需要经过 log2i +1 次 关键码比较，才能确定它应插入的位置。因 此，将 n 个对象用折半插入排序所进行的关 键码比较次数为：n*log2n
精选课件ppt
10
例2：关键字序列T= （21，25，49，25*，16，08），
请写出直接插入排序的具体实现过程。 *表示后一个25
解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或 暂存单元（Temp）。则程序执行过程为：
初态：
22410暂存59856*
021816
21156
2425951*
2459*
21445699*
49 08
0 123456
完成!
i=1 i=2 i=3 i=4 i=5 i=6
时间效率： O(n2)——因为在最坏情况下，所有元素的比较
次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况
下还要加上移动元素的次数。
空间效率：O（1）——因为仅占用1个缓冲单元
算法的稳定性：稳定——因为25*排序后仍然在25的后面。
技巧：子序列的构成不是简单地“逐段分割”，而是将 相隔某个增量dk的记录组成一个子序列,让增量dk逐趟 缩短（例如依次取5,3,1），直到dk＝1为止。

自然语言处理
自然语言处理中，数据结构用于表示句子、单词之间的关系，如依 存句法树。
计算机视觉
计算机视觉中的图像处理和识别使用数据结构来存储和操作图像信 息，如链表和二叉树。
算法在计算机科学中的应用
加密算法
加密算法用于保护数据的机密性和完整性，如 RSA算法用于公钥加密。
排序算法
排序算法用于对数据进行排序，如快速排序和归 并排序广泛应用于数据库和搜索引擎中。
归并排序
将两个或两个以上的有序表组合成一个新的有序表。
查找算法
线性查找：从数据结构的一端开始逐 个检查每个元素，直到找到所查找的 元素或检查完所有元素为止。
二分查找：在有序数据结构中查找某 一特定元素，从中间开始比较，如果 中间元素正好是要查找的元素，则搜 索过程结束；如果某一特定元素大于 或者小于中间元素，则在数组大于或 小于中间元素的那一半中查找，而且 跟开始一样从中间元素开始比较。如 果在某一步骤数组为空，则代表找不 到。这种搜索算法每一次比较都使搜 索范围缩小一半。
04
常见算法实现
排序算法
冒泡排序
通过重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复 地进行直到没有再需要交换，也就是说该数列已经排序完成。
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按 此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
数据结构在计算机科学中的应用
1 2
数据库系统
数据结构是数据库系统的基础，用于存储、检索 和管理大量数据。例如，B树和哈希表在数据库 索引中广泛应用。

{
change=false;
for(j=0;j<I;++j)
if (a[j]>a[j+1]) {
a[j] ←→a[j+1];
change=TURE}
}
最好情况：0次
最坏情况：1+2+3+…+n-1
=n(n-1)/2
平均时间复杂度为:O(n2)
1.4.4算法的存储空间需求
空间复杂度:算法所需存储空间的度量， 记作:
例3、整数的数据对象是{…-3，-2，-1，0，1， 2，3，…}
英文字符类型的数据对象是{A，B，C，D，E，
1.3 抽象数据类型的表示和实现
P11
1.4 算法和算法分析
算法：是对特定问题求解步骤的一种描述
算法是指令的有限序列，其中每一条指令 表示一个或多个操作。
算法具有以下五个特性：
(3)健状性(Robustness) 算法应具有容错处理。 当输入非法数据时，算法应对其作出反应，而 不是产年莫名其妙的输出结果。
(4)效率与存储量需求 效率指的是算法执行的 时间；存储量需求指算法执行过程中所需要的 最大存储空间。一般，这两者与问题的规模有 关。
1.4.3 算法效率的度量
对一个算法要作出全面的分析可分成两用人 才个阶段进行，即事先分析和事后测试
(a1，a2，…an)
这里的数据元素ai(1≦i≦n)只是一个抽象的符 号，其具体含义在不同的情况下可以不同。
例1、26个英文字母组成的字母表
（A，B，C、…、Z）
例2、某校从1978年到1983年各种型号的计算 机拥有量的变化情况。
（6，17，28，50，92，188）

算法设计技巧
讲解了一些常用的算法设计技巧 ，如分治法、贪心算法、动态规 划等。
算法分析
讲解了时间复杂度和空间复杂度 的概念，以及如何分析算法的效 率。
常见算法
介绍了各种常见算法，如排序、 搜索、图算法等，并讨论了它们 的实现和应用。
算法与数据结构的发展趋势
并行计算
随着多核处理器的普及，并行计 算成为算法与数据结构发展的重 要趋势。
解决实际问题
数据结构是解决实际问题 的关键，如排序、查找等 。
培养逻辑思维
学习数据结构有助于培养 人的逻辑思维和问题解决 能力。
Part
04
常见数据结构详解
数组
数组是一种线性数据结构，用于存储 相同类型的数据元素。
数组在内存中是连续的，可以通过索 引直接访问任意元素。数组的优点是 访问速度快，缺点是插入和删除操作 需要移动大量元素。
算法的表示方法
总结词
介绍算法的常见表示方法
详细描述
算法可以用自然语言、伪代码、流程图、程序设计语言等多种方式来表示。这些 表示方法各有优缺点，可以根据需要选择适合的方式。
算法的复杂度分析
总结词
分析算法的时间复杂度和空间复杂度
详细描述
算法的复杂度分析是评估算法性能的重要手段。时间复杂度关注算法执行所需的时间，空间复杂度关注算法所需 存储空间。通过分析复杂度，可以了解算法在不同规模输入下的性能表现。
末尾。
快速排序
采用分治策略，选取一个基准元素 ，重新排列序列，使得基准元素左 侧的元素都比它小，右侧的元素都 比它大。
归并排序
将待排序序列不断划分成两半，分 别进行排序，最后合并成一个有序 序列。
查找算法
线性查找
从头到尾依次比较每个元素，直到找到目标元素或遍历完整个序列 。

//按串名提取串中第i个字符
if ( i < 0 && i >= curLen ) {
cout << “Out Of Boundary!\n ”; exit (1) ;
}
return ch[i];
}
精选编辑ppt
12
String &String:: //串连接
operator += ( const String &ob ) {
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String & ob);
String ( const char *init );
String ( );
~String ( ) { delete [ ] ch; }
int operator != ( const String &ob )
const { return strcmp (ch, ob.ch) != 0; }
int operator ! ( )
const { return curLen == 0; }
String &operator = ( const String &ob );
String &operator += ( const String &ob );
char &operator [ ] ( int i );
int Find ( String pat ) const;
}
精选编辑ppt
4
字符串部分操作的实现