计算机导论-7-数据结构与算法

辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院1辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院2第7讲数据结构与算法辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院3数据结构（datastructure）数据结构的基本概念典型的数据结构算法（algorithm）算法的基本概念算法的描述方法衡量算法的优劣数据结构与算法辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院41、数据结构的基本概念数据结构（datastructure）：数据元素之间抽象化的关联构造。（重在元素之间的逻辑关系及数据处理）数据结构的作用（1）Pascal之父——NicklausWirth：算法+数据结构=程序（2）数据结构是程序设计之前必须先考虑好的问题（3）以数据为中心设计程序，因此，数据结构是关键。数据结构设计得当，程序设计得心应手，事半功倍；数据结构设计不好，程序设计事倍功半，甚至无从下手。数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院51、数据结构的基本概念数据结构的使用强调灵活运用，《数据结构》课程讲授典型的数据结构与处理算法，但实际应用中要综合，要变通，要深刻理解数据结构的思想，要有自己的设计。要学会将看似截然不同的问题抽象成相同的数据结构。例如：（1）某班级学生信息表的处理：线性表（2）某单位组织结构信息的处理：树（3）某地区公路网信息的处理：图以上问题都能在《数据结构》课程中找到标准的数据结构和处理算法。（4）补考排考场的处理这个问题可用“图”来组织数据，但在《数据结构》课程中没有相应算法。数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院61、数据结构的基本概念数据元素和数据项（1）数据（data）：所有能输入计算机并被计算机程序所处理的符号的总称。（2）数据元素（dataelement）：数据的基本单位，通常作为一个整体进行处理。又称结点（node）或记录（record）。（3）数据项（dataitem）：数据的不可分割的、具有独立意义的最小单位。有时称为字段或域（field）。（数据元素有哪些组成成分）数据结构数据元素（一名学生）学号6012410109姓名张三性别男政治面貌党员…………数据项1数据项2数据项3数据项4……辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院71、数据结构的基本概念逻辑结构与物理结构（1）数据逻辑结构（datalogicalstructure）：数据元素之间存在的一种或多种特定的关系。（2）数据物理结构（dataphysicalstructure）：数据在计算机中的存放方式，即数据逻辑结构在计算机存储器中的实现。（数据是如何在存储器中存放的）数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院81、数据结构的基本概念四种基本的逻辑结构数据结构集合线性结构树形结构图形结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院92、典型的数据结构线性表（list）：n（n≥0）个数据元素的有限序列（a1,a2,…,an）。（1）长度：线性表中数据元素的个数。（2）空表：长度为0的线性表。（3）直接前驱（immediatepredecessor）与直接后继（immediatesuccessor）ai是ai+1的直接前驱，ai+1是ai的直接后继。（4）基本操作：初始化空表、求长度、判断空表、置空、取第i号元素、定位（给定元素值）、修改元素、插入元素、删除元素。数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院102、典型的数据结构线性表（5）栈（stack）：只能在一端进行插入和删除操作的线性表。栈的插入：进栈、入栈、压栈栈的删除：退栈、出栈、弹栈栈的操作特点：先进后出（后进先出）（6）队列（queue）：只允许在表的一端插入元素，在表的另一端删除元素。队头：删除端队尾：插入端。队列的操作特点：先进先出（后进后出）数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院112、典型的数据结构线性表（7）线性表的应用（1）一组数据元素，互相之间地位平等（可能有先后次序，除此之外没有其他逻辑关系）。例如：30名学生、10个班级、100本书等例如：操作系统中的进程表、FAT表（2）栈的应用：例如：子程序调用的实现、表达式计算的实现、语法分析等（3）队列的应用：例如：操作系统中的作业队列、打印队列、缓冲区等数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院122、典型的数据结构树（tree）：n（n≥0）个结点的非线性结构；有且只有一个结点称为根（root）；余下结点分为m(m0)个不相交的集合，每个集合又是一棵树，称为根的子树（subtree）。数据结构ABCDGEFIHJ根子树辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院132、典型的数据结构树树的应用：一组数据元素，互相之间地位不平等，有严格的上下级层次关系。例如：文件索引的B+树、目录组织的树形结构网络交换机的生成树某单位的组织结构（如辽科院，之下分n多二级教学单位和职能部门，每个二级单位/部门下又分教研室、科室等）某些棋类对弈问题数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院14树……..……..…...…...…...…...例：人机对奕问题辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院152、典型的数据结构图（graph）：n个数据元素，任意两个元素之间都可能存在逻辑关系。（1）逻辑结构：G=(V,E)V：顶点（图结点）的有穷集合。E：边（两个顶点间的关系）的有穷集合。数据结构1234134无向图有向图2辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院162、典型的数据结构图（2）图的应用：一组数据元素，互相之间地位平等，互相之间都可能存放某种逻辑关系。例如：网络中的路由器交通图、电路图、列车运行图、地下管网棋类对弈迷宫、一笔画很多人工智能问题……数据结构辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院17ABACADBABCBDDADBDCEAEBECED图CEDAB例：多叉路口交通灯管理问题辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院18ABHIGCEDF1812979525631108598672145834（a）城市距离图ABHIGCEDF12979311021834（b）联通各城市最小生成树例：多城市间最小距离问题辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院19例：【八皇后问题】高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？这个问题可以抽象成图的问题，用图形结构和图的遍历算法来解决。辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院20例：【华容道游戏】如何使大方块（曹操）从重围中走出来？（除大方块可以最终移出出口外，所有块都只能在盒内向相邻的空格移动，）这个问题可以抽象成图的问题，用图形结构和图的遍历算法来解决。出口辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院211、算法的基本概念算法（algorithm）：为求解问题而采取的方法和步骤。算法分类：数值运算算法、非数值运算算法。算法的特征（1）有穷性：包含有限的操作步骤。（步骤数和时间上都有限）（2）确定性：每一个步骤都是确定的，没有歧义。（3）有效性：每一个步骤都有效执行，并得到确定的结果。（4）有零个或多个输入：从外界取得必要的信息。（5）有一个或多个输出：整个算法必须获得结果。算法辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院222、算法的描述方法流程图（flowchart）（1）基本符号（2）例：求最大公约数算法起止框输入输出框处理框判断框流线连接点开始输入m，nr=m%nr==0?m=nn=r输出n结束YN辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院232、算法的描述方法伪代码（pseudocode）：类似程序设计语言，但不那么严格、不那么形式化的算法描述方法。（1）赋值、输入、输出（2）程序块、顺序执行：begin…end（3）选择执行：if、switch（4）循环执行：while、for算法例：求最大公约数begininputm,n;r=m%n;whiler0beginm=n;n=r;endoutputn;end辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院243、衡量算法的优劣算法设计的要求（1）易读性：格式整洁，命名规范。易于阅读和理解，易于调试修改和扩充。（2）健壮性：对于非法输入，算法应作出反应或处理。（容错）（3）高效性：达到所需的时空性能。尽可能省时间（时间效率高）、省空间（空间效率高）。算法辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院253、衡量算法的优劣复杂度（complexity）用O(关于n的表达式)作为时间或空间复杂度的表示，其中“关于n的表达式”忽略常数项、低次项。（n代表问题规模，一般代表待处理的数据量——数据元素数）常见时间复杂度（timecomplexity）O(1)——常数阶（算法所需时间与问题规模无关）O(logan)——对数阶O(n)——线性阶（算法所需时间与问题规模成正比）O(n2)——平方阶、O(n3)——立方阶、……O(an)——指数阶O(nlogan)算法辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院263、衡量算法的优劣常见空间复杂度（spacecomplexity）O(1)——常数阶（算法所需辅助空间与问题规模无关）O(logan)——对数阶O(n)——线性阶（算法所需辅助空间与问题规模成正比）O(n2)——平方阶、O(n3)——立方阶、……O(an)——指数阶O(nlogan)算法辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院273、衡量算法的优劣举例：输入正整数n，输出n的所有因数。begininputn;fork=1tonbeginifn%k=0thenoutputk;endend算法时间复杂度：O(n)空间复杂度：O(1)辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院283、衡量算法的优劣举例：输入20个数，求最大值。begininputmax;fork=1to19begininputt;iftmaxthenmax=t;endoutputmax;end算法时间复杂度：O(n)空间复杂度：O(1)辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院29数据结构专门一门课程讲授数据结构（含线性表、树、图、排序、查找等内容）相关的主要课程辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院30多了解一些辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院31高德纳——唐纳德·克努斯辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院32高德纳——唐纳德•克努斯算法和程序设计技术的先驱者1938年出生于密尔沃基。1956年就读凯斯理工学院，1960年同时获学士和硕士学位，之后在伯克利攻读数学博士学位。1963年毕业后，在伯克利任教。1962年，世界著名出版社Addison-Wesley向他约稿，他原计划出7卷。1968年《计算机程序设计艺术》第一卷出版（基本算法）。同年，到斯坦福任教。第二年，第二卷出版（半数值算法）。1973年，第三卷出版（排序与查找）。辽宁科技学院电气与信息工程学院辽宁科技学院电气与信息工程学院33高德纳——唐纳德•克努斯算法和程序设计技术的先驱者1974年，仅36岁就因《计算机程序设计艺术》而获图灵奖。之后辍笔，但创造了字体设计系统METAFONT、文学化编程、排版系统TEX。1979年，获美国国家