顺序表动态存储及其接口的实现

小编 2026-06-18 阅读:615 评论:0

顺序表的存储有两种方式：静态存储和动态存储。静态存储开辟的是一个定长的空间，它只适用确定知道需要存储多少数据的场景。静态顺序表的定长数组开多了浪费，开少了不够用。所有在大多数情况下都是使用动...

顺序表的存储有两种方式：静态存储和动态存储。
静态存储开辟的是一个定长的空间，它只适用确定知道需要存储多少数据的场景。静态顺序表的定长数组开多了浪费，开少了不够用。所有在大多数情况下都是使用动态顺序表，根据需要动态分配空间大小。下面是对动态顺序表的实现：

SeqList.h
#ifndef __TEST_H__
#define __TEST_H__
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* _array;
	size_t _size;
	size_t _capacity;
}SeqList;
void SeqListInit(SeqList* ps, size_t capacity);//初始化顺序表
void SeqListPushBack(SeqList* ps,SLDataType x);//在顺序表尾部插入一个x
void SeqListPrint(SeqList* ps);//打印顺序表
void SeqListPopBack(SeqList* ps);//在顺序表尾部进行删除
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);//在顺序表某个位置进行插入一个数x
void SeqListPopFront(SeqList* ps);//头删
void SeqListErase(SeqList* ps, size_t pos);
int SeqListFind(SeqList*ps, SLDataType x);
size_t SeqListSize(SeqList* ps);//计算顺序表的大小
int SeqListEmpty(SeqList* ps);//检查是否为空
void SeqListModify(SeqList* ps,size_t pos,SLDataType x);//修改给定位置的值
void SeqListBubbleSort(SeqList* ps);//对顺序表进行冒泡排序
int SeqListBinaryFind(SeqList* ps, SLDataType x);
void SeqListRemoveAll(SeqList* ps, SLDataType x);


void SeqListDestory(SeqList* ps);
#endif //__TEST_H__

SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include\"SeqList.h\"
void SeqListInit(SeqList* ps, size_t capacity)
{
	assert(ps);
	ps->_array=(SLDataType*)malloc(sizeof(SLDataType)*capacity);
	ps->_size = 0;
	ps->_capacity = capacity;
}

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->_array)
	{
		free(ps->_array);
		ps->_array = NULL;
		ps->_capacity = ps->_size = 0;
	}
}


void CheckCapacity(SeqList* ps)
{
	if (ps->_size == ps->_capacity)
	{
		ps->_capacity *= 2;
		ps->_array = realloc(ps->_array, ps->_capacity*sizeof(SLDataType));
		assert(ps->_array);
	}
}


void SeqListPushBack(SeqList* ps,SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->_array[ps->_size++] = x;
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps && ps->_size > 0);
	ps->_size--;
}

void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
	assert(ps && pos <= ps->_size);
	CheckCapacity(ps);
	size_t end = ps->_size;
	while (end > pos)
	{
		ps->_array[end] = ps->_array[end - 1];
		--end;
	}
	ps->_array[pos] = x;
	ps->_size++;

}

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	size_t begin = 0;
	while (begin < ps->_size - 1)
	{
		ps->_array[begin] = ps->_array[begin + 1];
			++begin;
	}
	--ps->_size;
}

void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps && pos < ps->_size);
	size_t begin = pos;
	while (begin < ps->_size - 1)
	{
		ps->_array[begin] = ps->_array[begin + 1];
		++begin;
	}
	--ps->_size;

}

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

}


size_t SeqListSize(SeqList* ps)
{
	assert(ps);
	printf(\"%d\\n\", ps->_size);
	return 0;
}


//非空返回1，空返回0
int SeqListEmpty(SeqList* ps)
{
	assert(ps);
	return ps->_size > 0 ? 1 : 0;
}

void SeqListModify(SeqList* ps,size_t pos,SLDataType x)
{
	assert(ps && pos < ps->_size);
	ps->_array[pos] = x;

}

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (size_t i = 0; i < ps->_size; i++)
	{
		printf(\"%d \", ps->_array[i]);
	}
	printf(\"\\n\");
}

void SeqListBubbleSort(SeqList* ps)
{
	assert(ps);
	size_t finish = ps->_size;
	while (finish > 0)
	{
		int exchenge = 1;
		for (size_t i = 0; i <finish; i++)
		{

			if (ps->_array[i]>ps->_array[i + 1])
			{
				SLDataType tmp = ps->_array[i];
				ps->_array[i] = ps->_array[i + 1];
				ps->_array[i + 1] = tmp;
				exchenge = 1;
			}
		}
		--finish;
	}
}

int SeqListBinaryFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int begin = 0;
	int end = ps->_size - 1;
	while (end >= begin)
	{
		int mid = (begin + end) / 2;
		if (x > ps->_array[mid])
		{
			begin = mid + 1;
		}
		else if (x < ps->_array[mid])
		{
			end = mid - 1;
		}
		else
		{
			return mid;
			printf(\"找到了%d\\n\", mid);
		}
		return -1;
	}
}
	void SeqListRemoveAll(SeqList* ps, SLDataType x)
	{
		assert(ps);
		size_t cur = 0;
		size_t dest = 0;
		while (cur < ps->_size)
		{
			if (ps->_array[cur] == x)
			{
				++cur;
			}
			else
			{
				ps->_array[dest] = ps->_array[cur];
				++dest;
			}
			++cur;

		}
		ps->_size=dest;
	}

test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include\"SeqList.h\"

SeqList s;
void Test1()
{
	SeqListInit(&s, 8);
    SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 56);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 30);
	SeqListPushBack(&s, 3);
    SeqListPopBack(&s);
	SeqListInsert(&s, 2, 5);
	SeqListPopFront(&s);
	SeqListErase(&s, 2);
	SeqListSize(&s);
	SeqListEmpty(&s);
	SeqListModify(&s, 1,3);
	SeqListBubbleSort(&s);
	SeqListBinaryFind(&s, 56);

	SeqListRemoveAll(&s, 3);

	SeqListPrint(&s);
	SeqListDestory(&s);

}

int main()
{
	Test1();
	return 0;
}