1.1 什么是数据结构

数据(data)是对客观事物符号表示，在计算机中是指所有能输入的计算机并被计算机程序处理的数据总称。

数据元素(data element)是数据的基本单位，在计算机中通常做为一个整体进行处理。

数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。

数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。

数据类型(data type)是和数据结构密切关系的一个概念，在计算机语言中，每个变量、常量或者表达式都有一个所属的数据类型。

抽象数据类型(abstract data type ADT)是指一个数据模型以及定义在该模型上的一组操作，抽象数据类型的定义仅取决于它的一组逻辑性，与其在计算机内部如何表示以及实现无关。

1.2 什么是算法

算法是对特定问题求解的一种描述，它是指令的有限序列，其每一条指令表示一个或多个操作，算法还有以下特性：

Ø 有穷性

一个算法必须总是在执行有限步骤后的结果，而且每一步都可以在有限时间内完成。

Ø 确定性

算法中每一条指令都有确切的含义，读者理解时不会产生二义性，在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。

Ø 可行性

一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算来实现的。

Ø 输入

一个算法有零个或者多个输入，这些输入取自与某个特定对象的集合。

Ø 输出

一个算法有一个或多个输出，这些输出是和输入有某些特定关系的量。

1.3 排序

1.3.1 冒泡排序

冒泡排序首先将一个记录的关键字和第二个记录的关键字进行比较，如果为逆序(elem[1] > elem[2])，则两个记录交换之，然后比较第二个记录和第三个记录的关键字，以此类推，直到第n-1个记录和第n个记录的关键字进行过比较为止。

上述过程称作第一次冒泡排序，其结果是将关键字最大的记录被安排到最后一个记录的位置上。然后进行第二次冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字第二大记录被安置到第n-1位置上。直到将所有记录都完成冒泡排序为止。

1.3.2 选择排序

选择排序是每一次在n – I + 1(i=1,2,…n)个记录中选取关键字，最小的记录作为有序序列中第i个记录。

通过n-i次关键字间的比较，从n-i+1个记录中选取出关键字最小的记录，并 和第i(1<=i<=n)个记录交换之。

1.4 查找

1.4.1 顺序查找

顺序查找的过程为：从表的最后一个记录开始，逐个进行记录的关键字和给定值比较，如果某个记录的关键字与给定值相等，则查找成功，反之则表明表中没有所查找记录，查找失败。

1.4.2 二分查找

在一个已经排序的顺序表中查找，可以使用二分查找来实现。

二分查找的过程是：先确定待查记录所在的范围(区间)，然后逐步缩小查找范围，直到找到或者找不到该记录为止。

假设指针low和high分别指示待查找的范围下届和上届，指针mid指示区间的中间值，即 mid=(low + high) / 2。

版权声明：转载文章来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益，请与我们联系删除或授权事宜。