动态数组

数据结构与算法 评论

线性表的顺序存储:用一块连续的内存空间

插入新元素,空间不足

申请更大的内存空间,

旧的空间数据拷贝到新空间

释放旧空间的内存

新元素插入到新空间

构成元素:

容量，元素个数，int指针

1
2
3
4
5
typedef struct DYNAMICARRAY {
	int * pAddr;
	int size;	//元素个数
	int capacity;	//容量
}Dynamic_Array;

数组行为:

初始化，插入，根据位置删除，根据值删除，查找，打印元素，释放动态数组的内存

清空数组，获得动态数组容量，获得动态数据当前元素个数，根据位置获得某个位置元素



1.初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//初始化
Dynamic_Array * Init_Array() {
	//分配内存
	Dynamic_Array * myArray = (Dynamic_Array *)malloc(sizeof(Dynamic_Array));

	if (myArray == NULL)
	{
		return NULL;

	}
	myArray->size = 0;
	myArray->capacity = 20;
    //分配元素内存
	myArray->pAddr = (int *)malloc(myArray->capacity * sizeof(int));
	if (myArray->pAddr == NULL)
	{
		return NULL;
	}
	return myArray;
}

2.插入

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
//插入
void Push_Back_Array(Dynamic_Array* arr, int value) {
	if (arr == NULL) {
		return;
	}

	//判断空间是否足够
	if (arr->size == arr->capacity) {
		//第一步,申请一块更大的内存空间,新空间是旧空间的两倍
		int* newSpace = (int *)malloc(arr->capacity * sizeof(int) * 2);

		//第二步,拷贝数据到新空间
		memcpy(newSpace, arr->pAddr, arr->capacity * sizeof(int));
		//第三步,释放旧空间的内存
		free(arr->pAddr);
		//更新容量
		arr->capacity = arr->capacity * 2;
		arr->pAddr = newSpace;

	}
	
	//插入新元素
	arr->pAddr[arr->size] = value;
	arr->size++;


}

3.根据位置删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//根据位置删除
void Remove_Array(Dynamic_Array * arr, int pos) {
	if (arr == NULL) {
		return;
	}

	//判断位置是否有效
	if (pos < 0 || pos >= arr->size) {
		return;
	}
	//删除元素,将后面一位往前面移动一位
	for (int i = pos; i < arr->size - 1; i++)
	{
		arr->pAddr[i] = arr->pAddr[i + 1];

	}
	arr->size--;

}

4.根据值删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//根据值删除
void RemoveByValue(Dynamic_Array * arr, int value) {
	if (arr == NULL) {
		return;
	}
    //查找元素位置
	int pos = Find_Array(arr,value);
	//判断位置是否有效
	if (pos < 0 || pos >= arr->size) {
		return;
	}
    //根据位置删除元素
	Remove_Array(arr, pos);
}

5.查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//查找,找到返回位置,找不到返回-1
int Find_Array(Dynamic_Array * arr, int value) {

	if (arr == NULL) {
		return -1;
	}
	int pos = -1;
	for (int i = 0; i < arr->size; i++)
	{
		if (arr->pAddr[i] == value)
		{
			pos = i;

			break;
		}
	}
	return pos;

}

6.打印元素

1
2
3
4
5
6
7
8
9
10
void Print_Array(Dynamic_Array * arr) {

	if (arr == NULL) {
		return;
	}
	for (int i = 0; i < arr->size; i++) {
		printf("%d ", arr->pAddr[i]);
	}
	printf("\n");
}

7.释放动态数组的内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array * arr) {

	if (arr != NULL)
	{
		if (arr->pAddr != NULL)
		{
			free(arr->pAddr);
		}

		free(arr);
	}
	arr = NULL;
}

8.清空数组

1
2
3
4
5
6
7
8
//清空数组
void Clear_Array(Dynamic_Array * arr) {
	if (arr == NULL) {
		return;
	}

	arr->size = 0;
}

9.获得动态数组容量

1
2
3
4
5
6
7
8
//获得动态数组容量
int Capacity_Array(Dynamic_Array * arr) {
	if (arr == NULL) {
		return -1;
	}

	return arr->capacity;
}

10.获得动态数据当前元素个数

1
2
3
4
5
6
7
//获得动态数据当前元素个数
int Size_Array(Dynamic_Array * arr) {
	if (arr == NULL) {
		return -1;
	}
	return arr->size;
}

11.根据位置获得某个位置元素

1
2
3
4
5
6
7
//根据位置获得某个位置元素
int At_Array(Dynamic_Array * arr, int pos) {
	if (arr == NULL) {
		return -1;
	}
	return arr->pAddr[pos];
}

DynamicArray.h

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
#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//容量capacity
//元素个数size

//动态数组结构体
typedef struct DYNAMICARRAY {
	int * pAddr;
	int size;
	int capacity;
}Dynamic_Array;

//初始化
Dynamic_Array * Init_Array();

//插入
void Push_Back_Array(Dynamic_Array* arr,int value);

//根据位置删除
void Remove_Array(Dynamic_Array * arr,int pos);
//根据值删除
void RemoveByValue(Dynamic_Array * arr,int value);

//查找
int Find_Array(Dynamic_Array * arr,int value);

//打印
void Print_Array(Dynamic_Array * arr);

