动态顺序表----C语言实现

typedef int DataType;typedef struct SeqListD{	DataType* array;	size_t capacity;   // 空间的实际大小--存放元素的最大个数	size_t size;   //有效元素的个数}SeqListD, *PSeqListD;void InitSeqlistD(PSeqlistD seq)   //初始化动态顺序表{	assert(seq);	seq->array = (DataType*)malloc(CAPACITYSIZE*sizeof(DataType));	assert(seq->array);	seq->size = 0;	seq->capacity = CAPACITYSIZE;}int CheckCapacity(PSeqlistD seq)    //检查容量{	assert(seq);	if(seq->size ==seq->capacity)	{		DataType *ptmp = (DataType*)malloc((CAPACITYSIZE+seq->capacity)*sizeof(DataType));		if(ptmp ==NULL)		{			return 0;		}		seq->array = ptmp;		seq->capacity += CAPACITYSIZE;	}	return 1;}void PushBack(PSeqlistD seq,DataType data)     //后插动态顺序表{	assert(seq);	if(CheckCapacity(seq))	{		seq->array[seq->size++] = data;    }}void PushFront(PSeqlistD seq,DataType data)     //前插动态顺序表{	DataType idx = 0;	assert(seq);	if(CheckCapacity(seq))	{		for(idx=seq->size; idx>0; --idx)		{			seq->array[idx] = seq->array[idx-1];		}		seq->array[0] = data;    }}void Insert(PSeqlistD seq,DataType pos,DataType data)   //动态顺序表任意位置插入{	DataType idx = 0;	assert(seq);	for(idx = seq->size-1; idx>=pos; --idx)	{		seq->array[idx+1] = seq->array[idx];	}	seq->array[pos] = data;	seq->size++;}void Bubblesort(PSeqlist seq)   //冒泡排序{	DataType i = 0;	DataType j = 0;	DataType flag = 0;	assert(seq);	for(i=0; i<seq->size-1; ++i)	{		flag = 0;		for(j=0; j<seq->size-i-1; ++j)		{			if(seq->array[j]>seq->array[j+1])			{				DataType tmp = seq->array[j];				seq->array[j] = seq->array[j+1];				seq->array[j+1] = tmp;				flag = 1;			}		}		if(flag == 0)		{			break;         //防止当已排序成功但循环没有结束		}	}}void Secletsort(PSeqlist seq)  //选择排序法{	DataType i = 0;	DataType j = 0;	DataType pos = 0;	DataType tmp = 0;	assert(seq);	for(i=0; i<seq->size-1; ++i)	{		pos = 0;		for(j=1; j<seq->size-i; ++j)		{			if(seq->array[pos]<seq->array[j])			{				pos = j;			}		}			if(pos != seq->size-i)			{				tmp = seq->array[pos];				seq->array[pos] = seq->array[seq->size-i-1];				seq->array[seq->size-i-1] = tmp;			}	}}void Secletsort_OP(PSeqlist seq)    //优化后的选择排序法{             	DataType j = 0;	DataType begin = 0;	DataType end = 0; 	DataType maxPos = 0;	DataType minPos = 0;	DataType tmp = 0;	assert(seq);	end = seq->size-1;		while(begin<end)	{		maxPos = begin;		minPos = begin;				for(j=begin+1; j<=end; ++j)		{			if(seq->array[maxPos]<seq->array[j])			{								maxPos = j;			}						if(seq->array[minPos]>seq->array[j])			{								minPos = j;                        			}                                        		}		   			if(end != maxPos)			{				tmp = seq->array[maxPos];				seq->array[maxPos] = seq->array[end];				seq->array[end] = tmp;			}			if(begin != minPos)			{				tmp = seq->array[minPos];				seq->array[minPos] = seq->array[begin];				seq->array[begin] = tmp;				}				end--;				begin++;	}}int BinarySearch(PSeqlist seq,DataType data) //二分查找{	DataType left = 0;	DataType right = 0;	DataType mid = 0;	assert(seq);	right = seq->size;	while(left<right)	{		mid = left-((left-right)>>1);		if(seq->array[mid]>data)		{			right = mid;		}		else if(seq->array[mid]<data)		{			left = mid+1;		}		else		{			return mid;		}	}	return -1;}