【数据结构】模块一：线性存储

数据结构的学习大致可以分为三个模块，分别是：线性结构，非线性结构，查找和排序。

首先从线性结构开始学起：

线性结构，简单地说，就是把所有的结点用一根直线穿起来。

线性结构可以分为连续存储（数组）和离散存储（链表）两种存储方式，共有两种常见的应用，即栈和队列，其二者只不过是简化版的数组或链表，用于特殊应用，因此，学好线性结构，打好基础是十分重要的。今天就从最简单的连续存储（数组）学起来。

基础的数组知识在语言程序设计中均已有学习，因此，在数据结构中，要学会如何使用连续存储的知识，综合模拟使用数组与结构体，这是十分重要的。

代码实现：

#include <stdio.h>
#include <malloc.h> //包含了malloc函数
#include <stdlib.h> //包含了exit函数

//定义了一个数据类型，其名字叫做struct Arr,该数据类型含有三个成员，分别是pBase,len,cnt
struct Arr
{
	int* pBase; //存储的是数组第一个元素的地址
	int len;    //数组所能容纳的最大元素的个数
	int cnt;    //当前有效元素的个数
};

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); //pos的值从1开始
bool delete_arr(struct Arr* pArr, int pos, int* pVal);
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 inverse_arr(struct Arr* pArr);

int main(void)
{
	struct Arr arr;
	int val;

	init_arr(&arr, 6);
	show_arr(&arr);

	append_arr(&arr, -1);
	append_arr(&arr, 5);
	append_arr(&arr, 7);
	append_arr(&arr, 4);
	show_arr(&arr);
	/*append_arr(&arr, 5);
	show_arr(&arr);
	if (append_arr(&arr, 6))
	{
		printf("追加成功！\n");
	}
	else
	{
		printf("追加失败！\n");
	}
	show_arr(&arr);
	if (append_arr(&arr, 7))
	{
		printf("追加成功！\n");
	}
	else
	{
		printf("追加失败！\n");
	}
	show_arr(&arr);*/

	if (insert_arr(&arr, 2, 99))
	{
		printf("插入成功！\n");
	}
	else
	{
		printf("插入失败！\n");
	}
	show_arr(&arr);
	if (insert_arr(&arr, 7, 99))
	{
		printf("插入成功！\n");
	}
	else
	{
		printf("插入失败！\n");
	}
	show_arr(&arr);

	if (delete_arr(&arr, 2, &val))
	{
		printf("删除成功！\n");
		printf("您删除的元素是：%d\n", val);
	}
	else
	{
		printf("删除失败！\n");
	}
	show_arr(&arr);

	if (delete_arr(&arr, 5, &val))
	{
		printf("删除成功！\n");
		printf("您删除的元素是：%d\n", val);
	}
	else
	{
		printf("删除失败！\n");
	}
	show_arr(&arr);

	inverse_arr(&arr);
	printf("倒序后元素如下：\n");
	show_arr(&arr);

	sort_arr(&arr);
	printf("排序后元素如下：\n");
	show_arr(&arr);

	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;
}
void show_arr(struct Arr* pArr)
{
	if (is_empty(pArr))
	{
		printf("数组为空！\n");
	}
	else
	{
		for (int i = 0; i < pArr->cnt; ++i)
			printf("%d ", pArr->pBase[i]);
		printf("\n");
	}
}

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

bool append_arr(struct Arr* pArr, int val)
{
	//满时返回false
	if (is_full(pArr))
		return false;
	//不满时追加
	pArr->pBase[pArr->cnt++] = val;
	return true;
}

bool insert_arr(struct Arr* pArr, int pos, int val)
{
	if (is_full(pArr))
		return false;
	if (pos < 1 || pos > pArr->cnt + 1) //假设有3个元素，cnt为3，可以在第4个元素前插入，不能在第5个前插入
		return false;

	int i;
	//后移元素
	for (i = pArr->cnt - 1; i >= pos - 1; --i)
	{
		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)
{
	if (is_empty(pArr))
		return false;
	if (pos < 1 || pos > pArr->cnt) 
		return false;

	*pVal = pArr->pBase[pos - 1];
	int i;
	for (i = pos; i < pArr->cnt; ++i)
	{
		pArr->pBase[i - 1] = pArr->pBase[i];
	}
	pArr->cnt--;
	return true;
}

void inverse_arr(struct Arr* pArr)
{
	int t, i = 0, j = pArr->cnt - 1;

	while (i < j)
	{
		t = pArr->pBase[i];
		pArr->pBase[i++] = pArr->pBase[j];
		pArr->pBase[j--] = t;
	}
	return;
}

void sort_arr(struct Arr* pArr)
{
	int t, i, j;

	for (i = 0; i < pArr->cnt; ++i)
	{
		for (j = i + 1; j < pArr->cnt; ++j)
		{
			t = pArr->pBase[i];
			pArr->pBase[i] = pArr->pBase[j];
			pArr->pBase[j] = t;
		}
	}
	return;
}