数据结构1绪论课件

数据结构

付细楚

2011年2月1数据结构付细楚1联系方式电子邮件：xichuf@163.com欢迎同学们共同交流和探讨。2联系方式电子邮件：xichuf@163.com2课程的性质综合性的专业基础课程软件专业课程体系中的核心课程先修课:C++程序设计语言,离散数学后续课:几乎所有的软件方面课程,如:操作系统,编译原理,算法分析与设计,应用系统开发等.

3课程的性质综合性的专业基础课程3课程安排教学安排:

教学总学时数56学时（其中讲授:40课时,实验16课时）数据结构与算法课程设计（2周）10软件4、5、6、7、8班

4课程安排教学安排:4研究对象主要是研究：非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作

5研究对象主要是研究：5学习目的了解计算机处理对象的特性，将现实世界中实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练提高计算机思维的能力，通过程序设计的技能训练来促进综合应用能力和专业素质的提高。6学习目的了解计算机处理对象的特性，将现实世界中实际问题中所涉教材[1]严蔚敏等.数据结构（C语言版）,北京：清华大学出版社，1997年[2]李根强数据结构习题解答及实训指导北京：中国水利出版社，2009年7教材[1]严蔚敏等.数据结构（C语言版）,7参考资料[1]殷人昆等.数据结构（用面向对象方法与C++描）,北京：清华大学出版社，1999年[2]BrunoR.Preiss，数据结构与算法——面向对象的C++设计模式，北京：电子工业出版社，2003年[3]李春葆．数据结构习题与解析（C语言版第二版）．北京：清华大学出版社，2004年[4]陈元春等编，用数据结构基础，中国铁道出版社2003年8参考资料[1]殷人昆等.数据结构（用面向对象方法与C+第一章绪论介绍数据结构的基本概念1.什么是数据结构2.数据结构基本概念3.抽象数据类型表示与实现4.算法及算法分析9第一章绪论介绍数据结构的基本概念91.1什么是数据结构信息管理、人工智能、文字处理加工对象：数值字符、表格、图像或其他具有一定结构的数据应用领域：科学计算101.1什么是数据结构信息管理、人工智能、加工对象：字符、计算机解决问题的步骤用计算机解决具体实际问题时,一般过程如下:从具体问题抽象出适当的数据模型,设计求解数据模型的算法编写程序,运行并调试程序,直到解决实际问题.

举例:求水仙花数问题.寻求数据模型实质是:分析问题,从中提取操作的对象,并找出这些操作对象之间的关系,然后用数学语言加以描述.11计算机解决问题的步骤用计算机解决具体实际问题时,一般过程如下例1.1图书信息检索登录号,书名,作者,出版社,出版日期等构成一张表.

每本书一个登录号.要求按书名,作者,分类号等进行查找,

建立分别按书名,作者名,分类号的顺序排列的索引表.书目表,书名,作者名,分类号索引表构成数学模型.12例1.1图书信息检索登录号,书名,作者,出版社,出版图书信息表

000001高等数学樊映川S01。。。000002理论力学罗远祥

L01。。。000003高等数学华罗庚

S01。。。000004线性代数阳正宏

S02。。。。。。。。。。。。。。。。。。。13图书信息表000001高等数学樊映川S01。。。000例1.2八皇后问题N皇后问题是要求一个N×N的棋盘上放置N个皇后,每个皇后不能相遇按国际象棋的规则,皇后可以横吃,竖吃,斜吃.以简化的四皇后问题为例,说明八皇后问题.四皇后问题最后结果如附图.●

●●●四皇后最后的结果14例1.2八皇后问题N皇后问题●●●●四皇后最后的结四皇后问题情形一

●

●

●

●●

●●15四皇后问题情形一●●●●●●●15例1.3交通灯管理问题交通管理问题（P3图1.3）设计一个交通信号灯:

使车辆通行时互相之间不能碰撞.问题转化为:对图上的每一个顶点染一种颜色,要求有连线的顶点颜色不能相同.16例1.3交通灯管理问题交通管理问题（P3图1.3）1例1.4交通咨询问题城市公交线路图，求解出行路径。17例1.4交通咨询问题城市公交线路图，求解出行路径。171.2数据结构的基本概念数据（Data）信息的载体，它能够被计算机识别、存储和加工处理。例如：

