从顺序表开始，带你走进数据结构

前言

        数组是C语言规定的语法之一，功能是存储并使用一系列相同类型的变量。其工作原理是在内存中开辟一块连续的空间用于存储数据，在使用时则可通过下标的方式挨个访问数组中的元素。这种数据管理方法虽然能完成基本的功能，但计算机管理数据所需要的不仅限于此，在数据管理过程中可能会用到增删查改这些功能，而想用数组实现这一系列功能只能说大费周章、事倍功半。于是便有了顺序表、链表、栈和队列等一系列数据结构，目的是更好地管理和维护我们的数据。

---

线性表

        所谓线性表就是存储形式相同或相似的一系列数据结构的集合，也就是说线性表是相似数据结构的总称，不是其中的某一个数据结构。

线性表的特性

        线性表在逻辑上是线性的，在物理上不一定是线性的。

顺序表

        前面提到数组和线性表，数组是最简单的数据结构，同时数组满足逻辑上和物理上呈线性排列，因此数组就是一个线性表。但单用数组来管理数据仍有很多不足，为了更好地实现数据的增删查改等功能，顺序表(Sequence List)油然而生。

        顺序表是线性表的一种，顺序表的底层原理是数组，但实现方式与数组大相径庭，增删查改等功能的实现也是几近全新，切不可照猫画虎光看不写。

顺序表的分类

顺序表可分为两类：静态顺序表、动态顺序表

        其中静态顺序表几乎是在数组的基础上添加增删查改等功能，而动态顺序表可以实现增容等工作，几乎与数组架空。本文重点介绍动态顺序表。

静态顺序表

        静态顺序表类型的声明

#define MAX 100//控制数组的大小
SeqList struct SeqList//静态顺序表
{
	SLDataType data[MAX];
	int size;//记录有效数据的个数
}SeqList;

动态顺序表

        动态顺序表类型的声明

typefef struct SeqList
{
    SLDataType* arr;//指向所开辟的空间的指针
    int size;//记录有效的数据个数
    int capacity;//控制需要开辟的内存容量
}SeqList;

动态顺序表的创建

        （一）动态内存开辟函数的选用

在开辟空间时，第一次开辟需要传空指针，如果内存不够第二次申请空间时就需要扩容，而正好realloc函数能满足这个要求（当给realloc函数传空指针时，该函数功能相当于malloc），所以开辟空间需要选用realloc函数来实现。

        （二）顺序表的初始化

void SeqListInit(SeqList* ps)
{
    ps->arr = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

如上，初始化函数的主要功能是已创建的顺序表变量无用的值全置为0，这一步很有必要，如果不初始化可能会导致空间申请失败等错误。

        （三）顺序表的增容

当空间不够的时候会对已有空间进行增容，增容的方式有多样，在要求严格的情况下可适当调整增容的倍数，一般情况下以两倍的形式增容。空间不够时可分为两种情况，

1.初始内存为0

2.有效数据个数都等于空间容量

第一种情况下需要为顺序表设一个初始的空间，否则无法扩容，因此此处可以巧妙结合三目运算符来实现扩容,如下所示：

int newcapacity = ps->capacity == 0 ? 4 : 2 * capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));

 最后对申请的空间进行检查，如果申请失败返回空指针就退出程序，如果申请成功就将新空间交由arr管理，一下是增容函数全貌

void CheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capasity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* ptr = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (ptr == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = ptr;
	}
}

动态顺序表的接口函数

功能一：增加数据

三种方法：头插、尾插、指定位置插

        1.头插(SLPushFront)

 

如图，头插存在两种情况但由于第二种情况包含有第一种情况，因此可以统一处理。头插需要两个步骤，第一步将顺序表中的所有数据往后挪动一位，第二步再从头部插入数据。 

void SLPushFront(SeqList* ps, SLDataType x)//x为待插入的数据
{
	assert(ps);
	SLCheckCapacity(ps);
	int i = 0;
    //将所有数据往后挪动，为防止数据被覆盖，因此采用从后向前挪
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
    //在头部插入数据
	ps->arr[0] = x;
	ps->size++;
}

        2.尾插(SLPushBack)

void SLPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);//结构体指针不能为空
	SLCheckCapacity(ps);//检查空间是否充足,不足就扩容
	ps->arr[ps->size++] = x;//size++后表示有效数据增加，即扩容成功
 }

        3.指定位置插(SLInsert)

 图中对两种情况都做了分析，事实上第一种情况在第二种情况实现时可以得到解决，为了严谨分析，于是我把这种情况列出来给大家看一下，避免忽视。另外，在避免用户输入越界的pos值，应在函数前加多一条断言，就像这样：

assert(pos >= 0 && pos <= ps->size);

注意这里两边都是闭区间，原因在于当pos等于0时相当于头插，当pos等于size时相当于尾插

最后再结合图中红字的方案就可以写代码了

void SLInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	if (pos < ps->size)
	{
		for (int i = ps->size; i > pos; i--)
		{
			ps->arr[i] = ps->arr[i - 1];
		}
		ps->arr[pos] = x;
		ps->size++;//增加完数据后，别忘了要将有效的数据++
	}
	else
	{
		ps->arr[ps->size++] = x;
	}
}

以上是增加数据的三种方法，其中从指定位置插入包含有头插和尾插两种方法，所有指定插也可以代替二者。 

功能二：删除数据

删除数据的实质是，有效数据减少。具体而言是保证其他数据的有效性的同时，移除待删除数据，并将有效数据个数减少。

删除也有三个方法：头删、尾删、指定位置删

        1.头删(SLPopFront)

void SLPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)//注意结束条件为i < ps->size - 1
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//最后别忘了要让有效数据个数--
}

        2.尾删(SLPopBack)

 

void SLPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;//size--后就无法访问最后一个元素
}

        3.指定位置删(SLErase)

void SLErase(SL* ps, int pos)
{
	assert(ps && ps->size);
	assert(pos >= 0 && pos < ps->size);
	if (pos < ps->size - 1)
	{
		int i = 0;
		for (i = pos; i < ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;
	}
	else
	{
		ps->size--;
	}
}

以上是删除数据的所有方式，经过分析不难发现删除指定位置的方法也包含有头删和尾删这两特例，实际上也可以用删除指定位置的方法来代替头删和尾删，之所以三种方法都分析一遍是因为各自都有使用场景，也因为从简到难更易接收。

 功能三：查找数据

SLDateType SLFind(SL* ps, SLDateType x)//查找数据
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("数据为空，无法查找\n");
		exit(-1);
	}
	else
	{
		int i = 0;
		for (i = 0; i < ps->size; i++)
		{
			if (ps->arr[i] == x)
				return i;
		}
	}
	return -1;//返回-1的原因是顺序表和数组一样从0开始，取不到负数
}

功能四：修改数据

        

void SLModify(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	if (ps->size == 0)
	{
		printf("数据为空，无法查找\n");
		return;
	}
	else
	{
		ps->arr[pos] = x;
	}
	return;
}

---

结语

        以上是动态顺序表的所有接口函数，当然静态顺序表也可以使用但有些地方需要修改。至此顺序表的内容也就算是讲完了，大家有兴趣可以去研究一手通讯录，通讯录的设计底层原理就是用到顺序表，只是外加包装变成了一个小项目仅此。