数据结构(C语言版)-绪论-课件

数据结构(C语言版)1PPT课件约法三章1.上课不允许说话，玩手机。2.诚实对待作业和考试。3.对自己负责。2PPT课件C语言数据结构软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比学业基础3PPT课件前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程承上启下学业基础4PPT课件总学时：75学时，讲课学时：45实验学时：30总成绩：期末考试×0.7＋平时成绩×0.3平时成绩：上课表现＋出勤率＋课外作业＋实验报告教学安排5PPT课件教学内容

第一章绪论(4学时)第二章线性表(8学时)第三章栈和队列(6学时)第四章串、数组和广义表

(5学时)第五章树和二叉树(8学时)第六章图(6学时)第七章查找(4学时)第八章排序(4学时)6PPT课件掌握各类基本数据结构类型和相应的存储结构要求学生掌握典型算法思想及程序实现；能针对给定问题，选择相适应的数据结构，并能设计和分析算法，提高复杂程序设计的能力。提高阅读算法的能力为后继课的学习及从事软件开发打好基础。

课程学习基本要求7PPT课件1.1什么是数据结构1.2基本概念和术语1.3

抽象数据类型1.4

算法及算法分析（算法评价）第一章绪论8PPT课件

数据结构是研究什么的？这是课程最基本的问题，关系到我们为什么要学习数据结构这门课程1.1什么是数据结构9PPT课件例1已知：游泳池的长length和宽wide，求面积area。分析：1.1什么是数据结构（1）问题涉及的对象：length,wide,area

是实数——可用数值表示；（2）对象之间的关系：area=lengthwide——可用方程或函数表示；（3）数据存储：可用程序设计语言中的实型变量存储；（4）问题求解：用某种计算方法求解；10PPT课件程序：

main(){

int

len,wide,area;

scanf(“%d%d%\n”,&len,&wide);

area=len*wide;

printf(“area=%d”,area);

}

可见，对于数值问题，对象之间的关系通常可以用方程或函数表达，只要能列出表达对象之间关系的方程或函数，找到求解方程或函数的方法，就可以编写程序了。数值问题就是我们平时所说的计算问题。11PPT课件举例2--电话号码查询系统

设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码;如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的反馈信息12PPT课件举例3--学籍档案管理假设一个学籍档案管理系统包含如下表1-1所示的学生信息13PPT课件表1-1特点?14PPT课件

132213231321312123412431324134214231432等举例4——输出n个对象的全排列15PPT课件解决图1-13个对象的全排列过程16PPT课件(a1)(a2)(a3)(a4)(a5)(a)计算机和人对奕问题l 在求解过程中，所处理的数据之间具有层次关系，这是树形结构l 对它的操作有：建立树形结构，输出最低层结点内容等等17PPT课件在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：举例5——制定教学计划18PPT课件表1-219PPT课件课程先后关系的图形描述形式c1c9c4c2c12c10c11c5c3c6c7c8图1-2计算机专业必修课程开设先后关系20PPT课件特点课程之间的先后关系用图结构描述通过实施创建图结构，按要求将图结构中的顶点进行线性排序非数值问题就是问题中涉及的模型不能用数学方程来表达的那些问题21PPT课件

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科。

1.1什么是数据结构22PPT课件23

《数据结构》研究什么问题数学模型实现机外表示即外表示存储结构实现逻辑结构基本运算处理要求机外表示建模求精1.1什么是数据结构23PPT课件

《DS》主要研究内容：数据的各种逻辑结构和物理结构，以及它们之间的相应关系并对每种结构定义相适应的各种运算设计出相应的算法分析算法的效率常见的数据结构有：数组、栈、队列、表、串、树、图和文件等1.1什么是数据结构24PPT课件1.2基本概念和术语1、数据(Data):

是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。如图象、声音等都可以通过编码而归之于数据的范畴。2、数据元素(DataElement):

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3、数据项一个数据元素可由若干个数据项(Dataltem)组成，数据项是数据的不可分割的最小单位。25PPT课件表1-1个人书库26PPT课件数据对象结构数据结构[数据对象DataObject]具有相同特性的数据元素的一个集合,是数据的子集.例:整数数据对象是集合{0,1,-1,2,-2,…}扑克牌上的点数的数据对象是{2,3,4,5…J,Q,K,A}字母的数据对象是集合{A,B,C……X,Y,Z}1.2基本概念和术语27PPT课件