数值计算中的整数和实数，编译程序或文本编辑程序中的字符串。多媒体技术中所涉及的视频和音频信号，经采集转换后都能形成被计算机所接受的数据。181.2数据结构的基本概念数据（Data）18第一讲19第一讲19基本术语数据元素（DataElement）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录。数据元素类（DataElementClass）是具有相同性质的数据元素的集合。例如：整数数据对象N＝｛0，1-1,2,-2……｝字母数据对象C＝｛’a’,’b’,’c’……｝20基本术语数据元素（DataElement）20数据结构的概念数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。

四类基本的结构：（图1.5）（1）集合数据元素间的关系是’属于同一个集合’。（2）线性结构数据元素之间存在一对一的关系。（3）树形结构数据元素之间存在一对多的关系。（4）图状结构

数据元素之间存在多对多的关系，图状结构也称网状结构。21数据结构的概念数据结构（DataStructure）是指互数据的逻辑结构数据的逻辑结构可以看作是从具体问题中抽象出来的数学模型，它与数据的存储无关

逻辑结构线性：线性表、栈、队列、数组、串

非线性：广义表、树、图22数据的逻辑结构数据的逻辑结构可以看作是从具体问题中抽象出来的数据结构定义举例DataStructure=(D,R)其中，D是数据元素的有限集，R是D上关系的有限集例如:按员工的编号来建立元素间的线性关系Linear-List=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<02,03>,…………<09,10>}23数据结构定义举例DataStructure=(D,R)23按行政分组来建立树形的数据结构Tree=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<02,07>,<03,08>,<03,09>,<04,10>}按员工的爱好来建立图状的数据结构

Graph=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10,网，羽，乒}R＝{<01,羽>,<01,乒>,<05,网>,<05,乒>,<06,网>}24按行政分组来建立树形的数据结构24数据的物理结构数据结构在计算机中的表示（又称映象）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。

物理结构顺序使用一组连续的存储单元非顺序链式索引存储、散列存储

25数据的物理结构数据结构在计算机中的表示（又称映象）称为数据的1.3抽象数据类型表示与实现

数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称。例如：整数类型，其取值的范围为[-maxint,maxint]上的整数定义在其上的一组操作为加、减、乘、除及取模等。261.3抽象数据类型表示与实现数据类型（DataTyp抽象数据类型抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。27抽象数据类型抽象数据类型（AbstractDataTyp抽象数据类型的定义抽象数据类型的定义可以由（元素、关系、操作）三种要素来进行定义（由于数据类型＝数据结构＋操作，而数据结构＝数据元素＋元素间的关系）例如栈的ADT定义：元素属于同一个数据元素类。关系数据元素间呈线性关系。操作PUSH（S，X）进栈操作、POP（S）出栈操作等等

28抽象数据类型的定义抽象数据类型的定义可以由28实现方法的比较

面向过程的方法在数据与操作二者之间并没有建立必然的联系顺序执行面向对象的方法相关的数据及操作被统一在一个整体──对象之中程序简洁有利于数据保护和代码重用29实现方法的比较面向过程的方法29栈演示程序

面向过程的方法Node*top;charch;voidpush(charch);……charpop();……top=NULL;ch=’a’;while(ch!=‘E’){

输入一个字符存入ch;

对ch进行判别并进行相应的处理；输出栈中的当前元素};

面向对象的方法classLinkStack

{private:Node*top;public:

LinkStack();voidinit();voidprnt();charpop();voidpush(charel);};

……LinkStacklz1;

lz1.init();lz1.push(el);lz1.prnt();

30栈演示程序面向过程的方法面向对象的方法301.4算法及其分析

算法的概念：

算法是对特定问题求解步骤的一种描述

算法的特性：

有穷性、确定性、可行性、输入、输出算法的描述自然语言。使用流程图、N－S图等用于算法描述的工具，直接用某种高级程序设计语言来描述算法。使用伪码语言算法设计的要求

正确、可读、

健壮、

高效