//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array * arr);

//清空数组
void Clear_Array(Dynamic_Array * arr);

//获得动态数组容量
int Capacity_Array(Dynamic_Array * arr);
//获得动态数据当前元素个数
int Size_Array(Dynamic_Array * arr);
//根据位置获得某个位置元素
int At_Array(Dynamic_Array * arr, int pos);

#endif

DynamicArray.c

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include"DynamicArray.h"


//初始化
Dynamic_Array * Init_Array() {

	Dynamic_Array * myArray = (Dynamic_Array *)malloc(sizeof(Dynamic_Array));

	if (myArray == NULL)
	{
		return NULL;

	}
	myArray->size = 0;
	myArray->capacity = 20;
	myArray->pAddr = (int *)malloc(myArray->capacity * sizeof(int));
	if (myArray->pAddr == NULL)
	{
		return NULL;
	}
	return myArray;
}

//插入
void Push_Back_Array(Dynamic_Array* arr, int value) {
	if (arr == NULL) {
		return;
	}

	//判断空间是否足够
	if (arr->size == arr->capacity) {
		//第一步,申请一块更大的内存空间,新空间是旧空间的两倍
		int* newSpace = (int *)malloc(arr->capacity * sizeof(int) * 2);

		//第二步,拷贝数据到新空间
		memcpy(newSpace, arr->pAddr, arr->capacity * sizeof(int));
		//第三步,释放旧空间的内存
		free(arr->pAddr);
		//更新容量
		arr->capacity = arr->capacity * 2;
		arr->pAddr = newSpace;

	}
	
	//插入新元素
	arr->pAddr[arr->size] = value;
	arr->size++;


}



//根据位置删除
void Remove_Array(Dynamic_Array * arr, int pos) {
	if (arr == NULL) {
		return;
	}

	//判断位置是否有效
	if (pos < 0 || pos >= arr->size) {
		return;
	}
	//删除元素
	for (int i = pos; i < arr->size - 1; i++)
	{
		arr->pAddr[i] = arr->pAddr[i + 1];

	}
	arr->size--;

}
//根据值删除
void RemoveByValue(Dynamic_Array * arr, int value) {
	if (arr == NULL) {
		return;
	}
	int pos = Find_Array(arr,value);
	
	if (pos < 0 || pos >= arr->size) {
		return;
	}
	Remove_Array(arr, pos);
}
//查找
int Find_Array(Dynamic_Array * arr, int value) {

	if (arr == NULL) {
		return -1;
	}
	int pos = -1;
	for (int i = 0; i < arr->size; i++)
	{
		if (arr->pAddr[i] == value)
		{
			pos = i;

			break;
		}
	}
	return pos;

}
//打印
void Print_Array(Dynamic_Array * arr) {

	if (arr == NULL) {
		return;
	}
	for (int i = 0; i < arr->size; i++) {
		printf("%d ", arr->pAddr[i]);
	}
	printf("\n");
}
//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array * arr) {

	if (arr != NULL)
	{
		if (arr->pAddr != NULL)
		{
			free(arr->pAddr);
		}

		free(arr);
	}
	arr = NULL;
}


//清空数组
void Clear_Array(Dynamic_Array * arr) {
	if (arr == NULL) {
		return;
	}

	arr->size = 0;
}

//获得动态数组容量
int Capacity_Array(Dynamic_Array * arr) {
	if (arr == NULL) {
		return -1;
	}

	return arr->capacity;
}
//获得动态数据当前元素个数
int Size_Array(Dynamic_Array * arr) {
	if (arr == NULL) {
		return -1;
	}
	return arr->size;
}
//根据位置获得某个位置元素
int At_Array(Dynamic_Array * arr, int pos) {
	if (arr == NULL) {
		return -1;
	}
	return arr->pAddr[pos];
}

main.c

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
// 动态数组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include<stdio.h>
#include"DynamicArray.h"

void test() {

	//初始化
	Dynamic_Array *myArr = Init_Array();

	if (myArr == NULL)
	{
		return;
	}

	printf("数组容量:%d\n", Capacity_Array(myArr));
	printf("数组元素长度:%d\n", Size_Array(myArr));

	//插入元素
	for (int i = 0; i < 30; i++)
	{
		Push_Back_Array(myArr, i);
	}
	//打印
	Print_Array(myArr);

	//获取容量
	printf("数组容量:%d\n", Capacity_Array(myArr));
	//获取元素个数
	printf("数组元素长度:%d\n", Size_Array(myArr));
	
	//查找元素
	int pos = Find_Array(myArr, 20);
	printf("查找20的元素:pos=%d value=%d\n", pos, myArr->pAddr[pos]);
	
	//根据位置获得某个位置元素
	printf("元素:%d\n", At_Array(myArr,pos));

	//根据位置删除
	Remove_Array(myArr, pos);
	Print_Array(myArr);


	//根据值删除
	RemoveByValue(myArr, 23);
	Print_Array(myArr);

	


	//清空数组
	Clear_Array(myArr);
	printf("数组容量:%d\n", Capacity_Array(myArr));
	printf("数组元素长度:%d\n", Size_Array(myArr));
	//释放数组
	FreeSpace_Array(myArr);
}

int main()
{
	test();
	return 0;
}

YanChen

Personal profile