数据结构第1章绪论(第1-2讲补充结构体)

1、第第 1 1章章绪绪论论本章主题：数据结构的基本概念和术语本章主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常教学目的：了解数据结构的基本概念，理解常用术语用术语教学重点：熟悉数据结构常用术语，掌握基本教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分概念，了解算法时间复杂度和空间复杂度的分析与评价析与评价 教学难点：数据元素间的教学难点：数据元素间的 4 4 种结构关系。种结构关系。绪论绪论第第 1 1章章绪绪论论针对每一种新的应用领域的处理对象：针对每一种新的应用领域的处理对象：如何选择合适的数据表示（结构）；如何选择合适的数据表示（结构

2、）；如何有效地组织计算机存储；如何有效地组织计算机存储；在此基础上又如何有效地实现对象之间的在此基础上又如何有效地实现对象之间的“运算运算”关系；关系；数据结构就是研究和解决这些问题的重要基础数据结构就是研究和解决这些问题的重要基础理论。理论。为什么要学数据结构为什么要学数据结构第第 1 1章章绪绪论论数据结构课程的主要内容数据结构课程的主要内容数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计的程序设计问题中计算机的操作对象以及它们之间的关问题中计算机的操作对象以及它们之间的关系和操作的学科。系和操作的学科。数据结构主要包括数据结构主要包括3 3方面内容：逻辑结构、方面内容：

3、逻辑结构、存储结构（或称物理结构）、数据运算。存储结构（或称物理结构）、数据运算。数据结构在程序设计中的地位：数据结构在程序设计中的地位：程序设计程序设计 = = 算法算法 + + 数据结构数据结构第第 1 1章章绪绪论论一个含一个含1212位数的十进制数可以用三个位数的十进制数可以用三个4 4位的十进制数表示位的十进制数表示3214,6587,9345 a1(3214),a2(6587),a3(9345)3214,6587,9345 a1(3214),a2(6587),a3(9345)在在a1a1、a2a2和和a3 a3 之间存在之间存在“次序次序”关系关系 、 32143214，65876

4、587，9345 65879345 6587，32143214，93459345a1 a1 a2 a2 a3 a3 a2a2a1 a1 a3a3非数值计算的程序设计问题非数值计算的程序设计问题 例例1: 1: 求一组求一组(n(n个个) )整数中的最大值整数中的最大值算法算法: : 基本操作是基本操作是“比较两个数的大小比较两个数的大小”数据结构：？数据结构：？若整数为若整数为1212位数，在计算机中如何表示该数？位数，在计算机中如何表示该数？第第 1 1章章绪绪论论电话号码查询系统电话号码查询系统设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N N个人的名字和个人的名字和其相应的电

5、话号码。要求设计一个算法，当给定其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。则该算法也能够报告没有这个人的信息。算法的实现，依赖于计算机如何存储人的名字和对算法的实现，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的应的电话号码，或者说依赖于名字和其电话号码的结构。结构。第第 1 1章章绪绪论论数据结构在程序设计中的地位：数据结构在程序设计中的地位： 程序设计程序设计

6、 = = 算法算法 + + 数据结构数据结构数据结构是关于数据组织和处理的基本技数据结构是关于数据组织和处理的基本技术的一门学科，是程序设计的中级课程，术的一门学科，是程序设计的中级课程，主要培养我们分析数据、组织数据的能力，主要培养我们分析数据、组织数据的能力，告诉我们如何编写效率高、结构好的程序。告诉我们如何编写效率高、结构好的程序。第第 1 1章章绪绪论论1 1数据数据(Data) (Data) 数据数据(Data)(Data)：是对信息的一种符号表示。：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。机中并

7、被计算机程序处理的符号的总称。包括文字、表格、图象等。包括文字、表格、图象等。 如一个图书管理程序所要处理的数据可如一个图书管理程序所要处理的数据可能是一张表格。能是一张表格。基本概念和基本概念和常用术语常用术语第第 1 1章章绪绪论论数据元素数据元素(Data Element)(Data Element)：是数据的：是数据的基本单位基本单位，在计，在计算机程序中通常作为一个整体进行考虑和处理。算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个一个数据元素可由若干个数据项数据项组成。数据项是数组成。数据项是数据的不可分割的据的不可分割的最小单位最小单位。基本概念和基本概念和常用术

