단일 링크 (C 언어)

#pragma once
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define MAX_SIZE 100

typedef int DataType;
typedef struct Seqlist
{
	DataType *_array;
	size_t _size;
	size_t _capacity;
}Seqlist;

void InitSeqlist(Seqlist *pSeq)//   
{
	assert(pSeq);
	pSeq->_capacity=MAX_SIZE;
	pSeq->_array=(DataType*)malloc(sizeof(DataType)*pSeq->_capacity);
	pSeq->_size=0;
}

void print(Seqlist *pSeq)//    
{
	int i=0;
	assert(pSeq);
	for(;i<pSeq->_size;++i)
	{
		printf("%d ",pSeq->_array[i]);
	}
	printf("
");
}

void WideCapacity(Seqlist *pSeq)//  
{
	if(pSeq->_size>=pSeq->_capacity)
	{
		DataType *tmp=0;
		pSeq->_capacity*=2;
		tmp=(DataType *)malloc(sizeof(DataType)*pSeq->_capacity);
		memcpy(tmp,pSeq->_array,sizeof(DataType)*pSeq->_size);
		free(pSeq->_array);
		pSeq->_array=tmp;
	}
}
void PushBack(Seqlist *pSeq,DataType x)//    
{
	assert(pSeq);
	if(pSeq->_size>=pSeq->_capacity)
	{
		WideCapacity(pSeq);
	}
	pSeq->_array[pSeq->_size++]=x;
}

void PopBack(Seqlist *pSeq)//    
{
	assert(pSeq);
	if(pSeq->_size==0)
	{
		printf("      ，    ！
");
		return;
	}
	--pSeq->_size;
}

void PushFront(Seqlist *pSeq,DataType x)//    
{
	int i=pSeq->_size;
	assert(pSeq);
	if(pSeq->_size>=pSeq->_capacity)
	{
		WideCapacity(pSeq);
	}
	for(;i>0;--i)
	{
		pSeq->_array[i]=pSeq->_array[i-1];
	}
	pSeq->_array[0]=x;
	++pSeq->_size;
}


void PopFront(Seqlist *pSeq)//    
{
	int i=0;
	assert(pSeq);
	if(pSeq->_size==0)
	{
		printf("      ，    ！
");
		return;
	}
	for(;i<pSeq->_size;++i)
	{
		pSeq->_array[i]=pSeq->_array[i+1];
	}
	--pSeq->_size;
}

void Insert(Seqlist *pSeq,size_t pos,DataType x)//  
{
	int i=pSeq->_size-1;
	assert(pSeq);
	assert(pos<=pSeq->_size);
	if(pSeq->_size>=pSeq->_capacity)
	{
		WideCapacity(pSeq);
	}
	for(;i>=(int)pos;--i)
	{
		pSeq->_array[i+1]=pSeq->_array[i];
	}
	pSeq->_array[pos]=x;
	++pSeq->_size;
}

void Remove(Seqlist *pSeq,DataType x)//     (   )
{
	int i=0;
	assert(pSeq);
	assert(pSeq->_size!=0);
	for(;i<pSeq->_size;++i)
	{
		if(pSeq->_array[i]==x)
		{
			int start=i;
			for(;start<pSeq->_size;++start)
			{
				pSeq->_array[start]=pSeq->_array[start+1];
			}
			--pSeq->_size;
			return;
		}
	}
}


void RemoveAll(Seqlist *pSeq,DataType x)//     (  )
{
	/////////////      ：  //////////////
	//int i=0;
	//assert(pSeq);
	//assert(pSeq->_size!=0);
	//for(;i<pSeq->_size;++i)
	//{
	//	if(pSeq->_array[i]==x)
	//	{
	//		int start=i;
	//		for(;start<pSeq->_size;++start)
	//		{
	//			pSeq->_array[start]=pSeq->_array[start+1];
	//		}
	//		--pSeq->_size;
	//		--i;
	//	}
	//}
	///////////////      ： /////////////
	int count=0;
	int firstIndex=0;
	int nextIndex=0;
	assert(pSeq);
	assert(pSeq->_size!=0);
	while(nextIndex<pSeq->_size)
	{
		if(pSeq->_array[nextIndex]==x)
		{
			--pSeq->_array[nextIndex];
		}
		else
		{
			pSeq->_array[firstIndex]=pSeq->_array[nextIndex];
			++firstIndex;
			count++;
		}
		++nextIndex;
	}
	pSeq->_size=count;
}

int Find(Seqlist *pSeq,DataType x)//     
{
	int i=0;
	assert(pSeq);
	assert(pSeq->_size!=0);
	for(;i<pSeq->_size;++i)
	{
		if(pSeq->_array[i]==x)
		{
			return 1;
		}
	}
}

void Modify(Seqlist *pSeq,size_t pos,DataType x)//    
{
	int i=0;
	assert(pSeq);
	assert(pos<=pSeq->_size);
	assert(pSeq->_size!=0);
	for(;i<=(int)pos;++i)
	{
		if(i==pos)
		{
			pSeq->_array[i]=x;
		}
	}
}

void Erase(Seqlist *pSeq,size_t pos)//        
{
	int i=0;
	assert(pSeq);
	assert(pos<=pSeq->_size);
	assert(pSeq->_size!=0);
	for(;i<pSeq->_size;++i)
	{
		if(i==pos)
		{
			int start=i;
			for(;start<pSeq->_size;++start)
			{
				pSeq->_array[start]=pSeq->_array[start+1];
			}
			--pSeq->_size;
			return;
		}
	}
}

#define _CRT_SECURE_NO_WARNINGS



#include<stdio.h>
#include "Seqlist.h"

void Test1()//    
{
	Seqlist s;
	InitSeqlist(&s);
	PushBack(&s,1);
	PushBack(&s,2);
	PushBack(&s,3);
	PushBack(&s,4);
	print(&s);
	PopBack(&s);
	print(&s);
}

void Test2()//    
{
	Seqlist s;
	InitSeqlist(&s);
	PushFront(&s,4);
	PushFront(&s,3);
	PushFront(&s,2);
	PushFront(&s,1);
	PushFront(&s,0);
	print(&s);
	PopFront(&s);
	print(&s);
}

void Test3()//      
{
	Seqlist s;
	InitSeqlist(&s);
	PushFront(&s,4);
	PushFront(&s,2);
	PushFront(&s,2);
	PushFront(&s,3);
	PushFront(&s,2);
	PushFront(&s,1);
	print(&s);
	Insert(&s,1,0);
	print(&s);
	Remove(&s,2);
	print(&s);
	RemoveAll(&s,2);
	print(&s);
}

void Test4(int k)//  
{
	int ret=0;
	Seqlist s;
	InitSeqlist(&s);
	PushFront(&s,4);
	PushFront(&s,3);
	PushFront(&s,2);
	PushFront(&s,1);
	PushFront(&s,0);
	print(&s);
	ret=Find(&s,k);
	if(ret==1)
	{
		printf("         ！
");
	}
	else
	{
		printf("          ！
");
	}
}

void Test5()//  、  
{
	Seqlist s;
	InitSeqlist(&s);
	PushFront(&s,3);
	PushFront(&s,2);
	PushFront(&s,1);
	PushFront(&s,0);
	print(&s);
	Modify(&s,3,1);
	print(&s);
	Erase(&s,1);
	print(&s);
}


int main()
{
	int k=0;
	printf("     
");
	Test1();

	printf("     
");
	Test2();

	printf("       
");
	Test3();

	printf("     
");
	printf("     ：");
	scanf("%d",&k);
	Test4(k);

	printf("    、       
");
	Test5();

	system("pause");
	return 0;
}