计算机科学导论-数据结构与算法综述

第5讲数据结构与算法理解数据结构的概念，理解数据结构的逻辑和存储结构；理解算法的概念和算法的基本特性，了解算法复杂度的度量方法；理解线性数据结构，理解顺序存储和链式存储的存储方法；描述栈和队列、串和数组这几个线性数据结构的概念；了解非线性的数据结构，了解树、二叉树以及图的概念和数据结构；理解排序的概念，描述插入、选择、气泡和快速排序的算法；理解查找的概念，描述顺序查找和折半查找的算法，并能够比较它们理解递归的概念，能够在实践中了解递归的应用。

教学目的学习重点数据结构的基本概念算法的描述、流程图的使用以及算法的复杂度的衡量顺序存储和链式存储的方法栈、队列、串和数组的概念和用法二叉树数据结构查询、排序和递归算法第一节数据结构概述1.数据结构概述1.1《数据结构》研究的对象(1)对所加工的对象进行逻辑组织(2)如何把加工对象存储到计算机中去(3)数据运算数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作

[例5-1]设有一个电话号码薄，有N个人的姓名和电话号码。要求设计一个程序，按人名查找号码，若不存在则给出不存在的信息。1.数据结构概述1.2数据结构相关概念1.基本概念和术语

数据元素、结点、数据项、关键字或主关键字、次关键字、数据对象、数据结构

2.数据结构

特性相同的数据元素构成的集合中，如果在数据元素之间存在一种或多种特定的关系，则称之为数据结构。

Data-Structure=(D,R)

其中，D是数据元素的有限集，R是D上关系的有限集。1.数据结构概述1.数据结构概述3.四类基本的数据结构集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构，各元素间没有直接的关联。线性结构。该结构的数据元素之间存在着一对一的关系。树型结构。该结构的数据元素之间存在着一对多的关系。图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。

123456[例5-2]线性数据结构=(D,S)

D={1,2,3,4,5,6,7,8,9,10}

S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>,<7,8>,

<8,9>,<9,10>}

1.数据结构概述[例5-3]图形数据结构=(D,R)D={1,2,3,4,5,6,7,8,9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}1.数据结构概述

[例5-4]树形结构=（D,R）D={a,b,c,d,e,f,g,h,i,j,k,l}R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<b,g>,<c,h>,<c,i>,<c,j>,<d,k>,<d,l>}1.数据结构概述1.3数据结构的分类

1、按数据结构的性质划分

数据的逻辑结构——数据元素之间的逻辑关系（设计算法——

数学模型）数据的物理结构——数据结构在计算机中的映像（存储结构，算法的实现）

2、按数据结构的操作来划分

静态结构——经过操作后，数据的结构特征保持不变（如数组）。

半静态结构——经过操作后，数据的结构特性只允许很小变迁（如栈、队列）。

动态结构——经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。1.数据结构概述1.3数据结构的分类

3、按数据结构在计算机内的存储方式来划分

顺序存储结构——借助元素在存储器的相对位置来表示数据元素之的逻辑关系。

链式存储结构——借助指示元素存储地址的指针表示数据元素之间的逻辑关系

索引存储结构——在存储结点的同时，建立附加的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。

散列存储结构——根据结点的关键字直接计算出该结点的存储地址。说明：四种存储方法可结合起来对数据结构进行存储映像。1.数据结构概述1.4算法及其描述和算法分析

1、算法的概念及特征

算法:

对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列。

算法具有以下五个重要的特征：

1）有穷性：一个算法必须保证执行有限步之后结束。

2）确切性：算法的每一步骤必须有确切的定义。

3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。

4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。

5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。1.数据结构概述1.4算法及其描述和算法分析

2、算法的描述:

1）流程图

2）伪代码——类程序设计语言

3、算法的基本结构:

1）顺序结构

2）分支结构

3）循环结构1.数据结构概述1.数据结构概述

算法基本结构示意图1.4算法及其描述和算法分析

4、算法效率衡量方法与准则:

时间复杂度：指算法从开始执行到处理结束所需要的总时间。

T（n）=O（f(n)）

空间复杂度：指算法从开始执行到处理结束所需的存储量空间的总和。

S（n）=O（g(n)）1.数据结构概述1.4算法及其描述和算法分析

5、算法与数据结构的关系:计算机科学家沃斯（N.Wirth）提出的:“算法+数据结构=程序”揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。1.数据结构概述第二节线性结构2.1线性表

1.线性表的定义

