线性表

线性表(linear list)是n个具有相同特性元素的有限序列 。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

它是最简单的数据结构，也是最常用的数据结构——他的作用就是将数据存起来。

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可分为：

1.静态顺序表：使用定长数据存储。

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

下面的代码实现的是动态顺序表

结构定义

1
2
3
4
5
6
7
typedef int SeqListDataType;
typedef struct SeqList
{
	SeqListDataType* arry;//指向动态开辟的数组
	int size;//数组中有效数据的个数(在数组中说就是最后一个数据的下一个位置，因为数组下标是从0开始的)
	int capacity;//容量空间的大小
}SeqList;

image-20210605131238279

初始化

1
2
3
4
5
6
void SeqListInit(SeqList* ps)
{
	ps->arry = NULL;//可以一上来就给空间，也可以不给空间
	ps->size = 0;
	ps->capacity = 0;
}

销毁

严格来说空间用完之后就要销毁，如果malloc开辟的空间不销毁就会存在内存泄漏。

1
2
3
4
5
6
void SeqListDestory(SeqList* ps)
{
	free(ps->arry);
	ps->arry = NULL;
	ps->capacity = ps->size = 0;
}

打印

1
2
3
4
5
6
7
void SeqListPrint(SeqList* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arry[i]);
	}
}

扩展空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void SeqListCheckCapacity(SeqList* ps)
{
	//如果数组满了——有效的数据个数等于空间容量的总大小
	if (ps->size == ps->capacity)
	{
		//要注意如果满了，就进行扩容，在原来基础上*2，但是开始的空间是0，
		//0*2还是0,所以开始插入的时候要加一个判断
		//如果开始的空间是0，那么就给他赋值4，之后就不是0了，就给他*2
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//realloc扩充原来开辟好的空间
		//如果原来的空间在原来的地方是空，那就他是直接申请一个新的空间就跟malloc是一样的。
		SeqListDataType* tmp = (SeqListDataType*)realloc(ps->arry, newCapacity * sizeof(SeqListDataType));
		//如果扩容失败，给予提示
		if (tmp == NULL)
		{
			printf("realloc is fail!");
			exit(-1);//退出
		}
		else
		{
			//把扩充好的数组传给arry
			ps->arry = tmp;
			ps->capacity = newCapacity;//空间容量大小
		}
	}
}

尾插

1
2
3
4
5
6
7
void SeqListPushBack(SeqList* ps,SeqListDataType x)
{
	SeqListCheckCapacity(ps);
    //顺序表中的数据要依次存储
	ps->arry[ps->size] = x;
	ps->size++;
}

头插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SeqListPushFront(SeqList* ps, SeqListDataType x)
{
	//同尾插-空间不够了需要增容
	SeqListCheckCapacity(ps);
	//从后开始挪
	//注意初识条件-结束条件-迭代过程
	//先找到最后一个位置
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arry[end + 1] = ps->arry[end];
		end--;
	}
	ps->arry[0] = x;
	ps->size++;
}

尾删

1
2
3
4
5
6
7
8
void SeqListPopBack(SeqList* ps)
{
	assert(ps->size > 0);//等于0直接报错，比较粗暴。
	//下面这行代码没用，因为了顺序表中具体的数据个数是由size决定的
	//把这个位置置 成0，万一这个位置本来就是0呢，或者这个位置的数据类型不是int，是double呢，置成0也不合适，没有意义。
	//ps->arry[ps->size - 1] = 0;
	ps->size--;
}

头删

1
2
3
4
5
6
7
8
9
10
11
12
13
void SeqListPopFront(SeqList* ps)
{
	//检查一下还有没有元素，没有就别删了
	assert(ps->size > 0);
	int start = 1;
	//就是用后面的元素将前面的元素给覆盖了，每次消失的都是第一个，其他的依次向前推
	while (start < ps->size)
	{
		ps->arry[start - 1] = ps->arry[start];
		start++;
	}
	ps->size--;
}

在指定位置插入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SeqListInsert(SeqList* ps, int pos, SeqListDataType x)
{
	assert(pos < ps->size);//大于就报错
	//思路：先创建空间，利用循环找到pos这个位置，将元素放入数组，size+1
	//创建空间
	SeqListCheckCapacity(ps);
	//找到最后一个元素
	int end = ps->size - 1;
	while (end >= pos)
	{
		//依次往后推移一位，
		ps->arry[end + 1] = ps->arry[end];
		end--;
	}
	ps->arry[pos] = x;
	ps->capacity++;
}

删除指定位置数据

1
2
3
4
5
6
7
8
9
10
11
12
void SeqListErase(SeqList* ps, int pos)
{
	assert(pos < ps->size);
	//被删除元素后面的位置
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->arry[start - 1] = ps->arry[start];
		start++;
	}
	ps->size--;
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
int SeqListFind(SeqList* ps, SeqListDataType x)
{
    //找到返回下标，找不到返回-1
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arry[i] == x)
		{
			return i;
		}
	}
	return -1;
}

修改

1
2
3
4
5
void SeqListModity(SeqList* ps, int pos, SeqListDataType x)
{
	assert(pos < ps->size);
	ps->arry[pos] = x;
}