单链表

首元结点：是指链表中存储第一个数据元素的结点

头结点：是在首元结点之前附设的一个结点，其指针域指向首元结点，头结点的数据域可以不存储任何信息

头指针：是指向链表中第一个结点的指针，若有头结点，则指向头结点；若没有头结点，则指向首元结点

指针

**&**是取地址

*****是取值

指针间接赋值：

  1. 两个变量：普通变量、指针变量
  2. 建立关系 指针变量=&普通变量
  3. 通过 *运算符赋值 *指针变量=值
1
2
3
4
5
6
int a = 0;
int* b = &a;	//&a代表的数据类型是int*
cout<<b<<endl;  //把int*看作一个数据类型，而b就是代表&a,也就是地址
cout<<a<<endl;
cout<<&a<<endl;
cout<<*b<<endl;

image-20231123195007882

const修饰的指针变量

修饰普通变量

C语言

在C语言中，const修饰的全局变量保存在常量区，既不能通过变量名去修改，也不能通过地址去修改。

const修饰的局部变量，存在栈区，虽然不能通过const修饰的变量去修改栈区的内容，但是可以通过地址去改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

const int c = 1;
int main() {
	const int a = 123;
	printf("a修改前:%d\n", a);
	int* b = &a;
	*b = 456;
	printf("a修改后:%d\n", a);
	
    printf("c修改前:%d\n", c);
	int *d = &c;
	*d = 4;
	printf("c修改后:%d\n", c);
	return 0;
}

image-20231123201519812、

在这里c修改后的并没有输出来，

C++

在C++中，const修饰的全局变量与C语言中的情况是一样的，既不能通过变量名去修改，也不能通过地址去修改。const修饰的局部变量既不能通过变量名修改局部变量的值，也不能通过地址来改变const修饰的局部变量的值。

修饰指针类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int main() {
	int a = 10;
	int b = 20;
	const int* c = &a;
	printf("a的地址:%p\n", &a);//000000000062FE14
	printf("b的地址:%p\n", &b);//000000000062FE10
	printf("c修改前:%p\n", c);//000000000062FE14 = a
	c = &b;//无问题
	printf("c修改后:%p\n", c);//000000000062FE10 = b

	return 0;
}

image-20231123202413669

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int main() {
	int a = 10;
	int b = 20;
	const int* c = &a;

	c = &b;//ok：可以修改指针变量的值
	//*c = 99;//err：不可以修改指针对应的内存空间的值

	printf("%d\n", *c);
	return 0;
}

const 修饰指针类型 可以修改指针变量的值，不可以修改指针指向内存空间的值。

修饰指针变量

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int main() {
	int a = 10;
	int b = 20;
	int* const c = &a;
	//c = &b;//err
	*c = 200;//ok
	
	printf("%d\n", a);//200
	return 0;
}

const 修饰指针变量 可以修改指针指向内存空间的值，不可以修改指针变量的值 

1
2
int* const c;
const int* c;

->和.的区别

-> 用于访问指针指向的结构体成员，而 . 用于直接访问结构体的成员。

  1. ->（箭头操作符）：
    • 用于访问结构体或联合体的成员，通过指向结构体或联合体的指针。
    • 通常用于指针变量，例如 ptr->member 表示访问指针 ptr 指向的结构体或联合体的成员。
    • 比如，ptr->member 等同于 (*ptr).member。
  2. .（点操作符）：
    • 用于访问结构体或联合体的成员，通过结构体或联合体的实例。
    • 通常用于直接访问结构体或联合体的成员，例如 structInstance.member 表示访问结构体 structInstance 的成员。
    • 只能用于结构体或联合体的实例，不能用于指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

struct Point {
    int x;
    int y;
};

int main() {
    struct Point p1 = {10, 20};
    struct Point* ptr = &p1;

    // 使用箭头操作符访问指针指向的结构体成员
    printf("Using ->: %d\n", ptr->x);

    // 使用点操作符访问结构体成员
    printf("Using .: %d\n", p1.x);

    return 0;
}

C++ STL

map & unordered_map

1.首先是定义

1
2
#include<map>
map<int,string>mp;//中间的是数据类型

2.常用的函数以及操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//插入操作,直接类似数组赋值
mp[0] = "abc";
//查找,如果找到会返回该元素的迭代器,否则it指向mp.end(),这里mp.end()并不指向元素，空的
auto it = mp.find(0);
//map的开始结束迭代器
auto it = mp.begin();指向第一个元素
auto it = mp.end();指向最后一个元素的后一位
//判空
mp.empty();空则返回true
//返回元素个数
int len = mp.size();
//insert,因为元素键在map中是唯一的，所以插入操作首先检查给定键是否已存在于map中，如果键已存在于map中，则它不会插入map中
mp.insert(pair<int,char>(4,'d'));
//earse删除一个
mp.earse(1);
//清空clear
mp.clear();
//判断键的个数，map低层是红黑树，所以count只能是0或1
int c = mp.count(1);

说一下unordered_map 和map不同它是无序的。内部实现机理不同，map是共黑树，unordered_map是哈希表，unordered_map的查找时间复杂度可达到O(1)

有顺序要求时用map高效一些，而对于查找问题，unordered_map更高效

大小写转换

1.string类用algorithm的方法

transform(str.begin(),str.end(),str.begin(),::tolower);

记得::tolower前面有::,　而且是::tolower，不是::tolower(),

类似的toupper

2.string手写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string str;


void mytolower(string& s){
    int len=s.size();
    for(int i=0;i<len;i++){
        if(s[i]>='A'&&s[i]<='Z'){
            s[i]+=32;//+32转换为小写
            //s[i]=s[i]-'A'+'a';
        }
    }
}
void mytoupper(string& s){
    int len=s.size();
    for(int i=0;i<len;i++){
        if(s[i]>='a'&&s[i]<='z'){
            s[i]-=32;//+32转换为小写
            //s[i]=s[i]-'a'+'A';
        }
    }
}

3.char数组

tolower()和toupper()