顺序表的增、删、改、查

小伙伴们好，学完C语言，就要开始学数据结构了，数据结构也是非常重要的，今天我们主要来学习在数据结构中最常用的增删改查操作。话不多说，一起来学习吧

1.数据结构相关概念

1.什么是数据结构？

概念：数据结构是计算机存储、组织数据的?式。数据结构是指相互之间存在?种或多种特定关系

的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么?式构成，以及数据元素之间呈现的结构。

总结：

1）能够存储数据（如顺序表、链表等结构）

2）存储的数据能够?便查找

2、为什么需要数据结构？

如图中所?，不借助排队的?式来管理客?，会导致客?就餐感受差、等餐时间?、餐厅营业混乱等情况。同理，程序中如果不对数据进?管理，可能会导致数据丢失、操作数据困难、野指针等情况。通过数据结构，能够有效将数据组织和管理在?起。按照我们的?式任意对数据进?增删改查等操作。

最基础的数据结构：数组。

【思考】有了数组，为什么还要学习其他的数据结构？

假定数组有10个空间，已经使?了5个，向数组中插?数据步骤：

求数组的?度，求数组的有效数据个数，向下标为数据有效个数的位置插?数据（注意：这?是

否要判断数组是否满了，满了还能继续插?吗）.....

假设数据量?常庞?，频繁的获取数组有效数据个数会影响程序执?效率。

结论：最基础的数据结构能够提供的操作已经不能完全满?复杂算法实现。

2.顺序表

2.1 顺序表的概念及结构

1.线性表

线性表（ linear list ）是n个具有相同特性的数据元素的有限序列。 线性表是?种在实际中?泛使

?的数据结构，常?的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的?条直线。但是在物理结构上并不?定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

案例：蔬菜分为绿叶类、?类、菌菇类。线性表指的是具有部分相同特性的?类数据结构的集合

顺序表：逻辑结构是线性的，物理结构是连续的

2.2顺序表分类

? 顺序表和数组的区别

????????? 顺序表的底层结构是数组，对数组的封装，实现了常?的增删改查等接?

? 顺序表分类

????????? 静态顺序表

????????????????概念：使用定长数组存储元素

静态顺序表缺陷：空间给少了不够?，给多了造成空间浪费

? 动态顺序表

3.动态顺序表的实现

首先我们要创建3个文件，分别是1个头文件SeqList.h，2个源文件SeqList.c和test.c.它们的作用分别是：

SeqList.h：头文件的作用是定义顺序表的结构，顺序表要实现的接口/方法

SeqList.c:具体实现顺序表里定义的接口/方法

test.c:测试动作：测试顺序表

OK,文件准备好了，现在就开始写代码了

首先我们要给数据类型起一个别名，为什么呢？假设我们写了1000行代码，里面使用到了非常多的数据类型，假定全是int类型，有一天别人让你把一些int类型改成char类型，那么你就要一个一个的把int改成char，虽然你们想说不是可以一键替换吗，这个方法也可以，但是不是全部都要改成char类型，这不是最佳的方法。所以作为程序员我们要专业一点，于是就要给自定义的给int类型取个别名，取什么名字可以自己决定，专业的人就要干专业的事。比如说我们可以改成这个

typedef int SLDataType;

这样就能解决上面的问题了，你想要改成什么数据类型，就只需要把int改成你要的类型。是不是很方便呢。

我们首先要做一些准备工作，方便为接下来的操作做准备

3.1定义结构体

typedef struct SeqList  
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;   //记录顺序表的空间大小
	int size;       //记录顺序表当前有效的数据个数
}SL;

细心的小伙伴们发现我也给结构体取了一个别名SL，这样也是为了方便接下来的使用。

当然你也可以这样写

struct SeqList  
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;   //记录顺序表的空间大小
	int size;       //记录顺序表当前有效的数据个数
};

typedef struct SeqList SL;  

3.2 结构体的初始化和销毁

在SeqList.h文件中定义初始化和销毁的函数，具体实现方法要在SeqList.c文件中实现

可能有人会这么写

这样写会报错，因为这样写是传值调用，而我们要传地址。所以正确写法是下面这种

void SLInit(SL* ps);
void SLDestroy(SL* ps);

void SLInit(SL* ps)//ps是形参
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

我们可以测试一下

好了，这么写没有问题。

好了，准备工作基本完成。正式开始我们的增删改查吧。

3.3插入数据：尾插和头插

