数据结构学习笔记(一)

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

struct Arr {
    int * pBase; //存储数组的首元素的地址
	int len; //数组的长度
	int cnt; //有效元素的个数
};

void init(struct Arr * pArr, int length);
bool isEmpty(struct Arr * pArr);
void showArray(struct Arr * pArr);
bool append(struct Arr * pArr, int value);
bool isFull(struct Arr * pArr);
bool insert(struct Arr * pArr, int pos, int value);
bool deleteValue(struct Arr * pArr, int pos, int * pVal); 
void inversion(struct Arr * pArr);
void sort(struct Arr * pArr);

int main() {
	struct Arr arr;
	int val;
	init(&arr,7);
	append(&arr,1);
	append(&arr,454);
	append(&arr,-12);
	append(&arr,15742);
	append(&arr,2);
	showArray(&arr);
	inversion(&arr);
	showArray(&arr);
	sort(&arr);
	showArray(&arr);

	/*
	if(deleteValue(&arr,6,&val)) {
		printf("删除成功！\n");
		printf("您删除的元素是=%d\n",val);
	}else {
		printf("删除失败！\n");
	}
	showArray(&arr);
	*/

    return 0;
}

/*
	排序
	升序
*/
void sort(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;
			}
		}
	}
}

/*
	 将数组倒置
*/
void inversion(struct Arr * pArr) {
	int i = 0;
	int j = pArr->cnt - 1;
	int t = 0;
	while(i < j) {
		t = pArr->pBase[i];
		pArr->pBase[i] = pArr->pBase[j];
		pArr->pBase[j] = t;
		i++;
		j--;
	}
	return;
}

/*
	插入在pos的位置前面插入一个数值
	pos从1开始
*/
bool insert(struct Arr * pArr, int pos, int value) {
	int i;
	
	if(isFull(pArr)) {
		return false;
	}

	if(pos < 1 || pos>pArr->cnt + 1) {
		return false;
	}

	for(i = pArr->cnt - 1; i >= pos - 1; --i) {
		pArr->pBase[i+1] = pArr->pBase[i];
	}
	pArr->pBase[pos-1] = value;
	(pArr->cnt)++;

	return true;
}

/*
	删除指定元素
	成功返回true，失败返回false
*/
bool deleteValue(struct Arr * pArr, int pos, int * pVal) {
	int i;

	if(isEmpty(pArr)) {
		return false;
	}

	if(pos < 1 || pos > pArr->cnt) {
		return false;
	}

	* pVal = pArr->pBase[pos-1];

	for(i = pos; i < pArr->cnt; ++i) {
		pArr->pBase[i-1] = pArr->pBase[i];
	}

	pArr->cnt--;

	return true;
}

/*
	判断数组是否满
	满返回true，不满返回false
*/
bool isFull(struct Arr * pArr) {
	if(pArr->cnt == pArr->len) {
		return true;
	}else {
		return false;
	}
}

/*
	在数组的末尾追加一个值
*/
bool append(struct Arr * pArr, int value) {
	if(isFull(pArr)) {
		return false;
	}else {
	   	pArr->pBase[pArr->cnt] = value;
		(pArr->cnt)++;
		return true;
	}
}

/*
	显示数组
*/
void showArray(struct Arr * pArr) {
	if(pArr->cnt == 0) {
		printf("数组为空！\n");
	}else {
		for(int i = 0; i < pArr->cnt; i++ ) {
			printf("%d ",pArr->pBase[i]);
		}
		printf("\n");
	}
}

/*
	判断数组是否为空
	为空返回true，不为空返回false
*/
bool isEmpty(struct Arr * pArr) {
	if(pArr->cnt == 0) {
		return true;
	}else {
		return false;
	}
}

/*
	建立一个数组，并指定长度
*/

void init(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;
}