结构基础

起源1968年美国唐•欧•克努特教授开创了数据结构的最初体系他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构语其操作的著作。

我们一般认为本书开创了数据结构的系统概念。

70年代初数据结构作为一门独立的课程开始进入大学课堂。

数据结构的发展经历三个阶段无结构阶段结构化阶段和面向对象阶段和程序发展的三个阶段不谋而合了

无结构阶段在计算机发展的早期阶段主要应用于科学计算。

此时程序设计主要使用机器语言和汇编语言数据的表示和操作主要依赖数学公式和模型。

数据结构的概念尚未形成程序设计更注重数值计算而非数据之间的关系。

结构化阶段随着计算机应用领域的扩大人们开始关注程序设计规范化的重要性。

在这个阶段数据结构的概念逐渐形成并引入了抽象数据类型ADT的概念。

ADT将数据的表示和操作封装在一起使得程序设计更加模块化和灵活。

同时各种基本的数据结构如数组、链表、栈、队列等得到广泛应用。

此时数据结构的教学和研究也开始兴起。

面向对象阶段80年代初期至今面向对象的程序设计方法逐渐流行起来。

面向对象的设计思想将数据和操作封装在对象中通过类和继承的机制实现数据结构的抽象和重用。

这一阶段数据结构变得更加丰富多样大量的封装类如链表、树、图等被设计出来使得程序设计者能够更方便地使用和操作数据结构。

同时面向对象的设计方法也提供了更好的模块化和可扩展性。

总的来说数据结构的发展经历了无结构阶段、结构化阶段和面向对象阶段。

随着计算机应用领域的扩大和程序设计的不断演进数据结构的概念逐渐形成并得到广泛应用。

这些不同阶段的发展为程序设计者提供了丰富的工具和技术使得他们能够更好地组织和处理数据并设计出高效的算法和程序。

何为算法

算法是指解决特定问题的一系列清晰而有限的指令或步骤这些指令描述了如何在有限时间内完成任务或达成目标。

算法可以用来处理各种计算问题从简单的数学计算到复杂的数据处理和优化任务。

一个算法通常由输入、输出和处理三个部分组成。

输入是指问题的初始数据输出是指解决问题后得到的结果处理则是指将输入转换为输出的具体步骤。

高效性算法应该在合理的时间内完成任务即具有高效的时间和空间复杂度。

健壮性算法应该能够处理各种异常情况如输入数据的错误或不完整等。

算法在计算机科学中扮演着非常重要的角色因为它们是计算机程序的核心。

无论是编写操作系统、设计网络协议、开发应用程序还是创建游戏都需要使用算法来实现。

因此学习算法是计算机科学教育中的重要组成部分。

数据结构基础

数据数据是指描述事物的符号或信息。

数据不仅仅包括了整形浮点数等数值类型还包括了字符甚至声音视频图像等非数值的类型。

数据元素数据元素是数据的基本单位通常作为一个整体进行处理。

例如一个整数、一个字符或一个对象都可以是一个数据元素。

数据项数据项是数据元素中的最小单位它是数据的不可分割的基本单位。

例如一个整数中的每个数字就是一个数据项。

数据对象是性质相同的一类数据元素的集合是数据的一个子集。

数据对象可以是有限的也可以是无限的。

数据结构主要是指数据和关系的集合数据指的是计算机中需要处理的数据而关系指的是这些数据相关的前后逻辑这些逻辑与计算机储存的位置无关其主要包含以下的四大逻辑结构。

四大逻辑结构Logic

1、线性结构线性结构中的数据元素之间存在一对一的关系即每个数据元素只有一个直接前驱和一个直接后继。

常见的线性结构包括数组、链表、栈和队列。

如图:

2、树形结构树形结构中的数据元素之间存在一对多的关系即每个数据元素可以有多个直接后继。

常见的树形结构包括二叉树、堆和哈夫曼树。

3、图形结构图形结构中的数据元素之间存在多对多的关系即每个数据元素可以与多个其他元素相连。

常见的图形结构包括有向图和无向图。

4、集合结构集合结构中的数据元素之间没有任何特殊的关系是相互独立的。

常见的集合结构包括哈希表和并查集。

数据类型

Type是高级程序设计语言中的概念是数据的取值范围和对数进行操作的总和。

数据类型规定了程序中对象的特性。

程序中的每一个变量常量或者表达式都属于一种数据类型。

2、抽象数据类型

