线性结构之数组

数组

把所有节点用一根直线串起来而形成的一种数据结构称为线性结构。

今天我想谈谈线性结构中的数组。大家都知道数组是连续存储的一种线性结构，而数组名为该数组元素的首地址。如int a[3]={1,2,3};a就等价于&a[0],而&a[0]本身是int *类型，所以我们通常利用数组名来与指针建立联系，进而跨函数使用内存对数组进行操作。

实例说明：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct Arr
{
	int* pBase;//pBase存储的是数组第一个元素的地址
	int len;//len为数组所能容纳的最大元素的个数
	int cnt;//当前数组有效元素的个数
};
void InitArray(struct Arr *pArr,int length);//初始化数组
void AppendArray(struct Arr *pArr,int val);//尾部追加数据
int IsFull(struct Arr *pArr);//判断数组是否已满（我的这个vc++编译器不知道为什么，函数返回值不能为bool型；所以这里我把它设置成int型来判断）
void ShowArray(struct Arr *pArr);//输出显示
int IsEmpty(struct Arr *pArr);//判断数组是否为空
void DeleteArray(struct Arr *pArr,int pos,int *pVal);//删除元素，pVal指向pos(从1开始)位置的值
void InsertArray(struct Arr *pArr,int pos,int val);//插入元素,pos从1开始
void SortArray(struct Arr *pArr);//排序,因为初学数据结构,我这里用的是冒泡排序法
void InverseArray(struct Arr *pArr);//倒置
void GetByPostion(struct Arr *pArr,int pos);//根据位置来查找元素
void ModifyArray(struct Arr *pArr,int pos,int val);//修改元素元素，pVal指向pos(从1开始)位置的值
int main()
{
	struct Arr arr;//为arr分配内存
	int val;
    InitArray(&arr,6);
    AppendArray(&arr,7);
	AppendArray(&arr,2);
	AppendArray(&arr,5);
	AppendArray(&arr,9);
	printf("初始化");
	ShowArray(&arr);
    InsertArray(&arr,4,6);
	printf("插入后");
    ShowArray(&arr); 
	DeleteArray(&arr,3,&val);
	printf("删除的元素为：%d\n",val);
	printf("删除后");
	ShowArray(&arr); 
	SortArray(&arr);	
	printf("排序后");
	ShowArray(&arr); 
	InverseArray(&arr);
	printf("倒置后");
	ShowArray(&arr);
	GetByPostion(&arr,2);
	ModifyArray(&arr,1,1000);
	printf("修改后");
	ShowArray(&arr);
	return 0;
}

void InitArray(struct Arr *pArr,int length)
{
	pArr->pBase=(int *)malloc(sizeof(int)*length);//为结构体成员pBase动态分配一块内存
	if(NULL==pArr->pBase)
	{
		printf("动态内存分配失败！");
		exit(1);//终止整个程序
	}
	else
	{
		pArr->len=length;
		pArr->cnt=0;
	}
}

int IsFull(struct Arr *pArr)
{
	if(pArr->cnt==pArr->len)
		return 1;
	else
		return -1;
}

void AppendArray(struct Arr *pArr,int val)
{
	if(1==IsFull(pArr))
		printf("数组已满，越界元素添加失败！\n");
	else 
		pArr->pBase[pArr->cnt++]=val;
}

int IsEmpty(struct Arr *pArr)
{
	if(0==pArr->cnt)
		return 1;
	else
		return -1;
}

void ShowArray(struct Arr *pArr)
{
	int i;
	if(1==IsEmpty(pArr))
		printf("数组为空！\n");
	else
	{
		printf("数组元素为：");
		for(i=0;i<pArr->cnt;i++)
			printf("%d  ",pArr->pBase[i]);
		printf("\n");
	}
}

void DeleteArray(struct Arr *pArr,int pos,int *pVal)
{
	int i;
	if(1==IsEmpty(pArr))
		printf("数组为空！\n");
	else
	{
		if(pos<1||pos>pArr->cnt)
			printf("删除操作有误！%d删除失败！\n",*pVal);
		else
		{
			*pVal=pArr->pBase[pos-1];//要删除的元素
			for(i=pos;i<pArr->cnt;i++)
				pArr->pBase[i-1]=pArr->pBase[i];
			pArr->cnt--;
		}
	}
}

void InsertArray(struct Arr *pArr,int pos,int val)
{
	int i;
	if(1==IsFull(pArr))
		printf("数组已满，不能就行插入！\n");
	else
	{
		if(pos<1||pos>pArr->cnt)
			printf("插入操作有误！%d插入失败！\n",val);
		else
		{
			for(i=pArr->cnt-1;i>=pos-1;i--)
				pArr->pBase[i+1]=pArr->pBase[i];
			pArr->pBase[pos-1]=val;
			pArr->cnt++;
		}
	}
}

void SortArray(struct Arr *pArr)
{
	int i,j,t;
	for(i=0;i<pArr->cnt-1;i++)
	{
		for(j=0;j<pArr->cnt-i-1;j++)
		{
			if(pArr->pBase[j]>pArr->pBase[j+1])
			{
				t=pArr->pBase[j];
				pArr->pBase[j]=pArr->pBase[j+1];
				pArr->pBase[j+1]=t;
			}
			
		}
	}	
}

void InverseArray(struct Arr *pArr)
{
	int i,t;
	for(i=0;i<pArr->cnt/2;i++)
	{
		t=pArr->pBase[i];
        pArr->pBase[i]=pArr->pBase[pArr->cnt-i-1];
		pArr->pBase[pArr->cnt-i-1]=t;
	}
	return; 
}

void GetByPostion(struct Arr *pArr,int pos)
{
	if(1==IsEmpty(pArr))
		printf("数组为空！\n");
	else
	{
		if(pos<1||pos>pArr->cnt)
	    	printf("修改操作操作有误！\n");
		else
			printf("\n查找%d号位置的元素为：%d\n",pos,pArr->pBase[pos-1]);
	}
}

void ModifyArray(struct Arr *pArr,int pos,int val)
{
	if(1==IsEmpty(pArr))
		printf("数组为空！\n");
	else
	{
		if(pos<1||pos>pArr->cnt)
			printf("修改操作操作有误！\n");
		else
			pArr->pBase[pos-1]=val;
	}
}

注意：

1.数组为空

2.数组越界

3.进行增删改查时的位置及范围

结束语

有关数组的相关操作就写到这，若文中有不妥或有误的地方还请指点。 明天开始学习数据结构中最基本也是非常重要的线性结构中的离散存储结构---链表