顺序表操作详解

typedef struct vector {//结构体定义
	int size, count;//size为数组大小，count为数组存储元素个数
	int* data;//data为数组
}vector;//重命名为vector

vector* InitNewVector(int n)//结构体初始化，n为开辟空间大小
{
	vector* v = (vector*)malloc(sizeof(vector));//开辟这个结构体
	v->size = n;//记录空间大小为n
	v->count = 0;//此时数组内部没有元素
	v->data = (int*)malloc(sizeof(int) * n);//动态数组开辟空间
	return v;//返回开辟好的结构体
}

void clearVector(vector* v)//销毁顺序表，传入顺序表指针
{
	if (v == NULL)
		return;
	free(v->data);//先free掉顺序表内部动态开辟的数组
	free(v);//再将顺序表给销毁
	return;
}

int insert(vector* v, int pos, int val)//插入操作，对pos位置插入val值
{
	if (v->size < pos || pos < 0) return 0;//排除错误情况
	if (v->size == pos)//当数组满了也需要进行判断
		return 0;//返回0代表插入失败
	for (int i = v->count - 1; i >= pos; i--)//数组进行插入前需要将要插入位置之后的数据都往后移动一个单位
		v->data[i + 1] = v->data[i];//向后移动
	v->data[pos] = val;//此时pos位置的值已经被空下来了直接插入就行
    v->count += 1;//插入完之后数组元素个数进行记录一下
	return 1;//返回1代表插入成功
}

int delete(vector* v, int pos)//传入结构体指针与要删除的位置
{
	if (v == NULL) return 0;
	if (pos < 0 || v->size < pos)//排除边界情况
		return 0;
	for (int i = pos + 1; i < v->count; i++)//进行元素删除
		v->data[i - 1] = v->data[i];
	v->count -= 1;//删除完元素个数减一
	return 1;//删除成功返回1
}

int main()
{
	srand((unsigned int)time(NULL));//产生伪随机
	vector* v = InitNewVector(2);//初始化生成顺序表

    #define MAX_OP 10
	for (int i = 0; i < MAX_OP; i++)//进行数据操作的此数
	{
		int pos, val, op = rand() % 5;//pos为位置，val为待插入值，op为概率分配任务，在0-4之间分配任务随机产生数字
		switch (op)//经过op分发任务删除概率为20%,插入概率为80%
		{
	    	case 0:
		    {
			    pos = rand() % (v->count + 1);//插入位置进行随机
    			printf("Delete item %d at vector! = %d\n"
	    		, pos, delete(v, pos));
		    	break;
    		}
	    	case 1:
		    case 2:
    		case 3:
	    	case 4:
		    {
    			pos = rand() % (v->count + 1);
	    		val = rand() % 100 + 1;
		    	printf("Insert %d to %d at vector! = %d\n"
			   	, val, pos, insert(v, pos, val));
    			break;
	    	}
		}
		output(v);//打印函数，最后每次插入都会进行打印
	}
	clearVector(v);//销毁顺序表
	return 0;
}

void output(vector* v)//顺序表输出操作
{
	if (v == NULL)
		return;

	int len = 0;
	for (int i = 0; i < v->count; i++)
	len += printf("%3d", i);

	printf("\n");
	for (int i = 0; i < len; i++)
	printf("-");

	printf("\n");
	for (int i = 0; i < v->count; i++)
	printf("%3d", v->data[i]);

	printf("\n");
	printf("\n");
	printf("\n");

	return;
}

int insert(vector* v, int pos, int val)
{
	if (v->size < pos || pos < 0) return 0;
	if (v->size == pos  && !expand(v))//在这里进行扩容判断，如果扩容成功则继续插入操作否则return 0
		return 0;

	for (int i = v->count - 1; i >= pos; i--)
		v->data[i + 1] = v->data[i];

	v->count += 1;
	v->data[pos] = val;

	return 1;
}

int expand(vector* v)
{
	if (v == NULL)
		return 0;

	int *tmp = (int *)realloc(v -> data, sizeof(v->size) * 2 * sizeof(int));//指针变量接收realloc后的值防止扩容失败造成崩溃
	if (tmp == NULL)//对realloc函数是否扩容成功进行检查
	{
		perror("realloc");
		return 0;
	}
	v->data = tmp;
		
	printf("Expand %d from %d at vector!\n", v->size, v->size * 2);//扩容成功进行提示
	v->size *= 2;//将容量进行相同倍数扩大

	return 1;//成功返回1
}