C语言_动态内存分配

发表于2021-09-02更新于2025-11-04阅读次数

malloc

  1. 返回类型为void *
  2. 参数为(unsigned int size)，表示总共要开辟的字节数
1
2
3
4
5
int* p = nullptr;
int n = 0;
scanf_s("%d", &n);
//p = (int*)malloc(n);//这是错误的参数，因为malloc的参数要写要开辟的字节数，而不是以变量数为单位。
p = (int*)malloc(sizeof(int) * n);

calloc

  1. 返回类型为*void
  2. 参数为(unsigned int count, unsigned int size)，count表示变量数，size表示单个变量(类型)的字节数。
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<stdlib.h>
#include<string.h>//包含memset函数
typedef unsigned int size_t;
void* My_Calloc(size_t count, size_t size)
{
    void* p = malloc(count * size);
    if(nullptr != p)
    {
        memset(p, 0, count * size);//把p指向的内存空间中的数据赋值为0x00
    }
    return p;
}

free

  1. 不管是malloc还是calloc开辟的空间都是用free(p)来释放的。

  2. free并不是把p释放掉了，而是把p指向堆区的空间从引用状态转换成未引用状态。

  3. 空间的释放只能释放一次，不能释放多次

  4. free(p)释放后，要给p赋值nullptr，防止指针失效带来的麻烦。

    1
    2
    3
    4
    int* p = (int*)My_Calloc(10, sizeof(int));
    free(p);
    p = nullptr;
    return 0;

realloc

realloc扩充或收缩之前分配的内存块（重新分配内存块）

1
void *realloc(void *ptr, size_t new_size);
  1. 参数中的ptr指向需要重新分配的内存区域的地址，new_size为新的字节数
  2. 返回值：成功时，返回指向新分配内存的指针，返回的指针必须用free或realloc归还。；失败时，返回空指针。原指针ptr保持有效，并需要通过free或realloc归还。

重新分配给定的内存区域。它必须是之前为malloc/calloc/realloc分配的，并且仍未被free或realloc的调用所释放。否则，结果未定义。

1
2
3
4
5
6
7
8
9
int size=5;//分配空间的变量数为5
int new_size=10;//最终要分配空间的变量数为10
int* p = (int*)malloc(sizeof(int)*size);//开辟size个int空间
for(int i=0;i<size;++i)
{
    p[i]=1;
}
p = (int*)realloc(p, sizeof(int) * new_size);//增加到new_size个int空间，即由原来5个扩充到10个
p = (int*)realloc(p, sizeof(int) * 2);//减少到2个int空间，即由原来5个收缩到2个

基础数据结构_C语言实现

发表于2021-09-02更新于2025-11-04阅读次数

内容

  1. 数据结构的基础概念和时间空间复杂度
  2. 线性表：顺序表、链表
    1. 顺序表（定长的、扩容的）
    2. 单链表（带头结点的、不带头结点的）
      1. 需要动手实践，大量的面试题
  3. 栈（顺序栈、链栈）
    1. 用两个栈实现一个队列
  4. 队列（顺序队、链队）
    1. 用两个队实现一个栈
  5. 串（字符数组）
    1. API实现（strcpy strcat srtcmp strlen）
    2. 字符串的查找（BF、KMP算法）
  6. 双向链表、循环链表、双向循环链表
  7. 八大排序算法
    1. 冒泡排序
    2. 二路归并排序
    3. 插入排序
    4. 希尔排序
    5. 堆排序
    6. 基数排序（桶排序）
    7. 快速排序
    8. 选择排序

概念

数据结构

  1. 集合
  2. 线性（现实生活中的排队）
  3. 树型（部门架构、族谱）
  4. 图型（交通网络、六度分割理论、网络拓扑）

时间复杂度

执行语句与问题规模之间的函数

  1. O(1): 没有循环，或者有循环但是循环的退出条件和问题规模之间没有关系；
  2. O(n): 有循环，循环的退出条件与问题规模之间存在关系，并且控制循环的变量以++或者–的方式执行
  3. O(n^2): 有循环，嵌套一层。
  4. O(logn): 有循环，循环的退出条件与问题规模之间存在关系，并且控制循环的变量每次*2或/2的方式执行。

空间复杂度

算法所需的额外存储空间（除了函数本身计算申请的内存外）与问题规模之间的关系。

1
2
3
4
5
6
7
void Show(int arr[], int len)
{
    for(int i = 0;i<len;++i)
    {
        printf("%d ",arr[i]);
    }
}

此处，函数参数中的int arr[]和int len不是额外存储空间。而是for循环。

线性表

  • 唯一的头（此处的头指的是第一个有效节点），唯一的尾。
  • 除了头，剩余的节点都有前驱。除了尾，剩余的节点都有后继。

定长顺序表

相当于一个特殊使用的数组。

