数据结构-顺序表

1个月前发布

顺序表说白了就是内存中的一块连续的存储空间，这块连续的存储空间可以存放相同类型的数据。有的人可能就有疑问了，为什么不用数组呢？数组是程序在运行期间系统自动分配的，而创建的顺序表是用户手动创建的；数组存储在栈空间中，而顺序表是使用malloc函数或者calloc函数在堆空间申请的；栈空间用系统说了算，而对空间用户可以自己分配；如果申请的数组太大可能会导致栈空间溢出，出现段错误。而堆空间的容量一般来说是比栈空间大的，可以申请更多的内存。

1. 创建顺序表

创建一个顺序表的结构体

typedef int  DataType_t;
typedef struct SequenceList
{
	DataType_t * Addr;		//记录顺序表首地址
	unsigned int Size;		//记录顺序表的容量
	int			 Last;      //顺序表中最后元素的下标	

}SeqList_t;

创建顺序表并进行初始化

SeqList_t * SeqList_Create(unsigned int size)
{
	//1.利用calloc为顺序表的管理结构体申请一块堆内存
	SeqList_t *Manager = (SeqList_t *)calloc(1,sizeof(Manager));

	if(NULL == Manager)
	{
		perror("calloc memory for manager is failed");
		exit(-1); //程序异常终止
	}

	//2.利用calloc为所有元素申请堆内存
	Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));

	if (NULL == Manager->Addr)
	{
		perror("calloc memory for element is failed");
		free(Manager);
		exit(-1); //程序异常终止
	}

	//3.对管理顺序表的结构体进行初始化
	Manager->Size = size;	//对顺序表中的容量进行初始化
	Manager->Last = -1;		//由于顺序表为空，则最后元素下标初值为-1
	
	return Manager;
}

判断顺序表是否满

bool SeqList_IsFull(SeqList_t *Manager)
{
	return (Manager->Last + 1 == Manager->Size) ? true : false;
}

向顺序表尾部加入元素

bool SeqList_TailAdd(SeqList_t *Manager, DataType_t Data)
{
	//1.判断顺序表是否已满
	if ( SeqList_IsFull(Manager) )
	{
		printf("SequenceList is Full!\n");
		return false;
	}

	//2.如果顺序表有空闲空间，则把新元素添加到顺序表尾部
	Manager->Addr[++Manager->Last] = Data;

	return true;
}

向顺序表头部加入元素

bool SeqList_HeadAdd(SeqList_t *Manager, DataType_t Data)
{
	//1.判断顺序表是否已满
	if ( SeqList_IsFull(Manager) )
	{
		printf("SequenceList is Full!\n");
		return false;
	}

	//2.如果顺序表有空闲空间，则需要把顺序表所有元素向后移动1个单位
	for (int i = Manager->Last;i >= 0;i--)
	{
		Manager->Addr[i+1] = Manager->Addr[i];
	}

	//3把新元素添加到顺序表的头部,并且更新管理结构体中的元素下标+1
	Manager->Addr[0] = Data;
	Manager->Last++;

	return true;
}

判断顺序表是否为空

bool SeqList_IsEmpty(SeqList_t *Manager)
{
	return (-1 == Manager->Last) ? true : false;
}

顺序表删除指定的元素

bool SeqList_IsEmpty(SeqList_t *Manager)
{
	return (-1 == Manager->Last) ? true : false;
}

bool SeqList_Del(SeqList_t *Manager,DataType_t DestVal)
{
	//1.判断顺序表是否为空
	if(SeqList_IsEmpty(Manager)){
		printf("SequenceList is Empty\n");
		return false;
	}
	//2.删除指定的元素
	//循环遍历每个列表项
	for(int i=0;i<=Manager->Last;i++){
		//如果遇到该元素则进行删除
		if(DestVal==Manager->Addr[i]){
			for(int j=i;j<=Manager->Last;j++){
				Manager->Addr[j]=Manager->Addr[j+1];	
			}
			//最后一个元素的下标-1
			Manager->Last--;
			return true;
		}

	}
	//如果没有该元素则返回false
	return false;
}

打印顺序表

bool SeqList_Print(SeqList_t *Manager)
{
	//1.判断顺序表是否为空
	if(SeqList_IsEmpty(Manager)){
		return false;
	}
	for(int i=0;i<=Manager->Last;i++){
		printf("Manager[%d]=%d\n",i,Manager->Addr[i]);
	}
	return true;
}

来源链接：https://www.cnblogs.com/lradian/p/18801020

评分

欢迎为Ta评分