靜態(tài)順序表和動(dòng)態(tài)順序表

實(shí)現(xiàn)一個(gè)靜態(tài)順序表，首先，要定義一個(gè)保存數(shù)據(jù)的數(shù)組，保存在結(jié)構(gòu)體中，用size來存儲數(shù)組中的元素個(gè)數(shù)，

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

首先來實(shí)現(xiàn)一下靜態(tài)順序表的初始化函數(shù)，可以借用系統(tǒng)的memset函數(shù)來實(shí)現(xiàn)，開辟一塊空間全部初始化為0，沒有存入數(shù)據(jù)所以size也為0

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

然后簡單的實(shí)現(xiàn)一下尾插的函數(shù)，把順序表和需要插入的數(shù)據(jù)傳給函數(shù)

void PushBack(SeqList *pSeq, DataType x)
{
    assert(pSeq);//斷言順序表
    if (pSeq->size >= MAX_SIZE)//判斷順序表是否已滿，滿的話就輸出這個(gè)順序表已滿并返回程序
{
printf("The SeqList is Full.\n");
return;
}
pSeq->array[pSeq->size++] = x;//把需要尾插的數(shù)據(jù)插入順序表末尾的下一個(gè)元素
}
尾刪函數(shù)，只需要把順序表傳給函數(shù)，
void PopBack(SeqList *pSeq)
{
assert(pSeq);//斷言，養(yǎng)成良好的代碼習(xí)慣，方便出錯(cuò)時(shí)的檢查工作
if (pSeq->size array[pSeq->size] = 0;//將順序表的最后一個(gè)元素置為0，
--pSeq->size;//size減一
}
實(shí)現(xiàn)簡單的頭插函數(shù)
void PushFront(SeqList *pSeq, DataType x)
{
int begin = pSeq->size;//保存順序表的元素個(gè)數(shù)
	assert(pSeq);
	if (pSeq->size >= MAX_SIZE)
	{
		printf("The SeqList is Full.\n");
		return;
	}
for (; begin >= 0; --begin)//從順序表末尾開始移動(dòng)元素，把第一個(gè)元素的位置空出來
	{
		pSeq->array[begin] = pSeq->array[begin - 1];
	}
pSeq->array[0] = x;//將第一個(gè)位置插入需要插入的元素
pSeq->size++;//size加一
}
簡單的頭刪函數(shù)，原理與頭插相似，從第一個(gè)位置開始移動(dòng)元素，覆蓋第一個(gè)位置，將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--;
}
//實(shí)現(xiàn)一個(gè)查找函數(shù)，如果找到了，就返回它的下標(biāo)，如果沒找到，就返回-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;
}
//插入函數(shù)，從順序表末尾開始向后挪動(dòng)元素，直到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++;
}
//刪除函數(shù)
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;//定義一個(gè)i用開保存當(dāng)前位置
for (; i < pSeq->size; i++)//從當(dāng)前位置開始向后，依次用之后的元素覆蓋前面的元素，達(dá)到刪除它的作用
	{
		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);//把順序表，當(dāng)前位置和要?jiǎng)h除的元素傳給Find函數(shù)，循環(huán)查找刪除，直到把該元素全部刪除
	}
}
//但上面那種方法不夠高效，沒刪除一次就需要把之后的元素全部向前挪動(dòng)一次，頻繁的挪動(dòng)導(dǎo)致該函數(shù)比較低效，用count計(jì)數(shù)，計(jì)算每個(gè)元素前出現(xiàn)幾次需要?jiǎng)h除的元素，就將該元素向前挪動(dòng)幾個(gè)位置
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;
}
//冒泡排序函數(shù)，參考數(shù)組的冒泡排序
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;
			}
		}
	}

}
//選擇排序函數(shù)
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]);
	}
	
}
//但上面那個(gè)函數(shù)比較低效，我在下面實(shí)現(xiàn)了一個(gè)選擇排序函數(shù)，每次循環(huán)可以找出最大值和最小值，有效的減少循環(huán)次數(shù)，提該函數(shù)效率
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--;
	}
}
//在下面，我簡單的實(shí)現(xiàn)了一下二分查找，一定要注意循環(huán)條件
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;
}
//下面，是動(dòng)態(tài)順序表的各個(gè)函數(shù)的簡單實(shí)現(xiàn)
typedef struct SeqList
{
	DataType* array;   //數(shù)據(jù)塊指針
	size_t size;       //當(dāng)前有效數(shù)據(jù)個(gè)數(shù)
	size_t capicity;   //容量
}SeqList;
//這個(gè)是檢查容量，不夠時(shí)動(dòng)態(tài)開辟空間的函數(shù)，借助了系統(tǒng)的relloc函數(shù)
void CheckCapicity(SeqList* pSeq)
{
	if (pSeq->size >= pSeq->capicity)
	{
		pSeq->capicity = 2 * pSeq->capicity;
		pSeq->array = (DataType *)realloc(pSeq->array, pSeq->capicity*sizeof(DataType));
	}
}
其他函數(shù)的實(shí)現(xiàn)大致都是類似的，只是動(dòng)態(tài)開辟空間，在涉及到元素插入刪除時(shí)需要檢查容量