数据对象可以是有限的,也可以是无限的,其中的数据不是孤立的,而是彼此相关联的,这种数据元素相互之间的关系称为结构.[数据结构DataStructure]相互之间存在一种或多种特定关系的数据元素的集合,即带结构的数据元素的集合.1.2基本概念和术语数据逻辑结构数据存储结构运算28PPT课件数据元素之间的逻辑关系分为（数据逻辑结构）1)元素之间没有关系----集合2)元素之间有线性关系---线性数据结构(线性表结构)3)元素之间有层次关系---层次数据结构(树结构)4)元素之间有网状关系---网状数据结构(图结构)1.2基本概念和术语29PPT课件例1：某班学生基本情况登记表，记录了每个学生的学号姓名专业政治面貌，表中的记录是按学生的学号顺序排列的.

学号姓名 专业 政治面藐

001 王洪 计算机党员

002孙文计算机团员

003 谢军 计算机团员 004 李辉 计算机团员 005沈祥福计算机党员 006余斌计算机团员

007 巩力 计算机团员 008 孔令辉计算机团员学生基本情况登记表的图示

001003002004006005008007学号关系是一种线性结构关系1.2基本概念和术语30PPT课件例2家族的族谱

家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。这种分支结构关系被称为树结构。本例中树称为家族树，它很象一棵倒置的树，A是树的根。JIACBDHGFE家族树的图示表示1.2基本概念和术语31PPT课件例3教学计划编排问题32PPT课件学生基本情况表的二元组表示（D，S）二元组表示二元组表示是用一个二元组（D，S）表示数据结构，其中D是数据元素集合，S是D上关系的集合。D={001，002，003，004，005，006，007，008}S={R}R={<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}1.2基本概念和术语33PPT课件家族的族谱

家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE家族树的图示表示1.2基本概念和术语

D={}

S={R}

R=

{}34PPT课件请问此结构是什么结构？

D={A，B，C，D，E，F，G，H，I，J}

S={R}

R={〈A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}1.2基本概念和术语35PPT课件[数据的存储结构]数据结构在计算机中的表示(映象),即数据结构在计算机中的组织形式.又称为数据的物理结构.1.2基本概念和术语数据元素在计算机中的映射----结点数据项在计算机中的映射----数据域36PPT课件1.2基本概念和术语数据在计算机中的存储:只有两种形式顺序:数据元素逐个连续存放(通过物理相邻来确定关系)非顺序:数据元素任意存放(通过存储地址确定关系)数据结构的存储要把数据元素存放起来还必须把数据元素之间的逻辑关系也表示出来37PPT课件存储结构（StorgeStructure):

数据结构在计算机中的表示(或称映象)称为数据的存储结构，又称为物理结构。四种基本的存储方法：（1）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。38PPT课件顺序存储结构:

用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。链式存储结构：

在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。39PPT课件例：复数3.0－2.3i的两种存储方式：－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节40PPT课件逻辑结构、存贮结构、运算这三个方面的关系为：

（1）逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示；数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的存储结构。41PPT课件[数据类型DataType]一个值的集合和定义在这个值集上的一组操作的总称.例如：在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义1.2基本概念和术语42PPT课件§1.3抽象数据类型一.抽象数据类型定义是指一个数学模型以及定义在该模型上的一组操作，面向逻辑层次。抽象数据类型=数学模型+操作=数据结构+操作一个抽象数据类型的描述如下:ADT抽象数据类型的名称{数据对象数据关系基本操作}ADT抽象数据类型名43PPT课件例1-8：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）

S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：

bcaefd此结构为线性的。44PPT课件（2）

S=(D,R)

D={di|1≤i≤5}

R={<di,dj>,i<j}

d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：45PPT课件数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构46PPT课件一算法的概念

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一种或多种操作。例求10个正整数中的最大数max的算法。

描述算法的方法有很多流程图，自然语言，计算机语言用计算机语言表达的算法就是程序§1.4

算法与算法分析47PPT课件

二算法的基本特征1）输入：0个或多个输入

2）输出：1个或多个输出

3）有穷性：算法必须在有限步内结束

4）确定性：组成算法的操作必须清晰无二义性

5）可行性：组成算法的操作必须能够在计算机上实现§1.4算法与算法分析48PPT课件３．算法与程序的区别算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。主要区别在：有穷性、正确性和描述方法程序可以是无穷的，例如OS，算法是有穷的；程序可以是错误的，算法必须是正确的；程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。1.4算法和算法分析

49PPT课件二、算法的描述和实现描述---可采用自然语言、数学语言或约定的符号语言。实现---必须借助程序设计语言提供的数据类型及其运算。本课的描述---采用C语言。1.4算法和算法分析

