【数据结构】前置基础-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】前置基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、指针

1.1 指针是什么

指针是什么？
指针理解的 2 个要点：
1）指针是内存中一个最小单元的编号，也就是地址
2）平时口语中说的指针，通常指的是指针变量，是用来存放内存地址的变量
总结：指针就是地址，口语中说的指针通常指的是指针变量

那我们就可以这样理解：【数据结构】前置基础,考研408之数据结构,数据结构

1.2 指针和指针类型

#include<stdio.h>
int main()
{
	char* pc;
	int* pa;
	double* pd;
	printf("%d\n",sizeof(pc));    // 4
	printf("%d\n", sizeof(pa));   // 4
	printf("%d\n", sizeof(pd));   // 4
	return 0;
}

指针作用1：指针类型决定了在解引用时能访问几个字节（指针的权限）

 
#include<stdio.h>
int main()
{
	int a = 0x11223344;
	int* pa = &a;
	*pa = 0;
	char* pc = &a;
	*pc = 0;
	// 指针类型决定了在解引用的时候以此能访问几个字节（指针的权限）
	// int*     --> 4
	// char*    --> 1
	// double*  --> 8
	return 0;
}

指针作用2：指针类型决定了//指针作用2:指针类型决定了指针向前或者向后走一步，走多大距离（单位是字节）

1.3 野指针

概念：野指针就是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）
成因：

#include<stdio.h>
int main()
{
	/*int a;
	printf("%d\n", a);*/
	//未初始化
	//int* p;  //野指针
	//*p = 20;
	//越界访问
	int arr[10] = { 0 };
	int* p = arr;
	int i = 0;
	for (i = 0; i <= 10; i++)
	{
		*p = i;
		p++;
	}
 
	return 0;
}

如何规避野指针？如下：

指针初始化

小心指针越界

指针指向空间释放即使置NULL

避免返回局部变量的地址 5. 指针使用之前检查有效性

1.4 指针运算

#include<stdio.h>
int main()
{
	int arr[10] = { 0 };
	int* p = arr;
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < sz; i++)
	{
		*(p + i) = i + 1;
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d ", *(p + i));  // 1 2 3 4 5 6 7 8 9 10
	}
	return 0;
}

1.5 指针和数组

#include<stdio.h>
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int* p = arr;
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	/*for (i = 0; i < 10; i++)
	{
		printf("%p==%p\n", p + i, &arr[i]);
	}*/
	for (i = 0; i < 10; i++)
	{
		printf("%d ", p[i]);    // 1 2 3 4 5 6 7 8 9 10
	}
	return 0;
}

1.6 二级指针

指针变量也是变量，是变量就有地址，那指针变量的地址存放在哪里？这就是二级指针
【数据结构】前置基础,考研408之数据结构,数据结构

2.结构体

2.1 结构体的声明

结构体是一些值的集合，这些值称为成员变量。结构体的每个成员可以是不同类型的变量。

struct tag  //tag是标签名，是可以根据需求改的
{
   member-list;  //成员列表
}variable-list;  //全局变量

例如描述一个学生：

typedef struct Stu
{
	char name[20];//名字
	int age;//年龄
	char sex[5];//性别
	char id[20];//学号
}Stu;//分号不能丢

结构的成员可以是标量、数组、指针，甚至是其他结构体。

2.2 结构体变量的定义和初始化

有了结构体类型，那如何定义变量，其实很简单。

struct Point
{
	int x;
	int y;
}p1; //声明类型的同时定义变量p1
 
struct Point p2; //定义结构体变量p2
 
//初始化：定义变量的同时赋初值。
struct Point p3 = { x , y };
 
struct Stu        //类型声明
{
	char name[15];//名字
	int age;      //年龄
};
struct Stu s = { "zhangsan", 20 };//初始化
 
struct Node
{
	int data;
	struct Point p;
	struct Node* next;
}n1 = { 10, {4,5}, NULL }; //结构体嵌套初始化
struct Node n2 = { 20, {5, 6}, NULL };//结构体嵌套初始化

2.3 结构体成员的访问

2.3.1 结构体变量访问成员

结构变量的成员是通过点操作符（.）访问的。点操作符接受两个操作数

struct Stu
{
	char name[20];
	int age;
};
 
struct Stu s;

struct S s;
strcpy(s.name, "zhangsan");//使用.访问name成员
s.age = 20;//使用.访问age成员

【数据结构】前置基础,考研408之数据结构,数据结构

2.3.2 结构体指针访问成员