8、语常用术语数据元素是数据项的集合。例：数据元素是数据项的集合。例： 运动员信息表表头如下：运动员信息表表头如下：姓名姓名俱乐部俱乐部名称名称出生出生日期日期参 加参 加日期日期职务职务业绩业绩第第 1 1章章绪绪论论数据对象数据对象(Data Object)(Data Object)：是性质相同的数据元素的：是性质相同的数据元素的集合。是数据的一个子集。集合。是数据的一个子集。概念之间的关系：概念之间的关系：数据数据数据对象数据对象数据元素数据元素数据项数据项基本概念和基本概念和常用术语常用术语第第 1 1章章绪绪论论表表1 1 某班学生成绩管理表某班学生成绩管理表学号学号性别性别高数高数英语

9、英语 C C语言程序设计语言程序设计101101F F909085857878102102M M898976769090103103M M767643436969104104M M585892927676例：通过下表说明数据的相关概念例：通过下表说明数据的相关概念第第 1 1章章绪绪论论数据结构：是相互之间存在一种或多数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。种特定关系的数据元素的集合。问题：数据结构包括哪问题：数据结构包括哪3 3方面内容？方面内容？数据结构数据结构(Data(Data Structure) Structure)第第 1 1章章绪绪论论逻辑结构：描述数据元素

10、间的逻辑关系，与数据逻辑结构：描述数据元素间的逻辑关系，与数据的存储无关。的存储无关。数据逻辑结构可以用二元组（数据逻辑结构可以用二元组（D D，R R）描述）描述D D：数据元素定义域集合：数据元素定义域集合R R：数据元素上的关系：数据元素上的关系r ri i的集合的集合主要讨论主要讨论R=rR=r的情况的情况关系关系r r中若有序偶中若有序偶，则，则a a称为称为b b的的前驱前驱，b b称称为为a a的的后继后继1.1.逻辑结构逻辑结构第第 1 1章章绪绪论论逻辑结构可分为：逻辑结构可分为：集合结构集合结构：结构中的数据元素除了同属于一种类：结构中的数据元素除了同属于一种类型外，别无其

11、它关系。较少使用型外，别无其它关系。较少使用线性结构线性结构：结构中的数据元素之间存在一对一的：结构中的数据元素之间存在一对一的关系。关系。树型结构树型结构：结构中的数据元素之间存在一对多的：结构中的数据元素之间存在一对多的关系。关系。图形结构图形结构（或称（或称网状结构网状结构）：结构中的数据元素）：结构中的数据元素之间存在多对多的关系。之间存在多对多的关系。1.1.逻辑结构逻辑结构第第 1 1章章绪绪论论学号学号姓名姓名性别性别生日生日01丁一丁一男男02张三张三女女XXXOXOXOX沈阳沈阳北京北京西安西安长沙长沙广州广州重庆重庆乌鲁木齐乌鲁木齐拉萨拉萨23571113171923293

12、137线性结构线性结构树型结构树型结构图形结构图形结构集合结构集合结构第第 1 1章章绪绪论论一种数据结构一种数据结构G G（D, RD, R），其中），其中 D=D=1 1，2 2，3 3，4 4，5 5，6 6 R=R=r rr=r=， ， ， ， 试画出对试画出对应的逻辑结构图，并说明它是何种数据结构？应的逻辑结构图，并说明它是何种数据结构？逻辑逻辑结构结构举例举例第第 1 1章章绪绪论论物理结构（存储结构）：数据结构在计物理结构（存储结构）：数据结构在计算机中的存储表示。它包括数据元素的算机中的存储表示。它包括数据元素的表示和关系的表示。表示和关系的表示。基本物理结构基本物理结构顺序存

13、储结构顺序存储结构链式存储结构链式存储结构索引存储结构索引存储结构散列存储结构散列存储结构2.2.存储结构存储结构最常用的两种存储结构最常用的两种存储结构第第 1 1章章绪绪论论0 01 12 23 3.顺序结构空间示意图顺序结构空间示意图链式结构空间示意图链式结构空间示意图数组数组用指针实现用指针实现2.2.存储结构存储结构第第 1 1章章绪绪论论3.3.运算集合运算集合逻辑结构决定了算法的设计。逻辑结构决定了算法的设计。物理结构决定了算法的实现。物理结构决定了算法的实现。第第 1 1章章绪绪论论练习题1.1.从逻辑上可以把数据结构分为（从逻辑上可以把数据结构分为（ ）两大类。两大类。A A

