1 .一般数据结构人们在编程时，通常关注两个重要问题。 一种是如何将处理的数据保存在计算机存储器中，即数据表示。 二是设计算法来操作这些数据，也就是数据处理。 数据表示的本质是数据结构设计，而数据处理的本质是算法设计。 PASCAL之父、瑞士著名计算机科学家沃斯(Niklaus Wirth )教授提出了算法的数据结构=程序。 可见数据结构和算法是程序的两个重要组成部分。 数据结构是数据的逻辑结构和存储方法，算法是对数据的操作方式。 尽快c的标准模板类STL已经设计出了各种“车轮”，我们还是需要了解车轮的结构，这样我们才能因地制宜，根据具体场景选择合适的数据结构和算法来解决问题。 1.1线性表线性表根据存储方式可分为顺序表和链表。 线性表的基本运算是指对线性表的操作，常见的有求长、放空表、遍历、查找、修改、删除、插入、排序等。 此外，还有复杂的运算，如合并、反演线性表、求中值、删除重复元素等。 顺序表与数组相对应，在STL中矢量也是这样安装的。 顺序表的特征是，要素按照逻辑顺序被依次容纳在连续的存储区域中，所以是随机存取结构。 操作时间复杂度：查询、修改、求解长度o(1)、插入、删除、遍历o ) ) n。 链表包括单链表、循环链表、双向链表、静态链表等。 链表采用动态存储分配方式，必要时申请，不必要时释放。 操作时间复杂度：插入、删除o(1)，查询、修改、遍历、长度o ) n。 在容量方面，顺序表的存储空间是静态分配的，需要事先决定其大小，更改的话容易造成浪费。 适用于具有固定存储规模、不经常更改或不大更改的情况。 动态链表是动态分配空间的，不易溢出。 适用于长度变化较大的情况。 但是，由于保存指针，因此空间利用率低。 的STL具有许多与路线图相关的容器，例如向量(vector，列表)。 pre name='code' class='cpp'//要使用容器，请单击头文件# includevectorusingstd 33603360 vector； //定义向量对象vectorint ivec； //定义向量对象ivecvectorintivec1(ivec )； 定义//向量对象ivec1，定义用ivec初始化vectorintivec2(n，I )的//向量对象ivec2，其中包含n个值为I的元素vectorintivec3(n )； 定义包含n个//0值的向量vector int :迭代器it； //定义迭代器，模拟指针vectorvectorint vivec； //定义二维向量，“之间需要空间。 span style=' white-space : pre '/span vector通用接口为： a target=_ blank href=' http://www.cplusplus.com/referenent 具体包括： a target=_ blank href=' http://www.cplusplus.com/reference/list/'列表公用接口/a 2.2堆栈、队列和堆栈因此，堆栈的操作是按照后进先出的原则进行的。 栈的基本运算包括获取空栈、栈、外栈、栈顶元素和空判决。 堆栈是受限的线性表，所以可以通过顺序表和链表来实现。 队列也是受限制的线性表。 那个只能插入到一端。 队伍结束(rear )； 删除另一端称为头(front )，插入队末尾称为入队，删除头称为出队。 基本运算包括空队部署、入伍、入伍、带队、判定队空。 这也可以通过顺序表或链表来实现。 也称为字符串，是由字符组成的有限序列。 由字符串中任意连续字符组成的字符串称为子字符串，而原始字符串称为主字符串。 前缀子串是由第一个字符到某个字符组成的子串，而后缀子串是由某个字符到最后一个字符组成的子串。
的基本操作是代入、连接、求长度、求子字符串、比较字符串大小、插入、修改、删除等。 串的模式匹配算法包括朴素模式匹配算法、KMP算法、BM算法等，值得研究。
另外，还有多维数组和广义表、树(二叉树、B-tree、红黑树等)和图，这里不再详细说明，今后进行总结。 2 .常用的算法有检索和排序两种，其中检索是计算机数据处理中常用的重要APP序列，需要在大量数据中重复检索并进行记录时，检索效率是系统性能的关键。 搜索算法分为静态搜索和动态搜索，静态搜索包括顺序搜索、二叉树搜索和块搜索。 动态检索包括二叉树和平衡二叉树。 另外，还有理论上最快的检索技术——散列检索。 这里只显示两点检索的代码。 排序的目的是便于搜索，例如电话号码搜索、书籍目录组织和词典搜索。 常见的排序算法包括插入排序、气泡排序、堆栈排序、选择排序和合并排序。 请参阅下图比较这些性能。 2.1二分查找二分查找，又称折半查找，要求待检序列按键码有序。 其基本思想是，首先确定调查记录的区间，在找到或找不到该记录之前，逐步缩小范围。 半检索请求
线性表用顺序表作为存储结构，它特别需要注意的是边界控制的问题。该算法C++描述如下： int Search_俊秀的书本(int a[], int n, int target)//a[0]不用，a[1]~a[n]存储数据{ int low = 1; int high = n; while(low<=high) { int mid = low+(high-low)/2; //防止溢出 if(a[mid]==target) return mid; else if(a[mid]>target) high=mid-1; else low=mid+1; } return 0;} 2.2 直接插入排序 直接插入排序的原理可类比打牌时整理手中牌的过程，即不断地将新来的元素插到有序序列的合适位置。它是一种稳定的排序算法，特别适合于待排序序列基本有序的情况。该算法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[i-1]) { 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]; }} 2.3 冒泡排序 冒泡排序的方法是在待排序的元素中选择两个相邻的元素进行比较，反序则交换，直至没有反序为止。为了减少记录的重复比较，这里给出改进版的起泡排序，它是一种稳定的排序算法。 //普通版void BubbleSort(int r[],int n){ for(int i=1;i<n;i++) //n-1 趟 { 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<bound;i++) { if(r[i]>r[i+1]) { pos=i; //记录打破有序的位置 r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0]; } } }} 2.4 快速排序 快速排序是起泡排序的改进算法，由于起泡排序是在相邻位置进行的，故要比较移动多次才能到达目的地，而快排元素的比较和移动是从两端向中间进行的，移动的距离比较远，更靠近目的地，因此效率较高。 int Partion(int r[],int first,int end){ int i=first; int j=end; int pivot=r[i]; while(i<j) { while(i<j && r[j]>pivot) j--; //右侧扫描，不符合条件左移 r[i]=r[j]; while(i<j && r[i]<pivot) i++; //左侧扫描，不符合条件右移 r[j]=r[i]; } r[i]=pivot;}void Qsort(int r[],int i,int j){ if(i<j) { int pivotloc = 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<n;i++) //n-1趟排序 { int index=i; for(int j=i+1;j<=n;j++) { if(r[j]<r[index]) { index=j; //记录最小元素的索引 } } if(index!=i) //若r[i]即为最小，无序交换 { r[0]=r[i];r[i]=r[index];r[index]=r[0]; } }} 2.6 堆排序 堆排序通过构造大根堆或者小根堆的数据结构来记录简单选择排序中前一趟的比较结果，从而减少比较次数，提高整个排序的效率。这里以大根堆为例，给出堆排序算法的C++描述。 void Sift(int r[],int k,int m) //用数组记录堆，k是要调整的节点，通过调整使得满足堆的性质{ int i=k,j=2*i;//初始化，找到k的左孩子 while(j<=m) { if(j<m && r[j]<r[j+1]) j++;//寻找左右孩子中较大的一个 if(r[i]>r[j]) break;//满足条件，跳出 else { 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); //调整使满足堆的性质 }} 2.7 归并排序 归并排序的基本思想是：将两个或两个以上的有序序列归并成一个有序序列. //归并两个有序序列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]<r[j]) r1[k++]=r[i++]; else r1[k++]=r[j++]; } while(i<=m) r1[k++]=r[i++]; while(j<=t) r1[k++]=t[j++];}//递归归并void MergeSort(int r[],int r1[],int s,int t){ if(s==t) r1[s]=r[s]; else { int m=(s+t)/2; MergeSort(r,r1,s,m); MergeSort(r,r1,m+1,t); Merge(r1,r,s,m,t); }} 2.8 小结 迄今为止，排序算法还有很多。在常见的算法中，就时间性能而言，在希尔排序、堆排序、快速排序和归并排序算法中，快速排序被认为是最快的一种，而在待排序元素个数比较多的情况下，归并排序较堆排序更快。就稳定性而言，直接插入排序、冒泡排序和归并排序是稳定的排序算法，而简单选择排序、快排和堆排是不稳定的。元素较少时（n<50)，可选择直接插入排序或简单选择排序；元素初始状态基本有序时，选择直接插入排序或冒泡排序；元素较多时，选择快排、堆排或者归并，具体情况具体分析。