数据结构 (3).ppt

《数据结构 (3).ppt》由会员分享，可在线阅读，更多相关《数据结构 (3).ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1数据结构数据结构西南大学计信院西南大学计信院 张虹张虹 E-mail:2使用教材：使用教材：严蔚敏严蔚敏 吴伟民吴伟民 编著，编著，数据结构（数据结构（C语言版），清华大学出语言版），清华大学出版社版社参考书：参考书：1、数据结构题集（、数据结构题集（C语言版），清华大学出版社，严蔚敏、语言版），清华大学出版社，严蔚敏、吴伟民、米宁，第吴伟民、米宁，第1版，版，1997.4；2、数据结构，人民邮电出版社，晋良颖、数据结构，人民邮电出版社，晋良颖 编编3、数据结构数据结构算法实现及解析，高一凡，西安电子科技算法实现及解析，高一凡，西安电子科技大学出版社大学出版社使用教材及参考书使用教材及参考书

2、3课程教学目的课程教学目的l在计算机及其应用的各个领域中，都会用到各种各样的数在计算机及其应用的各个领域中，都会用到各种各样的数据结构，通过本课程使学生学会分析和研究计算机加工对据结构，通过本课程使学生学会分析和研究计算机加工对象的特性，选择合适的数据结构和存储表示，以及编制相象的特性，选择合适的数据结构和存储表示，以及编制相应的实现算法应的实现算法l课程教学基本要求课程教学基本要求:本课程介绍各种最常用的数据结构，本课程介绍各种最常用的数据结构，阐述各种数据结构内涵的逻辑关系，讨论它们在计算机中阐述各种数据结构内涵的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构上的运算和实际的执

3、行的存储表示，以及在这些数据结构上的运算和实际的执行算法，并对算法的效率进行简要的分析和讨论。算法，并对算法的效率进行简要的分析和讨论。4数据结构的研究不仅涉及到数据结构的研究不仅涉及到计算机硬件计算机硬件（特别是编码理论、存储装置和存取方法）的研究（特别是编码理论、存储装置和存取方法）的研究范围，范围，而且和而且和计算机软件计算机软件的研究有着密切的关系，无论是编译程序还的研究有着密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。是操作系统，都涉及到数据元素在存储器中的分配问题。在研究在研究信息检索时信息检索时也必须考虑如何组织数据，以便查找和存取也必须考虑如何组

4、织数据，以便查找和存取数据元素更为方便。数据元素更为方便。课程介绍课程介绍5因此，可以认为因此，可以认为数据结构数据结构是介于是介于数学、计算机硬件和计算数学、计算机硬件和计算机软件机软件三者之间的一门核心课程。三者之间的一门核心课程。程序算法数据结构程序算法数据结构目前在我国，目前在我国，数据结构数据结构已经不仅仅是计算机专业的教已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。主要选修课程之一。通过对这门课程的学习可增强选择合适的数据结构与编写通过对这门课程的学习可增强选择合适的数据结构与编写高效的程

5、序的能力。高效的程序的能力。课程介绍课程介绍6“数据结构数据结构”的形成和发展的形成和发展单纯的数值计算单纯的数值计算带有一定结构的数据带有一定结构的数据带结构的数据带结构的数据字符字符表格表格图象图象研究数据内部的联系研究数据内部的联系数据结构数据结构研究数据外部的联系研究数据外部的联系数据模型数据模型 进一步发展：多媒体数据进一步发展：多媒体数据多媒体数据模型多媒体数据模型多媒体数据库多媒体数据库7教学安排及考试教学安排及考试讲课学时：讲课学时：72学时学时考试成绩计算：考试成绩计算：平时成绩（考勤、平时成绩（考勤、作业、课堂提问）作业、课堂提问）10分分实验（实验（30分）分）考试（考试

6、（60分）分）8目录目录第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列第第4章章 串串第第5章章 数组和广义表数组和广义表第第6章章 树和二叉树树和二叉树第第7章章 图图第第8章章 查找查找第第9章章 内部排序内部排序9第第0 0章章 构造数据类型构造数据类型10基本类型基本类型 构造构造类类型型派生派生类类型型整型整型intint结构体结构体structstruct数组类型数组类型字符型字符型charchar共用体（联合）型共用体（联合）型unionunion指针类型指针类型实型实型floatfloat枚举型枚举型enumenum双精度型双精度型doubledoub

