avatar

数据结构之连续存储

预备知识—指针

指针:

  • 指针就是地址
  • 指针变量是存放地址的变量
  • 指针的本质是一个操作受限的非负整数

数据结构

线性结构

把所有节点用一根直线串起来

  • 连续存储 【数组】
  • 离散存储 【链表】

线性结构常用两种应用: 栈,队列

数组与指针

数组的增删改查:

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
# include<malloc.h>
# include<stdio.h>
# include<stdlib.h>

struct Arr
{
int *pBase; //数组首地址
int cnt; // 数组内有效值个数
int len; // 数组长度
};

void init_arr(struct Arr *arr, int length);
void show_arr(struct Arr *parr);
bool is_empty(struct Arr *parr);
bool is_full(struct Arr *parr);
bool append_arr(struct Arr *parr, int val);
bool insert_arr(struct Arr *parr, int pos, int val);
void reverse_arr(struct Arr *parr);
void sort_arr(struct Arr *parr);

int main()
{
struct Arr arr;

init_arr(&arr, 6);
// show_arr(&arr);
append_arr(&arr, 1);
append_arr(&arr, 2);
insert_arr(&arr, 2, 9);
append_arr(&arr, 5);
append_arr(&arr, -1);
show_arr(&arr);
reverse_arr(&arr);
printf("resveer==========\n");
show_arr(&arr);
printf("sort=============\n");
sort_arr(&arr);
show_arr(&arr);

return 0;
}

void init_arr(struct Arr *parr, int length)
{
parr->pBase = (int *)malloc(sizeof(int) * length);
if (parr->pBase == NULL)
{
printf("failed to allocate dynamic memory !\n");
exit(-1); // 终止程序
}
else
{
parr->len = length;
parr->cnt = 0;
}

printf("Initialize array successfully\n");
}

void show_arr(struct Arr *parr)
{
if (is_empty(parr))
printf("the array is empty\n");
else
{
for (int i = 0; i < (*parr).cnt; i++)
printf("content of the array: %d\n", *(parr->pBase + i));
printf("\n");
}
}

bool is_empty(struct Arr *parr)
{
if (parr->cnt == 0)
return true;
else
return false;
}

bool is_full(struct Arr *parr)
{
if (parr->cnt == parr->len)
return true;
else
return false;
}

bool append_arr(struct Arr *parr, int val)
{
if (is_full(parr))
printf("the array is already full !\n");
else
{
parr->pBase[parr->cnt] = val;
(parr->cnt)++;
}
return true;

}

bool insert_arr(struct Arr *parr, int pos, int val)
{
if (is_full(parr))
printf("the array is already full !\n");
if (pos <1 || pos > (parr->cnt + 1))
{
printf("failed to insert \n");
return false;
}
else
{
for (int i = parr->cnt; i >= pos-1; i--)
parr->pBase[i] = parr->pBase[i-1];
parr->pBase[pos-1] = val;
(parr->cnt)++;
}
return true;
}

void reverse_arr(struct Arr *parr)
{
int i = 0;
int j = parr->cnt - 1;
int t;
while (i < j)
{
t = parr->pBase[i];
parr->pBase[i] = parr->pBase[j];
parr->pBase[j] = t;
i++;
j--;
}
}

void sort_arr(struct Arr *parr)
{
int i, j, t;
for ( i = 0; i < parr->cnt; i++)
{
for ( j = i+1; j < parr->cnt; j++)
{
if (parr->pBase[i] > parr->pBase[j])
{
t = parr->pBase[i];
parr->pBase[i] = parr->pBase[j];
parr->pBase[j] = t;
}
}
}
}
文章作者: gh
文章链接: https://ghclub.top/posts/25393/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 GHBlog
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论