连续存储——动态数组及相关操作实现

数组

——连续存储

• 什么是数组？

  • 元素类型相同 大小相等
  • 在内存内连续存放

• 数组的优缺点

  • 优点

    • 存储元素的效率高

  • 缺点

    • 事先要知道数组的长度
    • 需要大块连续的内存空间
    • 插入删除的操作效率低

• 动态创建数组

  • 相关操作实现

    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    //定义结构体Arr（数组）
    struct Arr
    {
    	int * pBase;	//第一个元素的地址
    	int cnt;		//当前元素在第几个
    	int max;		//最多能储存多少个元素
    };
    
    void InitArr(struct Arr *,int);			//数组初始化
    bool IsEmpty(struct Arr *);				//判断数组是否为空		
    bool IsFull(struct Arr *,int);			//判断数组是否满
    void showArr(struct Arr *);				//输出数组所有元素
    bool append(struct Arr *,int);			//在数组末尾插入元素
    bool insertArr(struct Arr *,int,int);	//在数组第i个位置前插入元素
    bool deleteArr(struct Arr * pArr,int pos,int * val);//删除第i个元素
    void inverseArr(struct Arr *) ;			//将数组倒序输出
    void sort(struct Arr *);				//将数组元素从小到大排序
    
    int main()
    {
    	struct Arr Arr;
    	int len;
    	int val;
    	
    	//用户输入要创建的数组长度
    	printf("请输入要创建数组的长度:");
    	scanf("%d",&len);
    	
    	//初始化
    	InitArr(&Arr,len);
    	
    	//用户依次输入元素
    	for(int i = 0;i<5;i++)
    	{
    		printf("请输入您要添加的数：");
    		scanf("%d",&val); 
    		if(append(&Arr,val))
    		{
    			printf("追加%d成功\n",val);
    		}
    		else
    		{
    			printf("追加失败\n");
    			exit(-1);	
    		} 
    	}
    	//输出数组所有元素
    	showArr(&Arr);
    	//输出数组的相关信息，当前长度和数组最大长度
    	printf("cnt:%d max:%d\n",Arr.cnt,Arr.max);
    	
    	printf("inserArr()测试---------------\n");
    	//在第二个位置插入1000
    	if(insertArr(&Arr,2,1000))
    	{
    		printf("插入成功"); 
    	}
    	else
    	{
    		printf("插入失败");
    	}
    	
    	showArr(&Arr);
    	printf("cnt:%d max:%d\n\n",Arr.cnt,Arr.max);
    	
    	printf("deleteArr()测试---------------\n");
    	//将第二个位置的元素删除
    	if(deleteArr(&Arr,2,&val))
    	{
    		printf("删除 %d 成功\n",val);
    	}
    	else
    	{
    		printf("删除失败");	
    	}
    
    	showArr(&Arr);
    	printf("cnt:%d max:%d\n\n",Arr.cnt,Arr.max);
    	
    	printf("inverseArr()测试---------------\n");
    	//将数组倒序输出
    	inverseArr(&Arr);
    	showArr(&Arr);
    	printf("cnt:%d max:%d\n\n",Arr.cnt,Arr.max);
    	
    	printf("sort()测试---------------\n");
    	//数组排序
    	sort(&Arr);
    	showArr(&Arr);
    	printf("cnt:%d max:%d\n\n",Arr.cnt,Arr.max);
    	return 0;
    } 
    
    void InitArr(struct Arr * pArr,int length)
    {
    	pArr->pBase = (int *)malloc(sizeof(int)*length);
    	if(pArr == NULL )
    	{
    		printf("空间不足，分配失败");
    		exit(-1);
    	}
    	else
    	{
    		pArr->cnt = 0;
    		pArr->max = length;
    	} 
    	return;//：InitArr函数结束 
    }
    
    bool isEmpty(struct Arr * pArr)
    {
    	if(pArr->cnt == 0)
    	{
    		return true; 
    	}
    	else
    	{
    		return false;
    	}
    }
    
    bool isFull(struct Arr * pArr)
    {
    	if(pArr->cnt>pArr->max||pArr->cnt==pArr->max)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    
    }
    
    void showArr(struct Arr * pArr)
    {
    	if(isEmpty(pArr))
    	{
    		printf("数组为空！\n"); 
    	}
    	else
    	{
    		for(int i = 0;i < pArr->cnt; i++)
    		{
    			printf("%d ",pArr->pBase[i]);
    		}
    		printf("\n");
    	}
    	
    }
    bool append(struct Arr * pArr,int val)
    {
    	if(isFull(pArr))
    	{
    		printf("数组以满\n"); 
    	}
    	else
    	{
    		pArr->pBase[pArr->cnt] = val;
    		pArr->cnt++;
    		return true;
    	}
    }
    
    bool insertArr(struct Arr * pArr,int pos,int val)
    {
    	if(isFull(pArr))
    	{
    		printf("数组以满\n"); 
    		exit(-1);
    	}
    	else if(pos<=0||pos>pArr->cnt)
    	{
    		printf("sorry,请在%d-%d范围内插入",1,pArr->cnt);
    		exit(-1);
    	}
    	else{
    		for(int 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 deleteArr(struct Arr * pArr,int pos,int * val)
    {
    	if(isEmpty(pArr))
    	{
    		printf("数组为空！\n"); 
    		return false;
    	}
    	else if(pos<1||pos>pArr->cnt)
    	{
    		printf("请输入有效位置%d-%d\n",1,pArr->cnt);
    		return false;
    	}
    	else
    	{
    		*val = pArr->pBase[pos-1];
    		for(int i = pos;i < pArr->cnt;i++)
    		{
    			pArr->pBase[i-1] = pArr->pBase[i];
    		}
    		pArr->cnt--;
    		return true;
    	}
    	
    }
    
    void inverseArr(struct Arr * pArr)
    {
    	int t;
    	int i = 0;
    	int j = pArr->cnt-1;
    	while(i<j)
    	{
    		t = pArr->pBase[i];
    		pArr->pBase[i] = pArr->pBase[j];
    		pArr->pBase[j] = t;
    		i++;
    	j--;
    	}
    	return;
    }
    
    void sort(struct Arr * pArr)
    {
    	int t;
    	for(int i = 0;i<pArr->cnt;i++)
    	{
    		for(int j = 0;j<pArr->cnt-i;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;
    			}
    		}
    	}
    }