（数据结构）动态顺序表的实现

#pragma once
#include<malloc.h>
#include<stdio.h>
typedef int DataType;

typedef struct SeqListD
{
	Datatype* _array;
	int _size;//有效元素的个数
	int _capacity;//空间的总大小
}SeqListD, *PSeqListD;

_array为存放元素的指针，因为要动态的存储，所以不定义其所指空间的大小。

//初始化顺序表
void SeqListDInit(PSeqListD ps,int capacity)
{
	if(NULL == ps)
		return;
	ps->_array = (Datatype*)malloc(capacity);
	if(NULL == ps->_array)
	{
		printf("空间申请失败");
		return;
	}
}

先判断顺序表是否存在，之后给顺序表中的指针_array开辟空间大小为指定的capacity，还需判断空间是否申请成功

//尾插
void SeqListDPushBack(PSeqListD ps, DataType data)
{
	if(NULL == ps)
		return;
	
	if(!CheckCapacity(ps))
	{
		printf("增容失败\n");
		return;
	}
	ps->_array[ps->_size++] = data;
}

判断顺序表是否存在，调用增容函数（在该文章最后介绍），插入data并使size++，因为是动态的顺序表，所以不需要判断元素溢出的问题

//尾删
void SeqListDPopBack(PSeqListD ps)
{
	if(NULL == ps)
		return;

	if(SeqListDEmpty(ps))
	{
		printf("元素个数为空\n");
		return;
	}

	ps->_size--;
}

判断条件：顺序表是否存在，元素个数是否为空。然后直接将size--就行了

//任意位置的插入
void SeqListDInsert(PSeqListD ps, int pos, DataType data)
{
	int i = 0;

	if(NULL == ps || (pos < 0 && pos > ps->_size))
	{
		return;
	}
	
	if(!CheckCapacity(ps))
	{
		printf("增容失败\n");
		return;
	}

	for(i = ps->_size-1;i >= pos;--i)
	{
		ps->_array[i+1] = ps->_array[i];
	}

	ps->_array[pos] = data;
	ps->_size++;
}

判断条件：顺序表存在，pos大于0且小于size。先判断是否需要增容，将从后往前size-pos个元素全部向后移动一位，留出下标为pos的位置插入新的元素data，size++

//任意位置的删除
void SeqListDErase(PSeqListD ps, int pos, DataType data)
{
	int i;

	if(NULL == ps || (pos > ps->_size && pos < 0))
		return;

	if(SeqListDEmpty(ps))
	{
		printf("元素个数为空\n");
		return;
	}

	for(i=pos-1; i < ps->_size; i++)
	{
		ps->_array[i] = ps->_array[i+1];
	}

	ps->_size--;
}

判断条件：顺序表存在，pos大于0且小于size，元素个数是否为空。将从后往前size-pos个元素全部向前移动一位（下标为pos的元素被覆盖），size--

//求元素个数
int SeqListDSize(PSeqListD ps)
{
	return ps->_size;
}

返回值为size

//求元素个数上限
int SeqListDCapacity(PSeqListD ps)
{
	return ps->_capacity;
}

返回值为capacity

//判断元素个数是否为空
int SeqListDEmpty(PSeqListD ps)
{
	return 0 == ps->_size;
}

判断size是否为0，为空返回1，不为空返回0

//清空顺序表,但不改变空间的大小
void SeqListDClear(PSeqListD ps)
{
	ps->_size = 0;
}

直接将size改成0

//销毁动态顺序表
void SeqListDDestroy(PSeqListD ps)
{
	if(ps && ps->_array)//判断顺序表是否为空，判断顺序表中存放元素的数组是否为空
	{
		free(ps->_array);
		ps->_capacity = 0;
		ps->_size = 0;
	}


}

释放array中的空间，将capacity和size置0

//判断是否给动态顺序表增容
int CheckCapacity(PSeqListD ps)
{
	if(NILL == ps)
		return 0;

	if(ps->_size == ps->_capacity)
	{
		int newCapacity = 2*ps->_capacity;
		ps->_array = (Datatype*) realloc(ps->_array, newCapacity);
		if(NULL == ps->_array)
			return 0;
		
		ps->_capacity = newCapacity;
	}
        else return 0;
	return 1;
}

先判断顺序表存在。再判断size的是否大于最大长度capacity，大于需要增容。每次增容的最大容量是之前最大容量的二倍（用空间换取时间），用realloc函数，给指针array所指向重新开辟空间，realloc能够同时实现开辟空间和将原空间的元素放入新空间的操作。实现完增容将capacity修改为增容后的容量.

秒客网

（数据结构）动态顺序表的实现

相关文章