线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同的属性，表中相邻元素间存在“序偶”关系。 记做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an)

其中，ai-1称为ai

的直接前驱元素，ai+1是ai的直接后继元素

线性表的长度：表中的元素个数n

位序：i称元素ai在线性表中的位序2.线性结构2.1线性表

2.线性表的顺序表示和实现

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。

2.线性结构2.1线性表

2.线性表的顺序表示和实现

顺序表——线性表的顺序存储表示

ConstLIST_INIT_SIZE=100;(C++规范) ConstLISTINCREMENT=10; #defineLIST_INIT_SIZE100(C规范) TypedefStruct{ Elemtype *elem; Int length; Int listsize; Int incrementsize; }SqList;2.线性结构2.线性结构2.1线性表3.线性表的链式表示和实现

链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存贮单元的地址，这两部分信息组成一个“节点”。2.线性结构2.1线性表

3.线性表的链式表示和实现

单链表——线性表的链式存储表示

数据域（data）和指针域（next）存储表示

typedefstructLnode{ ElemType data; StructLnode *next; }Lnode,*LinkList;

2.线性结构2.线性结构2.1线性表

3.线性表的链式表示和实现

双向链表（循环链表）——线性表的链式存储表示

概念：两个指针，分别指向前驱元素和后继元素

typedefstructDuLnode{ ElemType data; StructDuLnode *prior; StructDuLnode *next;}DuLnode,*DuLinkList;2.线性结构2.2栈和队列1.栈的定义

栈（Stack）是限定只能在表得一端进行插入和删除操作得线性表，又称限定性线性表结构。2.栈的结构特点和操作

栈顶(Top)、栈底(Bottom),先入后出(LIFO)栈的基本操作

InitStack（&S）GetTop(S,&e)DestroyStack(&S)Push(&S,e)ClearStack(&S)Pop(&S,&e)StackEmpty（S）StackTraverse(S)StackLength（S）2.线性结构堆栈结构示意图2.线性结构2.2栈和队列3.队列的定义

队列（Queue）是限定只能在表得一端进行插入在表的另一端进行删除操作的线性表。4.队列的结构特点和操作

队列头(front)、队列尾(rear)，先入先出(FIFO)队列的基本操作

InitQueue(&Q)GetHead(Q,&e)DestroyStack(&S)EnQueue(&Q,e)ClearQueue(&Q)Dequeue(&Q,&e)QueueEmpty(Q)QueueTraverse(Q)QueueLength(Q)2.线性结构2.3串和数组1.串的定义和表示方法串定义

串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成字符串，由零个或多个字符组成的有限序列。

S＝“a0a1.....an-1”串的长度：n空串：n=0，NullString子串与主串，子串的位置（从0开始）串的比较：最大相等前缀子序列2.线性结构2.3串和数组1.串的定义和表示方法串的表示方法

定长顺序存储表示

两种表示方法：

1)下标为0的数组存放长度(pascal) typedefunsignedcharSString[MAXSTLEN+1];2)在串值后面加‘\0’结束(C语言)

堆分配存储表示串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。2.线性结构2.3串和数组2.数组的定义和操作数组定义数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识。数组可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。二维数组定义其数据元素是一维数组的线形表。N维数组定义其数据元素是N－1维数组的线形表。2.线性结构2.3串和数组2.数组的定义和操作数组的操作initarray(&A,n,bound1,bound2...boundn)——初始化Destroyarray(&A)——删除数组value(A,&e,index1,index2......indexn)——赋值assign(&A,e,index1,index2......indexn)——分配数组2.线性结构2.3串和数组3.数组的存储方式和表示数组元素的两种存储方式行主序存储列主序存储数组中元素在内存映象中的关系:二维数组A[m][n] LOC[i,j]=LOC[0,0]+(i*n+j)*L三维数组B[p][m][n] LOC[i,j,k]=LOC[0,0,0]+(i*m*n+j*n+k)*L2.线性结构第三节非线性结构3.1树

1.树的定义与结构特点

树的定义

n(n>=0)个数据元素（结点）的有限集D，若D为空集，则为空树。否则：在D中存在唯一的称为根的数据元素；

当n>1时，其余结点可分为m（m>0）个互不相交的有限子集T1，T2，......，Tm，其中每个子集本身又是一颗树，并成为根的子树。

3.非线性结构3.1树1.树的定义与结构特点

树的结构特点

树具有下面两个特点：

(1)树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点。

(2)树中所有节点可以有零个或多个后继节点。3.非线性结构3.非线性结构典型的树结构3.1树

