C言語実装順序表

シーケンステーブルはC言語の基本的な構造であり、様々な基本タイプのデータを格納することができ、基本タイプのデータだけでなく、構造も格納することができる.したがって、順序表はCを学ぶ過程で身につけなければならない構造であり、学習整理を通じて、以下に実現する.
まず、まず何で実現するかを考えて、一般的に最も基本的な順序表を実現するには直接配列で実現して、私たちはここで1つの構造体でこの順序表をカプセル化します(カプセル化という概念はC++の中で最もよく使われる概念です)

#define ARRAY_EMPTY -2
#define ARRAY_FULL -1
#define MAX_SIZE 10000
typedef int Datatype;


typedef struct Seqlist
{
	Datatype array[MAX_SIZE];
	size_t size;
}Seqlist;

配列サイズを決定できない場合は、マクロで表すことができます.
大体の構造を構築した後、1つの順序表が持つべき機能、頭挿し、尾挿し、定点挿入、ソートなどが最も基本的な機能であることを考えることができます.

	void PrintSeqlist(Seqlist* pSeq);
	void InitSeqlist(Seqlist* pSeq);
	void PushBack(Seqlist* pSeq, Datatype x);
	void PushFront(Seqlist* pSeq, Datatype x);
	void PopBack(Seqlist* pSeq);
	void PopFront(Seqlist* pSeq);
	void Insert(Seqlist* pSeq,size_t pos, Datatype x);
	int Find(Seqlist* pSeq, size_t pos, Datatype x);
	void Erase(Seqlist* pSeq, size_t pos);
	int Remove(Seqlist* pSeq, Datatype x);
	int Removeall(Seqlist* pSeq, Datatype x);
	void Bubblesort(Seqlist* pSeq);
	void Selectsort(Seqlist* pSeq);
	int BinarySearch(Seqlist* pSeq, Datatype x);

次に、いくつかの重要な関数の実装を示します.