7、le用户定义类型用户定义类型typedef typedef 空值型空值型voidvoid构造数据类型（导出类型）：构造数据类型（导出类型）：由基本数据类型按一定规则组由基本数据类型按一定规则组合而成的。广义上包括表中的合而成的。广义上包括表中的构造类型和派生类型。构造类型和派生类型。同一类型数据同一类型数据的顺序排列的顺序排列 类型不同但类型不同但相互关联相互关联 110.1结构体结构体结构体类型结构体类型结构体类型变量结构体类型变量(结构体变量结构体变量)结构体的成员结构体的成员(成员成员)：组成结构体的每个数据。组成结构体的每个数据。0.1.1 结构体类型定义结构体类型定义 0.1.2 结

8、构体变量说明结构体变量说明 0.1.3 结构体变量的使用结构体变量的使用 0.1.4 结构体变量的初始化结构体变量的初始化 0.1.5 结构体数组结构体数组 0.1.6 结构体和函数结构体和函数12struct结构体类型名结构体类型名类型名类型名结构体成员名；结构体成员名；/*成员表成员表*/;0.1.1 结构体类型定义结构体类型定义例例1描述通讯录的结构体类型。描述通讯录的结构体类型。structpersoncharname20;intage;charsex;charaddress100;longzipcode;例例2结构体类型的结构体类型的嵌套定义。嵌套定义。structbirthdayi

9、ntyear;intmonth;intday;structpersoncharname20;structbirthdaydate;charsex;charaddress100;longzipcode;类型名类型名成员变量名成员变量名130.1.2 结构体变量定义结构体变量定义 q间接定义间接定义q直接定义直接定义q无名定义无名定义qtypedef定义定义structbirthdayintyear;intmonth;intday;structpersoncharname20;structbirthdaydata;charsex;charaddress100;longzipcode;structp

10、ersonp;struct结构体类型名结构体类型名成员表；成员表；;struct结构体类型名结构体类型名变量名表；变量名表；先定义类型先定义类型,后单独定义变量。后单独定义变量。在类型定义之后立即定义变量。在类型定义之后立即定义变量。struct结构体类型名结构体类型名成员表；成员表；结构体变量名表结构体变量名表;structbirthdayintyear;intmonth;intday;structpersoncharname20;structbirthdaydata;charsex;charaddress100;longzipcode;p;定义一个无名结构体类型，直接定义变量。定义一个无名

11、结构体类型，直接定义变量。struct成员表；成员表；结构体变量名表结构体变量名表;structbirthdayintyear;intmonth;intday;structcharname20;structbirthdaydata;charsex;charaddress100;longzipcode;p;求结构体类型（或结构体变量）的字节数。求结构体类型（或结构体变量）的字节数。#defineNAMESIZE20#defineADDRSIZE100structbirthdayintyear;intmonth;intday;structpersoncharnameNAMESIZE;structb

