顺序表——功能实现

1.0 前言学习顺序表之前，我们需要具备三方面的知识点。指针，结构体，动态内存的开辟。

2.0 线性表

线性表是数据结构中的一种基本形式，是 n 个数据元素的有限序列。线性表中的数据元素之间有序且连续，可以用一组地址连续的存储单元存储。

线性表可以表示一维数组，也可以表示一串具有相同类型的元素。线性表中的元素可以是数字、字符、对象等。线性表有两种基本形式：顺序表和链表。

线性表中的数据结构有哪些相同的特性：

线性表的特性：结构不一定连续，逻辑结构一定连续的。

顺序表的特性：物理结构一定连续的，逻辑结构一定连续的。

本章主要讲的是顺序表。

2.1 顺序表

顺序表和数组的区别：顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。

2.2 顺序表的分类

开辟数组我们有两个方法：

1.静态内存开辟,开辟一个固定的空间。如：int arr[10]={0};

2.动态内存开辟，确定大小之后再去申请空间。如：int *arr

同理，顺序表分类也有两种：

1.静态顺序表定义

代码语言：javascript复制

struct SeqList
{
	int arr[100];//定长数组
	int size;//顺序表当前有效的数据个数
};

2.动态顺序表定义

代码语言：javascript复制

struct SeqList
{
	int* arr;
	int size;//有效的数据个数
	int capcacity;//空间大小
}

这两种哪一个好呢？

举个例子：某app原定只能储存100万的用户信息，但随着app的爆火，越来越多的人注册使用这app，但这个后台只能储存100万，剩下的数据全部丢失，这将是一次重大的事故。

若动态数组，那么我们就能够在空间不够的情况下，再一次进行开辟空间，代码更加灵活。

2.3 顺序表功能的实现

开始之前我们需要创建三个文件，分别是

test.c 顺序表结构声明，顺序表的方法。 SeqList.h 实现顺序表的方法。 SeqList.c 对实现的顺序表进行测试

在之前我们就讲过了多文件的好处，这里就不在重复了。

2.3.1 准备前奏

顺序表的实现需要创建一个动态顺序表。其中包括了有效数据的大小size，已经整个动态空间的大小。

SeqList.h

代码语言：javascript复制

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;//将int重命名，方便后续其他类型的修改
//动态顺序表
typedef struct SeqList 
{
	SLDataType* arr;//指向动态开辟的数组
	int size;       //有效数据个数
	int capacity;   //空间大小
}SL;

//typedef struct SeqList Sl;

text.c

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
int main()
{
	SL s1;//创建变量s1
	return 0;
}

SeqList.c

代码语言：javascript复制

#include"SeqList.h"

接下来就能进入我们函数的实现了。

2.3.2 初始化

代码语言：javascript复制

//初始化
//错误示范
void SLInit(SL ps)
{
	ps.arr = NULL;
	ps.capacity = ps.size = 0;
}




//正确代码
void SLInit(SL * ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

刚刚开始的时候，数组空间还没开辟所以是0；arr也还没有数据所以是空。

坑：错误的代码中采用了传值，而传值实际是是实参，拷贝一份给形参。还没进行初始化没有值。

所以这里要用传地址，用指针来接收。

2.3.3 打印

代码语言：javascript复制

void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i  )
	{
		printf("%d ", s.arr[i]);
	}
	printf("n");
}

完成的函数，要验证它它能不能符合要求，就要打印出来，方便观察。

2.3.4 销毁空间

动态内存用完之后，我们要进行销毁。且将ps置为空，将size和capacity赋为0。

有借有还，再借不难。

代码语言：javascript复制

void SLDestroy(SL * ps)
{
	if (ps->arr)//等价于if(ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

2.3.5 申请空间

代码语言：javascript复制

//申请空间的判断
void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc error");
			exit(1);
		}
		//空间申请成功
		ps->capacity = newCapacity;
		ps->arr = tmp;
	}
}

由于空间的申请不止一个函数需要用到，在这就单独给它封装函数，方便后续的使用。

首先，要判断arr数组空间内存的大小。

如果数组的空间容量Capacity不等于有效数据size，则跳出函数。

相反，相等的情况下，开始开辟空间，创建一个变量newCapacity来储存新的空间容量大小，再创建tmp来存放首元素的地址(防止realloc开辟失败，将原来的arr置为NULL)。并且判断tmp是否开辟成功。

最后将newCapacity赋给capacity，将tmp赋值给arr。

2.3.6 头部插入

代码语言：javascript复制

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = ps->size ; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size  ;
}

头部插入之前要满足两个条件：

传入指针不能为空。
判断是否需要申请空间。

因为这里是头部插入，所以需要讲数组内的数据往后移一位。然后将新的数据插入数组下标为0的地址。最后对size进行 1即可。

2.3.7 删除头部数据

代码语言：javascript复制

void SLPopFront(SL* ps)
{
	assert(ps);
	for (int i = 0; i > ps->size-1; i  )
	{
		ps->arr[i] = ps->arr[i   1];
	}
	ps->size--;
}

删除头部数据之前，首先要assert断言传入的指针是不是空指针。删除头部数据只需要将后一位往前移，循环往复，最后size进行-1。

2.3.8 尾部插入

代码语言：javascript复制

void SLPushBack(SL*ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size  ] = x;
	
}

尾插相比于头插会简单点，但同样也是需要断言，看传入的指针是否为空。在末尾插入数据需要在size处插入新的数据，然后对size进行 1即可。

