【零基础学数据结构】顺序表

目录

1.了解数据结构

什么是数据结构？ 

为什么要进行数据管理？ 

2.顺序表 

顺序表概要解析： 

​编辑顺序表的分类： 

差别和使用优先度： 

1.创建顺序表

1.1顺序表分为静态顺序表和动态顺序表

 1.2顺序表的初始化

 1.3顺序表的销毁

 1.4顺序表的打印

 1.5顺序表的扩容

1.6顺序表的头插，尾插

 1.6.1头插

1.6.2尾插

 1.7顺序表的头删，尾删

 1.7.1头删

1.7.2尾删

 1.8顺序表在指定位置之前插入，删除数据

 1.8.1 插入数据

1.8.2 删除数据

 1.9顺序表数据的查找

 测试代码：

---

 

1.了解数据结构

什么是数据结构？ 

为什么要进行数据管理？ 

 

2.顺序表 

顺序表概要解析： 

顺序表的分类： 

• 静态顺序表
• 动态顺序表 

差别和使用优先度： 

1.创建顺序表

1.1顺序表分为静态顺序表和动态顺序表

 
// 设定类型为一个全新名字，方便后续更改
typedef int SLDataType;
 
// 静态顺序表
 #define N 100
typedef struct SeqList
{
	SLDataType arr[N];//创建数组储存数据
	int size;			//有效数据的数量
}SL;
 
 
// 动态顺序表
typedef struct SeqList
{
	SLDataType* arr;//动态的空间，创建指针变量
	int size;		//有效数据的数量
	int capacity;   //空间的大小容量
}SL;

 1.2顺序表的初始化

void SLInit(SL* ps);

// 顺序表的初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;				//将顺序表指针置为NULL
	ps->size = ps->capacity = 0;//将其他数据置为0
}
 
// 顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)   //判断ps->arr是否为NULL,如果不为NULL,说明空间需要释放
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

 1.3顺序表的销毁

void SLDestroy(SL* ps);

// 顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)   //判断ps->arr是否为NULL,如果不为NULL,说明空间需要释放
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

 1.4顺序表的打印

void SLPrint(SL* ps);

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

 1.5顺序表的扩容

void SLCheckCapacity(SL* ps);

// 顺序表的扩容
void SLCheckCapacity(SL* ps)
{
	// 判断容量是否够用
	if (ps->capacity == ps->size)
	{
		//执行扩容
		
		//检验原先的容量，如果有在原先容量*2，没有的话就先分配4。
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
 
		// 为了防止空间申请失败返回NULL,先用临时变量tmp接收
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
 
		//申请失败提前返回
		if (tmp == NULL)
		{
			printf("perror realloc!");
			return;
		}
 
		//申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

1.6顺序表的头插，尾插

 1.6.1头插

void SLPushFront(SL* ps, SLDataType x);

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);//断言防止传入空指针
 
	// 插入之前判断空间容量是否够
	SLCheckCapacity(ps);
 
	//进行头插
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=ps->arr[2]
	}
	ps->arr[0] = x;
	ps->size++;
}

 

1.6.2尾插

void SLPushBack(SL* ps, SLDataType x);

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//断言防止传入空指针
 
	// 插入之前判断空间容量是否够
	SLCheckCapacity(ps);
 
	//进行尾插
	ps->arr[ps->size++] = x;
}

 

 1.7顺序表的头删，尾删

 1.7.1头删

void SLPopFront(SL* ps);

//头删
void SLPopFront(SL* ps)
{
	assert(ps);//断言防止传入空指针
 
	//防止顺序表没有数据可以删除
	assert(ps->size);
 
	//进行头删操作
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//ps->arr[size-2]=ps->arr[size-1]
	}
	ps->size--;
}

 

1.7.2尾删

void SLPopBack(SL* ps);

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);//断言防止传入空指针
 
	//防止顺序表没有数据可以删除
	assert(ps->size);
 
	//进行尾删操作
	ps->size--;
}

 

 1.8顺序表在指定位置之前插入，删除数据

 1.8.1 插入数据

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

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);//断言防止传入空指针
 
	//判断插入的数据是否合法
	if (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+1]=ps->arr[pos];
		}
		ps->arr[pos] = x;
		ps->size++;
	}
 
}

 

1.8.2 删除数据

void SLErase(SL* ps, int pos);

//在指定位置之前删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);//断言防止传入空指针
 
	//判断删除的数据是否合法
	if (pos >= 0 && pos < ps->size)
	{
		// 删除数据
		for (int i = pos; i < ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];//ps->[size-2]=ps->arr[size-1]
		}
		ps->size--;
	}
}

 

 1.9顺序表数据的查找

int SLFind(SL* ps, SLDataType x); 

// 1.9顺序表数据的查找
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;//返回一个不存在的下标
}

 测试代码：

#include "SeqList.h"
 
void SLText01()
{
	SL sl;
	//初始化
	SLInit(&sl);
	
	//打印
	//SLPrint(&sl);
	
	//增删查改
	
	//头插
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);
	//SLPrint(&sl);// 4 3 2 1
 
	//头删
	/*SLPopFront(&sl);
	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);*/
 
	//尾插
	//SLPushBack(&sl, 1);
	//SLPushBack(&sl, 2);
	//SLPushBack(&sl, 3);
	//SLPushBack(&sl, 4);
	//SLPrint(&sl);// 1 2 3 4
 
	//尾删
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPopBack(&sl);
	//SLPrint(&sl);
 
	在指定位置之前插入数据
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);
	//SLPrint(&sl);// 4 3 2 1
	//SLInsert(&sl, 4, 6);
	//SLPrint(&sl);// 4 3 2 6 1
 
	//在指定位置之前删除数据
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);
	//SLPrint(&sl);// 4 3 2 1
	//SLErase(&sl, 2);
	//SLPrint(&sl);// 4 3  1
 
	// 1.9顺序表数据的查找
	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);
	//SLPushFront(&sl, 3);
	//SLPushFront(&sl, 4);
	//printf("顺序表中有：");
	//SLPrint(&sl);// 4 3 2 1
	//int find = SLFind(&sl, 6);
	//if (find > 0)
	//{
	//	printf("找到了！下标是：%d\n", find);
	//}
	//else
	//{
	//	printf("没有找到！\n");
	//}
 
	//销毁
	SLDestroy(&sl);
 
}
 
int main()
{
	SLText01();
	return 0;
}

 源代码文件：SeqList_2024_4_3 · 14c5b99 · 阳区欠/C语言学习路程 - Gitee.com