数据结构c语言版严蔚敏

1、算法和数据结构，教材：数据结构(c语言版本)。严郁敏，吴伟民编着。清华大学出版社。参考文献：1数据结构。张择平，张艺兴咏梅编辑，严玉民审判。机械产业出版社。2数据结构和算法分析。克利福德ashaffer，张明，刘晓丹翻译。电子工业报道。3数据结构练习和分析(c实际版本)。李春宝。清华大学出版社。4数据结构和算法。节俭地改编夏天。国防产业出版社。第一章线程理论，现在计算机深入社会生活的各个领域，其应用不再局限于科学计算，更多地用于控制、管理、数据处理等非数值计算领域。电脑是研究用电脑表达和处理信息的科学。这包括两个问题。信息的表达，信息的处理。信息的表达和组织与处理信息的程序的效率直接相关。随着

2、应用程序问题的复杂，信息的急剧增长和信息范围的扩大，许多系统应用程序和应用程序的规模变大，结构变得非常复杂。因此，必须分析处理中对象的特性以及每个对象之间的关系，这是数据结构过程中要研究的问题。编写解决实际问题的程序一般流程：如何以数据格式描述问题？由问题抽象出适当的数学模型。与问题相关的数据大小和数据之间的关系；如何在计算机中存储数据并反映数据之间的关系？处理问题时，需要对数据进行哪些操作？您编写的程序性能好吗？以上列出的问题基本上由名为数据结构的课程回答。计算机故障诊断的一般阶段，1.1数据结构及其概念，算法和数据结构是计算机科学的综合专业基础课程。数学、计算机硬件和计算机软件之间的核心课

3、程是设计和实现编译程序、操作系统、数据库系统和其他系统程序以及大型应用程序的重要基础。1.1.1数据结构示例，示例1:电话号码祖怀系统记录n个人的姓名及其电话号码，其中(a1，B1)，(a2，B2)，(an，bn)，其中ai，bi(i=1，22)这个问题是常见的形式问题。如表1-1所示，数据与数据是简单的一对一线性关系。表1-1线性表结构，示例2:磁盘目录文件系统磁盘根目录下有许多子目录和文件，每个子目录可以包含多个子目录和文件，但每个子目录只能有一个父目录，等等，这是一个典型的非线性关系结构树结构，其中数据和数据具有一对多关系，如图1-1所示。图1-1树结构，示例3:交通网络图从一个位置到另

