Implementation of a sequence table

概念及结构

       顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.简单地说,A sequence table is an array,在数组上完成数据的增删查改.But the data of the sequence table must be stored consecutively from the first position.

顺序表的分类

静态顺序表：使用定长数组存储元素

 

 动态顺序表：使用动态开辟的数组存储

 

 Compare the selection order list and refine

静态顺序表只适用于确定知道需要存多少数据的场景.静态顺序表的定长数组导致N定大了,空
间开多了浪费,开少了不够用.所以现实中基本都是使用动态顺序表,根据需要动态的分配空间
大小.But the above sequence table has a little problem,It is this array that can only be storedint类型的变量,It is more troublesome for us to store other types of variables to modify,So let's improve it：

 动态顺序表的实现

SeqList.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* a; //指向动态数组指针
    int size;      //数据个数
    int capacity;  //容量空间大小
}SL;

void SListInit(SL* ps);  //初始化
void SLPrintf(SL* ps);   //打印
void SLCheckcapacity(SL* ps); //检查容量
void SLPushBack(SL* ps,SLDataType x);  //尾插
void SLPushFront(SL* ps,SLDataType x);  //头插
void SLPopBack(SL* ps);  //尾删
void SLPopFront(SL* ps);  //头删
void SLDestory(SL* ps);  //调用销毁
void SLInsert(SL* ps, int pos, SLDataType x); //任意位置插入
void SLErase(SL* ps, int pos);    //任意位置删除
int SLFind(SL* ps, SLDataType x);   //查找
void SLModify(SL* ps,int pos,SLDataType x);  //修改

SeqList.c:

#include"SeqList.h"

// 初始化
void SListInit(SL* ps)
{
	assert(ps);
	ps->a = 0;
	ps->size = ps->capacity = 0;
}

//打印
void SLPrintf(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d", ps->a[i]);
	}
	printf("\n");
}

//检查容量
void SLCheckcapacity(SL* ps)
{
	assert(ps);
	//检查容量空间,满了扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity==0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

//调用销毁
void SLDestory(SL* ps)
{
	assert(ps);
	if (ps->a = 0)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

// 尾插
void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);
	检查容量空间,满了扩容
	//if(ps->size == ps->capacity)
	//{
	//	int newcapacity = ps->capacity==0 ? 4 : ps->capacity * 2;
	//SLDataType* tmp = (SLDataType*)realloc(ps->a,newcapacity * sizeof(SLDataType));
	//if (tmp == NULL)
	//{
	//	printf("realloc fail\n");
	//	exit(-1);
	//}
	//ps->a = tmp;
	//ps->capacity = newcapacity;
	//}
	SLCheckcapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

//头插
void SLPushFornt(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckcapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	//ps->a[ps->size-1]=0;
	//温柔检查
	/*if (ps->size == 0)
	{
		printf("SeqList is empty\n");
		return;
	}*/
	//暴力检查
	assert(ps->size>0);
	ps->size--;
}

//头删
void SLPopFornt(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

//任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckcapacity(ps);
	int end = ps->size - 1;
	while (pos <= end)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

//任意位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size );
	int begin = pos+1;
	while (begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		return -1;
	}
}

//修改
void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

顺序表的问题

1. 中间/头部的插入删除,时间复杂度为O(N)
2. 增容需要申请新空间,拷贝数据,释放旧空间.会有不小的消耗.
3. 增容一般是呈2倍的增长,势必会有一定的空间浪费.例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间.