数组
实现和特点
随机访问和连续空间.
数组array 和 向量容器 vector 都属于顺序表.有一段连续的内存空间，并且起始地址不变,与数组类似： 优点：便于随机访问，时间复杂度为O（1）， 缺点：因为内存空间是连续的，所以在进入插入和删除操作时，会造成内存块的拷贝，时间复杂度为O（n）。
我们在谈论数据结构的连续性的时候, 连续空间指的是虚拟内存空间还是物理内存空间?
虚拟内存空间. 因为程序或者进程在计算机中都有独立的内存空间.
元素位序是从1开始的，数组中的元素下标是从0开始的。
int A[MAX_SIZE];
int n;
「数组 array」是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的「索引 index」。图 4-1 展示了数组的主要概念和存储方式。
数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。
空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。 支持随机访问：数组允许在 时间内访问任何元素。 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。 连续空间存储是一把双刃剑，其存在以下局限性。
插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。
数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。
随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。 查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。
存储在栈上和堆上的数组都被存储在连续内存空间内，数据操作效率基本一致。然而，栈和堆具有各自的特点，从而导致以下不同点。
分配和释放效率：栈是一块较小的内存，分配由编译器自动完成；而堆内存相对更大，可以在代码中动态分配，更容易碎片化。因此，堆上的分配和释放操作通常比栈上的慢。 大小限制：栈内存相对较小，堆的大小一般受限于可用内存。因此堆更加适合存储大型数组。 灵活性：栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定。
数组的操作
int insert(SqList &L, int p, int e){
//插入环境判断 位置有效，空间未满
if(p < 0 || p > L.length || L.length == maxSize) return 0;
// 后元素右移
for(int i = L.length - 1; i>=p; --i)
L.data[i+1]=L.data[i];
// 插入操作 长度加1
L.data[p] = e;
++(L.length);
return 1;
}
int delete(Sqlist &L, int p, int &e){
int i;
if(p < 0 || p > L.length - 1)
return 0;
// 操作目标元素返回
e = L.data[p];
// 后元素左移
for(i = p; i< L.length - 1; ++i)
L.data[i]=L.data[i+1];
--(L.length);
return 1;
}
void reverse(int a[],int left,int right){
int temp;
for(int i = left,j = right;i < right + 1 && i<j;++i,--j){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
//循环左移通过逆置算法实现
void moveP(int a[],int n, int p){
reverse(a,0,p-1);
reverse(a,p,n-1);
reverse(a,0,n-1);
}
数组的应用
矩阵
-
二维数组是一维数组的一维数组，一般采用顺序存储
-
广义表：表元素可以是原子或者广义表的线型表拓展结构。
-
二维数 组行优先列优先的下标问题
-
对称矩阵、三角矩阵、对角矩阵的物理表示和确定元素位置问题
稀疏矩阵：
三元组表示法
int trimat[maxterms+1][3];
trimat[k][0]; 表示原矩阵中元素按照行优先的顺序的第k个非零元素值
float trimat[maxterms+1][3] 的行号 (int)trimat[k][1];
伪地址表示法
两元组表示，值和伪地址：元素在矩阵中按照行优先或列优先存储的相对位置
邻接表表示法
每一行的非零元素连成一个链表，链表结点中有两个分量，一个是元素值，一个是列号。
十字链表表示法
行和列都用带头结点的邻接表表示，头结点数组不存储任何信息
链表结点有5个分量，行分量、列分量、数据域分量、同列下一个结点、同行下一个结点指针。
十字链表结点有5个分量，行数、列数、非零元素个数、行头结点数组指针、列头结点数组指针。
typedef struct OLNode {
int row,col;
struct OLNode *right,*down;
float val;
} OLNode;
typedef struct CrossList {
OLNode *rhead,*chead;
int m,n,k;
}
//T
void trsmat(int A[][maxSize],int B[][maxSize],int m,int n){
for(int i = 0;i <m;++i)
for(int j = 0;j < n ; ++ j)
B[j][i] = A[i][j];
}
字符串
//定长顺序分配表示
typedef struct {
char str[maxSize+1]; //\0 位置
int length;
}String;
//动态分配存储
typedef struct {
char *ch;
int length;
}String;
//需要malloc一个长度为length，类型为char型的连续存储空间
//赋值法 不能直接等于
int strassign(Str &str,char * ch){
if (str.ch) free(str.ch);
int len = 0;
char *c = ch;
while(*c){
++len;
++c;
}
if(len = 0){
str.ch = NULL;
str.length = 0;
return 1;
}
else{
str.ch = (char*)malloc((len+1) * sizeof(char));
if(str.ch == NULL) return 0;
else{
c = ch;
for(int i = 0; i<=len; ++i,++c) str.ch[i] = *c;
str.length = len;
return 1;
}
}
}
while(*p != '\0'){
...
++p;
}
KMP
Knuth-Morris-Pratt算法
在一个字符串中查找是否包含目标的匹配字符串。
其主要思想是每趟比较过程让子串先后滑动一个合适的位置。
当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。
BM
精确字符串匹配算法