首先要分析空间够不够。

空间足够：直接插入，假设插入的数据是x=6，即arr[size]=6，size是有效数据的下一个

空间不够：扩容。那么扩容的方法有哪些呢？

1. 一次扩充一个空间：插入一个元素还不会造成空间浪费
2. 一次扩容固定个大小空间（10，100……）
3. 成倍数的增加（1.5倍，2倍）

第一个方法虽然不会造成空间的浪费，但是由于扩容的频率太高会造成程序效率低下

第二个方法空间给小了，还需要继续扩容，也会造成程序效率低下，给大了又可能会造成空间的浪费。

这里我推荐第三个方法，成2倍数的增加（依次扩大4，8，16，32……个空间）数据插入的越多，扩容的空间越来越大，数据和扩容量成正相关，浪费也不会造成太多的浪费。扩容的方法是使用realloc函数，realloc函数使用方法可以看我这篇文章http://t.csdnimg.cn/rwb7g

头插的难点是如何将数据往后挪动

如果直接在第一个位置插入数据，那么就会造成数据丢失 ！所以就要从后往前挪动，把第i个位置移到第i-1的位置处。

由于头插和尾插都要判断是否扩容，所以我们要将扩容空间单独写一个函数，这样空间不够的时候可以直接调用

扩容函数

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//扩容成倍数增加，每次扩容2倍
		//ps->arr=(SLDataType*)realloc(ps->arr,2 * ps->capacity)
		//不能这样写，因为初始化capacity为0
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要乘以数据类型的大小
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//扩容失败直接中断程序
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//顺序表的头部/尾部的插入
void SLPushBack(SL* ps,SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插

void SLPushBack(SL* ps, SLDataType x)//尾插
{
	assert(ps != NULL);

	//空间不够，扩容。当capacity <= size时
	SLCheckCapacity(ps);
	//空间足够，直接插入。当capacity>size时
	ps->arr[ps->size++] = x;
	//ps->size++;
}

void SLPushFront(SL* ps, SLDataType x)//头插
{
	assert(ps != NULL);

	//判断是否扩容
	SLCheckCapacity(ps);
	//旧数据往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

测试尾插

测试头插

打印函数

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

ok,扩容没有问题，这样就说明增加操作没有问题了。另外不能传入一个空值，所以要进行assert断言。

3.4 删除数据：头删和尾删

删除数据要分两种情况：顺序表为空，则不能进行删除；顺序表不为空，尾删则删除最后一个有效数据，size--。头删就要删除第一个数据，然后把后面的数据往前挪动

//顺序表的头部/尾部的删除
void SLPoBack(SL* ps);
void SLPoFront(SL* ps);

//顺序表的头部/尾部的删除
void SLPoBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);//顺序表为空不能进行删除

	//顺序表不为空
	ps->size--;
}

void SLPoFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);//顺序表为空不能进行删除

	//不为空执行挪动操作,后面的数据往前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

测试尾删

测试头删

?3.5 指定位置删除或者插入数据

指定位置之前插入数据

