数据结构入门（二）：顺序表

目录

1.顺序表的概念

2.注意事项

3.接口的实现

4.顺序表的问题及思考

1.顺序表的概念

2.注意事项

在进行任意位置删除的时候：一定要注意是否越界，因为顺序表是以一个连续的线性表

3.接口的实现

3.1任意插入（头插和尾插）

3.2任意删除

尾删

任意删除

3.2打印顺序表

3.3最后释放开辟的空间

3.4举例实现

4.顺序表的问题及思考

---

1.顺序表的概念

顺序表是一种用连续的物理地址存储单元一次存储数据元素的线性结构，所以它和链表、栈、队列、字符串以及都是属于线性表。

1.1顺序表一般可以分为静态顺序表和动态顺序表

静态顺序表：

即给定数的长度，往里面存储数据

typedef struct Seqlist
{
   SLDataType a[N];
     size_t size;
}SeqList;

动态顺序表：

typedef struct Seqlist
{
	SLDataType* a;
	SLDataType size;
	SLDataType capacity; //数组实际存放的数据
}SL;

先给定一定的空间，当空间不够的时候可以扩容；

2.注意事项

在写接口函数之前一定要注意，在插入前要对顺序表进行判断空间是否足够，

为了调用的时候更方便一般先写一个函数来判断是否要对该空间进行增容；

void Checkcapacity(SL*pc)
{
	if (pc->capacity == pc->size)
	{
		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
		//进行扩容
		SLDataType* tem = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * newcapacity);
		if (tem == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//扩容失败，直接退出,终止整个程序，return只是结束了尾插这个函数
		}
		//扩容成功
		pc->a = tem;
		pc->capacity = newcapacity;
	}
}

在进行任意位置删除的时候：一定要注意是否越界，因为顺序表是以一个连续的线性表

3.接口的实现

3.1任意插入（头插和尾插）

头插

void SeqListPushFront(SL*pc,SLDataType x)
{
	Checkcapacity(pc);
	for (int i = pc->size-1; i>=0; i--)
	{
		pc->a[i+1] = pc->a[i];
	}
	pc->a[0] = x;
	pc->size++;
}

尾插

void SeqListPushBack(SL* pc,SLDataType x)
{
	Checkcapacity(pc);
	pc->a[pc->size] = x;
	pc->size++;
}

任意插入

void SeqLisrInsert(SL* pc, int pos, SLDataType x)
{
	assert(pos<=pc->size||pos>=0);
	Checkcapacity(pc);
	for (int i=pc->size-1;i>=pos; i--)
	{
		pc->a[i+1] = pc->a[i];
	}
	pc->a[pos] = x;
	pc->size++;
}

所以在运用头插的时候就不用专门写一个接口，直接对调用这个接口就行；

3.2任意删除

头删

void SeqListPopFront(SL*pc)
{
	assert(pc->size > 0);
	for (int i=0;i<pc->size-2; i++)
	{
		pc->a[i] = pc->a[i + 1];
	}
	pc->size--;
}

尾删

void SeqListPopBack(SL*pc)
{
	//判断一下是否size必须大于等于0；
	/*if (pc->size > 0)
		pc->size--;*/
	pc->size--;
	assert(pc->size > 0);
}

任意删除

void SeqListDes(SL* pc, int pos, SLDataType x)
{
	assert(pos>=0||pos<=pc->size);//因为顺序表是连续的
	for (int i = pos; i < pc->size - 1; i++)
	{
		pc->a[i] = pc->a[i + 1];
	}
	pc->size--;
	assert(pc->size > 0);
}

3.2打印顺序表

void SeqListprint(SL* pc)
{
	for (int i = 0; i <pc->size; i++)
	{
		printf("%d ", pc->a[i]);
  }
}

int SeqListFind(SL* pc, SLDataType x)
{
	for (int i = 0; i < pc->size; i++)
	{
		if (pc->a[i] == x)
			return i;
	}
	return -1;
}

3.3最后释放开辟的空间

void SeqListDestroy(SL* pc)
{
	free(pc->a);
	pc->a = NULL;
	pc->size = pc->capacity = 0;
}

3.4举例实现

void TestSeqlist1()
{
	SL sl;
	SeqListInIt(&sl);
	//尾插数据
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
	SeqListPushFront(&sl, 10);
	SeqListPushFront(&sl, 20);
	SeqLisrInsert(&sl, 7, 30);
	SeqListprint(&sl);

	//最后不用的时候销毁顺序表
	SeqListDestroy(&sl);

}


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

实现的结果

4.顺序表的问题及思考

1.插入数据的时候，时间复杂度其O(n)；

2.增容需要申请新的空间，拷贝数据，释放旧空间，会有不小的损耗；

3.增容一般呈2倍的增长，后面没有了数据的插入，就浪费了太多空间；