抽象数据类型是一种概念上的定义用于描述数据的逻辑结构和操作。

它将数据的表示和操作细节隐藏起来只暴露出对外的接口使得使用者只需要关注数据的功能而不需要了解具体的实现细节。

抽象数据类型可以看作是一种数据的模板或者蓝图它定义了数据的取值范围以及对数据进行的操作。

通过定义一组操作可以对数据进行增删改查等操作而不必关心具体的实现方式。

push将一个元素压入栈顶pop从栈顶弹出一个元素top获取栈顶元素的值isEmpty判断栈是否为空size获取栈的大小

通过这些操作我们可以在程序中使用栈这个抽象数据类型来实现各种功能比如实现括号匹配、逆序输出等。

抽象数据类型的优点在于它提供了高度的封装性和抽象性使得程序的设计更加模块化和可维护。

同时它也提供了良好的接口定义使得不同的实现可以替换而不影响使用者的代码。

总之抽象数据类型是对数据的抽象和封装定义了数据的取值范围和操作集合通过隐藏实现细节提供了高度的模块化和可维护性。

它在程序设计中起到了重要的作用帮助我们更好地组织和管理数据。

理解复杂度概念

Complexity是衡量算法执行时间随输入规模增长而增加的度量。

它表示算法执行所需的操作次数或时间通常用大O符号O来表示。

时间复杂度描述了算法执行时间与输入规模之间的关系即算法的运行时间如何随着输入规模的增加而增长。

它不是指具体的执行时间而是一种相对的度量用于比较不同算法的效率。

常数时间复杂度

O(1)无论输入规模大小算法的执行时间都保持不变。

例如访问数组中的某个元素。

线性时间复杂度

O(n)算法的执行时间与输入规模成线性关系。

例如遍历一个数组。

对数时间复杂度

O(log

n)算法的执行时间与输入规模的对数成正比。

例如二分查找算法。

平方时间复杂度

O(n^2)算法的执行时间与输入规模的平方成正比。

例如嵌套循环遍历一个二维数组。

指数时间复杂度

O(2^n)算法的执行时间与输入规模的指数成正比。

例如穷举搜索算法。

O(1)

Complexity是衡量算法所需的额外空间随输入规模增长而增加的度量。

它表示算法执行期间所占用的内存空间通常也用大O符号O来表示。

空间复杂度描述了算法所需的额外空间与输入规模之间的关系即算法的空间使用如何随着输入规模的增加而增长。

常数空间复杂度

O(1)算法所需的额外空间不随输入规模的增加而增加空间使用保持不变。

线性空间复杂度

O(n)算法所需的额外空间与输入规模成线性关系。

例如需要存储一个数组或链表。

对数空间复杂度

O(log

n)算法所需的额外空间与输入规模的对数成正比。

例如递归算法的调用栈空间。

平方空间复杂度

O(n^2)算法所需的额外空间与输入规模的平方成正比。

例如二维数组存储。

需要注意的是时间复杂度和空间复杂度是相对的概念它们描述了算法执行时间和空间使用随输入规模变化的趋势并不是精确的执行时间和空间占用量。

在分析算法时我们通常关注最坏情况下的时间复杂度和空间复杂度以评估算法的效率和资源消耗。

度量时间复杂度的常用方法是基于函数调用次数的方法和基于语句执行次数基于算法复杂度分析的方法。

这种方法通过分析算法中函数或递归调用的次数来度量时间复杂度。

它通常适用于递归算法或包含循环结构的算法。

具体步骤如下

根据算法的逻辑确定算法中涉及的函数或递归调用。

分析每个函数或递归调用的执行次数与输入规模之间的关系。

根据函数调用次数的增长趋势得出算法的时间复杂度。

int

}可以观察到每次递归调用会导致两次更小规模的递归调用。

因此递归调用次数与输入规模呈指数关系时间复杂度可以表示为O(2^n)。

这种方法通过分析算法中各个语句的执行次数来度量时间复杂度。

它适用于没有函数调用或循环结构的简单算法。

具体步骤如下

根据算法的逻辑确定算法中涉及的各个语句。

分析每个语句的执行次数与输入规模之间的关系。

根据语句执行次数的增长趋势得出算法的时间复杂度。

int

}循环语句的执行次数与输入规模n成线性关系因此时间复杂度可以表示为O(n)。

3、基于算法复杂度分析该方法通过分析算法中执行次数最多的语句来度量时间复杂度。

