动态顺序表的实现

本文实现语言：c语言

上篇文章回顾

动态顺序表的结构：

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1

//---------------SeqList.h----------------------
//  #pragma once  //防止头文件的多次引用

#include<assert.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef int DataType;
#define CapaCity 6  //定义一个容量，后面可以改变

//动态顺序表的结构
typedef struct SeqList
{
	DataType *arr;  //数据块指针
	size_t size;   //顺序表的实际长度
	size_t capacity;//容量
}SeqList, *pSeqList;

//一堆函数声明
void SeqListInit(pSeqList s);  //初始化
void CheckCapacity(pSeqList s);//判断数组容量是否已满，已满进行扩容
void SeqListPrint(const pSeqList s);//打印
void SeqListDestory(pSeqList s);  //销毁
void SeqListClear(pSeqList s);   //清空
void SeqListPushFront(pSeqList s, DataType x);//头插
void SeqListPushBack(pSeqList s, DataType x);// 尾插
void SeqListInsert(pSeqList s, size_t pos, DataType x);//任意位置插入
void SeqListPopFront(pSeqList s);//头删
void SeqListPopBack(pSeqList s);//尾删
void SeqListEarse(pSeqList s, size_t pos);//指定任意位置删除
int SeqListEmpty(pSeqList s);//判断是否为空
int SeqListFind(pSeqList s, DataType x);//查找，找到第一个遇到的书下标，没有就返回-1
void SeqListModify(pSeqList s, size_t pos, DataType x);//修改指定下标的数字
int SeqListSize(pSeqList s);//返回顺序表的数量
void SeqListRemove(pSeqList s, DataType x);//删除指定的数字，只删除第一个
void SeqListRemoveAll(pSeqList s, DataType x);//删除指定的数字，删除所有的
void SeqListBubbleSort(pSeqList s);//冒泡排序
int SeqListBinarary(pSeqList s, DataType x); //二分查找



//-------------------SeqList.c---------------------------
//初始化
void SeqListInit(pSeqList s)
{
	//1,对指针进行断言，判断指针不为空
	assert(s);
	//2,初始化数组指针
	s->arr = (DataType*)malloc(sizeof(DataType)*CapaCity);
	assert(s->arr);//malloc函数调用完后得检测指针是否为NULL，为NULL表示未能成功分配存储空间
	//3.设置数组
	s->size = 0;
	s->capacity = CapaCity;
}

//判断数组容量是否已满，已满进行扩容
void CheckCapacity(pSeqList s)
{
	assert(s);
	if (s->size < s->capacity)
	{
		return;
	}
	else 
	{
		s->arr = (DataType*)realloc(s->arr, sizeof(DataType)*s->capacity * 2);
		assert(s->arr);
		s->capacity *= 2;
		printf("扩容成功\n");
	}
}

//打印
void SeqListPrint(const pSeqList s)
{
	assert(s);
	size_t i = 0;
	for (i = 0; i < (s->size); i++)
	{
		printf("%d ", s->arr[i]);
	}
	printf("\n");
}

//销毁
void SeqListDestory(pSeqList s)
{
	//先释放空间，再至为NULL
	free(s->arr);
	s->arr = NULL;
	
	s->capacity = s->size = 0;
	printf("销毁成功\n");
}

//清空
void SeqListClear(pSeqList s)
{
	assert(s);
	SeqListInit(s);
}

//头插
void SeqListPushFront(pSeqList s, DataType x)
{
	SeqListInsert(s, 0, x);
}

// 尾插
void SeqListPushBack(pSeqList s, DataType x)
{
	SeqListInsert(s, s->size, x);
}

//任意位置插入
void SeqListInsert(pSeqList s, size_t pos, DataType x)
{
	assert(s);
	//断言输入的位置是否合理
	assert(pos >= 0 && pos <= s->size);
	//判断数组是否已经满了
	CheckCapacity(s);

	DataType end = s->size;
	while (end > (DataType)pos) {
		s->arr[end] = s->arr[end - 1];
		end--;
	}
	s->arr[pos] = x;
	s->size++;

}


//头删
void SeqListPopFront(pSeqList s)
{
	assert(s);
	//判断顺序表是否为空
	if (0 == s->size)
	{
		printf("顺序表为空，无法删除\n");
		return;
	}
	else {
		size_t tmp = 0;
		while (tmp < s->size - 1)
		{
			s->arr[tmp] = s->arr[tmp + 1];
			tmp++;
		}
		s->size--;
	}
}

//尾删
void SeqListPopBack(pSeqList s)
{
	assert(s);
	if (0 == s->size)
	{
		printf("顺序表为空，无法删除\n");
		return;
	}
	else {
		s->size--;
	}

}

//指定任意位置删除
void SeqListEarse(pSeqList s, size_t pos)
{
	assert(s);
	//判断顺序表是否为空
	if (0 == s->size)
	{
		printf("顺序表为空，无法删除\n");
		return;
	}
	else {
		size_t tmp = pos;
		while (tmp < s->size - 1)
		{
			s->arr[tmp] = s->arr[tmp + 1];
			tmp++;
		}
		s->size--;
	}

}

