データ構造——C言語実現シーケンス表

データ構造——C言語実現シーケンス表
シーケンステーブルは、データ要素を物理的アドレスで連続した記憶手段で順次記憶する線形構造である.一般的にはシーケンステーブルは配列を基本とし、構造体をフレームとして実現されます.アレイ記憶.配列上でデータの添削が完了し、構造体にはデータを格納する配列、格納されたデータの実際の長さ、およびシーケンステーブルの容量が含まれている.順序表は、一般的に、1.静的順序表に分けられます.固定長配列を使って保存します.

#define N 100
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N]; //     
size_t size; //        
}SeqList;

ダイナミック・シーケンス・テーブル:ダイナミック・オープン・アレイ記憶

を使用する.

typedef struct SeqList
{
SLDataType* array; //          
size_t size ; //       
size_t capicity ; //        
}SeqList;

静的順序表は、データの保存がどれぐらい必要かを知るシーンにのみ適用されます.静的な順序表の定長配列はN定が大きくなり、空間が開けすぎて無駄になり、足りなくなりました.したがって、現実的には基本的に動的な順序表を使用して、必要に応じて動的な空間サイズを割り当てるので、動的な順序表を実現する例で説明します.その動的な順序表の定義と関数インターフェースの宣言は以下の通りです.

typedef struct SeqList
{
	SLDataType* array;
	size_t size;
	size_t capacity;
}SeqList;
void SeqListInit(SeqList* psl);//      
void SeqListDestory(SeqList *psl);//     
void SeqListCheckCapacity(SeqList *psl);//    
void SeqListPushBack(SeqList *psl, SLDataType x);//  
void SeqListPopBack(SeqList *psl);//  
void SeqListPushFront(SeqList *psl, SLDataType x);//  
void SeqListPopFront(SeqList *psl);//  
void SeqListInsert(SeqList *psl, size_t pos, SLDataType x);//  pos     
void SeqListRErase(SeqList *psl, size_t pos);//   pos   
int SeqListFind(SeqList *psl, SLDataType x);//    
void SeqListMdfidy(SeqList *psl, size_t pos, SLDataType x);//   pos    
void SeqListPrint(SeqList *psl);//     
size_t SeqListSize(SeqList *psl);//      
void SeqListRemoveAll(SeqList *psl, SLDataType x);//       
void SeqListBubbleSort(SeqList *psl);//         
int SeqListBinaryFind(SeqList *psl, SLDataType x);//       

関数の実装および機能の説明は、以下のコードによって表されます.

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include"SeqList.h"
#include
#include