通常情况下算法中执行次数最多的语句是循环语句。

因此我们可以通过分析循环语句的执行次数来确定算法的时间复杂度。

double

}循环语句的执行次数与输入规模n成线性关系因此时间复杂度可以表示为O(n)。

这三种方法都是常用的度量时间复杂度的方式选择哪种方法取决于算法的特点和分析的需求。

在实际应用中我们通常使用基于语句执行次数的方法来分析算法的时间复杂度因为它更直观和简单。

但对于一些复杂的递归算法基于函数调用次数的方法可能更适用。

内存是计算机中用于存储数据和指令的地方每个内存单元都有一个唯一的地址用于访问其中的数据。

通过地址我们可以直接读取和修改内存中的数据。

在C语言中指针是一种特殊的变量类型它存储了一个内存地址。

指针的存在使得我们可以通过间接访问内存地址来操作数据这给编程带来了很大的灵活性。

通过指针我们可以动态分配内存、传递参数、遍历数据结构等。

首先请看这么一张图

由这个图可以清晰的发现对于每一段的内存中的数据都有一个地址与之相对应也真是因为有地址的存在我们计算机中才可以轻易的去访问到其中数据拿一个数组来说数组在C语言中是顺序存储的因此如上图的数据直接用代码找到其数据以及地址的话可以这样写

#includestdio.h

array[10]ACDEQSFVCK;for(i0;i10;i){printf(The

Address

\n,array[i],array[i]);//%x可以换成%p都是十六进制表示只不过%p会把所有的位数显示出来}return

在代码示例中使用了数组和指针来展示数据在内存中的地址。

数组在C语言中是一段连续存储的数据通过下标可以访问到对应的元素。

通过取地址运算符我们可以获取数组元素的内存地址。

指针变量可以存储这些地址并通过解引用操作符*来访问或修改该地址处的值。

需要注意的是不同类型的数据在内存中占用的空间大小是不同的所以对应的地址也会有所差异。

例如char类型通常占用1字节而int类型通常占用4字节。

因此当将char数组转换为int数组时每个元素的地址会相应地增加4个字节。

指针的灵活性和强大功能使其成为C语言的重要特性但同时也需要小心使用因为错误的指针操作可能导致内存泄漏、段错误等问题。

在编写代码时应该注意正确地分配和释放内存并避免悬空指针和越界访问等问题。

编程预备

1、malloc函数是C语言中用于动态分配内存空间的函数它在堆中申请一块指定大小的连续内存空间并返回该内存空间的起始地址。

malloc函数的原型如下

void*

size);其中size_t是一个无符号整数类型在stdlib.h头文件中定义。

malloc函数接受一个参数size表示需要分配的内存空间的大小以字节为单位。

如果内存分配成功则返回指向分配内存的指针如果分配失败则返回空指针NULL。

在调用malloc函数之后应该检查返回的指针是否为NULL以判断内存分配是否成功。

如果malloc返回NULL则表示内存分配失败。

分配的内存空间在使用完毕后应该通过调用free函数来释放以便将内存返还给系统。

否则会导致内存泄漏问题。

free函数用于释放通过malloc函数分配的内存空间。

free函数的原型如下

void

ptr);其中ptr是一个指向待释放内存空间的指针。

调用free函数后该指针所指向的内存空间将被释放并可以被其他程序重新使用。

需要注意的是ptr必须是通过malloc、calloc或realloc函数返回的指针或者是空指针NULL。

如果ptr不满足这些条件调用free函数将导致未定义的行为。

只能释放通过malloc、calloc或realloc函数分配的内存空间否则会导致未定义的行为。

释放内存后应该将指针设置为NULL以避免成为野指针。

总结来说malloc和free是C语言中用于动态分配和释放内存空间的重要函数。

合理地使用这两个函数可以避免内存泄漏和野指针等问题提高程序的效率和稳定性。

下面是一个使用malloc和free函数的代码示例用于动态分配一个int类型的数组并对其进行赋值和释放

#include

上述代码中首先定义了一个整型变量n表示数组大小然后使用malloc函数动态分配了一个大小为n的int类型数组并将返回的指针赋值给指针变量arr。

在分配内存空间之后需要检查返回的指针是否为NULL以判断内存分配是否成功。

接着使用for循环对数组进行赋值并使用另一个for循环输出数组元素。

最后使用free函数释放arr指向的内存空间并将指针设置为NULL以避免成为野指针。