但存放数据是按顺序来存的，不能随意位置存放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//sqlist.h
#pragma once	//防止头文件重复
typedef int ElemType;
typedef struct Sqlist
{
    ElemType arr[10];//节点
    int length;//当前有效数据节点的个数
}Sqlist,*PSqlist;
//初始化
void Init_sqlist(PSqlist plist);
//增删改查
//按位置插入（头插、尾插）
bool Insert_Pos(PSqlist plist, int pos, int val);
//删除：按值删、按位置删（删除这个值第一次出现的位置）
bool Del_val(PSqlist plist, int val);
bool Del_pos(PSqlist plist, int pos);
//查找值为val的节点
Sqlist* FindNode(PSqlist plist, int val);
//判空 判满
bool IsEmpty(PSqlist plist);
bool IsFull(PSqlist plist);
//清空
void Clear(PSqlist plist);
//销毁
void Destory(PSplist plist);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"sqlist.h"
#include<string.h>
//初始化
void Init_sqlist(PSqlist plist)
{
    assert(plist!=NULL);
    memset(plist->arr,0,sizeof(arr));
    plist->length = 0;
}
//增删改查
//按位置插入（头插、尾插）
bool Insert_Pos(PSqlist plist, int pos, int val)
{
    assert(plist!=NULL);
    if( pos<0 || pos > plist->length || IsFull(plist) )return false;
    
    //移动数据
    for(int i = plist->length-1; i>=pos ;i--)
    {
        //不会越界，因为如果length为10时，不能进入此循环
        plist->arr[i+1] = plist->arr[i];
    }
    //插空
    plist->arr[pos] = val;
    //长度加1
    plist->length++;
    return true;
}
//头插
bool Push_Front(PSqlist plist, int val)
{
    assert(plist!=NULL);
    return Insert_Pos(plist, 0, val);
}
//尾插
bool Push_Back(PSqlist plist, int val)
{
    assert(plist!=NULL);
    return Insert_Pos(plist, plist->length, val);
}
//删除：（删除这个值第一次出现的位置）
//按值删
bool Del_val(PSqlist plist, int val)
{
    assert(plist!=NULL);
    return Del_pos(plist, FindPos_withVal(plist, val) );
}
//按位置删
bool Del_pos(PSqlist plist, int pos)
{
    assert(plist!=NULL);
    if( pos<0 || pos > plist->length || IsEmpty(plist) )return false;
    //长度减1
    plist->length--;
    //移动数据（相当于清除了arr[pos]）
    for(int i = pos; i < plist->length-1 ;++i)//i < plist->length-1  容易出错
    {
        plist->arr[i] = plist->arr[i+1];
    }
    return true;
}
//头删
bool Pop_Front(PSqlist plist)
{
    assert(plist!=NULL);
    Del_pos(plist, 0);
}
//尾删
bool Pop_Back(PSqlist plist)
{
    assert(plist!=NULL);
    Del_pos(plist, plist->length);
}
//查找值为val的节点
int FindPos_withVal(PSqlist plist, int val)
{
    assert(plist!=NULL);
    int pos = -1;
    int i = 0;
    while(i< plist->length && val!=plist->arr[i])
    {
        ++i;
    }
    if(i!=length)//则while是因为val==plist->arr[i]跳出的。
    {
        pos = i;
    }
    return pos;
}
//判空 判满
bool IsEmpty(PSqlist plist)
{
    return plist->length == 0;
}
bool IsFull(PSqlist plist)
{
    return plist->length == sizeof(plist->arr)/sizeof(plist->arr[0]);
}
//清空
void Clear(PSqlist plist)
{
    assert(plist!=NULL);
    plist->length = 0;
}
//销毁
void Destory(PSplist plist)
{
    assert(plist!=NULL);
    Clear(plist);
}

不定长顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//sqlist.h
#pragma once	//防止头文件重复
typedef int ElemType;
#define INIT_SIZE 10
typedef struct DSqlist
{
    ElemType* ar;//基地址
    int cursize;//当前有效数据节点的个数
    int capacity;//当前最长容量
}DSqlist,*PDSqlist;
//初始化
void Init_sqlist(PDSqlist plist);
//增删改查
//按位置插入（头插、尾插）
bool Insert_Pos(PDSqlist plist, int pos, int val);
//头插
bool Push_Front(PDSqlist plist, int val);
//尾插
bool Push_Back(PDSqlist plist, int val);
//删除：按值删、按位置删（删除这个值第一次出现的位置）
bool Del_val(PDSqlist plist, int val);
bool Del_pos(PDSqlist plist, int pos);
//头删
bool Pop_Front(PDSqlist plist);
//尾删
bool Pop_Back(PDSqlist plist);
//查找值为val的节点
int FindPos_withVal(PDSqlist plist, int val);
//判空 判满
bool IsEmpty(PDSqlist plist);
bool IsFull(PDSqlist plist);
//清空
void Clear(PDSqlist plist);
//销毁
void Destory(PDSplist plist);
void Inc(PDsqlist plist);
1
2
3
4
void Inc(PDsqlist plist)
{
    
}

单链表

image-20210902180653639

image-20210902181055988

  1. 第一种大厂笔试/面试中常用，主要考察对边界条件检测的掌握力；
    • 不带头结点的逆置和带头结点的逆置难度不一样。
  2. 第二种实际编程中常用，方便好用；
  3. 第三种的循环无意义，因为功能和头指针差不多。
  4. 第四种是加了一个尾指针，使尾插也变O(1)，但代价是需要对尾指针进行密切维护。

面试

image-20210904191948363