311.4算法及其分析31时间的复杂性分析

表示形式：一个算法是由控制结构和原操作构成的。从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间量度。一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：T(n)=o(f(n))该式表示算法中原操作的执行次数与问题规模n的某个函数同阶。

32时间的复杂性分析32常数阶、线性阶、平方阶

o(1)o(n)o(n2)

x=x+1;for(i=1;i<=n;i++)x=x+1;for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//nfor(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//n2};

33常数阶、线性阶、平方阶

o(1)o(n)o例1.4n阶矩阵相乘算法的时间复杂度

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//基本语句(1)

for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//基语句(2)};

在通常情况下算法的时间复杂度是指基本语句重复执行的次数及频度。在上述算法中主要语句的频度分别是：基本语句(1)n2，基本语句(2)n3。该算法的时间复杂度所有语句的频度之和T(n)=n2+n3=

o(n3)。因此该算法时间复杂度为o(n3),称之为立方阶。34例1.4n阶矩阵相乘算法的时间复杂度34例1.5对数阶时间复杂度

i=1;//语句(1)while(i<=n)i=i*2;//语句(2)其中语句(1)的频度是1，设语句(2)的频度是f(n)，则有2

f(n)<=n，即：f(n)<=log2n，取最大值f(n)=log2n，因此该算法时间复杂度为:T(n)=1+log2n=o(log2n)35例1.5对数阶时间复杂度35空间的复杂性分析

类似于时间复杂性分析,空间的复杂性也可以表示为问题规模的函数.

表示形式：S(n)=o(f(n))36空间的复杂性分析36例1.6空间的复杂性举例

实例：将存放在一维数组a中的n个整数反向存放，即将a[1]存放在原a[n]存放的位置中，将a[2]存放在原a[n－1]存放的位置中，依次类推，直至将a[n]存放在原a[1]存放的位置中。

1.使用一组工作单元b[n]：for(i=1;i<=n;i++)b[n-i+1]=a[i];for(i=1;i<=n;i++)a[i]=b[i];

2.只使用工作单元i与w：for(i=1;i<=n/2;i++){w=a[i];a[i]=a[n-i+1];a[n-i+1]=w;};37例1.6空间的复杂性举例37教学互动：算法及其算法分析试写一个算法，实现将数组a[n]中的n个整数循环后移一个位置，并给出它的时间复杂度和辅助空间的大小。

38教学互动：算法及其算法分析38教学互动：算法及其算法分析inti,temp;temp=a[n-1];for(i=n-1;i>=1;i--)a[i]=a[i-1];a[0]=temp;时间复杂度T(n)=1+(n-1)+1=o(n)线性阶空间复杂度S(n)=2=o(1)常数阶39教学互动：算法及其算法分析39作业第一章习题

1,5,7,81、给出以下算法的时间复杂度1）voidfunA(intn){Inti=1,k=100;While(i<n){k=k+5;i+=2;}}2）voidfunB(intn){Inti,j,k,x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++);x=x+1;}40作业第一章习题40作业2、简述下列术语的喊含义？数据、数据元素、数据对象、存贮结构、数据类型和抽象数据类型。3、数据结构在计算机内存中的表示是指什么？41作业2、简述下列术语的喊含义？41数据结构

付细楚

2011年2月42数据结构付细楚1联系方式电子邮件：xichuf@163.com欢迎同学们共同交流和探讨。43联系方式电子邮件：xichuf@163.com2课程的性质综合性的专业基础课程软件专业课程体系中的核心课程先修课:C++程序设计语言,离散数学后续课:几乎所有的软件方面课程,如:操作系统,编译原理,算法分析与设计,应用系统开发等.

44课程的性质综合性的专业基础课程3课程安排教学安排:

教学总学时数56学时（其中讲授:40课时,实验16课时）数据结构与算法课程设计（2周）10软件4、5、6、7、8班

45课程安排教学安排:4研究对象主要是研究：非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作

