静态顺序表和动态顺序表

实现一个静态顺序表，首先，要定义一个保存数据的数组，保存在结构体中，用size来存储数组中的元素个数，

创新互联-专业网站定制、快速模板网站建设、高性价比婺城网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式婺城网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖婺城地区。费用合理售后完善，十载实体公司更值得信赖。

typedef struct SeqList
{
DataType array[MAX_SIZE];
size_t size;
}SeqList;

首先来实现一下静态顺序表的初始化函数，可以借用系统的memset函数来实现，开辟一块空间全部初始化为0，没有存入数据所以size也为0

void InitSeqList(SeqList *pSeq)
{
assert(pSeq);
memset(pSeq->array, 0, sizeof(DataType)*MAX_SIZE);
pSeq->size = 0;
}

然后简单的实现一下尾插的函数，把顺序表和需要插入的数据传给函数

void PushBack(SeqList *pSeq, DataType x)
{
    assert(pSeq);//断言顺序表
    if (pSeq->size >= MAX_SIZE)//判断顺序表是否已满，满的话就输出这个顺序表已满并返回程序
{
printf("The SeqList is Full.\n");
return;
}
pSeq->array[pSeq->size++] = x;//把需要尾插的数据插入顺序表末尾的下一个元素
}
尾删函数，只需要把顺序表传给函数，
void PopBack(SeqList *pSeq)
{
assert(pSeq);//断言，养成良好的代码习惯，方便出错时的检查工作
if (pSeq->size array[pSeq->size] = 0;//将顺序表的最后一个元素置为0，
--pSeq->size;//size减一
}
实现简单的头插函数
void PushFront(SeqList *pSeq, DataType x)
{
int begin = pSeq->size;//保存顺序表的元素个数
	assert(pSeq);
	if (pSeq->size >= MAX_SIZE)
	{
		printf("The SeqList is Full.\n");
		return;
	}
for (; begin >= 0; --begin)//从顺序表末尾开始移动元素，把第一个元素的位置空出来
	{
		pSeq->array[begin] = pSeq->array[begin - 1];
	}
pSeq->array[0] = x;//将第一个位置插入需要插入的元素
pSeq->size++;//size加一
}
简单的头删函数，原理与头插相似，从第一个位置开始移动元素，覆盖第一个位置，将size减一
void PopFront(SeqList* pSeq)
{
	int begin = 0;
	assert(pSeq);
	if (pSeq->size <= 0)
	{
		printf("The SeqList is NULL");
		return;
	}
	for (; begin size; begin++)
	{
		pSeq->array[begin] = pSeq->array[begin + 1];
	}
	pSeq->size--;
}
//实现一个查找函数，如果找到了，就返回它的下标，如果没找到，就返回-1
int Find(SeqList* pSeq, size_t pos, DataType x)
{
	int i = 0;
	assert(pSeq);
	for (; i < pSeq->size; ++i)
	{
		if (pSeq->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//插入函数，从顺序表末尾开始向后挪动元素，直到pos位置，将pos位置空出来插入元素
void Insert(SeqList* pSeq, int pos, DataType x)
{
	int begin = pSeq->size-1;
	assert(pSeq);
	assert(pos size);
	if (pos >= MAX_SIZE)
	{
		printf("The SeqList is Full");
		return;
	}
	for (; begin >= pos; begin--)
	{
		pSeq->array[begin+1] = pSeq->array[begin];
	}
	pSeq->array[pos] = x;
	pSeq->size++;
}
//删除函数
void Erase(SeqList* pSeq, size_t pos)
{
	assert(pSeq);
	if (pSeq->size<0)
	{
		printf("The SeqList is empty\n");
		return;
	}
	assert(pos < pSeq->size);
int i = pos;//定义一个i用开保存当前位置
for (; i < pSeq->size; i++)//从当前位置开始向后，依次用之后的元素覆盖前面的元素，达到删除它的作用
	{
		pSeq->array[i] = pSeq->array[i + 1];
	}
	--(pSeq->size);
}
//删除指定元素
int Remove(SeqList* pSeq, DataType x)
{
	int pos;
	assert(pSeq);
	if (pSeq->size size <= 0)
	{
		printf("The SeqList is empty\n");
		return;
	}
	pos = Find(pSeq, 0, x);
	while (pos != -1)
	{
		Erase(pSeq, pos);
pos = Find(pSeq, pos,x);//把顺序表，当前位置和要删除的元素传给Find函数，循环查找删除，直到把该元素全部删除
	}
}
//但上面那种方法不够高效，没删除一次就需要把之后的元素全部向前挪动一次，频繁的挪动导致该函数比较低效，用count计数，计算每个元素前出现几次需要删除的元素，就将该元素向前挪动几个位置
void RemoveAll(SeqList* pSeq, DataType x)
{
	int count = 0;
	int begin = 0;
	assert(pSeq);
	for (; begin < pSeq->size; ++begin)
	{
		if (pSeq->array[begin] == x)
		{
			++count;
		}
		else
		{
			pSeq->array[begin-count] = pSeq->array[begin];
		}
	}
	
pSeq->size -= count;
}
//冒泡排序函数，参考数组的冒泡排序
void Bubblesort(SeqList* pSeq)//冒泡排序
{
	assert(pSeq);
	int i = 0;
	int j = 0;
	for (; i < pSeq->size;i++)
	{
		for (j = 0; j < pSeq->size - i; j++)
		{
			if (pSeq->array[j] < pSeq->array[j - 1])
			{
				DataType temp;
				temp = pSeq->array[j - 1];
				pSeq->array[j-1] = pSeq->array[j] ;
				pSeq->array[j] = temp;
			}
		}
	}

}
//选择排序函数
void Selectsort(SeqList* pSeq)
{	
	assert(pSeq);
	int i = 0;
	int j = 0;
	int min = 0; 
	for (j = 0; j < pSeq->size - 1; ++j)
	{
		min = j;
		for (i = j + 1; i < pSeq->size; ++i)
		{
			if (pSeq->array[i] < pSeq->array[min])
			{
				min = i;
			}
		}
		Swap(&pSeq->array[min], &pSeq->array[j]);
	}
	
}
//但上面那个函数比较低效，我在下面实现了一个选择排序函数，每次循环可以找出最大值和最小值，有效的减少循环次数，提该函数效率
void Selectsort_OP(SeqList* pSeq)
{	
	int i = 0;
	int min = 0;
	int max = 0;
	int left = 0;
	int right = pSeq->size - 1;
	assert(pSeq);
	while (left < right)
	{
		min= left;
		max = right;
		for (i = left; i array[i] < pSeq->array[min])
			{
				Swap(&pSeq->array[i], &pSeq->array[left]);
			}
			if (pSeq->array[i] > pSeq->array[max])
			{
				Swap(&pSeq->array[i], &pSeq->array[right]);
			}
		}
		left++;
		right--;
	}
}
//在下面，我简单的实现了一下二分查找，一定要注意循环条件
int Binarysearch(SeqList* pSeq, DataType x)
{
	assert(pSeq);
	int left = 0;
	int right = pSeq->size - 1;
	while (left <= right)
	{
int mid = left - (left - right) / 2;//避免了溢出的问题
		if (x < pSeq->array[mid])
		{
			right = mid;
		}
		else if (x > pSeq->array[mid])
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}
//下面，是动态顺序表的各个函数的简单实现
typedef struct SeqList
{
	DataType* array;   //数据块指针
	size_t size;       //当前有效数据个数
	size_t capicity;   //容量
}SeqList;
//这个是检查容量，不够时动态开辟空间的函数，借助了系统的relloc函数
void CheckCapicity(SeqList* pSeq)
{
	if (pSeq->size >= pSeq->capicity)
	{
		pSeq->capicity = 2 * pSeq->capicity;
		pSeq->array = (DataType *)realloc(pSeq->array, pSeq->capicity*sizeof(DataType));
	}
}
其他函数的实现大致都是类似的，只是动态开辟空间，在涉及到元素插入删除时需要检查容量

本文名称：静态顺序表和动态顺序表
文章网址：http://mswzjz.cn/article/ppdpii.html