//判断是否为空
int SeqListEmpty(pSeqList s)
{
	assert(s);
	return s->size > 0 ? 1 : 0;

}

//查找，找到第一个遇到的书下标，没有就返回-1
int SeqListFind(pSeqList s, DataType x)
{
	assert(s);
	//判断数组是否为空
	if (0 == s->size)
	{
		printf("顺序表为空，无法查找\n");
		return -1;
	}

	//遍历查找法
	size_t i = 0;
	for (i = 0; i < s->size; i++)
	{
		if (x == s->arr[i])
		{
			return i;
		}
	}
	return -1;

}

//修改指定下标的数字
void SeqListModify(pSeqList s, size_t pos, DataType x)
{
	assert(s);
	s->arr[pos] = x;
}

//返回顺序表的数量
int SeqListSize(pSeqList s)
{
	assert(s);
	return s->size;
}

//删除指定的数字，只删除第一个
void SeqListRemove(pSeqList s, DataType x)
{
	assert(s);
	size_t pos = SeqListFind(s, x);
	if (-1 == pos)
	{
		printf("没有这个数字存在\n");
	}
	else {
		SeqListEarse(s, pos);
	}
}

//删除指定的数字，删除所有的
void SeqListRemoveAll(pSeqList s, DataType x)
{
	assert(s);

	//第一种方法
	//size_t pos = -1;
	//while (-1 != (pos = SeqListFind(s, x)))
	//{
	//	SeqListEarse(s, pos);
	//}


	//第二种方法:一次遍历删除
	int i, j;
	for (i = 0, j = 0; i < s->size; i++) {
		if (x != s->arr[i]) {
			s->arr[j] = s->arr[i];
			j++;
		}
	}
	s->size = j;

}

//冒泡排序
void SeqListBubbleSort(pSeqList s)
{
	assert(s);

	DataType i = 0, j = 0;
	for (j = 0; j < s->size - 1; j++)
	{
		size_t flag = 0;
		for (i = 0; i < s->size - 1 - j; i++)
		{
			if (s->arr[i] > s->arr[i + 1])
			{
				DataType tmp = s->arr[i];
				s->arr[i] = s->arr[i + 1];
				s->arr[i + 1] = tmp;
				flag = 1;//只要发生了交换就让flag = 1；
			}
		}
		if (0 == flag)
		{
			return;
		}
	}
}

//二分查找（前提，数组得有序，所以会改变数组元素的位置）
int SeqListBinarary(pSeqList s, DataType x)
{
	assert(s);
	SeqListBubbleSort(s);
	int left = 0;
	int right = s->size - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = (right + left) >> 2;
		if (x == s->arr[mid])
		{
			return mid;
		}
		else if (x > mid)
		{
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	if (right < left) {
		return -1;
	}
}


//------------------------------test.c---------------------------

void Test()
{
	SeqList s;
	SeqListInit(&s);//初始化
	SeqListPushFront(&s, 1);//头插
	SeqListPushFront(&s, 2);//头插
	SeqListPushFront(&s, 1);//头插
	SeqListPushFront(&s, 4);//头插
	SeqListPrint(&s);// 打印

	SeqListPushBack(&s, 1);//尾插
	SeqListPushBack(&s, 5);//尾插
	SeqListPushBack(&s, 3);//尾插
	SeqListPushBack(&s, 1);//尾插
	SeqListPrint(&s);// 打印

	SeqListPopFront(&s);//头删
	SeqListPrint(&s);// 打印

	SeqListPopBack(&s);//尾删
	SeqListPrint(&s);// 打印

	SeqListInsert(&s, 2, 9);//任意位置插
	SeqListPrint(&s);// 打印

	SeqListEarse(&s, 3);//任意位置删
	SeqListPrint(&s);// 打印

	SeqListModify(&s, 2, 3);//修改
	SeqListPrint(&s);// 打印

	int num = SeqListFind(&s, 3);//查找
	if (num != -1)
		printf("找到了，下标%d\n", num);
	else
		printf("该数不存在\n");

	int n = SeqListEmpty(&s);// 判断是否为空，1 表示空， 0 表示不空 
	if (n == 0)
		printf("为空\n");
	else
		printf("不为空\n");

	int count = SeqListSize(&s);// 返回数量 
	printf("顺序表个数为%d\n", count);

	SeqListRemove(&s, 3);//删除第一个x
	SeqListPrint(&s);// 打印

	SeqListRemoveAll(&s, 1);//删除所有x
	SeqListPrint(&s);// 打印

	SeqListClear(&s);// 清空 
	SeqListPrint(&s);// 打印

	SeqListPushFront(&s, 1);//头插
	SeqListPushFront(&s, 4);//头插
	SeqListPushFront(&s, 9);//头插
	SeqListPushFront(&s, 6);//头插
	SeqListPrint(&s);// 打印

	SeqListBubbleSort(&s);//冒泡排序
	SeqListPrint(&s);// 打印

	int ret = SeqListBinarary(&s, 0);//二分查找
	if (ret != -1)
		printf("找到了，下标为%d\n", ret);
	else
		printf("没找到\n");

	SeqListDestory(&s);
}



int main()
{
	Test();
	system("pause");
	return 0;
}