void SLInsert(SL* ps, int pos, SLDataType x);

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//pos不能超过当前顺序表的有效数据
	SLCheckCapacity(ps);//检查是否有空间可以插入

	//pos及之后的数据往后挪动一位，pos空出来,size++
	for (int i=ps->size; i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

?测试：

删除指定位置的数据

void SLErase(SL* ps, int pos);

void SLErase(SL* ps, int pos)
{
	assert(ps != NULL);
	assert(pos >= 0 && pos < ps->size);//只能对size之前的数据进行删除
	
	//pos以后的数据往前挪动一位
	for (int i=pos; i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

测试

3.6 查找数据

int SLFind(SL* ps, SLDataType x);

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

测试

3.7 修改数据

void SLRevise(SL* ps,int pos,SLDataType x);

void SLRevise(SL* ps,int pos,SLDataType x)
{
	if (pos >= ps->size)
		printf("修改失败!要修改的元素不存在\n");
	else
	{
		printf("修改成功,新数据为：");
		ps->arr[pos] = x;
	}
}

测试?

4.完整代码呈现

?SeqList.h

#pragma once
//头文件的作用是定义顺序表的结构，顺序表要实现的接口/方法
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//动态顺序表
//typedef Info SLDataType;

typedef int SLDataType;
typedef struct SeqList  //方法一
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;   //记录顺序表的空间大小
	int size;       //记录顺序表当前有效的数据个数
}SL;

//typedef struct SeqList SL;   //方法二

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);

//顺序表的头部/尾部的插入
void SLPushBack(SL* ps,SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插

//顺序表的头部/尾部的删除
void SLPoBack(SL* ps);
void SLPoFront(SL* ps);

//指定位置之前插入数据
//删除指定位置的数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

//修改数据
void SLRevise(SL* ps,int pos,SLDataType x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
//具体实现顺序表里定义的接口/方法
#include"SeqList.h"
//初始化和销毁
void SLInit(SL* ps)//ps是形参
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//扩容成倍数增加，每次扩容2倍
		//ps->arr=(SLDataType*)realloc(ps->arr,2 * ps->capacity)
		//不能这样写，因为初始化capacity为0
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要乘以数据类型的大小
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//扩容失败直接中断程序
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//顺序表的头部/尾部的插入
void SLPushBack(SL* ps, SLDataType x)//尾插
{
	assert(ps != NULL);

	//空间不够，扩容。当capacity <= size时
	SLCheckCapacity(ps);
	//空间足够，直接插入。当capacity>size时
	ps->arr[ps->size++] = x;
	//ps->size++;
}

void SLPushFront(SL* ps, SLDataType x)//头插
{
	assert(ps != NULL);

	//判断是否扩容
	SLCheckCapacity(ps);
	//旧数据往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//顺序表的头部/尾部的删除
void SLPoBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);//顺序表为空不能进行删除

	//顺序表不为空
	ps->size--;
}

void SLPoFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);//顺序表为空不能进行删除

	//不为空执行挪动操作,后面的数据往前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//pos不能超过当前顺序表的有效数据
	SLCheckCapacity(ps);

	//pos及之后的数据往后挪动一位，pos空出来,size++
	for (int i=ps->size; i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps != NULL);
	assert(pos >= 0 && pos < ps->size);//只能对size之前的数据进行删除
	
	//pos以后的数据往前挪动一位
	for (int i=pos; i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

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

//修改数据
void SLRevise(SL* ps,int pos,SLDataType x)
{
	if (pos >= ps->size)
		printf("修改失败!要修改的元素不存在\n");
	else
	{
		printf("修改成功,新数据为：");
		ps->arr[pos] = x;
	}
}

void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
//测试动作：测试顺序表
#include"SeqList.h"

void slTest01()
{
	SL sl;
	SLInit(&sl);//传址调用

	//测试尾插
	/*SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);	*///1 2 3 4
	//SLPushBack(&sl, 5);
	//SLPrint(&sl);	//1 2 3 4



	测试头插
	/*SLPushFront(&sl, 5);
	SLPushFront(&sl, 6);
	SLPushFront(&sl, 7);
	SLPrint(&sl);*/

	//测试尾删
	/*SLPoBack(&sl);
	SLPoBack(&sl);
	SLPrint(&sl);*/

	//测试头删
	/*SLPoFront(&sl);
	SLPoFront(&sl);
	SLPrint(&sl);*/

	//测试指定位置插入
	//SLInsert(&sl, 0, 100);
	//SLPrint(&sl);
	//SLInsert(&sl, sl.size, 200);//在size位置插入数据
	//SLPrint(&sl);

	//测试删除指定位置的数据
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLErase(&sl, 2);
	SLPrint(&sl);
	/*SLErase(&sl, sl.size - 1);
	SLPrint(&sl);*/
    
    //修改数据
	SLRevise(&sl, 1, 5);
	SLPrint(&sl);
	SLRevise(&sl, 4, 5);
}

void slTest02()
{
	SL sl;
	SLInit(&sl);//传址调用

	//测试尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	//测试查找
	int ret = SLFind(&sl, 2);
	if (ret < 0)
	{
		printf("数据不存在，查找失败！");
	}
	else {
		printf("数据找到了，在下标为%d的位置\n", ret);
	}
}

//void slTest03()
//{
//	SL sl;
//	SLInit(&sl);
//	SLDestroy(&sl);
//}

int main()
{
	//slTest01();
	slTest02();
	//slTest03();
	return 0;
}

终于大功告成了，感谢小伙伴们能看到这里，说明你们都想学好C语言，小伙伴们，我们一起加油。根据这个增删查改，我们就可以写出一个小程序了，那么就是通讯录的实现。等我有时间了我也会把通讯录的实现分享出来，供大家学习参考。感谢各位观看。