数据结构c语言版严蔚敏

算法和数据结构，教材： 数据结构(C语言版)。 严蔚敏，吴伟民编着。 清华大学出版社。 参考文献：1 数据结构。 张选平，雷咏梅编，严蔚敏审。 机械工业出版社。 2 数据结构与算法分析。 CliffordA.Shaffer着，张铭，刘晓丹译。 电子工业出版社。 3 数据结构习题与解析(C语实言版)。 李春葆。 清华大学出版社。 4 数据结构与算法。 夏克俭编着。 国防工业出版社。 第一章绪论，目前计算机已深入社会生活的各个领域，其应用不仅在科学计算领域，还广泛应用于控制、管理、数据处理等非数值计算领域。 计算机是用计算机研究信息显示和处理的科学。 这有信息显示、信息处理两个问题。 信息的表示和组织直接关系到处理信息的程序的效率。 随着应用问题的复杂化，导致信息量的激增和信息范围的扩大，许多系统程序和应用规模大，结构也相当复杂。 因此，必须分析待处理问题的对象特征与各对象之间的关系。 这就是数据结构这一课题需要探讨的问题。 创建解决实际问题的程序的常见过程：如何以数据格式描述问题-从问题中抽象出来的正确数学模型。如何将数据存储在问题的数据量大小和数据之间的关系计算机上，以及表示数据之间的关系？ 处理问题需要什么样的计算？ 编写的程序性能是否良好？ 上面列出的问题基本上用数据结构这一课程来回答。 计算机解题的一般程序，1.1数据结构及其概念，算法与数据结构是计算机科学中的综合性专业基础课。 数学、计算机硬件、计算机软件三者之间的核心课程，是一般程序设计的基础，也是编译器、操作系统、数据库系统和其他系统程序设计和实现大规模应用的重要基础例如，1.1.1数据结构的示例：在电话号码查询系统中有记录有n个姓名及其对应的电话号码的电话号码簿，(a1、b1)、(a2、b2)、(an、bn )，其中ai、bi (I=1，2n )分别表示某人的姓名及电话号码。 这个问题是典型的代表问题。 如表1-1所示，数据和数据是简单的一对一线性关系。 表1-1线性表结构，例2 :盘目录文件系统的盘根下有多个子目录和文件，各子目录可以包含多个子目录和文件，但各子目录只有一个父目录，以下相同图1-1树结构，示例3 :交通网络图可以从一个位置到另一个位置具有多条路径。 本问题是典型的网格结构问题，数据与数据的对多关系为非线性关系结构。 数据(Data ) :客观事物的符号表示。 在计算机科学中，是输入计算机并由计算机程序处理的所有符号的总称。 数据元素(DataElement ) :数据的基本单位，程序始终将其作为整体进行处理。 数据元素可以由多个数据项(DataItem )组成。 数据项是数据不可分割的最小单位。 数据项目是关于客观事物某一面的特性的数据记述。 数据对象(DataObject ) :具有相同性质的数据元素集合，是数据的子集。 字符集合c= (a、b、c，。 1.1.2基本概念和术语、数据结构(DataStructure ) :相互具有一定联系(关系)的数据元素的集合。 要素间的相互关系(关系)称为逻辑结构。 数据元素之间的逻辑结构有四种基本类型，如图1至图3所示。 集合：结构中的数据要素除了“属于同一集合”以外没有关系。 线性结构：结构中的数据要素之间有一对一的关系。树状结构：结构中的数据要素之间有一对多的关系。 图表结构或网格结构：结构中的数据要素之间存在多对多的关系。 数据结构的形式定义是Data-Structure=(D，s )这两个组。 其中d是数据元素的有限集合，s是d上关系的有限集合。 例2 :数据逻辑结构B=(K，R)K=k1，k2，k9R=， 画出该逻辑结构的图，它们为起点，它们为终点，1.1.3数据结构的形式定义，图1-3的基本结构图，1.1.4数据结构的存储方式， 数据元素之间的关系可以是人为定义以便于处理问题的自然关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。 在数据结构向计算机存储器的存储中，包括数据要素的存储与要素的关系的表现。 元素之间的关系在计算机上有两种不同的表达方式。 顺序显示和非顺序显示。 结果产生了两种不同的存储结构：顺序存储结构和链存储结构。 顺序存储结构表示数据元素之间的逻辑结构(关系)，以及数据元素在内存中的相对位置。 链式存储结构：添加一个指针，用于在每个数据元素中存储不同元素的地址，以表示数据元素之间的逻辑结构(关系)。 示例：设置数据集合a= 3.0，2.3，5.0，8.5，11.0 ，两种不同的存储结构。 顺序结构：数据元素存储的地址是连续的；链结构：不要求存储数据元素的地址是连续的。 数据的逻辑结构和物理结构是不可分割的两个方面，一种算法的设计取决于所选逻辑结构，算法的实现取决于所使用的存储结构。 在c语言中，用一维排列表现顺序记忆构造的链型记忆构造用构造体类型来表示。 数据结构的三个组件：逻辑结构：数据元素之间的逻辑关系的描述D_S=(D，s )存储结构：数据元素在计算机中的存储以及其逻辑关系的表示被称为数据存储结构或物理结构。 数据操作：对数据进行的运算。 本课程中说明的3个逻辑结构及其采用的存储结构如图14所示。 数据类型(DataType ) :值集合以及为该值集定义的一组操作的总称。 数据类型是与数据结构密切相关的概念。 c语言中的数据类型是基本类型和结构类型。 数据结构与数据类型不同，与数据对象不同，它不仅描述数据类型的数据对象，还描述数据对象元素之间的相互关系。 1.1.5数据类型、数据结构的主要运算如下。 从一个数据结构中删除(Destroy )一个数据元素；在数据结构中插入(Insert )一个数据元素；访问；修改(Modify )一个数据结构(其中的数据元素) 1.1.6数据结构运算，抽象数据类型(AbstractDataType，ADT )是指数学模型及其定义的一系列操作。 ADT的定义仅是一组逻辑特性描述，而不管其在计算机中的表示和实现方式如何。 因而，无论ADT的内部结构如何变化，只要其数学特性不变化，就不会对其外部使用产生影响。 ADT的形式化定义为ADT=(D，s，p )。 其中，d是数据对象，s是d上的关系集，p是针对d的基本操作集。 1.2抽象数据类型、ADT的一般定义形式是用伪代码记述ADT数据对象：数据关系：基本操作： ADT中的数据对象和数据关系的定义。 基本操作定义为：()初始条件：操作结果：初始条件：如果在执行操作之前不满足数据结构和参数必须满足的条件，则操作将失败并返回相应的错误消息。操作结果：说明操作正常结束后，数据结构的变化情况和应返回的结果。 另外，1.3.1算法(Algorithm ) :在特定问题解决方案(步骤)的描述中，在指令的有限序列中，每个指令代表一个或多个操作。 算法具有以下五个特性：贫困性：一个算法总是在执行贫困步骤后结束，所有步骤都必须在贫困时间内完成。 确定性：算法的各个指令必须具有正确的含义。 不存在二义性。 算法只有一个入口和一个出口。 可行性：算法是可行的。 即，算法记述的操作可以通过有限次执行已经实现的基本运算来实现。 1.3算法经初步分析，输入：一个算法有零个以上的输入，这些输入来自某一特定对象的集合。 输出：一个算法有一个或多个输出，这些输出是与输入有特定关系的量。 一种算法可以用多种方法来描述。 主要是用自然语言记述。用形式语言记述的计算机编程语言记述。 算法和程序是两个不同的概念。 计算机程序是使用算法中的编程语言的具体实现。 可能需要终止算法并非所有的计算机程序都是算法。 在本门课程的学习、作业练习、搭乘实践等过程中，算法都用c语言记述。 在网上实践时，必须编写完整的c语言程序以检查算法是否正确。 评估良好的算法有以下标准：准确性(Correctness ) :算法应满足具体问题的需要。 可读性(Readability ) :算法应易读，交流方便。 可读性好的算法有助于理解和修改算法。 鲁棒性(Robustness ) :算法应具有容错性。 在输入了不正当的数据或错误的数据的情况下，算法必须进行适当的反应或者处理，以免得出不可理解的输出结果。 通用性(Generality ) :算法应该具有普遍性，也就是说算法的处理结果对于一般的数据集合是成立的。 另外，1.3.2算法设计的要求通过在计算机上执行基于该算法而产生的程序的时间来测量算法的执行时间。 其方法通常是后验统计：在计算机内部进行运行时间和实际占有空间的统计。 问题：依赖于硬件和软件环境(它们必须首先运行以算法为基础编写的程序)，算法本身不具有实际价值，因为它们容易隐藏优劣。 预分析：求出该算法的时间边界函数。 1.3.3算法的效率测量，效率和存储需求：效率是运行算法的时间，存储需求是运行算法所需的最大存储容量。 一般来说，这两者都关系到问题的规模。 与此相关的要素是，根据算法选择哪个策略？问题的规模程序语言编译器生成的机器代码的质量机器执行指令的速度硬件和软件等相关部门的要素除外，特定的算法“执行功”的大小是问题的规模(通常为n 此外，在算法分析应用、算法中重复执行基本操作的次数是具有问题规模n的函数，将其时间标记为T(n)=O(f(n ) )，称为算法的渐近时间复杂度(AsymptoticTimecomplexity )，并且称为时间复杂度。 一般地，用最深的循环内的句子中的原始操作的执行频度(重复执行的次数)来表示。 “o”的定义：如果f(n )是正整数n的函数，则O(f(n ) )表示m0，如果nn0，则|f(n)|M|f(n0)|。 表示时间复杂度的次数为O(1) :常数时间次数O(n ) :线性时间次数O(n ) :对数时间次数O(n； n ) :线性对数时间次数、O(nk):k22、k次幂时间次数例1两个n次方阵的乘法运算for(i=1，i=n； i)for(j=1； j=n； j)cij=0； for(k=1； k=n； k)cij=aik*bkj； 因为是三重环，所以各环从1到n，总次数为nnn=n3的时间复杂度为T(n)=O(n3 )的例2 x； s=0； 将x的自我增加视为基本操作，句子的频度为1，即时间复杂度为O(1)。另外，s=0也考虑到基本操作，句子的频度为2，其时间复杂度为O(1)，即常数阶段。 例3for(i=1； i=n； i) x； s=x； 语句的频率为： 2n，其时间复杂度为： O(n )，为线性阶数。 例4for(i=1； i=n； i)for(j=1； j=n； j) x； s=x； 句子的频率为：2n2，其时间复杂度为： O(n2 )，是平方阶。 定理：如果A(n)=amnm am-1nm-1 a1n a0为m次多项式，则A(n)=O(nm )例5for(i=2； i=n； i)for(j=2； j=i-1； j) x； ai，j=x； 文本的频率为123n-2=(1n-2 ) (n-2 )/2=(n-1 ) (n-2 )/2=n2-3n 2小时复杂度为O(n2)，即算法的时间复杂度为均方根。 算法时间为O(1)的算法的基本运算的执行次数是固定的。 因此，总时间受常数(零次多项式)限制。 时间为O(n2 )的算法受二次多项式限制。 计算以下六个算法时间的