12、irthdaydate;charsex;charaddressADDRSIZE;longzipcode;main()structpersonp;printf(theplength:%dn,sizeof(p);printf(thestructpersonlength:%dn,sizeof(structperson);Theplength:131Thestructpersonlength:131结构体变量的结构体变量的存储结构存储结构：对结构体变量成员对结构体变量成员顺序顺序分配存储空间。分配存储空间。140.1.3结构体变量的使用结构体变量的使用结结构构体体一一般般不不能能作作为为一一个个整整体

13、体参参加加数数据据处处理理，而而参参加加各各种种运运算算和和操操作作的的是是结结构构体体的的各各个个成成员员项项数数据据。对对成成员的使用方式：员的使用方式：结构体变量名结构体变量名.成员名成员名注：相同结构体类型的变量可以相互赋值。注：相同结构体类型的变量可以相互赋值。p.zipcode=130022;p.date.year=1980;structpersonp1,p2;p1=p2;150.1.4结构体变量的初始化结构体变量的初始化q间接初始化间接初始化q直接初始化直接初始化q无名初始化无名初始化结构体变量的初始化。结构体变量的初始化。#defineNAMESIZE20#defineADDR

14、SIZE100structbirthdayintyear;intmonth;intday;structpersoncharnameNAMESIZE;structbirthdaydate;charsex;charaddressADDRSIZE;longzipcode;structpersonp=LiPing,1994,12,25,m,zhongshanroad,310000;main()printf(Name:%sn,p.name);printf(birthday:%d,%d,%dn,p.date.year,p.date.month,p.date.day);printf(sex:%cn,p.se

15、x);printf(address:%sn,p.address);printf(zipcode:%ldn,p.zipcode);name:LiPingbirthday:1994,12,25sex:maddress:zhongshanroadzipcode:310000160.1.5 结构体数组结构体数组 1.结构体数组的定义 struct 结构体类型名 结构体数组名元素个数；structstudentaatd10=“zhangming”,18,m,“Lipiang”,20,f;structstudentaatd=“zhangming”,18,m,“Lipiang”,20,f;2.结构体数组的初

16、始化结构体数组的初始化struct结构体名结构体名数组名数组名元素个数元素个数=,；例例对对N个学生进行年龄从小到大的排序。个学生进行年龄从小到大的排序。#includestdio.h#defineN3#defineNAMESIZE20structstudentcharnameNAMESIZE;intage;charsex;structstudentstd10;main()inti,j;structstudentchange;printf(Pleaseinputstudentdatan);i=0;while(iN)printf(name:age:sex:);scanf(%s,stdi.name

17、);scanf(%d,&stdi.age);scanf(%c,&stdi.sex);i=i+1;for(i=0;iN-1;i+)for(j=i+1;jstdj.age)change=stdi;stdi=stdj;stdj=change;printf(Theresultaftersortingn);for(i=0;iN;i+)printf(Name:%stAge:%dtSex:%cn,stdi.name,stdi.age,stdi.sex);输入：输入：name:age:sex:aaa21mname:age:sex:bbb22fname:age:sex:ccc25m输出：输出：name:aaaa

18、ge:21sex:mname:bbbage:22sex:fname:cccage:25sex:m结构体结构体数组初始化。数组初始化。structsintnum;charcolor;chartype;main()structscar=101,G,c,210,Y,m,105,R,l,222,B,s,308,P,b;inti;printf(numbercolortypen);for(i=0;i-成员名成员名q结构体指针的使用结构体指针的使用21structstudentintnum;charname20;charsex;st=2001,LiMing,M,2002,Wangfang,F,2003,Zh

19、angRong,M;main()inti;structstudent*p;p=&st0;for(i=0;inum,(*p).name,sti.sex);使用结构体指针访问结构体的成员使用结构体指针访问结构体的成员:2001,LiMing,M2002,Wangfang,F2003,ZhangRong,M22q结构体的自使用与链表结构体的自使用与链表结构体的自使用：结构体的自使用：结构体的成员是指向其自身的结构体指针变量。结构体的成员是指向其自身的结构体指针变量。一般形式：一般形式：struct node int data;struct node*next;headNULL链表链表结点结点数据区数

20、据区指针区指针区链表头链表头23建立一条链，数据从键盘读取，链的首结点由建立一条链，数据从键盘读取，链的首结点由head返回。返回。structnode*creat()structnode*p,*head;inti;head=NULL;for(i=0;idata);p-next=NULL;if(head=NULL)head=p;elsep-next=head;head=p;return(head);#defineNULL0structnodeintdata;structnode*next;main()structnode*Head,*np;Head=creat();if(Head=NULL)p

21、rintf(Creatlinkerror!n);elsefor(np=Head;np!=NULL;np=np-next)printf(%dt,np-data);输入：输入：12345输出：输出：54321240.2.2 结构体指针与函数结构体指针与函数q结构体指针作函数的参数结构体指针作函数的参数structsinti;charc;st=125,A;main()printf(Theolddata:n);printf(ti=%dtc=%cn,st.i,st.c);sub(&st);printf(Thenewdata:n);printf(ti=%dtc=%cn,st.i,st.c);voidsub

22、(structs*sa)(*sa).i=2;(*sa).c=(*sa).c+1;输入：输入：Theolddata:i=125c=A输出：输出：Thenewdata:i=2c=B返回返回25q函数返回值为结构体指针函数返回值为结构体指针定义形式：定义形式：struct 结构体类型名结构体类型名*函数名（形式参数表）函数名（形式参数表）形式参数表说明形式参数表说明 函数体函数体 structsinti;charc;*sp;main()structs*sub();sp=sub();printf(Thedata:n);printf(i=%dtc=%cn,sp-i,(*sp).c);structs*su

23、b()structs*sv;sv=(structs*)malloc(sizeof(structs);sv-i=5;sv-c=B;return(sv);Thedata:i=5c=Bstructs*sub()structssv;sv.i=5;sv.c=B;return(&sv);warning C4172:returning address of local variable or temporarystructs*sub()structs*sv;sv=(structs*)malloc(sizeof(structs);sv-i=5;sv-c=B;free(sv);return(sv);260.3

24、用用typedef定义类型定义类型0.3.1 一般形式一般形式 typedef 类型名类型名 标识符；标识符；注：注：(1)typedef只定义类型名，不能定义变量名，是类型名只定义类型名，不能定义变量名，是类型名的别名。的别名。(2)与与#define相似，但有区别，新旧类型位置相反。相似，但有区别，新旧类型位置相反。typedefintINTEGER;27 0.3.2 用用typedef说明类型的步骤说明类型的步骤1)先定义变量的方法写出定义体。先定义变量的方法写出定义体。2)把变量名换成新类型名。把变量名换成新类型名。3)在最前面加上在最前面加上typedef。4)已定义完新类型名，可用

25、此新类型名已定义完新类型名，可用此新类型名 去去 定义变量定义变量。inti,j;typedefintINTEGER;INTEGERi,j;structtagDATEintmonth;intday;intyear;birthday;typedefstructtagDATEintMonth;intDay;intYear;Date,*PDate;DateBirthday;PDater;chars80;typedefcharSTRING80;STRINGs;28void swap(int x,int y)int temp;temp=x;x=y;y=temp;void main()int a=10,b

26、=20;swap(a,b);printf(“%d,%d”,a,b);参数传值是参数值的拷参数传值是参数值的拷贝，而不是参数本身。贝，而不是参数本身。函数参数传递函数参数传递29void swap(int*x,int*y)int temp;temp=*x;*x=*y;*y=temp;void main()int a=10,b=20;swap(&a,&b);printf(“%d,%d”,a,b;函数要改变调用它的函数的变量函数要改变调用它的函数的变量有两种方法：有两种方法：传指针调用传指针调用和和引用引用调用调用。当形参和实参结合时，复。当形参和实参结合时，复制的是变量的地址。制的是变量的地址。3

27、0void swap(int*x,int*y)int*temp;temp=x;x=y;y=temp;void main()int a=10,b=20;int*m,*n;m=&a;n=&b;swap(m,n);printf(“%d,%d”,a,b);31void swap(int&x,int&y)int temp;temp=x;x=y;y=temp;void main()int a=10,b=20;swap(a,b);printf(“%d,%d”,a,b;32l计算机的应用已不再局限于科学计算，而更多地用于控制、计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等管理及数据处理等

28、非数值计算的处理工作非数值计算的处理工作。l与此对应，计算机加工处理的对象由纯粹的数值发展到与此对应，计算机加工处理的对象由纯粹的数值发展到字字符、表格和图像符、表格和图像等各种具有一定结构的数据。等各种具有一定结构的数据。l为了编写出一个为了编写出一个“好好”的程序，必须分析的程序，必须分析待处理的对象的待处理的对象的特征以及各对象之间存在的关系特征以及各对象之间存在的关系，这就是，这就是“数据结构数据结构”这这门学科形成和发展的背景。门学科形成和发展的背景。第一章第一章 绪绪 论论第一章第一章 绪绪 论论33问题描述确定求解步骤计算机求解：编程、调试、测试、获解输出 建立抽象数据模型计算机

29、解决问题的几个步骤：计算机解决问题的几个步骤：寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。些操作对象之间含有的关系，然后用数学的语言加以描述。然而，更多的非数值问题无法用数学方程描述。什么是数据结构呢然而，更多的非数值问题无法用数学方程描述。什么是数据结构呢？先看以下几个例子。？先看以下几个例子。34数学模型：数学模型：数值问题与非数值问题数值问题与非数值问题1）数值问题）数值问题例例已知：游泳池的长已知：游泳池的长len和宽和宽wide，求面积，求面积area设计设计求

30、解问题的方法求解问题的方法 编程编程main()intlen,wide,area;scanf(“%d%d%n”,&l,&w);area=len*wide;printf(“area=%d”,area);建模型：建模型：问题涉及的对象：游泳池的长问题涉及的对象：游泳池的长len宽宽wide，面积，面积area；对象之间的关系：对象之间的关系：area=len wide35书目文件线性表例例1 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片按书名按作者名按分类号索引表索引表36树.例例2 人机对奕问题人机对奕问题37l对于一个多叉路口，设计一个对于一

31、个多叉路口，设计一个交通信号灯的管理系统。交通信号灯的管理系统。l首先需要分析一下所有车辆的首先需要分析一下所有车辆的行驶路线的冲突问题。行驶路线的冲突问题。l这个问题可以归结为对车辆的这个问题可以归结为对车辆的可能行驶方向作某种分组，可能行驶方向作某种分组，对分组的要求是使任一个组对分组的要求是使任一个组中各个方向行驶的车辆可以中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。同时安全行驶而不发生碰撞。CEDAB例例3 多叉路口交通灯管理问题多叉路口交通灯管理问题38可通行方向可通行方向lABACADlBABCBDlDADBDClEAEBECEDCEDAB例例3多叉路口交通灯管理问题多叉路口

32、交通灯管理问题39有些通行方向显然不能同时进行，相应的结点间画一条连线。有些通行方向显然不能同时进行，相应的结点间画一条连线。ABACADBABCBDDAD BDCEAEBECED图图1.2交叉路口的图示模型交叉路口的图示模型CEDAB图40把图把图1.2中的结点进行分组，使得有结点相连的结点不在中的结点进行分组，使得有结点相连的结点不在同一个组里。同一个组里。l 地图着色问题地图着色问题如果把上图中的一个结点理解为一个国家，如果把上图中的一个结点理解为一个国家，结点之间的结点之间的连线看作两国有共同边界，上述问题连线看作两国有共同边界，上述问题 就变成著名的就变成著名的“着色问题着色问题”：

33、即求出最少要几种颜色可将图中所有即求出最少要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。国家着色，使得任意两个相邻的国家颜色都不相同。l通过上面的分析，我们就获得了该交通管理系统的数通过上面的分析，我们就获得了该交通管理系统的数学模型。下面就可以着手进行算法的设计。学模型。下面就可以着手进行算法的设计。例例3多叉路口交通灯管理问题多叉路口交通灯管理问题41算法设计算法设计2.“贪心法贪心法”while 有结点未着色；有结点未着色；选择一种新颜色；选择一种新颜色；在未着色的结点中在未着色的结点中,给尽可能多的彼此结点之间没有边连给尽可能多的彼此结点之间没有边连的点着色；的点

34、着色；1.对对n个结点，逐个测试其所有组合；个结点，逐个测试其所有组合；例例3多叉路口交通灯管理问题多叉路口交通灯管理问题42ABACADBABCBDDAD BDCEAEBECED图图1.2交叉路口的图示模型交叉路口的图示模型图ABACADBABCBDDADBDCEAEBECEDCEDAB着色结果着色结果43把上面方法应用于图把上面方法应用于图1.2，得到下面的分组：，得到下面的分组：绿色：绿色：AB,AC,AD,BA,DC,ED 蓝色：蓝色：BC,BD,EA 红色：红色：DA,DB 白色：白色：EB,EC例例3多叉路口交通灯管理问题多叉路口交通灯管理问题44l综合上面三个例子，描述这类非数值

35、计算问题的数学综合上面三个例子，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如模型不再是数学方程，而是诸如表、树和图表、树和图之类的数之类的数据结构。据结构。l因此，简单说来，数据结构是一门因此，简单说来，数据结构是一门研究非数值计算的研究非数值计算的程序设计问题中程序设计问题中计算机的操作对象以及它们之间的关计算机的操作对象以及它们之间的关系和操作等等的学科系和操作等等的学科。l数据结构研究的内容主要包括数据的逻辑结构、物理数据结构研究的内容主要包括数据的逻辑结构、物理结构以及对这种结构定义的运算。结构以及对这种结构定义的运算。第一章第一章 绪绪 论论45数据数据(Data):是对

36、客观事物的符号表示，在计算机科学是对客观事物的符号表示，在计算机科学中是指中是指所有能输入到计算机中并被计算机程序处理所有能输入到计算机中并被计算机程序处理的符号的总称。的符号的总称。对计算机科学而言，数据的含义极为广泛，如图像、对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。声音等都可以通过编码而归之于数据的范畴。数据元素数据元素(Data Element):是数据的基本单位，在计算是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。机程序中通常作为一个整体进行考虑和处理。例如，例例如，例12中的中的“树树”中的一个棋盘格局，例中的一个棋盘格

37、局，例13中的中的“图图”中的一个圆圈都被称为一个数据元素。中的一个圆圈都被称为一个数据元素。1.2 基本概念和术语基本概念和术语46一个数据元素可由若干个数据项组成。例如，例一个数据元素可由若干个数据项组成。例如，例11中一本书的书中一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。名等）为一个数据项。数据项是数据的不可分割的最小单位数据项是数据的不可分割的最小单位。数据对象：数据对象：是性质相同的数据元素的集合，是数据的一个子集。例是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集

38、合如，整数数据对象是集合N0，1，2，字母字符数据对，字母字符数据对象是集合象是集合C A，B，C，。数据结构数据结构(定义一定义一)：是相互之间存在一种或多种特定关系的数据元是相互之间存在一种或多种特定关系的数据元素的集合。素的集合。数据结构数据结构(定义二定义二)：是按照一定逻辑关系组织，并按一定存储方法：是按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。存储的数据的集合，且需要定义一系列运算。1.2 基本概念和术语基本概念和术语47逻辑结构、存储结构和运算合称为数据结构的三要素。逻辑结构、存储结构和运算合称为数据结构的三要素。逻辑结构：逻辑结构：指数据元素之

39、间的逻辑关系。即从逻辑关系上描述指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据，它与数据的存储无关，是独立于计算机的。通常分为四类基本结构：通常分为四类基本结构：一、集合一、集合 结构中的数据元素除了同属于一种类型外，别无其结构中的数据元素除了同属于一种类型外，别无其它关系。它关系。二、线性结构二、线性结构 结构中的数据元素之间存在一对一的关系。结构中的数据元素之间存在一对一的关系。三、树型结构三、树型结构 结构中的数据元素之间存在一对多的关系。结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构四、图状结构或网状结构 结构中的数据元素之间

40、存在多对多结构中的数据元素之间存在多对多的关系。的关系。1.2 基本概念和术语基本概念和术语48数据结构的形式定义为：数据结构是一个二元组：数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：其中：D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集。上关系的有限集。例例 复数的数据结构定义如下：复数的数据结构定义如下：Complex=(C，R)其中：其中：C是含两个实数的集合是含两个实数的集合C1，C2，分别表示复，分别表示复数的实部和虚部。数的实部和虚部。R=P，P是定义在集合上的一种关是定义在集合上的一种关系系C1，C2。1.2 基本概念

41、和术语基本概念和术语49（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f),(f,d)解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：bcaefd此结构为此结构为线性线性的。的。例：用图形表示下列数据结构，并指出它们是属于线例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。性结构还是非线性结构。50 d1 d5 d2 d4 d3该结构是该结构是非线性非线性的。的。解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：（2）S=(D,R)D=di|1i5 R=(di,dj),ij51存储结构存储结构亦称物理结构，

42、是数据的逻辑结构在计算机存储器内亦称物理结构，是数据的逻辑结构在计算机存储器内的表示（或映像），它依赖于计算机。的表示（或映像），它依赖于计算机。数据结构在计算机中有两种不同的表示方法：数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示顺序表示和非顺序表示常用的两种存储结构：常用的两种存储结构：顺序存储结构和链式存储结构顺序存储结构和链式存储结构顺序存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。素之间的逻辑关系。链式存储结构：链式存储结构：在每一个数据元素中增加一个存放地址的指针，在每一个数据元素中增加一个

43、存放地址的指针，用此指针来表示数据元素之间的逻辑关系。用此指针来表示数据元素之间的逻辑关系。1.2 基本概念和术语基本概念和术语52元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储531536元素21400元素11346元素3 元素41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1536 元素元素3 3 13

44、46 1346链式存储链式存储h54数数据据的的运运算算：在在数数据据的的逻逻辑辑结结构构上上定定义义的的操操作作算算法法，它它在在数据的存储结构上实现。数据的存储结构上实现。最常用的数据运算有最常用的数据运算有5种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序55数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等线性结构线性结构非线性结构非线性结构顺序存储顺序存储链式存储链式存储线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：1.2 基本概念和

45、术语基本概念和术语56数据类型：数据类型：数据类型是一个值的集合和定义在这个值集范围上数据类型是一个值的集合和定义在这个值集范围上的一组操作的总称。例如，的一组操作的总称。例如，C语言中的整型变量，其值集为某语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为：加、减、乘、除和个区间上的整数，定义在其上的操作为：加、减、乘、除和取模等算术运算。取模等算术运算。按按“值值”的不同特性，高级程序语言中的数据类型可分为：的不同特性，高级程序语言中的数据类型可分为：基本类型：基本类型：整型、浮点型、字符型等整型、浮点型、字符型等构造类型：构造类型：数组、结构、联合、指针、枚举等数组、结构、联

46、合、指针、枚举等1.2 基本概念和术语基本概念和术语571.2 基本概念和术语基本概念和术语抽象数据元素：抽象数据元素：抽象定义的、没有实际含义的数据元素。抽象定义的、没有实际含义的数据元素。抽象数据类型（定义一）：抽象数据类型（定义一）：l由用户定义，用以表示应用问题的数据模型。由用户定义，用以表示应用问题的数据模型。l由基本的数据类型构成，并包括一组相关的服务（或称由基本的数据类型构成，并包括一组相关的服务（或称操作）。操作）。l与数据类型实质上是一个概念，但其特征是使用与实现与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。分离，实行封装和信息隐蔽

47、（独立于计算机）。58抽象数据类型（定义二）：一个数学模型以及定义在该模型上的抽象数据类型（定义二）：一个数学模型以及定义在该模型上的一组操作。一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型实际上就是对数据结构的定义。因为它定义了一个抽象数据类型实际上就是对数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的

48、一组算法。数据的逻辑结构以及在此结构上的一组算法。和数据结构的形式定义相对应，抽象数据类型可用三元组描述如和数据结构的形式定义相对应，抽象数据类型可用三元组描述如下：（，）下：（，）D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P是对是对D的基本操作集。的基本操作集。1.2 基本概念和术语基本概念和术语59本书采用以下格式定义抽象数据类型本书采用以下格式定义抽象数据类型抽象数据类型的定义：抽象数据类型的定义：ADT抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT抽象数据类型名抽象数据类型名基本操作的定义格式为：基本操作的定义格式为：基

49、本操作名（参数表）基本操作名（参数表）初始条件：初始条件：操作结果：操作结果：1.2 基本概念和术语基本概念和术语60抽象数据类型三元组的定义：抽象数据类型三元组的定义：ADT Triplet数据对象：数据对象：D=e1,e2,e3|e1,e2,e3 ElemSet数据关系：数据关系：R1=,基本操作：基本操作：InitTriplet(&T,v1,v2,v3)操作结果操作结果：构造了三元组：构造了三元组T，元素，元素e1,e2和和e3分别赋以参数分别赋以参数v1,v2和和v3的值。的值。ADT Triplet1.2 基本概念和术语基本概念和术语61ADT Triplet数据对象数据对象：D=e

50、1,e2,e3|e1,e2,e3 ElemSet数据关系数据关系：R1=,基本操作基本操作：Get(T，i，&e)初始条件初始条件：三元组：三元组T已存在，已存在，1 i 3操作结果操作结果：用：用e返回返回T的第的第i元的值。元的值。ADT Triplet1.2 基本概念和术语基本概念和术语62抽象数据类型抽象数据类型可通过固有数据类型来表示和实现，即利用处理可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。来组合新的操作。由于本书在高级程序设计语言的虚拟层次上讨论抽象数据类型由于