菜单微网站,网页布局名称,网页制作学什么软件,快速排名上传统的数组#xff1a;
int arr[10]#xff1b; 传统的数组有以下的缺点#xff1a;
1#xff09;长度不可修改
2)内存分配
局部数组:把数组定在函数内#xff0c; 数组便是局部变量#xff0c;故会被分配在栈上 但栈的大小是有限制的 #xff0c;故其在内存中不能超…传统的数组
int arr[10] 传统的数组有以下的缺点
1长度不可修改
2)内存分配
局部数组:把数组定在函数内 数组便是局部变量故会被分配在栈上 但栈的大小是有限制的 故其在内存中不能超过1MB。 如果数组太大可能会导致栈溢出。
int arr[1000000]; // 如果超出了内存限制可能会失败
全局数组: 如果将数组声明为全局变量数组会分配在数据段或 BSS 段中不会受到栈大小的限制。但是OJ在线评测系统通常对内存有严格的限制。如果数组过大可能会超出内存限制导致超时或内存不足的错误。
3数组作为参数不方便。
在c语言中将数组作为参数实际上是传递数组的首地址即传递的是指针而不是整个数组。
故被调用函数只能得到数组的首地址而无法得到数组的长度。
在做oj时要求用纯c解题怎么解决上面的问题
》
1一开始申请一个大的数组如果局部数组的长度无法满足要求就将数组定义为全局数组。若全局数组的占用内存超过了题目的内存限制。就是算法有问题。
我们也可以使用动态内存分配malloc/realloc来模拟动态数组并手动管理内存。
2在传参的时候传两个参数数组的地址 和长度。
// 分配初始内存
int* arr (int*)malloc(sizeof(int) * initial_size); //动态扩展数组
arr (int*)realloc(arr, sizeof(int) * new_size);
//传递数组的指针和长度
void func(int* arr, int size) {} 但若用c/c,更好用的办法就是使用c提供的vector即动态数组。
vector的使用
都说 传统的静态数组 的大小在编译时就已经固定无法在程序运行时修改。 而动态数组可以对于这句话通俗一点讲就是说
我们可以在写代码时不必定义其大小即使定义了我们也可以在后续的代码中使用各种方法插入或删除其元素因为其在运行时会根据我们的代码操作自动调整其内存的 。
vector是c提供的STL。他有一些优点
1 会自动处理内存分配和释放 免了 C 语言中常见的内存管理错误。
2 通过 vector::size() 可以轻松获取数组的长度。
3提供了丰富的成员函数
我们主要学习vector的增删查改。
引入
#includevector
增
增操作包括初始化和插入
1.初始化
vectorint vec;
vectordouble vec;
注vector不是类型vector type才是类型故下面的vec1和vec2不是同一种类型。
当然了也可以自定义一个类,从而可以定义vectorMyType类型的变量
struct MyType{
int val1;
double val2;
}
vectorMyTypevec;
另外vectorint也可以作为一种类型放在vector的中
构成vectorvectorint,这种类型便是代表动态数组的动态数组即二维数组。
vectorvectorint
在机试中对于二维数组推荐使用动态数组的静态数组即下面这种写法以应用于实现图算法中的邻接表。
vectorint arr[10];
2.插入
插入数据使用push_back: 往动态数组的尾部插入
我们知道往顺序表中插入元素代价很大而这种往数组末尾插入元素的操作非常高效但若如果我们硬要往任意位置插入元素该怎么办
》可以使用迭代器我们稍后解答
int a;
while(scanf(%d,%a)!EOF){vec.pushback(a);//往vec尾部插入a
}
查找
1、根据数组下标访问对应元素
//定义的这个数组下标从0到4
vectorint vec{1,23,4};
int i0;
printf(“vec[i]%d\n,vec[i]);
2.遍历整个vectorfor,迭代器
vector本身携带了长度的信息可以使用vec.size()获取长度
从而可以使用for循环遍历数组
int sizevec.size();
for(int i0;isize;i){
}
除了用普通for循环还可以使用迭代器
其提供了一种通用方法可以访问不同类型的数据结构我们可以将迭代器理解为一个高级的指针
迭代器的类型是动态数组类型iterator
例vecotorintiterator
对于一个数组{1,3,5,7,9}
我们可以使用begin来获取第一个元素的位置使用end来获取尾后的位置当我们对迭代器做自增操作他便会后移他的用法如下
vectorint vec{1,3,5,7,9};
vectorint:: iterator it;
for(itvec.begin();it!vec.end();it){
printf(it%\n,*it);
}
现在解决上面硬要往任意位置插入元素的问题
因为迭代器可以访问到数组中任意一个位置所以可以利用它对任意位置插入删除元素。insert和erase
因为insert和erase会修改动态数组的结构所以插入或修改完成后it的指向无意义。所以之后要对迭代器重新赋值。
但是这种插入操作最好避免使用而使用push_back进行插入
vectorint:: iterator it;
itvec.begin();
vec.insert(it,2); //往it所在位置插入元素2
//注意迭代器要重新赋值
itit3;//it3相当于3次只能在vector中使用
3.通过元素信息查找其位置
删
1.删除一个元素
我们可以使用pop_back()删除最后一个位置的元素。
vec.pop_back();
同样的如果我们硬要删除一个位置的元素可以使用迭代器配合erase函数。
vecor.erase(it);
2.把vector清空
vector.clear()
list的使用
前面我们讲过即使使用迭代器配合insert和erase函数能够在任意位置对数组进行增加和删除操作但是还是不推荐那样做。因为如前面所言顺序表的线性结构进行这样的操作真的很低效。所以如果我们硬要做就不能使用传统的线性结构而得使用链式结构。
c标准库为我们提供了一个链式结构的顺序表叫list。
list的底层原理是一个双向链表。
引入
#includelist
增 insert
前面我们在vector中对于迭代器使用了it3表示迭代器it了3次但是因为链表中不支持随机访问故不支持加法运算符故只能靠自增3次来实现
listint ls{1,3,4,5,6};
//获取迭代器
listint::iterator itls.begin();
it;
it;
it;
ls.insert(it, 10);
删
it.erase();
查
遍历list
for(itls.begin();it!ls.end();it){
printf(it%d\n,*it);
} vector和list的选择
若一个题目中要求使用一个线性的数据结构我们首选vector,
但如果你发现这个vector在使用的过程中存在着大量的对中间元素进插入和删除的操作就改用list。
补充解惑
1.为什么往线性表中的任意元素插入或删除元素很低效
》
线性表如 vector的底层是一个连续的内存块数组。在往数组中间插入或删除元素时需要移动其他的元素。
因此 插入和删除最坏情况下的事件复杂度都是为o(n)。
2.list的增删改查都是使用迭代器完成的吗 是的list 的增删改查主要是通过迭代器来完成的。
由于 list 是基于链表实现的 因此没有下标访问的方式只能通过迭代器进行增删改查。 迭代器提供了一个统一的接口来遍历、修改 list 中的元素增加了代码的灵活性和可移植性。
ls.insert(it, 10);
ls.erase(it);
std::cout *it ;