2.3.9 删除尾部数据

代码语言：javascript复制

void SLPopBack(SL* ps)
{
	assert(ps);
	--ps->size;
}

同样尾删也是需要断言，看传入的指针是否为空。然后厎size-1就行了，有效数据减一，不会影响其他功能。

2.3.10 指定位置之前插入

代码语言：javascript复制

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i >  pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size  ;
}
//pos 表示数组的下标值。

掌握了头插和尾插，那么在指定位置之前插入数据就不难，这其实就是头插和尾插的结合。

在插入之前，要用assert断言传入指针是否为空。pos只能在0~size之间插入数据，当传入的数据不是这个范围，程序就会出错，所以这里也需要用assert来断言assert(pos >= 0 && pos <= ps->size)。

假设在下标为2的位置插入新的数据，就需要讲下标为2的数据移到后面，从后往前移（防止数据被覆盖），然后对size进行 1。

中间的值会了，插入两边就是头插和尾插，前面已经讲过了，这里就都是一样的。

2.3.11 指定位置之前删除

代码语言：javascript复制

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

在删除数据之前，要用assert断言传入指针是否为空。pos只能在0~size之间删除数据，但size指向的地址是没有数据的，当传入的数据不是这个范围，程序就会出错，所以这里也需要用assert来断言assert(pos >= 0 && pos < ps->size)。

接下来就是删除数据的部分，假设删除数组下标为2内容，只需要将后面的的数组往前放，循环往复，最后对size进行-1。

2.3.12 寻找指定数字

代码语言：javascript复制

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;
	}
}

寻找指定数据，对传入的地址进行断言，然后用一个for循环来寻找数组的值，再用if-else来判断，若ps->arr[i] == x则返回的值。相反则返回-1。

3.0 完整代码

3.1 SeqList.h

代码语言：javascript复制

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList 
{
	SLDataType* arr;
	int size; //有效数据个数
	int capacity; //空间大小
}SL;

//typedef struct SeqList Sl;
//开辟空间
void SLCheckCapacity(SL* ps);

//初始化
void  SLInit(SL* ps);

//打印
void SLPrint(SL s);

//头插
void SLPushFront(SL* ps, SLDataType x);

//尾插
void SLPushBack(SL* ps, SLDataType x);

//头删
void SLPopFront(SL* ps);

//尾删
void SLPopBack(SL* ps);

//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x);

//指定位置之前删除
void SLErase(SL* ps, int pos);

//查找数据
int SLFind(SL* ps, SLDataType x);

//销毁
void SLDestroy(SL* ps);

3.2 SeqList.c

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS

#include"SeqList.h"
//申请空间的判断
void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc error");
			exit(1);
		}
		//空间申请成功
		ps->capacity = newCapacity;
		ps->arr = tmp;
	}
}
//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i  )
	{
		printf("%d ", s.arr[i]);
	}
	printf("n");
}

//销毁
void SLDestroy(SL * ps)
{
	if (ps->arr)//等价于if(ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = ps->size ; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size  ;
}


//尾插
void SLPushBack(SL*ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size  ] = x;
	
}


//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	ps->arr[0] = -1;
	for (int i = 0; i > ps->size-1; i  )
	{
		ps->arr[i] = ps->arr[i   1];
	}
	ps->size--;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	--ps->size;
}


//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	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);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i  )
	{
		ps->arr[i] = ps->arr[i   1];
	}
	ps->size--;
}

//寻找指定数字
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.3 test.c

代码语言：javascript复制

void SLTest01()
{
	SL sl;
	SLInit(&sl);
	//增删查改操作
	//测试尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);//1 2 3 4

	//SLPushFront(&sl, 5);
	//SLPushFront(&sl, 6);

	//测试尾删
	SLPopBack(&sl);
	SLPrint(sl);//1 2 3 
	SLPopBack(&sl);
	SLPrint(sl);
	SLPopBack(&sl);
	SLPrint(sl);
	SLPopBack(&sl);
	SLPrint(sl);
	SLPopFront(&sl);
	SLPrint(sl);
	//...........
	SLDestroy(&sl);
}

void SLTest02()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);//1 2 3 4
	//测试指定位置之前插入数据
	//SLInsert(&sl, 1, 99);
	//SLInsert(&sl, sl.size, 88);

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

	//测试顺序表的查找
	int find = SLFind(&sl, 40);
	if (find < 0)
	{
		printf("没有找到！n");
	}
	else {
		printf("找到了！下标为%dn",find);
	}
	SLDestroy(&sl);
}

int main()
{
	//SLTest01();
	//SLTest02();
	ContactTest01();
	return 0;
}

ps size 数据数组指针

0 人点赞

顺序表——功能实现

1.0 前言 学习顺序表之前，我们需要具备三方面的知识点。指针，结构体，动态内存的开辟。

2.0 线性表

2.1 顺序表

2.2 顺序表的分类

2.3 顺序表功能的实现

2.3.1 准备前奏

2.3.2 初始化

2.3.3 打印

2.3.4 销毁空间

2.3.5 申请空间

2.3.6 头部插入

2.3.7 删除头部数据

2.3.8 尾部插入

2.3.9 删除尾部数据

2.3.10 指定位置之前插入

2.3.11 指定位置之前删除

2.3.12 寻找指定数字

3.0 完整代码

3.1 SeqList.h

3.2 SeqList.c

3.3 test.c

1.0 前言学习顺序表之前，我们需要具备三方面的知识点。指针，结构体，动态内存的开辟。