2.二叉树

二叉树的定义二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

3.非线性结构二叉树的五种基本形态

2.二叉树

满二叉树和完全二叉树

满二叉树（fullbinarytree）：所有结点度为2，叶子结点在同一层次。

完全二叉树（completebinarytree）：一棵深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的节点与满二叉树中编号为i的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。3.非线性结构3.1树

3.树的运算

树的运算主要是插入节点、删除节点和遍历等几种。插入节点、删除节点运算改变树的结构，但要求在改变结构的同时，保持树的特性不变，对于二叉树，插入和删除操作后的树仍然是一棵二叉树。这两个操作过于复杂，在专业书籍中介绍，在此不做详细讨论。

3.非线性结构3.1树

3.树的运算树的基本运算操作：

InitTree（&T）

DestroyTree（&T）

CreateTree(&T,definition)TreeEmpty(T)TreeDepth(T)Parent(T,e)LeftChild（T，e）

Rightsibling(T,e)InsertChild（&T,&p,i,C）

DeleteChild（&T,&p,i）

Traverse（T）3.非线性结构3.2图

1.图的定义与相关概念

图的定义

图是由一组节点（vertex）的有穷集V(G)和和一组顶点间的连线(arc)的集合E(G)组成的一种抽象数据结构。记做：G＝(V，E)。V是数据结构中的数据元素，E是集合上的关系

3.非线性结构3.2图

1.图的定义与相关概念

图的相关概念弧(arc)、弧头（终点）、弧尾（起点）：<v,w>表示从v到w的弧

有向图(digraph)、无向图(undigraph)、边:(v,w)代表<v,w>和<w,v>

有向网、无向网：带权的有向图和无向图

完全图（completegraph）：边e为n(n-1)/2有向完全图：弧e为n(n-1)

3.非线性结构3.非线性结构3.2图

2.图的运算

图的基本运算添加顶点——将一个新顶点插入到图中添加边——连接一个顶点和一个目标顶点删除顶点——从一个图里移除一个顶点，同时删除连接顶点的边。查找顶点——通过遍历图来查找特定的顶点。图的遍历——指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次说明：图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上。3非线性结构第四节算法主要内容一、算法概念二、算法结构三、算法表示（流程图、伪代码、N-S图等）四、基本算法（计数，累加，值交换，求最大（小）值，穷举、迭代、递推、递归）

一、算法的概念1.算法的定义为解决问题而采取的方法和步骤。（非正式）算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。（正式）

2.算法的分类计算机算法可分为两大类：数值运算算法：求解数值非数值运算算法：事务管理例1:

数值计算问题：结构静力分析计算需要解线性代数方程组。例2:

非数值计算问题：计算机对弈

算法—对弈的规则和策略

模型—棋盘及棋盘的格局3.算法的基本特征有穷性：任何算法都会在有限步后终止；确定性：算法的每一步都有唯一的含义；有效性：算法的每一步都可以被执行；有输入：可以有多个输入，也可能没有输入；有输出：算法至少有一个输出结果。

4.算法设计的原则正确性：对于一切合法的输入数据都能得出满足要求的结果。可读性：算法应该易理解，便于交流。健壮性：当输入非法数据时，算法应恰当地作出反应或进行相应处理。高效率与低存储量需求：算法执行时间较少，算法执行所需存储空间较小。定义动作确定一系列的步骤，每一步都只完成一个动作。精化剔除重复的步骤；不同的步骤完成的动作可能相同，但它们产生的结果不能相同。泛化使算法对尽可能多的具体问题具有适应性。5.如何设计一个算法例1：从一组正整数中找到最大的数。（正整数个数＝2，3，…N）例如,

12,8;

12,8,13;

12,8,13,9; 12,8,13,9,11,…..方法1：第一步:

比较第一个数和第二个数;第二步:

比较第一个数和第三个数;第三步:比较第二个数和第三个数;方法2：第一步：将最大值置为第一个数；第二步：将第二个数和最大值进行比较，如果第二个数大于最大值，将最大值置为第二个数，反之保持最大值不变。第三步：将第三个数和最大值进行比较，如果第三个数大于最大值，将最大值置为第三个数，反之保持最大值原值不变。第二、三步程序功能相同，程序描述语言相似和第二、三步不同方法3：第零步：将最大值置为零；第一步：如果当前数大于最大值，那么将最大值置为当前数，否则保留原最大值；第二步：重复第一步直至所有数全比较完。二、算法的三种基本结构任何算法（或程序）都由三种基本结构组成：顺序结构判断（选择）结构循环结构任何算法都是上述三种结构的组合。1.顺序结构S1S22.选择结构60N条件S1S2Y

