数据结构初识及顺序表详解

目录

1.数据结构相关概念

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

3.顺序表

1.概念

2.结构

3.顺序表的类型

3.1静态顺序表

3.2动态顺序表

4.顺序表的实现

1.准备工作

2.基础接口实现

2.1创建动态顺序表结构

2.2顺序表初始化

2.3顺序表的销毁

2.4顺序表的打印

3.顺序表的扩容接口

4.顺序表的插入数据接口

4.1尾插接口

4.2 头插接口

4.3 指定位置插入接口

5.顺序表的删除功能接口

5.1 尾删接口

5.2头删接口

5.3指定位置删除接口

6.顺序表的查找实现接口

5.总代码

SeqList.h

SepList.c

test.c

我们在写程序的时候，会出现许多的数据，如果我们想要修改某一个值或者删除和添加一个数据的时候就会非常困难，尤其是数据量庞大的时候，这时候数据结构就出来了

1.数据结构相关概念

数据结构是计算机存储、组织数据的⽅式。

就好比如，给小学生编排座位来方便管理

而数据结构就是这样的作用

1能够存储数据

2存储的数据能够⽅便查找

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

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

而我们对数据进⾏增删改查等操作就相当数据进入不同的接口

我们来举个例子：最基础的数据结构——》数组。

int arr[100]={1,2,3,4};

当我们想要修改一个数据时就可以arr[pos]=x

当我们想要删除一个数据时：找到数据，把后面的数据往前覆盖

当我们想要插入一个数据时：找到数据，把后面的数据往后移动，此时还要判断数组是否溢出

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

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

就出现了顺序表这样的数据结构

3.顺序表

1.概念

了解顺序表之前我们要先知道线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串......

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构（数据在内存中的存储位置）上并不⼀定是连续的

而接下来我们要学习的顺序表属于线性表的一种，顺序表在逻辑和物理结构上都是连续的

2.结构

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

3.顺序表的类型

3.1静态顺序表

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

 静态顺序表(这里拿里面存储的整形举例)
 typedef int SLDataType;
 #define N 100 //方便我们之后修改数组长度
 typedef struct SeqList
 {
     SLDatatype arr[N];
     int size;//size是有效数据的个数
 }SL;
  
我们知道数组不只有int类型，同样顺序表也是如此
因此我们可以利用 typedef方便以后修改使用不同的类型

我们发现使用静态顺序表时，如果我们N给小的话就会导致空间不够，N给大就会导致空间浪费，而这就是静态顺序表缺陷

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

3.2动态顺序表

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;// 指向数组的指针
	int capacity;   // 记录动态顺序表 申请空间的大小 
	int size;       // 记录顺序表当前有效的数据个数
}SL;

而动态顺序表我们在程序进行的时候自动的可以根据数据进行扩容，因此接下来顺序表的实现，我将要用动态顺序表

4.顺序表的实现

1.准备工作

创建三个文件

1、头文件SeqList.h  是来声明接口函数，定义顺序表，将几个公共用到的库函数集合起来
2、源文件SeqList.c  是用来具体实现接口
3、源文件test.c  用于接口的测试工作 ，即具体的使用场景

我们之后学习数据结构的时候都要创建这三个文件

2.基础接口实现

2.1创建动态顺序表结构

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;// 指向数组的指针
	int capacity;   // 记录动态顺序表 申请空间的大小 
	int size;       // 记录顺序表当前有效的数据个数
}SL;

2.2顺序表初始化

void SLInit(SL* ps)//由于是对数据的修改，因此传址
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

2.3顺序表的销毁

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

2.4顺序表的打印

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i) 
   {
       printf("%d ", ps->arr[i]);
       printf("\n");
   } 
}
// 打印顺序表：这里可以传值 也可传址 ，
// 因为不需要对数据进行修改(可以传值)，
//为了保持接口一致性(其他接口都是传址)，这里直接使用传址

3.顺序表的扩容接口

void SLCheckCapacity(SL* ps)
{
	//当容量capacity == size 时，说明数组已经满了，需要扩容
	if (ps->size == ps->capacity)
	{
		// 开辟空间时注意，当capacity初始化为 0 时，直接相乘的结果还是 0 
		// 所以要先判断一下, 并且需要做申请空间是否成功的判断
        // 同时先给一个临时变量，否则开辟空间失败，数据就会泄露
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; 
        // 每次两倍空间扩容（大家可以记住，每次扩容两倍扩就行）
		SLDataType* cmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (cmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		// 扩容成功
		ps->arr = cmp;
		ps->capacity = newCapacity;
	}


}

4.顺序表的插入数据接口

4.1尾插接口

// （1）尾插法：有三种情况：1 头部非空，尾部还有空间；
//                        2 空间为空；
//                        3 空间数据满了
void SLPushBack(SL* ps, SLDataType x)
{
	// 先判断指针是否非空
	assert(ps);
	// 空间不够，扩容
	SLCheckCapacity(ps);
	// 空间足够，直接插入
    //size是记录尾数据下一位的位置
	ps->arr[ps->size++] = x;
}

4.2 头插接口

// 头插法
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[0] = x; // 将插入数据放在头部
	ps->size++;
}

