数据结构01：数组
/*
* 根据郝斌老师视频整理
* 编译环境：
* guo@linux:~$ gcc --version
* gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
*/
#include <stdio.h>
#include <malloc.h> /*malloc()*/
#include <stdlib.h> /*exit()*/
#define FALSE 0
#define TRUE 1
typedef struct Array
{
int *pBase; /*存储数组第一个元素的地址*/
int len; /*数组能容纳的有效元素的个数*/
int cnt; /*当前数组有效元素的个数*/
// int increment; /*自动增长因子，需要allocate()函数*/
}ARRAY;
/**************************声明*******************************/
/*初始化数组*/
void InitArray(ARRAY *, int );
/*数组追加元素*/
int AppendArray(ARRAY *, int );
/*数组插入元素*/
int InsertArray(ARRAY *, int , int );
/*数组删除元素*/
int DeleteArray(ARRAY *, int, int *);
/*获得元素*/
int get(ARRAY *,int , int *);
/*判断数组是否为空*/
int IsEmpty(ARRAY *);
/*判断数组是否已满*/
int IsFull(ARRAY *);
/*数组排序*/
void SortArray(ARRAY *);
/*显示数组*/
void ShowArray(ARRAY *);
/*倒置数组*/
void InversionArray(ARRAY *);
/*
* 函数名称：InitArray。
* 函数说明：初始化数组，为数组分配内存，并确定长度。
* 输入参数：pArr数组首地址，length数组长度。
* 输出参数：无。
*/
void InitArray(ARRAY *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;
}
/*
* 函数名称：IsEmpty。
* 函数说明：判断数组是否为空。
* 输入参数：pArr数组首地址。
* 输出参数：如果数组为空，返回TRUE；否则返回FALSE。
*/
int IsEmpty(ARRAY *pArr)
{
if (0==pArr->cnt)
return TRUE;
else
return FALSE;
}
/*
* 函数名称：IsFull。
* 函数说明：判断数组是否为满。
* 输入参数：pArr数组首地址。
* 输出参数：如果数组为满，返回TRUE；否则返回FALSE。
*/
int IsFull(ARRAY *pArr)
{
if (pArr->len == pArr->cnt)
return TRUE;
else
return FALSE;
}
/*
* 函数名称：AppendArray。
* 函数说明：数组追加元素。
* 输入参数：pArr数组首地址，val要追加的值。
* 输出参数：如果数组为满，返回FALSE；追加成功返回TRUE。
*/
int AppendArray(ARRAY *pArr,int val)
{
if ( IsFull(pArr) )
return FALSE;
pArr->pBase = val;
pArr->cnt++;
return TRUE;
}
/*
* 函数名称：InsertArray。
* 函数说明：插入元素，如果数组只有3个元素，可以插入到第4个元素位置。
* 输入参数：pArr数组首地址；position要插入的位置，从1开始；val要插入的值。
* 输出参数：如果数组为满或下标越界或没有存储那么多元素，返回FALSE；插入成功返回TRUE。
*/
int InsertArray(ARRAY *pArr, int position, int val)
{
int i;
if ( IsFull(pArr) )
return FALSE; /*数组已满*/
if (position<1 || position>pArr->len)
return FALSE; /*下标越界*/
if (position>pArr->cnt+1)
return FALSE; /*没存储那么多元素*/
/*在位置position后的元素都向后移动一位*/
for (i=pArr->cnt;i>=position;--i)
{
pArr->pBase = pArr->pBase;
}
pArr->pBase = val;
pArr->cnt++;
return TRUE;
}
/*
* 函数名称：DeleteArray。
* 函数说明：删除元素。
* 输入参数：pArr数组首地址；position要删除的位置；val存储要删除的值。
* 输出参数：如果数组为满或下标越界或没有存储那么多元素，返回FALSE；删除成功返回TRUE。
* 删除成功前，先存储要删除的元素。
*/
int DeleteArray(ARRAY *pArr, int position, int *val)
{
int i;
if ( IsEmpty(pArr) )
return FALSE; /*数组为空*/
if (position<1 || position>pArr->len)
return FALSE; /*下标越界*/
if (position > pArr->cnt)
return FALSE; /*数组未存储那么多元素*/
*val = pArr->pBase;
for (i=position-1;i<pArr->cnt;++i)
{
pArr->pBase = pArr->pBase;
}
pArr->cnt--;
return TRUE;
}
/*
*
*/
int get(ARRAY *pArr, int i, int *val)
{
if (i<1 || i>pArr->cnt)
return FALSE;
*val = pArr->pBase;
return TRUE;
}
/*
* 函数名称：InversionArray。
* 函数说明：倒置数组。
* 输入参数：pArr数组首地址。
* 输出参数：无。
*/
void InversionArray(ARRAY *pArr)
{
int i = 0;
int j = pArr->cnt - 1;
int temp;
while (i<j)
{
temp = pArr->pBase;
pArr->pBase = pArr->pBase;
pArr->pBase = temp;
++i;
--j;
}
return;
}
/*
* 函数名称：SortArray。
* 函数说明：选择排序
* 1. 先取数组第一个元素，跟其他所有元素比较，放最小值
* 2. 再取数组第二个元素，跟其他除了第一个元素外的所有元素比较，放最小值
* 3. 依次进行，直到比较完
* 输入参数：pArr数组首地址。
* 输出参数：无。
*/
void SortArray(ARRAY *pArr)
{
int i, j, temp;
for (i=0;i<pArr->cnt-1;++i)
{
for (j=i+1;j<pArr->cnt;++j)
{
if (pArr->pBase > pArr->pBase)
{
temp = pArr->pBase;
pArr->pBase = pArr->pBase;
pArr->pBase = temp;
}
}
}
return;
}
/*
* 函数名称：ShowArray。
* 函数说明：显示数组元素。
* 输入参数：pArr数组首地址。
* 输出参数：无。
*/
void ShowArray(ARRAY *pArr)
{
int i;
if ( IsEmpty(pArr) )
{
printf("Array is empty!\n");
}
else
{
for (i=0;i<pArr->cnt;++i)
{
printf("%d ",pArr->pBase);
}
printf("\n");
}
}
int main(void)
{
int temp32;
int val;
ARRAY arr;
InitArray(&arr, 6);
printf("新建数组：\n");
printf("len=%d cnt=%d\n", arr.len, arr.cnt);
ShowArray(&arr);
printf("追加后，数组元素为:\n");
AppendArray(&arr,11);
AppendArray(&arr,22);
AppendArray(&arr,33);
AppendArray(&arr,44);
/* AppendArray(&arr,55);
AppendArray(&arr,66);
AppendArray(&arr,77);
AppendArray(&arr,88); */
ShowArray(&arr);
printf("插入后，数组元素为：\n");
temp32 = InsertArray(&arr,5,99);
if (TRUE == temp32)
{
ShowArray(&arr);
}
else
{
printf("插入错误！\n");
}
printf("删除后，数组元素为：\n");
temp32 = DeleteArray(&arr, 3, &val);
if (TRUE == temp32)
{
ShowArray(&arr);
printf("删除的元素是%d\n", val);
}
else
{
printf("删除错误!\n");;
}
temp32 = get(&arr, 5, &val);
if (temp32)
{
printf("第%d个元素是%d.\n", 5, val);
}
else
{
printf("获取元素错误！\n");
}
printf("数组倒置后为：\n");
InversionArray(&arr);
ShowArray(&arr);
printf("数组按升序排列后为：\n");
SortArray(&arr);
ShowArray(&arr);
return 0;
}
页:
[1]