14、动态结构、静态结构动态结构、静态结构 B B顺序结构、链式结构顺序结构、链式结构C C线性结构、非线性结构线性结构、非线性结构 D D初等结构、构造型结构初等结构、构造型结构第第 1 1章章绪绪论论练习题2.2.采用顺序存储结构表示数据时，相邻的采用顺序存储结构表示数据时，相邻的数数据元素的存储地址（据元素的存储地址（ ）。）。A A一定连续一定连续 B B一定不连续一定不连续 C C不一定连续不一定连续 D D部分连续，部分不连续部分连续，部分不连续第第 1 1章章绪绪论论抽象数据类型（抽象数据类型（AbstructAbstruct Data Data TypeType，简称简称ADTADT

15、）第第 1 1章章绪绪论论抽象数据类型（抽象数据类型（AbstructAbstruct Data Data TypeType，简称简称ADTADT）第第 1 1章章绪绪论论算法算法：对特定问题求解步骤的一种描述，是：对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个指令的有限序列。其中每一条指令表示一个或多个操作。或多个操作。例：烧开水的步骤（算法）：例：烧开水的步骤（算法）：E1E1：清洗水壶；：清洗水壶；E2E2：将水壶灌入适量的凉水；：将水壶灌入适量的凉水；E3E3：把水壶放到灶上；：把水壶放到灶上；E4E4：打开火；：打开火；E5E5：注意倾听，直到听到水开的声音；

16、：注意倾听，直到听到水开的声音；E6E6：关火；：关火；E7E7：把开水灌入暖瓶中；：把开水灌入暖瓶中；第第 1 1章章绪绪论论有穷性有穷性：算法总在执行有穷步后结束，且每：算法总在执行有穷步后结束，且每一步都在有穷时间内完成。一步都在有穷时间内完成。确定性确定性：不存在二义性，且相同的输入一定：不存在二义性，且相同的输入一定得到相同的输出。得到相同的输出。可行性可行性：算法描述的操作都可通过已经实现：算法描述的操作都可通过已经实现的基本运算执行有限次来实现。的基本运算执行有限次来实现。输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。输出输出：一个算法有一个或多个输出。：一个算

17、法有一个或多个输出。判断题：算法必须有输出，但可以没有输入。判断题：算法必须有输出，但可以没有输入。第第 1 1章章绪绪论论第第 1 1章章绪绪论论“好好”算法设计的要求算法设计的要求正确性正确性：算法应满足具体问题的需求。：算法应满足具体问题的需求。可读性可读性：便于理解、调试和维护。：便于理解、调试和维护。健状性健状性：算法应具有容错处理。当输入非法数据：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙时，算法应对其作出反应，而不是产生莫名其妙的输出结果。的输出结果。高效性和存储量需求：高效性和存储量需求：求解同一问题若有多种算求解同一问题若有多种算法，则执行时

18、间短的算法效率更高，占用存储空法，则执行时间短的算法效率更高，占用存储空间少的算法较好。间少的算法较好。 第第 1 1章章绪绪论论算法的时间复杂度算法的时间复杂度是指算法运行从开始到结束所需要的时间；是指算法运行从开始到结束所需要的时间；是对算法运行时间长短的相对度量；是对算法运行时间长短的相对度量；是用算法包含的简单操作的次数度量，是是用算法包含的简单操作的次数度量，是问问题规模题规模的一个函数。的一个函数。在实际应用中，往往放弃复杂的函数来表示在实际应用中，往往放弃复杂的函数来表示确切的时间复杂度，而采用一些简单的函数确切的时间复杂度，而采用一些简单的函数来近似表示时间性能，这就是来近似表

19、示时间性能，这就是渐近时间复杂渐近时间复杂度度，简称时间复杂度。，简称时间复杂度。第第 1 1章章绪绪论论例例: :求下列算法的时间复杂度求下列算法的时间复杂度main()main() int a,b,cint a,b,c; ;c=a+bc=a+b; ;printf(“the end is:%d”,cprintf(“the end is:%d”,c);); 时间复杂度为时间复杂度为(1)(1)，即，即常量阶常量阶。第第 1 1章章绪绪论论例：求下列算法的时间复杂度：例：求下列算法的时间复杂度：int sum(intint sum(int n) n) int i,sint i,s=0;=0; f