struct Stu
{
	char name[20];
	int age;
};
void print(struct Stu* ps)
{
	printf("name = %s   age = %d\n", (*ps).name, (*ps).age);
	//使用结构体指针访问指向对象的成员
	printf("name = %s   age = %d\n", ps->name, ps->age);
}
int main()
{
	struct Stu s = { "zhangsan", 20 };
	print(&s);//结构体地址传参
	return 0;
}

2.4 结构体内存对齐

我们已经掌握了结构体的基本使用了。
现在我们深入讨论一个问题：计算结构体的大小。
这也是一个特别热门的考点：结构体内存对齐
先看一下下面的代码：

#include <stdio.h>
 
struct S1
{
	char c1;//1
	int i;//4
	char c2;//1
};
 
int main()
{
	struct S1 s;
	printf("%d\n", sizeof(s));
	return 0;
}

【数据结构】前置基础,考研408之数据结构,数据结构
对这个结果是不是感到很疑惑，结果不应该是（1+4+1=6）嘛，为什么答案是12？

要想搞清楚怎么计算结构体大小的，首先得掌握结构体的对齐规则：

第一个成员在与结构体变量偏移量为 0 的地址处。

其他成员变量要对齐到某个数字（对齐数）的整数倍的地址处。
对齐数 = 编译器默认的一个对齐数与该成员大小的较小值。
VS中默认的值为8（Linux系统下是其本身大小）

结构体总大小为最大对齐数（每个成员变量都有一个对齐数）的整数倍。

如果嵌套了结构体的情况，嵌套的结构体对齐到自己的最大对齐数的整数倍处，结构体的整体大小就是所有最大对齐数（含嵌套结构体的对齐数）的整数倍。

那么为什么存在内存对齐呢?

大部分的参考资料都是如是说的：

平台原因 ( 移植原因 ) ：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。

性能原因：数据结构( 尤其是栈 ) 应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。
总体来说：结构体的内存对齐是拿空间来换取时间的做法。

现在回过头再来分析分析之前的代码：
【数据结构】前置基础,考研408之数据结构,数据结构

当然了，以上的偏移量只是学习到的理论依据，那该怎么验证呢？

offsetof - 宏
计算结构体成员相对于起始位置的偏移量的

我们先来看看offsetof是怎么用的：
【数据结构】前置基础,考研408之数据结构,数据结构

#include <stdio.h>
#include <stddef.h>
 
struct S1
{
	char c1;//1
	int i;//4
	char c2;//1
};
 
int main()
{
	printf("%d\n", sizeof(struct S1));
	printf("%u\n", offsetof(struct S1, c1));
	printf("%u\n", offsetof(struct S1, i));
	printf("%u\n", offsetof(struct S1, c2));
	return 0;
}

【数据结构】前置基础,考研408之数据结构,数据结构

2.5 结构体传参

#include <stdio.h>
 
struct S
{
	int data[1000];
	int num;
};
struct S s = { {1,2,3,4}, 1000 };
 
//结构体传参
void print1(struct S s)
{
	printf("%d\n", s.num);
}
 
//结构体地址传参
void print2(struct S* ps)
{
	printf("%d\n", ps->num);
}
 
int main()
{
	print1(s);  //传结构体
	print2(&s); //传地址
	return 0;
}

上面的 print1 和 print2 函数哪个好些？
答案是：首选 print2 函数。

原因：
1.函数传参的时候，参数是需要压栈，会有时间和空间上的系统开销。
2.如果传递一个结构体对象的时候，结构体过大，参数压栈的的系统开销比较大，所以会导致性能的下降

结论：结构体传参的时候，要传结构体的地址。

3.引用

3.1 引用概念

引用不是新定义一个变量，而是给已存在变量取了一个别名，编译器不会为引用变量开辟内存空间，它和它引用的变量共用同一块内存空间。
类型& 引用变量名(对象名) = 引用实体；看代码：

int main()
{
	//把b叫做a的引用，也叫做b是a的别名
	int a = 10;
	int& b = a;
	return 0;
}

引用的实质就是在取别名，既然引用是在取别名，那我对别名进行修改，就相当于对自己本身进行修改

3.2 引用特性

引用具有三大特性：
1）引用在定义时必须初始化
2）一个变量可以有多个引用
3）引用一旦引用一个实体，再不能引用其它实体

3.3 引用的使用场景

3.3.1 做参数

就比如说我现在要写一个Swap函数，以前是用指针写的：

//指针版
void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

而现在，我们就可以巧用引用来完成Swap函数

//引用版
void Swap(int& x, int& y)
{
	int tmp = x;
	x = y; 
	y = tmp;
}
//支持函数重载
void Swap(double& x, double& y)
{
	double tmp = x;
	x = y;
	y = tmp;
}

