前言
数据结构就是将大量而复杂的数据类型和特定的存储结构保存到主存储器，并在此基础上为了实现某个功能而执行的相应操作。 -- by 郝斌视频
今天研究并实现了数据结构中线性结构之一的数组实现。
数组就是一组连续存储的数据。
要实现的功能:
- 拼接 append
- 添加 insert
- 删除 delete
- 排序 sort
- 获取数组长度 len
- 判断数组是否为空 isempty
- 判断数组是否已满 isfull
- 打印显示数组数据 show
// 1. 创建数组
void init_arr(PARRAYLIST pArray, int len);
// 2. 获取数组长度
int len_arr(PARRAYLIST pArray);
// 3. 判断数组是否为空
bool isempty_arr(PARRAYLIST pArray);
// 4. 判断数组是否已满
bool isfull_arr(PARRAYLIST pArray);
// 5. 拼接数据
bool append_arr(PARRAYLIST pArray, int val);
// 6. 插入数据
bool insert_arr(PARRAYLIST pArray, int pos, int val);
// 7. 删除数据
bool delete_arr(PARRAYLIST pArray, int pos, int * pVal);
// 8. 数组排序
void sort_arr(PARRAYLIST pArray);
// 9. 打印显示
void show_arr(PARRAYLIST pArray);
首先我们要创建一个数组，那么数组在代码中怎么体现的呢？面向对象语言中，数组就是一个对象，C 语言是面向过程语言，并不存在对象一说，因此可以考虑使用结构。
数组的结构，数组我们需要了解哪些东西
- 肯定是数据，而且是保存一长串数据就会用到数组，我们这里使用指针保存数据；
- 既然是一个不可变数组，需要给数组指定一个总长度；
- 然后在指定一个有效长度，来保存数组中真实存储的数据个数。
// 数据结构：数组实现
typedef struct ArrayList {
int * pbase; // 保存数据的第一个指针
int len; // 数组长度
int cnt; // 数组有效长度
}ARRAYLIST, *PARRAYLIST;
OK,现在有数组了，我们要操作一个对象是不是需要有这个对象呐，现在要创建一个数组，C 语言中结构体并不会像面向对象语言中的对象可以跨函数调用。
C 语言中跨函数调用必须是动态分配内存，因此我们这个数组就需要我们动态分配内存。
接下来使用 malloc 函数，也就是 C 语言中动态分配内存的方法，创建数组并为其分配内存。
/**
创建数组
@param pArray 操作数组
@param len 创建数组长度
*/
void init_arr(PARRAYLIST pArray, int len)
{
// 1. 为指针域分配空间
pArray->pbase = (int *)malloc(sizeof(int)*len);
if (NULL == pArray->pbase) {
printf("内存分配失败!\n");
exit(-1);
}
// 初始化数组其他参数
pArray->len = len;
pArray->cnt = 0;
return;
}
现在有了数组，我们就应该实现数组的方法了。
首先，我们先实现获取长度的方法，也很简单，在结构体 ArrayList 中我们保存了一个 cnt 字段来表示有效长度，所有我们数组的长度就是这个 cnt 字段的值。
/**
获取数组长度
@param pArray 操作数组
@return 数组长度
*/
int len_arr(PARRAYLIST pArray)
{
return pArray->cnt;
}
然后，判断数组是否为空, 那么数组什么时候为空呢？当然是数组中没有数据，也就是数组有效长度为 0 的时候。
/**
判断数组是否为空
@param pArray 操作数组
@return 是否为空
*/
bool isempty_arr(PARRAYLIST pArray)
{
return pArray->cnt == 0;
}
接下来，判断数组是否已满，那么数组什么时候已满呢？当然是当数组中的个数等于数组总长度的时候。
/**
判断数组是否已满
@param pArray 操作数组
@return 数组是否已满
*/
bool isfull_arr(PARRAYLIST pArray)
{
return pArray->cnt == pArray->len;
}
再然后，我们来实现拼接、插入和删除的逻辑。
拼接就是在数组最后插入一条数据，那么只要知道当前数组的个数 count，并将拼接数据插入到 count+1 的位置，当然不要忘记把我们有效数据的表示为 +1。
/**
拼接数据
@param pArray 操作数组
@param val 拼接数据
@return 拼接是否成功
*/
bool append_arr(PARRAYLIST pArray, int val)
{
if (isfull_arr(pArray)) {
printf("数组已满, 拼接操作失败\n");
return false;
}
pArray->pbase[pArray->cnt] = val;
pArray->cnt ++;
return true;
}
插入操作需要接受三个参数，一个是数组地址，一个
插入位置，最后是数值。
其实拼接操作可以看做插入操作的一个特例，因为我们可以自己计算出了，省略了插入位置，由拼接操作可以推算出插入操作执行步骤。
第一步，需要定位到要插入的位置。
第二步，插数据到这个位置。
咦，貌似不对，数据是插进去，位置也对，但是数组的长度怎么没有变，好像少了一个数吧。
每次，我们是插入数据，但是我们把原来位置数据替换成了我们要插的数据，但是原来数据却丢了！因此，我们需要在插数据前在执行一个步骤。
将当前位置数据以及其后所有数据都往后移动一个位置，当然不要忘记把我们有效数据的表示为 +1。
/**
插入数据
@param pArray 操作数组
@param pos 插入位置
@param val 插入值
@return 插入是否成功
*/
bool insert_arr(PARRAYLIST pArray, int pos, int val)
{
if (isfull_arr(pArray)) {
printf("数组已满, 拼接操作失败\n");
return false;
}
if (0 > pos - 1 || pos > pArray->cnt + 1) {
printf("插入位置不合法!\n");
return false;
}
if (pos == pArray->cnt + 1) {
pArray->pbase[pos - 1] = val;
pArray->cnt ++;
return true;
}
int i ;
for (i = pArray->cnt; i >= pos - 1; -- i) {
pArray->pbase[i] = pArray->pbase[i - 1];
}
pArray->pbase[pos - 1] = val;
pArray->cnt ++;
return true;
}
删除操作跟插入操作是反向操作。
既然插入操作要将插入位置以及之后的数据后移一位，那么作为死对头，删除肯定就是将删除位置之后的数据前移一位，然后修改有效数据的标识 -1。
/**
删除数据
@param pArray 操作数组
@param pos 删除位置
@param pVal 删除值
@return 是否删除成功
*/
bool delete_arr(PARRAYLIST pArray, int pos, int * pVal)
{
if (isempty_arr(pArray)) {
printf("数组为空,不能执行删除操作!\n");
exit(-1);
}
if (0 > pos - 1 || pos > pArray->cnt) {
printf("删除位置不合法!\n");
return false;
}
*pVal = pArray->pbase[pos - 1];
if (pos == pArray->cnt + 1) {
pArray->cnt --;
return true;
}
int i ;
for (i = pos - 1; i < pArray->cnt; ++ i) {
pArray->pbase[i] = pArray->pbase[i + 1];
}
pArray->cnt --;
return true;
}
最后就是数组排序和显示了，对于接触过面向对象语言的各位，排序应该是常客了，较为常见的排序有顺序和冒泡两种，在这里就不啰嗦了，直接上代码
/**
数组排序
@param pArray 操作数组
*/
void sort_arr(PARRAYLIST pArray)
{
int i, j, t;
for (i = 0; i < pArray->cnt - 1; ++ i) {
for (j = i; j < pArray->cnt; ++ j) {
if (pArray->pbase[i] > pArray->pbase[j]) {
t = pArray->pbase[j];
pArray->pbase[j] = pArray->pbase[i];
pArray->pbase[i] = t;
}
}
}
}
/**
打印显示
@param pArray 操作数组
*/
void show_arr(PARRAYLIST pArray)
{
int i ;
for (i = 0; i < pArray->cnt; ++ i) {
printf("%d ", pArray->pbase[i]);
}
printf("\n");
return;
}
到目前为止，C 语言实现数组的任务基本完工，剩下的就是测试和拓展新功能了。
如果各位客官有兴趣可以在此基础上完善，或者有什么需求也可以提出，如果我能完成也可以分享出来。
各路大牛轻喷，新手练手，有错请指出。
下面放出完整代码供大家学习，喜欢请 star 谢谢！
网友评论