20、or(i=1;i=n;ifor(i=1;i=n;i+)+) s+=i;s+=i; return s;return s;时间复杂度为时间复杂度为(n)(n)，即，即线性阶线性阶。第第 1 1章章绪绪论论例例: :计算计算f=1f=1！+2+2！+3+3！+ +n+n！void factorsumvoid factorsum（intint n n） int i,j,f,wint i,j,f,w；f=0f=0；forfor（i=1;i=n;ii=1;i=n;i+） w=1w=1； forfor（j=1;j=i;jj=1;j=i;j+）w=ww=w* *j j； f=f+wf=f+w； return

21、return； 时间复杂度为时间复杂度为(n(n2 2) )。第第 1 1章章绪绪论论例：例：for(I=1,I=n;+Ifor(I=1,I=n;+I) ) for(j=1;j=n;+j for(j=1;j=n;+j) ) cIj cIj=0;=0; for(k=1;k=n;+k for(k=1;k1 & change;-I) change=0; for(j=0;jaj+1) aj aj+1; change=1；该程序中的操作次数依据输入数据的不同而该程序中的操作次数依据输入数据的不同而不同，通常这种情况下以最坏的情况为依据不同，通常这种情况下以最坏的情况为依据计算时间复杂度为计算时间复杂度为

22、:O(n:O(n2 2) )第第 1 1章章绪绪论论常见的渐进时间复杂度按数量级递增常见的渐进时间复杂度按数量级递增排列为：排列为：(1)(1)(loglog2 2n)(n)(n)(n)(nlognlog2 2n)n)(n n2 2)()(n n3 3)(2)numstu2-num若定义了指向结构体的指针变量，也可用若定义了指向结构体的指针变量，也可用-来引用成员。来引用成员。第第 1 1章章绪绪论论结构体变量的初始化结构体变量的初始化结构体变量的初始化，就是在定义结构体变量的结构体变量的初始化，就是在定义结构体变量的同时，对其成员赋初值。同时，对其成员赋初值。结构体变量初始化的格式：结构体变

23、量初始化的格式：structstruct 结构体名结构体名 结构体变量名结构体变量名= = 初始数据初始数据 ；与数组类似，结构体变量只可整体初始化，不与数组类似，结构体变量只可整体初始化，不可可整体赋值整体赋值，但结构体变量间可以相互赋值。，但结构体变量间可以相互赋值。第第 1 1章章绪绪论论main()struct student stu1；stu1=2010001,“Lifeng”,M,18,87.0, “Beijing”; 例：例：struct student long num; char name20; char sex; int age; float score; char add

24、r30;struct student stu1=2010001, “Li feng”, M, 18, 87.0, “Beijing”; 结构体变量可以整体初始化。结构体变量可以整体初始化。结构体变量不可整体赋值。结构体变量不可整体赋值。第第 1 1章章绪绪论论structstruct student student long num=2010001; long num=2010001; char name20=“ char name20=“Li fengLi feng”;”; char sex=M; char sex=M; int int age=18; age=18; float score

25、=87.0; float score=87.0; char addr30=“Beijing”; char addr30=“Beijing”; stu1,stu2; stu1,stu2;结构体类型不能直接在结构体成员表中对成结构体类型不能直接在结构体成员表中对成员赋初值员赋初值第第 1 1章章绪绪论论结构体数组的概念结构体数组的概念结构体数组是其数组元素都是具有相同结构体结构体数组是其数组元素都是具有相同结构体类型的结构体变量。即结构体数组是结构体变类型的结构体变量。即结构体数组是结构体变量集合的一种数组。量集合的一种数组。例如例如: :20100011 2010002 2010030 Life

26、ng Wangbing Chenming M M M 18 18 17 87 79 92 Beijing Beijing Beijing structstruct student student int int num; num; char name20; char name20; char sex; char sex; int int age; age; float score; float score; char addr30; char addr30; stu1,stu2, stu1,stu2,stu30; stu30; stu30;stu30;第第 1 1章章绪绪论论思考思考学生信息包括学号和成绩学生信息包括学号和成绩2 2项，请从键盘敲项，请从键盘敲入入4 4个学生的信息，然后计算该四名学生的个学生的信息，然后计算该四名学生的平均成绩并输出结果。平均成绩并输出结果。structstruct student studentintint num; num;intint score; score;structstruct student s4; student s4;第第 1 1章章绪绪论论用用typedeftypedef定义数据类型定义数据类型用用typedeftypedef定义数据类型定义数据类型就是给已经存在的就是给已经存在的数据类型重新命名一个新名字。