4、一个位置可以有多条路径。这是一个典型的网格结构问题，具有数据和数据的多对一关系，是非线性关系结构。数据：客观事物的象征性表达。在计算机科学中，停止是可以输入计算机并由计算机程序处理的所有符号的总称。数据元素：通常在程序中作为整体考虑和处理的数据的基本单位。数据元素可以包含多个数据项(Data Item)。数据项是数据不可分割的最小单位。数据项是对客观事物某一方面的特性的数据描述。数据对象：具有相同特性的数据元素的集合，是数据的子集。字母集合C=A、B、C .1.1.2基本概念和术语、数据结构(Data Structure):具有徐璐(存在)特定关系(关系)的数据元素的集合。元素之间的相互关系(

5、关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。集合：除了“属于同一集合”外，结构中的数据元素没有其他关系。线性结构：结构中的数据元素之间存在一对一关系。树状结构：结构中的资料元素之间存在一对多关系。图表结构或网格结构：结构中的数据元素之间存在多对一关系。数据结构的格式定义是二进制组。Data-Structure=(D，s)，其中：D是数据元素的有限集，s是D相关系的有限集。范例2:设定资料逻辑结构B=(K，R) K=k1，k2，K9 R=，以图形方式显示此逻辑结构，它们是起点，它们是终点，1.1.3资料结构的形式也可以是人为定义的关系，以便于处理问题。这种自然或人工

6、定义的“关系”称为数据元素之间的逻辑关系，其结构称为逻辑结构。计算机内存中数据结构的存储包括数据元素的存储和元素之间关系的显示。元素之间的关系在计算机上有两种不同的表示方法：顺序表示和非顺序表示。因此，产生了两种不同的存储结构：顺序存储结构和链存储结构。顺序存储结构：数据元素之间的逻辑结构(关系)，表示为数据元素在存储中的相对位置。链存储结构：指示数据元素之间逻辑结构(关系)的指针为每个数据元素添加存储不同元素地址的指针。例如，数据集A=3.0，2.3，5.0，-8.5，11.0，还有两个徐璐的不同存储结构。顺序结构：存储数据点的地址是连续的。链结构：存储数据元的地址要求是否连续。数据的逻辑结

7、构和物理结构不可分割的两个方面，一种算法的设计取决于选择的逻辑结构，而算法的实现取决于采用的存储结构。在c语言中，以一维数组表示顺序存储结构。链存储结构显示为结构类型。数据结构的三个组件：逻辑结构：数据元素之间逻辑关系的说明D_S=(D，S)存储结构：在计算机上存储数据元素并表示其逻辑关系的方法称为数据的存储结构或物理结构。使用数据：要对数据执行的操作。本课程将讨论的三个逻辑结构和使用的存储结构如图1-4所示。数据类型：一个通用术语，指值集及其值集中定义的工作集。数据类型是与数据结构密切相关的概念。c语言的数据类型是默认类型和构造类型。数据结构不同于数据类型，与数据对象不同，数据结构描述数据对

8、象的元素以及数据类型的数据对象之间的相互关系。1.1.5数据类型，数据结构的主要运算是数据结构的创建(Create)。移除资料结构(Destroy):从资料结构中删除资料元素(Delete)。将数据元素插入数据结构(Insert)。存取资料结构(access)；修改一个数据结构(中的数据元素)(modify)；数据结构排序(sort)；浏览数据结构(Search)。1.1.6数据结构的运算，抽象数据类型(Abstract Data Type，ADT):表示数学模型及其定义的操作集。ADT的定义只是一组逻辑特性说明，与计算机中的表示或实现无关。因此，无论ADT的内部结构如何变化，除非其数学特性发

9、生变化，否则不会影响其外部使用。ADT的公式定义为ADT=(D，s，p)。其中：d是数据对象，s是d的关系集，p是d的基本操作集。1.2抽象数据类型，ADT的一般定义形式用伪代码描述ADT数据对象：数据关系：基本操作：在ADT中，数据对象和数据关系的定义。默认操作定义如下：()初始条件：作业结果：初始条件：说明执行作业之前数据结构和参数必须满足的条件。如果不满足，操作将失败，并返回相应的错误消息。作业结果：说明作业正常完成后数据结构的更改以及应返回的结果。1.3.1算法(Algorithm):特定故障排除方法(步骤)的说明，其中每个指令代表一个或多个任务的受限命令序列。算法具有以下5个特征：也

10、就是说，算法必须总是在可怜的阶段运行后终止，每个阶段必须在贫穷的时间内完成。确定性：算法中的每个命令必须具有正确的含义。没有异议。算法只有一个入口和一个出口。可行性：算法是可能的。算法中描述的操作可以通过有限地执行已经实现的基本运算来完成。1.3算法分析初步，输入：算法具有从特定对象集合中获取的零个或多个输入。输出：算法具有一个或多个输出，这些输出是与输入有特定关系的量。算法主要可以使用自然语言说明，以多种方式进行说明。使用格式语言说明使用计算机编程语言说明。算法和程序是两个不同的概念。一个计算机程序是对一种算法使用一种编程语言的具体实现。算法必须能够终止，这意味着不是所有的计算机程序都是算法

11、。在这门课的学习、作业练习、上述实践等方面，算法都用c语言描述。在机器实践中，为了确保算法正确，必须用完整的c语言程序编写。评估好的算法有几个标准正确性。算法必须满足特定问题的要求。可读性：算法应该易于阅读和沟通。可读性好的算法有助于理解和修改算法。坚固性：算法必须具有容错能力。如果输入的数据不正确或无效，算法必须能够在没有未知输出结果的情况下正确地进行匹配或处理。通用性：算法必须是通用的。换句话说，算法的处理结果对于一般数据集是成立的。1.3.2算法设计的要求，算法执行时间以根据该算法编写的程序在计算机上执行所花费的时间来测量。通常有两种后统计信息：计算机内部运行时间和实际占用空间。问题：首

12、先必须根据算法运行准备好的程序。依靠硬件和软件环境，很容易隐藏算法本身的优缺点。没有实际价值。预分析：查找算法的时间边界函数。1.3.3算法的效率测量、效率和存储要求：效率表示算法运行的时间。存储要求是运行算法所需的最大存储空间。一般来说，这两件事与问题的规模有关。与此相关的元素包括：根据算法选择什么策略？问题的规模编程语言；编译程序生成的机器代码的质量；机器执行指令的速度；您可以离开相关部门元素(如硬件和软件)，认为特定算法“运行工作量”的大小仅取决于问题大小(通常用n表示)，也可以说是问题大小的函数。算法分析应用示例，算法中基本运算重复的次数是以T(n)=O(f(n)记录时间测量的问题规模

13、n的函数，称为算法的渐近时间复杂性，这称为时间复杂性。通常在最深的循环内经常使用的语句中，以原始作业的执行频率(重复执行次数)表示。“O”的定义：如果f(n)是正整数n的函数，则O(f(n)表示M0；如果n n0，则为| f(n) | M | f(n0) |。表示时间复杂性的阶数为O(1):常数时间阶O (n):线性时间阶O(n):对数时间阶O(nn):线性对数时间阶O (nk)，O (nk): k2，k阶时间阶示例两个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)是x；s=0；如果将x自身增量视为主要操作，则语句频率为(1)。如果S=0度被视为默认操作，则语句频率为，时间复杂性为(1)，即常数度数。范例for(I=1；I=n；I)x；s=x；语句频率为2n，时间复杂度为O(n)，是线性阶数。范例for(I=1；I=n；I)for(j=1；j=n；j)x；s=x；语句频率为2n2，时间复杂度为O(n2)，平方阶。清理：A(n)=a m n m a m-1 n m-1 a1n A0是m阶多项式时A