靜態順序表和動態順序表

實現一個靜態順序表，首先，要定義一個保存數據的數組，保存在結構體中，用size來存儲數組中的元素個數，

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));
	}
}
其他函數的實現大致都是類似的，只是動態開辟空間，在涉及到元素插入刪除時需要檢查容量