郝斌数据结构-线性表程序

以下代码来自于郝斌老师数据结构视频，加以自己的理解作了注释，用于学习和复习，欢迎大家指正错误。
代码的运行环境：DEV-C++ 6.3版本，创建源文件为.cpp文件即可编译运行。

#include 
#include 

//定义了一个数据类型，该数据类型含有三个成员
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 *pVal);//删除指定位置数据
//bool get();
bool is_empty(struct ARR *pArr);		//判断数组是否空
bool is_full(struct ARR *pArr);			//判断数组是否满
void sort_arr(struct ARR *pArr);		//排序数组元素(升序排序)
void show_arr(struct ARR *pArr);		//打印数组元素
void inversion_arr(struct ARR *pArr);	//倒置元素函数(全部倒置)


int main(void){
	struct ARR a;//尚未创建线性表
	int val;
	
	init_arr(&a,7);//初始化7个数据空间的数组
	//show_arr(&a);
	append_arr(&a,1);
	append_arr(&a,2);
	append_arr(&a,3);
	append_arr(&a,7);
	insert_arr(&a,2,99);
	show_arr(&a);
	if(delete_arr(&a,3,&val)){
		printf("删除成功!n%d被删除n",val);
	}
	else{
		printf("删除失败!n");
	}

//	insert_arr(&a,3,26);
//	if(append_arr(&a,4))
//		printf("追加成功n");
//	else
//		printf("追加失败n");
	show_arr(&a);
	inversion_arr(&a);
	show_arr(&a);
	sort_arr(&a);
	show_arr(&a);
	//printf("%dn",a.len);
}





//结构体变量不能加减乘除，但能相互赋值

void init_arr(struct ARR *pArr,int length){
	pArr->pBase = (int *)malloc(sizeof(int)*length);//分配失败malloc会给pBase一个NULL，成功会返回开辟空间的首地址
	//如果动态分配失败，说明pBase是NULL
	if(NULL == pArr->pBase){
		printf("动态分配内存失败！n");
		exit(-1);//终止整个程序
	}
	else{
		pArr->len = length;
		pArr->cnt = 0;//线性表中有效元素个数为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){//取地址操作，pArr已经是线性表的地址了
	if(is_empty(pArr))//这里填pArr?*pArr?&pArr?第二第三个不对，第二个是地址的指针，不对；第三个对地址再取地址，显然不对
	{
		printf("array is empty!n");
	}
	else
	{
		for (int i=0;icnt;++i)
			printf("%d ",pArr->pBase[i]);
		printf("n");
	}	
}

bool append_arr(struct ARR *pArr,int val){
	if(is_full(pArr))//满返回false
		return false;
		//不满时追加
	pArr->pBase[pArr->cnt] = val;	//让结构体中的第cnt个指针地址赋值val
	pArr->cnt++;					//结构体中的cnt++有效个数自增一，不然添加元素不显示
	return 0;
}

bool insert_arr(struct ARR *pArr,int pos,int val){
	int i;
	if(is_full(pArr)){
		return false;
	}
	if(pos<1||pos>pArr->cnt+1){//+1是因为pos可以设置有效位数的最后一位插入，显然是在数组没有满的前提下
		return false;
	}
	for(i=pArr->cnt-1;i>=pos-1;--i){//在第pos个位置插入数据，对应数组下标pos-1
		pArr->pBase[i+1] = pArr->pBase[i];
	}//先移动，把插入位置的空间腾出来
	pArr->pBase[pos-1] = val;//再赋值，完成数据插入
	pArr->cnt++;			//最后不要忘了有效个数的改变，不然插入一位就会丢失一位
	return true;
}	

bool delete_arr(struct ARR *pArr,int pos,int *pVal){
	int i;
	if(is_empty(pArr)){//判断数组是否空，要删除的肯定不能是空数组
		return false;
	}
	if(pos<1||pos>pArr->cnt){//删除的只能是已有数据，不能在有效计数外删除
		return false;		//这一点和插入有区别
	}
	//主函数中的实参val等价于pVal形参
	*pVal = pArr->pBase[pos-1];//pos-1为要删除的数据数组下标
	for(i=pos;icnt;++i){
		pArr->pBase[i-1] = pArr->pBase[i];
	}
	pArr->cnt--;
	//删除完之后数组有效个数-1，不然会有一个多余数据
	return true;
}

void inversion_arr(struct ARR *pArr){
	int i=0;
	int t=0;//中间变量用于过渡
	int j = pArr->cnt-1;//最后一个有效值所在的数组下标
	
	while(i
		t = pArr->pBase[i];
		pArr->pBase[i] = pArr->pBase[j];
		pArr->pBase[j] = t;
		++i;--j;
	}
	return;//函数结束
}

void sort_arr(struct ARR *pArr){
	int i,j;
	int t=0;
	for(i=0;icnt;++i){
		for(j=i+1;jcnt;++j){
			if(pArr->pBase[i]>pArr->pBase[j]){
				t = pArr->pBase[i];
				pArr->pBase[i] = pArr->pBase[j];
				pArr->pBase[j] = t;
			}
		}
	}	
}