温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C语言实现顺序表

发布时间:2020-06-19 02:53:41 来源:网络 阅读:490 作者:稻草阳光L 栏目:开发技术

  顺序表是C语言中一种基本的结构,可以存储各种基本类型的数据,而且不但可以存储基本类型的数据,也可以存储一种结构。所以顺序表是一种在学C的过程中必须掌握的结构,通过学习整理,下面来实现一下:

  首先,先要想好用什么实现,一般实现最基本的顺序表的话直接用数组实现,我们在这用一个结构体来封装这个顺序表(封装这一概念是在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;

  对于无法确定数组大小,我们可以用宏来表示。

  把大体结构搭建好了之后,就可以思考一个顺序表应该具有的功能,头插,尾插,定点插入,排序等等都是一些最基本的功能:

	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\n");
		return;
	}
	else if (pSeq->size >= MAX_SIZE)
	{
		printf("Array is full\n");
	}
	for (; i < pSeq->size; ++i)
	{
		printf("%-4d", pSeq->array[i]);
	}
}

void InitSeqlist(Seqlist* pSeq)//初始化顺序表
{
	pSeq->size = 0;
	//printf("Initialization is complete\n");
}

void PushBack(Seqlist* pSeq, Datatype x)//后插入
{
	assert(pSeq);
	if (pSeq->size >= MAX_SIZE)
	{
		printf("Array is full, insert the failure\n");
		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\n");
		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\n");
		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\n");
		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\n");
		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\n");
		return ARRAY_EMPTY;
	}

	if (pos < 0 || pos >= MAX_SIZE)
	{
		printf("Began to find the position error\n");
		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\n");
		return;
	}
	if (pos < 0 || pos >= MAX_SIZE)
	{
		printf("Began to find the position error\n");
		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\n");
		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\n");
		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++的深浅拷贝问题,而且用一个数组来存未知大小的数据结构的话是做不到的。

  本人的博客后面会更新顺序表的一些优化写法,希望对朋友微小的帮助。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI