数据结构是随着计算机科学的发展而建立起来的围绕非数值计算问题的一门科学,是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合。
通过精心选择的数据结构可以带来更高的运行或存储效率。
首先建立问题的数据模型:
数据的组成结构,数据的关联方式,以及实施相应运算后,数据组成结构的完整性。
完整性:
即是指不因对数据运算而改变数据模型的性质。设计相应的算法,需要保证结构的完整性前提下,以相同规律进行的。
数据结构可以分成两个层次
算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令。它代表着用系统的方法描述解决问题的策略机制。
在 C/C++ 中,算法有以下一些特征:
算法评价:
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
#include
//冒泡排序
void Bubble_Sort(int arr[], int size) //升序
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - 1 - i; j++)
{
if (arr[j]>arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
选择排序(Selection sort)是一种简单直观的排序算法。
它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。
以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
//选择排序
void Select_Sort(int arr[], int size) //升序
{
for (int i = size - 1; i > 0; i--)
{
for (int j = i - 1; j >= 0; --j)
{
if (arr[i] < arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。
但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列(已序)。
工作原理是:将要查找的元素一分为两半然后一半一半的查找。
//二分查找
int Binary_Search(int arr[], int len, int findVal)
{
int left = 0, right = len - 1;
int mid; //中位数
while (left <= right)
{
//第一步:确定中位数
mid = left + ((right - left) >> 1); //(right - left) >> 1 等价于 (right - left)/2
//第二步:和目标值比较
if (findVal == arr[mid])
return mid;
else if (findVal > arr[mid])
left = mid + 1;
else if (findVal < arr[mid])
right = mid - 1;
}
return -1; //找不到,返回不存在的下标值
}