50PPT课件三．算法分析 衡量的四个尺度：正确性:问题的任何一个实例作为输入，算法都能得到正确的结果作为输出；时间特性:运行所花费的时间；空间特性:所占用存储空间的大小；其他（可读性、易调性、健壮性等）。

时间和空间特性的巨大改进源于更好的数据结构或算法。1.4算法和算法分析

正确性、可读性、健壮性、效率与低存储量需求51PPT课件算法效率的度量1.事后统计的方法2.事前分析估算的方法1.4算法和算法分析

52PPT课件

算法的时间特性的度量不应依赖算法运行的计算机和软件平台（操作系统、编程语言和编译系统），下面几种度量算法的时间特性的方法被废弃：算法运行的实际执行时间运行过程中所执行的指令条数运行过程中程序循环的次数算法的时间特性用执行基本操作次数来度量。1.4算法和算法分析

53PPT课件54PPT课件算法计算量或问题规模：是指算法运行中，输入的规模。例如：实数矩阵乘法中，问题规模为矩阵的阶数（n阶方阵）；

排序问题中，问题规模是待排序元素个数；1.4算法和算法分析

一个特定算法”运行工作量”的大小,只依赖于问题的规模55PPT课件算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作：

T（n）=O（f（n））随问题规模的增大，算法执行时间的增长率和操作执行次数的增长率相同。称为时间复杂度。56PPT课件O（n）O（1）T（n）=T（n）=57PPT课件判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。58PPT课件

算法时间量度T(n)[语句频度]

原操作语句重复执行的次数当有若干循环语句时,算法的时间复杂度由嵌套层数最多的语句的频度决定59PPT课件例1：程序段x:=x+1语句频度时间复杂度x:=x+1;1O(1)常数阶FORi:=1TOnDOx:=x+1;nO(n)线性阶FORi:=1TOnDOnFORj:=1TOnDOx:=x+1;n(n)O(n2)平方阶1.4算法和算法分析

60PPT课件例2分析以下程序段的时间复杂度

for(i=1;i<n;i++) {y=y+1; for(j=0;j<=(2*n);j++) x++; }/*1*//*2*/1.4算法和算法分析

61PPT课件分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：则该程序段的时间复杂度：

T(n)=1.4算法和算法分析

62PPT课件例3

分析以下程序段的时间复杂度

i=1; while(i<=n)

i=i*2语句1的频度是：1设语句2的频度是f(n)，则有：即 ，取最大值则该程序段的时间复杂度为：/*1*//*2*/63PPT课件当有若干循环语句时,算法的时间复杂度由嵌套层数最多的语句的频度决定64PPT课件常见函数的时间复杂度按数量递增排列及增长率。P16图1.7时间复杂度T(n)按数量级递增顺序为：复杂度高复杂度低65PPT课件四、设计好算法的必要性一方面计算机性能在不断提高，另一方面用计算机解决应用问题也在不断变化：应用的范围不断扩张（由字符发展为多媒体）应用问题的规模不断增加应用问题本身也越来越复杂1.4算法和算法分析

66PPT课件

五、空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n))

我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。67PPT课件数据项(字段)数据结构数据结构运算的实现数据结构是指组成数据的元素之间的结构关系。线性结构、树型结构和图结构是数据结构中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合基本概念数据数据元素逻辑结构物理结构数据中具有独立意义的个体，也称之为元素、记录、结点、顶点等将线性结构、树型结构和图结构这几类结构称为逻辑结构，因为仅考虑了元素之间的逻辑关系，而没有考虑到其在计算机中的具体实现。在选择了数据结构的存储结构之后，可实现所给出的运算(操作)数据是信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。字段是对元素的详细描述，通常情况下，元素可能包含多个字段。为所涉及的数据结构选择一种存储形式，并将其存储到计算机中，这样就得到了数据结构在内存中的物理结构（存储结构）68PPT课件本章小结1.如下一些基本概念：数据：客观事物的符号表示。在计算机学科中，数据的概念被大大的扩充了，不仅包含数学中的整数实数，任何能用计算机识别的符号都可作为数据。数据元素：数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。数据项:构成数据元素的成分,是数据不可分割的最小单位69PPT课件存储结构：数据结构在计算机中的表示(又称映象)称为数据的存储结构,又称物理结构逻辑结构：数据之间的结构关系，是具体关系的抽象。结点和结点之间的逻辑关系称为数据的逻辑结构。数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合.简单地说是带有结构和操作的数据元素本章小结70PPT课件2数据结构的研究对象：

非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。3逻辑结构有:（1）集合（2）线性结构（3）树形结构（4）图状结构或网状结构4