46研究对象主要是研究：5学习目的了解计算机处理对象的特性，将现实世界中实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练提高计算机思维的能力，通过程序设计的技能训练来促进综合应用能力和专业素质的提高。47学习目的了解计算机处理对象的特性，将现实世界中实际问题中所涉教材[1]严蔚敏等.数据结构（C语言版）,北京：清华大学出版社，1997年[2]李根强数据结构习题解答及实训指导北京：中国水利出版社，2009年48教材[1]严蔚敏等.数据结构（C语言版）,7参考资料[1]殷人昆等.数据结构（用面向对象方法与C++描）,北京：清华大学出版社，1999年[2]BrunoR.Preiss，数据结构与算法——面向对象的C++设计模式，北京：电子工业出版社，2003年[3]李春葆．数据结构习题与解析（C语言版第二版）．北京：清华大学出版社，2004年[4]陈元春等编，用数据结构基础，中国铁道出版社2003年49参考资料[1]殷人昆等.数据结构（用面向对象方法与C+第一章绪论介绍数据结构的基本概念1.什么是数据结构2.数据结构基本概念3.抽象数据类型表示与实现4.算法及算法分析50第一章绪论介绍数据结构的基本概念91.1什么是数据结构信息管理、人工智能、文字处理加工对象：数值字符、表格、图像或其他具有一定结构的数据应用领域：科学计算511.1什么是数据结构信息管理、人工智能、加工对象：字符、计算机解决问题的步骤用计算机解决具体实际问题时,一般过程如下:从具体问题抽象出适当的数据模型,设计求解数据模型的算法编写程序,运行并调试程序,直到解决实际问题.

举例:求水仙花数问题.寻求数据模型实质是:分析问题,从中提取操作的对象,并找出这些操作对象之间的关系,然后用数学语言加以描述.52计算机解决问题的步骤用计算机解决具体实际问题时,一般过程如下例1.1图书信息检索登录号,书名,作者,出版社,出版日期等构成一张表.

每本书一个登录号.要求按书名,作者,分类号等进行查找,

建立分别按书名,作者名,分类号的顺序排列的索引表.书目表,书名,作者名,分类号索引表构成数学模型.53例1.1图书信息检索登录号,书名,作者,出版社,出版图书信息表

000001高等数学樊映川S01。。。000002理论力学罗远祥

L01。。。000003高等数学华罗庚

S01。。。000004线性代数阳正宏

S02。。。。。。。。。。。。。。。。。。。54图书信息表000001高等数学樊映川S01。。。000例1.2八皇后问题N皇后问题是要求一个N×N的棋盘上放置N个皇后,每个皇后不能相遇按国际象棋的规则,皇后可以横吃,竖吃,斜吃.以简化的四皇后问题为例,说明八皇后问题.四皇后问题最后结果如附图.●

●●●四皇后最后的结果55例1.2八皇后问题N皇后问题●●●●四皇后最后的结四皇后问题情形一

●

●

●

●●

●●56四皇后问题情形一●●●●●●●15例1.3交通灯管理问题交通管理问题（P3图1.3）设计一个交通信号灯:

使车辆通行时互相之间不能碰撞.问题转化为:对图上的每一个顶点染一种颜色,要求有连线的顶点颜色不能相同.57例1.3交通灯管理问题交通管理问题（P3图1.3）1例1.4交通咨询问题城市公交线路图，求解出行路径。58例1.4交通咨询问题城市公交线路图，求解出行路径。171.2数据结构的基本概念数据（Data）信息的载体，它能够被计算机识别、存储和加工处理。例如：

数值计算中的整数和实数，编译程序或文本编辑程序中的字符串。多媒体技术中所涉及的视频和音频信号，经采集转换后都能形成被计算机所接受的数据。591.2数据结构的基本概念数据（Data）18第一讲60第一讲19基本术语数据元素（DataElement）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录。数据元素类（DataElementClass）是具有相同性质的数据元素的集合。例如：整数数据对象N＝｛0，1-1,2,-2……｝字母数据对象C＝｛’a’,’b’,’c’……｝61基本术语数据元素（DataElement）20数据结构的概念数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。

四类基本的结构：（图1.5）（1）集合数据元素间的关系是’属于同一个集合’。（2）线性结构数据元素之间存在一对一的关系。（3）树形结构数据元素之间存在一对多的关系。（4）图状结构

