데이터 구조: 순서 표 단순 기능 실현

#pragma once
#include 

typedef int SLDataType;

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


//         
//   
void SeqListInit(SeqList* psl, size_t capacity);
//  
void SeqListDestory(SeqList* psl);
//  
void CheckCapacity(SeqList* psl);

//  
void SeqListPushBack(SeqList* psl, SLDataType x);
//  
void SeqListPopBack(SeqList* psl);

//  
void SeqListPushFront(SeqList* psl, SLDataType x);
//  
void SeqListPopFront(SeqList* psl);

//  
//      -1
int SeqListFind(SeqList* psl, SLDataType x);

// pos          
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);

//  pos    
void SeqListErase(SeqList* psl, size_t pos);

//     x
void SeqListRemove(SeqList* psl, SLDataType x);

//  pos      x
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

void SeqListPrint(SeqList* psl);

//    
void SeqListBubbleSort(SeqList* psl); 

//    (    )
int SeqListBinaryFind(SeqList* psl, SLDataType x);

//       x
void SeqListRemoveAll(SeqList* psl, SLDataType x);

#include "Seqlist.h"
#include 
#include 
#include 

void SeqListInit(SeqList* psl, size_t capacity)
{
	assert(psl != NULL);
	psl->array = (SLDataType *)malloc(capacity* sizeof(SLDataType));
	psl->size = 0;
	psl->capicity = capacity;

}

void SeqListDestory(SeqList* psl)
{
	assert(psl != NULL);
	free(psl->array);
	psl->array = NULL;
	psl->capicity = 0;
	psl->size = 0;
}

void CheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->sizecapicity)
	{
		return;
	}
	int newcapicity = 2 * psl->capicity;
	SLDataType * newarray = (SLDataType*)malloc(newcapicity*sizeof(SeqList));
	assert(newarray);
	for (size_t i = 0; i < psl->size; i++)
	{
		newarray[i] = psl->array[i];
	}
	free(psl->array);
	assert(psl->array == NULL);
	psl->array = newarray;
	psl->capicity = newcapicity;

}

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->array[psl->size]=x;
	psl->size++;
}

void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	if (psl->size<1)
	{
		return;
	}
	psl->size--;
}

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (size_t i = psl->size; i >0; i++)
	{
		psl->array[psl->size] = psl->array[psl->size - 1];
	}
	psl->size++;
	psl->array[0] = x;

}

void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	for (size_t i = 0; i size-1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (size_t i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	assert(pos >= 0 && pos <= psl->size);

	for (int i = psl->size; i>(int)pos ; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->size++;
	psl->array[pos] = x;

}

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(psl->size > 0);
	assert(pos >= 0 && pos <= psl->size);
	for (size_t i = pos; i < psl->size-1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;

}

void SeqListRemove(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (size_t i = 0; i < psl->size; i++)
	{
		if (x == psl->array[i])
		{
			SeqListErase(psl, i);
			break;
		}
	}
}
1
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	psl->array[pos] = x;
}

void SeqListPrint(SeqList* psl)
{
	for (size_t i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);	
	}
	printf("
");
}

void SeqListBubbleSort(SeqList* psl)
{
	assert(psl);
	for (size_t i = 0; i < psl->size -1; i++)
	{
		int flag =0;
		for (size_t j = 0; j < psl->size - 1 - i; j++)
		{
			if (psl->array[j] >= psl->array[j + 1])
			{
				int temp = psl->array[j];
				psl->array[j] = psl->array[j + 1];
				psl->array[j + 1] = temp;
				flag = 1;
			}
		}
		if (flag==0)
		{
			return;
		}
	}
}

int SeqListBinaryFind(SeqList* psl, SLDataType x)
{	
	SeqListBubbleSort(psl);
	int left = 0;
	int right = psl->size ;
	while (left>right)
	{
		int mid = left+(right-left) / 2;
		if (x == psl->array[mid] )
		{
			return mid ;
		}
		else if (x < psl->array[mid])
		{
			right = mid;
		}
		else
		{
			left = mid+1;
		}
	}
	return -1;

}

void SeqListRemoveAll(SeqList* psl, SLDataType x)
{
	assert(psl);
	int j = 0;
	for (size_t i = 0; i < psl->size; i++)
	{
		if (x != psl->array[i])
		{
			//psl->array[j++] = psl->array[i];
			psl->array[j] = psl->array[i];
			j++;			
		}
	}
	psl->size = j;

}

#include "SeqList.h"
#include 


void TestSeqList()
{
	SeqList seqlist;
	SeqListInit(&seqlist,5);
	SeqListPushBack(&seqlist, 1);
	SeqListPushBack(&seqlist, 2);
	SeqListPushBack(&seqlist, 2);
	SeqListPushBack(&seqlist, 3);
	SeqListPushBack(&seqlist, 2);

	SeqListPrint(&seqlist);

	SeqListRemoveAll(&seqlist, 2);

	SeqListPrint(&seqlist);

	SeqListDestory(&seqlist);

}

int main()
{
	TestSeqList();
	system("pause");
	return 0;
}