双选择结构N条件S1Y单选择结构3.循环结构61

条件A块NY直到型循环结构条件A块YN

当型循环结构三种基本结构的特点：一个入口

一个出口不出现死循环和死语句6263T+ITI≤10YN1I，0K,0TK>10YNT+KT64T+ITI≤10YN1I，0K,0TK>10YNT+KT死循环死语句65用顺序结构描述将华氏温度F转换成摄氏温度C的流程。算法：C=5/9*（F-32）4.顺序结构设计顺序结构中，按语句的自然顺序依次执行。开始5/9bb*(F-32)C输出F，C结束输入F66已知三角形的3条边边长，求三角形面积。用顺序结构描述求三角形面积的流程。开始(a+b+c)/2ss*(s-a)*(s-b)*(s-c)t输出area结束输入a,b,c用顺序结构描述两个值（a=1,b=2）交换的流程

12bca1开始1a，2babba

输出a，b结束acbacb2112ab21选择结构（分支结构），根据选择结构中判断的结果，选择执行相应的语句。5.选择结构及其程序设计开始输出MAX结束输入R,HRMAXHMAXR≥HYN例用选择结构描述求两个数中的最大值的流程例用选择结构描述检查某年是否闰年的流程。X年为闰年满足下列条件之一：1.N能被400整除2.N能被4整除，但不能被100整除开始输出XYES结束输入XX被400整除YNX被4整除YNX被100整除YN输出XNO用选择结构描述检查某成绩级别的流程。成绩N的级别：A级--X≥90B级—90>X≥80C级—80>X≥60D级—X<60开始输出X-A结束输入XX≥90YNX≥80YNYNX≥60输出X-B输出X-C输出X-D循环结构：当循环控制条件为真时反复执行循环体中的语句，直到循环控制条件为假时为止。开始输出T的值结束输入KT+KTI+1II≤10YN1I，0T累加器计数器用循环结构描述求10个学生成绩之和的流程用T累计10个学生的成绩（K），用I记录累加的次数（I=1,2,…,10）6.循环结构及其程序设计例用循环结构描述求10到100之间所有不能被3整除的整数的流程开始结束I+1II≤100YN10II不能被3整除输出IYN对10到100之间所有数逐一验证，凡满足“不能被3整除”的整数即可输出。

循环嵌套结构：

一个循环结构的循环体中又出现另一个循环结构。外循环

内循环

J+1JI≤3YN1I输出IJ≤21J输出JI+1IYNI=1，输出1

J=1，输出1J=2，输出2I=2，输出2

J=1，输出1J=2，输出2I=3，输出3

J=1，输出1J=2，输出274

例

打印边长为m的正方型 要求：从键盘输入m值，输出m行每行m个*号。 例：输入m=4，输出的图形如下：****************算法：

1.输入m 2.重复打印

m行，每行打印

m个*开始结束输入MI+1II≤MYN1I

对行循环(I=1,2,…，M)

对I行的各列循环(J=1,2,…，M)输出*J+1JJ≤MYN1J换行输出I行的M个*I=1，J=1输出**

J=2输出***

J=3输出****

J=4输出*****换行I=2J=1，2，3，4********……I=4J=1，2，3，4************

****77例从键盘输入n值，输出n行用*号组成等腰三角形。例：输入n=4，输出的图形如下：****************

*k=1,n-1=3个空，2*1-1=1个*  ***k=2,n-2=2个空，2*2-1=3个* *****k=3,n-3=1个空，2*3-1=5个********k=4,n-4=0个空，2*4-1=7个*共n行，其中第K行由n-k个空格和2k-1个*组成

分析：

1、输出n

行。

2、图形的第k

行(1<=k<=n)由n-k个空格和2k-1个*组成。算法设计：1.输入n;2.重复输出n行。对于第

k

行，每行输出n-k

个空格和2k-1个*

开始结束输入nk+1kk≤nYN1k

对行循环(k=1,2,…，n)输出空J+1JJ≤n-kYN1J输出*J+1JJ≤2k-1YN1J换行

对每个k行各列循环，输出n-k个空格和2k-1个*三、

算法的表示

自然语言

流程图伪代码

结构图

N-S结构图

PAD结构图计算机语言√√√√

用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。流程图包括：

