数据结构字符串的基本算法

人们在设计程序时通常会注意两个重要问题. 一种是如何将要处理的数据存储到计算机内存中，即数据表示形式. 第二是设计算法来处理这些数据，即数据处理. 数据表示的本质是数据结构设计，而数据处理的本质是算法设计. PASCAL的父亲，著名的瑞士计算机科学家Niklaus Wirth教授曾提出: 算法+数据结构=程序. 可以看出，数据结构和算法是程序的两个重要组成部分. 数据结构是指数据的逻辑结构和存储方法，算法是指数据的操作方法. 一旦C ++的标准模板STL设计了各种“轮子”，我们仍然需要了解轮子的结构，以便我们能够适应本地条件并选择适当的数据结构和算法来解决问题. 根据具体情况.

根据存储方法，线性表可以分为顺序表和链表. 线性表的基本操作是指线性表的操作. 常见的操作包括: 查找长度，清空表，遍历，搜索，修改，删除，插入，排序等. 此外，还有复杂的操作，例如合并，求逆，求平均和删除重复元素.

序列表对应于数组，并且STL中的向量也以这种方式实现. 序列表的特征是元素按逻辑顺序顺序存储在连续的存储空间中，因此它是随机访问结构. 操作时间复杂度: 查询，修改，查找长度O（1），插入，删除，遍历O（n）.

链表包括单链表，循环链表，双链表和静态链表. 链表使用动态存储分配方法，该方法在需要时应用，在不需要时释放. 操作时间复杂度: 插入，删除O（1），查询，修改，遍历和查找长度O（n）. 就空间性能而言，序列表的存储空间是静态分配的，需要预先确定其大小. 如果更换，很容易造成浪费. 适用于确定存储规模且不经常更改或更改不大的场合；动态链表是动态分配的空间，不容易溢出. 适用于长度变化很大的场合. 但是，由于需要存储指针，因此空间利用率很低.

C ++ STL有许多与线性表相关的容器，例如向量，列表和其他顺序容器.

 //使用容器，包括头文件

#include 
使用std :: vector;
//定义矢量对象
vector  ivec; //定义矢量对象ivec
vector  ivec1（ivec）; //定义矢量对象ivec1并使用ivec初始化
vector  ivec2（n，i）; //定义向量对象ivec2，包括n个值为i的元素
vector  ivec3（n）; //定义一个包含n个值为0的向量
vector  :: iterator it; //定义迭代器，模拟指针
vector > vivec; //定义一个二维矢量，在“>”
之间必须有一个空格
 公共向量矢量接口可以在公共向量矢量接口 list的操作类似于vector. 有关详细信息，请参阅列表的通用界面


堆栈是一个线性表，仅限于在尾部进行插入和删除操作. 插入和删除操作称为堆栈的顶部，另一端称为底部. 因此，堆栈的操作基​​于后进先出的原理. 堆栈的基本操作包括: 清空堆栈，推入和推出堆栈，获取堆栈的顶部元素以及判断为空. 由于堆栈是一个受限制的线性表，因此可以通过顺序表和链表来实现.
队列也是一个受限制的线性表. 它只允许插入一端（称为后部）. 在另一端的删除称为前，在队列末尾的插入称为入队，而在另一头的删除称为出队. 基本操作包括: 排空团队，进入团队c语言链表冒泡排序，离开团队，带领团队负责人和判断团队为空. 也可以通过顺序列表或链接列表来实现.
字符串，也称为字符串，是字符的有限序列. 由字符串中任何连续字符组成的字符串称为子字符串，原始字符串称为主字符串. 前缀子串是指从第一个字符到特定字符的子串，后缀子串是从某个字符到最后一个字符的子串. 字符串的基本操作包括: 赋值，字符串串联，长度，子字符串，字符串大小比较，插入，修改，删除等. 字符串模式匹配算法包括朴素模式匹配算法，KMP算法和BM算法等，需要学习.
此外，还有多维数组和广义表，树（二叉树，B树，红黑树等）和图，此处将不对其进行详细说明，并将在以下内容中进行概述. 未来.
两种常见的算法是搜索和排序. 搜索是计算机数据处理中经常使用的重要应用程序. 当您需要重复搜索和制定海量数据中的记录时，搜索效率成为系统性能的关键. 搜索算法分为静态搜索和动态搜索，其中静态搜索包括: 顺序搜索，二进制搜索和块搜索；动态搜索包括: 二进制排序树和平衡二进制树. 还有最快的理论搜索技术-哈希搜索. 此处仅提供二进制搜索代码. 排序的目的是为了方便搜索，例如电话号码搜索，书籍分类，字典搜索等. 常见的排序算法包括: 插入排序，气泡排序，堆排序，选择排序和合并排序. 它们的性能比较如下图所示.

