[数据结构与算法]顺序表-基本操作

数据结构学习整理-顺序表

动态的增加表空间-动态顺序表

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

//动态顺序表结构体
#define InitSize 10
#define IncreaseSize 10
typedef struct{
	int *elem;//数组指针变量 
	int length;//当前已经占用的长度 
	int SqlSize;//当前分配的内存空间大小 
}SqList;

/*
	动态分配内存空间方式：
	1、初始分配:SqList L;
				L.elem = (int *) malloc (InitSize * sizeof(int));
	2、增加内存空间：
				L.elem = (int *) realloc (L.elem,((L.SqlSize + IncreaseSize)) * sizeof(int)));
					
*/
//创建顺序表-带参数
SqList CreateSql();

//遍历输出顺序表中数据
void PrintfSql(SqList L);

//输出指定位置的元素
void PrintfById(SqList L,int i);

//删除指定位置的元素
void DeleteById(SqList &L,int i,int &e);

//向指定位置添加元素
void InsertById(SqList &L,int i,int e);

//将第n个元素数据值修改为指定值
void ModifyById(SqList &L,int i,int e);

//查找与指定值相等数据的个数
int CountByValue(SqList L,int e);

//主函数如下：
int main(){
	//begin
	//创建顺序表L 
	SqList L = CreateSql();
	printf("遍历输出顺序表L：");//输出 
	PrintfSql(L);
	
	//输出指定位置的元素值
	int i;
	printf("输入指定输出为位置：");
	scanf("%d",&i);//输入 
	PrintfById(L,i);
	printf("\n");
	
	//删除指定位置的元素,并将 其赋值给e 
	int j,e;
	printf("输入指定删除的位置：");
	scanf("%d",&j);
	DeleteById(L,i,e);
	printf("删除的元素值为：%d\n",e); 
	printf("删除第%d个元素后的顺序表为：",j);
	PrintfSql(L);
	
	//向指定位置k处插入元素值a
	int k,a;
	printf("输入插入的位置k和插入的元素值a：");
	scanf("%d %d",&k,&a);
	InsertById(L,k,a);
	printf("向L表的第%d位置插入%d后的顺序表为：",k,a);
	PrintfSql(L);
	
	//将第n个元素数据值修改为指定值data 
	int n,data;
	printf("输入修改位n值和指定的数据data：");
	scanf("%d %d",&n,&data);
	ModifyById(L,n,data);
	printf("修改后的顺序表为：");
	PrintfSql(L);
	
	//查找与指定值相等数据的个数
	int count = 0;
	int s;//指定值s
	printf("输入需要查找的值S：");
	scanf("%d",&s);
	count = CountByValue(L,s);
	printf("顺序表L中与s值相等的元素有%d个\n",count);
	
	//输出表的基本数据信息
	printf("输出表L的借本信息如下：");
	printf("表长为%d,总的表空间为%d,未分配元素的表空间为%d",L.length,L.SqlSize,L.SqlSize-L.length); 
	//over 
	return 0;	
} 
//创建顺序表L
SqList CreateSql(){
	SqList P;
	P.length = 0;
	if((P.elem = (int *) malloc (InitSize * sizeof(int))) == NULL){
		printf("内存空间分配失败！！");
		exit(1);//异常退出 
	}
	P.SqlSize = InitSize;
	for(int i = 0; i <= 30;i++){
		if(P.length >= P.SqlSize){
			printf("内存空间不足，需增加空间！\n");
			int k = 31 - P.SqlSize;
			int temp = 1;//用于添加增量的倍数，以便于一次性添加完成 
			if(k % IncreaseSize == 0){
				temp = k / IncreaseSize;
			}
			else{
				temp = k / IncreaseSize + 1;
			}
			if(!((P.elem = (int *) realloc 
			(P.elem,((P.SqlSize + k * IncreaseSize) * sizeof(int))))))
			{
				printf("分配空间失败！！！");
				exit(1);//异常退出
			}
			Sleep(3000);
			printf("内存增加成功！\n");
			Sleep(1500);
			P.SqlSize = P.SqlSize + temp * IncreaseSize;
		}
		P.elem[i] = i;
		P.length ++;
	}
	return P; 
} 

//遍历输出顺序表
void PrintfSql(SqList L){
	for(int i = 0;i < L.length;i++){
		printf("%d ",L.elem[i]);
	}
	printf("\n");
} 

//输出指定位置的数据元素值
void PrintfById(SqList L,int i){
	if(i < 1 || i > L.length){
		printf("指定位置不符合！");
		exit(1);//退出
	}
	printf("顺序表的第%d个数据元素是：%d",i,L.elem[i - 1]);
}
 
//删除指定位置的元素 
void DeleteById(SqList &L,int i,int &e){
	if(i < 1 || i > L.length){
		printf("删除位置不符合！！");
		return; 
	}
	e = L.elem[i - 1];//将待删除的元素值赋值予e
	//从第i+1 开始依次向前移动一个位置
	for(int j = i; j < L.length;j++){
		L.elem[j - 1] = L.elem[j];
	} 
	L.length--;//表长减一  
}

//在指定位置插入元素
void InsertById(SqList &L,int i,int e){
	if(L.length == L.SqlSize){
		printf("表空间已满，需要再次分配表空间！");
		if(!(L.elem = (int *) realloc (L.elem,((L.SqlSize + IncreaseSize) *sizeof(int))))){
			printf("空间分配失败！！");
			exit(1);//异常退出
		}
		Sleep(2000);//睡眠两秒
		printf("空间已分配成功！");
		Sleep(1200);
		L.SqlSize = L.SqlSize + IncreaseSize; 
	}
	//将第i个元素之后的向后移动一个单位空间
	for(int j = L.length; j >= i; j--){
		L.elem[j] = L.elem[j-1];
	} 
	L.elem[i-1] = e;//将第i个赋值e
	L.length++;//表长加一 
}

//修改第i个数据为e 
void ModifyById(SqList &L,int i,int e){
	//判断i是否越界和线性表是否为空
	if(i < 1 || i > L.length || L.length == 0){
		printf("位置i越界或者线性表为空！！");
		return;
	}
	L.elem[i -1] = e; 
} 

//查找与给定值相等的元素个数
int CountByValue(SqList L,int e){
	if(L.length == 0){
		return 0;
	}
	int count = 0;
	for(int i = 0; i < L.length ; i++){
		if(L.elem[i] == e){
			count++;
		}
	}
	return count;
}