数据结构概述.

大外软件学院第1章数据结构概述大外软件学院数据结构课程的重要地位•考研必考：•数据结构（DataStructure）•操作系统（OperationSystem）•计算机行业中的作用•应用程序的开发•底层开发•程序=算法+数据结构大外软件学院1.1什么是数据结构•数据类型：•intfloatchar43.5‘a’•数组：inta[5]floatb[3]charc[7]a[0]1a[1]2a[2]3a[3]4a[4]5b[0]3.5b[1]4.1b[2]7.9c[0]Hc[1]ec[2]lc[3]lc[4]0c[5]\0c[6]大外软件学院1.1什么是数据结构•数据类型：•结构体：一个学生的基本信息包括学号，姓名，性别，年龄，籍贯•线性表：结构体数组•表中的每一行是一个结点，除了第一个结点和最后一个结点以外，其余的结点都有且仅有一个直接前驱结点和一个直接后续结点,称为线性结构。0101张三男19河北省0101张三男19河北省0102李四女18辽宁省0103王五男19北京市0104赵六男20江苏省大外软件学院1.1什么是数据结构•数据类型：•树：网站中经常有树形结构的结点信息大外软件学院计算机教研室日语教研室英语教研室日语学院树中除了根结点以外，其余的结点都有且仅有一个直接前驱结点和一到多个直接后续结点，称为树形结构。大外软件学院1.1什么是数据结构•数据类型：•图：旅行家旅行问题•图中每个结点都有多个直接前驱结点和多个直接后续结点，称为图形结构。•图中主要涉及到最短路径问题和最优路径问题。FABEDC大外软件学院1.2数据的逻辑结构•数据结构分为逻辑结构和存储结构•例如：•点名册上学生姓名的顺序和座位上学生的位置•计算机资源管理器和文件具体存放的位置•存储结构：数据在计算机内部，在硬盘或内存的存储方式，也称为物理结构。大外软件学院1.2.1基本概念和术语•数据：能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音和视频等一切信息都可以称为数据。•数值型数据---整数、浮点数、复数、双精度数。•非数值型数据---字符、字符串，以及文字、声音、图形、图像。•数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。•每一个学生的信息大外软件学院1.2.1基本概念和术语•数据项：是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。•学号、姓名、性别•数据对象：是性质相同的数据元素的集合，是数据的一个子集。•整数的数据对象是集合N={0,±1,±2,…}•四季的数据对象是集合S={春，夏，秋，冬}大外软件学院•在学校中，学生是数据对象，每个数据元素就是一个学生记录，每个学生记录包括：学号，姓名，性别，出生年月，家庭住址等数据项，以表明学生在某方面的属性。数据项大连市男1551987李明0001家庭住址性别出生时间姓名学号沈阳市男631986王庆0002日月年数据数据元素1.2.1基本概念和术语大外软件学院1.2.1基本概念和术语•数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。•集合：数据元素之间除了“同属于一个集合”的关系之外，别无其他关系。•线性结构：数据元素之间存在着“一对一”的关系。•树形结构：数据元素之间存在着“一对多”的关系。•图形结构：数据元素之间存在着“多对多”的关系。大外软件学院1.2.1基本概念和术语•集合•线性结构•树形结构•图形结构大外软件学院1.2.2逻辑结构的描述•二元组表示法：•G=（D,R）•G表示数据逻辑结构的名称；•D表示数据元素的有限集合；•R表示D上所有元素之间关系的有限集合。大外软件学院1.2.2逻辑结构的描述•【例1-4】一种数据结构Line=（D,R）•D={1,2,3,4,5,6,7,8},R={r},•r={3,2,2,1,1,5,5,6,6,4,4,7,7,8}•r是关系集合，尖括号表示数据元素的关系是有向的，如3,2表示从3指向2。32156478大外软件学院1.2.2逻辑结构的描述•【例1-5】一种数据结构Tree=（D,R）•D={a,b,c,d,e,f,g,h,i},R={r}，•r={a,b,a,c,a,d,b,e,b,f,b,g,c,h,c,i}abcdefghi大外软件学院1.2.2逻辑结构的描述•【例1-6】一种数据结构Graph=（D,R）•D={A,B,C,D,E,F},R={r}，•r={(A,B),(A,C),(A,D),(B,E),(B,F),(C,E),(D,F),(E,F)}•圆括号表示数据元素之间的关系是无向的，如(A,B)表示从A到B之间的边是双向的。CAFEDB大外软件学院1.2.2逻辑结构的描述•练习：下面给出几种逻辑结构，S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构（线性or非线性）。D={A，B，C，D，E，F},R={r1,r2,r3}(1)r1={〈A，B〉，〈B，C〉，〈C，D〉，〈D，E〉，〈E，F〉}(2)r2={〈A，B〉，〈B，C〉，〈B，D〉，〈D，E〉，〈D，F〉}(3)r3={〈A，B〉，〈B，C〉，〈D，A〉，〈D，B〉，〈D，E〉}大外软件学院1.2.2逻辑结构的描述ACBDEACBDEF（3）（2）（1）ACBDEFF大外软件学院1.3数据的存储结构•具有一定逻辑结构的数据元素，在计算机内部是如何存储的，称为数据的存储结构，也叫物理结构。•逻辑结构影响程序的设计，而存储结构影响程序的编码。•存储结构的分类：•顺序存储•链式存储•索引存储•散列存储大外软件学院1.顺序存储•把逻辑上相邻的结点存储在物理位置相邻的存储单元里。•使用C语言中的一维数组实现顺序存储。•插入和删除都会引起大量的结点移动。•S=(D，R)•D={a，b，c，d，e}•R={a，b，b，c，c，d，d，e}大外软件学院2.链式存储•不要求逻辑上相邻的结点在物理位置上亦相邻。•数据元素不一定存放在地址连续的存储单元。•结点间的逻辑关系由附加的指针域表示。•删除和插入操作灵活方便，不必移动结点，只改变结点中的指针值即可。大外软件学院2.链式存储•S=(D，R)•D={45，63，67，14，97}•S={97，67，67，63，63，45，45，14}大外软件学院3.索引存储•索引存储除了建立存储结点信息外，还建立附加的索引表。•索引表中的每一项都由关键字（能唯一标识一个结点的数据项）和地址组成。•索引表反映了所有结点信息按某一个关键字递增或递减排列的逻辑次序。•采取索引存储的主要作用是为了提高数据的检索速度，类似于一本图书的目录。大外软件学院3.散列存储•散列技术是一种将数据元素的存储位置与关键字之间建立确定对应关系的查找技术。散列技术除了可以用于查找外，还可以用于存储。•散列存储是通过构造散列函数来确定数据存储地址。散列存储的内存存放形式称为散列表，也称为哈希（Hash）表。大外软件学院3.散列存储•例如，要存储某地区解放后每年出生的人口数，可以用“出生年份-1948=存储地址”构造出散列函数，存放地址如表所示。这样，若要查2008年出生的人数，则只要查表中存储地址60（2008-1948）对应的存放数据（15200）即可。•某地区年出生人口散列存储表。存储地址出生年份人数存储地址出生年份人数011949100003119791700002195010100………0319511460060200815200………61200914500大外软件学院1.4算法和算法分析•算法和数据结构的关系紧密。•算法的设计取决于选定数据的逻辑结构。•算法的实现则依赖于数据所采用的存储结构。大外软件学院1.4.1算法及特性•算法：求解问题的一系列步骤的集合。•例如：已知n个整数，放在一个数组中，求此数组中n个整数中的最大数。求解步骤：•①将数组中第一个元素a[0]赋值给max;•②初始化下标变量i为1;•③当in时，执行以下语句：•ⅰ.比较a[i]与max，若a[i]大于max，则将a[i]赋值给max;•ⅱ.变量i自增1;•④输出max的值。大外软件学院1.4.1算法及特性•算法的特性•有穷性•确定性•可行性•输入•输出•算法设计的目标•正确性•可读性•健壮性•高效性•低存储量大外软件学院1.4.2算法的时间复杂度•算法的评价标准•时间复杂度：用一个算法中的基本操作所执行的次数来衡量。•空间复杂度：指一个算法执行过程中所需的存储空间。•算法复杂度=时间复杂度+空间复杂度大外软件学院1.4.2算法的时间复杂度•算法的时间复杂度•指算法运行从开始到结束所花费的时间，与计算机的软、硬件及问题规模有关。•使用执行算法的绝对时间来衡量算法的效率是不合适的。•常用算法中语句被执行的次数，即算法的规模来表示算法的时间复杂度。大外软件学院1.4.2算法的时间复杂度•例如：求解1+2+3+…+n的算法。•分析以下列算法中简单操作的执行次数：•inti,sum=0;for(i=1;i=n;i++)sum=sum+I;//次数为1+n大外软件学院1.4.2算法的时间复杂度•以上程序的时间复杂度分别为：•T(n)=O(n)•时间复杂度分析：•算法1中的时间复杂度会随着n的增加而成比例的增长，所以当n-∞时，T(n)是n数量级的。•0(Order)，即大O表示法，表示当n-∞，算法的时间复杂度与括号里的内容具有相同的数量级。大外软件学院1.4.2算法的时间复杂度•【例1-7】有以下语句，求其时间复杂度。t=a;a=b;b=t;T(n)=O(1)•【例1-8】有以下语句，求其时间复杂度。x++;for(i=1;i=n;i++)x++;for(i=1;in;i++)for(j=1;jn;j++)x++;T(n)=O(n2)大外软件学院1.4.2算法的时间复杂度•算法时间复杂度数量级越低，效率就越高。•常见的时间复杂度，按数量级递增排列为：O(1)O(lgn)O(n)O(nlgn)O(n2)O(2n)大外软件学院1.4.3算法的空间复杂度•算法或程序运行时所占用的存储空间的度量。•空间复杂度一般只统计数据部分所占用的存储空间，而不统计代码部分所占用的存储空间。