二进制搜索也称为半搜索. 它要求要搜索的序列按键码排序. 其基本思想是，首先确定要检查的记录的间隔，然后逐渐缩小范围，直到找到或找不到记录为止. 二进制搜索要求线性表将序列表用作存储结构，尤其需要注意边界控制的问题.  C ++算法的描述如下:
int Search_Bin（int a []，int n，int target）// a [0]未使用，a [1]〜a [n]存储数据
{
int low = 1;
int high = n;
while（low <= high）
{
int mid =低+（高-低）/ 2; //防止溢出
if（a [mid] == target）返回mid;
否则if（a [mid]> target）high = mid-1;
else low = mid + 1;
}
返回0；

}
直接插入分类的原理可以类似于在玩纸牌时将手中的纸牌分类的过程，也就是说，不断将新元素插入有序序列的适当位置. 这是一种稳定的排序算法，特别适合要排序的序列基本排序的情况.  C ++算法的描述如下:
void InsertSort（int r []，int n）// r [0]未使用，n是元素数
{
for（int i = 2; i <= n; i ++）//从2〜n循环，对n-1次行程进行排序
{
if（r [i] 
{
r [0] = r [i];
r [i] = r [i-1];
}
for（int j = i-2; r [j]> r [0]; j--）//检查并移回
r [j + 1] = r [j];
r [j + 1] = r [0];
}
}
气泡排序的方法是在要排序的元素中选择两个相邻的元素进行比较. 交换逆序直到没有逆序为止. 为了减少记录的重复比较，这是气泡排序的一种改进版本，它是一种稳定的排序算法.
//普通版
void BubbleSort（int r []，int n）
{
for（int i = 1; i 
{
for（int j = 1; j <= n-i; j ++）//内循环，每次行程减少一个比较元素
{
if（r [j]> r [j + 1]）//相邻元素的比较，交换
{
r [0] = r [j];
r [j] = r [j + 1];
r [j + 1] = r [0];
}
}
}
}
//改进版本
void BubbleSort（int r []，int n）
{
int pos = n;

while（pos！= 0）
{
int bound = pos; //比较边界，下一个顺序，不比较顺序
int pos = 0;
for（int i = 1; i 
{
if（r [i]> r [i + 1]）
{
pos = i; //记录取消订单的位置
r [0] = r [i]; r [i] = r [i + 1]; r [i + 1] = r [0];
}
}
}
}
快速排序是一种用于冒泡排序的改进算法. 由于冒泡排序是在相邻位置进行的，因此需要多次移动才能到达目的地，并且快速排序元素的比较和移动是从两端到中间. 在此过程中，移动的距离越来越远，因此效率更高.
int Partion（int r []，int first，int end）
{
int i = first;
int j = end;
int axis = r [i];
while（i 
{
while（i  pivot）j--; //向右扫描，如果不符合条件，则向左移动
r [i] = r [j];
while（i 
r [j] = r [i];
}
r [i] = pivot;
}
void Qsort（int r []，int i，int j）
{
if（i 
{
intivotloc = Partion（r，i，j）; //每行排列一个元素
Qsort（r，i，pivotloc-1）;
Qsort（r，pivotloc + 1，j）;
}
}
2.5简单选择排序
选择和排序的基本方法是在每次要排序的序列中选择键码最小的元素，并将该序列排序后添加到排序的序列中，直到对所有记录进行排序为止.
void SelectSort（int r []，int n）
{
for（int i = 1; i 
{
int index = i;
for（int j = i + 1; j <= n; j ++）
{
if（r [j] 
{
index = j; //记录最小元素的索引
}
}
if（index！= i）//如果r [i]是最小的无序交换
{
r [0] = r [i]; r [i] = r [index]; r [index] = r [0];
}
}
}
堆分类通过构造大根桩或小根桩的数据结构，在简单选择分类中记录上一次行程的比较结果，从而减少了比较次数并提高了整个分类的效率. 这里以大根堆为例，给出了堆排序算法的C ++描述.
void Sift（int r []，int k，int m）//使用数组记录堆，k是要调整的节点，可以通过调整来调整堆的性质
{
int i = k，j = 2 * i; //初始化，找到k的左子级
while（j <= m）
{
if（j 
if（r [i]> r [j]）break; //如果满足条件，则退出
其他
{
r [0] = r [i];
r [i] = r [j];
r [j] = r [0];
i = j; j = 2 * i; //比较节点向下移动
}
}
}
void HeapSort（int r []，int n）
{
for（int i = n / 2; i> = 0; i--）//构建堆
Sift（r，i，n）;
for（int i = n; i> 1; i-）
{
r [0] = r [1]; r [1] = r [i]; r [i] = r [0]; //输出堆的顶部元素
Sift（r，1，i-1）; //调整以满足堆的属性
}
}
合并排序的基本思想是: 将两个或多个有序序列合并为一个有序序列.
//合并两个有序序列
void Merge（int r []，int r1 []，int s，int m，int t）
{
int i = s，j = m + 1，k = s;
while（i <= m && j <= t）
{
if（r [i] 
r1 [k ++] = r [i ++];
其他
r1 [k ++] = r [j ++];
}
while（i <= m）r1 [k ++] = r [i ++];
while（j <= t）r1 [k ++] = t [j ++];
}
//递归合并
void MergeSort（int r []c语言链表冒泡排序，int r1 []，int s，int t）
{
if（s == t）r1 [s] = r [s];
其他
{
int m =（s + t）/ 2;
MergeSort（r，r1，s，m）;
MergeSort（r，r1，m + 1，t）;
Merge（r1，r，s，m，t）;
}
}
到目前为止，有很多排序算法. 在常用算法中，就时间性能而言，在希尔排序，堆排序，快速排序和合并排序算法中，快速排序被认为是最快的，并且当要排序的元素数量相对较大时，可以进行合并排序比堆排序快. 就稳定性而言，直接插入排序，气泡排序和合并排序是稳定的排序算法，而简单选择排序，快速排序和堆排序则不稳定. 当元素很少（n <50）时，可以选择直接插入排序或简单选择排序；当元素的初始状态基本有序时，选择直接插入排序或冒泡排序；当元素很多时，选择快速排序，堆排序或合并，特定分析.
					

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-238192-1.html