《2023年数据结构讲稿》由会员分享，可在线阅读，更多相关《2023年数据结构讲稿（70页珍藏版）》请在金锄头文库上搜索。
1、2023年数据结构讲稿 云淡风清 http:/ 第1章 数据结构概述 1.1概述 以下为某市部分院校的交通地图情况，要求找出从出发点到目的地之间的最短路径及其长度。 对于此问题，如果手工去做，速度慢(特别地，现实中实际地图信息要比此例复杂许多)，还容易出错，此时可借助于计算机完成。 计算机进行此类信息的处理时，涉及到两个问题：一是现实当中的信息在计算机中如何表示，二是如何对信息进行处理。 信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题不断复杂化，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间
2、存在的关系，这就是数据结构这门课所要研究的问题。 1.1.1编写解决实际问题的程序的一般流程 如何通过编写程序，以比手工更为高效精确的方式解决实际问题呢？一般流程如下： 1、由具体问题抽象出一个适当的数学模型； 2、分析问题所涉及的数据量大小及数据之间的关系； 3、确定如何在计算机中存储数据及体现数据之间的关系？ 4、确定处理问题时需要对数据作何种运算？ 5、确定算法并编写程序； 5、分析所编写的程序的性能是否良好？若性能不够好则重复以上步骤。 云淡风清 http:/ 上面所列举的问题基本上由数据结构这门课程来回答。 数据结构是计算机科学中的一门综合性专业基础课，是介于数学、计算机硬件、计算机
3、软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。 1.1.2数据结构的例子 1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 姓名 电话号码 陈伟海 13612345588 李四锋 13056112345 。 这是一种典型的线性结构。 2、磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，
4、但每个子目录只有一个父目录，依此类推。 。 本问题中各目录从上到小形成了一种一对多的关系，是一种典型的树形结构。 云淡风清 http:/ 3、交通网络图 下图表明了若干个城市之间的联系： 从图中可看出，一个地方到另外一个地方可以有多条路径，是一种典型的网状结构，数据与数据成多对多的关系。 4、排序问题 对100000个整数进行降序排序。 冒泡法程序： #include #include #include #define N 100000 void main() int i,j; int aN+1; srand(time(NULL); for(i=1;i ai=rand(); printf(n按
5、原序输出：n); for(i=1;i printf(%8d,ai); system(pause); for(j=1;j for(i=N;ij;i-) if(aiai-1) a0=ai; ai=ai-1; ai-1=a0; printf(n按新次序输出：n); 云淡风清 http:/ for(i=1;i printf(%8d,ai); printf(n); 快速排序程序： #include #include #include #define N 100000 void quick_sort(int aN+1,int left,int right) int j,last,temp; if(left
6、 /将划分子集的元素(此处选中间元素)移动到最左边 temp=aleft; aleft=a(left+right)/2; a(left+right)/2=aleft; last=left;/用last记录比关键字小的元素的最右位置 for(j=left+1;j if(ajaleft) temp=alast; alast=aj; aj=temp; last+; /对形成的新子集递归进行快速排序 quick_sort(a,left,last-1); quick_sort(a,last+1,right); void main() int i; int aN+1; srand(time(NULL);
7、for(i=1;i ai=rand(); printf(n按原序输出：n); for(i=1;i printf(%8d,ai); system(pause); 云淡风清 http:/ quick_sort(a,1,N); printf(n按新次序输出：n); for(i=1;i printf(%8d,ai); printf(n); 运行可知，两者速度差异非常明显，主要是排序所花的时间差别很大。可看出，同样的问题，采用不同方法进行处理，有可能呈现出非常大的性能方面的差异。 还可以找到许多其它例子，如图书馆的书目检索系统自动化问题，教师资料档案管理系统，多叉路口交通灯的管理问题等。 1.2基本概念
8、和术语 1.2.1数据(Data)： 是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 1.2.2数据元素(Data Element)： 是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。 1.2.3数据对象(Data Object)： 是性质相同的数据元素的集合，是数据的一个子集，其中的数据元素可以是有限的，也可以是无限的。如整数集合：N=0，1，2，是无限集，而字符集合：C=A，B，Z则为有限集。 1.2
9、.4数据的逻辑结构： 指对数据元素之间逻辑关系的描述。 数据元素之间的关系可以是一种或多种。 数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。其要点有两个方面：一是元素本身，二是元素之间的关系。数据元素之间的逻辑结构有四种基本类型，如下： 云淡风清 http:/ 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 线性结构：结构中相邻的数据元素之间存在一对一的关系。 树型结构：结构中相邻的数据元素之间存在一对多的关系。 图状结构或网状结构：结构中相邻的数据
10、元素之间存在多对多的关系。 数据结构数学形式的定义是一个二元组： DataStructure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例：设数据逻辑结构B=(K，R)，其中： K=k1, k2, , k9 R=， 画出这逻辑结构的图示，并确定哪些是起点，哪些是终点。 1.2.5数据的物理结构： 又称存储结构，指数据结构在计算机内存中的存储方式。 数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的存储。 元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。 顺序存储结构：用数据元素在存储
11、器中的相对位置来表示数据元素之间的逻辑结构(关系)。 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。 例：设有数据集合A=3.0,2.3,5.0,-8.5,11.0，两种不同的存储结构。 顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；通过结构体类型实现的链表来表示链式存储结构。 1.2.6数据结构(Data S
12、tructure)： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。 1.2.7数据结构的三个组成部分： 逻辑结构：数据元素之间逻辑关系的描述：D_S=(D，S)。 存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作：对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储结构如下图所示。 云淡风清 http:/ 逻辑结构与所采用的存储结构 数据逻辑结构层次关系图 1.2.8数据类型(Data Type)： 指的是一个值的集合和定义在该值集上的一组操作的总称。
13、数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型(如int，float，double，char等)和构造类型(如数组，结构体，共用体等)。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 1.3数据结构的运算 数据结构的主要运算包括： 建立(Create)一个数据结构； 消除(Destroy)一个数据结构； 从一个数据结构中删除(Delete)一个数据元素； 把一个数据元素插入(Insert)到一个数据结构中； 对一个数据结构进行访问(Acce)； 对一个数据结构(中的数据元素)进行修改(Modify)； 对一个数据结构进行排序(Sort)； 对一个数据结构进行查找(Search)。 以上只列举了一些常见运算，实际应用当中可能会遇到许多其它运算。 云淡风清 http:/ 1.4抽象数据类型(Abstract Data Type) 1.4.1抽象数据类型简
