第02课数组
sizeof(a) // 返回a占用内存的字节数. 注意不是数组元素的个数.
voidmemcpy(voiddestin, void*source, unsigned n);
从存储区 source 复制 n 个字节到存储区 destin
// 清零
memset(a, 0, sizeof(a));
//极大值
memset(a, 0x7f, sizeof(a));
// -1
memset(a, -1, size of(a));
第05课字符串string
str.insert(2, 3, ‘A’)——在str下标为2的位置添加3个字符’A’
str.insert(2, “ABC”)——在str下标为2的位置添加字符串”ABC”
str.insert(2, “ABC”, 1)——在str下标为2的位置添加字符串”ABC”中1个字符
str.insert(2, “ABC”, 1, 1)——在str下标为2的位置添加字符串”ABC”中从位置1开始的1个字符
str.erase(2)——删除下标2 的位置开始,之后的全删除
str.erase(2,1)——删除下标2 的位置开始,之后的 1个删除
str.clear()——删除 str 所有
str.replace(2,4,”abcd”)——从下标2 的位置,替换 4个字节,为”abcd”
str.empty()——判空
str.find(‘A’)——查找 ‘A’
str.find(“ABC”)——查找 “ABC”
int n=s4.find(“ABC”); s4:ABCD -> n = 0
str.find(‘B’, 1)——从位置1 处,查找’B’
str.find(“ABC”, 1, 2)——从位置1 处,开始查找 ‘ABC’ 的前 2个字符reverse(str.begin(),str.end())——str的开始到结束字符反转
rfind函数:从尾部查找
str.rfind(‘A’)——查找 ‘A’
str.rfind(“ABC”)——查找 “ABC”
int n=s4.rfind(“ABC”); s4:AAAABCD -> n = 3
str.rfind(‘B’,1)——从位置1 处,向前查找’B’
str.rfind(“ABC”,1,2)——从位置1 处,开始向前查找 ‘ABC’ 的前 2个字符
find_last_of ()末尾查找, 从末尾处开始,向前查找是否包含有子串中任何一个字符
compare函数:完全相等返回0;完全不等返回小于0;部分相等返回大于0
第07课-动态数组
//b为向量,将b的0-2个元素赋值给向量a
a.assign(b.begin(), b.begin() + 3);
//a含有4个值为2的元素
a.assign(4, 2);
//返回a的最后一个元素
a.back();
//返回a的第一个元素
a.front();
//b为向量,将a中的元素和b中的元素整体交换
a.swap(b);
初始化二维vector
(看不懂)
// 初始化一个二维的matrix, 行M,列N,且值为0
vector
//等价于下面的
vector
for(int i=0;i
}
//等价于下面的
vector< vector
matrix.resize(M);//M行
for(int i=0;i
}
// 初始化一个二维的matrix, 行M,列N,且值自定义为data;
vector
学会用大括号初始化二维数组
vector
vector
matrix1.pushback({ 1, 2, 1 });//插入_
初始化一个 二维vector,行M,列不固定 vector
第09课 双向链表和list
![image.png](/uploads/projects/zijie-wap8c@ake7mb/39331fa545413598310c0a27072ea5ec.png)
双向循环链表
include
struct Node … {
int data; //数据域
Node prev; //指向前驱结点的指针
Node next; //指向后继结点的指针
};
struct Node … {
int data; //数据域
Node prev; //指向前驱结点的指针
Node next; //指向后继结点的指针
};
void init(Node *mylist)
… {
mylist = new Node;
(mylist)->data = 0;
(mylist)->prev = mylist;
(mylist)->next = *mylist;
}
// 插入元素操作
bool insert(Node *mylist, int i, int data)
… {
// 判断链表是否存在
if (!mylist)
…{
printf(“list not exist!\n”);
return false;
}
// 只能在位置1以及后面插入,所以i至少为1
if (i < 1)
…{
printf(“i is invalid!\n”);
return false;
}
// 找到i位置所在的前一个结点
Node *front = mylist; // 这里是让front与i不同步,始终指向j对应的前一个结点
for (int j = 1; j < i; j++) …{
front = front->next;
if (front == mylist)
…{
printf(“don’t find front!\n”);
return false;
}
}
// 创建一个空节点,存放要插入的新元素
Node *s = new Node;
s->data = data;
// 插入结点
s->prev = front;
s->next = front->next;
front->next->prev = s;
front->next = s;
return true;
}
// 删除元素操作
Node deleteNode(Node mylist, int i)
… {
// 找到i位置所在的前一个结点
Node front = mylist, s;
for (int j = 1; j < i; j++)
…{
front = front->next;
if (front->next == mylist)
…{
printf(“don’t find front!\n”);
return NULL;
}
}
s=front->next;
s->next->prev = front;
front->next = s->next;
return s;
}
// 头部插入元素操作
bool insert(Node mylist, int data)
… {
Node head;
Node *s;
head = mylist;
// 创建存放插入元素的结点
s = new Node;
s->data = data;
// 头结点后插入结点
s->prev = head;
s->next = head->next;
head->next->prev = s;
head->next = s;
return true;
}
// 遍历链表操作
void print(Node mylist)
… {
Node cur = mylist->next;
while (cur != mylist)
…{
printf(“<—>%d “, cur->data);
cur = cur->next;
}
printf(“\n”);
}
int main()
… {
Node *mylist;
// 初始化链表
init(&mylist);
for (int i = 0; i < 6; i++)
…{
insert(mylist, i+1);
}
print(mylist);
// 插入结点
insert(mylist, 1, 9);
print(mylist);
printf(“\n”);
// 删除结点
deleteNode(mylist, 2);
print(mylist);
printf(“\n”);
STL list
list 由双向链表(doubly linked list)实现而成,元素也存放在堆中,每个元素都是放在一块内存中,他的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变得非常没有效率,因此它没有提供 [] 操作符的重载。但是由于链表的特点,它可以很有效率的支持任意地方的插入和删除操作。
基本操作
u大小
o 容器大小:lst.size();
o 容器最大容量:lst.maxsize();
o 更改容器大小:lst.resize();
o 容器判空:lst.empty();
u添加函数
o 头部添加元素:lst.push_front(const T& x);
o 末尾添加元素:lst.push_back(const T& x);
o 任意位置插入一个元素:lst.insert(iterator it, const T& x);
list
lst.push_front(4);
// 末尾添加元素
lst.push_back(5);
// 任意位置插入一个元素
list
lst.insert(it, 2);
// 任意位置插入n个相同元素
lst.insert(lst.begin(), 3, 9);
// 插入另一个向量的[forst,last]间的数据
list
lst.insert(lst.begin(), lst2.begin(), ++lst2.begin());
u删除函数
o 头部删除元素:lst.pop_front();
o 末尾删除元素:lst.pop_back();
o 任意位置删除一个元素:lst.erase(iterator it);
o 清空所有元素:lst.clear();
u访问函数
o 访问第一个元素:lst.front();
o 访问最后一个元素:lst.back();
u其他函数
删除容器中相邻的重复元素:lst.unique();
算法
o 遍历元素
list
**for (it = lst.begin(); it != lst.end(); it++) cout << it << endl;
o 元素翻转reverse(lst.begin(), lst.end());
o 元素排序
#include
如果想从大到小排序,可以采用先排序后反转的方式
o 查找
find(lst.begin(), lst.end(), a);*
第10课 静态链表
struct Node{
int lft, rgt, data;
} s[100001];
//或者拆开结构体成多个数组, 减少代码长度
int lft[N], rgt[N], w[N];
o 链接 x 和 y(没考虑头和尾的特殊情况)
void link(int x, int y)
{
rgt[x] = y;
lft[y] = x;
}
u插入
//将下标为 y 的结点 插入到 x 的 左边
// x 始终为 head 时, 则是头插法 建立链表.
void inst(int x, int y) {
int lx = lft[x];
link(lx, y);
link(y, x);
}
u删除
void del(int x) {
int lx = lft[x], rx = rgt[x];
link(lx, rx);
}
第11课 栈
s.empty() 堆栈为空则返回真
s.pop() 移除栈顶元素
s.push() 在栈顶增加元素
s.size() 返回栈中元素数目
s.top() 返回栈顶元素