现在，引用就可以做我的形参，就不用再像以前C语言那样总是取地址&，并且在调用的时候也会非常方便，因为有函数重载的加持。

引用做参数的好处如下：
1）输出型参数
2）减少拷贝、提高效率

3.3.2 做返回值

传值返回

int Count()
{
	int n = 0;
	n++;
	return n;
}
int main()
{
	int ret = Count();
	return 0;
}

在传值返回的过程中会产生一个临时变量（类型是int），如果这个临时变量小它会用寄存器替代，如果大就不会用寄存器替代。
具体返回的过程是先把函数的n拷贝给临时变量，再把临时变量拷贝给ret。

传引用返回

int& Count()
{
	int n = 0;
	n++;
	return n;
}
int main()
{
	int ret = Count();
	return 0;
}

这里加上了引用&后，中间也会产生一个临时变量，只是这个临时变量的类型是int&。我们把这个临时变量假定为tmp，那么此时tmp就是n的别名，再把tmp赋值给ret。这个过程不就是直接把n赋给ret吗。这里区分于传值返回的核心就在于传引用的返回就是n的别名。

此外传值返回比传引用返回效率更低，我们偏向传引用

3.4 引用和指针的区别

引用和指针的不同点：
1）引用概念上定义一个变量的别名，指针存储一个变量地址
2）引用在定义时必须初始化，指针没有要求
3）引用在初始化时引用一个实体后，就不能再引用其他实体，而指针可以在任何时候指向任何一个同类型实体
4）没有NULL引用，但有NULL指针
5）在sizeof中含义不同：引用结果为引用类型的大小，但指针始终是地址空间所占字节个数(32位平台下占4个字节)
6）引用自加即引用的实体增加1，指针自加即指针向后偏移一个类型的大小
7）有多级指针，但是没有多级引用
8）访问实体方式不同，指针需要显式解引用，引用编译器自己处理
9）引用比指针使用起来相对更安全

4.动态内存管理

4.1 malloc

void* malloc (size_t size);

这个函数向内存申请一块连续可用的空间，并返回指向这块空间的指针。

如果开辟成功，则返回一个指向开辟好空间的指针。
如果开辟失败，则返回一个NULL指针，因此malloc的返回值一定要做检查。
返回值的类型是 void* ，所以malloc函数并不知道开辟空间的类型，具体在使用的时候使用者自己来决定。
如果参数 size 为0，malloc的行为是标准是未定义的，取决于编译器。
注意：使用malloc函数要引用头文件#include<stdlib.h>

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
int main()
{
	//开辟10个整型的空间
	int* p = (int*)malloc(40);
	if (NULL == p)
	{
		printf("%s\n", strerror(errno));
		return 0;
	}
	// 使用……
 
	//释放
	return 0;
}

4.2 free

C语言提供了另外一个函数free，专门是用来做动态内存的释放和回收的，函数原型如下：

void free (void* ptr);

free函数用来释放动态开辟的内存。
如果参数 ptr 指向的空间不是动态开辟的，那free函数的行为是未定义的。
如果参数 ptr 是NULL指针，则函数什么事都不做。
malloc和free都声明在 stdlib.h 头文件中。

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
int main()
{
	//开辟10个整型的空间
	int* p = (int*)malloc(40);
	if (NULL == p)
	{
		printf("%s\n", strerror(errno));
		return 0;
	}
	// 使用……
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		*(p + i) = i;
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", p[i]);
	}
	//释放
	free(p);
	p = NULL;
	return 0;
}

4.3 realloc

realloc函数的出现让动态内存管理更加灵活。有时会我们发现过去申请的空间太小了，有时候我们又会觉得申请的空间过大了，那为了合理的时候内存，我们一定会对内存的大小做灵活的调整。那 realloc 函数就可以做到对动态开辟内存大小的调整。
函数原型如下：

void* realloc (void* ptr, size_t size);

ptr 是要调整的内存地址
size 是调整之后新大小
返回值为调整之后的内存起始位置。
这个函数调整原内存空间大小的基础上，还会将原来内存中的数据移动到新的空间。

realloc在调整内存空间的是存在两种情况：
情况1：原有空间之后有足够大的空间，当是情况1的时候，要扩展内存就直接原有内存之后直接追加空间，原来空间的数据不发生变化。
情况2：原有空间之后没有足够大的空间，当是情况2 的时候，原有54空间之后没有足够多的空间时，扩展的方法是：在堆空间上另找一个合适大小的连续空间来使用。这样函数返回的是一个新的内存地址。
【数据结构】前置基础,考研408之数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-828216.html