数据元素之间存在多对多的关系，图状结构也称网状结构。62数据结构的概念数据结构（DataStructure）是指互数据的逻辑结构数据的逻辑结构可以看作是从具体问题中抽象出来的数学模型，它与数据的存储无关

逻辑结构线性：线性表、栈、队列、数组、串

非线性：广义表、树、图63数据的逻辑结构数据的逻辑结构可以看作是从具体问题中抽象出来的数据结构定义举例DataStructure=(D,R)其中，D是数据元素的有限集，R是D上关系的有限集例如:按员工的编号来建立元素间的线性关系Linear-List=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<02,03>,…………<09,10>}64数据结构定义举例DataStructure=(D,R)23按行政分组来建立树形的数据结构Tree=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10}R＝{<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<02,07>,<03,08>,<03,09>,<04,10>}按员工的爱好来建立图状的数据结构

Graph=(D,R)其中：D={01,02,03,04,05,06,07,08,09,10,网，羽，乒}R＝{<01,羽>,<01,乒>,<05,网>,<05,乒>,<06,网>}65按行政分组来建立树形的数据结构24数据的物理结构数据结构在计算机中的表示（又称映象）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。

物理结构顺序使用一组连续的存储单元非顺序链式索引存储、散列存储

66数据的物理结构数据结构在计算机中的表示（又称映象）称为数据的1.3抽象数据类型表示与实现

数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称。例如：整数类型，其取值的范围为[-maxint,maxint]上的整数定义在其上的一组操作为加、减、乘、除及取模等。671.3抽象数据类型表示与实现数据类型（DataTyp抽象数据类型抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。68抽象数据类型抽象数据类型（AbstractDataTyp抽象数据类型的定义抽象数据类型的定义可以由（元素、关系、操作）三种要素来进行定义（由于数据类型＝数据结构＋操作，而数据结构＝数据元素＋元素间的关系）例如栈的ADT定义：元素属于同一个数据元素类。关系数据元素间呈线性关系。操作PUSH（S，X）进栈操作、POP（S）出栈操作等等

69抽象数据类型的定义抽象数据类型的定义可以由28实现方法的比较

面向过程的方法在数据与操作二者之间并没有建立必然的联系顺序执行面向对象的方法相关的数据及操作被统一在一个整体──对象之中程序简洁有利于数据保护和代码重用70实现方法的比较面向过程的方法29栈演示程序

面向过程的方法Node*top;charch;voidpush(charch);……charpop();……top=NULL;ch=’a’;while(ch!=‘E’){

输入一个字符存入ch;

对ch进行判别并进行相应的处理；输出栈中的当前元素};

面向对象的方法classLinkStack

{private:Node*top;public:

LinkStack();voidinit();voidprnt();charpop();voidpush(charel);};

……LinkStacklz1;

lz1.init();lz1.push(el);lz1.prnt();

71栈演示程序面向过程的方法面向对象的方法301.4算法及其分析

算法的概念：

算法是对特定问题求解步骤的一种描述

算法的特性：

有穷性、确定性、可行性、输入、输出算法的描述自然语言。使用流程图、N－S图等用于算法描述的工具，直接用某种高级程序设计语言来描述算法。使用伪码语言算法设计的要求

正确、可读、

健壮、

高效

721.4算法及其分析31时间的复杂性分析

表示形式：一个算法是由控制结构和原操作构成的。从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间量度。一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：T(n)=o(f(n))该式表示算法中原操作的执行次数与问题规模n的某个函数同阶。

73时间的复杂性分析32常数阶、线性阶、平方阶

o(1)o(n)o(n2)

x=x+1;for(i=1;i<=n;i++)x=x+1;for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//nfor(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//n2};

74常数阶、线性阶、平方阶

o(1)o(n)o例1.4n阶矩阵相乘算法的时间复杂度

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;//基本语句(1)

for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];//基语句(2)};

在通常情况下算法的时间复杂度是指基本语句重复执行的次数及频度。在上述算法中主要语句的频度分别是：基本语句(1)n2，基本语句(2)n3。该算法的时间复杂度所有语句的频度之和T(n)=n2