4.3 指定位置插入接口

// 指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	// pos可能越界, 要断言判断一下
	assert(0 <= pos && pos <= ps->size); // 当pos==size相当尾插
	// 判断是否有足够的空间
	SLCheckCapacity(ps);
 
	// 在pos位置中插入数据 x ，将pos位置起的后面数据向后挪动
	for (int i = ps->size; i >= pos + 1; --i) // 让pos这个位置空出来
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;//插入数据
	ps->size++;
}

5.顺序表的删除功能接口

5.1 尾删接口

void SLPopBack(SL* ps)
{
	// 删除前 检查：顺序表非空才能执行删除，同时 size 不能为 0
	assert(ps);
	assert(ps->size);// 顺序表不为空
	ps->size--; 
    // 直接 size-- 将 size 位置的数值丢出我们的有效数据空间，
    // 那个位置不属于有效空间了，则类似达到删除的效果
}

5.2头删接口

void SLPopFront(SL* ps)
{
	// 删除前检查顺序表非空才能执行删除，同时 size 不能为 0
	assert(ps);
	assert(ps->size);
    
	// 将 后面的 数据 向前移动注意边界
	for (int i = 1; i < ps->size; ++i)
    {
        ps->arr[i - 1] = ps->arr[i];
    } 
	ps->size--;
}

5.3指定位置删除接口

void SLErase(SL* ps, int pos)
{
	assert(ps);
	//指定的位置可能越界, 要断言判断一下
	assert(0 <= pos && pos < ps->size); // 注意 不能等于 size
	for (int i = pos + 1; i < ps->size; ++i)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

6.顺序表的查找实现接口

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

5.总代码

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int Capacity;
	int size;
}SL;
 
// 一、初始化
void SLInit(SL* ps);
 
// 二、 尾插法
void SLPushBack(SL* ps, SLDataType x);
 
// 二、 头插法
void SLPushFront(SL* ps, SLDataType x);
 
// 三、尾删法
void SLPopBack(SL* ps);
 
// 四、头删法
void SLPopFront(SL* ps);
 
// 五、指定位置删除
void SLErase(SL* ps, int pos);
 
// 六、指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
 
//顺序表的扩容检查(扩容的原则,以及扩容的方法)
void SLCheckCapacity(SL* ps);
 
// 打印函数
void SLPrint(SL* ps);

SepList.c

#include"SeqList.h"
 
 
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->Capacity = ps->size = 0;
}
 
// 开辟空间函数
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->Capacity)
	{
		int NewCapacity = ps->Capacity == 0 ? 4 : 2 * (ps->Capacity);
		SLDataType* cmp = realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		if (cmp == NULL)
		{
			perror("realloc fail !");
			exit(1);
		}
		ps->arr =cmp;
		ps->Capacity = NewCapacity;
	}
}
// 二、 尾插法
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps); 
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = 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[0] = x;
	ps->size++; // 别忘记了
}
 
// 三、尾删法
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}
 
// 四、头删法
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->size--;
}
 
// 五、指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(0 <= pos && pos < ps->size);
	for (int i = pos; 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(0 <= pos && pos < ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i >= pos + 1; --i)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++; 
}
 
// 打印函数
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

test.c

#include"SeqList.h"
void slTest01()
{
	SL sl;  // 创建一个结构体变量 sl
	SLInit(&sl); // 这里需要 传地址：才能真正被初始化
 
	//测试尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4); // ctrl + d == ctrl + c + v
	printf("测试尾插: ");
	SLPrint(&sl);
 
	// 测试头插
	SLPushFront(&sl, 10);
	printf("测试头插: ");
	SLPrint(&sl);
 
	// 测试 尾删
	SLPopBack(&sl);
	printf("测试尾删: ");
	SLPrint(&sl);
 
	// 测试 头删
	SLPopFront(&sl);
	printf("测试头删: ");
	SLPrint(&sl);
 
	// 测试 指定位置插入
	SLInsert(&sl, 1, 15);
	printf("指定插入: ");
	SLPrint(&sl);
 
	SLErase(&sl, 1);
	printf("指定删除: ");
	SLPrint(&sl);
}
int main()
{
	slTest01(); // 第一个测试函数
	return 0;
}

1.不管写任意一种接口函数，我们在处理之前都要进行断言，避免穿过来的是NULL指针  assert(ps->arr) ;
 2.在进行扩容操作 的时候别忘记了 realloc要将新空间的地址和容量 更新给自己的数组和容量变量
 3.进行插入操作之后  要把size++;  在进行删除操作的时候要进行size--
 4、插入操作 和 删除操作 用到循环 数据整体后移或前移一定要注意边界