//   
void SeqListInit(SeqList* psl)
{
	assert(psl);//  sql    
	psl->array = NULL;//       
	psl->size = 0;//        0
	psl->capacity = 0;//        0
}
//     
void SeqListDestory(SeqList *psl)
{
	assert(psl);//  psl    
	if (psl->array)
	{
		free(psl->array);//  psl  
		psl->array = NULL;//       
		psl->capacity = 0;//      0
		psl->size = 0;//        0
	}
}
//    ：     malloc        ，   realloc      ，                            malloc            。
void CheckCapacity(SeqList* psl)
{
	 assert(psl);
	 //    
	 if (psl->size == psl->capacity)
	 {
	  //     
	  size_t newcapacity = psl->capacity == 0 ? 5 : 2 * psl->capacity;
	  //    
	  psl->array = (SLDataType*)realloc(psl->array, newcapacity * sizeof(SLDataType));
	  //        
	  assert(psl->array);
	  //    
	  psl->capacity = newcapacity;
	 }
}
//  
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);//  sql    
	SeqListCheckCapacity(psl);
	psl->array[psl->size] = x;//           
	psl->size++;//         
}
//  
void SeqListPopBack(SeqList *psl)
{
	assert(psl);//  sql    
	if (psl->size == 0)//         
	{
		printf("SeqList has been empty
");
		return;
	}
	psl->size--;//       ，       
}
//  
void SeqListPushFront(SeqList *psl, SLDataType x)
{
	size_t end = 0;
	assert(psl);//  sql    
	SeqListCheckCapacity(psl);//    
	for (end = psl->size; end > 0; end--)
	{
		psl->array[end] = psl->array[end - 1];//              
	}
	psl->array[0] = x;//          
	psl->size++;//        1
}
//  
void SeqListPopFront(SeqList *psl)
{
	size_t start = 0;
	assert(psl);//  psl    
	if (psl->size == 0)//         
	{
		printf("SeqList has been empty!
");
		return;
	}
	for (start = 0; start < psl->size - 1; start++)
	{
		psl->array[start] = psl->array[start + 1];//              
	}
	psl->size--;//         
}
// pos     
void SeqListInsert(SeqList *psl, size_t pos, SLDataType x)
{
	//pos==0-->  
	//pso==szie-->  
	size_t end = 0;
	assert(psl && (pos >= 0) && (pos <= psl->size));//  psl               
	SeqListCheckCapacity(psl);
	for (end = psl->size; end > pos; end--)
	{
		psl->array[end] = psl->array[end - 1];//      pos           
	}
	psl->array[pos] = x;//  pos    x
	psl->size++;//        1
}
//   pos   
void SeqListErase(SeqList *psl, size_t pos)
{
	size_t start = 0;
	assert(psl && (pos >= 0) && (pos <= psl->size));//  psl               
	if (psl->size == 0)//         
	{
		printf("SeqList has been empty
");
		return;
	}
	for (start = pos; start < psl->size - 1; start++)
	{
		psl->array[start] = psl->array[start + 1];//  pos          
	}
	psl->size--;//         
}
//    
int SeqListFind(SeqList *psl, SLDataType x)
{
	size_t i = 0;
	assert(psl);//  psl    
	if (psl->size == 0)//         
	{
		printf("SeqList has been empty
");
		return -1;
	}
	for (i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)//         
		{
			return i;//      
		}
	}
	return -1;//     -1
}

//   pos   
void SeqListModify(SeqList *psl, size_t pos, SLDataType x)
{
	assert(psl && (pos >= 0) && (pos <= psl->size));//  psl               
	if (psl->size == 0)//         
	{
		printf("SeqList has been empty
");
		return;
	}
	psl->array[pos] = x;//  pos    
}
//     
void SeqListPrint(SeqList *psl)
{
	size_t i = 0;
	assert(psl);//  psl    
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);//  
	}
	printf("
");
}
//      
size_t SeqListSize(SeqList *psl)
{
	assert(psl);//  psl    
	return psl->size;//    
}
//       
void SeqListRemoveAll(SeqList *psl, SLDataType x)
{
	size_t i = 0;
	size_t index = 0;
	assert(psl);//  psl    
	if (psl->size == 0)//         
	{
		printf("SeqList has been empty
");
		return;
	}
	for (i = 0; i < psl->size; i++)
	{
		//          
		//    
		//if (psl->array[i] == x)//    
		//{
		//psl->size--;//      
		//	for (index=i; index < psl->size ; index++)
		//	{
		//		psl->array[index] = psl->array[index + 1];//    ，             
		//	}
		//	return;
		//}
		//    ：      ，     
		if (psl->array[i] != x)//       x 
		{
			psl->array[index] = psl->array[i];//    
			index++;
		}
	}
	if (index < psl->size)//         ，    
	{
		psl->size = index;//            
		return;
	}
	printf("SeqList does not the data
");//      
}
//         
void SeqListBubbleSort(SeqList *psl)
{
	assert(psl);
	//  
	size_t end = psl->size;
	while (end > 1)
	{
		//      
		int flag = 0;
		for (size_t i = 0; i < end; i++)
		{
			if (psl->array[i - 1]>psl->array[i])
			{
				flag = 1;
				//  
				(psl->array[i - 1]) ^= (psl->array[i]);
				(psl->array[i]) ^= (psl->array[i - 1]);
				(psl->array[i - 1]) ^= (psl->array[i]);
			}
		}
		if (flag == 0)
		{
			break;
		}
		--end;
	}
}
//       ：                  ，        。
int SeqListBinaryFind(SeqList *psl, SLDataType x)
{
	assert(psl);
	if (psl->size == 0)
	{
		printf("SeqList has been empt
");
		return -1;
	}
	size_t start = 0;
	size_t end = psl->size - 1;
	while (start <= end)
	{
		size_t mid = start+(end-start) / 2;
		if (psl->array[mid] == x)
		{
			return mid;
		}
		else if (psl->array[mid] > x)
		{
			end = mid - 1;
		}
		else
		{
			start = mid + 1;
		}
	}
	return -1;
}

順序表インターフェース関数を実現するには、関数体では、インターフェース関数パラメータの有効性、順序表の容量、および順序表が空かどうかの判断とチェックが必要です.オーバーフローなどのエラーが発生しないようにしてください.ループタイムアウトを行い、境界値の判断をメモしてください.そうでないと境界のオーバーまたは漏れを引き起こしやすく、メモリ空間のオーバーフローをもたらします.