数据结构 第3节 ArrayList实现
2019-07-18 本文已影响2人
小超_8b2f
一、素组的2种实现方式
- int arr[len];
- int * arr = (int *)malloc(sizeof(int) * len);
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//定义了一个数据类型,改数据类型的名字叫做struct Arr,该数据类型含有下面4个成员
struct Arr {
int * pBase; //存储的是数组第一个元素的地址
int len; //数组所能容纳的最大元素个数
int cnt; //当前数组有效元素个数
int increment; //自动增长因子
};
void init_arr(struct Arr * pArr, int length);
bool append_arr(struct Arr * pArr, int val);
bool insert_arr(struct Arr * pArr, int pos, int val);
bool delete_arr(struct Arr * pArr, int pos, int * del_val);
int get(struct Arr * arr,int i);
bool is_empty(struct Arr * pArr);
bool is_full(struct Arr * pArr);
void sort_arr(struct Arr * pArr);
void sort_arr2(struct Arr * pArr);
void show_arr(struct Arr * pArr);
void inverse_arr(struct Arr * pArr);
int main(void) {
int i;
int val;
struct Arr arr;
init_arr(&arr,6);
show_arr(&arr);
for(i = 0; i < 8; i++)
append_arr(&arr, i);
show_arr(&arr);
delete_arr(&arr,4, &val);
printf("删除元素的值是:%d\n", val);
show_arr(&arr);
insert_arr(&arr, 1, 99);
show_arr(&arr);
inverse_arr(&arr);
show_arr(&arr);
sort_arr(&arr);
show_arr(&arr);
printf("%d \n", get(&arr,5));
return 0;
}
void init_arr(struct Arr * pArr, int length) {
pArr->pBase = (int *)malloc(sizeof(int) * length);
if(NULL == pArr->pBase) {
printf("动态内存分配失败!\n");
exit(-1);
} else {
pArr->len = length;
pArr->cnt = 0;
}
return;
}
bool is_empty(struct Arr * pArr) {
if(0 == pArr->cnt)
return true;
else
return false;
}
bool is_full(struct Arr * pArr) {
if(pArr->cnt == pArr->len)
return true;
else
return false;
}
void show_arr(struct Arr * pArr) {
if(is_empty(pArr)) {
printf("[]\n");
} else {
printf("{");
for(int i = 0; i < pArr->cnt; i++) {
printf("%d ", *(pArr->pBase+i)); //pArr->pBase[i]
}
printf("}\n");
}
return;
}
bool append_arr(struct Arr * pArr,int val) {
if(is_full(pArr)){
printf("");
return false;
} else {
//*(pArr->pBase+pArr->cnt+1) = val;
pArr->pBase[pArr->cnt] = val;
++(pArr->cnt);
}
return true;
}
bool insert_arr(struct Arr * pArr, int pos, int val) {
if(pos < 1 || pos > pArr->cnt) {
printf("位置不正确\n");
return false;
}
if(is_full(pArr)) {
printf("已满,不允许插入\n");
}
for(int i = pArr->cnt-1; i >= pos-1 ; i--) {
pArr->pBase[i+1] = pArr->pBase[i];
}
pArr->pBase[pos-1] = val;
pArr->cnt++;
return true;
/*
值:12 3456 position=3
下标:01 2345 unser_ >=2 都需要移
arr[unser_ ==2] = new Val
*/
}
bool delete_arr(struct Arr * pArr, int pos, int * del_val) {
if(is_empty(pArr)) {
printf("内容为空,不允许删除\n");
return false;
}
if(pos < 1 || pos > pArr->cnt) {
printf("下标不合法,不允许删除\n");
return false;
}
*del_val = pArr->pBase[pos-1];
//1 2 3 4 5 pos = 3 则 4 5 往前挪,即下标
for(int i = pos; i < pArr->cnt; i++) {
pArr->pBase[i-1] = pArr->pBase[i];
}
pArr->cnt--;
return true;
}
/** 反转 */
void inverse_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--;
}
return;
}
/**排序1*/
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;
}
}
}
return;
}
int get(struct Arr * arr,int i) {
return *((arr->pBase)+i);
}