表示相应操作的框；带箭头的流程线；

框内外必要的文字说明。1.流程图（1）图形符号起止框判断框处理框输入/输出框注释框流向线连接点例：求给定半径R的圆面积和圆周长。算法：圆面积

S=π*R2圆周长

L=2*π*R开始输出S、L的值结束输入半径Rπ*R*RS2*π*R

L顺序（2）用流程图表示算法例：求给定数R的绝对值。算法：|R|=RR≥0

-RR<0开始输出S的值结束输入RRS-R

SR≥0YN选择求S=1+2+3+......+1000s;s+1ss+2s......s+100s0ss+is(循环体)(i=1,2,...,100)例:给定K值，求T=1+2+3+…+K。K=5，T=0I=1：T=0+1=1，I=1+1=2I=2：T=1+2=3，I=2+1=3I=3：T=3+3=6，I=3+1=4I=4：T=6+4=10，I=4+1=5I=5：T=10+5=15，I=5+1=60

TT+I

T(I=1,2,3,…K)开始输出T的值结束输入KT+ITI+1II≤KYN1I，0T循环

由于流程线的任意转向性，传统流程图无法保证自顶向下的程序设计，使模块之间的调用关系难以表达。故两位美国学者Nassi和Shneiderman于1973年提出了无流程线的N-S流程图。2.N–S流程图S1S2流程图S1S2N-S流程图（1）图形符号YNS1S2条件流程图条件YNS1S2N-S流程图YN循环体条件流程图循环体循环条件N-S流程图流程图NY循环体条件循环体循环条件N–S流程图（2）用N-S流程图表示算法输入半径R输出S、L的值π*R*RS2*π*R

L例：求给定半径R的圆面积和圆周长开始输出S、L的值结束输入半径Rπ*R*RS2*π*R

L顺序开始输出S的值结束输入RRS-R

SR≥0YN选择输入R输出S的值RS-RSYR≥0N例：求给定数R的绝对值例:

给定K值，求T=1+2+3+…+K开始输出T的值结束输入KT+ITI+1II≤KYN1I，0T循环输入K输出T的值I≤K

1I，0TT+ITI+1I伪代码是算法的一种类似英语的表示法。它是部分英语和部分结构化代码的组合。英文代码部分采用不严格的语法，很容易看懂；代码部分包含基本算法结构（顺序、选择和循环）的扩展形式。目前还没有伪代码的标准。3.伪代码伪代码描述算法的一般组成：算法头：算法的名字。目的、条件和返回值：

目的：有关算法要做什么的简短说明

前置条件：列出算法所有前驱条件

后置条件：指出算法产生的影响

返回值：算法返回的结果或无返回值语句序号：表示语句之间的附属关系。例：用伪代码描述在一数列中找最小值的算法Algorithm（算法）：FindingSmallestPurpose（目的）：在一数列中找最小值Pre（前置条件）：Listofnumbers（数列）Post（后置条件）：NoneReturn（返回值）：Thesmallest32416a:S3

21算法：设数列中第一个数为最小值S，然后用后续数依次与S比较，若比S小，则用该数替换原S的值，全部比较完成后S即最小值。1.Setsmallesttothefirstnumber2.Loop(notendoflist)

2.1if(nextnumber<smallest)

2.1.1setsmallesttonextnumber

2.2endif3.endloop4.returnsmallestEndFindingSmallest数列ai(i=1,5)a1S,2ii≤5Yai<SNaiSi+1i返回最小值S1.数列ai(i=1,5)2.

a1S,2i3.while(i≤5)

3.1if(ai<S)thenaiS

endif3.2i+1i

endwhile4.

returnS伪代码不一定按上述严格的格式，且可以使用汉字，只要把算法表达清楚即可。数列ai(i=1,5)a1S,2ii≤5Yai<SNaiSi+1i返回最小值Ss=a[1];i=2;while(i<=5)

{if(a[i]<s)s=a[i];i=i+1;}returns;数列ai(i=1,5)a1S,2ii≤5Yai<SNaiSi+1i返回最小值S4.计算机语言计数累加值交换求最大（小）值四、基本算法穷举迭代递推递归1.穷举法基本思想首先根据问题的部分条件预估计出答案的范围在预估计的答案范围内，对所有可能的情况逐一验证。若某个情况使验证符合题目的全部条件，则该情况是本题目的一个答案。分析：假设a,b分别代表父亲和儿子的年龄，x年后a=2b。根据人的寿命，x取值为：1,2,…,150