void PrintSeqlist(Seqlist* pSeq)//     
{
	assert(pSeq);
	size_t i = 0;
	if (pSeq->size <= 0)
	{
		printf("Array is empty
");
		return;
	}
	else if (pSeq->size >= MAX_SIZE)
	{
		printf("Array is full
");
	}
	for (; i < pSeq->size; ++i)
	{
		printf("%-4d", pSeq->array[i]);
	}
}

void InitSeqlist(Seqlist* pSeq)//      
{
	pSeq->size = 0;
	//printf("Initialization is complete
");
}

void PushBack(Seqlist* pSeq, Datatype x)//   
{
	assert(pSeq);
	if (pSeq->size >= MAX_SIZE)
	{
		printf("Array is full, insert the failure
");
		return;
	}
	pSeq->array[pSeq->size] = x;
	pSeq->size++;
}

void PushFront(Seqlist* pSeq, Datatype x)//   
{
	assert(pSeq);
	size_t i = 0;

	if (pSeq->size >= MAX_SIZE)
	{
		printf("Array is full, insert the failure
");
		return;
	}

	for (i = pSeq->size; i > 0; --i)
	{
		pSeq->array[i] = pSeq->array[i - 1];
	}

	pSeq->array[0] = x;
	pSeq->size++;
}


void PopBack(Seqlist* pSeq)//   
{
	assert(pSeq);

	if (pSeq->size <= 0)
	{
		printf("Array is empty,popback is eeror
");
		return;
	}

	pSeq->array[pSeq->size-1] = 0;
	pSeq->size--;
}


void PopFront(Seqlist* pSeq)//   
{
	assert(pSeq);
	size_t i = 0;

	if (pSeq->size <= 0)
	{
		printf("Array is empty,popback is eeror
");
		return;
	}

	for (i = 1; i < pSeq->size; i++)
	{
		pSeq->array[i - 1] = pSeq->array[i];
	}

	pSeq->size--;
}


void Insert(Seqlist* pSeq, size_t pos, Datatype x)//    
{
	assert(pSeq);
	size_t i = 0;

	if (pSeq->size >= MAX_SIZE)
	{
		printf("Array is full, insert the failure
");
		return;
	}

	for (i = pSeq->size ; i > pos; i--)
	{
		pSeq->array[i] = pSeq->array[i - 1];
	}

	pSeq->array[pos] = x;
	pSeq->size++;
}


int Find(Seqlist* pSeq, size_t pos, Datatype x)//    
{
	assert(pSeq);
	size_t i = 0;

	if (pSeq->size <= 0)
	{
		printf("Array is empty,erase error
");
		return ARRAY_EMPTY;
	}

	if (pos < 0 || pos >= MAX_SIZE)
	{
		printf("Began to find the position error
");
		return -1;
	}

	for (i = pos; i < pSeq->size; i++)
	{
		if (pSeq->array[i] == x)
		{
			return i;
		}
	}


	return -2;
}


void Erase(Seqlist* pSeq, size_t pos)//      
{
	assert(pSeq);
	size_t i = 0;
	if (pSeq->size <= 0)
	{
		printf("Array is empty,erase error
");
		return;
	}
	if (pos < 0 || pos >= MAX_SIZE)
	{
		printf("Began to find the position error
");
		return;
	}
	for (i = pos; i < pSeq->size; i++)
	{
		pSeq->array[i] = pSeq->array[i + 1];
	}
	pSeq->size--;
}


int Remove(Seqlist* pSeq, Datatype x)
{
	assert(pSeq);
	size_t i = 0;
	if (pSeq->size <= 0)
	{
		printf("Array is empt,remove error
");
		return ARRAY_EMPTY;
	}
	for (; i < pSeq->size; i++)
	{
		if (pSeq->array[i] == x)
		{
			size_t j = i + 1;
			for (; j < pSeq->size; j++)
			{
				pSeq->array[j - 1] = pSeq->array[j];
			}
			pSeq->size--;
			return 0;
		}
	}
	return -1;
}


int Removeall(Seqlist* pSeq, Datatype x)
{
	assert(pSeq);
	size_t i = 0;
	int flag = 0;
	if (pSeq->size <= 0)
	{
		printf("Array is empt,remove error
");
		return ARRAY_EMPTY;
	}
	for (; i < pSeq->size; i++)
	{
		if (pSeq->array[i] == x)
		{
			size_t j = i + 1;
			for (; j < pSeq->size; j++)
			{
				pSeq->array[j - 1] = pSeq->array[j];
			}
			pSeq->size--;
			flag++;
			if (pSeq->size <= 0)//                 ，  
			{
				return 0;
			}
			else
			{
				i--;
			}
		}
	}
	if (flag > 0)
		return 0;
	else
		return -1;
}


void Bubblesort(Seqlist* pSeq)//    
{
	assert(pSeq);
	size_t i = 0;
	for (; i < pSeq->size; i++)
	{
		size_t j = 0;
		for (; j < pSeq->size - i - 1; j++)
		{
			if (pSeq->array[j] > pSeq->array[j + 1])
			{
				int tmp = pSeq->array[j];
				pSeq->array[j] = pSeq->array[j + 1];
				pSeq->array[j + 1] = tmp;
			}
		}
	}
}



void Selectsort(Seqlist* pSeq)//    
{
	assert(pSeq);
	size_t i = 0;
	for (; i < pSeq->size; i++)
	{
		int flag = pSeq->array[i];
		size_t j = i;
		for (; j < pSeq->size; j++)
		{
			if (pSeq->array[j] < flag)
			{
				int tmp = pSeq->array[j];
				pSeq->array[j] = flag;
				flag = tmp;
			}
		}
		pSeq->array[i] = flag;
	}
}


int BinarySearch(Seqlist* pSeq, Datatype x)//    
{
	assert(pSeq);
	size_t left = 0;
	size_t right = pSeq->size - 1;
	while (left <= right)
	{
		size_t mid = left + (right - left) / 2;
		if (x > pSeq->array[mid])
		{
			left = mid + 1;
		}
		else if (x < pSeq->array[mid])
		{
			right = mid - 1;
		}
		else if (x == pSeq->array[mid])
		{
			return (int)mid;
		}
	}
	return -1;
}

これは基本的な順序表にすぎず、基本タイプのデータしか格納できません.構造体やstringのようなデータを格納したい場合はC++の深浅コピーの問題があり、未知のサイズのデータ構造を1つの配列で格納することはできません.
本人のブログの后で顺番表のいくつかの最适化の书き方を更新することができて、友达の微小な助けに対して望みます.